Logika voor AI Werkboek

Logika voor AI Werkboek drs. Rosalie Iemhoff

drs. Marco Vervoort dr. Dick de Jongh

Universiteit van Amsterdam Faculteit der Wiskunde en Informatica, Natuurkunde en Sterrenkunde Plantage Muidergracht 24 1018 TV Amsterdam 2 september 2002

Inhoudsopgave 1 Introductie Propositielogika

3

2 Waarheidstafels

7

3 Inductie

11

4 Semantische Tableaus I

19

5 Resolutie I

21

6 Vertaalopgaven

23

7 Predikaatlogika en Modellen

27

8 Tarski’s World

33

9 Semantische Tableaus II

41

10 Prenexvorm

43

11 Resolutie II

45

A Oefententamens

51

B Uitwerking Oefententamen

63

Werkboek Logika voor AI

3

Hoofdstuk 1

Introductie Propositielogika 1.1. Vertaal de volgende zinnen in de taal van de propositielogika. Gebruik daarbij de volgende vertaalsleutel: b := Marie is braaf f := Marie vraagt een fiets voor haar verjaardag j := Jan gaat naar de bioscoop m := Marie krijgt een fiets voor haar verjaardag p := Marie haat Jan q := Marie verafschuwt Jan r := het regent s := Jan gaat naar het strand v := Jan heeft vakantie z := de zon schijnt (a) Het is niet zo dat Marie Jan haat of verafschuwt. (b) Als Jan vakantie heeft dan gaat hij als de zon schijnt naar het strand en als het regent naar de bioscoop. (c) Marie vraagt een fiets voor haar verjaardag, maar ze krijgt er hooguit een als ze braaf is. 1.2. Vertaal de volgende zinnen in de taal van de propositielogika. Gebruik daarbij de volgende vertaalsleutel: p := je hebt zin om je bed op te maken, q := je moet je bed opmaken, r := Peter heeft de tafel gedekt, s := Peter heeft de afwas gedaan, t := je moet afwassen, u := je moet afdrogen. (a) Als je geen zin hebt om je bed op te maken, hoef je het niet te doen. (b) Peter heeft niet alleen de tafel gedekt, maar ook de afwas gedaan.

4

Introductie Propositielogika

(c) Het is niet zo dat als Peter de tafel heeft gedekt, hij niet hoeft af te wassen of af te drogen. 1.3. Vertaal de volgende zinnen in de taal van de propositielogika. Geef zoveel mogelijk de logische structuur weer en vermeld de vertaalsleutel. (a) Als Clinton de verkiezingen niet wint, dan wint Dole ze. (b) Perot wint de verkiezingen niet, en Dole evenmin. (c) Gore wordt vice–president als Clinton president wordt, maar anders niet. (d) Als Clinton of Gore het te veel over het milieu of te weinig over de economie blijft hebben, dan wint Dole. 1.4. Vertaal de volgende zinnen in de taal van de propositielogika. Geef zoveel mogelijk de logische structuur weer en vermeld de vertaalsleutel. (a) De doorsnee PvdA-kiezer kan zich niet herkennen in het regeringsbeleid, maar Kok kan niets anders. (b) Zouden er nu verkiezingen worden gehouden, dan zou de PvdA ernstige verliezen lijden, en D’66 zou de PvdA zelfs in zetelaantal voorbijstreven. (c) D’66 zal veel zetels winnen als de partij geleid wordt door van Mierlo, maar niet als Wolfensperger de leider is. (d) Als het kabinet nu niet valt, dan valt het volgend jaar alsnog op de WAO, of als de inflatie hoger is dan 4%, op de koppeling. 1.5. Vertaal de volgende zinnen in de taal van de propositielogika. Geef zoveel mogelijk de logische structuur weer en vermeld de vertaalsleutel. (a) Jan heeft een auto gekocht, maar zijn vrouw noch hijzelf heeft een rijbewijs. (b) Piet ontsteekt de lichten wel als het donker is, maar niet als het regent. (c) Kees ontsteekt de lichten niet alleen als het donker is, maar ook als het regent of mist. 1.6. Vertaal de volgende zinnen in de taal van de propositielogika. Geef zoveel mogelijk de logische structuur weer, en vermeld de vertaalsleutel. Welke paren formules zijn logisch equivalent? (a) Als paarden vliegen kunnen, dan kunnen honden fluiten. (b) Als paarden kunnen fluiten, dan kunnen honden vliegen. (c) Als paarden niet kunnen fluiten, dan kunnen honden niet vliegen. (d) Als honden niet kunnen fluiten, dan kunnen paarden niet vliegen.


5

(e) Het is niet waar dat paarden kunnen vliegen en ook niet dat honden kunnen fluiten. (f) Als vogels kunnen vliegen, dan kunnen mensen fluiten. (g) Als mensen niet kunnen fluiten, dan kunnen vogels niet vliegen. (h) Als paarden niet kunnen fluiten of honden niet kunnen vliegen, dan kunnen paarden vliegen en honden fluiten. 1.7. De volgende puzzels komen allemaal uit het boek De prinses of de tijger van Raymond Smullyan (AMBOBOEKEN/BAARN). De situatie is als volgt. Een gevangene kan kiezen uit twee deuren, waarachter, òf een prinses, òf een tijger zit (het is in principe mogelijk dat er achter beide een prinses of achter beide een tijger zit). Op beide deuren zitten bordjes met gegevens die waar of onwaar kunnen zijn. Verder wordt je iets verteld over de waarheid/onwaarheid van die gegevens. De opdracht is: vind door correct redeneren een deur waarvan je zeker weet dat er een prinses achter zit. Je moet niet alleen opschrijven welke deur, maar ook hoe je zeker weet dat er een prinses achter de deur zit. De eerste puzzel is hier verdeelt in deelvragen, om je een indruk te geven van de manier van redeneren die je wordt gevraagd te gebruiken. (a) Deur 1: In deze kamer zit een prinses en in de andere kamer een tijger. Deur 2: In een van de kamers zit een prinses, in de andere een tijger. Eén van de twee gegevens is waar, het andere niet. i. Stel dat het gegeven op deur 1 waar is, en dat op deur 2 onwaar (dit is één van de twee mogelijke situaties). Is deze situaties mogelijk? Zo ja, wie zit er dan achter de eerste deur? En wie achter de tweede? ii. Stel dat het gegeven op deur 1 onwaar is, en dat op deur 2 waar (dit is de andere van de twee mogelijke situaties). Is deze situatie mogelijk? Zo ja, wie zit er in dit geval achter de eerste deur? En wie achter de tweede? iii. Achter welke deur zit een prinses? (b) Deur 1: In minstens een van de twee kamers zit een prinses. Deur 2: In de andere kamer zit een tijger. De gegevens zijn beide waar of beide onwaar. (c) Deur 1: Een of twee van de volgende uitspraken zijn waar: Er zit een tijger in deze kamer. Er zit een prinses in de andere kamer. Deur 2: In de ander kamer zit een prinses. De gegevens zijn beide waar of beide onwaar.

6

Introductie Propositielogika

(d) Deur 1: In beide kamers zit een prinses. Deur 2: In beide kamers zit een prinses. Als er een prinses in kamer 1 zit, dan is het gegeven op deur 1 waar, als er een tijger in zit, dan niet. Als er een tijger in kamer 2 zit, dan is het gegeven op deur 2 waar, als er een prinses in zit, dan niet. (e) Deur 1: In minstens een kamer zit een prinses. Deur 2: In de andere kamer zit een prinses. Gegevens als bij (d). (f) Deur 1: Het maakt geen verschil welke kamer u kiest. Deur 2: In de andere kamer zit een prinses. Gegevens als bij (d). (g) Deur 1: Het maakt wel verschil welke kamer u kiest. Deur 2: U kunt beter de andere kamer kiezen. Gegevens als bij (d). (h) Op een van beide deuren: In deze kamer zit een tijger. Op de ander deur: In beide kamers zit een tijger. De bordjes zijn hier van de deuren gevallen. Desondanks is het probleem op te lossen. Verdere gegevens als bij (d).


7

Hoofdstuk 2

Waarheidstafels 2.1. Maak waarheidstafels voor de volgende formules. Geef bij (b)-(d) de bijbehorende verzameling modellen en de disjunctieve en conjunctieve normaalvorm. (a) ¬(p ↔ (q ∨ r)); (b) p ↔ (q ↔ r); (c) (¬p ∨ q ∨ ¬r) ∧ (p ∨ ¬q); (d) q ∧ ¬q. 2.2. Geef met behulp van waarheidstafels voor de volgende formules de disjunctieve en de conjunctieve normaalvorm. (a) ((p ∧ q) ∨ r) ↔ ((q → ¬p) → ¬r). (b) (p → ¬r) ∧ ((p ∨ q) → r). 2.3. Test met gebruikmaking van waarheidstafels welke van de volgende formules tautologiën zijn: (a) p → (q ∨ p); (b) (p → q) → (p → ¬r); (c) ¬(p ∨ q) ↔ (¬p ∧ ¬q). 2.4. Test met gebruikmaking van waarheidstafels welke van de volgende tweetallen formules logisch equivalent zijn: (a) p ↔ (q ↔ r) en (p ↔ q) ↔ r; (b) p ∧ (q ∨ r) en (p ∧ q) ∨ (p ∧ r); (c) ¬¬(p ∧ q) en p ∧ q ∧ r; (d) p → q en ¬p ∨ q.

8

Waarheidstafels

2.5. Welke van de volgende verzamelingen formules zijn vervulbaar? Als een verzameling vervulbaar is, geef een model. (a) Sa = {p1 → ¬p2 , p2 ∨ p1 }. (b) Sb = {(p1 ∧ p2 ) ∨ p3 , ¬p2 → ¬(p1 ∧ p3 )}. (c) Sc = {p1 ∨ p2 , ¬p2 ∨ ¬p3 , p3 ∨ p4 }. (d) Sd = {p1 ∨ p2 , ¬p2 ∨ ¬p3 , p3 ∨ p4 , ¬p4 ∨ ¬p5 , . . .}. 2.6. Beschouw de volgende twee formules: F G

= ¬(p → ((q ∧ r) ∨ (¬q ∧ ¬r))) = ((p → q) ∨ r) ∧ (r → ¬q)

(a) Laat met behulp van waarheidstafels zien dat alle modellen van F modellen van G zijn. (b) Zijn alle modellen van G modellen van F? Zo ja, toon dat aan. Zo nee, geef een model van G dat géén model van F is. (c) Is F → G een tautologie? Is G → F een tautologie? (d) Geef een conjunctieve en een disjunctieve normaalvorm van G. 2.7. Los opgave (1.7) op met behulp van waarheidstafels. 2.8. Voor elke formule φ waarin slechts p en q als propositieletters voorkomen, kunnen we een waarheidstabel maken door de juiste waarden in te vullen in de laatste kolom van de volgende tabel: p 0 0 1 1

q 0 1 0 1

φ ... ... ... ...

Omgekeerd, als we de laatste kolom vullen met de waarden ‘0’ en ‘1’, dan krijgen we een waarheidstabel van een dergelijke formule φ. (a) Op hoeveel verschillende manieren kunnen we de laatste kolom van de tabel vullen met de waarden ‘0’ en ‘1’ ? (b) Vind voor elke waarheidstabel die je op deze manier kan krijgen een corresponderende formule. (c) Beredeneer dat elke formule φ waarin slechts p en q als propositieletters voorkomen, logisch equivalent is met één van de formules die je hebt gevonden in (b). (d) Hoeveel logisch niet-equivalente formules zijn er waarin slechts p en q als propositieletters voorkomen?


9

2.9. Zij φ en ψ twee formules, waarin slechts p en q als propositieletters voorkomen. We kunnen een waarheidstafel maken van φ, ψ, φ → ψ, en φ → ¬ψ, met p en q als propositieletters. (a) Vul in: φ → ψ is een tautologie, dan en slechts dan als overal waar in de waarheidstafel bij . . .∗ een . . .o staat, bij . . .∗ een . . .o staat. φ → ¬ψ is een tautologie, dan en slechts dan als overal waar in de waarheidstafel bij . . .∗ een . . .o staat, bij . . .∗ een . . .o staat. ∗

vul in: φ of ψ

o

vul in: ‘0’ of ‘1’

(b) Laat zien dat, als in de waarheidstafel van φ vier keer ‘0’ en nul keer ‘1’ voorkomt, dat dan voor elke formule ψ (waarin slechts p en q als propositieletters voorkomen) φ → ψ én φ → ¬ψ tautologiën zijn. (c) Laat zien dat, als in de waarheidstafel van φ drie keer ‘0’ en één keer ‘1’ voorkomt, dat dan voor elke formule ψ (waarin slechts p en q als propositieletters voorkomen) φ → ψ óf φ → ¬ψ een tautologie is. (d) Laat zien dat, als in de waarheidstafel van φ twee of meer keer ‘1’ voorkomt, dat er dan een formule ψ bestaat (waarin slechts p en q als propositieletters voorkomen) zó dat noch φ → ψ, noch φ → ¬ψ een tautologie is. (e) Bewijs: voor elke formule ψ (waarin slechts p en q als propositieletters voorkomen) geldt dat φ → ψ of φ → ¬ψ (of allebei) een tautologie is, dan en slechts dan als φ is equivalent met één van de formules p ∧ ¬p, p ∧ q, p ∧ ¬q, ¬p ∧ q of ¬p ∧ ¬q. 2.10. Beantwoord de volgende vragen: (a) Hoeveel verschillende deelverzamelingen heeft een verzameling van n elementen? (b) Hoeveel verschillende modellen zijn er voor een gegeven domein van n propositieletters? (c) Wat is de lengte van een waarheidstafel met n propositieletters? (d) Hoeveel verschillende waarheidstafels zijn er met n propositieletters? (e) Hoeveel logisch niet-equivalente formules zijn definieerbaar met het alfabet {p1 , . . . , pn }, ¬, ∧ en ∨?


11

Hoofdstuk 3

