Formeel Denken Opgavenbundel
Engelbert Hubbers en Freek Wiedijk
10 december 2014
Inhoudsopgave
1 Propositielogica
2
2 Predikaatlogica
10
3 Talen en automaten
20
4 Discrete wiskunde
40
5 Modale logica
58
1
1
Propositielogica
Opgave 1.A Vind zinnen uit de formele taal die hetzelfde betekenen als de volgende zinnen.
(i) Het regent niet, noch schijnt de zon.
Oplossing: ¬R ∧ ¬Z: het regent niet en de zon schijnt niet.
(ii) De zon schijnt, tenzij het regent
Oplossing: De betekenis van het woord ‘tenzij’ is een beetje onduidelijk. Meestal wordt
het gelezen als ‘De zon schijnt, behalve als het regent’. Vandaar dat er verschillende
mogelijkheden zijn. In het bijzonder zijn deze verschillende oplossingen niet logisch
equivalent (zie definitie 1.11).
• R → ¬Z: als het regent schijnt de zon niet (merk op dat hier niets gezegd wordt
over wanneer de zon dan wel schijnt: komt dat overeen met de betekenis van
‘tenzij’ ?),
• ¬R → Z: als het niet regent schijnt de zon,
• Z ↔ ¬R: de zon schijnt dan en slechts dan als het niet regent.
(iii) Of de zon schijnt, of het regent. (We bedoelen dus niet allebei)
Oplossing: Ook hier zijn er verschillende mogelijkheden, maar in dit geval zijn de formules wel logisch equivalent. De eerste versie lijkt iets meer op de originele vraag dan
de tweede.
• (Z ∨ R) ∧ ¬(Z ∧ R): de zon schijnt of het regent, en niet allebei tegelijk,
• (Z ∧ ¬R) ∨ (¬Z ∧ R): de zon schijnt en het regent niet of de zon schijnt niet en
het regent wel.
Merk op dat de formule Z ↔ ¬R dezelfde waarheidstabel heeft als de hierboven genoemde oplossingen. Maar omdat de structuur van deze formule helemaal niet meer
lijkt op de oorspronkelijke zin, vinden we deze formule minder goed als vertaling.
Waarschijnlijk ten overvloede maar simpelweg Z ∨ R is dus fout, want dit sluit het
‘allebei’ niet uit.
(iv) Er is alleen een regenboog als de zon schijnt en het regent.
Oplossing: Deze oplossing heeft de voorkeur: RB → (Z ∧ R): als er een regenboog is,
dan schijnt de zon en regent het, want alleen als de zon schijnt en het regent is er een
regenboog.
De volgende optie vinden we niet zo goed, maar nog wel enigszins verdedigbaar: RB ↔
(Z ∧ R): er is een regenboog dan en slechts dan als de zon schijnt en het regent. Hier
wordt het woordje ‘alleen’ wel erg sterk ge¨ınterpreteerd: de bewering geldt blijkbaar
ook de andere kant op.
Verder is het duidelijk dat (Z ∧ R) → RB een te zwakke vertaling is van de zin. Dit is
namelijk de vertaling van ‘Er is een regenboog als de zon schijnt en het regent’ en dus
zou het woordje ‘alleen’ niets toevoegen.
(v) Als ik buiten ben, dan word ik nat, mits het regent.
Oplossing: Het woordje ‘mits’ kan hier worden gezien als ‘en als’. Dat levert weer een
aantal logisch equivalente formules. De eerste sluit het beste aan bij de exacte tekst in
de vraag.
• Bui → (R → N ): als ik buiten ben en als het dan regent dan word ik nat,
• R → (Bui → N ): als het regent en als ik dan buiten ben dan word ik nat,
2
• (Bui ∧R) → N : als ik buiten ben en het regent dan word ik nat.
Het woordje ‘mits’ kan ook worden gezien als ‘op voorwaarde dat’ wat min of meer
dezelfde betekenis heeft als ‘alleen als’ en dus kun je ook deze formule gebruiken:
• (Bui → N ) → R: als ik nat word als ik buiten ben, dan regent het.
• Bui → (N → R): als ik buiten ben en als ik dan nat word, dan regent het.
Opgave 1.B Kun je f ↔ g ook uitdrukken met behulp van de andere symbolen?
Oplossing: De formule f ↔ g is ook te schrijven als (f → g) ∧ (g → f ) of als (f ∨ g) →
(f ∧ g). Ook (f ∧ g) ∨ (¬f ∧ ¬g) is logisch equivalent.
Opgave 1.C Vertaal de volgende zinnen uit de formele taal naar het Nederlands:
(i) R ↔ Z
Oplossing: Het regent dan en slechts dan als de zon schijnt. (Of iets gebruikelijker in
het spraakgebruik: Het regent precies als de zon schijnt.) Merk op dat bijvoorbeeld
de zin ‘Als het regent dan schijnt de zon en als de zon schijnt regent het’ een prima
vertaling is van de formule (R → Z) ∧ (Z → R) en die formule is weliswaar equivalent
aan de formule R ↔ Z, maar toch is die zin geen goede vertaling van de oorspronkelijke
formule R ↔ Z.
(ii) RB → (R ∧ Z)
Oplossing: Als er een regenboog is, regent het en schijnt de zon.
(iii) Bui → ¬ Bin
Oplossing: Als ik buiten ben dan ben ik niet binnen.
(iv) Bui ∨ Bin
Oplossing: Ik ben buiten of ik ben binnen, of allebei.
Opgave 1.D Schrijf de waarheidstabellen op van:
(i) a ∨ ¬a
Oplossing: Zorg dat je altijd begint met kolommen te maken voor alle atomen. In
onderstaande tabellen zijn die kolommen met atomen nooit herhaald, maar dat mag
natuurlijk wel. Zorg er verder voor dat je tabellen er verzorgd uitzien en leesbaar
zijn. Merk op dat in onderstaande tabellen soms extra haakjes zijn opgenomen om het
parseren van de formules makkelijker te maken.
a ¬a a ∨ ¬a
0
1
1
1
0
1
(ii) (a → b) → a
Oplossing:
a b a → b (a → b) → a
0 0
1
0
0 1
1
0
1 0
0
1
1 1
1
1
(iii) a → (b → a)
Oplossing:
3
a b b → a a → (b → a)
0 0
1
1
0 1
0
1
1 0
1
1
1 1
1
1
(iv) a ∧ b → a
Oplossing:
a b (a ∧ b) (a ∧ b) → a
0 0
0
1
0 1
0
1
1 0
0
1
1 1
1
1
(v) a ∧ (b → a)
Oplossing:
a b b → a a ∧ (b → a)
0 0
1
0
0 1
0
0
1 0
1
1
1 1
1
1
(vi) ¬a → ¬b
Oplossing:
a b ¬a ¬b ¬a → ¬b
0 0
1
1
1
0 1
1
0
0
1 0
0
1
1
1 1
0
0
1
Opgave 1.E Welke van de volgende proposities zijn logisch waar?
Oplossing: Het antwoord wordt gevonden door de waarheidstabellen op te schrijven. Staan
er in de kolom onder de formule alleen 1-en, dan is die formule logisch waar. Zodra er echter
´e´en of meer 0-en staan, is de formule niet logisch waar.
Bedenk dat het uitsluitend geven van een waarheidstabel normaal gesproken geen
antwoord is op de vraag. Koppel altijd wat je in de tabel ziet aan wat er gevraagd
wordt!
In deze uitwerking is dat hierboven globaal gedaan door expliciet te zeggen hoe je ‘logisch
waar of niet’ kunt afleiden uit de tabel.
(i) a ∨ ¬a
Oplossing: Uit de waarheidstabel in opgave 1.D volgt dat a ∨ ¬a logisch waar is.
(ii) a → (a → a)
Oplossing: Logisch waar. Zie de laatste kolom uit deze tabel:
a a → a a → (a → a)
0
1
1
1
1
1
(iii) a → a
Oplossing: Logisch waar. Zie de tweede kolom uit de tabel van het vorige onderdeel.
4
(iv) (a → b) → a
Oplossing: Uit de 0-en in de overeenkomstige waarheidstabel in opgave 1.D blijkt dat
(a → b) → a niet logisch waar is.
(v) a → (b → a)
Oplossing: Uit de 1-en in de overeenkomstige waarheidstabel in opgave 1.D blijkt dat
a → (b → a) wel logisch waar is.
(vi) a ∧ b → a
Oplossing: Uit de 1-en in de overeenkomstige waarheidstabel in opgave 1.D blijkt dat
a ∧ b → a wel logisch waar is.
(vii) a ∨ (b → a)
Oplossing: Niet logisch waar. Zie de laatste kolom uit deze tabel:
a b b → a a ∨ (b → a)
0 0
1
1
0 1
0
0
1 0
1
1
1 1
1
1
(viii) a ∨ b → a
Oplossing: Niet logisch waar. Zie de laatste kolom uit deze tabel:
a b a ∨ b (a ∨ b) → a
0 0
0
1
0 1
1
0
1 0
1
1
1 1
1
1
Opgave 1.F Laat f en g proposities zijn. Ga na of de volgende uitspraken kloppen. Verklaar
je antwoorden.
Oplossing: Merk op dat alle uitspraken hier van het type ‘als. . . , dan. . . ’ zijn. Als de
uitspraak klopt moet je een redenering geven die dat ondersteunt. Als de uitspraak niet klopt
kun je volstaan met een tegenvoorbeeld, maar je mag natuurlijk ook een algemene redenering
geven.
Een bewijs van een ‘als. . . , dan. . . ’ bewering komt erop neer dat je mag aannemen wat
er in het ‘als’ stuk staat en daaruit moet afleiden wat er in het ‘dan’ stuk staat.
Bij een tegenvoorbeeld moet je concrete formules f en g kiezen, waarbij je laat zien dat
het ‘als’ stuk wel geldt, maar het ‘dan’ stuk niet.
(i) Als |= f en |= g, dan |= f ∧ g.
Oplossing: Klopt.
Neem aan |= f en |= g. Dan geldt voor elk model v dat v(f ) = 1 en v(g) = 1. Vervolgens
kun je bij zo’n model v v(f ∧ g) uitrekenen met de waarheidstabel van ∧. Daaruit blijkt
dat dan ook v(f ∧ g) = 1. Dus blijkbaar volgt uit de aanname dat voor elk model v,
v(f ∧ g) = 1. En dus per definitie geldt dan |= f ∧ g. En dus klopt de oorspronkelijke
uitspraak.
(ii) Als niet |= f , dan |= ¬f .
Oplossing: Klopt niet.
Als we een tegenvoorbeeld willen vinden waarvoor dus wel geldt dat ‘niet |= f ’, moeten
we in elk geval een f kiezen waarbij er minimaal een model v1 is met v1 (f ) = 0. Dan
volgt automatisch dat v(¬f ) = 1. Maar om zeker te weten dat ‘|= ¬f ’ niet geldt, moet
er dus ook een model v2 zijn met v2 (¬f ) = 0. Dat kan alleen maar als v2 (f ) = 1. Dus
5
kunnen we alleen een tegenvoorbeeld vinden als f dus in sommige modellen waar is en
in andere modellen niet waar. Gelukkig zijn daar genoeg mogelijkheden voor. Neem
maar f = a. Dan geldt ‘niet |= a’ en toch geldt de conclusie ‘|= ¬a’ niet. En dus klopt
de oorspronkelijke uitspraak niet.
(iii) Als |= f of |= g, dan |= f ∨ g.
Oplossing: Klopt.
Neem aan |= f of |= g. Dan hebben we eigenlijk drie gevallen die we moeten bekijken
en waarin we steeds dezelfde conclusie, namelijk |= f ∨ g moeten afleiden.
(1) |= f geldt. Dus voor elk model v geldt v(f ) = 1. Maar dan geldt ook voor elk
model v dat v(f ∨ g) = 1 omdat alleen het ‘waar’ zijn van f al garandeert dat de
samengestelde formule f ∨ g ook waar is. Maar dan geldt per definitie |= f ∨ g.
(2) |= g geldt. Dit gaat volkomen analoog aan het vorige geval.
(3) |= f geldt en |= g geldt. In het bijzonder geldt dus |= f en bij de beschrijving
van dat geval hebben we nergens gebruikt dat |= g al dan niet geldt, dus hetzelfde
bewijs kan nog een keer gegeven worden.
Dus in alle drie de gevallen geldt de conclusie. Dus geldt de conclusie dan ook onder de
samengestelde aanname ‘|= f of |= g’. En dus klopt de oorspronkelijke uitspraak.
(iv) Als (als |= f , dan |= g), dan |= f → g.
Oplossing: Klopt niet.
We hebben dus een voorbeeld nodig waarvoor ‘(als |= f , dan |= g)’ waar is. Dit is
zelf ook weer een ‘als. . . , dan. . . ’ bewering en kan dus op twee manieren waar worden
gemaakt.
(1) Als |= f niet waar is.
(2) Als |= f en |= g allebei waar zijn.
Als we in ´e´en van deze situaties kunnen laten zien dat |= f → g niet waar is, hebben
we dus een tegenvoorbeeld gevonden.
Neem nu f = a en g = b. Als we nu naar de modellen van a → b kijken, zien we dat
er vier verschillende modellen zijn: v1 (a) = 0 en v1 (b) = 0, v2 (a) = 0 en v2 (b) = 1,
v3 (a) = 1 en v3 (b) = 0, v4 (a) = 1 en v4 (b) = 1. In een waarheidstabel ziet dat er zo uit:
modelnaam a b a → b
v1
0 0
1
v2
0 1
1
v3
1 0
0
v4
1 1
1
Maar omdat bijvoorbeeld v1 (a) = 0 volgt meteen dat |= a niet waar is. Dus voor deze
concrete keuze van f en g geldt ‘(als |= f , dan |= g)’. Echter, als we v3 (a → b) gaan
uitrekenen, zien we dat v3 (a → b) = 0. Dus geldt |= f → g niet. En dus hebben
we inderdaad een tegenvoorbeeld gevonden. En dus klopt de oorspronkelijke uitspraak
niet.
(v) Als |= ¬f, dan niet |= f .
Oplossing: Klopt.
Deze keer geven we het bewijs zonder het woord ‘model’ te gebruiken, maar door te
beschrijven wat er in de waarheidstabellen gebeurt, zonder de waarheidstabellen uit te
schrijven. Omdat de bewering moet worden bewezen voor elke f kun je ook helemaal
6
geen tabel uitschrijven want je weet bijvoorbeeld niet welke atomen er in zitten. Maar
je weet wel of er al dan niet 1-en en 0-en in de tabel voorkomen en dat is genoeg om
deze bewering te bewijzen.
Neem aan |= ¬f . Dan bevat de kolom van ¬f alleen 1-en. En die van f dus alleen 0-en.
Per definitie geldt |= f dus niet. En dus klopt de uitspraak zelf wel.
(vi) Als |= f ∨ g, dan |= f of |= g.
Oplossing: Klopt niet.
We zoeken een tegenvoorbeeld met |= f ∨ g maar toch niet |= f en niet |= g. Neem
voor f = a en g = ¬a. Dan zijn er twee verschillende modellen: v1 met v1 (a) = 0 en
v2 met v2 (a) = 1. Hieruit volgt meteen dat v1 (¬a) = 1 en v2 (¬a) = 0. Uit v1 (a) = 0
volgt dat |= a niet geldt. En uit v2 (¬a) = 0 volgt dat ook |= ¬a niet geldt. Echter,
v1 (a ∨ ¬a) = 1 en v2 (a ∨ ¬a) = 1, dus geldt inderdaad wel |= f ∨ g. En dus is dit een
goed tegenvoorbeeld. En dus klopt de oorspronkelijke uitspraak niet.
(vii) Als |= f → g, dan (als |= f , dan |= g).
Oplossing: Klopt.
Neem aan |= f → g. Dan geldt voor elk model v dat v(f → g) = 1. Door te kijken hoe
→ werkt zien we dat er twee manieren zijn waarop v(f → g) = 1 kan voorkomen:
(1) v(f ) = 0 (en de waarde van v(g) is niet van belang)
(2) v(f ) = 1 en v(g) = 1.
We moeten in beide gevallen laten zien dat ‘als |= f , dan |= g’ waar is.
(1) Stel dat er een model v is met v(f ) = 0. Dat betekent automatisch dat |= f niet
waar kan zijn en dus is de bewering ‘als |= f , dan |= g’ kloppend.
(2) Dus hoeven we alleen nog maar te kijken naar de situatie dat alle modellen v(f ) = 1
geven. Maar dan volgt meteen uit de hierboven gemaakte gevalsonderscheiding dat
v(g) = 1 voor alle modellen. Dus is ‘als |= f , dan |= g’ waar.
Omdat in beide situaties de conclusie ‘als |= f , dan |= g’ volgt, klopt de oorspronkelijke
bewering dus.
(viii) Als |= f ↔ g, dan (|= f dan en slechts dan als |= g).
Oplossing: Klopt.
Voor de afwisseling weer een keer een bewijs zonder modellen, maar met waarheidstabellen.
Neem aan |= f ↔ g. Dit betekent dat in de waarheidstabel de waarheidswaarden van f
en g op elke regel gelijk zijn (of allebei 0 of allebei 1). Als we nu verder aannemen dat
|= f , dan heeft f dus alleen maar 1-en als waarheidswaarden. Maar dan heeft g ook
alleen maar 1-en. En dus geldt dan |= g. Andersom geldt ook: als |= g waar is, dan
heeft g allemaal 1-en in de waarheidstabel en f dus ook. Dus de hele bewering klopt.
(ix) Als (|= f dan en slechts dan als |= g), dan |= f ↔ g.
Oplossing: Klopt niet.
Neem voor f = a en g = b. We hebben dan weer dezelfde vier modellen als bij onderdeel
4. In het bijzonder hebben we dus v1 (a) = 0 en v1 (b) = 0. Dus geldt |= a niet. En ook
|= b geldt niet. De bewering ‘|= f dan en slechts dan als |= g’ is dan echter wel waar!
Als we echter v3 bekijken dan zien we dat v3 (a ↔ b) = 0. En dus geldt |= f ↔ g niet.
En dus hebben we een tegenvoorbeeld gevonden. En klopt de oorspronkelijke bewering
niet.
7
Opgave 1.G Laat zien dat de volgende proposities telkens logisch equivalent aan elkaar zijn.
Oplossing:
Of proposities logisch equivalent zijn, kunnen we makkelijk zien aan de
waarheidstabellen. Twee proposities zijn alleen maar logisch equivalent als hun kolommen
precies gelijk zijn.
(i) (a ∧ b) ∧ c en a ∧ (b ∧ c)
Oplossing: Deze proposities zijn logisch equivalent:
a b c a ∧ b b ∧ c (a ∧ b) ∧ c a ∧ (b ∧ c)
0 0 0
0
0
0
0
0 0 1
0
0
0
0
0 1 0
0
0
0
0
0 1 1
0
1
0
0
1 0 0
0
0
0
0
1 0 1
0
0
0
0
1 1 0
1
0
0
0
1 1 1
1
1
1
1
(ii) (a ∨ b) ∨ c en a ∨ (b ∨ c)
Oplossing: Ook deze proposities zijn logisch equivalent:
a b c a ∨ b b ∨ c (a ∨ b) ∨ c a ∨ (b ∨ c)
0 0 0
0
0
0
0
0 0 1
0
1
1
1
0 1 0
1
1
1
1
0 1 1
1
1
1
1
1 0 0
1
0
1
1
1 0 1
1
1
1
1
1 1 0
1
1
1
1
1 1 1
1
1
1
1
Opgave 1.H Laat f en g proposities zijn. Is de volgende uitspraak waar? f ≡ g dan en
slechts dan als |= f ↔ g.
Oplossing: Deze uitspraak is te splitsen in twee deeluitspraken:
1. Als f ≡ g dan |= f ↔ g. Stel f ≡ g, dan hebben f en g altijd dezelfde waarheidswaarde
in iedere rij van de waarheidstabel (of allebei 0 of allebei 1). Maar dan heeft f ↔ g
automatisch in elke rij een 1. En dus geldt |= f ↔ g is dan waar.
2. Als |= f ↔ g, dan f ≡ g. Stel |= f ↔ g is waar. Dan staat op elke regel in de waarheidstabel voor f ↔ g dus een 1. Maar dat betekent dat in elk model de waarheidswaarde
van f gelijk is aan die van g. En dat is precies wat f ≡ g ook uitdrukt, dus f ≡ g is
waar.
De twee deeluitspraken zijn waar, dus de totale uitspraak is waar.
Opgave 1.I Zijn de volgende uitspraken waar?
Oplossing: Ook deze opgave kun je eenvoudig oplossen door de waarheidstabellen uit te
schrijven en vervolgens de definitie van ‘logisch gevolg’ te controleren.
(i) a ∧ b |= a
Oplossing: a ∧ b |= a is waar, want in ieder model waar a ∧ b waar is, is ook a waar.
8
(ii) a ∨ b |= a
Oplossing: a ∨ b |= a is niet waar; de bewering zegt dat als a ∨ b waar is voor een model,
dan moet ook a waar zijn in dat model. Er zijn echter modellen te vinden waarvoor dat
niet geldt. Neem bijvoorbeeld het model v met v(a) = 0 en v(b) = 1.
(iii) a |= a ∨ b
Oplossing: a |= a ∨ b is waar: als a waar is in een model, dan is altijd ook a ∨ b waar
in dat model.
(iv) a ∧ ¬a |= b
Oplossing: a ∧ ¬a |= b is waar: als a ∧ ¬a waar is in een model, dan is b ook waar
in dat model. Dit lijkt een foute bewering omdat a ∧ ¬a in geen enkel model waar is.
Echter, de woordjes ‘als’ en ‘dan’ maken de totale bewering waar, juist doordat het ‘als’
deel nooit waar zal zijn.
Je kunt het ook andersom bekijken: als de bewering a ∧ ¬a |= b niet waar zou zijn, moet
je een model kunnen aanwijzen waarin b niet waar is en a ∧ ¬a wel. Dat laatste gaat
natuurlijk niet lukken.
9
2
Predikaatlogica
Opgave 2.A Geef twee mogelijke vertalingen voor de volgende zin.
Sharon houdt van Maud; een aardige man houdt van zo’n knappe vrouw.
Oplossing: Dit is een lastige opgave. Het probleem is dat in het Nederlands niet duidelijk
is wat er bedoeld wordt met zo’n knappe vrouw. Hier moet je dus je eigen interpretatie voor
geven. Uiteraard mag je geen onzinnige interpretaties geven. Het is wel de bedoeling dat je
hier iets verdedigbaars gebruikt. Het nu volgende lijstje is dan ook niet volledig, maar bevat
slechts voorbeelden van interpretaties.
(i) Heel zwak: interpreteer zo’n als een:
H(s, m) ∧ ∀x ∈ M [A(x) → ∃y ∈ V [K(y) ∧ H(x, y)]]
(ii) Interpreteer zo’n knappe vrouw als Sharon die nog knap is ook
H(s, m) ∧ ∀x ∈ M [A(x) → (H(x, s) ∧ K(s))]
(iii) Interpreteer zo’n knappe vrouw als Maud die nog knap is ook
H(s, m) ∧ ∀x ∈ M [A(x) → (H(x, m) ∧ K(m))]
(iv) Interpreteer zo’n knappe vrouw als alle vrouwen die knap zijn:
H(s, m) ∧ ∀x ∈ M [A(x) → ∀y ∈ V [K(y) → H(x, y)]]
(v) Interpreteer zo’n knappe vrouw als alle vrouwen die net zo knap zijn als Sharon:
H(s, m) ∧ ∀x ∈ M [A(x) → ∀y ∈ V [(K(y) ↔ K(s)) → H(x, y)]]
Let wel, hier staat dus niet dat Sharon knap is. Alleen maar dat als Sharon knap is,
dan wordt een willekeurige vrouw die ook knap is bemind door aardige mannen. En
als Sharon niet knap is, dan wordt een willekeurige vrouw die ook niet knap is bemind
door aardige mannen.
(vi) Interpreteer zo’n knappe vrouw als alle vrouwen die net zo knap zijn als Maud :
H(s, m) ∧ ∀x ∈ M [A(x) → ∀y ∈ V [(K(y) ↔ K(m)) → H(x, y)]]
(vii) Interpreteer zo’n knappe vrouw als knappe lesbiennes
H(s, m) ∧ ∀x ∈ M [A(x) → ∀y1 , y2 ∈ V [(K(y1 ) ∧ H(y1 , y2 )) → H(x, y1 )]]
Bedenk dat ∀y1 , y2 ∈ V [f ] een afkorting is voor ∀y1 ∈ V [∀y2 ∈ V [f ]].
Merk overigens op dat in geen enkele interpretatie die hier gegeven wordt de existenti¨ele
kwantor ∃x ∈ M is gebruikt, terwijl er in de tekst toch alleen maar ‘een aardige man’ staat.
Ook dat heeft weer met de onduidelijke interpretatie van het Nederlands te maken. Wat
bedoelen we nu eigenlijk als we zeggen ‘een kind houdt van ijs’ ? Bedoelen we dan dat er
ergens een kind is dat van ijs houdt of bedoelen we dan dat (normaal gesproken) alle kinderen
van ijs houden?
10
Opgave 2.B Vertaal de onderstaande formules naar een zin in het Nederlands.
Oplossing: Dit soort opgaven kun je het beste in stappen maken. Eerst geef je een
Nederlandse zin die heel dicht bij de formule blijft. Vervolgens ga je in het Nederlands met
voegwoorden en woordvolgordes spelen om er een duidelijkere zin van te maken. Hierbij moet
je er natuurlijk wel op letten dat de betekenis hetzelfde blijft!
h
i
(i) ∃x ∈ M L(x) ∧ ∃v ∈ V [K(v) ∧ I(v) ∧ H(x, v)]
Oplossing:
• Er is een man die lang is en er is een vrouw die knap en intelligent is en waar die
man van houdt.
• Er is een lange man en er is een knappe en intelligente vrouw waar die man van
houdt.
• Er is een lange man die van een zekere knappe en intelligente vrouw houdt.
Het woord zekere is hier toegevoegd om aan te geven dat deze man niet van elke
knappe en intelligente vrouw houdt maar van een of andere vrouw waarvan we
alleen maar weten dat er minimaal ´e´en bestaat van dat type.
h
i
(ii) ∃x ∈ M L(x) ∧ ∃v ∈ V [K(v) ∧ ¬I(v) ∧ H(x, v)] ∧ ∃w ∈ V [I(w) ∧ H(w, x)]
Oplossing:
• Er is een man die lang is en er is een vrouw die knap en niet intelligent is en waar
die man van houdt en er is een vrouw die intelligent is en die van die man houdt.
• Er is een lange man die van een zekere knappe, maar niet intelligente vrouw houdt
en die zelf wordt bemind door een of andere intelligente vrouw.
De ∃v ∈ V en ∃w ∈ V sluiten niet uit dat die v en w dezelfde vrouw kunnen zijn.
Echter omdat er een extra gegeven is dat v niet en w wel intelligent is, weten we
zeker dat het hier om verschillende vrouwen gaat.
Opgave 2.C Formaliseer de volgende zin.
Sharon is knap; er is een man die lekker in zijn vel zit van wie zij houdt.
Hierbij wordt gedefinieerd dat iemand lekker in zijn vel zit als hij of zij van zich zelf houdt.
Oplossing: Gebruikmakend van de woordenboeken op pagina 11 en 12 kan dit zo geformaliseerd worden:
K(s) ∧ ∃x ∈ M [H(x, x) ∧ H(s, x)]
Opgave 2.D Formaliseer de volgende zinnen.
(i) Voor iedere x en y geldt: x houdt van y alleen als x lekker in zijn of haar vel zit.
Oplossing: Bedenk dat ‘alleen als’ niet hetzelfde is als ‘dan en slechts dan als’. Dus
∀x, y ∈ V ∪ M [H(x, y) → H(x, x)] is goed en ∀x, y ∈ V ∪ M [H(x, y) ↔ H(x, x)] niet.
(ii) Voor iedere x en y geldt: x houdt van y als die lekker in zijn of haar vel zit.
Oplossing: ∀x, y ∈ V ∪ M [H(y, y) → H(x, y)]
(iii) Voor iedere x en y geldt: x houdt precies dan van y als y lekker in zijn of haar vel zit.
Oplossing: ∀x, y ∈ V ∪ M [H(y, y) ↔ H(x, y)]
11
(iv) Er is iemand die van alle mensen houdt.
Oplossing: ∃x ∈ V ∪ M [∀y ∈ V ∪ M [H(x, y)]]
Opgave 2.E (i) Ga na dat F2 in model M1 onder interpretatie I1 niet geldt. Geldt F1
wel?
Oplossing:
F1 := ∀x ∈ D∃y ∈ D K(x, y)
F2 := ∃x ∈ D∀y ∈ D K(x, y)
Dus ongeacht van welk model of welke interpretaie wij gebruiken wil F1 zeggen dat voor
alle x in het domein er een y in datzelfde domein gekozen kan worden waarvoor de
relatie K(x, y) geldt.
En F2 wil zeggen dat er een x in het domein gekozen kan worden waarvoor de relatie
K(x, y) geldt voor elke y in dat zelfde domein.
Wat betekent dat nu in model M1 onder interpretatie I1 :
D
alle studenten in het lokaal
K(x, y) x heeft een lager studentnummer dan y
Er wordt al verklapt dat F2 niet geldt in model M1 onder deze interpretatie. Dus je
moet laten zien dat F2 niet waar is. Omdat F2 eruit ziet als ∃x ∈ D[f ] betekent dat dat
je voor alle x ∈ D moet laten zien dat de bewering f niet waar is. En analoog omdat
deze f zelf eruit ziet als ∀y ∈ D[g] betekent dat dat je voor alle x ∈ D moet laten zien
dat er een y ∈ D bestaat waarvoor g niet waar is.
Omdat er maar eindig veel studenten (zeg n met n ≥ 1) in het lokaal zitten, kun je ze
op hun nummers sorteren. En omdat de nummers ook uniek zijn kunnen we spreken
over het laagste nummer en het hoogste nummer. Op grond van deze ordening geven
we de studenten een naam: s1 is de student met het laagste nummer en sn de student
met het hoogste nummer.
Als F2 waar is, moet je dus een student x kunnen kiezen waarvoor geldt dat hij een lager
nummer heeft dan de nummers van alle studenten in het lokaal. De enige kanshebber
voor x is natuurlijk de student met het laagste nummer, dus s1 . (Duidelijk toch?) Dus
kies je x = s1 . Dat betekent dat je verder moet bepalen of de formule
∀y ∈ D K(s1 , y)
geldt of niet. Omdat s1 het laagste studentnummer heeft, geldt deze formule voor de
meeste studenten y wel. Echter, voor alle studenten y in het lokaal geldt de bewering
niet. Want s1 zit namelijk zelf ook in dat lokaal en dus zou de formule
K(s1 , s1 )
ook waar moeten zijn en dat is zeker niet waar: s1 heeft geen lager studentnummer dan
s1 .
Omdat s1 onze enige kanshebber was om met succes de rol van x te spelen, weten we
nu dus dat de formule
F2 := ∃x ∈ D∀y ∈ D K(x, y)
niet geldt in model M1 onder interpretatie I1 .
12
Grote vraag is: kan dit niet wat korter worden opgeschreven? Ja, dat kan wel. In het
bovenstaande verhaal zijn heel veel vanzelfsprekende details uitgeschreven. Hieronder
een kortere variant:
Sorteer de studenten oplopend op hun unieke studentnummer. Geef ze in
die volgorde een naam waarbij s1 de student is met het laagste nummer en
sn die met het hoogste nummer. Stel dat F2 wel waar is. Dan zijn er twee
mogelijkheden voor x.
• x = si met i ∈ {2, . . . , n}. Dan geldt K(si , s1 ) niet, dus zeker niet
∀y ∈ D K(x, y). Dus is dit geen goede keuze voor x.
• x = s1 . Dan geldt K(s1 , s1 ) niet en dus ook hier geldt ∀y ∈ D K(x, y))
niet, want ook s1 ∈ D.
Dus we kunnen geen x vinden die F2 waarmaakt en dus geldt F2 niet in dit
model.
Nu de vraag of F1 geldt in dit model. Of met andere woorden: is het zo dat er voor
elke student x er een student y gekozen kan worden die een hoger studentnummer heeft
dan x. Ook dit is niet mogelijk. Omdat F1 van de vorm ∀x ∈ D [∃y ∈ D K(x, y)] is,
zijn we nu tevreden zodra we ´e´en x kunnen aanwijzen waarvoor er geen y bestaat zodat
K(x, y) waar is.
Kies nu maar voor x de student sn die het hoogste studentnummer uit het lokaal heeft.
We hebben eerder al laten zien dat dat kan. Bij deze sn is er geen enkele y te vinden
waarvoor het studentnummer hoger is; het is immers op z’n hoogst gelijk als we weer
sn zelf kiezen. En dus hebben we met student sn een student gevonden waarbij we geen
student kunnen vinden met een hoger studentnummer. Dus F1 geldt niet in model M1
onder interpretatie I1 .
(ii) Ga na dat F1 in model M1 onder interpretatie I2 geldt. Geldt F2 ook?
Oplossing: Dit is interpretatie I2 :
D
alle studenten in het lokaal
K(x, y) x is niet ouder dan y
We moeten laten zien dat F1 wel geldt onder deze interpretatie I2 . Dat betekent dat
we voor elke x moeten laten zien dat we een y kunnen kiezen waarvoor K(x, y) waar is.
Of met andere woorden: je moet een soort algoritme hebben om bij gegeven x een y te
kiezen zodanig dat K(x, y) waar is.
Hier is dat algoritme eenvoudig: kies y namelijk maar gelijk aan die gegeven x. Dan
geldt K(x, y) want de leeftijd van x is de leeftijd van y en dus is x niet ouder dan y.
Op een soortgelijke manier kunnen we ook laten zien dat F2 geldt in model M1 onder
interpretatie I2 . Hier is het voldoende om een verstandige x te kiezen. Zostraks hebben
we de studenten gesorteerd op studentnummer, nu doen we dat op leeftijd. Het grote
verschil is dat de leeftijden niet uniek hoeven te zijn, zelfs niet als je leeftijd niet zoals
gebruikelijk meet in jaren, maar in seconden of nog kleinere eenheden. Dus we kunnen
hier niet spreken over de jongste of de oudste student. Er kunnen namelijk meerdere
studenten de laagste leeftijd hebben. Of met andere woorden de deelverzameling van
jongste studenten bevat minstens ´e´en element. Gelukkig is dat hier goed genoeg. Neem
voor x maar ´e´en van de studenten uit die deelverzameling van jongste studenten. Voor
alle studenten y geldt dan dat of x even oud is als y, of x is echt jonger dan y. In alle
gevallen is x dus niet ouder dan y en geldt F2 dus in model M1 onder interpretatie I2 .
13
(iii) Kijk om je heen en ga na of F1 in het model M1 onder interpretatie I3 geldt. Ga ook
na of F2 geldt.
Oplossing: Dit is interpretatie I3 :
D
alle studenten in het lokaal
K(x, y) x zit naast y
In model M1 onder interpretatie I3 is het niet duidelijk of F1 waar is of niet. Dat hangt
namelijk af van de concrete situatie in het lokaal. Als er ergens een student zit zonder
directe buren, kun je hem als tegenvoorbeeld gebruiken. Immers kies je hem als x, kun
je geen student y vinden die naast hem zit. Als er nergens studenten apart zitten, is
F1 wel waar. Bij elke student x die je kiest heb je een algoritme om een student y te
kiezen zodat K(x, y) waar is: neem namelijk ´e´en van zijn buren.
F2 is altijd niet waar in model M1 onder interpretatie I3 . De formule zegt namelijk
dat er ´e´en student moet zijn die naast alle studenten moet zitten. Nu kun je nog wel
proberen om een klas met twee studenten te nemen of een klas waarin alle tafels in een
soort ster staan waar ´e´en student in het midden naast alle andere studenten kan zitten,
maar je krijgt het nooit voor elkaar om een situatie te hebben waar je een student kunt
kiezen die ook naast zichzelf zit. En dat is wel wat er volgens F2 zou moeten gelden
onder interpretatie I3 .
Opgave 2.F Ga na dat G2 waar is in model M4 onder interpretatie I8 , maar niet in model
M3 onder interpretatie I7 . Ofwel: ((Q, <), I8 ) |= G2 , en ((N, <), I7 ) 6|= G2 .
Oplossing:
(i) Interpretatie I7 geeft G2 de betekenis dat voor iedere x ∈ N er een y ∈ N is zodat y < x.
Tegenvoorbeeld: neem x = 0 want dan lukt het niet om een y te vinden met y < 0.
(ii) Interpretatie I8 geeft G2 de betekenis dat voor iedere x ∈ Q er een y ∈ Q is zodat y < x.
Dit is waar, want voor ieder getal x is er een kleiner getal y te vinden. Kies voor y maar
het getal x − 1.
Opgave 2.G Definieer interpretatie I9 als volgt:
D
N
K(x, y) x = 2 · y
Welke van de formules G1 en G2 zijn waar?
Oplossing:
(i) Onder interpretatie I9 betekent G1 dat voor iedere x ∈ N er een y ∈ N is zodat x = 2 · y.
Tegenvoorbeeld: zo’n y bestaat niet als x = 3, dus niet waar.
(ii) Onder interpretatie I9 betekent G2 dat voor iedere x ∈ N er een y ∈ N is zodat y = 2 · x.
Dit is wel waar: kies een x en kies daarna voor y maar het getal 2 · x.
Opgave 2.H Definieer interpretatie I10 als volgt:
D
Q
K(x, y) x = 2 · y
Welke van de formules G1 en G2 zijn waar?
Oplossing:
(i) Onder interpretatie I10 betekent G1 dat voor iedere x ∈ Q er een y ∈ Q is zodat x = 2·y.
Dit is waar: kies een x en kies daarna voor y maar het getal x2 .
14
(ii) Onder interpretatie I10 betekent G2 dat voor iedere x ∈ Q er een y ∈ Q is zodat y = 2·x.
Dit is waar: kies een x en kies daarna voor y maar het getal 2 · x.
Opgave 2.I We bekijken als model de landen van Europa met de volgende interpretatie I11 .
L
verzameling van landen van Europa
n
Nederland
d
Duitsland
i
Ierland
G(x, y)
x grenst aan y
D(x, y, z) x, y en z hebben een drielandenpunt met elkaar
(i) Formaliseer de zin “Nederland en Duitsland delen een drielandenpunt”
Oplossing: De meest voor de hand liggende formule is ∃x ∈ L [D(n, d, x)], maar er
zijn genoeg alternatieven te bedenken: ∃x ∈ L [D(n, d, x)], ∃x ∈ L [D(x, d, n)], ∃y ∈
L [D(y, n, d)], . . .
(ii) Welke van de volgende formules is waar in dit model onder deze interpretatie:
(1) G3 := ∀x ∈ L∃y ∈ L[G(x, y)]
Oplossing: G3 betekent dat voor elk land x er een land y is dat grenst aan x. Dit
is niet waar, want het geldt bijvoorbeeld niet voor eilanden als IJsland en Malta.
(2) G4 := ∀x, y ∈ L[(∃z ∈ L D(x, y, z)) → G(x, y)]
Oplossing: G4 betekent dat voor alle landen x en y geldt dat als er een land z is
dat een drielandenpunt heeft met x en y, dan grenzen x en y aan elkaar. Dit is
waar: als twee landen een drielandenpunt hebben, dan grenzen ze automatisch aan
elkaar.
(3) G5 := ∀x ∈ L[G(i, x) → ∃y ∈ L[D(i, x, y)]].
Oplossing: G5 betekent dat als een land grenst aan Ierland dan heeft het daar
ook een drielandenpunt mee. Dit is niet waar: neem het Verenigd Koninkrijk: dat
grenst aan Ierland (via het gebied Noord-Ierland) maar heeft er geen drielandenpunt mee gemeen. (Als i als interpretatie IJsland zou hebben, zou G5 waar zijn,
want G(i, x) is altijd onwaar (voor iedere x), dus is de implicatie altijd waar.)
Opgave 2.J Bedenk zelf een model M5 en een interpretatie I12 zodat
(M5 , I12 ) |= ∀x ∈ D∃y ∈ E[R(x, y) ∧ ¬R(y, x) ∧ ¬R(y, y)]
Oplossing: Neem bijvoorbeeld
• als model M5 de natuurlijke getallen en als interpretatie I12 :
D
E
R(x, y)
N
N
x<y
Check zelf dat de formule geldt als je bij x ∈ N voor y de waarde x + 1 kiest.
• als model M5 de verzameling alle mensen en de vader van relatie en als interpretatie
I12 :
D
E
R(x, y)
alle mensen
alle mensen
y is de vader van x
Merk op dat R(x, y) met x is de vader van y niet werkt.
15
Bij deze opgave dient eigenlijk nog gezegd te worden dat de domeinen D en E wel wat met
elkaar te maken moeten hebben. Bij Formeel Denken gaan we hier niet echt verder op in,
maar bij Beweren en Bewijzen zul je zien dat elke relatie R(x, y) een type heeft, bijvoorbeeld
N → Q → {0, 1}. Dit betekent dat x ∈ N en y ∈ Q moet zitten en vervolgens levert R(x, y)
dan een 1 of 0 als de relatie in de gegeven interpretatie al dan niet waar is. Bij deze opgave
schrijven we zowel R(x, y) als R(y, x). Omdat het type van R vastligt als D → E → {0, 1},
moet dus x ∈ D, x ∈ E, y ∈ D en y ∈ E! Dus een model defini¨eren waarbij D de verzameling
auto’s is en E de verzameling fietsen en dan R(x, y) interpreteren als ‘x is sneller dan y’ is
een beetje gek omdat een auto namelijk nooit een fiets is of omgekeerd. In dit geval zou je
dan ook een superdomein V , de verzameling van voertuigen, kunnen toevoegen en het type
van R defini¨eren als V → V → {0, 1}. In dat geval kun je zonder problemen zowel R(x, y) als
R(y, x) schrijven zonder iets onzinnigs te beweren. Heb je niets begrepen van deze opmerking,
hoef je je voorlopig nog geen zorgen te maken. Het komt bij Beweren en Bewijzen aan bod.
Opgave 2.K Beschouw de interpretatie I13 :
M
V (x)
O(x, y)
G(x, y)
domein van de mensen;
x is vrouw;
x is ouder van y;
x is getrouwd met y.
Formaliseer de volgende zinnen in de predikaatlogica met gelijkheid.
(i) Iedereen heeft precies ´e´en moeder.
Oplossing:
∀x ∈ M
∃y ∈ M
[
∧
∀y, z ∈ M
[ V (y) ∧ O(y, x)
]
[ (V (y) ∧ O(y, x) ∧ V (z) ∧ O(z, x)) → y = z
]
]
In deze formule speelt x de rol van iemand, de y en z spelen de rol van moeders. De
eerste y wordt gebruikt om aan te tonen dat er een moeder is, de tweede wordt samen
met de z gebruikt om te laten zien dat er maximaal ´e´en moeder is. Strikt genomen
hebben die twee y’s dus niets met elkaar te maken. Als de tweede y op elke plaats
vervangen was door een w was de formule ook goed geweest. Let ook op de scope van
die x: ook in het tweede stuk (≤ 1 moeders), moet je wel terug kunnen verwijzen naar
je oorspronkelijke persoon x.
Een alternatieve oplossing die net zo goed is:
∀x ∈ M
[ ∃y ∈ M
[ V (y) ∧ O(y, x)
∧
∀z ∈ M [(V (z) ∧ O(z, x)) → y = z]
]
]
Het grote verschil is dat de y nu maar ´e´en keer gebonden wordt en zowel gebruikt wordt
om aan te tonen dat er minimaal ´e´en moeder is als om aan te tonen dat elke ‘andere’
moeder dezelfde blijkt te zijn.
16
(ii) Iedereen heeft precies twee oma’s.
Oplossing:
∀x ∈ M
[
∃y, z ∈ M
∧
∀y, z, v ∈ M
[ y 6= z ∧
∃u ∈ M [V (y) ∧ O(y, u) ∧ O(u, x)]∧
∃u ∈ M [V (z) ∧ O(z, u) ∧ O(u, x)]
]
[ (y 6= z ∧
∃u ∈ M [V (y) ∧ O(y, u) ∧ O(u, x)]∧
∃u ∈ M [V (z) ∧ O(z, u) ∧ O(u, x)]∧
∃u ∈ M [V (v) ∧ O(v, u) ∧ O(u, x)]) → (v = y ∨ v = z)
]
]
De x speelt weer de rol van iemand, de y en z spelen de rol van de twee verschillende
oma’s en de u speelt de rol van de vader of moeder van x en tegelijkertijd het kind van
de oma’s.
(iii) Iedere getrouwde man heeft precies ´e´en echtgenote.
Oplossing: Een eerste poging is:
∀x ∈ M [∃y ∈ M [G(x, y)] → (∀z1 , z2 ∈ M [G(x, z1 ) ∧ G(x, z2 ) → z1 = z2 ])]
Deze zin zegt dat voor iedere persoon x het volgende geldt: Als x getrouwd is, dan is
er maar ´e´en persoon met wie x getrouwd is (want als x met z1 en met z2 getrouwd is,
dan z1 = z2 ).
Het zegt echter niets over het man zijn en het vrouw zijn van de echtgenote. We moeten
de formule dus iets aanpassen:
∀x ∈ M
[ ¬V (x) ∧ ∃y ∈ M [G(x, y)]
→
(∀z1 , z2 ∈ M [G(x, z1 ) ∧ G(x, z2 ) → z1 = z2 ∧ V (z1 )])
]
Merk op dat we na de → niets meer over y kunnen zeggen. Echter, omdat die ∀z1 in
het bijzonder ook die eerdergenoemde y moet bevatten, volgt uit de V (z1 ) toch dat die
ene persoon waarmee de man x getrouwd is een vrouw meot zijn.
Opgave 2.L Gebruik interpretatie I13 van opgave 2.K. Formaliseer de volgende eigenschappen.
(i) S(x, y): x en y hebben samen een kind gemaakt.
Oplossing: Definieer
S(x, y) := x 6= y ∧ ∃z ∈ M [O(x, z) ∧ O(y, z)]
Dan zijn x en y twee verschillende personen en er is een persoon z waar zowel x als y
ouder van is. (Als we x 6= y weglaten zou S(x, x) ook waar zijn, maar de zin bedoelt
niet te zeggen dat iemand met zichzelf een kind heeft gemaakt. . . )
17
(ii) B(x, y): x is broer van y (pas op: zie ook volgende item).
Oplossing: Definieer
B(x, y) := ¬V (x) ∧ x 6= y ∧ ∃q, r ∈ M [q 6= r ∧ O(q, x) ∧ O(q, y) ∧ O(r, x) ∧ O(r, y)]
Dan is x een broer van y als x man is (en niet dezelfde is als y), en er twee verschillende
ouders q en r zijn, die ouder zijn van ieder van deze twee kinderen.
(iii) H(x, y): x is halfzus van y.
Oplossing: Definieer
H(x, y) := V (x) ∧ x 6= y∧
∃o1 , o2 , o3 ∈ M [o1 6= o2 ∧ o2 6= o3 ∧ o3 6= o1 ∧
O(o1 , x) ∧ O(o2 , x) ∧ O(o2 , y) ∧ O(o3 , y)]
Dan is x een halfzus van y als x vrouw is, en er drie ouders o1 , o2 , o3 zijn waarbij x kind
is van o1 en o2 en y kind is van o2 en o3 . Bovendien moeten deze drie ouders verschillend
zijn.
Vertaal terug naar de omgangstaal.
(iv) ∃x∈M ∀y∈M O(x, y). Geldt dit?
Oplossing: “Er is een persoon x die ouder is van alle mensen.” Dit geldt niet.
(v) ∀z1 ∈M ∀z2 ∈M [(∃x∈M ∃y1 ∈M ∃y2 ∈M O(x, y1 ) ∧ O(y1 , z1 ) ∧ O(x, y2 ) ∧ O(y2 , z2 )) →
¬(∃w∈M (O(z1 , w) ∧ O(z2 , w)))]. Geldt dit?
Oplossing: “Ieder tweetal mensen dat een gemeenschappelijke grootouder heeft, heeft
geen gemeenschappelijk kind”. Dit geldt niet. (Realiseer je dat het “tweetal mensen”
waar het over gaat ook ´e´en en dezelfde persoon kan zijn! Dan zie je meteen dat het niet
geldt.)
Opgave 2.M Gegeven de interpretatie I14
D
P (x, y, z)
M (x, y, z)
N;
x + y = z;
x · y = z.
Formaliseer
Oplossing: Bij deze opgave hebben we straks de formalisatie van x = 0 en x = 1 nodig.
Daar beginnen we mee.
• x = 0 als a · x = x voor alle a. Dus definieer
x = 0 := ∀a ∈ D[M (a, x, x)]
• x = 1 als x · a = a voor alle a. Dus definieer
x = 1 := ∀a ∈ D[M (x, a, a)]
(i) x < y.
Oplossing: x < y: dit is waar wanneer x + r = y en r 6= 0.
Definieer:
x < y := ∃r ∈ D[P (x, r, y) ∧ r 6= 0]
18
(ii) x | y (x is deler van y).
Oplossing: x|y (x is deler van y): er is een getal z zodat x · z = y. Definieer
x|y := ∃z ∈ D[M (x, z, y)]
(iii) x is priemgetal.
Oplossing: x is priem: x is niet 1 en het heeft geen factoren anders dan 1 en zichzelf.
Definieer
x is priem := x 6= 1 ∧ ¬∃y, z ∈ D[M (y, z, x) ∧ y 6= x ∧ z 6= x ∧ y 6= 1 ∧ z 6= 1]
Een andere formalisatie gebruikt de zojuist gedefinieerde x|y.
x is priem := x 6= 1 ∧ ∀y ∈ D[(y|x) → (y = 1 ∨ y = x)]
19
3
Talen en automaten
Opgave 3.A In voorbeeld 3.5 heb je voorbeelden gezien van beschrijvingen van talen. Probeer het nu zelf.
(i) Beschrijf L1 ∩ L2 .
Oplossing: L1 ∩ L2 bestaat uit de woorden van de vorm an bn die een even aantal a’s
bevatten, dus L1 ∩ L2 = {an bn | n ∈ N, n is even}. Een andere manier om dit te
beschrijven is L1 ∩ L2 = {a2n b2n | n ∈ N}
(ii) Beschrijf L2 ∩ L4 .
Oplossing: L2 ∩ L4 bestaat uit de woorden w van de vorm an bn waarvoor geldt w = wR .
Dat geldt alleen als n = 0, dus als w = λ, dus L2 ∩ L4 = {λ}.
(iii) Beschrijf L3 ∩ L4 .
Oplossing: L3 ∩ L4 bestaat dan uit de woorden van de vorm wcv waarvoor geldt:
|w| = |v|, w bevat geen b en v bevat geen a en wcv = v R cwR . Dat kan alleen als w en v
allebei uit alleen c’s bestaan, dus L3 ∩ L4 = {cn | n ∈ N, n is oneven} = {c2n+1 | n ∈ N}.
Opgave 3.B Gebruik de definities uit voorbeeld 3.5.
(i) Bewijs dat L1 = L∗1
Oplossing: Om L1 = L∗1 te bewijzen laten we zien dat L1 ⊆ L∗1 en L∗1 ⊆ L1 . Het eerste
is bekend: voor elk woord w in L1 kun je in de definitie van L∗1 k = 1 nemen en w1 = w
en dan heb je bewezen dat w ∈ L∗1 . Voor het tweede deel: als w ∈ L∗1 dan is w van de
vorm w1 · · · wk met k ≥ 0 en alle wi hebben een even aantal a’s (want elke wi ∈ L1 ).
Maar dan heeft w zelf ook een even aantal a’s, en dus w ∈ L1 .
(ii) Geldt L2 L2 = L2 ? Geef een bewijs of een tegenvoorbeeld.
Oplossing: Nee. ab ∈ L2 , dus abab ∈ L2 L2 en het is duidelijk dat abab 6∈ L2 . Dus
L2 L2 6= L2 .
∗
(iii) Geldt L1 = L1 ? Geef een bewijs of een tegenvoorbeeld.
Oplossing: L1 = {w | w bevat een oneven aantal a’s}. Het antwoord is ‘nee’, want
∗
a ∈ L1 en dus aa ∈ L1 maar het is duidelijk dat aa ∈ L1 en dus automatisch aa 6∈ L1 .
∗
∗
Dus L1 6= L1 . (Bedenk dat L1 betekent dat je eerst het complement van L1 neemt en
daarna pas de Kleene afsluiting.)
(iv) Voor welke talen uit voorbeeld 3.5 geldt L = LR ? (Alleen antwoord, geen bewijs.)
Oplossing: Alleen voor L1 en L4 .
Bij L1 draai je woorden om die een even aantal a’s hebben en dat verandert het aantal
a’s natuurlijk niet. Bij L2 gaat het mis: bbaa ∈ LR
2 maar bbaa 6∈ L2 . Bij L3 gaat het
ook mis: bca ∈ LR
maar
bca
∈
6
L
.
Bij
L
gaat
het
om omgedraaide palindromen en
3
4
3
per definitie is een omgedraaide palindroom weer een palindroom.
Opgave 3.C (i) Laat zien dat we de operator ?, waarbij a? staat voor 0 of 1 keer a niet
hoeven toe te voegen aan de reguliere expressies, omdat we hem al kunnen maken.
Oplossing: We kunnen a? defini¨eren als a ∪ λ.
(ii) Wat is L(∅ab∗ )?
Oplossing: L(∅ab∗ ) = L(∅)L(a)L(b∗ ) = ∅{a}{b}∗ en dat zijn de woorden w1 w2 w3 zodat
w1 ∈ ∅, w2 ∈ {a} en w3 ∈ {b}∗ . Maar er is geen w1 ∈ ∅, dus L(∅ab∗ ) = ∅.
(iii) Geef een reguliere expressie die de taal L5 := {w ∈ {a, b}∗ | w bevat minstens ´e´en a}
beschrijft.
Oplossing: (a ∪ b)∗ a(a ∪ b)∗ . De minimale a staat in het midden van de expressie; zowel
daarvoor als daarna kan er een willekeurig rijtje van a’s en b’s komen en zo’n willekeurig
20
rijtje (eventueel van lengte 0) wordt met (a ∪ b)∗ weergegeven. Een andere expressie die
dezelfde taal genereert is b∗ a(a ∪ b)∗ .
(iv) Geef een reguliere expressie die de taal L1 uit voorbeeld 3.5 beschrijft.
Oplossing: (b∗ ab∗ ab∗ )∗ b∗ . Het idee is dat de ingewikkelde expressie b∗ ab∗ ab∗ een reguliere expressie is die elk woord met precies twee a’s erin beschrijft. Door nu (b∗ ab∗ ab∗ )∗
te nemen krijg je dus 0 of meer rijtjes met precies twee a’s en daarmee kun je bijna alle
rijtjes met een even aantal a’s maken. De enige die je dan nog mist is als je 0 a’s hebt:
in dat geval moet je nog een b∗ toevoegen om woorden als bbb te kunnen maken. Die
b∗ mag overigens ook vooraan worden geschreven, dus b∗ (b∗ ab∗ ab∗ )∗ is ook een goede
oplossing. Verder is (b ∪ ab∗ a)∗ ook correct.
(v) Laat zien dat L(ab(ab)∗ ) = L(a(ba)∗ b).
Oplossing: L(ab(ab)∗ ) bestaat uit woorden van de vorm ab gevolgd door n keer ab (met
n ≥ 0). Maar ab gevolgd door n keer ab is dezelfde string als a gevolgd door n keer ba,
gevolgd door b. En de woorden van de laatste vorm zijn precies de taal L(a(ba)∗ b).
Je kunt het ook op de volgende manier bewijzen. Een willekeurig woord uit L(ab(ab)∗ )
ziet eruit als ab(ab)n met n ∈ N. Maar zo’n willekeurig woord kunnen we herschrijven:
ab(ab)n = ab(ab) · · · (ab)
= abab · · · ab
= ababa · · · bab
= a(ba)(ba) · · · (ba)b
= a(ba)n b
en dat is een woord uit L(a(ba)∗ b). Dus L(ab(ab)∗ ) ⊆ L(a(ba)∗ b). Het bewijs dat ook
L(a(ba)∗ b) ⊆ L(ab(ab)∗ ) gaat analoog.
Merk op dat het algemene bewijs dat hier gegeven is (met · · · ) alleen maar klopt voor
n ≥ 3; ga zelf na dat je voor n = 0, 1, 2 een soortgelijk herschrijfbewijs kunt opschrijven
(maar dan zonder · · · ).
Wie niet houdt van bewijzen met · · · erin, moet even wachten op het volgende hoofdstuk
waarin bewijzen met inductie worden uitgelegd. Heel in het kort is dat een manier om
aan de hand van een bewijs voor een specifiek simpel geval (basisstap) en een bewijs van
een methode om uit een simpel geval een iets moeilijker geval af te leiden (inductiestap),
een bewijs voor alle gevallen te maken. Hier ziet dat er zo uit (maar dit hoef je nu
natuurlijk nog niet te begrijpen).
Basisstap. Elk woord in L(ab(ab)∗ ) ziet eruit als ab(ab)n met n ∈ N. Het kleinste
woord krijgen we dus als n = 0 en dat is dus ab. Het is meteen duidelijk dat ab ook in
L(a(ba)∗ b) zit. Dus voor n = 0 geldt het dat ab(ab)n = a(ba)n b.
Inductiestap. We nemen nu aan dat we al weten dat de gewenste eigenschap geldt voor
een of andere n ∈ N. In dit geval betekent dat dus dat we weten dat voor zekere n
geldt dat ab(ab)n = a(ba)n b. Dit noemen we de inductiehypothese (IH). Nu moeten we
21
bewijzen dat dan ook geldt ab(ab)n+1 = a(ba)n+1 b. Dat gaan we nu laten zien:
ab(ab)n+1
=
ab(ab)n (ab)
= ab(ab)n ab
IH
= a(ba)n bab
=
a(ba)n (ba)b
=
a(ba)n+1 b
Op de plaats waar IH staat, passen we de inductiehypothese toe op het eerste deel van
de string.
Doordat we nu weten dat de eigenschap voor n = 0 geldt, weten we met de inductiestap
dat hij ook voor n = 1 geldt. Maar dan weten we door nogmaals de inductiestap toe
te passen dat hij ook voor n = 2 geldt. En zo verder gaand, kun je aantonen dat
voor elke n ∈ N geldt dat ab(ab)n = a(ba)n b. Maar dat betekent dat elk woord in
L(ab(ab)∗ ) ook in L(a(ba)∗ b) zit. Dus L(ab(ab)∗ ) ⊆ L(a(ba)∗ b). Het bewijs dat ook
L(a(ba)∗ b) ⊆ L(ab(ab)∗ ) waar is, gaat analoog natuurlijk.
Opgave 3.D Laat zien dat de volgende talen regulier zijn.
(i) L6 := {w ∈ {a, b}∗ | iedere a in w wordt direct gevolgd door een b},
Oplossing: Een reguliere expressie voor L6 is (b ∪ ab)∗ . (NB: een woord uit L6 hoeft
niet noodzakelijk een a te bevatten.) Een andere oplossing is (b∗ (ab)∗ )∗ . De expressie
(b∗ ab)∗ lijkt daar heel erg op, maar is toch niet goed. Welk woord uit L6 kun je met die
laatste expressie bijvoorbeeld niet maken?
(ii) L7 := de taal van alle goedgevormde integer-expressies. Deze bestaan uit de symbolen 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, maar ze beginnen nooit met een 0 (behalve het getal 0 zelf
natuurlijk) en mogen eventueel worden voorafgegaan door een + of een −.
Oplossing: Een reguliere expressie voor L7 is
((+ ∪ − ∪ λ)(1 ∪ 2 ∪ 3 ∪ 4 ∪ 5 ∪ 6 ∪ 7 ∪ 8 ∪ 9)(0 ∪ 1 ∪ 2 ∪ 3 ∪ 4 ∪ 5 ∪ 6 ∪ 7 ∪ 8 ∪ 9)∗ ) ∪ 0
Bij deze oplossing is er voor gekozen dat je wel 0 zelf kunt maken, maar niet +0 of
−0. Hoe kun je deze oplossing aanpassen om toch ook −0 toe te staan? Let wel: met
integer-expressies worden dus eigenlijk alleen getallen bedoeld, al dan niet voorzien van
een teken en geen rekenkundige operaties zoals hierna.
(iii) L8 := de taal van alle goedgevormde rekenkundige expressies zonder haakjes. Deze
bestaan uit natuurlijke getallen met daartussen de operatoren +, − of ×, bijvoorbeeld
7 + 3 × 29 − 78. (Hint: maak eerst een reguliere expressie voor de natuurlijke getallen;
zo’n getal begint (bijna) nooit met een 0.)
Oplossing: Het bijna nooit beginnen met een 0 levert de volgende gevalsonderscheiding
op: ofwel we hebben het getal 0, ofwel we hebben een getal dat nooit met een 0 begint:
r := (0 ∪ (1 ∪ 2 ∪ 3 ∪ 4 ∪ 5 ∪ 6 ∪ 7 ∪ 8 ∪ 9)(0 ∪ 1 ∪ 2 ∪ 3 ∪ 4 ∪ 5 ∪ 6 ∪ 7 ∪ 8 ∪ 9)∗ )
Een reguliere expressie voor L8 is dan (r(+ ∪ − ∪ ×))∗ r. Merk op dat deze expressie ook
expressies zonder operator genereert als bijvoorbeeld 37. Dat kun je voorkomen door
de ∗ ´e´en keer uit te pakken: (r(+ ∪ − ∪ ×))∗ r(+ ∪ − ∪ ×)r.
22
Opgave 3.E Welke van de volgende reguliere expressies beschrijven dezelfde taal? Toon het
aan of geef een string die wel in de ene en niet in de andere taal zit.
(i) b∗ (aab)∗ .
(ii) b∗ (baa)∗ b.
(iii) bb∗ (aab)∗ .
Oplossing: We geven de talen even een naam: L := L(b∗ (aab)∗ ), L0 := L(b∗ (baa)∗ b) en
L00 := L(bb∗ (aab)∗ ).
(i) L 6= L0 , want λ zit in L maar niet in L0 .
(ii) L 6= L00 , want λ zit in L maar niet in L00 .
(iii) L0 = L00 , want
• Als w ∈ L0 , dan is w van de vorm b . . . b baa . . . baa b met n keer b en m keer baa
(n, m ≥ 0). Als m = 0 zit dit woord zeker in L00 . ALs m > 0, dan kunnen we dit
woord ook lezen als b . . . b b aab . . . aab met n + 1 keer b en m keer aab, dus w ∈ L00 .
In herschrijfregels ziet dit er zo uit:
w = bn (baa)m b
= bn (baa) · · · (baa)b
= bn baa · · · baab
= bn baab · · · aabaab
= bbn aab · · · aabaab
= bbn (aab) · · · (aab)(aab)
= bbn (aab)m ∈ L00
Ook hier geldt het algemene bewijs alleen als m ≥ 3 is; toon zelf aan dat de stelling
ook klopt als m = 0, 1, 2.
• Als w ∈ L00 , dan is w van de vorm b b . . . b aab . . . aab met n + 1 keer b en m keer
aab (n, m ≥ 0). Als m = 0 zit dit woord zeker in L0 . Als m > 0, dan kunnen we
dit woord ook lezen als b . . . b baa . . . baa b met n keer b en m keer baa, dus w ∈ L0 .
Analoog als hierboven kan er ook een bewijs met herschrijfregels worden gegeven.
Opgave 3.F (i) Laat zien dat de taal van gebalanceerde haakjesexpressies contextvrij is.
Dat zijn expressies over {(, )} waarbij ieder openingshaakje altijd precies ´e´en sluithaakje
heeft, dus bijvoorbeeld (( )(( ))) en (( ))( ) zijn gebalanceerd, maar (( )( ))) niet.
Oplossing: Gebalanceerde haakjesexpressies, zoals (()(())) en (())(), maak je met de
volgende grammatica:
S → SS | (S) | λ
of met
S → (S)S | λ
(ii) Laat zien dat L1 uit voorbeeld 3.5 contextvrij is.
Oplossing: L1 :
S → bS | aT | λ
T
→ bT | aS
23
(iii) Laat zien dat L2 uit voorbeeld 3.5 contextvrij is. (Kijk naar voorbeeld 3.13.)
Oplossing: L2 :
S → aSb | λ
(iv) Laat zien dat L3 uit voorbeeld 3.5 contextvrij is.
Oplossing: L3 :
S → ASB | c
A → a|c
B → b|c
Bouw de strings op vanuit het midden en plaats de middelste c pas in de laatste stap.
Als je die c eerder plaatst verlies je de controle om de lengte van w en v gelijk te houden.
(v) Laat zien dat L4 uit voorbeeld 3.5 contextvrij is.
Oplossing: L4 :
S → aSa | bSb | cSc | a | b | c | λ
Bouw wederom de woorden op vanuit het midden.
Opgave 3.G Bekijk de grammatica G1 :
S → AS | Sb | λ
A → aA | λ
(i) Schrijf G1 als een tripel hΣ, V, Ri.
Oplossing:
G1 = h{a, b}, {S, A}, {S → AS, S → Sb, S → λ, A → aA, A → λ}i
(ii) Geef een productie die laat zien dat aabb ∈ L(G1 ).
Oplossing: Er zijn verschillende producties mogelijk. Hier twee voorbeelden:
S → AS → aAS → aaAS → aaS → aaSb → aaSbb → aabb
S → AS → ASb → ASbb → Abb → aAbb → aaAbb → aabb
(iii) Kun je binnen drie minuten een productie geven die laat zien dat bbaa ∈ L(G1 )?
Oplossing: Nee, dat zal niet lukken want bbaa 6∈ L(G1 ). Het bewijs daarvan kunnen
we nu nog niet geven, maar we komen er op terug in een latere opgave.
Opgave 3.H Gegeven is de volgende grammatica voor de taal L12 .
S → aSb | A | λ
A → aAbb | abb
De hulpsymbolen zijn dit keer S en A en Σ = {a, b}.
(i) Geef de productie van abb en van aabb.
Oplossing: Produceer abb via S → A → abb. Produceer aabb via S → aSb → aaSbb →
aabb.
24
(ii) Welke woorden zitten in L12 ?
Oplossing:
• λ, door de regel S → λ
• woorden van de vorm an Sbn met n ∈ N, geproduceerd door regel S → aSb
• het hulpsymbool A produceert woorden van de vorm am b2m met m ∈ N en m ≥ 1:
abb,aabbbb,aaabbbbbb,... Dit is eenvoudig in te zien, omdat de productieregels voor
A alleen gebruik maken van A zelf (geen S).
• de regel S → A zorgt ervoor dat een S vervangen kan worden door dat wat A
produceert: am b2m dus. En an Sbn levert dus an am b2m bn met n, m ∈ N en m ≥ 1.
Dit kan vereenvoudigd worden tot an+m bn+2m met n, m ∈ N en m ≥ 1.
Dit bij elkaar genomen levert de algemene vorm:
L12 = {an+m bn+2m | n, m ∈ N}
De m ≥ 1 wordt opgeheven doordat je ook 0 keer de regel S → A kunt toepassen.
We kunnen dit ook anders schrijven, namelijk als
L12 := {ak bk+l | k ≥ 0, k ≥ l ≥ 0}.
Opgave 3.I We bekijken nogmaals de taal behorende bij G1 uit opgave 3.G. Er is daar al
opgemerkt dat bbaa 6∈ L(G1 ).
(i) Is
P (w) := w bevat geen ba als deelwoord
een invariant voor G1 die bewijst dat bbaa 6∈ L(G1 )?
Oplossing: Nee, want P (bA) geldt (want bA bevat niet het deelwoord ba) en A → aA
is een productieregel van de grammatica, maar er geldt duidelijk niet P (baA). Dus is
P helemaal geen invariant.
(ii) Is
P (w) := w bevat geen ba en geen bA als deelwoord
een invariant voor G1 die bewijst dat bbaa 6∈ L(G1 )?
Oplossing: Nee, ook niet. Het tegenvoorbeeld uit het vorige onderdeel werkt nu niet
meer omdat P (bA) niet geldt, maar er is wel een ander tegenvoorbeeld. Nu geldt
namelijk wel P (bS), maar P (bAS) niet terwijl S → AS wel een productieregel is.
(iii) Is
P (w) := w bevat geen ba en geen bA en geen bS als deelwoord
een invariant voor G1 die bewijst dat bbaa 6∈ L(G1 )?
Oplossing: Nee, nog steeds niet. Nu geldt wel P (SaA), maar via de regel S → Sb geldt
SaA → SbaA en P (SbaA) geldt niet.
Opgave 3.J Gebruik invarianten om te bewijzen dat:
(i) bba 6∈ L12 .
Oplossing: Een invariant is nu
P (w) := w = λ of w = S, of w begint met een A of een a
25
we zullen het bewijs hier heel uitvoerig geven. Daartoe nummeren we eerst alle productieregels:
1
S → aSb
2
S → A
3
S → λ
4
A → aAbb
5
A → abb
Het is meteen duidelijk dat P (S) geldt. Nu moeten we nog laten zien dat de invariant
onder de productieregels behouden blijft. Dus als P (v) geldt voor zekere v en v → v 0
dan moet ook P (v 0 ) gelden. Omdat onze invariant van het type “w heeft ´e´en van deze
vier vormen” is, betekent dat dat we een grote gevalsonderscheiding moeten maken.
• v = λ. In dit geval is er geen enkele productieregel toepasbaar en dus valt hier
niets te controleren. In het bijzonder geldt dus in al die gevallen P (v 0 ).
• v = S. In dit geval moeten de eerste drie regels gecontroleerd worden. Uit de regels
hierboven zien we meteen dat v 0 dan ´e´en van de volgende vormen heeft: v 0 = aSb,
v 0 = A of v 0 = λ. En in alle drie de gevallen geldt P (v 0 ). Dus ook dit geval is in
orde.
• v begint met een A. In dit geval moeten we nog meer gevallen onderscheiden omdat
het mogelijk is dat in de rest van v ook nog hulpsymbolen staan. We schrijven ze
hieronder op, gevolgd door de mogelijke productieregels. Met v = A . . . bedoelen
we dat v begint met A en er in de rest geen hulpsymbolen A of S staan. Met
v = A . . . S . . . bedoelen we dat v begint met een A en er in de staart minimaal
´e´en keer een S staat.
4
A . . . → aAbb . . .
5
A . . . → abb
1
A . . . S . . . → A . . . aSb . . .
2
A...S ... → A...A...
3
A...S ... → A...λ...
4
A . . . S . . . → aAbb . . . S . . .
5
A . . . S . . . → abb . . . S . . .
4
A . . . A . . . → aAbb . . . A . . .
4
A . . . A . . . → A . . . aAbb . . .
5
A . . . A . . . → abb . . . A . . .
5
A . . . A . . . → A . . . abb . . .
We zien meteen dat alle mogelijke v 0 ofwel met een a ofwel met een A beginnen en
dus geldt in alle gevallen P (v 0 ).
26
• v begint met een a. We maken een soortgelijke analyse van de mogelijkheden:
1
a . . . S . . . → a . . . aSb . . .
2
a...S ... → a...A...
3
a...S ... → a...λ...
4
a . . . A . . . → a . . . aAbb . . .
5
a . . . A . . . → a . . . abb . . .
Ook hier zien we dat v 0 altijd met een a begint en dus geldt P (v 0 ) altijd.
Op dit moment hebben we dus bewezen dat P een invariant is van de grammatica.
Omdat P (bba) niet geldt moet dus wel gelden bba 6∈ L12 .
Zoals gezegd is dit bewijs heel uitvoerig opgeschreven. Natuurlijk mag je het ook anders
doen. Voor het geval v begint met een a kun je bijvoorbeeld volstaan met iets als: er is
geen enkele productieregel die de eerste letter verandert en dus begint v 0 automatisch
ook met een a.
(ii) aabbb niet geproduceerd kan worden via de grammatica voor L3 die je in opgave 3.F
gemaakt hebt.
Oplossing: Een invariant is hier
P (w) := w bevat een S of een c
Wederom geldt P (S). Verder geldt dat P een invariant is onder de productieregels.
Immers de regels voor A en B veranderen het aantal S-en niet en verminderen het
aantal c’s niet. En de regels voor S laten ofwel het aantal S-en gelijk ofwel neemt het
aantal c’s met ´e´en toe. Duidelijk is ook dat aabbb geen S en geen c bevat. Dus P (aabbb)
geldt niet en dus aabbb 6∈ L3 .
(iii) aabbb niet geproduceerd kan worden via de grammatica voor L4 die je in opgave 3.F
gemaakt hebt.
Oplossing: Een voor de hand liggende keuze als invariant is
P (w) := het eerste symbool van w is hetzelfde als het laatste
Dan geldt P (S). Echter, in tegenstelling tot de verwachting blijft deze eigenschap niet
behouden onder de productieregels. Stel bijvoorbeeld dat v = SS. Dan geldt P (v).
Maar we hebben dan de productie SS → Sc. En P (Sc) geldt duidelijk niet. Hier merk
je echt dat de invariant behouden moet blijven voor alle woorden v en in het bijzonder
dus ook voor woorden als v = SS die je helemaal nooit met deze grammatica kunt
maken!
Toch is de essentie van de invariant niet slecht. We hoeven hem alleen maar uit te
breiden om problemen als hierboven te voorkomen. Neem
P (w) := het eerste symbool van w is hetzelfde als het laatste en w bevat
maximaal ´e´en S die dan ook nog eens precies in het midden van w staat
Duidelijk is dat P (S) weer geldt. Voor de productieregels maken we de volgende gevalsonderscheiding.
• v bevat geen S. Dan is het heel simpel: er zijn geen productieregels toepasbaar
dus voor alle v 0 met v → v 0 geldt P (v 0 ).
27
• v bevat precies ´e´en S die in het midden staat van v. Dus v = xySzx met x ∈
{a, b, c}, y, z ∈ {a, b, c}∗ en |y| = |z|. De volgende producties zijn dan mogelijk:
xySzx → xyaSazx
xySzx → xybSbzx
xySzx → xycSczx
xySzx → xyazx
xySzx → xybzx
xySzx → xyczx
En het is meteen duidelijk dat P (v 0 ) geldt voor al deze mogelijkheden. Dus is P
een invariant van de grammatica. Duidelijk is ook dat P (aabbb) niet geldt. Dus
aabbb 6∈ L4 .
Opgave 3.K
(i) Bekijk de volgende grammatica over alfabet {a, b, c}:
S → A|B
A → abS | λ
B → bcS | λ
Ga na of je de volgende woorden kunt produceren met deze grammatica: abab, bcabbc,
abba. Lukt dat, geef dan een productie. Lukt dat niet, geef dan een geschikte invariant
waarmee je dit zou kunnen bewijzen.
Oplossing: abab en bcabbc kunnen wel geproduceerd worden:
S → A → abS → abA → ababS → ababA → abab
S → B → bcS → bcA → bcabS → bcabB → bcabbcS → bcabbcB → bcabbc
Het woord abba kan niet worden geproduceerd. Bekijk maar de eigenschap
P (w) := het laatste symbool van w dat geen hulpsymbool is, is geen a
Dit is een invariant. Omdat S geen niet-hulpsymbolen bevat, geldt P (S) automatisch.
Stel nu dat we een v hebben met P (v). Dan is het laatste symbool dat geen hulpsymbool
is geen a, maar een b of c. We onderscheiden weer twee gevallen:
• Er staan alleen maar hulpsymbolen in v. Dan zijn we op dezelfde manier als voor
S meteen klaar.
• Er is echt een laatste niet-hulpsymbool aanwezig. Noem dat x. We maken nu verder
onderscheid naar de in v aanwezige hulpsymbolen en hun bijbehorende producties.
– Als er een hulpsymbool voor x staat, dan maakt het niet uit welke productieregel we daarop toepassen. Omdat er alleen maar dingen voor x veranderen,
blijft x het laatste niet-hulpsymbool dat dus automatisch ongelijk aan a blijft.
– Als er een A achter x staat kunnen er twee productieregels worden toegepast:
. . . x . . . A . . . → . . . x . . . abS . . .
...x...A... → ...x...λ...
28
Omdat er op de . . . achter de x alleen maar hulpsymbolen kunnen staan, is in
het eerste geval het laatste niet-hulpsymbool de b direct voor de S geworden
en dus ongelijk aan a. In het tweede geval is x het laatste niet-hulpsymbool
gebleven en dus ook nog steeds ongelijk aan a. In beide gevallen geldt P (v 0 )
dus.
– Als er een B achter x staat, krijg je twee analoge gevallen. In het ene geval
wordt het laatste niet-hulpsymbool een c en in het andere geval blijft het weer
x. Dus ook nu geldt P (v 0 ) voor alle mogelijkheden.
– Als er een S achter de x staat zijn er ook twee mogelijkheden. Maar beide
leveren alleen maar andere hulpsymbolen op en dus blijft x automatisch het
laatste niet-hulpsymbool (en dus ongelijk aan a). Dus ook in dit geval geldt
P (v 0 ).
Dus P is inderdaad een invariant. Echter, het laatste niet-hulpsymbool van abba is een
a en dus geldt P (abba) niet en kan dat woord dus niet geproduceerd worden.
(ii) Beschrijf de reguliere taal L13 die deze grammatica produceert met een reguliere expressie.
Oplossing: De taal L13 die deze grammatica produceert wordt ook gegeven
door de
reguliere expressie ((ab) ∪ (bc))∗ , in andere woorden L13 = L ((ab) ∪ (bc))∗ .
(iii) Maak een rechtslineaire grammatica voor de taal L14 bestaande uit woorden van de
vorm ab . . . aba (dus a’s en b’s om en om met vooraan en achteraan een a; zorg dat je
ook a krijgt).
Oplossing: Een rechts-lineaire grammatica voor de woorden van de vorm ab . . . aba is
S → abS | a
Een andere mogelijkheid die natuurlijk ook goed is:
S → aB
B → bS | λ
Opgave 3.L Geef rechtslineaire grammatica’s voor de talen uit opgave 3.D:
(i) L6 := {w ∈ {a, b}∗ | iedere a in w wordt direct gevolgd door een b},
Oplossing:
S → abS | bS | λ
(ii) L7 := de taal van alle goedgevormde integer-expressies. Deze bestaan uit de symbolen 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, maar ze beginnen nooit met een 0 (behalve het getal 0 zelf
natuurlijk) en mogen eventueel worden voorafgegaan door een + of een −.
Oplossing:
S → +T | −T | T
T
→ 0 | 1C | 2C | 3C | 4C | 5C | 6C | 7C | 8C | 9C
C → 0C | 1C | 2C | 3C | 4C | 5C | 6C | 7C | 8C | 9C | λ
(iii) L8 := de taal van alle goedgevormde rekenkundige expressies zonder haakjes. Deze
bestaan uit natuurlijke getallen met daartussen de operatoren +, − of ×, bijvoorbeeld
7 + 3 × 29 − 78.
29
Oplossing:
S → 0 | 1C | 2C | 3C | 4C | 5C | 6C | 7C | 8C | 9C
C → 0C | 1C | 2C | 3C | 4C | 5C | 6C | 7C | 8C | 9C | λ | A
A → +S | −S | ×S
Merk op dat in deze uitwerking een rekenkundige expressie ook kan bestaan uit ´e´en
getal zonder operatoren.
Opgave 3.M Hieronder tonen we een grammatica voor een klein gedeelte van de Engelse
taal.
S = hzini
hzini
honderwerpvormi
heigennaami
hzelfstandignaamwoordi
hlidwoordi
hwerkwoordvormi
hwerkwoordi
hbijwoordi
hbijvoeglijknaamwoordlijsti
hbijvoeglijknaamwoordi
hlijdendvoorwerpvormi
hlijdendvoorwerpvormi
→
→
→
→
→
→
→
→
→
→
→
→
→
honderwerpvormihwerkwoordvormi.
honderwerpvormihwerkwoordvormihlijdendvoorwerpvormi.
heigennaami | hlidwoordihzelfstandignaamwoordi
John | Jill
bicycle | mango
a | the
hwerkwoordi | hbijwoordihwerkwoordi
eats | rides
slowly | frequently
hbijvoeglijknaamwoordihbijvoeglijknaamwoordlijsti | λ
big | juicy | yellow
hbijvoeglijknaamwoordlijstiheigennaami
hlidwoordihbijvoeglijknaamwoordlijstihzelfstandignaamwoordi
(i) Is deze grammatica rechtslineair?
Oplossing: Deze grammatica is contextvrij, maar niet rechts-lineair (bijvoorbeeld de
eerste productieregel voldoet niet).
(ii) Laat zien hoe je de volgende zin produceert: Jill frequently eats a big juicy yellow mango.
Oplossing:
• <zin>
• →<onderwerpvorm><werkwoordvorm><lijdendvoorwerpvorm>. (R2)
• →<eigennaam><werkwoordvorm><lijdendvoorwerpvorm>. (R3.1)
• →Jill<werkwoordvorm><lijdendvoorwerpvorm>. (R4.2)
• →Jill<bijwoord><werkwoord><lijdendvoorwerpvorm>. (R7.2)
• →Jill frequently <werkwoord><lijdendvoorwerpvorm>. (R9.2)
• →Jill frequently eats <lijdendvoorwerpvorm>. (R8.1)
• →Jill frequently eats <lidwoord><bijvoeglijknaamwoordlijst><zelfstandignaamwoord>. (R13)
• →Jill frequently eats a <bijvoeglijknaamwoordlijst><zelfstandignaamwoord>. (R6.1)
• →Jill frequently eats a <bijvoeglijknaamwoord><bijvoeglijknaamwoordlijst><zelfstandignaamwoord>. (R10.1)
• →Jill frequently eats a big <bijvoeglijknaamwoordlijst><zelfstandignaamwoord>. (R11.1)
• →Jill frequently eats a big <bijvoeglijknaamwoord><bijvoeglijknaamwoordlijst><zelfstandignaamwoord>. (R10.1)
• →Jill frequently eats a big juicy <bijvoeglijknaamwoordlijst><zelfstandignaamwoord>. (R11.2)
• →Jill frequently eats a big juicy <bijvoeglijknaamwoord><bijvoeglijknaamwoordlijst><zelfstandignaamwoord>. (R10.1)
• →Jill frequently eats a big juicy yellow <bijvoeglijknaamwoordlijst><zelfstandignaamwoord>. (R11.3)
• →Jill frequently eats a big juicy yellow <zelfstandignaamwoord>. (R10.2)
• →Jill frequently eats a big juicy yellow mango. (R5.2)
(iii) Maak zelf andere zinnetjes.
Oplossing: Doe zelf.
30
Opgave 3.N Bekijk de volgende automaat M1 .
M1 :
/ q0
O
/ q1
a
b
a
b
& x
q3 o
a
b
a
q2
;
b
k
In deze automaat is Q = {q0 , q1 , q2 , q3 }, F = {q3 } en Σ = {a, b}.
(i) Ga voor de volgende woorden na of ze geaccepteerd worden: abaab, aaaba, bab, λ en
aabbab.
Oplossing: De woorden worden op de volgende manier verwerkt:
a
b
a
a
b
a
a
a
b
a
b
a
b
a
a
b
b
a
abaab : q0 → q1 → q3 → q0 → q1 → q3
aaaba : q0 → q1 → q2 → q3 → q2 → q3
bab : q0 → q2 → q3 → q2
λ : q0
b
aabbab : q0 → q1 → q2 → q2 → q2 → q3 → q2
Alleen de woorden abaab en aaaba eindigen in een eindtoestand (q3 ), dus alleen die twee
woorden worden geaccepteerd.
(ii) Gelden de volgende uitspraken? Geef steeds een tegenvoorbeeld of een bewijs.
(1) Als w geaccepteerd wordt, dan wordt wabba ook geaccepteerd.
Oplossing: Dit is waar. Stel dat w geaccepteerd wordt, dan zit de automaat na het
lezen van w dus in toestand q3 . Vervolgens moet vanuit q3 dan nog de string abba
a
b
b
a
gelezen worden: q3 → q0 → q2 → q2 → q3 . En dus bevindt de automaat zich na
het lezen van wabba ook in een eindtoestand en wordt dat woord dus geaccepteerd.
(2) Als w geaccepteerd wordt, dan wordt wab niet geaccepteerd.
Oplossing: Dit is waar. Bewijs het nu zelf analoog aan het vorige geval.
(3) Als w niet geaccepteerd wordt, dan wordt waa ook niet geaccepteerd.
Oplossing: Dit is niet waar. Neem bijvoorbeeld w = a. Dan wordt w niet
geaccepteerd, maar waa wordt wel geaccepteerd.
(4) Als w niet geaccepteerd wordt, dan wordt wbb ook niet geaccepteerd.
Oplossing: Dit is waar. Als de automaat na w ge¨eindigd is en w is niet geaccepteerd, zit hij dus in q0 , q1 of q2 . Maar vanuit elk van deze toestanden ga je na het
verwerken van bb naar toestand q2 en dat is geen eindtoestand en dus wordt wbb
inderdaad niet geaccepteerd.
Opgave 3.O Concludeer uit de grammatica G3 dat
(i) (aba)k ab ∈ L(G3 ) voor k ≥ 0,
Oplossing: S → abaS → . . . → (aba)k S → (aba)k ab voor iedere k ≥ 0. Dus eerst k
keer de regel S → abaS toepassen en dan ´e´en keer de regel S → ab.
(ii) aabk a ∈ L(G3 ) voor k ≥ 0,
Oplossing: S → aaB → aabB → aabbB → . . . → aabk B → aabk a voor iedere k ≥ 0.
Dus eerst de regel S → aaB toepassen, dan k keer regel B → bB en tenslotte ´e´en keer
B → a.
31
(iii) als w ∈ L(G3 ), dan ook abaw ∈ L(G3 ),
Oplossing: S → abaS en omdat w geaccepteerd is weet je ook dat er een S → . . . → w
bestaat. Maar dan bestaat dus ook S → abaS → . . . → abaw.
(iv) als w ∈ L(G3 ), dan ook aaaaw ∈ L(G3 ),
Oplossing: S → aaB → aaaaS en je weet ook dat S → . . . → w bestaat, dus ook
S → aaB → aaaaS → . . . → aaaaw.
Opgave 3.P Maak een rechtslineaire grammatica bij de eindige automaat M0 , zoals boven
gedaan voor M1 . Verklein deze grammatica door overbodige productieregels en hulpsymbolen
weg te laten.
Oplossing: Introduceer S voor q0 , A voor q1 , B voor q2 en C voor q3 .
S → aA | bC
A → bA | aB
B → aC | bB | λ
C → aC | bC
Omdat A, B en C recursief naar zichzelf verwijzen, kun je die niet elimineren door substitutie.
Echter, omdat elke productie die naar C gaat nooit tot een woord dat geaccepteerd wordt zal
leiden, kan deze C weggelaten worden zonder dat de taal die bij de grammatica hoort wijzigt.
Je krijgt dan:
S → aA
A → bA | aB
B → bB | λ
Opgave 3.Q Maak een eindige automaat die de taal van de volgende grammatica accepteert.
S → abS | aA | bB
A → aA | λ
B → bB | λ
Oplossing: Eerst eens kijken welke woorden er zoal geproduceerd kunnen worden: a,
aa, aaa, b, bb, bbb, aba, abaa, abaaa, abb, abbb, abbb, ababa, ababaa, ababaaa, ababb, ababbb,
ababbbb,. . . . De taal waar het hier om gaat lijkt dan ook de taal L((ab)∗ (aa∗ ∪ bb∗ )) te zijn.
Een automaat die diezelfde taal accepteert is:
/ q0 k a / q1
/ q2
a
b
b
3
b
q3
a
/ q4
a,b
32
U
~
b
k
a
Opgave 3.R Bekijk de eindige automaat M3 :
b
M3 :
a
/ q0 k
b
+ q
1
b
b
a
q2
a
k
Maak een rechtslineaire grammatica die L(M3 ) genereert.
Oplossing: Eerst weer eens kijken welke woorden allemaal geaccepteerd worden: λ, b, bb,
bbb, ab, abab, bab, bbab, aab, aaab, aaaab, . . . . Is dit misschien de taal van alle woorden die
niet op een a eindigen? Introduceer weer S voor q0 , A voor q1 en B voor q2 en je krijgt de
grammatica:
S → bS | aA | λ
A → bS | aB
B → bS | aB
Opvallend is dat de laatste twee regels min of meer hetzelfde zijn. Als je hier goed over
nadenkt, kun je inzien dat je de grammatica kunt reduceren tot:
S → bS | aA | λ
A → bS | aA
Dit hadden we natuurlijk ook al aan de automaat kunnen zien: de uitgaande pijlen van q1
en q2 zijn gelijk en geen van twee¨en is een eindtoestand, dus hun gedrag is hetzelfde. Dus
kunnen ze ook wel samengenomen worden en dan krijgen we de simpelere automaat
b
M30 :
/ q0 k
a
+ q
1
b
a
k
die dezelfde taal accepteert als M3 .
Opgave 3.S Bekijk de eindige automaat M4 :
b
M4 :
/ q0 k
a
+ q
1
b
k
(i) Maak een rechtslineaire grammatica die L(M4 ) genereert.
Oplossing:
S → bS | aA
A → aA | bS | λ
33
a
(ii) Geef een (eenvoudige) beschrijving van L(M4 ).
Oplossing: Door sterk te letten op de structuur van de automaat kom je al snel tot
deze beschrijving: {bk aal (bbm aan )p | k, l, m, n, p ≥ 0} of L(b∗ aa∗ (bb∗ aa∗ )∗ ). Echter, als
je wat verder kijkt, zie je dat de taal L(M4 ) eigenlijk gekarakteriseerd wordt door het
feit dat het laatste symbool een a moet zijn. Maar dat betekent dat de taal ook zo kan
worden beschreven: L(M4 ) = L((a ∪ b)∗ a).
(iii) Als we alle toestanden eindtoestand maken, welke taal accepteert M4 dan?
Oplossing: {a, b}∗ (alle woorden over {a, b}).
(iv) Als we de eindtoestanden en de niet-eindtoestanden omwisselen, welke taal accepteert
M4 dan?
Oplossing: Het complement van L(M4 ), dwz. alle woorden over {a, b} die niet in
L(M4 ) zitten. Uit de structuur van de automaat volgt de beschrijving: {bk (aal bbm )p |
k, l, m, p ≥ 0}. In termen van reguliere expressies krijgen we dan de beschrijving
L(b∗ (aa∗ bb∗ )∗ ). Echter, als we even herinneren dat L(M4 ) = L((a ∪ b)∗ a), dan is het
complement natuurlijk alles dat niet op een a eindigt. Dus wat op een b eindigt of λ.
Dus een simpelere beschrijving voor het complement van L(M4 ) is L((a ∪ b)∗ b ∪ λ).
Opgave 3.T Maak een eindige automaat die de taal L15 := {(ab)k (aba)l | k, l ≥ 0} over
Σ = {a, b} accepteert.
Oplossing: Deze opgave staat bekend als een erg lastige opgave!
/ q0
/ q2
a
b
a
' w
7 > q1 U `
b
a,b
b
q7 o
a
q6 o
b
/ q3
R
b
b
a
a
q o
8 5
b
a
q4
a
Hoe vind je nu zo’n automaat? Een combinatie van nadenken en proberen om zo min mogelijk
toestanden toe te voegen. Een reconstructie:
1. λ ∈ L15 dus begintoestand q0 moet tevens eindtoestand zijn.
b
2. q0 → . . . ? Merk op dat woorden uit L15 nooit met een b beginnen, dus weten we meteen
b
dat er een put q1 nodig is met q0 → q1 .
a
3. q0 → . . . ? Omdat a 6∈ L15 moet er een nieuwe toestand q2 gemaakt worden die geen
a
eindtoestand is en q0 → q2 .
a
b
4. q1 → q1 en q1 → q1 want q1 is de put.
a
a
5. q2 → . . . ? Omdat woorden nooit met aa beginnen, moet a naar de put, dus q2 → q1 .
b
6. q2 → . . . ? Omdat ab ∈ L15 moet b naar een eindtoestand: q0 of een nieuwe.
b
• Als q2 → q0 dan wordt aba niet geaccepteerd, dus dat kan niet.
34
b
Er moet dus een nieuwe eindtoestand q3 worden toegevoegd: q2 → q3 .
a
7. q3 → . . . ? Omdat aba ∈ L15 moet a naar een eindtoestand: q0 , q3 of een nieuwe.
a
• Als q3 → q0 dan wordt abaab geaccepteerd, terwijl abaab 6∈ L15 , dus dat kan niet.
a
• Als q3 → q3 dan wordt abaa geaccepteerd, terwijl abaa 6∈ L15 , dus dat kan ook
niet.
a
Er moet dus een nieuwe eindtoestand q4 worden toegevoegd: q3 → q4 .
b
b
8. q3 → . . . ? Omdat woorden nooit met abb beginnen, moet b naar de put: q3 → q1 .
a
9. q4 → . . . ? Omdat abaa 6∈ L15 mag a niet naar een eindtoestand en omdat abaaba ∈ L15
mag a niet naar de put. Dus naar q2 of naar een nieuwe niet-eindtoestand.
a
• Als q4 → q2 dan wordt abaab geaccepteerd, terwijl abaab 6∈ L15 , dus dat kan niet.
a
Er moet dus een nieuwe niet-eindtoestand q5 worden toegevoegd: q4 → q5 .
b
10. q4 → . . . ? Omdat abab ∈ L15 moet b naar een eindtoestand: q0 , q3 , q4 of een nieuwe.
b
• Als q4 → q0 dan wordt ababaaba naar de put gestuurd, terwijl ababaaba ∈ L15 , dus
dat kan niet.
b
• Als q4 → q3 dan zijn er geen problemen, dus laten we dit maar proberen en kijken
of we de automaat af kunnen maken.
b
Dus q4 → q3 .
a
a
11. q5 → . . . ? Omdat woorden nooit met abaaa beginnen, moet a naar de put: q5 → q1 .
b
12. q5 → . . . ? Omdat abaab 6∈ L15 , moet b naar een niet-eindtoestand. Omdat abaaba ∈
L15 , mag b niet naar de put. Dus de kandidaten zijn: q2 , q5 of een nieuwe nieteindtoestand.
b
• Als q5 → q2 dan wordt abaabb geaccepteerd, terwijl abaabb 6∈ L15 , dus dat kan niet.
b
• Als q5 → q5 dan wordt abaaba naar de put gestuurd, terwijl abaaba ∈ L15 , dus dat
kan ook niet.
b
Er moet dus een nieuwe niet-eindtoestand q6 worden toegevoegd: q5 → q6 .
a
13. q6 → . . . ? Omdat abaaba ∈ L15 moet a naar een eindtoestand: q0 , q3 , q4 of een nieuwe.
a
• Als q6 → q0 dan wordt abaabaab geaccepteerd, terwijl abaabaab 6∈ L15 , dus dat kan
niet.
a
• Als q6 → q3 dan wordt weer abaabaab geaccepteerd, terwijl abaabaab 6∈ L15 , dus
dat kan ook niet.
a
• Als q6 → q4 dan wordt abaababa geaccepteerd, terwijl abaababa 6∈ L15 , dus dat kan
ook niet.
a
Er moet dus een nieuwe eindtoestand q7 worden toegevoegd: q6 → q7 .
35
b
14. q6 → . . . ? Omdat woorden nooit met abaabb kunnen beginnen, moet b naar de put:
b
q6 → q1 .
a
15. q7 → . . . ? Omdat abaabaa 6∈ L15 moet a naar een niet-eindtoestand: q2 , q5 , q6 of een
nieuwe.
a
• Als q7 → q2 dan wordt abaabaab geaccepteerd, terwijl abaabaab 6∈ L15 , dus dat kan
niet.
a
• Als q7 → q5 dan zijn er geen problemen. Je kunt hier dan meteen de loop van de
laatste aba-blokken herkennen.
a
Dus q7 → q5 .
b
16. q7 → . . . ? Omdat woorden nooit beginnen met abaabab, moet b naar de put. Dus
b
q7 → q1 .
En nu hebben we een geldige automaat waar precies de juiste woorden in worden geaccepteerd!
Opgave 3.U Maak een eindige automaat die de taal L16 := {(ab)k x(ab)l | x ∈ {a, b}, k, l ≥
0} over Σ = {a, b} accepteert.
Oplossing: Deze is waarschijnlijk iets makkelijker dan de vorige, maar desondanks nog
vrij lastig. (Ga voor jezelf na dat woorden van de vorm (ab)k a(ab)l en (ab)k b(ab)l inderdaad
geaccepteerd worden.)
/ q0
J
b
b
a
q1
b
a
a
/ q2 k
O
+
q4
b
b
/ q3
a
a
/ q5
k
a,b
Hoe vind je deze automaat nu? We gebruiken hier een andere methode dan bij opgave 3.T.
In het dictaat staat al beschreven hoe je vanuit een rechtslineaire grammatica vrij eenvoudig
een deterministische automaat kunt maken. Dus beginnen we hier ook maar met het maken
van zo’n rechtslineaire grammatica.
S → abS | aA | bA
A → abA | λ
Helaas werkt het algoritme uit het dictaat niet direct. Dat komt doordat er overlap is: de a is
zowel het begin van abS als van aA. Dus zorgen we ervoor dat we een equivalente grammatica
maken waar die overlap is verdwenen door een extra hulpsymbool in te voeren.
S → aP | bA
P
→ bS | A
A → abA | λ
Helaas hebben we nu een overgang P → A ge¨ıntroduceerd en dan werkt het algoritme ook
niet. Dus vervangen we de grammatica weer door een equivalente grammatica.
S → aP | bA
P
→ bS | abA | λ
A → abA | λ
36
Ga na dat deze inderdaad equivalent is! De grammatica die we nu hebben is van de goede
vorm en we kunnen dus het algoritme erop los laten door voor elk hulpsymbool een toestand
te maken (S → q0 , P → q1 en A → q2 ).
/ q0
J
b
/ q2
>
k
b
a
ab
ab
q1
Vervolgens breken we de woorden bij de pijlen op door extra toestanden te maken:
/ q0
J
b
/ q2 k
O
b
a
q1
a
+
q4
b
b
/ q3
a
En als we nu nog een put toevoegen krijgen we precies de automaat die we hierboven al
hadden laten zien.
/ q0
J
b
b
a
q1
b
a
a
/ q2 k
O
+
q4
b
b
/ q3
a
a
/ q5
k
a,b
Echter, er is nog een kleinere automaat die dezelfde taal voortbrengt. Als we namelijk naar
de toestanden q3 en q4 kijken dan zien we dat ze precies dezelfde uitgaande pijlen hebben:
een a-pijl naar put q5 en een b-pijl naar q2 . Maar dat betekent dat we die twee toestanden
ook samen mogen nemen, zonder dat de taal verandert.
/ q0
J
b
q1
b
a
/ q2
J
b
a
/ q3
a
b
a
/ q5
k
a,b
NB: Indien je op dezelfde manier te werk was gegaan als beschreven bij opgave 3.T dan had
je meteen deze kleinere automaat gekregen.
Opgave 3.V Bekijk de automaat M5 die (input) getallen in ‘normale’ decimale notatie accepteert. Zo’n getal mag eventueel beginnen met een + of een −, maar niet met een 0, behalve
natuurlijk als het van de vorm 0, 5 is, want dan is het weer wel goed. In het diagram staat
37
0 . . . 9 voor ´e´en van de cijfers uit 0 t/m 9 enz.
/ q0
M5 :
/ q1
>
0
+−
0
q2
1...9
,
~
I
1...9
q3
,
0...9
* q
4
k
0...9
(i) Vind je de automaat M5 goed? Worden alle ‘juiste’ getallen geaccepteerd en alle ‘foute’
verworpen?
Oplossing: Nee, de automaat is niet goed. Om te beginnen is hij niet deterministisch:
er ontbreekt een put om bijvoorbeeld vanuit q0 een komma te kunnen verwerken.
Daarnaast accepteert de automaat ook nog eens vreemde getallen: bijvoorbeeld ‘+0’,
‘-0’ en ‘+37,’. Zijn getallen zonder komma in decimale notatie? En kan een getal in
decimale notatie met een komma eindigen? Hier staan we dat niet toe, maar je kunt
daarover van mening verschillen. Als jij hier anders over denkt, zorg dan dat jouw
automaat overeenkomt met jouw idee over decimale getallen.
(ii) Pas M5 aan als je het er niet mee eens bent.
Oplossing: Er moeten verschillende problemen worden opgelost:
• Om te voorkomen dat getallen op een komma kunnen eindigen: voeg een toestand
q5 toe waar de ‘komma’ pijlen uit q1 en q3 naar toe wijzen en van q5 naar q4 een
0 . . . 9 pijl.
• Om te voorkomen dat er getallen zonder komma worden geaccepteerd: zorg dat q1
en q3 niet langer eindtoestanden zijn.
• Tenslotte moet er een put worden toegevoegd: maak een nieuwe q6 waar alle
‘verboden’ symbolen naar toe gaan.
,
M50 :
/ q0
/ q1
>
0
+−
0
q2
1...9
+−0...9
(
/ q6
7> IP k
+−,
,
+−,
+−,
~
I
q3
/ q5
1...9
,
0...9
0...9
q4
k
+−
38
0...9
+−,0...9
(iii) Geef een rechtslineaire grammatica die dezelfde taal als M5 genereert.
Oplossing: De volgende grammatica accepteert precies de taal van de originele M5 ,
dus inclusief de foute getallen als ‘+37,’.
S → 0A | 1B | 2B | 3B | 4B | 5B | 6B | 7B | 8B | 9B | +C | −C
A → ,D | λ
B → , D | λ | 0B | 1B | 2B | 3B | 4B | 5B | 6B | 7B | 8B | 9B
C → 0A | 1B | 2B | 3B | 4B | 5B | 6B | 7B | 8B | 9B
D → λ | 0D | 1D | 2D | 3D | 4D | 5D | 6D | 7D | 8D | 9D
En voor M50 wordt het:
S → 0A | 1B | 2B | 3B | 4B | 5B | 6B | 7B | 8B | 9B | +C | −C
A → ,D
B → , D | 0B | 1B | 2B | 3B | 4B | 5B | 6B | 7B | 8B | 9B
C → 0A | 1B | 2B | 3B | 4B | 5B | 6B | 7B | 8B | 9B
D → 0E | 1E | 2E | 3E | 4E | 5E | 6E | 7E | 8E | 9E
E → λ | 0E | 1E | 2E | 3E | 4E | 5E | 6E | 7E | 8E | 9E
39
4
Discrete wiskunde
Opgave 4.A Bewijs dat er in een boom van een punt p naar een ander punt q precies ´e´en
pad bestaat.
Oplossing: Deze opgave is nagenoeg geheel gebaseerd op definitie 4.2. Volgens die definitie
is een boom een samenhangende graaf zonder cykels. We moeten twee beweringen bewijzen:
• Er is minimaal ´e´en pad van p naar q.
• Er is maximaal ´e´en pad van p naar q.
Het eerste volgt meteen uit de definitie van samenhangend: tussen ieder tweetal punten
bestaat een pad. Dus ook tussen onze punten p en q.
Het tweede is makkelijk in te zien, maar moeilijk helemaal precies te bewijzen. Een
gebruikelijke techniek om aan te tonen dat er maximaal ´e´en pad is, is om aan te nemen dat
er twee verschillende paden zijn en dan tot een tegenspraak te komen:
p = x0 → x1 → x2 → · · · → xn−1 → xn = q en p = y0 → y1 → y2 → · · · → ym−1 → ym = q
We proberen aan te tonen dat we hiermee een cykel kunnen maken, wat een tegenspraak is.
Het eenvoudige argument dat we dan dus ook een cykel
p = x0 → x1 → x2 → · · · → xn−1 → xn = q = ym → ym−1 → ym−2 → · · · → y1 → y0 = p
hebben, gaat niet op omdat dit misschien geen pad is. Volgens de definitie van paden mogen
we elke lijn maar ´e´en keer doorlopen in een pad en dat is hier niet gegarandeerd. Bekijk maar
eens het volgende plaatje.
b
p
a
d
q
c
Er zijn duidelijk twee paden p → a → b → d → q en p → a → c → d → q, maar als je ze
achter elkaar zet krijg je
p→a→b→d→q→d→c→a→p
en daarin komen de lijnen (p, a) en (d, q) twee keer voor en dus is het geen pad en dus ook
geen cykel. Maar door de dubbelvoorkomende lijnen weg te laten kun je wel altijd een cykel
vinden. Hier bijvoorbeeld
a→b→d→c→a
En dus hebben we toch een tegenspraak. In het bijzonder is het niet nodig dat onze tegenvoorbeeldcykel door de speciale punten p en q gaat! Het algemene bewijs is te lastig en laten
we daarom weg. We volstaan met het idee om zo’n cykel te construeren:
• Verwijder het gemeenschappelijke beginstuk van de twee paden zodat je in een p0 begint
waar de twee paden meteen in de eerste stap verschillend zijn. Je hebt dan dus nog
steeds twee paden, alleen nu van p0 naar q.
40
• Bepaal het eerste punt waar de twee paden elkaar weer kruisen. Omdat dat in elk geval
in q gebeurt, weet je zeker dat het een keer moet gebeuren. Noem dit punt q 0 . We
hebben dan twee paden van p0 naar q 0 .
• Omdat we p0 en q 0 op deze manier geconstrueerd hebben, weten we nu dat we wel een
echt pad krijgen als we eerst het ene pad van p0 naar q 0 nemen en er vervolgens het
tweede pad achterstevoren, dus van q 0 naar p0 achter plakken.
• In het bijzonder is dit pad een cykel en dus kunnen we geen boom hebben als er twee
paden tussen p en q bestaan. Dus kan er maximaal ´e´en zo’n pad bestaan.
Opgave 4.B Een brug in een graaf G is een lijn l waarvoor geldt: als je l uit G weglaat,
wordt het aantal componenten verhoogd. Bewijs dat in een boom iedere lijn een brug is.
Oplossing: Kies maar eens een willekeurige lijn. Die lijn verbindt twee punten p en q
en is dus in het bijzonder een pad van p naar q. Op grond van opgave 4.A weten we nu dat
als we deze lijn weghalen, daarmee het enige pad tussen p en q is verdwenen. Dus zitten p
en q niet meer in dezelfde component en is door het weghalen het aantal componenten dus
verhoogd. Dus was deze willekeurige lijn een brug. Maar dan is elke lijn in een boom dus een
brug.
Opgave 4.C Bewijs dat voor alle n ≥ 1 geldt dat de Kn precies 21 n(n − 1) lijnen heeft.
Oplossing: Elk punt in Kn heeft graad n − 1. Dus vanuit elk punt vertrekken er n − 1
lijnen. Er zijn n punten, dus op die manier tellen we n(n − 1) lijnen. Echter, omdat elk punt
zowel beginpunt als eindpunt is, hebben we nu alle lijnen dubbel geteld. Dus het aantal lijnen
in Kn is 21 n(n − 1).
Opgave 4.D Ga na welke van de onderstaande grafen isomorf zijn:
1
3
G1
2
5
4
7
G2
6
a
8
c
G3
b
d
Als twee grafen isomorf zijn, geef dan een bijbehorend isomorfisme. En als twee grafen niet
isomorf zijn, leg dan uit waarom zo’n isomorfisme niet kan bestaan.
Oplossing: Isomorfe grafen hebben evenveel punten met dezelfde graden. In G2 hebben
alle punten graad 2, in de andere twee grafen niet. Dus G2 is niet isomorf met de andere twee
grafen. G1 en G3 zijn wel isomorf. Een isomorfisme ϕ is gegeven door ϕ(1) = b, ϕ(2) = a,
ϕ(3) = c en ϕ(4) = d, of afgekort zonder expliciet ϕ te vermelden: 1 7→ b, 2 7→ a, 3 7→ c en
4 7→ d.
Opgave 4.E Hier is een plattegrond G van een dorpje, waarbij de straten aangegeven worden
door lijntjes. Op ieder hoekpunt bevindt zich een kroeg. De kroegen zijn aangegeven door
punten, genummerd van 1 t/m 12:
41
11
1
2
3
8
9
12
4
5
6
7
10
Formuleer de volgende vragen in termen van Hamilton- of Euler-circuits/paden en beantwoord ze:
(i) Is het mogelijk, een wandeling te maken waarbij je iedere straat precies ´e´en keer doorloopt? Zo ja, geef dan zo’n wandeling. Zo nee, leg uit waarom niet.
Oplossing: Een wandeling waarbij je iedere straat–dus ieder lijntje–precies ´e´en keer
doorloopt is een Euler-pad. De vraag is dus eigenlijk of er een Euler-pad bestaat. Met
stelling 4.13 is dit makkelijk te beantwoorden. Hiervoor moeten we de graden van de
kroegen–de punten–bepalen.
punt graad punt graad punt graad punt graad
1
2
4
4
7
3
10
3
2
4
5
4
8
4
11
4
3
4
6
4
9
2
12
4
Alleen de punten 7 en 10 hebben oneven graad, dus volgens de stelling van Euler bestaat
er een Euler-pad. Een concreet voorbeeld van zo’n pad is: 7 → 12 → 5 → 10 → 7 →
6 → 12 → 11 → 4 → 8 → 1 → 2 → 11 → 3 → 9 → 8 → 2 → 3 → 4 → 5 → 6 → 10.
(ii) Is het mogelijk, een wandeling te maken waarbij je iedere straat precies ´e´en keer doorloopt en bovendien begint en eindigt bij kroeg 3? Zo ja, geef dan zo’n wandeling. Zo
nee, leg uit waarom niet.
Oplossing: Nu is de vraag eigenlijk of er een Euler-cykel bestaat. Het antwoord daarop
komt weer uit de stelling van Euler. Die stelt dat een Euler-cykel alleen bestaat als elk
punt een even graad heeft. We hebben al gezien dat dat hier niet het geval is en dus
bestaat er geen Euler-cykel. (En zeker geen die begint en eindigt bij punt 3.)
(iii) Bestaat er een kroegentocht waarin iedere kroeg precies ´e´en keer voorkomt? Zo ja, geef
dan zo’n tocht. Zo nee, leg uit waarom niet.
Oplossing: Nu gaat de wandeling door alle punten en gaat het dus om de vraag of er
een Hamilton-pad bestaat. Zo’n pad bestaat inderdaad. Neem bijvoorbeeld 12 → 7 →
10 → 6 → 5 → 4 → 11 → 3 → 9 → 8 → 1 → 2.
Opgave 4.F Hieronder vind je twee plattegronden van huizen.
(i) Teken bij elke plattegrond de bijbehorende graaf, waarbij je de vertrekken (inclusief het
42
buitengebied) door punten voorstelt en de deuren door lijnen. Bedenk dat punten in
een graaf een naam moeten hebben!
Oplossing:
g
a
e
b
d
c
a
f
e
b
c
d
Of in een wat schematischere weergave:
g
e
a
b
c
a
b
d
e
f
c
d
(ii) Zoek voor elk huis uit of het mogelijk is een rondwandelingetje te maken waarin je iedere
deur precies ´e´en keer gebruikt en bij je uitgangspunt terugkeert. Verklaar je antwoord en
mocht je conclusie zijn dat zo’n rondwandeling bestaat, geef dan een expliciet voorbeeld.
Oplossing: Omdat de deuren overeenkomen met de lijnen in de graaf, wordt hier dus
gevraagd of er een Euler-cykel is. Dus moeten we weer de graden gaan tellen.
a b c d e f g
Eerste huis
4 2 2 2 4 2 4
Tweede huis 2 4 2 2 4
In beide huizen hebben alle punten een even graad, dus kun je volgens de stelling van
Euler (4.13) een Euler-cykel maken. Bijvoorbeeld a → g → d → a → b → e → f → c →
g → e → a in het eerste huis en e → a → b → c → e → b → d → e in het tweede huis.
(iii) Zoek voor elk huis uit of het mogelijk is een rondwandelingetje te maken waarin je ieder
vertrek (en de tuin) precies ´e´en keer bezoekt en bij je uitgangspunt terugkeert. Verklaar
je antwoord en mocht je conclusie zijn dat zo’n rondwandeling bestaat, geef dan een
expliciet voorbeeld.
Oplossing: Omdat de vertrekken met de punten overeenkomen wordt er nu dus om
een Hamilton-circuit gevraagd. Bij het eerste huis is zo’n pad wel mogelijk. Neem
bijvoorbeeld g → d → a → b → e → f → c → g.
In het tweede huis is zo’n pad niet mogelijk. In een Hamilton-circuit moet namelijk
iedere lijn die aan een punt met graad twee ligt voorkomen (we moeten dat punt immers
in en uit). Als we die lijnen (e, c), (c, b), (e, a), (a, b), (e, d) en (d, b) tekenen, zien we
dat we het circuit niet af kunnen maken. Zowel punt e als b komt in drie van deze lijnen
voor en in een Hamilton-circuit mag elk punt maar in twee lijnen voorkomen.
43
Opgave 4.G Welke van de volgende grafen hebben een Hamilton-circuit? Geef zo’n circuit
of leg uit waarom zo’n circuit niet kan bestaan.
a
b
d
e
g
h
c
a
b
c
f
d
e
f
i
g
h
i
Oplossing:
Bij de eerste graaf is er wel een Hamilton-circuit mogelijk, bijvoorbeeld
a → b → c → i → f → e → h → g → d → a:
a
b
c
d
e
f
g
h
i
Bij de tweede graaf is het niet mogelijk om een Hamilton-circuit te maken. Zoals we al bij
opgave 4.F hebben gezien, moeten we over elke lijn die aan een punt van graad 2 ligt. We
moeten dus over alle horizontale lijnen in het midden. Als we bij een punt links beginnen,
gaan we dus eerst naar rechts, dan weer naar links, dan weer naar rechts, maar dan kunnen we
helaas niet meer terug terwijl dat wel zou moeten voor een Hamilton-circuit. Een Hamiltonpad is natuurlijk wel mogelijk: a → b → c → f → e → d → g → h → i.
Opgave 4.H Zij G de kubus-graaf, met als P de verzameling van de acht hoekpunten, en
als L de verzameling van de twaalf ribben.
(i) Is G planair?
Oplossing: Hieronder zie je twee representaties van de kubus-graaf. Dat de graaf
planair is volgt overduidelijk uit het tweede plaatje.
H
E
G
F
D
A
E
C
B
F
H
G
D
C
A
B
(ii) Heeft G een Hamilton-circuit?
Oplossing: Ja, kijk maar naar A → B → F → E → H → G → C → D → A:
E
F
H
G
D
C
A
B
(iii) Heeft G een Euler-circuit?
Oplossing: Nee, de graaf G heeft geen Euler-circuit want alle punten hebben oneven
graad terwijl de stelling van Euler juist zegt dat alle punten even graad moeten hebben
wil er een Euler-circuit bestaan.
44
Verklaar telkens je antwoord!
Opgave 4.I Laat zien dat de Petersen-graaf een Hamilton-pad heeft, maar geen Hamiltoncykel.
Oplossing: Een Hamilton-pad is bijvoorbeeld ab → cd → ae → bc → de → ac → bd →
ce → ad → be. Omdat er geen lijn is tussen ab en be kan dit pad in elk geval niet tot een
circuit worden uitgebreid.
Dat er in het algemeen geen Hamilton-circuit in de Petersen-graaf zit is moeilijk te bewijzen. Hier geven we een bewijs gebaseerd op lijnkleuringen1 . Dit moet te begrijpen zijn,
maar het hoeft uiteraard niet op een toets of tentamen gereproduceerd te worden. We gaan
de Petersen-graaf in drie kleuren proberen te verdelen. Dat doen we door de lijnen die op
het circuit liggen afwisselend rood en groen te kleuren en de lijnen die niet op het circuit liggen blauw te kleuren. De Petersen-graaf heeft 10 punten en 15 lijnen. Een Hamilton-circuit
heeft dus 10 lijnen. We vinden het een goede lijnkleuring als geen enkel punt twee lijnen met
dezelfde kleuren heeft. Dit betekent dus meteen dat er 5 rode, 5 groene en 5 blauwe lijnen
moeten zijn. Het bewijs dat er geen Hamilton-circuit is, komt er op neer dat we laten zien
dat zo’n lijnkleuring niet bestaat.
We bewijzen het uit het ongerijmde: we nemen aan dat het wel waar is en leiden dan
een tegenspraak af. Stel dat zo’n lijnkleuring wel bestaat. Dan weten we zeker dat er van de
vijf buitenste lijnen (ab, de), (de, bc), (bc, ae), (ae, cd) en (cd, ab) er minimaal twee dezelfde
kleur hebben, om de simpele reden dat je nu eenmaal geen vijf verschillende kleuren hebt.
Verder is het per definitie van de lijnkleuring zo dat twee lijnen die dezelfde kleur hebben,
geen gemeenschappelijk punt hebben. Zeg dat (de, bc) en (ae, cd) allebei rood zijn. Door de
graaf te draaien, kun je inzien dat het niet uitmaakt welke twee lijnen je rood kiest. Verder
kun je ook nagaan dat het niet uitmaakt welke kleur je kiest. Deze twee rode lijnen betekenen
dat de lijn (bc, ae) automatisch een andere kleur heeft. Zeg groen. Maar dat betekent dan
ook meteen dat de twee lijnen (bc, ad) en (ae, bd) blauw moeten zijn.
ab
ce
de
ac
cd
be
ad
bd
bc
ae
Kijken we nu verder in de buitenste lijnen dan zien we dat ofwel de lijn (ab, de) groen en de
lijn (cd, ab) blauw moet zijn ofwel net andersom. In elk geval betekent dat dat de lijn (ab, ce)
rood moet zijn. De andere twee kleuren zijn uit punt ab immers al gebruikt.
1
Merk op dat lijnkleuringen echt andere dingen zijn dan de puntkleuringen die wel uitgebreid aan bod
komen in het dictaat.
45
ab
ce
de
ac
cd
be
ad
bd
bc
ae
Maar dan hebben we een probleem. De lijn (ce, ad) moet groen zijn omdat hij tussen een
rode en een blauwe lijn inzit. Maar net zo moet de lijn (ce, bd) groen zijn. En dan komen er
dus twee groene en een rode lijn samen in het punt ce.
ab
ce
de
ac
cd
be
ad
bd
bc
ae
En dat mocht niet bij een goede lijnkleuring. Dus bestaat zo’n lijnkleuring niet. En dus zit
er ook geen Hamilton-circuit in de Petersen-graaf.
Opgave 4.J Bepaal het kleurgetal van de volgende grafen. Verklaar je antwoord.
Oplossing: De standaardtechniek om te laten zien dat een (eindige) graaf een bepaald
kleurgetal heeft, is om zo’n kleuring te geven. En vervolgens dient dan te worden uitgelegd
waarom het niet met minder kleuren kan.
46
Het is duidelijk dat de linkergraaf niet met ´e´en kleur gekleurd kan worden, dus het kleurgetal
is 2. Bij de rechtergraaf kunnen we in het midden de K4 zien zitten. Maar in de K4 zijn alle
punten buren van elkaar en dus zijn daar vier kleuren voor nodig. En dus is het kleurgetal
van de hele graaf ook 4.
Opgave 4.K Laat zien dat als een bipartite graaf een Hamilton-pad toelaat het aantal rode
en het aantal blauwe punten hoogstens ´e´en verschilt.
Oplossing: Een bipartite graaf kun je altijd opdelen in een aantal rode punten en een
aantal blauwe punten waarbij alle lijnen telkens een rood en een blauw punt met elkaar
verbinden. Een Hamilton-pad doet alle punten precies ´e´en keer aan. In een bipartite graaf
betekent dat dat zo’n Hamilton-pad afwisselend een rood en een blauw punt aandoet, want
er zijn immers geen directe verbindingen tussen punten met dezelfde kleur. Begin je met een
rood punt dan eindig je ofwel met een blauw punt ofwel weer met een rood punt. In het
eerste geval heb je precies evenveel rode als blauwe punten. In het tweede geval heb je exact
´e´en rood punt meer dan dat je blauwe punten hebt. Uiteraard werkt het argument hetzelfde
als je begonnen was met een blauw punt.
Opgave 4.L Op de Volksuniversiteit worden er heel wat vreemde talen aangeboden: Arabisch, Bulgaars, Chinees, Deens, Egyptisch, Fries en Grieks. Bij het maken van het rooster
voor de cursussen, moet de roostermaker met twee zaken rekeninghouden:
• Het gebouw met tien lokalen kan alleen in zijn geheel gehuurd worden, dus hoe meer cursussen er parallel gegeven kunnen worden, hoe goedkoper het voor de Volksuniversiteit
is.
• Sommige studenten hebben zich voor verschillende cursussen ingeschreven en die betreffende talen mogen dus niet tegelijk gegeven worden. In onderstaande tabel betekent
een ∗ op een bepaalde positie, dat de taal uit die rij niet mag samen vallen met de taal
uit die kolom.
A
A
B
C
D
E
F
G
*
*
*
B
*
*
*
*
C
*
*
D
*
*
*
*
*
*
E
F
*
*
*
*
*
*
*
47
G
*
*
Hoeveel verschillende lesblokken zal de roostermaker gebruiken om aan beide eisen te voldoen?
Oplossing: Het minimale aantal verschillende lesblokken komt overeen met het kleurgetal
van de graaf waarbij de punten de talen weergeven en de lijnen aangeven welke talen er niet
tegelijk mogen worden gegeven. Met andere woorden, de lijnen geven aan waar studenten
beide vakken volgen.
We beginnen bij taal A en lopen door de tabel heen om alle lijnen te bepalen en zodra we
weten dat we zeker een nieuwe kleur nodig hebben wijzen we zo’n kleur toe aan een taal. Op
grond van symmetrie hoeven we alleen de helft rechtsboven te bekijken. Deze methode zorgt
ervoor dat we een minimale kleuring krijgen.
• Taal A moet een kleur hebben: zwart.
• A en B mogen niet samenvallen, dus B moet een andere kleur hebben: rood.
• A en C mogen niet samenvallen, dus C is niet zwart, maar kan misschien nog wel rood
zijn.
• A en D mogen niet samenvallen, dus D is niet zwart, maar kan misschien nog wel rood
zijn.
• A en G mogen niet samenvallen, dus G is niet zwart, maar kan misschien nog wel rood
zijn.
• B en C mogen niet samenvallen, dus C is niet zwart en niet rood, dus C moet een nieuwe
kleur hebben: groen.
• B en D mogen niet samenvallen, dus D is niet zwart en niet rood, maar kan misschien
nog wel groen zijn.
• B en E mogen niet samenvallen, dus E is niet rood, maar kan misschien nog wel zwart
of groen zijn.
• B en G mogen niet samenvallen, dus G is niet zwart en niet rood, maar kan misschien
nog wel groen zijn.
• C en D mogen niet samenvallen, dus D is niet zwart, niet rood en niet groen, dus D
moet een nieuwe kleur krijgen: blauw.
• C en F mogen niet samenvallen, dus F is niet groen, maar kan misschien nog wel zwart,
rood of blauw zijn.
• D en F mogen niet samenvallen, dus F is niet groen en niet blauw, maar kan misschien
nog wel zwart of rood zijn.
• Omdat E alleen maar niet mag samenvallen met B, weten we dat E zwart, groen of
blauw mag zijn. We kiezen zwart.
• F en G mogen niet samenvallen, dus G is niet zwart, niet rood en heeft ook niet dezelfde
kleur als F.
• Er zijn verder geen beperkingen meer, dus hebben we nog wat vrijheid om de kleuren
van F en G te kiezen. Zeg F wordt zwart en G groen.
48
Uiteindelijk is de graaf dus met vier kleuren gekleurd: zwart voor Arabisch, Egyptisch en
Fries, rood voor Bulgaars, groen voor Chinees en Grieks en blauw voor Deens.
G
F
E
A
D
B
C
De roostermaker heeft dus vier verschillende lesblokken nodig, want elke kleur representeert
de lessen die tegelijk gegeven mogen worden.
Opgave 4.M Definieer met recursie de rij an door:
a0 = 3
an+1 = a2n − 2an voor n ≥ 0
Geef de waarde van a5 .
Oplossing:
a1 = a20 − 2a0 = 32 − 2 · 3 = 3
a2 = a21 − 2a1 = 32 − 2 · 3 = 3
a3 = a22 − 2a2 = 32 − 2 · 3 = 3
a4 = a23 − 2a3 = 32 − 2 · 3 = 3
a5 = a24 − 2a4 = 32 − 2 · 3 = 3
Opgave 4.N Definieer met recursie de rij bn door:
b0 = 4
bn+1 = b2n − 2bn voor n ≥ 0
Geef de waarde van b5 .
Oplossing:
b1 = b20 − 2b0 =
42 − 2 · 4
=
16 − 8
=
8
2
b2 = b1 − 2b1 =
82 − 2 · 8
=
64 − 16
=
48
b3 = b22 − 2b2 =
482 − 2 · 48
=
2304 − 96
=
2208
2
b4 = b3 − 2b3 =
22082 − 2 · 2208
=
4875264 − 4416
=
4870848
b5 = b24 − 2b4 = 48708482 − 2 · 4870848 = 23725160239104 − 9741696 = 23725150497408
Opgave 4.O Bekijk de rij cn gedefinieerd door:
1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, . . .
Geef een recursieve formule voor cn .
49
Oplossing: Vanaf het derde getal is het telkens zo dat de twee voorgaande getallen bij
elkaar opgeteld het nieuwe getal geven. Er moeten dus twee startwaarden gegeven worden en
daarna kan de recursie gebruikt worden.
c0 = 1
c1 = 3
cn+2 = cn+1 + cn voor n ≥ 0
Opgave 4.P De Maple-programma’s uit voorbeeld 4.23 zijn niet erg robuust. Indien er voor
m een niet natuurlijk getal of 0 wordt gebruikt, zal Maple in een oneindige lus terechtkomen.
Probeer de programma’s zo aan te passen dat er een juiste uitkomst wordt bepaald indien
n, m ∈ Z.
Oplossing: Als het goed is kun je volgen wat onderstaande programma’s doen. Wat
betreft syntax kan het in Maple overigens wel korter worden opgeschreven, maar dat was hier
niet het doel.
powZ := proc ( n ,m)
multZ := proc ( n ,m)
i f m=0
i f m=0
then 1
then 0
else
else
i f m<0
i f m<0
then 1/powZ ( n,−m)
then −multZ ( n,−m)
else
else
i f m=1
i f m=1
then n
then n
e l s e multZ ( powZ ( n ,m−1) ,n )
e l s e multZ ( n ,m−1)+n
end i f
end i f
end i f
end i f
end i f
end i f
end proc ;
end proc ;
Opgave 4.Q De uitvinder van het schaakbord mocht van de koning van Perzi¨e een beloning
uitzoeken. Hij mocht vragen wat hij maar wilde. Hij koos voor de volgende beloning. Hij
wilde op het eerste vakje van het schaakbord 1 rijstkorrel hebben, op de tweede 2, op de derde
4, etc. Dus op ieder vakje twee keer zoveel rijstkorrels. De koning vond hem erg bescheiden.
Laten we eens kijken hoeveel hij vroeg: hij wilde dus
1 + 2 + 22 + 23 + 24 + · · · + 263
korrels hebben. Kun je een eenvoudige formule vinden voor de uitkomst van deze som?
[Hint: tel eerst eens wat termen uit het begin van de rij 1, 2, 22 , 23 , 24 , . . . op en bekijk het
verband, dus bekijk 1 en 1 + 2 en 1 + 2 + 22 enz. Herken je iets? Wat is je vermoeden van de
uitkomst? Kun je dit met inductie bewijzen?]
Oplossing: Definieer de rij sn recursief als volgt
s1 = 1
sn = sn−1 + 2n−1 voor n ≥ 2
In het bijzonder betekent dit dus dat sn het totale aantal korrels geeft op de eerste n velden
samen. Dus uiteindelijk willen we straks s64 weten. Hopelijk krijg je na wat proberen het
vermoeden dat sn = 2n − 1. Dat proberen we te bewijzen met inductie.
50
Inductie Hypothese (IH): Definieer P (n) als sn = 2n − 1.
Basisstap n = 1: P (1) geldt want s1 = 1 = 21 − 1.
Inductiestap: Neem aan dat P (n) geldt. We moeten laten zien dat dan ook P (n + 1) geldt.
sn+1 = sn + 2n (definitie sn+1 )
= (2n − 1) + 2n (gebruik IH)
= 2 · 2n − 1 (elementair rekenwerk)
= 2n+1 − 1 (elementair rekenwerk)
Dus als P (n), dan ook P (n + 1).
Met inductie zien we nu dus dat voor alle n ∈ N, n ≥ 1 P (n) geldt, dus voor al die n geldt
sn = 2n − 1. Om te weten hoeveel er gevraagd werd door die uitvinder hoeven we nu alleen
nog maar s64 uit te rekenen: s64 = 264 − 1 = 18446744073709551615.
Opgave 4.R Gegeven is een rij an gedefinieerd door
a0
= 0
an+1 = an + 2n + 1 voor n ≥ 0
Bewijs dat voor elke n ∈ N geldt: an = n2 .
Oplossing: We beginnen weer met het expliciet opschrijven van ons predikaat P (n).
IH: Definieer P (n) als: an = n2 .
Basisstap n = 0: P (0) geldt want a0 = 0 en 02 = 0.
Inductiestap: We nemen aan dat P (n) geldt. Dus an = n2 . Nu willen we laten zien dat
P (n + 1) ook geldt. We moeten dus laten zien dat
an+1 = (n + 1)2
Zoals gebruikelijk beginnen we de linkerkant van deze vergelijking te herschrijven om
uiteindelijk op de rechterkant uit te komen.
an+1 = an + 2n + 1 (definitie an+1 )
= n2 + 2n + 1 (IH)
= (n + 1)2 (rekenregels)
En dat was precies wat we moesten laten zien.
Dus geldt an = n2 inderdaad voor alle n ∈ N.
Opgave 4.S In opgave 4.C heb je bewezen dat voor elke n ≥ 1 geldt dat de graaf Kn precies
1
2 n(n − 1) lijnen heeft. Bewijs dat nu nog eens, maar dan met inductie naar n.
Oplossing: Het bewijs volgt het gebruikelijke patroon.
IH: Definieer P (n) als: Kn heeft precies 12 n(n − 1) lijnen.
51
Basisstap n = 1: P (1) geldt want de K1 bestaat uit ´e´en punt en nul lijnen. En natuurlijk
geldt ook 12 · 1 · (1 − 1) = 0.
Inductiestap: Neem aan dat P (n) geldt. Dan willen we laten zien dat P (n + 1) ook geldt.
We moeten dus laten zien dat de Kn+1 precies 21 (n + 1)n lijnen heeft. We doen dit door
Kn+1 op te bouwen uit Kn . Het is niet zo moeilijk in te zien dat de Kn+1 is opgebouwd
uit Kn en ´e´en extra punt, waarbij er vanuit dat extra punt precies ´e´en lijn loopt naar
elk punt van Kn . Met de IH weten we dat Kn precies 12 n(n − 1) lijnen heeft. Maar dan
is het aantal lijnen van Kn+1 gelijk aan:
1
n + n(n − 1) =
2
=
=
=
=
=
=
2
1
n + n(n − 1) (noemers gelijkmaken)
2
2
2n n(n − 1)
+
(breuken vermenigvuldigen)
2
2
2n + n(n − 1)
(breuken optellen)
2
2n + n2 − n
(haakjes uitwerken)
2
n2 + n
(vereenvoudigen)
2
(n + 1)n
(buiten haakjes halen)
2
1
(n + 1)n (herschrijven)
2
En dat was precies wat we moesten bewijzen.
Dus voor alle n ≥ 1 geldt P (n).
Opgave 4.T Bewijs met inductie dat voor alle n ∈ N, 2n ≥ n.
Oplossing: We gaan met inductie bewijzen dat voor alle n ∈ N 2n ≥ n.
IH: Definieer P (n) als: 2n ≥ n.
Basisstap n = 0: P (0) geldt want 20 = 1 ≥ 0.
Inductiestap: Neem aan dat P (n) geldt. Dan willen we laten zien dat P (n + 1) ook klopt:
P (n)
2n+1 = 2 · 2n ≥ 2 · n
Dus nu is de vraag of 2n ≥ n + 1? Dat geldt niet voor alle n ∈ N. Het geldt alleen
voor n ≥ 1. Dus uit P (1) kunnen we inderdaad P (2) bewijzen en uit P (2) weer P (3)
en verder. Maar uit P (0) kunnen we dus op deze manier nog niet bewijzen dat P (1)
geldt! Dus onze basisstap schiet te kort. Gelukkig kunnen we dat oplossen door een
extra basisstap toe te voegen:
Basisstap n = 1: P (1) geldt want 21 = 2 ≥ 1.
We hebben nu P (0) en P (1) apart bewezen en vervolgens met inductie P (n) voor n ≥ 2.
Maar dan hebben we dus voor alle n ∈ N bewezen dat 2n ≥ n.
52
Opgave 4.U We hebben al een mooie formule voor de som van de rij
1 + 2 + 3 + 4 + 5 + ··· + n =
(n + 1)n
.
2
Wat is het verband met het volgende plaatje?
•
•
•
•
•
◦
•
•
•
•
◦
◦
•
•
•
◦
◦
◦
•
•
◦
◦
◦
◦
•
◦
◦
◦
◦
◦
Oplossing: Denk aan oppervlakten. Wat is de formule voor de oppervlakte van een
rechthoek? Wat is hier de breedte en wat is hier de lengte? En waarom moet je het door
twee delen?
Opgave 4.V Hoeveel rijtjes kunnen we maken van lengte n met daarin alleen de getallen 1
tot en met 5? Dit kunnen we ook weer recursief oplossen. Noem het aantal rijtjes van lengte
n an . Een rijtje van lengte 1 kunnen we op vijf manieren maken, dus a1 = 5. Een rijtje van
lengte n + 1 kunnen we maken door eerst een rijtje van lengte n te maken en daar een element
achter te zetten. Dus an+1 := 5 · an . Herinner je nu even de definitie van machtsverheffen.
Bewijs met inductie dat voor alle n ≥ 1, an = 5n .
Oplossing: Voor alle duidelijkheid: het gaat hier om rijtjes waar de getallen 1 tot en met
5 best dubbel in mogen voorkomen. Dat kun je bijvoorbeeld al afleiden uit het feit dat er ook
een rijtje van lengte 6 gemaakt moet kunnen worden.
IH: Definieer P (n) als an = 5n .
Basisstap n = 1: a1 = 5 = 51 dus P (1) klopt.
Inductiestap: Neem aan dat P (n) geldt. We moeten nu bewijzen dat ook P (n + 1) geldt.
P (n)
an+1 = 5 · an = 5 · 5n = 5n+1
Dus inderdaad kunnen we P (n + 1) afleiden uit P (n).
Dus voor alle n ∈ N, n ≥ 1 geldt an = 5n .
Merk op dat we nu alleen maar naar rijtjes van lengte 1 of meer hebben gekeken. Als je
echter ook alle mogelijke rijtjes van lengte 0 meeneemt, blijkt het ook te kloppen. Het enige
dat verandert in dit bewijs is dat de basis bij n = 0 zit. Controleer zelf dat het voor n = 0
inderdaad ook geldt. (Of met andere woorden: bedenk hoeveel verschillende rijtjes van lengte
0 bestaan.)
Opgave 4.W Bewijs met inductie dat 1 + 3 + 5 + 7 + · · · + (2n − 1) = n2 . Wat is het verband
met het volgende plaatje?
◦ • ◦ • ◦
• • ◦ • ◦
◦ ◦ ◦ • ◦
• • • • ◦
◦ ◦ ◦ ◦ ◦
53
Oplossing: Definieer de rij sn recursief als volgt
s1 = 1
sn = sn−1 + 2n − 1 voor n ≥ 2
Dus sn = 1 + 3 + . . . + (2n − 1). We moeten met inductie bewijzen dat sn = n2 .
IH: Definieer P (n) als sn = n2 .
Basisstap n = 1: s1 = 1 = 12 , dus P (1) geldt.
Inductiestap: Uit P (n) gaan we P (n + 1) bewijzen.
P (n)
sn+1 = sn + 2(n + 1) − 1 = n2 + 2(n + 1) − 1 = n2 + 2n + 2 − 1 = n2 + 2n + 1 = (n + 1)2
En dus kunnen we P (n + 1) inderdaad bewijzen als P (n) geldt.
En dus weten we nu dat voor n ∈ N, n ≥ 1 1 + 3 + . . . + (2n − 1) = n2 . (Merk op dat het bij
deze opgave geen zin heeft om over n = 0 te praten.)
In het plaatje zou je weer de link met oppervlakten moeten kunnen zien.
Opgave 4.X Bewijs dat er in de 2e 4vP aan de rand allemaal eentjes staan.
Oplossing: De punten op de rand
ordinaten (n, 0) ofwel (n, n). Per
hebben ofwel nco¨
n
definitie van 2e 4vP staat er dus 0 respectievelijk n . En die zijn beide per definitie 1
voor elke n.
Opgave 4.Y Laat zien dat ook de 4e 4vP gelijk is aan de 1e 4vP.
Oplossing:
Voordat we dit formeel gaan bewijzen met inductie, eerst informeel het
achterliggende idee. In de 4e 4vP staat op co¨ordinaat (n, k) de co¨effici¨ent van xk in de
veelterm (1 + x)n . Wat we nu straks formeel willen bewijzen is dat de term in 4e 4vP op
positie (n+1, k) kan worden verkregen door de getallen op posities (n, k−1) en (n, k) bij elkaar
op te tellen, precies zoals in de 1e 4vP. Dat kunnen we doen door de veelterm (1 + x)n+1
te ontbinden tot (1 + x)(1 + x)n wat natuurlijk weer gelijk is aan (1 + x)n + x(1 + xn ). Hoe
kun je nu de co¨effici¨ent van xk bepalen in deze veelterm? Nou, die krijg je natuurlijk door de
co¨efficient van xk in de veelterm van (1 + x)n te nemen en die op te tellen bij de co¨effici¨ent
van xk in de veelterm x(1 + x)n . Maar die laatste is natuurlijk precies de co¨effici¨ent van xk−1
in de veelterm (1 + x)n . En daarmee hebben we precies de getallen gevonden die volgens de
4e 4vP op de posities (n, k) en (n, k − 1) staan.
Nu het formele bewijs. We laten zien dat alle co¨effici¨enten in de n-e rij van 1e 4vP gelijk
zijn aan die in de n-e rij van 4e 4vP. Door vervolgens inductie op n toe te passen, kunnen
we dus uiteindelijk voor elke rij bewijzen dat de entries hetzelfde zijn. Voordat we het bewijs
uitschrijven introduceren we eerst een afkorting voor de co¨effici¨ent van xk in een veelterm
f (x):
[f (x)]|k
Twee prettige eigenschappen van deze operatie zijn:
[f (x) + g(x)]|k = [f (x)]|k + [g(x)]|k
[x · f (x)]|k = [f (x)]|k−1 als k > 0
54
(1)
(2)
Beredeneer zelf dat (1) geldt. Hier bewijzen we (2) Neem aan dat deg(f (x)) = p.
[x · f (x)]|k
h i
= x [f (x)]|0 + [f (x)]|1 x + · · · + [f (x)]|k−1 xk−1 + · · · + [f (x)]|p xp
|k
h
i
2
k
p+1
= [f (x)]|0 x + [f (x)]|1 x + · · · + [f (x)]|k−1 x + · · · + [f (x)]|p x
|k
= [f (x)]|k−1
Defineer nu de bewering P (n) alsvolgt:
P (n) := ∀k ∈ {0, . . . , n}[4e 4vP(n,k) = 1e 4vP(n,k) ]
De stelling die we nu moeten bewijzen is: P (n) geldt voor alle n ∈ N. Zoals gezegd gaat het
bewijs met inductie naar n.
Basisstap n = 0: We moeten dus bewijzen dat voor alle k ∈ {0} geldt dat 4e 4vP(0,k) =
1e 4vP(0,k) , dus alleen maar voor k = 0. Bewijs:
4e 4vP(0,0) =
(1 + x)0
|0
= [1]|0
= x0 |0
= 1
= 1e 4vP(0,0)
Dus voor n = 0 geldt P (n).
Inductiestap: Uit P (n) gaan we P (n + 1) bewijzen. We moeten nu dus laten zien dat voor
alle k ∈ {0, . . . , n + 1} geldt dat
4e 4vP(n+1,k) = 1e 4vP(n+1,k)
We maken een gevalsonderscheiding voor k.
• k = 0. Bewijs:
(1 + x)n+1 |0
n+1
=
[1 + x]|0
4e 4vP(n+1,0) =
= 1n+1
= 1
= 1e 4vP(n+1,0)
En dus geldt (3) voor k = 0.
55
(3)
• 0 < k < n + 1. Bewijs:
4e 4vP(n+1,k) =
(1 + x)n+1
(4)
|k
n
= [(1 + x)(1 + x) ]|k
n
(5)
n
= [(1 + x) + x(1 + x) ]|k
n
n
= [(1 + x) ]|k + [x(1 + x) ]|k
n
n
(6)
(7)
= [(1 + x) ]|k + [(1 + x) ]|k−1
(8)
= 4e 4vP(n,k) + 4e 4vP(n,k−1)
(9)
= 1e 4vP(n,k) + 1e 4vP(n,k−1)
(10)
= 1e 4vP(n+1,k)
(11)
Merk op dat (4) niets anders is dan de definitie van 4e 4vP. Verder zijn (5) en (6)
het resultaat van een eenvoudige berekening. En (7) volgt uit (6) en eigenschap
(1). Verder volgt (8) uit (7) en eigenschap (2). En (9) is niets anders dan twee keer
de definitie van 4e 4vP toepassen. Pas in (10) passen we de inductiehypothese
toe, maar dan wel meteen twee keer. En tot slot is (11) een toepassing van de
definitie van 1e 4vP. Alles bij elkaar hebben we nu bewezen dat (3) geldt voor
0 < k < n + 1.
• k = n + 1. Bewijs:
(1 + x)n+1 |n+1
n+1
=
[1 + x]|1
4e 4vP(n+1,n+1) =
= 1n+1
= 1
= 1e 4vP(n+1,n+1)
En dus geldt (3) voor k = n + 1.
En dus geldt (3) voor alle k ∈ {0, . . . , n + 1}. Maar dan geldt dus dat P (n + 1) geldt.
Merk overigens op dat je voor de gevallen k = 0 en k = n + 1 helemaal geen inductie
gebruikt!
En dus is nu voor alle n ∈ N bewezen dat P (n) geldt.
Opgave 4.Z Laat zien hoe je in de driehoek van Pascal kunt vinden hoeveel manieren er
zijn om vier objecten uit een collectie van zes objecten te kiezen. Wat is de notatie voor de
bijbehorende binomiaalco¨effici¨ent?
Oplossing: Voor de n-e rij uit de driehoek van Pascal geldt dat het m-e getal aangeeft op
hoeveel manier je m − 1 objecten uit een collectie van n − 1 objecten kunt pakken. Bedenk
dat de eerste 1 telkens betekent dat je op precies ´e´en manier ‘niets’ kunt pakken uit een serie
objecten. Dat klinkt misschien gek, maar probeer het maar als volgt te begrijpen. Stel dat
je op twee manieren ‘niets’ kunt pakken. Dan moet je verschil kunnen aangeven tussen die
twee resultaten. Maar omdat je niets gepakt hebt is er geen verschil te zien. En dus was het
eigenlijk dezelfde manier.
56
Hier moet je dus het vijfde getal uit de zevende rij pakken:
1
1
1
1
1
1
1
1
3
4
5
6
7
1
3
6
10
15
21
1
2
1
4
10
20
35
1
5
15
35
1
6
21
1
7
1
De bijbehorende binomiaalco¨effici¨ent is 64 .
Let wel: de 0-e rij uit zo’n driehoek bestaat niet. Je kunt het wel hebben over een rij
met naam 0, maar de eerste rij die je tegenkomt is per definitie de eerste rij en niet de nulde
rij! Op dezelfde manier kun je niet spreken over het nulde element. Vandaar dat je hier het
vijfde element uit de zevende rij pakt, daar waar je misschien het vierde element uit de zesde
rij had verwacht.
57
5
Modale logica
Opgave 5.A De formule ♦R betekent dus hetzelfde als ¬¬R. Vind een formule zonder
het symbool ‘’ die hetzelfde betekent als R. Vertaal zowel R als de formule die je hebt
gevonden in een Nederlandse zin.
Oplossing: R ≡ ¬♦¬R. R betekent ‘Het is noodzakelijk dat het regent’. ¬♦¬R
betekent ‘Het is niet mogelijk dat het niet regent’.
Opgave 5.B Nu wordt ‘U is noodzakelijk’ symbolisch opgeschreven als U , en ‘U is onmogelijk’ als ¬U of ¬♦U . Geef twee verschillende formules van de modale logica die ‘U is
contingent’ uitdrukken.
Oplossing: ¬U ∧ ♦U en ♦U ∧ ♦¬U .
Opgave 5.C Gebruik het woordenboek:
G
K
ik heb geld
ik koop iets
en vertaal de volgende Nederlandse zinnen naar formules van de modale logica:
(i) Het is mogelijk dat ik iets koop zonder dat ik geld heb.
Oplossing: ♦(K ∧ ¬G). De oorspronkelijke zin lijkt onmogelijk (als we kopen op afbetaling buiten beschouwing laten). Een alternatieve vertaling is (♦K) ∧ ¬G. Die is ook
onmogelijk.
(ii) Het is noodzakelijk dat als ik iets koop dat ik dan ook geld heb.
Oplossing: (K → G). Dit lijkt een noodzakelijk ware zin.
(iii) Het is mogelijk dat als ik iets koop dat ik dan geen geld heb.
Oplossing: Hier is het erg afhankelijk van hoe je de zin interpreteert. Doe je dat
als ♦(K → ¬G), dan is het een noodzakelijk ware bewering. Immers K → ¬G is
bijvoorbeeld waar als je niets koopt, ongeacht of je geld hebt of niet. Dus ♦(K → ¬G)
is dan noodzakelijk waar. Als je echter de alternatieve interpretatie ♦(K ∧ ¬G) neemt,
dan hebben we hierboven al gezien dat die onmogelijk waar is.
Welke van deze zinnen lijken je waar? Leg uit waarom.
Opgave 5.D Geef bij de volgende formules van de modale logica de vorm die aan de offici¨ele
grammatica voldoet, en teken de bijbehorende bomen.
(i) (a)
Oplossing: a;
a
(ii) a → a
Oplossing: (a → a);
→
}
a
a
58
(iii) (a) → a
Oplossing: (a → a);
→
}
a
a
(iv) (a → a)
Oplossing: (a → a);
→
a
}
!
(v) ¬a → ¬a
Oplossing: (¬a → ¬a);
a
→
¬
}
"
¬
a
a
(vi) ♦a → ♦a
Oplossing: (♦a → ♦a);
→
♦
!
~
a
♦
a
(vii) a → ♦a
Oplossing: (a → ♦a);
→
}
♦
a
a
(viii) ♦a ∧ b → ♦a ∨ ¬c
Oplossing: ((♦a ∧ b) → (♦a ∨ ¬c));
→
∧
♦
a

w
(
b
♦
a
Opgave 5.E Gebruik het volgende woordenboek:
59

∨
¬
c
K
H
ik ben klaar
ik ga naar huis
Vertaal voor ieder van de logica’s uit de tabel (behalve voor de programma-logica) de formule
¬K → ¬♦H
naar het Nederlands.
Oplossing:
(i) Modaal: Als ik niet klaar ben dan is het niet mogelijk dat ik naar huis ga.
(ii) Epistemisch: Als ik niet klaar ben dan is het strijdig met mijn kennis dat ik naar huis
ga.
(iii) Doxastisch: Als ik niet klaar ben dan is het strijdig met mijn geloof dat ik naar huis ga.
(iv) Temporeel: Als ik niet klaar ben dan niet soms ga ik naar huis. Als ik niet klaar ben
dan ga ik nooit naar huis.
(v) Deontisch: Als ik niet klaar ben dan niet mag ik naar huis gaan. Als ik niet klaar ben
dan mag ik niet naar huis gaan.
Opgave 5.F Maak een tabel van modale logica’s en axiomaschema’s, waarin je aangeeft
in welke logica’s welke schema’s gelden. Zet de logica’s uit de lijst op pagina 65 langs de
linkerkant van de tabel en de axiomaschema’s aan de bovenkant. Zet nu een ‘+’ in de tabel
wanneer je denkt dat het schema in de logica geldt, en een ‘−’ wanneer je denkt dat dat niet
altijd zo hoeft te zijn. Zo maak je dus een tabel met 36 plussen en minnen.
Oplossing:
Modaal
Epistemisch
Doxastisch
Temporeel
Deontisch
Programma
distr.
K
+1
+7
+13
+19
+25
+31
refl.
T
+2
+8
-14
+20
-26
-32
sym.
B
+3
+9
+15
-21
-27
-33
trans.
4
+4
+10
+16
+22
-/+28
-34
Eucl.
5
+5
-/+11
-/+17
-23
-/+29
-35
ser.
D
+6
+12
-18
+24
-/+30
+36
Hieronder de uitleg waarom er een ‘+’ of een ‘-’ staat. In het bijzonder is hier discussie
over mogelijk, dus als je het ergens duidelijk niet mee eens bent, geef dan door wat er mis is
met onze redenering. In het bijzonder heeft het geen zin om deze redeneringen uit het hoofd
te leren! Op een toets of tentamen moet je zelf een argument kunnen geven waarom een
bepaalde eigenschap wel of niet geldt.
1. (Modaal) Als g noodzakelijk uit f volgt en f is noodzakelijk, dan is g zelf ook noodzakelijk.
2. Als f noodzakelijk is, dan is f waar.
3. Als f waar is, dan is de mogelijkheid dat f waar is noodzakelijk.
4. Als f noodzakelijk is, dan is f ook noodzakelijk op grond van logisch redeneren.
5. Als f mogelijk is, dan is ♦f ook noodzakelijk.
60
6. Elk reflexief systeem is ook serieel.
7. (Epistemisch) Als we weten dat uit f g volgt en we weten dat f waar is dan weten we
ook dat g geldt.
8. Alleen ware feiten f kunnen gekend worden.
9. Als f waar is, dan weet je dat het niet strijdig is met je kennis.
10. Je weet wat je weet.
11. Dit betekent zoiets als: je weet wat je niet weet. Als iets niet strijdig is met wat je weet,
dan weet je dat ook. Niet iedereen vindt dat dit redelijk is.
12. Elk reflexief systeem is ook serieel.
13. (Doxastisch) Als je gelooft dat f g impliceert en je gelooft f dan ligt het voor de hand
ook g te geloven.
14. Niet alles wat je gelooft is waar.
15. Als iets waar is, geloof je dan dat het niet strijdig is met je geloof?
16. Als je iets gelooft, geloof je (vast) ook wel dat je dat gelooft.
17. Als iets niet strijdig is met je geloof, is dat dan een reden om het dan zelf ook maar te
geloven?
18. Mensen kunnen best in strijdige dingen geloven.
19. (Temporeel) Als altijd geldt dat f g impliceert en verder geldt f altijd dan moet g ook
wel altijd gelden.
20. Als f altijd geldt, dan moet het in het bijzonder nu gelden. (Nb. hier gebruiken we de
LTL interpretatie uit sectie 5.6; er zijn ook andere temporele logica’s.)
21. Onder de LTL interpretatie dat nu een onderdeel van de toekomst is, volgt uit het feit
dat f nu waar is automatisch dat het altijd een keer waar is? Nee, neem maar een
eigenschap f die alleen vandaag waar is. Dan geldt voor vandaag ♦f wel. Maar voor
morgen geldt ♦f niet. En dus geldt ♦f niet. (In zekere zin betekent ♦f dat f
oneindig vaak waar is: op elk moment is er een later moment waarop f waar is.)
22. Als iets vanaf nu altijd waar is, dan is het ook altijd waar vanaf elk later moment dan
nu.
23. Als iets ooit waar is, hoeft dat niet te betekenen dat het altijd ooit waar is. Zie het
voorbeeld tegen symmetrie.
24. Als iets altijd waar is, dan is het zeker ooit waar.
25. (Deontisch) Als het zo is dat je g moet doen indien je f doet en je moet f doen, dan
moet je ook g doen.
26. Uit het feit dat je f moet doen volgt niet dat je f ook doet.
61
27. Als je f doet dan volgt daaruit niet dat dat moet mogen.
28. Als je f moet doen, moet je dan ook f moeten?
29. Als je f mag doen, moet dat dan ook mogen?
30. Het klinkt niet onredelijk om aan te nemen dat als je iets moet, je het ook mag. Aan de
andere kant, soms moet je naar de wc terwijl dat van de docent niet mag. Verder is dit
axioma equivalent aan f ∧ ¬f . En het komt best voor dat je tegenstrijdige dingen
moet. Een zogenaamde ‘double bind’. Neem bijvoorbeeld een gebodsbord met daarop
de tekst ‘negeer dit bord’.
31. (Programma) Als na executie geldt dat f g impliceert en na executie geldt f , dan moet
g ook na executie gelden.
32. Het feit dat f geldt na executies betekent niet dat f nu geldt.
33. Het feit dat f nu geldt betekent niet dat na executie het moet zijn dat na executie f
kan gelden.
34. Als f na executie geldt, betekent dat nog niet dat na een tweede executie f weer geldt.
35. Als f na executie kan gelden, betekent dat nog niet dat het na executie moet zijn dat
het na executie kan gelden.
36. Als f na executie moet gelden, dan kan het na executie zeker gelden.
Opgave 5.G Ga van de volgende formules f na in welke werelden x van ons voorbeeld van
een Kripke-model ze waar zijn, ofwel, voor welke x er geldt dat x f . Welke zijn in het hele
model waar, ofwel, voor welke geldt M1 |= f ?
(i) a
Oplossing: Als x ∈ {x1 , x2 , x4 } dan geldt a ∈ V (x) en dus x a. Omdat x 6∈ V (x3 )
geldt x3 6 a. En dus ook M1 6|= a.
(ii) a
Oplossing: R(x1 ) = {x2 } en x2 a, dus x1 a. R(x2 ) = {x1 , x2 }, x1 a en x2 a,
dus x2 a. R(x3 ) = {x1 } en x1 a, dus x3 a. R(x4 ) = ∅ en dus automatisch
x4 a, want er is geen enkele wereld waarvoor er iets gecontroleerd hoeft te worden.
En dus M1 |= a.
(iii) ♦a
Oplossing: R(x1 ) = {x2 } en x2 a, dus x1 ♦a. R(x2 ) = {x1 , x2 } en x1 a, dus
x2 ♦a. R(x3 ) = {x1 } en x1 a, dus x3 ♦a. R(x4 ) = ∅ en dus automatisch x4 6 ♦a,
want ♦a vereist dat er een toegankelijke wereld vanuit x4 is. En dus M1 6|= ♦a.
(iv) a → a
Oplossing: We hebben al gezien dat x1 a, x2 a en x4 a. En dus weten
we ook meteen met de waarheidstabel van → dat x1 a → a, x2 a → a en
x4 a → a. Verder weten we dat x3 a maar x3 6 a. En dus x3 6 a → a. En
dus M1 6|= a → a.
(v) a → a
Oplossing: R(x1 ) = {x2 } en x2 a, dus x1 a. En dus ook x1 a → a.
R(x2 ) = {x1 , x2 }, x1 a en x2 a, dus x2 a. En dus ook x2 a → a.
62
R(x3 ) = {x1 } en x1 a, dus x3 a. En dus ook x3 a → a. R(x4 ) = ∅ en
dus automatisch x4 a. En dus ook x4 a → a. En dus M1 |= a → a.
(vi) a → ♦a
Oplossing: R(x1 ) = {x2 }. We hebben al gezien dat x2 ♦a. Dus x1 ♦a. En
dus ook x1 a → ♦a. R(x2 ) = {x1 , x2 }. We weten al dat x1 ♦a en x2 ♦a.
Dus x2 ♦a. En dus ook x2 a → ♦a. Omdat x3 6 a weten we meteen dat
x3 a → ♦a. R(x4 ) = ∅. En dus meteen x4 ♦a. En dus ook x4 a → ♦a. En
dus M1 |= a → ♦a.
Opgave 5.H (i) Bestaat er een Kripke-model M2 zodat M2 |= a maar M2 6|= a? Als
je antwoord ‘ja’ is: geef een voorbeeld van zo’n model M2 . Als je antwoord ‘nee’ is:
waarom niet?
Oplossing: Nee, zo’n model M2 bestaat niet. Stel dat er wel een model M2 = hW, R, V i
bestaat met M2 |= a en M2 6|= a. Dan bestaat er dus een x ∈ W met x a en
x 6 a. Er zijn dan twee mogelijkheden voor R(x): leeg of niet-leeg. Als R(x) = ∅
geldt automatisch x a en dus hebben we een tegenspraak. Dus R(x) 6= ∅. Maar
voor alle y ∈ R(x) geldt dat y a want R(x) ⊆ W en M2 |= a betekent dat y a voor
alle y ∈ W geldt. Maar dan geldt x a en we hebben weer een tegenspraak. Dus kan
zo’n model niet bestaan.
(ii) Bestaat er een Kripke-model M3 zodat M3 |= a maar M3 6|= ♦a? Als je antwoord ‘ja’
is: geef een voorbeeld van zo’n model M3 . Als je antwoord ‘nee’ is: waarom niet?
Oplossing: Ja. Neem M3 = hW, R, V i met W = {x1 }, R(x1 ) = ∅ en V (x1 ) = {a}. In
een diagram ziet dat er zo uit:
x1
M3 :
a
Omdat x1 a geldt M3 |= a. Maar omdat R(x1 ) = ∅ geldt x1 6 ♦a en dus ook
M3 6|= ♦a.
Opgave 5.I (i) Bestaat er een Kripke-model M4 dat serieel is maar niet reflexief? Als
je antwoord ‘ja’ is: geef een voorbeeld van zo’n model M4 . Als je antwoord ‘nee’ is:
waarom niet?
Oplossing: Laat je bij deze opgave niet foppen: een model is serieel als het voor alle f
aan axioma D voldoet en reflexief als het voor alle f aan axioma T voldoet. Een model
geven dat voor bijvoorbeeld f = a voldoet aan die axioma’s wil dus nog niet zeggen
dat het model inderdaad serieel of reflexief is! In het algemeen is het zelfs vrij lastig te
bewijzen dat een model serieel of reflexief is. Echter, de karakterisering die in sectie 5.5
wordt gegeven is veel handiger:
• Een model is serieel als er uit elke wereld minstens ´e´en pijl vertrekt.
• Een model is reflexief als er vanuit iedere wereld een pijl naar zichzelf is.
Nu terug naar deze opgave. Het antwoord is ja; zo’n model bestaat. Neem M4 =
hW, R, V i met W = {x1 , x2 }, R(x1 ) = {x1 }, R(x2 ) = {x1 }, V (x1 ) = {a} en V (x2 ) = ∅.
In een diagram ziet dat er zo uit:
M4 :
x1
N
63
ao
x2
Omdat R(x1 ) = R(x2 ) = {x1 } gaat er dus vanuit elke wereld minimaal ´e´en pijl en is
M4 dus serieel. Het model is echter niet reflexief: vanuit x2 is er geen pijl naar x2 zelf.
Omdat we hier laten zien dat het model niet reflexief is, kunnen we ook ´e´en specifieke
formule f pakken en laten zien dat M4 6|= f → f . We nemen hiervoor f = a. Omdat
R(x2 ) = {x1 } en a ∈ V (x1 ) geldt x2 a. Echter, omdat a 6∈ V (x2 ) geldt x2 a niet.
En dus geldt x2 6 a → a. En dus geldt M4 6|= a → a. Dus M4 is niet reflexief.
(ii) Bestaat er een Kripke-model M5 dat reflexief is maar niet serieel? Als je antwoord ‘ja’
is: geef een voorbeeld van zo’n model M5 . Als je antwoord ‘nee’ is: waarom niet?
Oplossing: Nee, zo’n model M5 bestaat niet. M5 is reflexief betekent dat x ∈ R(x)
voor alle x ∈ W . Dus is er in elk geval een pijl vanuit x naar zichzelf. In het bijzonder
is er dus minimaal ´e´en pijl vanuit x en dus is M5 serieel. Dus M5 kan niet wel reflexief
en toch niet serieel zijn.
64

Proeftentamen Functies en Reeksen

L, EI F A B k - WSG Isaac Newton

Oefentoets V4

Werkcollege QCB II

Opgaves week 51-2014 - Universiteit Utrecht

Hs7 Veranderingen - uitwerkingensite.nl

bijlage - Daventria

opgaven - Protagoras

het overlijdensbericht (in PDF-formaat)

Gedeeltelijke uitwerkingen tentamen algebra 1

DATA Opmaak/homilie St. Hilarius Za. 17 uur Wijnberg Za. 18.30 uur