Predikaatlogica en informatica

Logica in actie H O O F D S T U K 5

Predikaatlogica en informatica Wanneer is een predikaatlogische formule waar? Om de gedachten te bepalen, beschouwen we nog eens de formule: ∀x (P(x) → ∃y (P(y) ∧ y > x)) Wanneer ‘P’ staat voor ‘is priem’, drukt deze formule uit dat er geen grootste priemgetal bestaat. Is deze formule waar? Wel, een kijkje in de getaltheorie leert dat er inderdaad geen grootste priemgetal is, en de formule zou dan dus waar zijn. Maar het is hier oppassen geblazen: deze waarheid steunt op het feit dat P staat voor de priemeigenschap, maar logisch gezien is er geen enkele reden waarom de formule zo opgevat moet worden. P kan net zo goed staan voor ‘is een prijs in de trekking van de staatsloterij van 31 december 2008’, en in die situatie zou de formule zeker niet waar zijn, want er is zeker een grootste prijs (de hoofdprijs). Met andere woorden, dat we ‘volgens de vertaalsleutel’ geneigd zouden zijn een formule waar te noemen, is een neiging die we moeten onderdrukken. Dit is in feite niet anders dan bij de propositielogica: na de vertaling van een uitspraak, keken we ook los van die vertaalsleutel naar de omstandig‐ heden waaronder een formule waar is. Maar omdat de predikaatlogica ontegenzeggelijk dichter bij de wiskunde (en bij de gewone taal, of zelfs het denken ...) staat dan de propositielogica, is het bespeurde gevaar hier zeker niet denkbeeldig. In dit hoofdstuk gaan we, wat informeel, betekenis geven aan predikaat‐ logische formules door invoering van het begrip predikaatlogisch model, en op basis daarvan analyseren we ook logisch gevolg voor redeneren met objecten, predikaten en kwantoren. Als we dat alles eenmaal begrijpen, dan kunnen we ook laten zien hoe de predikaatlogica verrassende toepassingen kent in de studie van informatie en rekenen. We kunnen er gewoon infor‐ matief taalgebruik mee beschrijven over de wereld om ons heen zoals zij is, maar zelfs ook, veel minder voor de hand liggend, het gewenste gedrag van rekenprogrammaʹs in de informatica die doelbewust toestanden van een rekenautomaat veranderen.

1

Logica in actie / Hoofdstuk 5 Predikaatlogica en informatica

5.1 Modellen voor de predikaatlogica Precies aangeven wanneer een formule waar is, is in de predikaatlogica minder eenvoudig dan in de propositielogica. Hoewel de waarheidsta‐ bellen van de connectieven nog steeds een rol spelen, kunnen we de waar‐ heidswaarden van een formule niet in een overzichtelijke tabel weergeven. Dit komt omdat anders dan in de propositielogica in de predikaatlogica de waarheidswaarde van een formule niet altijd te berekenen is uit de waar‐ heidswaarden van de deelformules. Wel kunnen we situaties aangeven waarin formules waar zijn. We illustreren dit aan de hand van een een‐ voudig geval. VOORBEELD 5.1 De figuur hierna is een graaf: een verzameling objecten, namelijk a en b, met een binaire relatie daartussen.