Inductie 3.1. Zij gegeven de volgende beweringen: (i) Gilgamesh heeft rood haar. (ii) Kinderen van mensen met rood haar hebben zelf rood haar. Beargumenteer dat hieruit volgt dat alle nazaten van Gilgamesh rood haar hebben. 3.2. Stel dat we van een bepaalde eigenschap E van getallen het volgende weten: (i) Het getal 0 heeft eigenschap E. (ii) Als een getal n eigenschap E heeft, dan ook n + 1. (a) Laat zien dat het getal 1 eigenschap E heeft. (b) Laat zien dat de getallen 2, 3 en 4 eigenschap E hebben. (c) Beargumenteer in je eigen woorden dat alle natuurlijke getallen eigenschap E hebben. (d) Kan je uit (i) en (ii) een conclusie trekken over niet-natuurlijke getallen, zoals bijvoorbeeld 2 21 ? Beargumenteer je antwoord. 3.3. (a) Laat zien dat, om aan te tonen dat alle natuurlijke getallen een eigenschap E hebben, het niet voldoende is om aan te tonen dat: (i) Het getal 0 heeft eigenschap E. (ii’) Als 0 eigenschap E heeft, dan ook 0 + 1. (hint: geef een voorbeeld van een eigenschap E, die niet voor alle natuurlijke getallen geldt, zó dat (i) en (ii’) waar zijn). (b) Laat zien dat, om aan te tonen dat alle natuurlijke getallen een eigenschap E hebben, het niet voldoende is om aan te tonen dat: (ii”) Als een getal n eigenschap E heeft, dan ook n + 1. (hint als boven).

12

Inductie

3.4. In de volgende opgave schrijven we G(n) voor de bewering 1 + 2 + 3 + 4 + . . . + n = n(n + 1)/2 (a) Laat zien dat de bewering G(0) waar is. (b) Laat zien dat voor een willekeurig getal n geldt, dat als de bewering G(n) waar is, dan de bewering G(n + 1) ook waar is. (c) Beargumenteer dat hieruit volgt dat de bewering G(n) waar is voor alle natuurlijke getallen n. Hint: zie opgave (3.2). 3.5. Bewijs met inductie dat voor alle natuurlijke getallen n geldt: 20 + 21 + 22 + . . . + 2n = 2n+1 − 1 3.6. De Fibonacci-functie Fib(n) wordt gedefinieerd door de volgende inductieve definitie: (i) Fib(0) := 1 (ii) Fib(1) := 1 (iii) Fib(n + 2) := Fib(n) + Fib(n + 1) voor alle n ≥ 0. (a) Bereken de waarde van Fib(n) voor n=2, 3, 4, 5, 6. (b) Beargumenteer dat Fib(n) is gedefinieerd voor alle natuurlijke getallen n. (c) Kan je iets zeggen over de waarde van Fib(2 12 )? 3.7. Geef een inductieve definitie van de functie E(n) gedefinieerd door E(0) := 1, E(n) := 2n = 2 × 2 × . . . × 2 (n keer) (met behulp van de operaties +, −, × en/of /, en zónder gebruik te maken van machtsverheffen, puntjes (. . .), of de kreet ‘n keer’). 3.8. Geef een inductieve definitie van de functie n! gedefinieerd door 0! := 1, n! := 1 × 2 × . . . × n µ ¶ n groeperen in de driehoek van Pas3.9. Als we de binominaalcoëfficiënten i cal: µ ¶ 0 1 µ ¶0µ ¶ 1 1 1 1 0 µ ¶ µ ¶1µ ¶ 2 2 2 = 1 2 1 1 0 µ ¶ µ ¶ µ ¶2µ ¶ 3 3 3 3 1 3 3 1 0 1 2 µ ¶ µ ¶ µ ¶ µ ¶3µ ¶ 4 4 4 4 4 1 4 6 4 1 0 1 2 3 4 ... ...


13

dan zien we dat elk getal de som is µ van¶de twee getallen erboven. Het is n bekend dat de binominaalcoëfficiënt inderdaad inductief gedefiniëerd i kan worden, als volgt: µ ¶ 0 := 1 (i) 0 µ ¶ µ ¶ µ ¶ n n−1 n−1 (ii) := + voor 0 ≤ i ≤ n, n ≥ 1 i i−1 i µ ¶ n := 0 voor i < 0 en voor i > n (iii) i (a) Geef de volgende twee rijen van de driehoek van Pascal. µ ¶ 8 met behulp van de driehoek van Pascal. (b) Bereken 3 (c) Bewijs met inductie dat voor alle n ≥ 0 geldt: µ ¶ µ ¶ µ ¶ µ ¶ n n n n + + = 2n + ... + 0 1 n 2 (d) Bewijs dat de inductieve definitie overeenkomt met de gebruikelijke, i.e. bewijs met inductie dat voor alle i, n met 0 ≤ i ≤ n geldt: µ ¶ n! n = i i!(n − i)! 3.10. Stel dat we van een bepaalde eigenschap E van formules weten dat de volgende beweringen waar zijn: (i) Alle propositieletters p hebben eigenschap E. (ii) Als een formule φ eigenschap E heeft, dan ook ¬φ. (iii) Als twee formules φ en ψ allebei eigenschap E hebben, dan ook de formules (φ ∧ ψ), (φ ∨ ψ), (φ → ψ) en (φ ↔ ψ) (collectief genoteerd als (φ ◦ ψ)). (a) Laat zien dat de formule ¬p eigenschap E heeft. (b) Laat zien de formules (p ∧ q), (¬p → (p ∧ q)) en ¬(¬p → (p ∧ q)) eigenschap E hebben. (c) Beargumenteer in je eigen woorden dat alle formules die volgens de strikte definitie goed gevormd zijn eigenschap E hebben. (d) Kan je uit de gegeven beweringen een conclusie trekken over formules die volgens de strikte definitie niet goed gevormd zijn, zoals bijvoorbeeld (p ∧ q ∧ r)? Beargumenteer je antwoord.

14

Inductie

3.11. Toon aan dat, om te laten zien alle strikt welgevormde formules een eigenschap E hebben, het niet voldoende is om te laten zien dat: (i) Alle propositieletters p hebben eigenschap E. (ii’) Als een propositieletter p eigenschap E heeft, dan ook ¬p. (iii’) Als twee propositieletters p en q allebei eigenschap E hebben, dan ook de formules (p ∧ q), (p ∨ q), (p → q) en (p ↔ q) (collectief genoteerd als (p ◦ q)). (hint: geef een voorbeeld van een eigenschap E, die niet voor alle strikt welgevormde formules geldt, zó dat (i), (ii’) en (iii’) waar zijn). 3.12. Welke van de volgende rijtjes symbolen zijn volgens de strikte definitie een formule en welke niet? Zo niet, waarom niet? (a) ¬¬¬¬p (b) p ∧ q (c) (((p ∨ q) ∨ q) ∨ q) (d) ¬(p) (e) (¬p) (f) ¬(¬p) (g) (¬p ∧ q) (h) ¬(p ∧ q) (i) ¬p(∧q) (j) (p ∨ q ∨ r) (k) (p ∨ (q ∨ r) ∨ s) (l) ((p ∨ (q ∨ r)) ∨ s) 3.13. In de volgende opgave schrijven we T (φ) voor het aantal voorkomens van tweeplaatsige connectieven in een formule φ, en P (φ) voor het aantal voorkomens van propositieletters in een formule φ. (a) Laat zien dat T (φ) = P (φ) − 1 als φ een propositieletter is. (b) Laat zien dat voor een willekeurige formule φ geldt, dat als T (φ) = P (φ) − 1, dat dan T (¬φ) = P (¬φ) − 1. (c) Laat zien dat voor willekeurige formules φ en ψ geldt, dat als T (φ) = P (φ) − 1 en T (ψ) = P (ψ) − 1, dat dan T ((φ ◦ ψ)) = P ((φ ◦ ψ)) − 1 (waarbij ◦ staat voor één van de connectieven ∧, ∨, → of ↔). (d) Beargumenteer dat hieruit volgt dat T (φ) = P (φ)−1 voor alle (strikt welgevormde) formules φ. Hint: zie opgave (3.10). 3.14. Bewijs met behulp van inductie dat het aantal linkerhaakjes in een (strikt welgevormde) formule gelijk is aan het aantal voorkomens van tweeplaatsige connectieven.


15

