Oefeningen
1. Een alfabet is een verzameling symbolen, bvb. {a, b, c} of {1, 2, 3} of
{koe, paard, varken}. Als Σ een alfabet is, dan is Σi de verzameling van
alle woorden over Σ van lengte i.
Σ0 = {}
Σ1 = Σ
Σ2 = Σ × Σ
Σ3 = Σ × Σ × Σ
Algemeen:
Σ0 = {}
Σi = Σi−1 × Σ
Σ∗ = i≥0 Σi
S
Gegeven Σ = {a, b}. Bereken Σ0 , Σ1 , Σ2 , Σ3 .
2. Op Σ∗ is een ‘concatenatie’ operatie gedefineerd:
. : Σ∗ × Σ∗ → Σ∗
die 2 woorden over Σ∗ aaneenplakt (concateneert). Bvb., abc.de = abcde.
Verder is, voor w ∈ Σ∗ , wr de omgekeerde versie van w.
(a) Defineer .r .
(b) Bereken (abcd)r volgens de definitie.
(c) Toon aan dat (wa)r = awr .
r
(d) Toon aan dat wr = w.
3. Schrijf het alfabet van de λ-calculus op.
4. Schrijf het alfabet van de propositielogica op.
5. Definieer d : Σ∗ × Σ → Σ∗ door
d(, a) =
d(a, a) =
d(b, a) = b als b 6= a
d(cx, a) = d(c, a)d(x, a)
en dit ∀a, b, c ∈ Σ en ∀x ∈ Σ∗
(a) Wat doet d informeel ?
(b) Toon aan dat d en .r commuteren: (d(w, a))r = d(wr , a), ∀w ∈ Σ∗ en
∀a ∈ Σ.
1
, (c) Toon aan dat d commutatief is in haar 2de argument: d(d(w, a), b) =
d(d(w, b), a) voor alle w ∈ Σ∗ en voor alle a, b ∈ Σ.
6. Bekijk de definitie van de propositieformules P ROP ⊂ Σ∗ .
(a) Waarvoor dient de afsluitende stap ?
(b) Zijn de volgende formules geldige formules? Zo ja, teken hun con-
structieboom. Zo neen, zeg wat er fout loopt.
i. ((p → q) ∨ ¬r)
ii. (p ∨ q ∨ r)
iii. (((p ∨ q) ∧ r) → (r ∨ ¬p))
7. Geef de volgende zinnen weer in propositionele notatie:
(a) ‘Als de bus niet komt, komen de tram en de trein’
(b) ‘Als de tram komt als de trein niet komt, dan komen de trein en de
bus niet allebei’
8. Geef alle formules die met haakjes invoegen te maken zijn uit p ∧ ¬q → r,
met bijbehorende constructiebomen.
9. Kan je een efficiëntere representatie bedenken voor constructiebomen. Doe
dit voor de formules uit oefening 6b.
10. (a) Definieer inductief rijen gebalanceerde haakjes.
(b) Definieer op een inductieve manier een syntax voor natuurlijke rekenkundige
expressies. Maak gebruik van IN en van {(, ), +, −, ∗, /}.
Teken bomen in de stijl van oefening 9 voor volgende expressies.
i. (3 + 4) ∗ 7
ii. ((8 − 5) + (6/2))
11. Schrijf de volgende formules op in prefix en postfix notatie.
(a) (1 + ((2 ∗ 7) − 5))
(b) ((3 + 4) ∗ (8/2))
(c) (((q ↔ r) → p) ∧ ¬p)
12. Voer volgende substituties met de hand uit
(a) [(q ↔ r)/p]¬p
(b) [(q → s)/p](p → q)
(c) [((q ∨ s) → ¬p)/r](p → p)
13. Welke getallen x voldoen aan de volgende condities :
(a) (¬(p ∧ q) ∧ r)
(b) ((¬p ∧ q) ∧ r)
(c) ¬(p ∧ (q ∧ r))
waarbij p =“x ≤ 1”, q =“x ≤ 3” en r =“x ≥ 2”.
2
, 14. Zij v de waardering gedefinieerd door v(p) = 0 en v(q) = 1.
(a) Wat is v(p ∧ q) en v(p ↑ q) ?
(b) Toon aan waar het boek te kort schiet in de definitie van semantiek.
(c) Probeer de exacte definities te formuleren.
(d) Geef exacte semantiek aan de standaardconnectieven.
(e) Bereken v(((p ∧ q) → r)) als v(p) = 0, v(q) = 1 en v(r) = 0.
15. Geef waarheidtabellen op twee manieren voor
(a) (¬p ∨ ¬q)
(b) p ∧ (q ∧ p)
(c) (¬p ∧ (¬q ∧ r)) ∨ ((q ∧ r) ∨ (p ∧ r))
16. We voeren een nieuw connectief ∆ in waarvan de betekenis door de vol-
gende waarheidstabel is gegeven:
p q p∆q
0 0 0
0 1 1
1 0 1
1 1 0
(a) Vind nu een propositie waarin alleen p, q en de connectieven ¬, ∧, ∨
voorkomen, die dezelfde eindkolom in een waarheidstabel oplevert.
(b) Wat is de intuı̈tieve betekenis van ∆?
(c) Druk ook → en ↔ uit m.b.v. ¬, ∧, ¬.
17. Rekenen binnen een computer gebeurt binair. Zij (p1 , p2 , p3 , p4 , p5 , p6 , p7 , p8 )
en zij (q1 , q2 , q3 , q4 , q5 , q6 , q7 , q8 ) twee binaire getallen (laten we afspreken
dat p1 en q1 de minst-significante cijfers voorstellen). Net zoals gewoon
decimaal optellen maakt binair optellen gebruik van twee mechanismen:
één mechanisme om een reeks cijfers te combineren tot een nieuw cijfer
(bvb voor 5 + 8 is het nieuwe cijfer 3) en een ander mechanisme om te
weten wat de overdracht is (bvb 5 + 8 heeft als overdracht 1, t.t.z. “één
onthouden”). Net zoals bij decimaal rekenen zowel het resulterend cijfer
als de overdracht begrensd zijn door 9, is bij binair rekenen de uitkomst
en de overdracht beperkt door 1.
p q p q p q p q p q p q p q p q
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8
overflow
carry
result
Figure 1: De full adder
3
, (a) Vind een logisch connectief om het cijfer bij de optelling van twee
bits p en q te bepalen.
(b) Vind een logisch connectief om de overdracht bij optelling van 2 bits
te bepalen.
(c) Bovenstaande schakeling (de “full adder”) rekent de som uit van 2 bi-
naire getallen (p1 , p2 , p3 , p4 , p5 , p6 , p7 , p8 ) en (q1 , q2 , q3 , q4 , q5 , q6 , q7 , q8 ).
Geef voor iedere digit van het resultaat een logische formule en geeft
een logische formule voor de overflow. Er zal natuurlijk steeds gerek-
end worden met v(c1 ) = 0
18. Bepaal M OD(ϕ) voor volgende formules:
(a) ϕ = ((¬p ∨ q) ↔ (p → q))
(b) ϕ = (q ∧ (¬p ∨ p))
(c) ϕ = (q ∧ (¬p ∧ p))
19. Bepaal alle modellen van volgende formuleverzamelingen (t.t.z. M OD(Σ)):
(a) Σ = {((p ↔ q) ↔ ((p → q) ∧ (q → p)))}
(b) Σ = {((p ↔ q) ↔ ((p → q) ∧ (q → p))), (p ∨ q)}
Wat gebeurt er met M OD(Σ) als je Σ groter maakt ?
20. Gebruik modeleliminatie om de volgende problemen op te lossen:
(a) i. Als Formele Methoden veel blokwerk is, of een slechte assistent
heeft, dan is het een moeilijk vak.
ii. Als Formele Methoden plezant is, heeft het geen slechte assistent.
iii. Als Formele Methoden veel blokwerk is, of als het geen slechte
assistent heeft, dan is het een plezant vak.
iv. Formele Methoden is plezant enkel en alleen als er veel blokwerk
aan is. Bovendien doet de assistent het fantastisch.
Wat zijn de eigenschappen van het vak ?
(b) i. Als je bist was je gebuisd.
ii. Als je gebuisd was, ging je niet veel naar TD.
iii. Als je bist of gebuisd was, ging je veel naar TD.
iv. Als je niet bist, ging je veel naar TD.
Is het aangeraden om van TD weg te blijven ?
21. Zijn volgende formules tautologieën ? Zijn het contradicties ?
(a) (((p → q) ∧ (q → p)) ↔ (p ↔ q))
(b) (((p ∧ q) ∨ (r ∧ s)) ∧ ¬r)
(c) ((p ∧ ¬p) ∧ r)
22. Zijn volgende formules equivalent ?
(a) (p ∧ q) en (p → q)
(b) (p → (q → r) en (p → q) → (p → r))
4