De atomaire formule R(a, b) is waar in een situatie als de met a en b aange‐ duide objecten in een relatie staan die met R overeenkomt. De (binaire) relatie R is met pijlen weergegeven. In dit geval is R(a, b) waar: er gaat een pijl van a naar b. Ook kunnen we kijken of samengestelde formules waar zijn in deze structuur: – ∃y R(a, y) is waar, want de keuze van b voor y voldoet. – ∀x R(x, x) is onwaar, want (a, a) behoort niet tot de pijlrelatie. – ∃y ∀x R(x, y) is waar, want neem voor y eens b, dan gaat zowel van a als van b een pijl naar b. ◊ Er is een verschil tussen de objecten a en b in de figuur, waarvan we kun‐ nen zien dat ze verschillen, en de constanten a en b in de logische taal, die best hetzelfde object zouden kunnen aanduiden. De constanten in de taal zijn de namen die we aan de objecten toekennen. (Net zoals in de propo‐ sitielogica propositieletters proposities uitdrukken, en in de predikaatlogica predikaatsymbolen predikaten aangeven.) We hadden best a en b hetzelfde object kunnen laten aanduiden. Dit zou dan net als bij pseudoniemen zijn: ‘Paul Haenen’, ‘Margreet Dolman’ en ‘Dominee Gremdaat’ zijn namen voor dezelfde persoon. In de logica zijn constanten namen voor objecten, en hetzelfde object kan met verschillende namen worden aangeduid. Met connectieven kan nog steeds gerekend worden zoals in de propositie‐ logica. Zo is in de situatie van voorbeeld 5.1 de formule R(a, b) ∧ R(b, b) waar, omdat R(a, b) en R(b, b) beide waar zijn, terwijl R(a, b) → R(b, a) onwaar is: er gaat immers wel een pijl van a naar b, maar niet eentje van b naar a. Vervolgens kunnen we kwantoren en connectieven weer in for‐ mules combineren: ∀y (∃x R(x, y) → R(y, y)) is waar in de situatie van voorbeeld 5.1, want als y = a, dan is ∃x R(x, y) onwaar en dus de implicatie

2


waar, en als y = b, dan zijn ∃x R(x, y) en R(y, y) beide waar en ook dan is de implicatie waar. Model Een situatie als in voorbeeld 5.1 heet in de logica een model. We kunnen deze notie zien als de generalisering van het begrip waardering in de propositielogica (en het is net als in de propositielogica gebruikelijk ‘model’ relatief ten opzichte van een formule, of een verzameling formules, te gebruiken: een situatie is model van een formule als de formule daarin waar is). Een model bestaat uit een verzameling objecten waarop een aantal relaties en bewerkingen zijn gegeven die overeenkomen met de predikaat‐ en functiesymbolen. Ook moeten we aangeven welk object uit de gegeven verzameling staat voor welke constante. We laten door middel van een aantal voorbeelden zien hoe modellen werken, en geven geen echte definitie. Waarheid in een Een atomaire formule zoals R(a,b) is waar in een model als, gegeven de predikaatlogisch vertaalsleutel voor a, b en R, de met R in het model corresponderende model relatie geldt tussen de in het model met a en b corresponderende objecten (en net zo voor variabele objecten x en y). Een formule ∃x ϕ is waar als er een object in het model is zodat ϕ waar is als we de voorkomens van x in ϕ over dat object laten gaan. En een formule ∀x ϕ is waar als dat voor alle objecten in het model zo is. VOORBEELD 5.2 De modellen waarin we predikaatlogica interpreteren kunnen heel abstract zijn maar ook tamelijk concreet. Beschouw bijvoorbeeld het model hierna.

Dit is eigenlijk hetzelfde model als in voorbeeld 5.1. Alleen is het linker‐ object hier Arch en het rechterobject Fonz. Maar Arch en Fonz hadden we net zo goed a en b kunnen noemen. De binaire relatie R(x, y) staat nu voor ‘persoon x kent persoon y’. De drie andere formules in voorbeeld 5.1 kunnen we nu ook een wat concretere interpretatie geven: – ∃y R(a, y): ‘Arch kent iemand’. Dit is waar, want Arch kent Fonz. – ∀x R(x, x): ‘iedereen kent zichzelf’. Dit is onwaar, want Arch kent zich‐ zelf niet, alleen Fonz kent zichzelf. – ∃y ∀x R(x, y): er is iemand die door iedereen gekend wordt. Dit is waar, want het gaat op voor Fonz. ◊ Wanneer er ook nog sprake is van een eenplaatsig predikaatsymbool P (een eigenschap), dan geven we behalve pijlen ook gebieden in het model aan (waarin de objecten liggen die de eigenschap hebben) of we markeren de punten die aan een bepaalde eigenschap voldoen afzonderlijk.

3


VOORBEELD 5.3 We gaan van een aantal formules na of ze waar of onwaar zijn in het model