3.15. Bewijs met behulp van inductie dat (strikt welgevormde) formules van de propositielogika niet met ’)’ beginnen, niet met ’(’ eindigen, en geen haakjesconfiguraties van de vorm ‘()’ of ‘)(’ bevatten. 3.16. Beschouw de functie α(φ), die aan iedere formule een natuurlijk getal toekent, en die wordt gedefinieerd door de volgende inductieve definitie: (i) α(φ) := 0, als φ een propositieletter is (ii) α(¬φ) := α(φ) (iii) α((φ ◦ ψ)) := α(φ) + α(ψ) + 1, voor ieder tweeplaatsig connectief ◦. (a) Reken de waardes van α(φ) uit voor de volgende formules: p, ¬p, ¬¬p, (p ∧ q), (p ∧ (q ∧ r)), (¬p ∧ q), ¬(p ∧ q) (b) Met welk begrip komt de functie α overeen? Hint: kies uw antwoord uit de volgende alternatieven: (0) het aantal haakjes in een formule; (1) het aantal symbolen in een formule; (2) het aantal voorkomens van negatie in een formule; (3) het aantal voorkomens van binaire connectieven in een formule; (4) het aantal linkerhaakjes in een formule; (5) het aantal verschillende propositieletters in een formule; (6) het aantal voorkomens van propositieletters in een formule; (7) het aantal niet-haakje symbolen in een formule; (8) het aantal voorkomens van connectieven in een formule; (c) Idem voor de functie β(φ) gedefinieerd door (i) β(φ) := 1, als φ een propositieletter is (ii) β(¬φ) := β(φ) (iii) β((φ ◦ ψ)) := β(φ) + β(ψ), voor ieder tweeplaatsig connectief ◦. 3.17. Geef een inductieve definitie van 0, 1, 2, 7 en 8 in de voorgaande opgave. 3.18. Geef een inductieve definitie van de functie P l(φ) gedefinieerd door P l(φ) := “de verzameling propositieletters die voorkomen in φ” Bijvoorbeeld: P l(((p ∧ q) → p)) = {p, q}.

16

Inductie

3.19. (a) Geef een inductieve definitie van de functie α(φ) gedefinieerd door α(φ) := “het aantal voorkomens van de connectieven ∧ en ∨ in φ” (b) Beschouw de verzameling formules waarin slechts de connectieven ∧, ∨ en ¬ voorkomen. Een voorkomen van een propositieletter p in zo’n formule φ heet positief als het in het bereik ligt van een even aantal negaties, en negatief als het in het bereik ligt van een oneven aantal negaties. Geef een inductieve definitie van de functies Pp (φ) en Pn (φ) gedefinieerd door Pp (φ) := “de verzameling propositieletters die positief voorkomen in φ” Pn (φ) := “de verzameling propositieletters die negatief voorkomen in φ” Bijvoorbeeld: Pp ((p ∨ ¬(p ∨ ¬q))) = {p, q}, Pn ((p ∨ ¬(p ∨ ¬q))) = {p}. (hint: dit kan je het beste doen met behulp van simultane inductieve definities, waarbij je voor de definitie van bijvoorbeeld Pp (¬φ) niet alleen gebruik mag maken van Pp (φ), maar ook van Pn (φ)). 3.20. (a) Vul in onderstaande tabel in elk hokje een formule in die logisch equivalent is met ((formule van de kolom)↔(formule van de rij)). Kies hiervoor telkens één van de formules p, q, (p ↔ p) en (p ↔ q). ↔ p q (p ↔ p) (p ↔ q)

p

q

(p ↔ p)

(p ↔ q)

(b) Bewijs nu met inductie dat voor alle zinnen φ die slechts de propositieletters p en q en het connectief ↔ bevatten, geldt: φ is equivalent met één van de formules p, q, (p ↔ p) of (p ↔ q). 3.21. (a) Vind voor elk van de volgende formules een daarmee logisch equivalente formule, die alleen de symbolen ‘φ’, ‘ψ’, ‘→’, ‘¬’, ‘(’ en ‘)’ bevat: i. (φ ∧ ψ) ii. (φ ∨ ψ) iii. (φ ↔ ψ) (b) Bewijs dat er voor elke formule φ een daarmee logisch equivalente formule t(φ) bestaat, die alleen propositieletters en de symbolen ‘→’, ‘¬’, ‘(’ en ‘)’ bevat. Hint: geef eerst een inductieve definitie van t(φ), o.a. gebruikmakend


17

van de herschrijvingen die je gevonden hebt in (a) (hier definieer je dus een functie die voor elke formule een nieuwe formule geeft). Bewijs daarna met inductie dat voor alle formules φ, φ logisch equivalent is met t(φ), en dat t(φ) alleen maar propositieletters en de symbolen ‘→’, ‘¬’, ‘(’ en ‘)’ bevat. (c) Is {→, ¬} functioneel volledig? 3.22. Laat het connectief ! gegeven zijn door Φ!Ψ := ¬(Φ ∧ Ψ). Maak een waarheidstafel voor ! en laat zien dat de verzameling connectieven {!} functioneel volledig is. 3.23. Zij W(φ) de waarheidswaarde van een formule φ in het model waarin alle propositieletters (die in φ voorkomen) waar zijn, i.e. W(φ) = 1 als φ waar is in dat model, en W(φ) = 0 als φ onwaar is in dat model. (a) Vul de juiste waarden (0 of 1) in om deze bewering waar te maken: ½ 1 als W(φ) = . . . en W(ψ) = . . . W(φ ∧ ψ) = 0 als W(φ) = . . . of W(ψ) = . . . (b) Geef een inductieve definitie van W(φ). Je mag hierbij constructies gebruiken als in (a). (c) Bewijs met formule-inductie dat voor alle formules φ die alleen connectieven uit {∧, ∨, →, ↔} bevatten, geldt dat W(φ) = 1. (d) Als een formule φ logisch equivalent is met ¬p, wat kun je dan zeggen over W(φ)? (e) Laat zien, met behulp van (d) en de bewering uit (c), dat de verzameling connectieven {∧, ∨, →, ↔} niet functioneel volledig is. 3.24. Laat het connectief ∗ gegeven zijn door de waarheidstafel p 0 0 1 1

q 0 1 0 1

p∗q 0 0 1 1

i.e. φ ∗ ψ is logisch equivalent met φ voor alle formules φ en ψ. (a) Zij P (φ) de functie gedefinieerd door P (φ)=”de eerste propositieletter die voorkomt in φ, lezend van links naar rechts”, waarbij naast de gewone connectieven ook het connectief ∗ mag voorkomen in φ. Geef een inductieve definitie van P (φ). (b) Bewijs met inductie dat voor alle formules φ die alleen de connectieven ∗ en ¬ bevatten, φ logisch equivalent is met P (φ) of met ¬P (φ). (c) Laat zien dat de verzameling connectieven {∗, ¬} niet functioneel volledig is.


19

Hoofdstuk 4

Semantische Tableaus I 4.1. Test met gebruikmaking van semantische tableaus de geldigheid van de volgende gevolgtrekkingen. Geef in geval van ongeldigheid een tegenvoorbeeld. (a) ¬(p → (q ∧ r)), r → (p ∧ q) / ¬r; (b) p → (q ∨ r), ¬((p ∨ q) → r) / p. (c) p → q, p → r / q ↔ r. (d) p1 → q1 , p2 → q2 , p1 ∨ p2 , ¬(q1 ∧ q2 ) / (q1 → p1 ) ∧ (q2 → p2 ). (e) p ∨ (q ∧ r) / (p ∨ q) ∧ r. (f) p → q, q → r / ¬r → ¬p. 4.2. Check met gebruikmaking van semantische tableaus de consistentie van de volgende verzamelingen formules. Als de verzameling consistent is, geef dan een model ervoor. (a) {(p ∨ r) → q, ¬q → r, p → (r ∨ ¬q)}; (b) {q → (r ∧ ¬p), r → p, (¬p ∧ r) → r, ¬q → ¬p}. (c) {p ↔ (q ∧ r), p ∧ s, s → (¬q ∨ ¬r)}. (d) {q → p, ¬p ∨ q, ¬p, ¬(q ∧ ¬r), ¬r}. (e) {p ↔ (q ∨ r), ¬q → ¬r, ¬(q ∧ p), ¬p}. (f) {p ∨ q, ¬(p → q), (p ∧ q) ↔ p}. 4.3. Test met gebruikmaking van semantische tableaus of de volgende formules tautologiën zijn. Indien dit niet het geval is, geef dan een tegenvoorbeeld. (a) ¬(p → q) ↔ (p ∧ ¬q). (b) ((p ∧ q) ∧ r) ∨ ((¬p ∧ ¬q) ∧ ¬r). (c) (p → q) ∨ (q → p).

20

Semantische Tableaus I

4.4. Test met gebruikmaking van semantische tableaus of de volgende paren formules logisch equivalent zijn. Indien dit niet het geval is, geef dan een tegenvoorbeeld. (a) ¬(¬p ∨ ¬q), ((q → p) ∧ q). (b) ¬(p ∧ (q ∨ r)), ¬p ∨ (¬q ∧ ¬r). (c) (p → q) → r, (p ∧ ¬q) ∨ ¬r. 4.5. Het connectief ⊕ (exclusieve of) wordt gedefinieerd door: ϕ ⊕ ψ is waar dan en slechts dan als ϕ of ψ waar is, maar niet allebei. Bepaal de reductieregels voor ⊕. 4.6. Bij het maken van een semantisch tableau ligt de volgorde waarin de regels toegepast worden niet vast. Beargumenteer dat desondanks het volgende geldt: Als een tableau sluit bij een bepaalde volgorde van toepassing van de regels, dan sluit dit tableau bij elke volgorde. 4.7. Beschouw de volgende oneindige top-sequent: p1 ∨ p2 , ¬p2 ∨ ¬p3 , p3 ∨ p4 , ¬p4 ∨ ¬p5 , . . . ◦ (a) Werk dit tableau uit totdat er een patroon duidelijk wordt. Welk patroon ontstaat er? (b) Laat zien dat er een oneindige tak is, zó dat: i. de tak nooit sluit ii. elke formule en subformule ergens op de tak afgehandeld wordt (c) Geef het model dat correspondeert met de oneindige tak die je hebt gevonden. 4.8. Stel dat voor de formules φ, ψ en χ, de tableaus voor de sequenten φ ◦ ψ en ψ ◦ χ sluiten. Bewijs dat dan het tableau voor de sequent φ ◦ χ ook sluit.


21

Hoofdstuk 5

Resolutie I 5.1. Breng de volgende formules op een conjunctieve normaalvorm en maak er daarna verzamelingen clausules van in accoladevorm. Welke van de clausules zijn Horn-clausules? (a) (¬p → q) ∧ ((p ∧ ¬r) ↔ q)) (b) (¬p ∧ ¬q ∧ ¬r) ∨ (p ∧ ¬q ∧ ¬r) ∨ (p ∧ ¬q ∧ r) (c) (q → p) ∧ (¬(r ∧ p) → s) ∧ ¬(p ∧ q) ∧ s ∧ ¬t 5.2. Geef de verzameling clausules in accoladevorm geassocieerd met de volgende formules: (a) (¬p ∨ ¬q ∨ t) ∧ ¬r ∧ (r ∨ p ∨ r) ∧ (¬q ∨ t ∨ ¬p) ∧ (¬t ∨ q) (b) (¬p → q) ∧ (s → ¬t). 5.3. Laat met behulp van resolutie zien dat de volgende verzamelingen clausules niet vervulbaar zijn: (a) {{p, ¬q, ¬r}, {¬p, ¬q, ¬r}, {r}, {¬r, q}} (b) {{¬q, ¬r, p}, {¬q, p}, {q, ¬r, p}, {s, q}, {r, p}, {¬p}} (c) {{¬p, q}, {¬q, r}, {¬r, p}, {p, q, r}, {¬p, ¬q, ¬r}} 5.4. Laat met gebruikmaking van resolutie zien dat de volgende formules niet vervulbaar zijn: (a) (p ∨ ¬q ∨ t) ∧ (¬p ∨ r) ∧ ¬r ∧ (t ∨ q) ∧ (r ∨ ¬t) (b) (p ∨ q) ∧ (p ∨ ¬q) ∧ (¬p ∨ q) ∧ ¬p (c) (p ∨ ¬r) ∧ (q → r) ∧ ¬(¬q ∨ s) ∧ ((p ∧ q) → s) 5.5. Laat met gebruikmaking van resolutie zien dat de volgende formule een tautologie is (¬q ∧ ¬r ∧ s) ∨ (¬q ∧ ¬s) ∨ (r ∧ s) ∨ q.

22

Resolutie I

5.6. Laat met gebruikmaking van resolutie zien dat p ∧ q ∧ r een gevolg is van de volgende verzameling clausules: {{¬p, q}, {¬q, r}, {p, ¬r}, {p, q, r}}.


23

Hoofdstuk 6

Vertaalopgaven 6.1. Vertaal de onderstaande predikaatlogische zinnen in het Nederlands. Gebruik daarbij de volgende vertaalsleutel: Bx := x is een bakker , Sx := x is slim, T x := x is traag. (a) ∃x(Bx ∧ T x) (b) ¬∃x(Bx ∧ T x ∧ Sx) (c) ∀x(Sx → Bx) (d) ∀x((Bx ∧ Sx) → ¬T x) (e) ∃xT x ∧ ∃xSx ∧ ¬∃x(T x ∧ Sx) (f) ∀x(Bx ∨ ¬Bx) 6.2. Vertaal de volgende zinnen in de predikaatlogika. Gebruik dezelfde vertaalsleutel als in de voorgaande opgave. (a) Trage bakkers zijn slim. (b) Sommige bakkers zijn slim. (c) Alle bakkers zijn slim en traag. (d) Iedereen die traag is en slim is een bakker. (e) Alleen bakkers zijn slim en traag. 6.3. Vertaal de volgende zinnen in de predikaatlogika, met identiteit (i.e. je mag, waar nodig, het identiteitssymbool ‘=’ gebruiken). Gebruik de volgende vertaalsleutel: H(x, y) := x houdt van y, m := Marjo, t := Ton, p := Piet (a) Ton houdt van Marjo, maar Marjo houdt van Piet. (b) Marjo houdt alleen van Ton. (c) Marjo en Ton houden van elkaar.

24

Vertaalopgaven

(d) Marjo houdt van iedereen van wie Ton houdt. (e) Marjo houdt hoogstens van diegenen van wie Ton houdt. (f) Marjo houdt van precies diegenen van wie Ton houdt. 6.4. Vertaal de volgende predikaatlogische zinnen in het Nederlands. Gebruik daarbij de volgende vertaalsleutel: Sx := x woont in Sneek, F x := x kan fietsen, Hxy := x respecteert y. (a) ∀x(Sx → F x) (b) ∀y(F y → ∃zHzy) (c) ∃x∀yHxy (d) ∀x(Sx ↔ ¬F x) (e) ∀x(Hxx ↔ Sx) (f) ∀x(∃uHxu → ∃v¬Hvx) 6.5. Vertaal de volgende zinnen in de predikaatlogika. Gebruik dezelfde vertaalsleutel als in de voorgaande opgave, het domein ‘mensen’, en eventueel het symbool ‘=’. (a) Er kan minstens één iemand fietsen. (b) Er wonen minstens twee mensen in Sneek. (c) Er wonen hoogstens twee mensen in Sneek. (d) Er wonen precies twee mensen in Sneek. (e) Er wonen precies twee mensen in Sneek die kunnen fietsen. (f) Er wonen precies twee mensen in Sneek, en die kunnen fietsen. 6.6. Vertaal de onderstaande zinnen in de predikaatlogika. Gebruik de volgende vertaalsleutel: B(x) := “x is een beer”, R(x) := “x is een broodje” S(x, y) := “x smeert y”, E(x, y) := “x eet y” (a) Alle beren smeren een broodje. (b) Er zijn geen 2 beren die hetzelfde broodje smeren. (c) Er is (precies) één beer die alle broodjes smeert. (d) Er zijn beren die alle broodjes eten die een van de andere beren smeert. (e) Alle beren eten alleen broodjes die door een andere beer zijn gesmeerd. (f) Als een beer een broodje smeert, dan is er een beer die het opeet. (g) Wie een door een beer gesmeerd broodje opeet is een beer.


25

6.7. Vertaal de onderstaande zinnen in de predikaatlogika. Gebruik de volgende vertaalsleutel, het gegeven domein, en eventueel ‘=’: Domein: mensen p := Paco Ox m := Masja P x Sx Lx

:= := := :=

x x x x

is is is is

een optimist een pessimist een student laf

Bxy := x is bevriend met y W xy := x vertrouwt y V xy := x verdedigt y

(a) Paco is niet met iedereen bevriend. (b) Er is iemand die niet met Paco bevriend is en wel door hem verdedigd wordt . (c) Paco vertrouwt zichzelf maar niemand anders. (d) Masja verdedigt iedereen die laf is, maar niemand anders. (e) Als iemand door niemand verdedigd wordt, dan is iedereen laf. (f) Naast Masja heeft Paco nóg een vriend(in), en die verdedigt hem. (g) Als iedereen iemand verdedigt, dan is niemand laf. (h) Masja verdedigt iedereen die niet door Paco verdedigd wordt. (i) Paco verdedigt iedereen die zichzelf niet verdedigt, en niemand anders. (j) Als minstens twee mensen niet laf zijn, dan bestaan er twee (verschillende) mensen die elkaar verdedigen. (k) Iedereen die met Paco bevriend is is een student. (l) Sommige studenten zijn niet met elkaar bevriend. (m) Masja is niet de enige student die met Paco bevriend is. (n) Alle optimisten verdedigen zichzelf. (o) Als Paco alleen met optimisten bevriend is, is hij zelf een optimist. (p) Paco is de enige optimist die met Masja bevriend is. (q) Er is iemand met wie Paco bevriend is, maar die hem niet vertrouwt. (r) Iedereen die met Masja bevriend is, is een pessimist. (s) Sommige pessimisten zijn met optimisten bevriend. (t) Paco is niet de enige pessimist die met Masja en niemand anders bevriend is. 6.8. Beschouw de volgende zinnen over natuurlijke getallen. Het éénplaatsige functiesymbool S staat voor de opvolgerfunctie Sn := n+1, de individuele constante 0 voor het getal 0. Welke uitspraken worden weergegeven door de volgende zinnen? (a) ∀x ¬(Sx = 0); (b) ∀x (x = 0 ∨ ∃y(x = Sy)).

26

Vertaalopgaven

6.9. Welke uitspraken over getallen worden weergegeven door de volgende zinnen? (a) ∀x∀y(x < y → ∃z(x < z ∧ z < y)); (b) ∀x∃y(y · y = x). Geef voor iedere zin een model waarin de zin waar is en een model waarin de zin niet waar is. 6.10. Vertaal de onderstaande predikaatlogische zinnen in het Nederlands. Gebruik daarbij de volgende vertaalsleutel: Hxy := x houdt van y. (a) ∀x(∀yHxy → ¬∀zHzx) (b) ∀x(∀yHxy → ∀z¬Hzx) (c) ∀x(∀yHxy → ∃z¬Hzx) (d) ∀x∃z(∀yHxy → ¬Hzx) (e) ∀x∃z∀y(Hxy → ¬Hzx) (f) ∀x∃z∃y(Hxy → ¬Hzx) (g) ∃z∀x∃y(Hxy → ¬Hzx) (h) ∃z∃y∀x(Hxy → ¬Hzx) (i) ∀x∀y(Hxy → Hyx) (j) ∀x∀y(Hxy ∧ Hyx) (k) ∃x∃y(Hxy → Hyx) (l) ∃x∃y(Hxy ∧ Hyx) Welke van deze zinnen zijn equivalent aan elkaar?

Hoofdstuk 7

Predikaatlogika en Modellen 7.1. Beschouw het model M = (D, I) gegeven door onderstaand plaatje, met D I(ci )

= {1, 2, 3, 4, 5} = i voor i = 1, 2, . . . 5

I(A) = {i|i is omcirkeld} I(R) = {< i, j > | er loopt een pijl van i naar j} 1

2

3

4

5 Welke van de volgende zinnen zijn waar in dit model? (a) Rc3 c4 27

28