hierna. Dit model verbeeldt twee objecten, een eigenschap en een relatie. Object a heeft de eigenschap P, wat we aangeven met een open rondje, en de relatie {(a, a), (a, b)} komt met R overeen.

– ∃x (P(x) ∧ R(x, x)) Dit is waar. Ken aan x a toe, dan zien we dat P(a) geldt (object a heeft de eigenschap P) en dat (a, a) ∈ R (de relatie R bestaat tussen a en zichzelf). – ∀x ∃y R(x, y) Dit is onwaar. Ken aan x b toe. Er is geen uitgaande pijl van b (er is geen pijl van b naar b, en er is ook geen pijl van b naar a). Kennelijk is ∃y R(x, y) on‐ waar als x gelijk aan b is. Het geldt dus niet voor alle x dat ∃y R(x, y) waar is. Dus ∀x ∃y R(x, y) is eveneens onwaar. – ∀x (P(x) → ∃y R(x, y)) Dit is waar. We moeten iets aantonen voor alle x. Aan x kunnen we a toe‐ kennen, maar ook b. In het eerste geval heeft het object de eigenschap P, en moeten we laten zien dat er een y is zodat R(x, y). En die is er: ken b aan y toe. In het tweede geval geldt de implicatie omdat het object de eigenschap P niet heeft: P(b) is immers onwaar. – ∀x (R(x, x) → (P(x) ∧ ∃y (R(x, y) ∧ ¬P(y)))) Dit is eveneens waar. U kunt zelf de verificatie uitvoeren. Het grappige is dat in deze vier formules a en b nergens genoemd worden, maar dat we er toch betekenis aan kunnen geven. Dit zien we vaak in de predikaatlogica. ◊ VOORBEELD 5.4 Ook in het geval van voorbeeld 5.3 kunnen we een iets beeldender inter‐ pretatie kiezen. Kijk maar eens naar figuur hierna, die verbeeldt dat: Arch heeft haar, Arch kent zichzelf, en Arch kent Fonz.

De formules van voorbeeld 5.3 zijn hier natuurlijk eveneens waar/onwaar. Voor de interpretatie kunnen we bedenken (voor ‘object’ nemen we nu gemakshalve ‘man’): – ∃x (P(x) ∧ R(x, x)) “Er is een behaarde man die zichzelf kent.” Dit is waar: Arch. – ∀x ∃y R(x, y) “Iedereen kent iemand.” Dit is onwaar. Fonz kent niemand.

4


– ∀x (P(x) → ∃y R(x, y)) “Iedere behaarde man kent iemand.” Dit is ook waar. Arch heeft haar en kent Fonz. – ∀x (R(x, x) → (P(x) ∧ ∃y (R(x, y) ∧ ¬P(y)))) “Iedereen met zelfkennis is behaard en kent een kale.” ◊ Vervulbaar Tot nu gaven we een model en bekeken dan welke formules waar waren. Soms zijn we meer in een andere vraag geïnteresseerd: gegeven een for‐ mule, verzin een model dat deze formule waar (of juist onwaar) maakt. Als dit lukt, noemen we de formule vervulbaar. Dit gaat dus net als in de pro‐ positielogica: een formule is vervulbaar als ze een model heeft. VOORBEELD 5.5 De formule ∀x ∃y R(x, y) is waar in het model van voorbeeld 5.1 en onwaar in het model van voorbeeld 5.3. Voor de formule ∀x ∀y (R(x, y) → R(x, x)) is het omgekeerde het geval: deze is onwaar in het model van voorbeeld 5.1 en waar in het model van voorbeeld 5.3. Ze is onwaar in het eerste model, want neem namelijk x = a en y = b, dan is R(a, b) → R(a, a) onwaar. Maar ze is waar in het laatste model, want neem namelijk x = a dan zijn R(a, a) → R(a, a) en R(a, b) → R(a, a) beide waar en voor x = b zijn ook R(b, a) → R(b, b) en R(b, b) → R(b, b) beide waar. Beide formules zijn dus vervulbaar. ◊ Tot nu toe hebben we het alleen over modellen voor gesloten formules gehad. Wat te doen met vrije variabelen? Anders dan voor een constante, ligt de waarde van een (vrije) variabele niet vast door het model. Om te kunnen vaststellen of de formule in zo’n geval waar is, moeten de waarden van de vrije variabelen expliciet worden aangegeven. Zo is P(x) ∧ ∃y R(x, y) waar in het model van voorbeeld 5.3 als x = a, maar onwaar als x = b. VOORBEELD 5.6 Beschouw het volgende model. Het bestaat uit de getallen 2, 3, 4, en 5 met de ‘kleiner dan’‐relatie en de priemgetaleigenschap.

De constanten 2, 3, 4, en 5 zijn gewoon door die getallen weergegeven. De eigenschap P staat voor ‘priemgetal’. Neem nu de formule x < 5 → P(x). Deze is waar als x = 3, omdat 3 < 5 en 3 een priemgetal is. De formule is daarentegen onwaar als x = 4, omdat 4 < 5 maar 4 geen priemgetal is. Maar als x = 5 is de formule waar: 5 is immers niet (echt) kleiner dan 5. Voor de waarheid van de implicatie maakt het verder niet uit dat 5 een priemgetal is. ◊ VOORBEELD 5.7 Hoewel de nadruk tot zover heeft gelegen op eindige modellen, zijn ook oneindige modellen mogelijk. De verzameling van de natuurlijke getallen ` = {0, 1, 2, 3, 4, ...} is het schoolvoorbeeld van een oneindige verzameling.

5


Vat in dit model het predikaatsymbool P op als de verzameling priem‐ getallen {2, 3, 5, 7, 11, ...}, het predikaatsymbool E als de verzameling even natuurlijke getallen {0, 2, 4, 6, 8, ...}, en de tweeplaatsige predikaatsymbolen > en ≤ als de groter‐dan‐relatie respectievelijk kleiner‐dan‐of‐gelijk‐relatie. Op dit model zijn bijvoorbeeld de volgende formules waar: ∀x (E(x) → ∃y ((y > x) ∧ E(y))) ∀x (P(x) → ∃y ((y > x) ∧ P(y))) Onwaar zijn: ∀x (E(x) ∨ P(x)) ∀x (P(x) → P(x + 2)) Het functiesymbool ‘+’ wordt hier opgevat als gewone optelling. Ten slotte zijn er nog formules waarvan de waarheid onbekend is, zoals het vermoe‐ den van Goldbach: ∀x ((E(x) ∧ x > 2) → ∃y ∃z (P(y) ∧ P(z) ∧ x = y + z)) Zoals eerder gezegd staan we in de predikaatlogische taal ook uitdrukkin‐ gen als x + y toe als term. ◊ 5.2 Predikaatlogische wetten en logisch gevolg Net als voor de propositielogica kunnen we ook voor de predikaatlogica logisch gevolg en logische equivalentie definiëren – met letterlijk dezelfde formuleringen als in hoofdstuk 3. We kunnen dan laten zien dat, bijvoor‐ beeld, alle vier de volgende formuleringen precies hetzelfde uitdrukken, namelijk dat er geen grootste priemgetal is (zie het voorbeeld aan het begin van dit hoofdstuk): ∀x (P(x) → ∃y (P(y) ∧ y > x)) ∀x ∃y (P(x) → (P(y) ∧ y > x)) ∀x ∃y (¬P(x) ∨ (P(y) ∧ y > x)) ∀x ∃y ((P(x) → P(y)) ∧ ((P(x) → y > x)) Een voorbeeld van een algemene predikaatlogische wet, die we informeel inmiddels al wel toegepast hebben, is dat ¬∃x ϕ equivalent is met ∀x ¬ϕ. Met zo’n regel, en nog een variatie erop, kunnen we ook aantonen dat ∀x ∃y x < y, voor ‘er is geen grootste getal’, logisch equivalent is met de formule ¬∃x ∀y x ≥ y ‐ we gebruiken daarin tevens dat ¬(x < y) equivalent is met x ≥ y. Met de notie van predikaatlogisch gevolg kunnen we formeel laten zien dat een eeuwenoude redenering inderdaad geldig is:

6


∀x (M(x) → S(x)), M(s) ⇒ S(s) Deze formule formaliseert de redenering ‘Alle mensen zijn sterfelijk. Socrates is een mens. Dus Socrates is sterfelijk.’ Een volgend voorbeeld van een standaard predikaatlogisch gevolg is ∃x ∀y ϕ ⇒ ∀y ∃x ϕ. Maar in de andere richting is dit nu juist ongeldig: neem bijvoorbeeld voor ϕ de atomaire formule y > x en als model de natuurlijke getallen, dan is ∀y ∃x x > y het geval want bij ieder natuurlijk getal is er nog een groter natuurlijk getal, bijvoorbeeld dat getal plus 1. Maar ∃x ∀y x > y is onwaar, want er is geen grootste natuurlijk getal. Dus ∀y ∃x ϕ ⇒ / ∃x ∀y ϕ. 5.3 Correctheidsbeweringen We besluiten dit hoofdstuk met een wellicht verrassende toepassing. Logische systemen beschrijven niet alleen onveranderlijke situaties, zoals eeuwige wiskundige structuren, maar ze zijn ook heel geschikt om verande‐ ringen te beschrijven, zowel informatieveranderingen (die in het volgende hoofdstuk aan bod komen) als feitelijke veranderingen in de wereld (waar‐ bij de waardering van atomaire beweringen telkens verschuift). Een mooi en belangrijk voorbeeld daarvan zijn rekenprocessen, waarbij geheugen‐ toestanden van een computer stapsgewijs veranderen door het uitvoeren van opeenvolgende instructies van een programmeur. Tijdens de uitvoe‐ ring van een programma kan eerst de bewering ‘x = 2’ waar zijn, en op een later moment de bewering ‘x = 3’, zodat daarmee de bewering ‘x = 2’ onwaar moet zijn geworden. Kunnen we het gedrag van een computer‐ programma systematisch onderzoeken, en is logica daarbij behulpzaam? De beschrijving van het gedrag van een programma bestaat uit stukken ‘commentaar’ dat, net als het gewone commentaar dat de programmeur toevoegt, tussen accolades wordt gezet. We illustreren dit aan de hand van zogenaamde toekenningsopdrachten. In programmeertalen als Pascal of Java komen we eenvoudige opdrachten tegen als ‘x := x + 1’. Het effect van deze opdracht is dat de waarde van x met 1 verhoogd wordt. VOORBEELD 5.8 Als x eerst 3 was, dan is de waarde van x na het uitvoeren van de opdracht x := x + 1 gelijk aan 4. We noteren dit nu als: {x = 3} x := x + 1 {x = 4}

Iets algemener: als x voor het uitvoeren van het programma de waarde a had, dan is x na afloop a + 1, kortom: {x = a} x := x + 1 {x = a + 1}

7

◊


Dit heet een correctheidsbewering; de stukken tussen de accolades worden wel specificaties genoemd: ze specificeren de toestanden van de computer. Die specificaties worden gegeven met predikaatlogische formules. Meestal doet het programma nog wel meer dan in de correctheidsbewering wordt vermeld ‐ daarin staat slechts datgene waarin we geïnteresseerd zijn. In het algemeen heeft een correctheidsbewering de vorm {ϕ} π {ψ}, waarbij ϕ en ψ formules van de predikaatlogica zijn en π (de Griekse letter ‘pi’) een pro‐ gramma is. Zo’n correctheidsbewering is dus juist, indien in alle gevallen waarin vóór het uitvoeren ϕ het geval is, het programma na uitvoeren in een toestand komt waarin ψ geldt. Wanneer het programma meerdere regels telt, zetten we de specificaties onder en boven het programma. Dit zien we in een volgend programma, waaraan we een kleine anekdote vooraf laten gaan. VOORBEELD 5.9 Stel Marie en Jan hebben op een feestje al een drankje op, Marie een whisky en Jan een berenburg. Ze lusten er nog wel eentje, maar per ongeluk verwisselt de gastheer voor het inschenken de glazen. Jan en Marie willen niet uit elkaars glas drinken. Kunnen we de inhoud van deze glazen verwisselen? Dat kan niet zonder meer, want als we de whisky bij de berenburg gieten, hebben we de drankjes vermengd, en dat was niet de bedoeling. Moeten we dan twee schone glazen pakken, of kan het met minder? Ja, het kan met slechts één extra glas: giet achtereenvolgens de whisky in het extra glas, dan de berenburg in het zojuist geleegde whisky‐ glas, en ten slotte de whisky in het lege berenburgglas. ◊ VOORBEELD 5.10 Eenzelfde truc kan bij het programmeren worden gebruikt om de waarden van twee variabelen om te wisselen: ook dan is een hulp‐variabele handig. Correctheids‐ bewering

begin z := x; x := y; y := z einde

Het uiteindelijke effect van dit programmaatje kan nu als volgt gespecificeerd worden: {x = a, y = b} begin z := x; x := y; y := z einde {x = b, y = a}

In de waarde van z zijn we niet geïnteresseerd. Aan het criterium voor een correctheidsbewering wordt voldaan: als x en y vooraf respectievelijk de

8


waarden a en b hebben, dan zijn die waarden achteraf inderdaad omgewis‐ seld. De gegeven programmaspecificatie is daarom juist en het programma de correcte implementatie van deze specificatie. ◊ We kunnen de correctheidsbewering ook stapsgewijs opbouwen, en het programma op die manier controleren. Door per regel commentaar toe te voegen, kunnen we de juistheid van de correctheidsbewering hiervoor in‐ zien. Om ruimte te besparen, schrijven we het effect van een programma‐ regel steeds achter de opdracht: {x = a, y = b} begin z := x; {x = a, y = b, z = a} x := y; {x = b, y = b, z = a} y := z {x = b, y = a, z = a} einde {x = b, y = a}

VOORBEELD 5.11 Het volgende programma heeft niet hetzelfde omwisseleffect als dat van

voorbeeld 5.10. begin x := y; y := x einde

Wat gebeurt hier namelijk: eerst wordt de nieuwe waarde van x de oude waarde van y. Daarna wordt de nieuwe waarde van y de waarde die x inmiddels heeft aangenomen. Aangezien dat al de waarde van y was, verandert de waarde van y dus niet. Bij dit programma hoort de correct‐ heidsbewering: {x = a, y = b} begin x := y; {x = b, y = b} y := x {x = b, y = b} einde {x = b, y = b}

◊ VOORBEELD 5.12 Hoewel het zeker makkelijk is een derde variabele te gebruiken om de waarden van twee andere variabelen te verwisselen, is dit strikt genomen niet nodig. Een programma dat slechts x en y als variabelen gebruikt en de waarden van x en y verwisselt is bijvoorbeeld:

9


begin x := x + y; y := x - y; x := x - y einde

Stel x = 3 en y = 5. Eerst tellen we y bij x op: 3 + 5 = 8. Daarna trekken we (nog steeds de oude waarde van) y van deze nieuwe waarde van x af: 8 – 5 = 3. Dit is de oude waarde van x, die nu de waarde van y geworden is. Ten slotte trekken we de nieuwe waarde van y (dus de oude waarde van x) van de nieuwe waarde van x af: 8 – 3 = 5. Hiermee hebben we x dus de oude waarde van y gegeven, en we zijn klaar. ◊ Dit ‘annoteren’ van programma’s zou een tamelijk zinloze hobby zijn als het slechts commentaar over het effect van een programma zou inhouden; vaak zouden we dit commentaar net zo goed of zelfs beter in gewone taal kunnen geven. Maar de belangrijkste reden voor de informaticus C.A.R. Hoare om correctheidsbeweringen op te voeren, is dat men zich zo voor eens en altijd kan vergewissen van de juistheid van een programma. Hoare heeft namelijk een methode ontwikkeld om de correctheid van een pro‐ gramma te kunnen bewijzen. In deze methode leiden we correctheids‐ beweringen van hele programma’s af door de correctheidsbeweringen van opvolgende opdrachten aan elkaar te koppelen, zoals we bij de voorbeel‐ den hiervoor al informeel hebben gedaan. Predikaatlogica en Tijdens de uitvoering van een computerprogramma speelt dus ten eerste programma‐ een rol welke beweringen over de toekenning van waarden aan variabelen correctheid op een gegeven moment waar en onwaar zijn. Dit komt overeen met het bepalen van het predikaatlogisch model voor die gegeven situatie. Net iets anders dan de modeleliminatie uit paragraaf 3.3, waarbij in iedere stap het aantal modellen werd ingeperkt, is er nu zelfs sprake van echte verandering van modellen; maar het idee van sequentiële, achtereenvolgende update is gelijkgebleven. De correctheidsbewering zelf zegt als het ware iets over de logische gevolgen van bepaalde stappen tijdens welke programmaverwer‐ king dan ook ‐ opnieuw een ons reeds bekende logische notie die in net iets andere vorm weer terugkeert. Zo zijn er verschillende manieren waarop programmacorrectheid stevig in de logica verankerd is. En eigenlijk is dat ook geen modieuze nieuwlichterij. Het samenbrengen van bewijzen en algoritmes is de moderne versie van de alleroudste traditie waarmee we dit boek begonnen: de meetkunde van Euclides, waar bewijzen en constructies van figuren hand in hand gingen. Uiteraard zijn er vele andere toepassingen van de logica in de informatica. Zo zouden we ook veel kunnen vertellen over de zogenaamde logische programmeertaal Prolog. Vanuit een abstracter gezichtspunt is een belangrijk overlappingsgebied de studie van de complexiteit van berekeningen. Hierover gaat hoofdstuk 7.

10


Samenvatting Voor het bepalen van de waarheidswaarde van een formule spelen in de predikaatlogica modellen dezelfde rol als waarderingen in de propositie‐ logica. Een model is een structuur die bestaat uit een verzameling objecten waarop relaties (en in het bijzonder: eigenschappen) zijn gedefinieerd. De relaties komen overeen met de predikaatsymbolen van de formules waar‐ aan we een waarheidswaarde willen toekennen. Objecten kennen we aan de constanten in de predikaatlogische taal toe. Verschillende constanten kunnen in een model hetzelfde object aanduiden, en een constante kan in verschillende modellen door verschillende objecten worden weergegeven. Voor variabelen kunnen we in een gegeven model verschillende waarden kiezen. Een formule ∀x ϕ is waar als ϕ geldt voor elk object dat we aan x kunnen toekennen; ∃x ϕ is waar als er ten minste één zo’n object bestaat. Wiskundige talen weerspiegelen de (abstracte) realiteit zoals zij is, en de predikaatlogica past goed bij dit ‘statische’ beeld. Maar dit systeem heeft ook een verrassend ‘dynamisch’ aspect. Een informaticatoepassing van predikaatlogica is het gebruik van correctheidsbeweringen die het effect van een programma op logische wijze omschrijven. In het stapsgewijs annoteren van programma’s met predikaatlogische formules die na zo’n gegeven stap waar zijn, zien we het idee van modeleliminatie in enigszins andere vorm als modelverandering terugkomen. Dit document bevat hoofdstuk 5 van de cursus Logica in actie. De volledige cursus is beschikbaar op http://www.spinoza.ou.nl. © Open Universiteit Nederland; Uitgeverij: Sdu Uitgevers, ’s‐Gravenhage. Dit materiaal is gelicentieerd onder een Creative Commons Licentie. Zie de licentie voor details. The content on this site is licensed under a Creative Commons Licentie. See licence for more details.

11


OPGAVE 5.1

OPGAVE 5.2

OPGAVE 5.3

Opgaven Stel we gebruiken het functiesymbool ‘–’ voor de bewerking ‘aftrekken’. Als E staat voor ‘is even’ en P voor ‘is een priemgetal’, wat drukken de volgende formules dan uit? – ∀x ((E(x) ∧ x > 2) → ∃y (P(y) ∧ P(x – y))) – ¬∃x (P(x) ∧ ∀y (P(y) → y ≤ x)) Beschouw de formule ∀x ∀y ∀z ((R(x, y) ∧ R(y, z)) → R(x, z)). – Is deze formule waar in een model met de natuurlijke getallen als objecten, waarin R overeenkomt met de gewone kleiner‐dan‐relatie (<)? – En in een model met dezelfde verzameling objecten, maar nu met de relatie D gedefinieerd door: D(x, y) precies dan als x ≤ y + 1? – Is de formule waar in het model uit voorbeeld 5.1? – Is de formule waar in elk model met precies twee objecten? Zo ja, bewijs dit, zo nee, geef een voorbeeld van een model met twee objecten waarop de formule niet waar is. Geef bij het volgende programma de specificaties die gelden na iedere op‐ dracht. Wat is de specificatie die geldt na uitvoering van dit programma en wat is de correctheidsbewering? {x = a, y = b, z = c} begin u := x; x := y; y := z; z := u einde

OPGAVE 5.4

Bewijs de correctheid van het volgende omwisselprogramma uit voorbeeld 5.12. {x = a, begin x := x y := x x := x einde {x = b,

12

y = b} + y; - y; - y y = a}


5.1

5.2

5.3

Uitwerkingen van de opgaven bij hoofdstuk 5 E staat voor ‘is even’, P voor ‘is een priemgetal’, en ‘–’ voor aftrekken. De formule ∀x ((E(x) ∧ x > 2) → ∃y (P(y) ∧ P(x – y))) drukt uit ‘voor alle even getallen x groter dan 2 is er een priemgetal y zodat x – y eveneens priem is’. Dit zegt met andere woorden dat alle even getallen groter dan twee de som zijn van twee priemgetallen: het vermoeden van Goldbach, zie voorbeeld 5.7. Het is dus niet bekend of dit waar is! De formule ¬∃x (P(x) ∧ ∀y (P(y) → y ≤ x)) drukt uit ‘er is geen priemgetal x zodat alle priemgetallen kleiner dan of gelijk zijn aan x.’ Met andere woor‐ den: er is geen grootste priemgetal. En dit is waar. Gegeven de formule ∀x ∀y ∀z ((R(x, y) ∧ R(y, z)) → R(x, z)) . – Natuurlijke getallen met R als <: ja, de formule is waar. Als k < m en m < n, dan zeker ook k < n, voor alle natuurlijke getallen k, m en n. – Natuurlijke getallen met D gedefinieerd als “D(x, y) precies dan als x ≤ y + 1”: nee, want kies maar x = 2, y = 1 en z = 0 . Dan geldt D(2, 1) en D(1, 0), maar er geldt niet D(2, 0). – Model uit voorbeeld 5.1: ja, er zijn dus zeker geen drie objecten nodig om de formule waar te laten zijn op een model! R(x, y) ∧ R(y, z) kan alleen maar waar zijn in twee gevallen: (i) x = a en y = z = b en (ii) x = y = z = b. In beide gevallen is dan ook R(x, z) waar, zodat de implicatie waar is, welke objecten we ook voor x, y en z kiezen. – Elk model met precies twee objecten? Nee, een model met twee objec‐ ten waarop de formule onwaar is, is bijvoorbeeld: Dan behoren (a, b) en (b, a) wel tot de pijlrelatie, maar (a, a) niet. Dus kiezen we voor x en z object a, en voor y object b, dan is de implicatie onwaar. We specificeren het programma regel voor regel. {x = a, y = b, z = c} begin u := x; {x = a, y = b, z = c, u = a} x := y; {x = b, y = b, z = c, u = a} y := z; {x = b, y = c, z = c, u = a} z := u {x = b, y = c, z = a, u = a} einde {x = b, y = c, z = a}

We zien hier een zogenaamde cyclische permutatie van de waarden van x, y en z.

13


5.4

Stap voor stap de specificaties uitschrijven levert onderstaande, waarmee de correctheid is aangetoond. {x = a, y = b} begin {x = a, y = b} x := x + y; {x = a + b, y = b} y := x - y; {x = a + b, y = a} x := x - y {x = b, y = a} einde {x = b, y = a}

14

Predikaatlogica en informatica

Recommend Documents