Vertaalopgaven

(b) Ac5 (c) Rc1 c1 7.2. Geef de constructieboom van de predikaatlogische formule: ∀x(A(x) → ∀y(R(x, y) → A(y))). 7.3. Beschouw hetzelfde model als in opgave (7.1). Geef van elk van de volgende zinnen een constructie boom en geef aan of de zin waar of onwaar is. (a) Rc3 c5 ∧ Rc1 c2 (b) (Rc1 c3 ∨ Rc5 c5 ) → Ac4 (c) ∃xRxc2 (d) ∀x(∃yRyx ∨ Ax) (e) ∀z(Az → ∀u(Au ↔ (Rzu ∨ Ruz))) 7.4. Beschouw hetzelfde model als in opgave (7.1). Geef voor elk van de volgende zinnen aan of ze waar of onwaar zijn, en geef het bereik van de kwantoren die in de zin voorkomen. (a) ∃xAx ∧ ∀z(Rzz ∨ ∃xRxz) (b) ∃x∃y(Rxy → ∃zRyz) (c) ∃x(∃yRyx → ∃zRxz) (d) ∀xAx ∨ ∃y∃z(Ryz ∧ Rzy ∧ ¬∃u(¬u = y ∧ ¬u = z ∧ Ryu)) (e) ∀x(Ax ∨ ∃y∃z(Ryz ∧ Rzy ∧ ¬∃u(¬u = y ∧ ¬u = z ∧ Ryu))) 7.5. Geef voor de volgende formules aan wat de vrije en wat de gebonden variabelen zijn. Welke van deze formules zijn zinnen? (a) ∃x∃y(Rxy ∧ Ax) ∨ Az (b) ∃x∃y(Rxy ∧ Ax) ∨ Ax (c) ∀u(∃vAv → (∀zRvuz ∧ ¬Bu)) (d) ¬∃x¬(∀y(P x ∧ ∀x(Rx → Ry)) → ∃zSxyz) 7.6. We werken weer met het model van opgave (7.1). Geef voor elk van de volgende formules een constructie boom en zo mogelijk een bedeling voor de vrije variabelen zodat die formule waar is in het model onder die bedeling. Als voor een bepaalde formule zo’n bedeling niet bestaat, leg dan uit waarom niet. (a) Ax ∧ Rxy ∧ ¬Ryx ∧ ¬Ay (b) ¬∃yRxy (c) ¬Ax ∧ ∃y(Rxy ∧ ¬Ay ∧ ∃z(Ryz ∧ ¬Az))


29

(d) ¬Ax ∧ ∃y∃z(Rxy ∧ Ryz ∧ Rzx) (e) ∀y(Rxy → Ay) ∧ ∀y(Ryx → Ay) (f) ∀yRyx ∨ ∀yRxy (g) ∀y(Ryx → Ryy) (h) ∃y∃z(Rxy ∧ Ryx ∧ Rxz ∧ ∀w¬Rzw) (i) ∀y(Rxy → ∀z¬Ryz) (j) ∀u∀v((Rxu ∧ Rxv) → (Au ↔ Av)) 7.7. 1

2

5

3

4

In bovenstaand plaatje is M = (D, I) met D

=

{1, 2, 3, 4, 5}

I(A) = {i|i is omcirkeld} I(R) = {< i, j > | er loopt een pijl van i naar j} Geef voor elk van de volgende formules zo mogelijk een bedeling zodat die formule waar is in het model onder de bedeling. Als voor een bepaalde formule zo’n bedeling niet bestaat, leg dan uit waarom niet. (a) Ax ∧ Rxy ∧ Ryy (b) Ax ∧ ∀y(Rxy → Ryy) (c) ∀y(∀z(Rzz → Rzy) → Rxy) (d) Ax ∧ ∀y(Rxy → ¬Ay) (e) ∀y(Rxy → Ryx) (f) ∀y(Rxy ↔ Ryx) (g) ∀yRxy → Rxx (h) ∀y(Ryy ↔ x = y) (i) ∀u∀v((Au ∧ Av ∧ Ruv) ↔ ((x = u ∧ y = v) ∨ (y = u ∧ x = v)))

30

Vertaalopgaven

(j) ¬Ax ∧ ∀y∀z((Ryx ∧ Rzx) → y = z) 7.8. 1

4

2

3

In bovenstaand plaatje is M = (D, I) met D

= {1, 2, 3, 4}

I(A) = {i|i is omcirkeld} I(R) = {< i, j > | er loopt een pijl van i naar j} Geef voor elk van de volgende formules zo mogelijk een bedeling zodat die formule waar is in het model onder de bedeling. Als voor een bepaalde formule zo’n bedeling niet bestaat, leg dan uit waarom niet. (a) ¬Rxx ∧ Rxy ∧ Ryy (b) ∀y¬Rxy (c) ∀y(Ryx → ¬Ryy) (d) ∀y(¬Ay ↔ y = x) (e) ∃yRxy ∧ ¬∃y∃z(y 6= z ∧ Rxy ∧ Rxz) (f) Ax ∧ Ay ∧ ¬Rxy ∧ ¬Ryx ∧ ¬∃z(Rxz ∧ Rzy) (g) Rxy ∧ ¬Rxx ∧ (Ax ↔ Ay) (h) Ax ∧ Rxy ∧ Rzw ∧ ¬(x = y) ∧ ¬(z = w) 7.9. Beschouw het model M = (D, I) waarbij D

=

IN

I(a) I(b)

= 2 = 3

I(c) I(R)

= 5 = <

I(F )

=

+


31

Welke van de volgende zinnen zijn waar in dit model? (a) ∀x(Rax → Rc(F xb)) (b) ∃x(Rbx ∧ ∃y(Rxy ∧ Ryc)) (c) ∀x(Rax → ∃y(F by = x)) 7.10. Beschouw het model van de vorige opgave. Daarbij zijn nu de volgende twee bedelingen b1 , b2 : Var → IN gegeven: • b1 (x) = 0, b1 (y) = 12 • b2 (x) = 5, b2 (y) = 7 Welke van de volgende formules zijn waar in dit model, bij de bedelingen b1 en/of b2 ? (a) Rax (b) ¬∃z(Rzx) (c) ∀z∀w(¬Rxz ∨ ¬Rzw ∨ ¬Rwy)

T

7.11. Beschouw de 3-dimensionale figuur hiernaast. M1 = (D1 , I1 ) en M2 = (D2 , I2 ) zijn twee modellen gebaseerd op deze figuur, gegeven door: D1 = D2 = {A, B, C, D, E, F, G, H, T } I1 (R)(x, y) = “er is een rechte tussen x en y” I2 (R)(x, y) = “x en y liggen op dezelfde hoogte” I1 (S)(x, y) = I2 (S)(x, y) = “x ligt lager dan y” I1 (c) = I2 (c) = T

H

E

G F

D A

C B

(a) Geef voor M1 en M2 aan welke van de volgende zinnen waar zijn: i. ∀x∃y(Rxy ∧ ¬Sxy) ii. ∀x∀y(Rxy ∨ Sxy ∨ Syx) iii. ∀x(¬∃y(Rxy ∧ ¬∃zSzy) → x = c) (b) Geef voor elk van de volgende formules (apart) een bedeling b zodat die formule waar is in het model M1 onder die bedeling: i. ∃x(¬Sxy ∧ Rxy ∧ Rxz) ∧ ∃u(¬Suy ∧ Ruy ∧ ¬Ruz) ii. ∃y(Rxy ∧ Sxy ∧ ∀z(Ryz → z 6= c)) (c) Geef een formule φ(x) die in het model M1 alleen waar is onder bedelingen b waarvoor geldt b(x) = T . 7.12. Geef voor elk van de volgende zinnen (apart) zo mogelijk een interpretatie functie voor de in de zin voorkomende predikaten, zó dat de gegeven zin waar is in het model met domein D = {1, 2, 3, 4} en die interpretatiefunctie. Wanneer zo’n interpretatie niet bestaat, leg dan uit waarom niet.

32

Vertaalopgaven

(a) ∃xRxx ∧ ∀yBy (b) ∀x∀y(Bx → Rxy) (c) ∀x(∃yRyx ↔ Bx) (d) ∃x∃y∃z(Rxy ∧ Ryz ∧ ¬Rzy ∧ ∀u(Qxyu ∨ Quzu)) (e) ∀x∃yRxy ∧ ∀x∀y(Rxy → ¬x = y) 7.13. Beschouw de definities van de eigenschappen van een tweeplaatsige relatie in de appendix van het boek “Logica voor informatici”. Welke eigenschappen worden weergegeven door de volgende zinnen? (a) ∀x∀y((R(x, y) → R(y, x)); (b) ∀x∀y((R(x, y) ∧ R(y, x)) → x = y); (c) ∀x∀y∀z((R(x, y) ∧ R(y, z)) → R(x, z)); (d) ∀x∀y(R(x, y) → ∃w(R(x, w) ∧ R(w, y)). 7.14. Laat zien dat je kwantoren niet zomaar van plaats mag wisselen. (hint: probeer een formule te vinden, zó dat je door verwisselen van kwantoren een niet-equivalente formule kan krijgen. Laat zien met behulp van een model dat de verkregen formules wérkelijk niet logisch equivalent zijn).


33

Hoofdstuk 8

Tarski’s World 8.1. (Understanding atomic sentences) Open the files called Wittgenstein’s World and Wittgenstein’s Sentences. Notice that all the sentences in this file are atomic sentences. Run through them assessing their truth values in the given world. Use the evaluation capability of Tarski’s World to check your answers. (Since the sentences are all atomic sentences the game will not be helpful.) Then change Wittgenstein’s World in many different ways, seeing what happens to the truth of the various sentences. The main point of this exercise is to help you figure out how Tarski’s World interprets the various predicates. For example, what does BackOf(d, c) mean? Do two things have to be in the same column for one to be in back of the other? Play around as much as you need until you are sure you understand the meanings of the atomic sentences in this file. When you are finished, do not save the changes you have made to the files. 8.2. (Copying some atomic sentences) This exercise will give you some practice with the Tarski’s World Keyboard, as well as with the syntax of atomic sentences. The following are all atomic sentences of our language. Start a new sentence file and copy them into it. Using the Evaluation box, check each formula after you write it to see that it is a sentence. If you make a mistake, edit it before going on. (1) Tet(a) (2) Medium(a) (3) Dodec(b) (4) Cube(c) (5) FrontOf(a, b) (6) Between(a, b, c) (7) a = d (8) Larger(a, b)

34

Tarski’s World

(9) Smaller(a, c) (10) LeftOf(b, c) Save these sentences in a file named SENT2.SEN. 8.3. (Building a world) Build a world in which all the sentences in exercise 2 are simultaneously true. Save it in a file named WORLD3.WLD. Remark: the sentence “a = d” is only true if a and d are the same in size, shape and position, i.e. if a and d are different labels for the same object. Remark 2: Tarski’s World defines “Between(x, y, z)” to be true if and only if the line connecting the squares containing y and z, intersects or touches the square containing x. If y and z lie either on the same row or column or on adjacent rows or columns, the line is drawn from the midpoints of the containing squares’ facing sides, otherwise it is drawn from the closest corners of the squares. See also page 23 of the Tarski’s World Manual. Remark 3: You might find it useful to switch to the 2-D view on occasion. 8.4. (Translating atomic sentences) Here are some simple sentences of English. Start a new sentence file and translate them into the language of Tarski’s World. (1) a is a cube. (2) b is smaller than a. (3) c is between a and d. (4) d is large. (5) e is larger than a. (6) b is a tetrahedron. (7) e is a dodecahedron. (8) e is right of b. (9) a is smaller than than e. (10) d is in back of a. Now build a world in which all of them are true. Save these sentences and your world in files named SENT4.SEN and WORLD4.WLD. 8.5. Open Wittgenstein’s World. Start a new sentence list and write the following sentence. Then see if it is true. ¬¬¬¬¬Between(c, b, d). Now play the game, committing yourself to the truth of the sentence. What happens to the number of negation symbols as the game proceeds? What happens to your commitment?


35

8.6. Start a new sentence list and open Wittgenstein’s World. Write the following sentences in the list, saving them as SENT6.SEN. (1) (2) (3) (4) (5) (6) (7) (8) (9) (10)

Tet(f ) ∧ Small(f ) Tet(f ) ∧ Large(f ) Tet(f ) ∧ ¬Small(f ) Tet(f ) ∧ ¬Large(f ) ¬Tet(f ) ∧ ¬Small(f ) ¬Tet(f ) ∧ ¬Large(f ) ¬(Tet(f ) ∧ Small(f )) ¬(¬Tet(f ) ∧ Large(f )) ¬(¬Tet(f ) ∧ ¬Small(f )) ¬(¬Tet(f ) ∧ ¬Large(f ))

Once you have written these sentences, decide which you think are true. Record your evaluations, to help you remember. Then go through and use Tarski’s World to evaluate your assessments. Whenever you are wrong, play the game to see where you went wrong. If you are never wrong, then play the game a couple times anyway, knowing that you should win. Next, change the size or shape of f , predict how this will affect the truth values of these sentences, and see if your prediction is right. 8.7. (Evaluating sentences in a world) Open Peirce’s World and Peirce’s Sentences. There are 30 sentences in this file. Work through them, assessing their truth and playing the game when necessary. You may need to switch to the 2 − D view for some of the sentences. 8.8. (Evaluating sentences in a world) Open Leibniz’s World and Zorn’s Sentences. The sentences in this file contain both quantifiers and the identity symbol ‘=’. Work through them, assessing their truth and playing the game when necessary. 8.9. (A common translation mistake) Open Edgar’s Sentences and evaluate them in Edgar’s World. Make sure you understand why each of them has the truth value it does. Which of them would be a good translation of “There is a tetrahedron that is large”? (Clearly this English sentence is false in Edgar’s World, since there are no tetrahedra at all.) Which would be a good translation of “There is a cube between a and b”? Can you express in English the claim made by sentence 5? How about sentence 6? 8.10. (Name the object) Open Maigret’s World and Maigret’s Sentences. The object is to try to figure out which objects have names, and what they are. You should be able to figure this out from the sentences, all of which are true. Rereading the remarks to exercise (8.3) could prove useful as well. Once you have come to your conclusion, add names to the objects in the world and see if all the sentences do indeed evaluate as true. Save your modified world as WORLD10.WLD.

36

Tarski’s World

8.11. (Describing a world) Open Reichenbach’s World 1. Start a new sentence file where you will describe some features of this world using sentences of the simple Aristotelian forms. Check each of your sentences to see that it is indeed a sentence and that it is true in this world. (1) Use your first sentence to describe the size of all the tetrahedra. (2) Use your second sentence to describe the size of all the cubes. (3) Use your third sentence to express the truism that every dodecahedron is either small, medium, or large. (4) Notice that some dodecahedron is large. Express this fact. (5) Observe that some dodecahedron is not large. Express this fact. (6) Notice that some dodecahedron is small. Express this fact. (7) Observe that some dodecahedron is not small. Express this fact. (8) Notice that some dodecahedron is neither large nor small. Express this fact. (9) Express the observation that no tetrahedron is large. (10) Express the fact that no cube is large. Now change the sizes of the objects in the following way: make one of the cubes large, one of the tetrahedra medium, and all the dodecahedra small. With this changes, the following should come out false: 1, 2, 4, 7, 8, and 10. If not, then you have made an error in describing the original world. Can you figure out what it is? Try making other changes and see if you sentences have the expected truth values. Save your sentences as SENT11.SEN. 8.12. (Translating existential noun phrases) (a) Start a new sentence file named SENT12.SEN, and enter translations of the following English sentences. Each will use the symbol ∃ exactly once. None will use the symbol ∀. As you go, check that your entries are well-formed sentences. By the way, you will find that many of these English sentences are translated using the same first-order sentences. (1) (2) (3) (4) (5) (6) (7) (8)

Something is large. Something is a cube. Something is a large cube. Some cube is large. Some large cube is to the left of b. A large cube is to the left of b. b has a large cube to its left. b is to the right of a large cube. [Hint: This translation should be almost the same as the last, but it should contain the predicate symbol RightOf.]


(9) (10) (11) (12) (13) (14) (15)

37

Something to the left of b is in back of c. A large cube to the left of b is in back of c. Some large cube is to the left of b and in back of c. Some dodecahedron is not large. Something is not a large dodecahedron. It is not the case that something is a large dodecahedron. b is not to the left of a cube.

[Warning: This sentence is ambiguous. Can you think of two importantly different translations? One starts with ∃, the other starts with ¬. Use the second of these for your translation, since this is the most natural reading of the English sentence.] (b) Open Montague’s World. Notice that all the English sentences above are true in this world. Check that all your translations are also true. If not, you have made a mistake. Can you figure out what is wrong with your translation? (c) Move the large cube to the back right corner of the grid. Observe that English sentences 5, 6, 7, 8, 10, 11 and 15 are now false, while the rest are still true. Check that the same holds of your translations. If not, you have made a mistake. Can you figure out what is wrong with your translation? (d) Now make the large cube small. The English sentences 1, 3, 4, 5, 6, 7, 8, 10, 11 and 15 are false in the modified world, the rest are true. Again, check that your translations have the same truth values. If not, figure out what is wrong. (e) Finally, move c straight back to the back row, and make b large. All the English sentences other than 1, 2 and 13 are false. Check that the same holds for your translations. If not, figure out where you have gone wrong. 8.13. (Vacuously true generalizations) Open Dodgson’s Sentences. Note that the first sentence says that every tetrahedron is large. (a) Open Peano’s World. Sentence 1 is clearly false in this world, since the small tetrahedron is a ‘counterexample’ to the universal claim. What this means is that if you play the game committed to the falsity of this claim, then when Tarski’s World asks you to pick an object you will be able to pick the small tetrahedron and win the game. Try this. (b) Delete this counterexample and verify that sentence 1 is now true. (c) Now open Peirce’s World. Verify that sentence 1 is again false, this time there are three counterexamples. (Now if you play the game committed to the falsity of the sentence, you will have three different winning moves when asked to pick an object: you can pick any of the small tetrahedra and win.)

38

Tarski’s World

(d) Delete all three counterexamples, and evaluate the claim. Is the result what you expected? The generalization is true, because there are no counterexamples to it. It is what we called a vacuously true generalization, since there are no objects that satisfy the antecedent. That is, there are no tetrahedra at all, small, medium or large. (e) Confirm that all of sentences 1-3 are vacuously true in the current world. (f) Two more vacuously true sentences are given in sentences 4 and 5. However, these sentences are different in another respect. Each of the first three sentences could have been non-vacuously true in a world, but these latter two can only be true in worlds containing no tetrahedra. That is, they are inherently vacuous. 8.14. (Translating universal noun phrases) (a) Start a new sentence file, and enter translations of the following sentences. This time each translation will contain exactly one ∀ and no ∃. (1) (2) (3) (4) (5) (6) (7) (8) (9) (10)

(11) (12)

(13)

(14) (15) (16)

All cubes are small. Each small cube is to the right of a. All dodecahedra are large. a is to the left of every dodecahedron. Every medium tetrahedron is in front of b. Each cube is either in front of b or in back of a. Every cube is to the right of a and to the left of b. Everything between a and b is a cube. Everything smaller than a is a cube. All dodecahedra are not small. [Note: Most people find this sentence ambiguous. Can you find both readings? One starts with ∀, the other with ¬. Use the former, the one that means, in effect, that all the dodecahedra are either medium or large.] No dodecahedron is small. a is not to the right of everything. [Note: This sentence is ambiguous. We want you to interpret it as denial of the claim that a is to the right of everything.] a is not to the right of anything. [Note: These last two sentences mean different things, though they can both be translated using ∀, ¬, and RightOf.] a is not to the right of any cube. If something? is a cube, then it is right of a and left of b. Something? is a cube if and only if it is right of a and left of b.

Save your sentences as SENT14.SEN. (*) While these sentences contain the noun phrase ‘something’, they


39

are actually making a universal claim, and so should be translated with ∀. You might first try to paraphrase them using the English phrase ‘every cube’. (b) Open Claire’s World. Check to see that all the English sentences are true in this world. Now check to see that all your translations are true. Again, if you have made any mistakes, fix them. (c) Adjust Claire’s World by moving a to the front, right corner of the grid. With this change, the English sentences 2, 4, 7, 13, 14, 15 and 16 are false, while the rest are true. Make sure that the same holds of your translations. If not, try to figure out what is wrong and fix it. (d) Next, open Wittgenstein’s World. Observe that the English sentences 2, 4, 8, 9, 12 and 14 are true, but the rest are false. Check that the same is the case with your translations. If not, try to fix them. (e) Finally, open Leibniz’s World. The English sentences 3, 4, 8, 9, 10, 11, 12, 13, and 14 are true, but the rest are false. Check your translations. 8.15. (Evaluating multiple quantifier sentences) Open up Peano’s World and Peano’s Sentences, and evaluate the sentences in the world. If you have trouble with any, play the game (several times if necessary) until you see where you are going wrong. 8.16. (Evaluating multiple quantifier sentences) This exercise deals with multiple quantifiers and their interaction with negation. Open Frege’s Sentences. Work through them one at a time, assessing their truth in Peirce’s World. The game should come in very handy here. 8.17. (Evaluating mixed quantifier sentences with the identity symbol) Open Leibniz’s World and use it to evaluate the sentences in Leibniz’s Sentences. If your assessment of a sentence is wrong, use the game to figure out why. 8.18. (Building a world) Open Buridan’s Sentences. Build a world in which all ten sentences are true at once. Save the world, calling it WORLD18.WLD. 8.19. (Evaluating more mixed quantifier sentences) Open Hilbert’s Sentences and evaluate them in Peano’s World. 8.20. Start a new sentence file named SENT20.SEN, and enter translations of the following sentences: (1) Every cube is left of every pyramid. (2) Every small cube is behind a big cube. (3) In front of every pyramid there is a cube. (4) There is a big cube in front of a small cube. (5) Nothing is bigger than everything.

40

Tarski’s World

(6) Any cube that is in front of all pyramids, is big. (7) Everything that is right of any big cube, is small. (8) Nothing that is behind a cube and in front of another cube, is big. (9) If something has nothing behind it, then it is a cube. (10) Every dodecaëder is smaller than some pyramid. Can you build a world in which all ten sentences are true? If so, build one. If not, explain why it isn’t possible. 8.21. A limitation of Tarski’s World is that the ‘area’ is only 8x8. Replace sentence (8) in the last exercise, by “In front of every big cube there is a small cube”, and translate it into a predicate-logic formula. Can you build an 8x8 world in which all ten sentences are true? Can you find an infinite world in which all ten sentences are true?

41


Hoofdstuk 9

Semantische Tableaus II 9.1. Stel dat in een semantisch tableau op een gegeven moment de volgende sequent voorkomt: ∃yRd1 y, ∀x∃yRxy ◦ ∀xAx ∧ ∃yBy, Bd2

D = {d1 , d2 }

Geef alle mogelijkheden voor de volgende stap in het tableau. 9.2. (a) Zij gegeven de sequent ∀x∃yRxy ◦ ∃y∀xRxy Laat zien dat, door het toepassen van de regel ∃L op een inwendige existentiele kwantor, we dit tableau sluitend kunnen krijgen. (b) Beargumenteer dat het toepassen van de regels ∃L , ∃R , ∀L , ∀R op inwendige kwantoren niet een goed idee is (hint: laat zien dat de gevolgtrekking ∀x∃yRxy / ∃y∀xRxy niet geldig is). 9.3. Check met gebruikmaking van semantische tableaus de geldigheid van de volgende gevolgtrekkingen. Geef in geval van ongeldigheid een tegenvoorbeeld. Als je meerdere open takken hebt gevonden, geef dan duidelijk aan welke tak je als basis hebt genomen voor je tegenvoorbeeld. (a) ∃x(Ax ∧ Bx) / ∀x(Ax → ∃yBy) (b) ∃x(Ax ∧ Bx) / ∀x∃y(Ax ∧ By) (c) ∀x(Ax → (Bx ∨ Cx)) / ∀x(Ax → Bx) ∨ ¬∃x(Ax ∧ Cx) (d) ∀x(Ax → (Bx ∨ Cx)) / ∀x(Ax → Bx) ∨ ∃x(Ax ∧ ¬Cx) (e) ∀xRxx, ∃x(Ax ∨ ∀yRxy) / ∀xAx (f) / ¬∃x∀y(Rxy ↔ ¬Ryy) (g) / ¬∃x∀y(Rxy ↔ ¬∃z(Ryz ∧ Rzy)) (h) ∃x(Ax ∧ Rxx), ∃y∀x(Ax → Rxy) / ∀x∃yRxy

42

Semantische Tableaus II

9.4. Als bij opdracht 9.3 (a) (b) (c) (d) (e) (f) (g) (h)

∀x∀y(Cxy → Dyx), ∀x∀y(Cxy → Cyx) / ∀x∀y(Dxy → Dyx) ∀xAx → (∃yAy → ∀xBx) / ∃xBx ∀x∀y∀z((Rxy ∧ Rxz) → Ryz) / ∀x∀y∀z((Rxy ∧ Rxz) → Rzy) ∃xRx ∧ ∃x∀y(Rx → Sy) / ∀ySy ∀x(Ax → Bx) ∨ ∀y(By → Ay) / ∀x∀y((Ax ∧ By) → (Bx ∨ Ay)) ∀x(Ax → Bx) ∨ ∀y(By → Ay) / ∃x(Ax ↔ Bx) ∀x∀y(Rxy ∨ Ryx)), ∀x(Ax ∨ Bx) / ∀x∀y((¬Rxy ∧ ¬Ryx) → Bx) ∃xAx ∧ ∃x∀y(Ax → Ryy) / ∃x(Ax ∧ Rxx)

9.5. (a) Laat zien dat je een tableau kan vinden met een oneindige tak, beginnende met de sequent ∃xAx, ∀x∃yRxy ◦ ∃yAy (b) Laat zien dat de gevolgtrekking ∃xAx, ∀x∃yRxy / ∃yAy geldig is. (c) Beargumenteer dat niet elke oneindige tak een open tak is. Kan je zeggen wanneer dat wel het geval is? 9.6. Als bij opdracht 9.3 (a) (b) (c) (d) (e) (f) (g) (h)

∀xAx / ∀x¬Bx ∨ ∃x(Bx ∧ ∀yAy) ∃x(Ax → ∀yBy) / ∀x∃y(Ax → By) ∃x(Ax → ∀yBy) / ∃y∀x(Ax → By) ∀xRx ∧ ∀x∃y(Ry → Sx) / ∀ySy ∀x(Ax → ∃yRxy) / ∀x(Ax → ¬Rxx) ∀x∃y(P xy ↔ ¬Rxy) / ∀x∃y(P xy ∨ Rxy) ∀x∃yRxy / ∃y∀xRxy ∀x∃y(Rxy ∧ ¬∃zRyz) / ∀xAx

9.7. Een formule φ heet een Π2 -formule als zij te schrijven is als φ ≡ ∀¯ x∃¯ y ψ(¯ x, y¯) i.e. als φ bestaat uit een aantal ‘∀’ kwantoren, gevolgt door een aantal ‘∃’ kwantoren, gevolgd door een formule zonder kwantoren. Voorbeelden van Π2 -formules zijn ∀x∃yR(x, y) en ∀x∀y∃z(A(x, y) → B(z)). (a) Zij φ een Π2 -formule. Laat zien dat als een semantisch tableau begint met de sequent ◦φ dat dan alle takken eindig zijn. (b) Beargumenteer dat voor elke Π2 -formule φ, de vraag “is ψ een tautologie?” in eindige tijd beslisbaar is.


43

Hoofdstuk 10

Prenexvorm 10.1. Beschouw de formule (∀x∃yAxy) ∧ (∃z∃u(Cz ∨ Cu)). (a) Breng de kwantor ∀x ’naar buiten’, dat is: herschrijf de formule tot een formule van de vorm ∀x(. . .) (geen nieuwe kwantoren toevoegen). (b) Breng hierna de kwantor ∃y naar buiten. (c) Idem voor ∃z. (d) Idem voor ∃u. 10.2. Beschouw de formule ∃x(∀yRy → ∃yByx). (a) Hernoem de variabelen zodanig dat geen twee kwantoren in de formule dezelfde variabelen gebruiken. (b) Breng één voor één de kwantoren naar buiten. 10.3. Zet de volgende zinnen in prenexvorm: (a) (b) (c) (d) (e) (f)

∀x∀y(Rxy → ∀z(Ryz → Rxz)); ∀x(∃yRxf y → ¬P x); ∃x∀y(Rxy ↔ ¬∃zSxyz); ¬∀x∀y(Rxy ∨ ∀zAz); ∀x∃y(Rxy → ∃wRwy) → ∃y∀x(Sxy → ∃wSyw); ∀x(Rx ∨ Sx) → (∀xRx ∨ ∀xSx).

10.4. Zet de volgende formules in prenexvorm: (a) (b) (c) (d) (e) (f)

Qxy → ∃z(∀yQyz → Qxz) ∃x∀yR(x, y) → ¬∀xR(x, x) Ax ↔ ∃xAx ¬(¬∃y∀zRxyz → ∃z∀ySzyx) (∀x∃yAxy ∧ ¬∃x∀yBxy) → ∃yCxy (Rx ∨ Sx) → (∀xRx ∨ ∀xSx).


45

Hoofdstuk 11

Resolutie II 11.1. Bepaal voor elk van de volgende paren uitdrukkingen of ze unificeerbaar zijn en zo ja, geef dan de meest algemene substitutie. (a) Bevat(ijzer, y) en Bevat(x, spinazie) (b) Rel(x, x, y) en Rel(x0 , y 0 , y 0 ) (c) Som(S(x), y, S(z)) en Som(0, S(S(0)), w) (d) Som(S(x), y, S(z)) en Som(S(0), S(0), w) 11.2. De afdeling diëtetiek van een academisch ziekenhuis gebruikt het volgende logische programma: {Heeft-Engelse-ziekte(Shelley)} {Heeft-bloedarmoede(Ben)} {Bevat(ijzer, spinazie)} {Bevat(vitamine-D, eieren)} {Peulvrucht(linzen)} {Peulvrucht(kikkererwten)} {Vette-vis(makreel)} {Vette-vis(sardines)} {Bevat(vitamine-D, x), ¬Vette-vis(x)} {Bevat(calcium, x), ¬Peulvrucht(x)} {Heeft-nodig(x, ijzer), ¬Heeft-bloedarmoede(x)} {Heeft-nodig(x, calcium), ¬Heeft-Engelse-ziekte(x)} {Heeft-nodig(x, vitamine-D), ¬Heeft-nodig(x, calcium)} {Moet-eten(x, y), ¬Heeft-nodig(x, z), ¬Bevat(z, y)}

46

Resolutie II

(a) Hieronder volgt een resolutie-afleiding uit bovenstaand programma: {¬Heeft-nodig(x, vitamine-D)} {Heeft-nodig(x0 , vitamine-D), ¬Heeft-nodig(x0 , calcium)}

[. . . ] {¬Heeft-nodig(x, calcium)} {Heeft-nodig(x0 , calcium), ¬Heeft-Engelse-ziekte(x0 )}

[. . . ] {¬Heeft-Engelse-ziekte(x)} {Heeft-Engelse-ziekte(Shelley)}

[. . . ]

2 Geef de substituties die gebruikt zijn in deze afleiding, en de uiteindelijke substitutie voor x. (b) Wat zijn de mogelijke clausules waarmee de query Heeft-nodig(Ben, y) gecombineerd zou kunnen worden in een volgende resolutiestap? (c) Bepaal met behulp van resolutie of de formule Heeft-nodig(x, y) ∧ Bevat(y, spinazie) vervulbaar is. Doe dit door te proberen uit de query {¬Heeft-nodig(x, y), ¬Bevat(y, spinazie)} en de programmaclausules met behulp van resolutie de lege query (2) af te leiden. Vermeld bij iedere resolutie-stap de gebruikte clausule, substitutie en hernoeming. (d) Als bij (b) voor de formule Moet-eten(x, linzen). (e) Als bij (b) voor de formule Moet-eten(Shelley, sardines). 11.3. Een relatiebemiddelingsbureau gebruikt het onderstaande logische programma. Van alle clienten (tot nu toe vier) wordt met behulp van het vierplaatsige predikaat Persoon(x,y,w,z) de naam, het geslacht (man of vrouw), het karakter (verlegen of extravert) en de leeftijd (jong, middel of oud) bijgehouden. Tevens administreert men met het vierplaatsig predikaat Prefereert(x, y, w, z) welke eigenschappen (w.b. geslacht, karakter en leeftijd) de clienten in hun eventuele nieuwe partners wensen. Wil-wel(x, y) geeft aan dat x in principe wel met y kennis wil smaken. Koppel(x, y) tenslotte geeft aan dat het bemiddelingsbureau x en y voorstelt met elkaar kennis te maken.


47

{Persoon(James, man, verlegen, oud)} {Persoon(Laura, vrouw, verlegen, middel)} {Persoon(Ruth, vrouw, extravert, oud)} {Persoon(Simon, man, extravert, jong)} {Prefereert(James, vrouw, w, z)} {Prefereert(Laura, u, extravert, z)} {Prefereert(Laura, u, verlegen, middel)} {Prefereert(Ruth, vrouw, w, middel)} {Prefereert(Ruth, man, w, jong)} {Prefereert(Simon, vrouw, extravert, z)} {Wil-wel(x,y), ¬Prefereert(x, , , ), ¬Persoon( {Koppel(x, y), ¬Wil-wel(x, y), ¬Wil-wel(y, x)}

,

,

,

)}

(a) Vul de lege plaatsen in de één-na-laatste regel van het programma zo aan met variabelen dat Wil-wel de juiste betekenis krijgt. (b) Welk antwoord krijg je op de query {¬Koppel(James, x)}? (Maak hiervoor geen resolutie-afleiding.) (c) Leid met resolutie antwoorden af op de volgende drie queries. Vermeld hierbij alle gebruikte resoluties, clausules, substituties en hernoemingen. i. {¬ Prefereert(x, vrouw, verlegen, middel), ¬ Persoon(x, vrouw, verlegen, z)} ii. {¬ Koppel(Laura, x)} iii. {¬ Koppel(x, Simon)} 11.4. Op het plaatje hieronder rechts vindt je een schematische kaart waarop een grote haven bij Athene, Piraeus, en de eilandengroep de Cycladen zijn afgebeeld. De pijltjes staan voor directe bootverbindingen. Voor deze opgave nemen we aan dat men alleen in de richting van de pijltjes kan reizen. Bij het kaartje hoort het volgende Horn-clausule programma: {Direct(Piraeus, Kythnos)}

Piraeus

{Direct(Piraeus, Syros)} {Direct(Piraeus, Milos)}

Kythnos

Syros

{Direct(Kythnos, Serifos)} {Direct(Serifos, Milos)}

Paros

{Direct(Syros, Paros)} Serifos

{Direct(Paros, Serifos)} {Direct(Paros, Naxos)}

Naxos

{Direct(Milos, Santorini)} {Direct(Naxos, Santorini)} {Direct(Naxos, Amorgos)}

Amorgos Milos Santorini

48

Resolutie II

We willen nu een programma Reis schrijven, zó dat Reis(x, y) staat voor “men kan (eventueel met tussenstops) een bootreis maken van x naar y via de pijlen zoals die in het kaartje gegeven zijn”. Dus bijvoorbeeld Reis(Syros, Amorgos) moet waar worden (omdat men van Syros via Paros en Naxos naar Amorgos kan reizen) en Reis(Amorgos, Paros) moet onwaar worden (omdat vanaf Paros je niet met de richting van de pijlen mee naar Amorgos kunt varen). (a) Schrijf een Horn-clausule programma voor Reis(x, y), door aan het boven gegeven programma hoogstens twee Horn-clausules toe te voegen. (b) Leid met behulp van resolutie uit je uitgebreide programma een antwoord af op de query {¬ Reis(Piraeus, Santorini)}. Vermeld hierbij alle gebruikte resoluties, clausules, substituties en hernoemingen. 11.5. Waarom is het volgende programma niet een correct antwoord op opgave 11.4a? {Reis(x, y), ¬Direct(x, y)} {Reis(x, y), ¬Direct(x, z), ¬Direct(z, y)} 11.6. De stamboom: Bregor Emeldir X Barahir Luthien X Beren

Bregolas Belegund

Erchamion

Huor X Rian Dior X Nimloth ‘Thingol’s Erfgenaam’ Tuor X Idril

Celebrindal

kan gecodeerd worden met de volgende clausules: {Kind(Barahir, Bregor)}

{Kind(R´ıan, Belegund)}

{Kind(Bregolas, Bregor)}

{Kind(Dior, L´ uthien)}

{Kind(Beren, Emeldir)}

{Kind(Dior, Beren)}

{Kind(Beren, Barahir)}

{Kind(Tuor, Huor)}

{Kind(Belegund, Bregolas)}

{Kind(Tuor, R´ıan)}


49

Het programma Gvv(x, y) berekent dan of twee mensen een gemeenschappelijke voorvader hebben: {¬Kind(x, z), ¬Kind(y, z), Gvv(x, y)} {¬Kind(x, z), ¬Gvv(y, z), Gvv(x, y)} {¬Gvv(x, z), ¬Kind(y, z), Gvv(x, y)} (a) Laat met behulp van dit programma zien, dat Dior en Belegund een gemeenschappelijke voorvader hebben. Vermeldt hierbij alle gebruikte resoluties, clausules, substituties en hernoemingen. (b) Schrijf een nieuw programma Afstammeling(x, y) in Horn-clausule vorm, dat berekent of x een afstammeling is van y. (c) Schrijf een nieuw programma Gvv2 (x, y), bestaande uit het programma Afstammeling plus één extra Horn-clausule, dat net als Gvv berekent of x en y een gemeenschappelijke voorvader hebben. Het programma mag geen gebruik maken van Gvv zelf. 11.7. Gegeven is het volgende programma Greater, dat bepaalt of een getal groter is dan een ander getal: {Greater(Sx, x)}, {Greater(Sy, x), ¬Greater(y, x)} Laat met behulp van dit programma zien dat 4 > 1. Vermeldt hierbij alle gebruikte resoluties, clausules, substituties en hernoemingen. 11.8. Gegeven is het volgende programma Som voor het berekenen van de som van twee getallen: {Som(0, x, x)}, {Som(Sx, y, Sz), ¬Som(x, y, z)} (a) Bereken 2 + 2 met dit programma. Vermeld hierbij alle gebruikte resoluties, clausules, substituties en hernoemingen. (b) Bereken alle x en y zó dat x + y = 3. Voor elke combinatie, geef een resolutie-afleiding die laat zien dat deze x en y voldoen. 11.9. (a) Schrijf een Horn-clausule programma Min voor het aftrekken van twee getallen, gebruikmakend van het predikaat Som. (b) Bereken 3 − 1 met dit programma. Vermeld hierbij alle gebruikte resoluties, clausules, substituties en hernoemingen.

50

Resolutie II

11.10. Gegeven is het volgende programma Prod (gebruikmakend van het predikaat Som) voor het berekenen van het produkt van twee getallen: {Prod(0, x, 0)}, {Prod(Sx, y, z), ¬Prod(x, y, u), ¬Som(u, y, z)} (a) Bereken 2 × 2 met dit programma. Vermeld hierbij alle gebruikte resoluties, clausules, substituties en hernoemingen. (b) Bereken met behulp van dit programma een x en y zo dat x × y = 2. Vermeld hierbij alle gebruikte resoluties, clausules, substituties en hernoemingen. 11.11. De Fibonacci-functie f wordt gedefinieerd door: • f (0) = 1, f (1) = 1, • f (n + 2) = f (n + 1) + f (n), voor n ≥ 0. (a) Schrijf een Horn-clausule programma om de Fibonacci-functie te berekenen, gebruikmakend van het predikaat Som. (b) Voer het programma uit met resolutie ter berekening van f (3). Vermeld hierbij alle gebruikte resoluties, clausules, substituties en hernoemingen. 11.12. In opgave (3.7) werd je gevraagd een inductieve definitie te geven van de exponentiefunctie E(n) gedefinieerd door E(0) := 1, E(n) := 2n = 2 × 2 × . . . × 2 (n times) (a) Zet de inductieve definitie van opgave (3.7) om in een Horn-clausule programma, gebruikmakend van het predikaat Prod. (b) Bereken 23 met dit programma. Vermeld hierbij alle gebruikte resoluties, clausules, substituties en hernoemingen. Je mag hierbij Prod beschouwen als basispredikaat, i.e. je mag doen alsof het predikaat Prod niet gedefinieerd is door de clausules van opgave (11.10), maar door de oneindige collectie clausules: {Prod(0, 0, 0)}, {Prod(0, 1, 0)}, {Prod(0, 2, 0)}, {Prod(0, 3, 0)}, . . . {Prod(1, 0, 0)}, {Prod(1, 1, 1)}, {Prod(1, 2, 2)}, {Prod(1, 3, 3)}, . . . {Prod(2, 0, 0)}, {Prod(2, 1, 2)}, {Prod(2, 2, 4)}, {Prod(2, 3, 6)}, . . . {Prod(3, 0, 0)}, {Prod(3, 1, 3)}, {Prod(3, 2, 6)}, {Prod(3, 3, 9)}, . . . .. .. .. .. .. . . . . .


51

Bijlage A

Oefententamens Voor alle tentamens hier was oorspronkelijk drie uur gegeven. Bij sommige hertentamens hadden studenten de mogelijkheid om deel I en deel II tegelijk te doen. Daarvoor hoefden dan alleen de opgaven gemaakt te worden, die met een sterretje (*) zijn aangegeven.

52

Oefententamens

Hertentamen Logika voor AI: deel I 8 januari 1996 1.*(15 punten) Beschouw de volgende formule: F = ((¬p → q) ∧ r) ↔ (p → (q ∧ r)) (a) Geef de waarheidstafel van F . (b) Geef de conjunctieve en de disjunctieve normaalvorm van F . (c) Geef de modellen van F . 2.(15 punten) Test met behulp van semantische tableaus de geldigheid van de volgende gevolgtrekkingen. Geef in het geval van ongeldigheid een tegenvoorbeeld. (a) p → (r → (q ∧ s)), ¬(q → r) / p → s (b) p ↔ (q ∨ r), ¬r ∨ ¬p / ¬r 3.(20 punten) (a) Laat met behulp van resolutie zien dat de volgende formule niet vervulbaar is: (q → p) ∧ ¬(p ∨ r) ∧ (r ∨ s) ∧ (s → (p ∨ q)) (b) Laat met behulp van resolutie zien dat ¬q ∧ ¬p een logisch gevolg is van (¬p ∨ ¬q) ∧ (¬p ∨ q) ∧ (¬q ∨ p). 4.*(20 punten) (a) Geef een inductieve definitie van i. het aantal haakjes in een formule, ii. het aantal symbolen in een formule die geen haakjes zijn. (b) Bewijs met formule-inductie dat voor elke formule het aantal symbolen die geen haakjes zijn groter is dan het aantal haakjes in de formule. 5.*(20 punten) Van het nieuwe connectief ∗ zijn er de volgende gegevens: (a) {p ∗ q, p, q} is niet consistent, (b) p ∨ q is een logisch gevolg van p ∗ q, (c) q is een logisch gevolg van {p, ¬(p ∗ q)}, (d) {q, p ∗ q} is consistent. Geef de waarheidstafel van ∗ . +++++++


53

Hertentamen Logika voor AI: deel II 8 januari 1996 1.*(20 punten) Vertaal de onderstaande zinnen in de predikaatlogika. Gebruik de volgende vertaalsleutel, het gegeven domein, en eventueel ‘=’. Domein := mensen,

D(x) := x is een vandaal,

P (x) := x is een politieman,

N (x):= x is nalatig geweest,

I(x, y) := x heeft y ingerekend. (a) Iedere vandaal is door een politieman ingerekend. (b) Er zijn politiemannen die meer dan één vandaal hebben ingerekend. (c) Niet iedere politieman die geen vandaal heeft ingerekend is nalatig geweest. 2.(15 punten) Beschouw de volgende twee 3-dimensionale modellen M1 = (D1 , I1 ) en M2 = (D2 , I2 ): H

E

F

D A

F

G

D

E C

C

B

B

A

I1 (R)(x, y) = I2 (R)(x, y) =“er is een lijn tussen x en y” I1 (B)(x, y) = I2 (B)(x, y) =“x ligt (3-dimensionaal gezien) hoger dan y” (a) Geef voor zowel M1 als M2 aan welke van de volgende 3 zinnen waar zijn: i. ∀x∀y∀z((Rxy ∧ Ryz) → ¬Rxz) ii. ∀x∃y(Rxy ∧ ¬Bxy ∧ ¬Byx) iii. ∃x∀y(x 6= y → Byx) (b) Geef voor elk van de volgende formules (apart) een bedeling zodat die formule waar is in het model M1 onder de bedeling: i. ∀z(Rxz ∨ Ryz) ii. ¬Bxy ∧ ¬Byx ∧ ¬Rxy ∧ ∃z(Rxz ∧ Rzy) iii. ∃x(Bxy ∧ Rxy) ∧ ∃y(Bxy ∧ Rxy) ∧ ¬Rxy

54

Oefententamens

3.(15 punten) Zet de volgende formules in prenexvorm. (a) ¬(∀x∃yRxy ∨ ∃x¬∃yRyx) (b) ∀x(∃yRxy ↔ ∃ySxy) 4.*(20 punten) Test met behulp van semantische tableaus de geldigheid van de volgende gevolgtrekkingen. Geef in het geval van ongeldigheid een tegenvoorbeeld. (a) ∀xAx → ∀yBy / ∃x∀y(Ax → By) (b) ∀x¬Rxx, ∀x∀y(Rxy → Ryx) / ∀x∀y¬Rxy 5.*(20 punten) Het volgende programma berekent of een getal even dan wel oneven is: {Even(0)}, {¬Even(x),Oneven(Sx)}, {¬Oneven(x),Even(Sx)}. (a) Laat met behulp van dit programma zien dat 4 even is. Vermeld hierbij alle gebruikte resoluties, clausules, substituties en hernoemingen. (b) Schrijf een nieuw programma in Horn-clausule vorm zonder gebruik te maken van Oneven, dat berekent of een getal even is. (c) Schrijf een nieuw programma in Horn-clausule vorm zonder gebruik te maken van Even, dat berekent of een getal oneven is. +++++++


55

Hertentamen Logika voor AI: deel I 6 januari 1997 1.*(20 punten) Beschouw de volgende twee formules: F

=

¬(((p → q) ∧ r) ∨ ¬p)

G

=

(p ∧ ¬r) ∨ ¬(p → (p ↔ q))

(a) Laat met behulp van waarheidstafels zien dat F en G logisch equivalent zijn. (b) Geef een conjunctieve en een disjunctieve normaalvorm van F . (c) Geef de modellen van F . 2.(15 punten) Test met behulp van semantische tableaus de geldigheid van de volgende gevolgtrekkingen. Geef in het geval van ongeldigheid een tegenvoorbeeld. (a) (¬p ∨ (q ∨ r)), ¬(p → q), (q ↔ s) / (r → (p ∧ s)) (b) ((p ∧ q) → r), (r ↔ ¬s) / (s → (¬p ∨ ¬q)) 3.*(20 punten) In de volgende opgave beschouwen we uitsluitend en alleen zinnen die zijn opgebouwd met de propositieletters en de connectieven ∧, ∨ en ¬. De opgave draait om het vinden van een generalisatie van de equivalentie ¬(p ∧ q) ⇔ ¬p ∨ ¬q (a) Zij F (φ) de formule die we uit φ krijgen als we voor elke propositieletter een negatieteken erbij zetten, en vervolgens alle ∧-connectieven vervangen door ∨-connectieven en omgekeerd. Geef een inductieve definitie van F (φ). (b) Bewijs met inductie dat voor alle zinnen φ geldt F (φ) is logisch equivalent met ¬φ 4.*(15 punten) Laat het éénplaatsige connectief 3 gegeven zijn door de waarheidstafel p 3p 0 0 1 0 Laat zien dat de verzameling connectieven {→, 3} functioneel volledig is.

56

Oefententamens

5.(20 punten) (a) Geef de verzameling clausules in accoladevorm geassocieerd met de formule (p ↔ (p ∧ q)) ∧ ¬(q ∧ r ∧ s) ∧ (¬r → t) ∧ (¬t → s) (b) Laat met behulp van resolutie zien dat p → t een gevolg is van de bovenstaande formule. (c) Laat met behulp van resolutie zien dat de volgende verzameling clausules niet vervulbaar is: {{p, q}, {p, r}, {q, r}, {¬p, ¬q}, {¬p, ¬r}, {¬q, ¬r}} +++++++


57

Hertentamen Logika voor AI: deel II 6 januari 1997 1.*(15 punten) Vertaal de onderstaande zinnen in de predikaatlogika. Gebruik de volgende vertaalsleutel, het gegeven domein, en eventueel ‘=’: Domein := mensen P := Piet

B(x, y) := x is een vriend van y H(x, y) := x helpt y

(a) De vrienden van je vrienden zijn je vrienden. (b) Piet helpt zijn vrienden, maar alleen als ze zichzelf helpen. (c) Er is maar één persoon die geen van zijn vrienden helpt. 2. *(20 punten) De afbeelding hiernaast is een beeld van het model M = (D, I) gegeven door: D = {1, 2, 3, 4} I(P )(x, y) = “er is een pijl van x naar y” I(O)(x, y) = “x is omcirkeld”

2

1

4

3

(a) Geef aan welke van de volgende drie zinnen waar zijn in M: i. ∀x∀y((P xy ∧ Ox) → P yx) ii. ∃x∀y(¬Oy → P xy) iii. ∀x∃z¬(¬(Ox ∨ Oz) ∨ ∀y(¬P xy ∨ ¬P yz ∨ ¬P zy)) (b) Geef voor elk van de volgende formules (apart) een bedeling b zodat die formule waar is in het model M onder die bedeling: i. ∃y(¬Ox ∧ P xy ∧ ∀z(P yz → P zy)) ii. P xy ∧ P yz ∧ ¬P zy ∧ (P yy ↔ (P zx ∧ P xz)) (c) Geef een formule φ(x) die in het model M alleen waar is onder bedelingen b waarvoor geldt b(x) = 4. 3.(15 punten) Zet de volgende formules in Prenexvorm (a) ∀x(∃y(Sx → ∃x∀yRxy) → Sx) (b) ∃x∀yRxy ↔ ∀y∃xRxy

58

Oefententamens

4.*(20 punten) Test met behulp van semantische tableaus de geldigheid van de volgende gevolgtrekkingen. Geef in het geval van ongeldigheid een tegenvoorbeeld. (a) ∃x∀yRxy, ∀x(Rxx → ∀uRux) / ∃x∀y(Rxy ∧ Ryx) (b) ∃y∀x(Ay ↔ Bxy), ∀xBxx / ∀y∃x(Ay ∧ Bxy) 5.*(20 punten) (a) Geef het programma Som dat de som van twee getallen uitrekent. (b) Het programma Prod, dat het produkt van twee getallen uitrekent, wordt gegeven door de Horn-clausules: {Prod(0, x, 0)}, {Prod(Sx, y, z), ¬Prod(x, y, w), ¬Som(w, y, z)} De faculteit n! van een getal n is het produkt van de getallen 1 tot en met n, i.e. 0! = 1, n! = 1 · 2 · 3 · . . . · n Schrijf met behulp van het programma Prod een Horn-clausule programma om de faculteit van een getal te berekenen. (c) Bereken met behulp van dit programma de faculteit van 2. Vermeld hierbij alle gebruikte resoluties, clausules, substituties en hernoemingen. Je mag hierbij Som beschouwen als basispredikaat, i.e. je mag doen alsof het predikaat Som niet gedefinieerd is door de clausules van onderdeel (a), maar door de oneindige collectie clausules: {Som(0, 0, 0)}, {Som(0, 1, 1)}, {Som(0, 2, 2)}, {Som(0, 3, 3)}, . . . {Som(1, 0, 1)}, {Som(1, 1, 2)}, {Som(1, 2, 3)}, {Som(1, 3, 4)}, . . . {Som(2, 0, 2)}, {Som(2, 1, 3)}, {Som(2, 2, 4)}, {Som(2, 3, 5)}, . . . {Som(3, 0, 3)}, {Som(3, 1, 4)}, {Som(3, 2, 5)}, {Som(3, 3, 6)}, . . . .. .. .. .. .. . . . . .

+++++++


59

Logika voor AI, Toets I 14 Oktober 1997 1.(15 punten) Beschouw de volgende twee formules: F G

= ((p → ¬(¬q ∧ ¬r)) ↔ (¬p ∨ q)) = (p → (¬p ∧ ¬r))

(a) Laat met behulp van waarheidstafels zien dat F ∨ G geen tautologie is. (b) Geef een conjunctieve en een disjunctieve normaalvorm van F . (c) Geef de modellen van G. 2.(25 punten) (a) Test met behulp van semantische tableaus de geldigheid van de volgende gevolgtrekking. Geef in het geval van ongeldigheid een tegenvoorbeeld. r ↔ q, (p → q) ∨ r / p → r (b) Check met behulp van semantische tableaux of de volgende verzameling formules consistent is. Als de verzameling consistent is, geef dan een model ervoor. {(t ∧ s) ↔ (s ∨ r), (r ∧ s) → t, t → ¬s} (c) Laat het connectief ∗ gegeven zijn door de waarheidstafel p 0 0 1 1

q 0 1 0 1

p∗q 0 0 1 1

Bepaal de reductieregels voor ∗ bij semantische tableaus. (d) Bij het maken van een semantisch tableau ligt de volgorde waarin de regels toegepast worden niet vast. Beargumenteer dat desondanks het volgende geldt: Als een tableau sluit bij een bepaalde volgorde van toepassing van de regels, dan sluit dit tableau bij elke volgorde. Je mag gebruik maken van stellingen uit het boek.

60

Oefententamens

3.(20 punten) (a) Laat zien dat je in de onderstaande tabel de lege hokjes kan vullen met de formules p, q, (p ↔ p) en (p ↔ q), op zo’n manier dat de formule in elk hokje logisch equivalent is met ((de formule van de kolom)↔(de formule van de rij)). p

q

(p ↔ p)

(p ↔ q)

p q (p ↔ p) (p ↔ q) (b) Bewijs met inductie dat voor alle zinnen φ die slechts de propositieletters p en q en het connectief ↔ bevatten, geldt: φ is equivalent met één van de formules p, q, (p ↔ p) of (p ↔ q). (hint: maak gebruik van het antwoord op vraag (a)). (c) Geef een inductieve definitie van de functie G(n) gedefinieerd door G(0) = 0, G(n) =

1 1 1 + + ... + 1 2 n

4.(10 punten) De verzameling connectieven {∧, ∨, →} is niet functioneel volledig. Gebruik dit gegeven om te laten zien dat de verzameling connectieven {∧, ∨, →, ↔} ook niet functioneel volledig is. 5.(20 punten) (a) Laat met behulp van resolutie zien dat de volgende verzameling clausules niet vervulbaar is: {{p, ¬q, r}, {¬p, ¬q}, {p, ¬r}, {q, r}, {¬p, q, ¬r}} (b) Geef de verzameling clausules in accoladevorm geassociëerd met de formule (p ∨ (q ∧ r)) ∧ (q ∨ (r ∧ p)) ∧ (r ∨ (p ∧ q)) ∧ ((p ∧ q ∧ r) → s) (c) Laat met behulp van resolutie zien dat (¬s → (p ∨ q ∨ r)) en (¬s → (¬p ∨ ¬q ∨ ¬r)) gevolgen zijn van de bovenstaande formule. +++++++


61

Logika voor AI, Toets II 5 december 1997 1.(15 punten) Vertaal de onderstaande zinnen in de predikaatlogika. Geef daarbij zoveel mogelijk de logische structuur weer. Gebruik de volgende vertaalsleutel, het gegeven domein, en eventueel ‘=’: Domein := mensen Kxy := x kent y

V xyz := x stelt y aan z voor

(a) Niemand kent iedereen. (b) Als je iemand niet kent, dan stel je jezelf aan hem of haar voor. (c) Als je iemand zelf niet kent, dan stel je hem of haar niet aan iemand anders voor. 2.(20 punten) Beschouw het model M = (D, I) gegeven door het plaatje hiernaast, met D = {Kevers 1,2,3,4,5,6,7 en 8} I(L)(i, j) = Kever i zit op een lagere sport dan kever j I(S)(i, j) = Kever i zit één sport lager dan kever j

1

(a) Geef aan welke van de volgende drie zinnen waar zijn in M: i. ∃x∃y(x 6= y ∧ ¬Lxy ∧ ¬Lyx)

2

3

ii. ∀x(∃yLyx ↔ ∃y∃z(Lyx ∧ Lzy)) iii. ∃x∀y∀z(Lxy → (Lxz → ¬Syz)) (b) Geef voor elk van de volgende formules (apart) een bedeling b zodat die formule waar is in het model M onder die bedeling:

4 5

6 7

i. ¬∃y(x 6= y ∧ ¬(Lxy ∨ Lyx)) ∧ ∃ySyx. ii. ∀z((Sxz ∨ Syz) ↔ (y = z ∨ ∃w(w 6= z ∧ Syw ∧ Syz))) ∧Sxy (c) Geef een formule φ(x) die in het model M alleen waar is onder bedelingen b waarvoor geldt dat b(x) = kever 7. 3.(10 punten) Zet de volgende formules in Prenexvorm: (a) ∀x∃yRxy → ∃z(P z ∨ ∀xRxx) (b) (∀xP x ↔ ∃yQy) ∨ ∀x(P x ∧ Qx)

8

62

Oefententamens

4.(15 punten) Test met behulp van semantische tableaus de geldigheid van de volgende gevolgtrekkingen. Geef bij ongeldigheid een tegenvoorbeeld. (a) ∃x∀y(Ax ∧ By) / ∀x∃y(Ax ∧ By) (b) ∀x∃y(Ax ∧ By) / ∀xAx ∧ ∃yBy 5.(10 punten) Laat zien dat kwantoren niet altijd met elkaar van plaats verwisseld mogen worden. (hint: probeer een formule te vinden, zó dat je door verwisselen van kwantoren een niet-equivalente formule kan krijgen. Laat zien met behulp van modellen dat de verkregen formules wérkelijk niet logisch equivalent zijn) 6.(20 punten) Op het plaatje hieronder rechts vindt je een schematisch kaartje van een aantal lokaties in Amsterdam, en de (soms een-richtings-) verbindingen daartussen. Voor deze opgave nemen we aan dat men alleen in de richting van de pijltjes kan lopen. Bij het kaartje hoort het volgende Horn-clausule programma: C.S.

{Verbinding(Dam, Nieuwmarkt, 500)} {Verbinding(C.S., Nieuwmarkt, 600)} {Verbinding(C.S., Dam, 700)}

600 m

700 m

Dam

{Verbinding(Nieuwmarkt, Dam, 500)}

500 m

Nieuwmarkt 400 m

{Verbinding(Nieuwmarkt, Stopera, 400)} {Verbinding(Stopera, Faculteit, 800)}

Stopera 800 m

{Verbinding(Stopera, Mensa, 700)} {Verbinding(Faculteit, Mensa, 100)}

700 m

{Verbinding(Mensa, Faculteit, 100)} (a) Het volgende programma definieert een predikaat Bereikbaar(x,y), dat berekent of een plaats y bereikbaar is vanaf een plaats x:

Faculteit 100 m Mensa

{Bereikbaar(x, x)} {Bereikbaar(x, y), ¬Verbinding(x, w, z), ¬Bereikbaar(w, y)} Laat met behulp van dit programma met resolutie zien, dat je van de Dam naar de Mensa kan komen. Vermeld hierbij alle gebruikte resoluties, clausules, substituties en hernoemingen. (b) Schrijf een nieuw Horn-clausule programma voor het predikaat Route(x,y,z), dat berekent of er een route bestaat van x naar y van precies z meter. Je mag hierbij het predikaat SOM gebruiken. (c) Schrijf een nieuw Horn-clausule programma voor het predikaat Route2 (x,y,z), dat berekent of er een reis is van x naar y van hoogstens z meter. Je mag hierbij het predikaat Route begruiken dat je gedefinieerd hebt in de vorige opgave. Opmerking: je mag ervan uit gaan dat alle gebruikte getallen natuurlijke getallen zijn. +++++++

63


Bijlage B

Uitwerking Oefententamen Uitwerking Hertentamen Logika voor AI, 8 januari 1996, Deel I I.1. (a) De waarheidstafel van F = ((¬p → q) ∧ r) ↔ (p → (q ∧ r)): p q r ¬p → q (¬p → q) ∧ r q ∧ r p → (q ∧ r) F V1 0 0 0 0 0 0 1 0 V2 0 0 1 0 0 0 1 0 V3 0 1 0 1 0 0 1 0 1 1 1 1 1 V4 0 1 1 V5 1 0 0 1 0 0 0 1 1 1 0 0 0 V6 1 0 1 V7 1 1 0 1 0 0 0 1 V8 1 1 1 1 1 1 1 1 (b) CNV(F ): (p ∨ q ∨ r) ∧ (p ∨ q ∨ ¬r) ∧ (p ∨ ¬q ∨ r) ∧ (¬p ∨ q ∨ ¬r) DNV(F ): (¬p ∧ q ∧ r) ∨ (p ∧ ¬q ∧ ¬r) ∨ (p ∧ q ∧ ¬r) ∨ (p ∧ q ∧ r) (c) Mod(F )= {V4 , V5 , V7 , V8 } I.2. (a)

p → (r → (q ∧ s)), ¬(q → r) ◦ p → s p◦s ◦q → r q ◦r ◦p =

r → (q ∧ s) ◦ ◦r

q ∧ s◦

↑

q, s ◦ =

Het tableau heeft een open tak, dus de gevolgtrekking is niet geldig. Een tegenvoorbeeld is het model V met V (p) = V (q) = 1, V (r) = V (s) = 0.

64

Uitwerking Oefententamen

(b)

p ↔ (q ∨ r), ¬r ∨ ¬p ◦ ¬r r◦ p, q ∨ r ◦

◦ p, q ∨ r

¬r ◦ ¬p ◦ ◦r ◦p = =

◦ q, r =

Het tableau is gesloten, dus de gevolgtrekking is geldig. I.3. (a) Als we de formule (q → p) ∧ ¬(p ∨ r) ∧ (r ∨ s) ∧ (s → (p ∨ q)) omzetten in Horn-clausules krijgen we: {{p, ¬q}, {¬p}, {¬r}, {r, s}, {p, q, ¬s}} en daaruit kunnen we 2 afleiden met resolutie:

{¬p}

{r, s} {p, q, ¬s} {p, q, r} {¬r} {p, q} {p, ¬q} {p} 2

Dus de formule is niet vervulbaar. (b) Als we de formule (¬p ∨ ¬q) ∧ (¬p ∨ q) ∧ (¬q ∨ p) omzetten in Hornclausules krijgen we: {{¬p, ¬q}, {¬p, q}, {p, ¬q}} en daaruit kunnen we {¬p} en {¬q} afleiden met resolutie: {¬p, ¬q} {¬p, q} {¬p}

{¬p, ¬q} {p, ¬q} {¬q}

I.4. (a) H(φ) =‘het aantal haakjes in een formule φ’ kan inductief worden gedefinieerd met i. H(φ) = 0 als φ een propositieletter is ii. H(¬φ) = H(φ) iii. H((φ ◦ ψ)) = H(φ) + H(ψ) + 2 S(φ) =‘het aantal symbolen in een formule φ die geen haakjes zijn’ kan inductief worden gedefinieerd met i. S(φ) = 1 als φ een propositieletter is ii. S(¬φ) = S(φ) + 1 iii. S((φ ◦ ψ)) = S(φ) + S(ψ) + 1


65

(b) Voor elke formule φ geldt dat S(φ) > H(φ). Bewijs met inductie: i. Stel dat φ een propositieletter is. Dan is S(φ) = 1 > 0 = H(φ). ii. Stel dat de bewering waar is voor een formule φ, i.e. S(φ) > H(φ). Dan is S(¬φ) = S(φ) + 1 > S(φ) > H(φ) = H(¬φ). Dus dan is de bewering ook waar voor ¬φ iii. Stel dat de bewering waar is voor φ en ψ, i.e. S(φ) > H(φ) en S(ψ) > H(ψ). Dan is S(φ) ≥ H(φ) + 1 en S(ψ) ≥ H(ψ) + 1. Er volgt dat S((φ ◦ ψ)) = S(φ) + S(ψ) + 1 ≥ H(φ) + 1 + H(ψ) + 1 + 1 > H(φ) + H(ψ) + 2 = H((φ ◦ ψ)). Dus dan is de bewering ook waar voor (φ ◦ ψ). I.5. Uit de gegevens kunnen we de volgende conclusies trekken: (a) {p ∗ q, p, q} is niet consistent, dus in model V4 kan p ∗ q niet waar. (b) p ∨ q is een logisch gevolg van p ∗ q, dus in model V1 kan p ∗ q niet waar zijn. (c) q is een logisch gevolg van {p, ¬(p ∗ q)}, dus in model V3 kan p ∗ q niet onwaar zijn. (d) {q, p ∗ q} is consistent, dus er is een model waarin q waar is en p ∗ q ook. Wegens (a) is dat niet V4 , dus moet het V2 zijn. De enige mogelijke waarheidstafel van p ∗ q is dus: V1 V2 V3 V4

p q p∗q 0 0 0 0 1 1 1 0 1 1 1 0

66

Uitwerking Oefententamen

Uitwerking Hertentamen Logika voor AI, 8 januari 1996, Deel II Opmerking: Bij een aantal opgaven zijn ook andere dan de hier gegeven antwoorden mogelijk. II.1. (a) ∀x(Dx → ∃y(P y ∧ Iyx)) (b) ∃x(P x ∧ ∃y∃z(Dy ∧ Dz ∧ Ixy ∧ Ixz ∧ (y 6= z))) (c) ¬∀x((P x ∧ ¬∃y(Dy ∧ Ixy)) → N x) II.2. (a)

Zin i is waar in M1 en onwaar in M2 . Zin ii is waar in M1 en onwaar in M2 . Zin iii is onwaar in M1 en waar in M2 .

(b)

Zin i is waar in M1 onder de bedeling b met b(x) = A, b(y) = G. Zin ii is waar in M1 onder de bedeling b met b(x) = A, b(y) = C. Zin iii is waar in M1 onder de bedeling b met b(x) = E, b(y) = C.

II.3. (a) ∃x∀y∀x0 ∃y 0 ¬(Rxy ∨ ¬Ry 0 x0 ) of ∃x∀y∀x0 ∃y 0 (¬Rxy ∧ Ry 0 x0 ) (b) ∀x∃y∃y 0 ∀y 00 ∀y 000 ((Rxy ∧ Sxy 0 ) ∨ (¬Rxy 00 ∧ ¬Sxy 000 )) of ∀x∀y∃y 0 ∃y 00 ∀y 000 ((Rxy → Sxy 0 ) ∧ (Sxy 00 → Rxy 000 )) II.4. Opmerking: op een toets kan je stoppen met het uitwerken van een tableau zodra je een open tak hebt gevonden. Mocht je het tableau toch nog verder uitwerken, en meerdere open takken vinden, dan moet je duidelijk aangeven welke open tak als basis dient voor het model dat je als tegenvoorbeeld geeft. (∀xAx → ∀yBy) ◦ ∃x∀y(Ax → By)

(a)

◦ ∀xAx ◦ Ad1

∀yBy ◦ D = {d1 }

◦ ∀y(Ad1 → By) ◦

(Ad1 → Bd2 ), ∀y(Ad2 → By) D = {d1 , d2 }

Ad1 ◦ Bd2 =

†

Bd1 ◦

D = {d1 }

◦ ∀y(Ad1 → By) Bd2 ◦

(Ad1 → Bd2 ), ∀y(Ad2 → By) D = {d1 , d2 }

Ad1 ◦ Bd2 =

Het tableau is gesloten, dus de gevolgtrekking is geldig. Bij de sequent aangegeven met † wordt een element van het domein ge¨ıntroduceerd als voorgift.


(b)

67

∀x¬Rxx, ∀x∀y(Rxy → Ryx) ◦ ∀x∀y¬Rxy ◦ ∀y¬Rd1 y ◦ ¬Rd1 d2

D = {d1 } D = {d1 , d2 }

Rd1 d2 ◦ ¬Rd1 d1 , ¬Rd2 d2 ◦ ◦ Rd1 d1 ◦ Rd2 d2 ∀y(Rd1 y → Ryd1 ), ∀y(Rd2 y → Ryd2 ) ◦ (Rd1 d1 → Rd1 d1 ), (Rd1 d2 → Rd2 d1 ) ◦ (Rd2 d1 → Rd1 d2 ), (Rd2 d2 → Rd2 d2 ) ◦ ◦ Rd1 d1 ◦ Rd1 d2 =

Rd1 d1 ◦ = Rd2 d1 ◦

◦ Rd2 d1 =

Rd1 d2 ◦ ◦ Rd2 d2 Rd2 d2 ◦ =

↑

Het tableau is open, dus de gevolgtrekking is ongeldig. Uit de open tak kunnen we een tegenvoorbeeld construeren, het model M = (D, I) met D = {d1 , d2 }, I(R) = {(d1 , d2 ), (d2 , d1 )}. II.5. (a)

{¬Even(SSSS0)} {¬Oneven(x), Even(Sx)} [SSS0/x] {¬Oneven(SSS0)} {¬Even(x), Oneven(Sx)} [SS0/x] {¬Even(SS0)} {¬Oneven(x), Even(Sx)} [S0/x] {¬Oneven(S0)} {¬Even(x), Oneven(Sx)} [0/x] {¬Even(0)} {Even(0)}

2 (b) {Even(0)}, {Even(SSx), ¬Even(x)}. (c) {Oneven(S0)}, {Oneven(SSx), ¬Oneven(x)}.

Logika voor AI Werkboek

Recommend Documents