Johan van Benthem Hans van Ditmarsch Jan van Eijck. Logica in actie

Logica in actie

Johan van Benthem Hans van Ditmarsch Jan van Eijck

Logica in actie

Dit boek bevat de teksten van de cursus Logica in actie. De volledige cursus is beschikbaar op www.spinoza.ou.nl. Meer informatie over de uitgaven van Sdu Uitgevers en Academic Service kunt u verkrijgen bij: Sdu Klantenservice Postbus 20014 2500 EA Den Haag tel.: (070) 378 98 80 www.sdu.nl/service © 2009 Open Universiteit Nederland, Heerlen Uitgegeven door Sdu Uitgevers bv, Den Haag Academic Service is een imprint van Sdu Uitgevers bv 1e druk, april 2009 Zetwerk: Open Universiteit Nederland, Heerlen Omslag: Dennis Schmitz, Polka Design, Roermond ISBN: 978 90 395 2599 9 NUR: 738

Dit materiaal is gelicentieerd onder de Creative Commons Licentie Naamsvermelding-NietCommercieel-GelijkDelen 3.0. Zie de licentie voor details: http://creativecommons.org/licenses/by-nc-sa/3.0/nl/. This content is licensed under the Creative Commons License AttributionNoncommercial-Share Alike 3.0. See licence for more details: http://creativecommons.org/licenses/by-nc-sa/3.0/

Voorwoord

Een Spinozapremie geeft een vrije ruimte om nieuwe perspectieven te ontwikkelen die in een vak nog niet centraal zijn, maar het wel kunnen worden. “Logica in Actie” ging over ‘dynamische’ gezichtspunten in de moderne logica: als de wetenschap van niet alleen correct wiskundig bewijzen, of correct gebruik van taal, maar het hele scala aan informatieverwerkende activiteiten dat ons leven vormt. Het project opende daartoe twee onderzoekslijnen, Computationele Logica over nieuwe verbanden tussen logica en rekenen, en Logica en Spel, over logica als theorie van interacties tussen meerdere personen, zoals een gesprek of een debat. Misschien wel het meest interactieve dynamische proces van allemaal is onderwijs, en dus bevatte “Logica in Actie” ook een educatief project Logic Dissemination, waar Jan van Eijck, Jan Jaspars, en anderen nieuwe onderwijsmaterialen maakten met gebruik van nieuwe inzichten. Samen met Hans van Ditmarsch, een andere oude bekende uit de internationale wereld van het logica-onderwijs met elektronische hulpmiddelen, vormen zij het team achter deze cursus. Historisch gezien ontstond de logica zo’n 2500 jaar geleden in verschillende culturen, Griekenland, India, en China. In al die gevallen was de oorsprong het inzicht dat in een gewoon gesprek, openbaar debat, of juridische procedure vaste patronen zitten die we kunnen zien als geldige of ongeldige manieren om de discussie te winnen. Een geldige manier om jouw bewering A te bestrijden is er een consequentie B uit af te leiden waarvan jijzelf moet toegeven dat die onwaar is. Een ongeldige manier om jouw A te bestrijden is daarentegen de ‘drogreden’ om hem af te leiden uit een andere B, en dan die B te bestrijden. We zien in deze voorbeelden een essentiële rol voor meerdere personen die op elkaar reageren, inclusief een spelelement (debatten kun je winnen of verliezen), en een duidelijke koppeling aan praktisch redeneren zoals mensen dat doen.

v

Logica in actie

Maar de logica als wetenschap ontstond door daar nog een ander paradigma aan toe te voegen, en wel van bewuste wiskundige systeembouw. De patronen die we in het redeneren zien vormen een systeem dat op zich wiskundig beschreven kan worden. Dat aspect werd in de Griekse traditie opgemerkt, en later overgenomen en verder gebracht in de Islamitische (met name de Perzische) en onze eigen Europese cultuur. Door die belangrijke rol van de wiskunde denken veel logici, dat wiskundig redeneren eigenlijk de mooiste, meest zuivere vorm van redeneren is: de gouden standaard voor hun werk. Een wiskundig bewijs blijft geldig, hoe mensen ook in het echt redeneren - en zelfs al schreven de Verenigde Naties een wereldwijd referendum uit waarbij iedereen de bovengenoemde drogreden accepteerde, dan nog zal een logicus deze verwerpen. Bovendien zijn voor het nagaan van deze geldigheid in principe geen andere mensen nodig: wiskundige bewijzen kunnen door een computer worden gelezen, en soms zelfs gevonden. Dus hebben we nu twee sporen: één van menselijk redeneren en interactie, en een tweede met wiskundige structuur waarbij helemaal geen handelende persoon nodig is. Die twee gezichtspunten van wiskundig systeem en dialoog bepalen voor mij de logica, als twee beelden:

Links ziet u Euclides “Elementen” vol bewijs, rechts Rubens’ schilderij “De vier Filosofen” (1608, Palazzo Pitti, Florence; de vijfde persoon is overigens de buste van de filosoof Seneca) met een gesprek. Die twee gezichtspunten lijken in spanning met elkaar, en soms lijkt het zuiver wiskundige beeld te hebben gewonnen. Maar ze werkten in de geschiedenis harmonieus samen, en deze cursus brengt beide met klem naar voren. Aristoteles begon met menselijk redeneren over “alle”, “sommige” en “geen”, maar beschreef dat met een wiskundig systeem van ‘syllogismen’. De Griekse school van de Stoa bestudeerde redeneren met “niet”, “en” en

vi

Voorwoord

“of”, en het wiskundige systeem daarachter werd later ontdekt door Leibniz en Boole, die verrassende ontdekkingen deden zoals algebraïsche analogieën in redeneren tussen “en” en “of”. Dat wiskundige systeem heeft veel te maken met binair rekenen, en inderdaad zijn redeneren en rekenen al eeuwenlang nauw met elkaar verbonden, zoals u kunt lezen in het boekje “Denkende Machines” van Jan van Eijck, Jan Jaspars en Marc Pauly (verschenen bij de Amsterdam University Press), dat uit ‘Logica in Actie’ voortkwam. Beroemd is Leibniz’ ideaal van een ideale taal waarmee meningsverschillen zouden kunnen worden beslecht door zuiver rekenen, “Calculemus”. Zoals deze cursus laat zien is een simplistische reductie van dialoog tot wiskunde niet plausibel, gezien de rijkdom van verschijnselen die informatie doen stromen als mensen communiceren. Dat er wel een serieuze wiskunde van communicatie over en weer is, blijkt bijvoorbeeld uit de moderne speltheorie, waar interactief gedrag en ‘formeel systeem’ weer harmonieus samenkomen. In de 19de eeuw ontstond de moderne logica in Frege’s boek “Begriffsschift”, bedoeld als formeel instrument om de grondslagen van de wiskunde te analyseren. Dat leidde tot in de 20ste eeuw tot een stormachtige ontwikkeling van nieuwe logische begrippen en technieken, culminerend in ‘Gödel’s Stellingen’ over bewijskracht en beperkingen van formele systemen. We vatten deze historische ontwikkeling samen in vier portretten:

Aristoteles

Ibn Si’na

Frege

Gödel

Nu over de inhoud van deze cursus. Twee systemen komen overal voor in de zuivere en toegepaste logica, te weten de propositielogica en predikaatlogica, en daaraan zijn dan ook onze eerste hoofdstukken gewijd. De propositielogica bevat de kern van redeneren zoals dat wordt gedaan door digitale computers. De veel rijkere predikaatlogica is sterk genoeg om grote delen van de wiskunde, informatica, en natuurlijke taal te beschrijven. Daarmee bent u in principe ingevoerd in de denkwereld van de klassieke logica, en vanaf dit punt openen zich vele wegen. Een daarvan begaan we in deze cursus iets verder, te weten de contacten met de informatica, de wetenschap van rekenen met informatie. Op vele plaatsen blijkt hoe informatie stroomt door middel van rekenprocessen, waarbij we zelfs conversatie in onze natuurlijke taal kunnen opvatten als ‘programmeren’ van opeenvolgende informatietoestanden van betrokken personen. Verbanden tussen

vii

Logica in actie

logica, informatie ‘update’, programmeren, en complexiteit van rekenprocessen vormen dan ook een der rode draden door de tekst. Deze ‘computationele logica’ begon in de 60er jaren, en dit grensgebied met de informatica is inmiddels het grootste gebied van logisch onderzoek geworden. Een tweede, hiermee verbonden draad is de analyse van informatie op zich, waarbij ook andere aspecten spelen dan zuiver gevolgtrekken. U ziet dat de straten droog zijn, en concludeert dat het niet heeft geregend. Dat zien is ook een vorm van informatie, even belangrijk als de conclusie, en de moderne logica kan ook dat eerste exact beschrijven. Dan moeten wel andere vakgebieden meehelpen. Als illustratie hebben we een hoofdstuk opgenomen over ‘kennislogica’, een systeem dat werd voorgesteld in de filosofie, herontdekt in de economie, dat thans een belangrijke rol speelt in de informatica en kunstmatige intelligentie. Onze derde en laatste rode draad is de logische analyse van interactie, waarbij we terug gaan naar de origines van het vak. Ons laatste hoofdstuk laat zien hoe logica veel te maken heeft met speltheorie, waarbij de logische sleutelbegrippen als “en” en “of” komen te staan voor keuzes van spelers in een argumentatie, en “niet” voor een ‘rolwisseling’, het essentiële intellectuele vermogen je te kunnen verplaatsen in de situatie van een ander. Onderwijs is zelf een vorm van spel tussen leerling en leraar, en daarmee is dit een passend besluit. Deze cursus is een voorportaal. Ze introduceert een klein aantal centrale ideeën en vaardigheden, zonder enige hang naar volledigheid in thema’s en interdisciplinaire connecties. Daarmee is de actieve lezer toch enigszins toegerust voor de vele wegen die zichtbaar worden, want de logica ligt op een kruispunt van academische disciplines. Onze website (http://www.illc.uva.nl/lia/) geeft u verdere routes, naar alfa, bèta en gamma. Goede reis! Johan van Benthem

viii

INHOUDSOPGAVE Redeneren en bewijzen 1 1.1 De stelling van Pythagoras 2 1.2 De wortel uit twee is geen breuk 4 1.3 Een bewijs zonder constructie 7 1.4 Overzicht van de inhoud van het boek 8 Propositielogica, waarheid en classificeren 11 2.1 Wat is propositielogica? 12 2.2 Hoe analyseren we natuurlijke taal formeel? 13 2.3 Propositielogische formules 16 2.4 Waarheidstabellen 18 2.5 De kracht van de propositielogica 23 Wie A zegt moet B zeggen 27 3.1 Tautologie 27 3.2 Logisch gevolg 30 3.3 Van gevolgtrekking tot informatieverwerking 34 Predikaatlogica, modellen en programma’s 39 4.1 Bouwstenen van de predikaatlogica 40 4.2 Formules van de predikaatlogica 46 Predikaatlogica en informatica 51 5.1 Modellen voor de predikaatlogica 52 5.2 Predikaatlogische wetten en logisch gevolg 56 5.3 Correctheidsbeweringen 57 Kennis en communicatie 63 6.1 Taal en betekenis van de kennislogica 64 6.3 Communicatie 70 Complexiteit van berekeningen 73 7.1 Bewijzen, vervullen, evalueren en vergelijken 74 7.2 Hoe moeilijk zijn logische taken? 76 7.3 Computationale complexiteit 78 Spel en logica van interactie 83 8.1 Winnende strategieën 83 8.2 Spelen met voorkeuren 88 8.3 Strategisch evenwicht 90 8.4 Logica en spel 92 8.5 Het ultimatumspel 95 Tot besluit 99 Uitwerkingen van de opgaven 103 Register 115

ix

HOOFDSTUK 1 Redeneren en bewijzen Jan en Johan zijn net in Dunedin gearriveerd en Hans neemt ze mee naar een terrasje. “Wat willen jullie hebben?” “Koffie!” De bediening komt langs. Matt. “Two long black please and a flat white.” Dat begrijpt Matt wel, maar Jan en Johan begrijpen niet meteen waarom deze bestelling correct is. Ze concluderen dat een gewoon kopje koffie kennelijk in Nieuw-Zeeland ‘long black’ heet. Inderdaad: een ‘long black’ is een ‘short black’ met extra water. En een ‘short black’ is een espresso. Terwijl een ‘flat white’ slaat op een koffie met melk; net zo’n lokale benaming als bij ons ‘koffie verkeerd’. Matt komt terug met een dienblad waarop drie kopjes staan. “Who’s got the flat white?” Hans reageert. Daarna worden de andere twee kopjes bij Jan en Johan neergezet. “Thanks, Matt!” Bij zo’n scenario zien we al heel wat logica in actie. Hans weet dat ‘kopje koffie’ lokaal ‘long black’ heet. En dat daarom de bediening dat ook weet, en dat het niet uitmaakt dat Jan en Johan dat niet weten. Jan en Johan bestelden hetzelfde. In de bestelling komt twee keer iets van hetzelfde voor. Hieruit volgt dus, concluderen ze, dat ‘long black’ overeenkomt met het gewone kopje koffie, en ‘flat white’ niet. Matt is ook niet dom. Hij vraagt namelijk niet wie long black heeft maar wie de flat white heeft. Hij krijgt dus maar één antwoord in plaats van twee antwoorden. Voor drie personen is dat nog te overzien, maar vraag nu eens ‘who’s got the beer’ aan een tafel met tien personen; terwijl je net zo goed met die ene gin tonic had kunnen beginnen. En na Hans de flat white gegeven te hebben, kan hij de rest van de bestelling in willekeurige volgorde bij Hans’ tafelgenoten neerzetten, zonder daar verder over te hoeven nadenken. Voor Hans’ antwoord weet hij dat alle drie de gasten een long black of flat white hebben. Omdat Hans flat white heeft en er één flat white was, hebben Johan en Jan niet flat white. Uit ‘niet flat white’ en ‘long black of flat white’ volgt logisch ‘long black’. Johan en Jan hebben dus allebei een long black. Van oudsher is de logica de leer van dit soort correcte redeneringen. Nog steeds is het herkennen van correcte en incorrecte redeneringen een belangrijke doelstelling van de logica, en het beschrijven van methoden om te bewijzen dat een conclusie volgt uit een verzameling aannames. Natuurlijk speelt in ons openingsvoorbeeld veel meer dan alleen bewijzen, want er worden bijvoorbeeld ook vragen gesteld, met antwoorden die informatie overdragen. De bredere rol van de moderne logica als studie van iedere correcte vorm van informatieoverdracht zal ook volop aan bod komen in

1

Logica in actie

deze cursus, maar we beginnen in dit eerste hoofdstuk klassiek. Zelfs heel klassiek! Een exact wetenschapsgebied als de wiskunde is de beste plaats om te beginnen, omdat je daar redeneren in ‘reincultuur’ ziet. In dit eerste, inleidende, hoofdstuk geven we een aantal klassieke voorbeelden van dergelijke wiskundige bewijzen. Aan het eind van het hoofdstuk geven we een kort overzicht van de inhoud van dit boek.

1.1

De stelling van Pythagoras

Het hart van de exacte wetenschappen wordt gevormd door het begrip bewijs. De ontdekking van de methode om een onderwerp te presenteren in termen van axioma’s, definities en bewijzen is één van de grote uitvindingen van de mensheid. Het beroemdste voorbeeld van deze axiomatische methode is de systematische presentatie van meetkundige inzichten in de Elementen van Euclides, geschreven tussen 330 en 320 voor Christus. Om toegang te krijgen tot cultuurschatten zoals deze, moet je vertrouwd raken met de gebruikte manier van presenteren. Het stramien van een bewijs in Euclides’ Elementen is heel strak. Alle bewijzen beginnen met een opsomming van wat gegeven is, gevolgd door ‘te bewijzen:’, met daarna de bewering waarvan de waarheid moet worden aangetoond. Dan volgen de stappen die nodig zijn om de ‘te bewijzen’ bewering af te leiden uit wat gegeven is. Door de stappen te volgen kunt u inzien dat de ‘te bewijzen’ bewering waar moet zijn. In die bewijsstappen kunnen ook beweringen worden gebruikt die al eerder bewezen zijn. Zulke al bewezen beweringen heten stellingen. Het bewijs eindigt wanneer we zijn aangeland bij de bewering die bewezen moet worden. De laatste zin van het bewijs luidt: ‘En dat is precies wat moest worden aangetoond’. De Latijnse versie van deze afsluitende frase is quod erat demonstrandum, afgekort QED (in het Grieks stond er: οπερ εδει δειξαι). Dit is nog steeds een veelgebruikte afkorting om aan te geven dat een bewijs rond is. En als een bewijs rond is, is er een nieuwe stelling toegevoegd aan de lijst van stellingen. Zo groeit onze kennis stapje voor stapje. In plaats van QED noteren we het einde van een bewijs met een blokje: ‘ ’. Een van de stellingen die in het eerste boek van Euclides’ Elementen wordt bewezen is de stelling van Pythagoras. STELLING 1.1

2

In een rechthoekige driehoek is de som van de kwadraten van de rechthoekszijden gelijk aan het kwadraat van de schuine zijde.

Hoofdstuk 1

FIGUUR 1.1

Redeneren en bewijzen

Een bewijs van de stelling van Pythagoras in de vorm van twee plaatjes

De stelling van Pythagoras kan op veel verschillende manieren worden bewezen. Een daarvan vindt u in figuur 1.1. (Dit plaatjesbewijs is overigens niet het bewijs dat Euclides geeft.) Een bewijs van een stelling heb je wanneer je kunt laten zien waarom die stelling waar is. Hoe laten de twee plaatjes zien dat de stelling van Pythagoras waar is? Hieronder volgt het bewijs in woorden. Bewijs Figuur 1.1 bevat twee vierkanten van dezelfde grootte. Links staan er twee donkere vierkanten in, en rechts één. Noem de zijde van het kleinste vierkant links a, de zijde van het grotere vierkant links b, en de zijde van het gekantelde vierkant rechts c. Zowel links als rechts zien we viermaal een rechthoekige driehoek. Al deze driehoeken hebben als korte rechthoekszijde a, als lange rechthoekszijde b en als schuine zijde c. De oppervlakte van het vierkant in het linkerplaatje wordt gegeven door: ( a + b)2 = a 2 + 2 ab + b2 Hierbij geeft 2ab dus de oppervlakte aan van de vier driehoeken samen. Het vierkant in het rechterplaatje is even groot, maar hier wordt de oppervlakte gegeven door: c 2 + 2 ab Immers, 2ab is weer de oppervlakte van de vier driehoeken samen. Omdat de volledige vierkanten even groot zijn, volgt nu: a 2 + 2 ab + b2 = c 2 + 2 ab Dit kan worden vereenvoudigd tot: a2 + b2 = c 2 En dit laatste is precies wat moest worden aangetoond.

3

Logica in actie

1.2

De wortel uit twee is geen breuk

De oude Grieken waren dol op constructies met behulp van passer en liniaal. Meetkunde gaat over cirkels en lijnen; cirkels teken je met een passer en lijnen trek je met een liniaal. Met passer en liniaal kun je een loodlijn construeren in een punt P op een lijn l. De loodlijn moet lijn l in P snijden onder een hoek van 90 0 (een rechte hoek). De benaming ‘loodlijn’ is ontleend aan het ‘loodkoord’ waarmee een metselaar ervoor zorgt dat het muurtje dat hij aan het metselen is precies verticaal is.

FIGUUR 1.2

De passer-en-lineaalconstructie van een loodlijn

In figuur 1.2 visualiseren we de constructie. Punt P is het zwarte rondje, en de gegeven lijn l is de niet-gestippelde lijn. Eerst trekken we een willekeurige cirkel met P als middelpunt. Dit is de kleine cirkel in de figuur. Deze cirkel snijdt de lijn in twee punten. We trekken nu twee cirkels met deze snijpunten als middelpunt. Als straal van die cirkels nemen we de afstand tussen deze twee snijpunten (in feite komt dit niet zo nauw, zolang deze twee grotere cirkels elkaar maar snijden). Door de snijpunten van deze twee grotere cirkels trekken we een lijn. Dit is de loodlijn l’ op l, door P. Hoewel het liniaal van de oude Grieken geen schaalverdeling had, kunnen we wel een eenheidsmaat afspreken. We passen dan een of andere lengte af met de passer, en spreken af dat we die lengte 1 noemen. Dat is dan de afgesproken eenheidsmaat. Bij een driehoek met een rechte hoek en rechthoekszijden van lengte 1 geldt volgens de Stelling van Pythagoras dat het kwadraat van de schuine zijde gelijk is aan 2 (tweemaal de eenheidsmaat). Als we de schuine zijde x noemen, wil dit zeggen: x 2 = 2. Met passer en liniaal kunnen we nu een lijnstuk ter lengte van deze x construeren. Neem daartoe een lijnstuk AB en noem de lengte van dat lijnstuk 1. We hebben geen liniaal met schaalverdeling, maar we kunnen wel de lengte van AB als de eenheidsmaat beschouwen van een schaal die

4

Hoofdstuk 1

Redeneren en bewijzen

we zelf construeren. Noem de lijn die door A en B gaat l. Teken nu een loodlijn op l in het punt A. Bepaal met een passer een punt C op die loodlijn (zet de passer in A, neem als straal AB, en trek de cirkel; het snijpunt met de loodlijn is het gewenste punt C), op afstand 1 van A. Het lijnstuk CB heeft lengte x. Zie figuur 1.3.

FIGUUR 1.3

Het construeren van

2

Constructies met passer en liniaal zijn elementair en van een bijzondere schoonheid. De oude Grieken geloofden ook in de schoonheid van simpele verhoudingen. Als een strak gespannen snaar wordt verdeeld in stukken die zich verhouden als 1 : 2 of 2 : 3 of 3 : 4 of 4 : 5, dan zijn de tonen die je krijgt door die twee snaarstukken te tokkelen of aan te strijken in samenklank met elkaar en klinkt er een harmonisch interval (bij 1 : 2 een octaaf, bij 2 : 3 een kwint, bij 3 : 4 een kwart, bij 4 : 5 een grote terts, bij 5 : 6 een kleine terts). Dit komt omdat bij dezelfde snaardikte en snaarspanning een twee keer zo lange snaar twee keer zo langzaam trilt, maar dat wisten de Grieken nog niet. De snaarverhoudingen a : b corresponderen dus met verhoudingen van trillingsfrequenties b : a. Stapelingen geven harmonische drieklanken. Zo levert de frequentieverhouding 4 : 5 : 6 een grote tertsakkoord op. De buitenste twee tonen staan in verhouding 4 : 6 of 2 : 3, dus ze vormen een kwint, de laagste twee vormen samen een grote terts, en de hoogste twee vormen samen een kleine terts. Voor Pythagoras en zijn leerlingen, die deze verhoudingen ontdekten, illustreerde dit dat de kosmos geordend is door eenvoudige getalsverhoudingen. Alle mooie verhoudingen zijn eenvoudige breuken. Verhoudingen zijn direct verbonden met breuken. De breuken zijn alle getallen van de vorm: p q Hierin zijn p en q gehele getallen, en p is de teller en de noemer q is ongelijk aan 0. We duiden de verzameling van alle breuken aan met ¤ . Dit heet ook wel de verzameling van rationale getallen (getallen die een ratio of verhouding aangeven). We schrijven zo’n breuk ook wel als p q . Deze breuk drukt eigenlijk de verhouding p : q uit.

5

Logica in actie

Tot hun verbijstering ontdekten Griekse wiskundigen op zeker ogenblik dat sommige van de lijnstukken die je met passer en liniaal kunt construeren een lengte hebben die niet als breuk valt uit te drukken. We zagen hiervoor dat je een rechthoekige gelijkbenige driehoek met rechthoekszijde 1 en schuine zijde x, met passer en liniaal kunt construeren. Maar x is geen breuk. STELLING 1.2

Er bestaat geen breuk x met x 2 = 2. Bewijs Neem aan dat er een breuk x bestaat met x 2 = 2. Zo’n breuk heeft een teller m en een noemer n, met m en n allebei natuurlijke getallen, en de noemer n ongelijk aan 0. We mogen aannemen dat de breuk m n niet verder te vereenvoudigen is, dat wil zeggen m en n hebben geen gemeenschappelijke factoren. Preciezer: er zijn geen natuurlijke getallen k, p, q met k ≠ 1, m = kp en n = kq. De breuk 2 10 kan worden vereenvoudigd, want de teller en noemer hebben een factor 2 gemeenschappelijk. Deze breuk kan door teller en noemer door 2 te delen op haar eenvoudigste vorm worden gebracht: 1 5 . Teller en noemer hebben nu geen gemeenschappelijke factoren meer. Goed, we nemen aan dat x = m n , met m en n zonder gemeenschappelijke factoren. Dan geldt: 2

 m x2 =   = 2  n Hieruit volgt dus: 2

 m m2 2=   = 2 n  n Door beide zijden met n2 te vermenigvuldigen vinden we: 2n2 = m 2 Met andere woorden: m2 is even. Omdat kwadraten van oneven getallen altijd oneven zijn (immers, (2n + 1)2 = 4n2 + 4n + 1 is oneven) moet m even zijn. Er is dus een natuurlijk getal p met m = 2p. Invullen van 2p voor m in 2n2 = m 2 geeft nu: 2n2 = (2 p)2 = 4 p 2 Hieruit blijkt dat: n2 = 2 p 2

6

Hoofdstuk 1

Redeneren en bewijzen

En dit leidt weer tot de conclusie dat n ook even is. Maar dat betekent dat er een natuurlijk getal q is met n = 2q. Dit brengt ons in tegenspraak met de aanname dat m n een breuk is in eenvoudigste vorm: we hebben immers een gemeenschappelijke factor 2 gevonden. Hieruit volgt dat er geen breuk x is met x 2 = 2 , dat wil zeggen: de vierkantswortel uit 2 is geen breuk. De bewering die in stelling 1.2 wordt bewezen heeft de vorm van een ontkenning: het is niet zo dat de wortel uit 2 een breuk is. Die ontkenning wordt aangetoond door aan te nemen dat er wel zo’n breuk is. Een bewijs zonder constructie

1.3

We weten nu dat de wortel van twee geen rationaal getal is. Hiermee hebben we dus meteen in het algemeen aangetoond dat er rationale getallen x en y zijn, zodat x y niet rationaal is, namelijk x = 2 en y = 1 2 , want daarmee 1 volgt: 2 2 = 2 . Dus met machtsverheffen kunnen we uit de rationale getallen een irrationaal getal maken. We kunnen natuurlijk ook met machtsverheffen uit twee rationale getallen een ander rationaal getal maken, neem maar x = y = 2, dan hebben we 2 2 = 4 en 4 is rationaal. Laat r voor rationaal staan, en i voor irrationaal, dan hebben we nu r r = i en r r = r . Welke andere mogelijkheden zijn er nog? We hebben ook nog r i = r en i r = r , bijvoorbeeld 0 2 = 0 , want 0 blijft 0 verheven tot welke macht dan ook, en ( 2 )0 = 1 , want ieder getal (ongelijk 0) tot de macht 0 is 1. Zouden er twee irrationale getallen zijn die, als de een tot de macht van de ander wordt verheven, weer een rationaal getal opleveren? Dit kunnen we aantonen in wat een puur existentiebewijs wordt genoemd: we kunnen bewijzen dat die getallen moeten bestaan, alleen weten we niet wat de getallen zijn. We formuleren dat hieronder in een stelling en geven daarvan het bewijs. STELLING 1.3

Er zijn twee irrationale getallen, zodat de een tot de macht van de ander rationaal is. Bewijs We zoeken irrationale getallen x en y zodat x y rationaal is. Hieraan voldoen ofwel x= y=

2

(i)

ofwel x=

2

2

en y =

2

(ii)

7

Logica in actie

Waarom? Om te beginnen: het is duidelijk dat ( 2 ) 2 rationaal is of niet rationaal is. In het eerste geval zitten we in situatie (i). Maar zo niet, dan zitten we in situatie (ii), omdat immers geldt dat:   2 

2

  

2

=

2

2× 2

=

2

2 = 2

De getallen die we zoeken zijn dan x =

2

2

en y =

2.

Helaas vertelt dit bewijs ons niet welke van (i) of (ii) waar is. Het bewijs helpt ons niet zo’n getallenpaar te construeren. Daarom heet het een existentiebewijs. Overigens, om u niet al te onzeker te houden: in feite is (ii) het geval. Dit staat bekend als de stelling van Gelfond-Schneider, uit 1934. Bewijs en constructie gaan al sinds de Oudheid samen, maar dit oude thema is tegelijkertijd hypermodern. In de informatica hebben we niets aan zuivere existentiebewijzen, en alleen iets aan bewijzen waarmee we objecten door middel van een programma of algoritme kunnen construeren. Dat thema zal in hoofdstukken 5 en 7 meer concreet terugkomen als we zien hoe computers rekenen. En zelfs in de dagelijkse praktijk hebben we weinig aan louter een bewijs dat we morgen in Dunedin kunnen zijn zonder een expliciet plan om daar ook daadwerkelijk te komen. Een algemeen inzicht in bewijsvormen en bijbehorende constructies is dus ook relevant voor de dagelijkse praktijk van ons menselijk gedrag.

1.4

Overzicht van de inhoud van het boek

We hebben deze verschillende voorbeelden van bewijzen gegeven om te illustreren dat precisering en formalisering van redeneringen een heel belangrijke rol spelen in de wetenschap, en al sinds de oudheid met name in de wiskunde en in de wijsbegeerte. Een belangrijke traditionele rol van de logica is om wiskundige bewijsvoering precisie te geven, en om filosofische begripsvorming te ondersteunen. Tevens zijn er vele dwarsverbanden met recente wetenschaps- en toepassingsgebieden zoals de theoretische informatica en de kunstmatige intelligentie, en de laatste jaren ook de speltheorie en cognitiewetenschap. Deze breedte is niet toevallig. Het werkterrein van de logica is niet beperkt tot de wetenschap, want ook ons gewone gedrag wordt voortdurend gestuurd door redeneren. En al maken we dan soms fouten, dat alledaagse redeneervermogen is historisch-evolutionair de oorspronkelijke bron van ons wetenschappelijk denken. Dit boek loopt dan ook van het meest verheven wiskundig bewijzen tot het meest alledaagse redeneren, en in feite tot informatieoverdracht van elke soort. Daarmee is

8

Hoofdstuk 1

Redeneren en bewijzen

de logica een ideaal ‘uitkijkpunt’ om verbanden te zien tussen allerlei disciplines die vaak als gescheiden werelden worden beschouwd. Wel blijft een feit dat de wiskunde een speciale rol speelt, zelfs in de brede visie op logica die u zult vinden in dit boek. Het gaat dan niet om het terrein van studie op zich, maar om de methode waarmee we dat doen. Logici hebben in de loop van de geschiedenis geleerd dat het bijzonder goed werkt om stukjes redeneerpraktijk en informatiepraktijk als wiskundig systeem te definiëren, en dan verder te ontwikkelen. In de volgende twee hoofdstukken, ‘Hoofdstuk 2, Propositielogica, waarheid en classificeren’ en ‘Hoofdstuk 3, Wie A zegt moet B zeggen’, behandelen we de logica van beweringen op zinsniveau en hun onderlinge logische verbanden. Dit is de propositielogica waarin we redeneringen kunnen formaliseren zoals ‘als bewering p het geval is en als bewering p → q (p impliceert q) waar is, dan is q ook waar’. We onderzoeken ook propositielogische beweringen als p ∨ ¬p (p of niet-p) die altijd waar zijn. In de twee daaropvolgende hoofdstukken, ‘Hoofdstuk 4, Predikaatlogica, modellen en programma’s’ en ‘Hoofdstuk 5, Predikaatlogica en informatica’, behandelen we de predikaatlogica. Dit is de logica waarin beroemde redeneringen als “Alle mensen zijn sterfelijk. Socrates is een mens. Dus: Socrates is sterfelijk.” geformaliseerd kunnen worden. We kunnen deze logica zien als een uitbreiding van de propositielogica, namelijk als een logica waarin beweringen op zinsniveau ook nog aanvullende structuur hebben: als de zin ‘Jan is de vader van Emma’ is, dan zouden we hier in propositielogica p voor kunnen schrijven, maar in predikaatlogica P(j, e), waarbij P voor ‘vader zijn van’ staat, j voor Jan, en e voor Emma. Meer structuur, dus. Deze structuur blijkt zowel getrouwer aan de natuurlijke taal waarmee wij communiceren als aan de beschrijving van meer technische verschijnselen, zoals de rekenprocessen van een computer. Na het hoofdstuk over predikaatlogica komt een hoofdstuk over de logica van kennis, ‘Hoofdstuk 6, Kennis en communicatie’. Deze logica is ook te zien als een uitbreiding van de propositielogica, maar een heel ander soort uitbreiding dan de predikaatlogica. De laatste twee hoofdstukken behandelen een aantal nogal ‘moderne’ onderwerpen in de logica: ‘Hoofdstuk 7, Complexiteit van berekeningen’ laat zien hoe ‘lang’ berekeningen bij programmeren en bij logische taken kunnen duren. Dit weerspiegelt een belangrijk algemeen thema in vele wetenschappen, van de natuurkunde tot de taalkunde: hoe kunnen wij de in principe aanwezige informatie om ons heen ook werkelijk bevatten en verwerken? ‘Hoofdstuk 8, Spel en logica van interactie’ gaat over een ander fundamenteel modern thema, te weten wisselwerking tussen meerdere personen. De klassieke logica richtte zich op eenzame denkers die conclusie na conclusie trekken. Maar net zoals de natuurkunde pas echt tot haar recht komt als we ‘meerlichamenproblemen’ aanpakken, met onderlinge wisselwerking van deeltjes, geldt dat ook voor ons eigen intelligente gedrag. ‘Logica in actie’

9

Logica in actie

zie je op zijn best als mensen communiceren, argumenteren, en strategisch op elkaar ingaan. Het wiskundige model bij uitstek voor deze ‘meergeestenproblemen’ is het spel. We leggen uit dat het spelen van spelletjes op heel serieuze manier bedreven kan worden, zowel binnen de economie als binnen de logica. We besluiten dit boek met een kort afrondend hoofdstuk, waarin een terugblik is opgenomen en een overzicht in vogelvlucht van enkele logische vakgebieden.

10

HOOFDSTUK 2 Propositielogica, waarheid en classificeren We hebben al gezien dat voor een logicus het verhevene heel dicht kan liggen bij het alledaagse. Misschien beter gezegd: een logicus ziet het verhevene in het alledaagse ... Om een aantal logische kernbegrippen uit te leggen gaan we nu terug van bewijzen in de wiskunde naar een meer elementair niveau van correct redeneren. Waarom is de ene redenering correct en de andere niet? Een eenvoudig voorbeeld van een correcte redenering is: ‘De afstandsbediening is kapot of de tv werkt niet goed. Maar de tv werkt wel goed. Dus de afstandsbediening is kapot.’ Daarentegen is de volgende redenering niet correct. ‘Het schilderij hangt hier niet als het gestolen is. Het schilderij hangt hier niet. Dus is het gestolen.’ Waarin zit nu het verschil? Beide redeneringen bestaan uit een conclusie (‘Dus ...’), voorafgegaan door twee Nederlandse zinnen, dus daar zit het niet in. Maar bij de eerste redenering moet de conclusie (‘Dus ...’) wel juist zijn als de uitgangspunten (de beide voorafgaande zinnen) waar zijn. Met andere woorden: er lijkt geen situatie te verzinnen waarin de eerste twee zinnen waar zijn en de derde niet. Bij de tweede redenering ligt dit heel anders. De beide uitgangspunten kunnen hier heel goed waar zijn zonder dat de vermeende conclusie dat is, denk maar aan een situatie waarin het schilderij net gerestaureerd wordt. Dan hangt het er inderdaad niet en we kunnen nog steeds beamen dat het er ook niet hangt als het gestolen is. Maar het is helemaal niet gestolen, het wordt immers gerestaureerd. Bij voorgaande voorbeeldredeneringen ziet u misschien meteen al of ze correct zijn of niet. Voor meer ingewikkelde betogen hoeft dat helemaal niet zo simpel te zijn. En zelfs al zouden we voor iedere concrete redenering kunnen beargumenteren of die al dan niet correct is, dan blijft dat een moeizame onderneming. Bovendien: wie zegt ons dat die argumentatie weer correct is? Daarom is het beter eerst een andere weg in te slaan: welke kenmerken van de zinnen zorgen er nu voor dat een redenering correct is? Allereerst kunnen we opmerken dat de eerste redenering dezelfde vorm (maar een heel andere inhoud) heeft als de volgende, die ook correct is:

11

Logica in actie

‘Onze export stagneert of de dollar staat niet hoog. De dollar staat echter wel hoog. Dus stagneert onze export.’ Kennelijk zijn het vooral de woordjes ‘of’ en ‘niet’ en de plaats waar ze voorkomen, die bepalen dat deze redenering correct is - van de rest mogen we abstraheren. We stuiten hier echter op een ander probleem: wil een redenering correct zijn, dan moet ze in elke situatie juist zijn, maar woordjes als ‘of’ betekenen niet steeds hetzelfde. Bij het eerste voorbeeld zal een monteur die de uitspraak ‘De afstandsbediening is kapot of de tv werkt niet goed’ doet, waarschijnlijk bij de diagnose rekening houden met de mogelijkheid dat zowel afstandsbediening als tv kapot kunnen zijn, terwijl een beursanalist die ‘Onze export stagneert of de dollar staat niet hoog’ bezigt, vermoedelijk bedoelt dat ofwel onze export stagneert, ofwel de dollar niet hoog staat, maar niet allebei. En ouders die tegen hun kinderen zeggen ‘Voor je 18de verjaardag krijg je een racefiets of een serie autorijlessen’ zullen wel nooit bedoelen dat ze dat ook beide zullen krijgen. Kortom, willen we iets definitiefs kunnen zeggen over de correctheid van redeneringen, dan zullen we een logisch ‘of’ moeten maken dat aanzienlijk preciezer is dan het vage en dubbelzinnige woordje uit de gewone taal. Dit kan in een eenvoudige, maar precieze en compacte logische taal: die van de propositielogica.

2.1 Propositie

Wat is propositielogica?

Een propositie is een uitspraak die waar of onwaar kan zijn. Voorbeelden zijn ware uitspraken als ‘Er is geen grootste priemgetal’ en onware als ‘Kopenhagen ligt in Nederland’. Afgezien van filosofische spitsvondigheden (hoe kunnen we bewijzen dat Kopenhagen niet in Nederland ligt?), is het waarheidsgehalte van deze proposities onomstreden. Bij minder algemene uitspraken speelt de context vrijwel altijd een rol. Of ‘Het regent’ waar is, hangt duidelijk af van de situatie waarin we ons bevinden. Toch noemen we ook ‘Het regent’ een propositie, want het is in elke situatie óf waar óf onwaar. Dat is zelfs het geval als we niet in staat zijn het waarheidsgehalte van een uitspraak hier en nu te bepalen. ‘Het regent morgen’, ‘De snel stijgende olieprijzen zijn de oorzaak van de crisis’ en ‘Er bestaan zwarte gaten’ zijn dus wel degelijk proposities. Waar het om gaat, is dat deze uitspraken in elke situatie waar of onwaar zijn, en niet zowel waar als onwaar. Als de enige eis aan proposities is dat ze in iedere omstandigheid een waarheidswaarde (waar of onwaar) moeten hebben, dan lijkt dit zo algemeen dat we ons kunnen afvragen wat dan in hemelsnaam géén proposities zijn. Andere zinstypen zoals vraagzinnen en zinnen in de gebiedende wijs druk-

12

Hoofdstuk 2

Propositielogica, waarheid en classificeren

ken in de regel geen propositie uit. De volgende voorbeelden, twee gewone zinnen, een wiskundig probleem en een programmaopdracht, zijn geen proposities: – – – –

Hoe laat is het? Kijk uit bij het oversteken! Zijn er natuurlijke getallen x, y, z, n met n > 2 waarvoor xn + y n = zn ? Als x > 0 , dan x := x + 1.

Bij vragen kunnen de antwoorden wel waar of onwaar zijn, maar de vragen zelf niet. Het laatste voorbeeld is misschien wel verrassend: de vorm lijkt immers veel op die van een gewone als-dan-uitspraak. Maar voor een programmaopdracht geldt niet dat die waar of onwaar is. Een programmaopdracht is een instructie om de computer iets te laten doen, en als zodanig vergelijkbaar met de gewone gebiedende wijs (‘Doe ...!’). De voorwaarde van een als-dan-opdracht is wél een propositie, en de instructie na ‘dan’ wordt alleen uitgevoerd als de voorwaarde waar is. Dit betekent dat wanneer deze opdracht deel uitmaakt van een ‘lus’ in het programma, de waarheidswaarde tijdens de uitvoering van het programma kan veranderen - dat is juist de bedoeling van de voorwaarde. Uiteindelijk heeft de moderne logica iets te zeggen over al deze genres, maar we beginnen bij de bron: waarheidsdragende zinnen. Het is niet de taak van de logica om de werkelijkheid te bestuderen en zo de waarheidswaarde van een propositie in een bepaalde situatie te achterhalen, zo dit al mogelijk is. De logica houdt zich ermee bezig of de waarheidswaarde is af te leiden uit die van andere proposities. Kenmerkend voor de propositielogica is dat de waarheidswaarde van een uitspraak is af te leiden uit de waarheidswaarden van haar delen. Met een mooi woord wordt de propositielogica daarom wel waarheidsfunctioneel genoemd.

2.2

Hoe analyseren we natuurlijke taal formeel?

In de propositielogica kunnen we uitspraken analyseren die zijn opgebouwd met behulp van het woordje niet en voegwoorden (en, of, als, mits, ...). In het begin van dit hoofdstuk zagen we daarvan al diverse voorbeelden (de woorden waar het hier om gaat zijn gecursiveerd): De afstandsbediening is kapot of de tv werkt niet goed. Het schilderij hangt hier niet als het gestolen is. Zoals gezegd is de taal van alledag echter vaak dubbelzinnig en te vaag om dergelijke proposities goed mee te analyseren. We vervangen woordjes zoals ‘niet’ en ‘of’ daarom door symbolen die we een heel precieze betekenis gaan geven.

13

Logica in actie

Negatie

In plaats van ‘Het schilderij hangt hier niet.’ schrijven we: ¬ Het schilderij hangt hier. Het symbool ¬ (het logische ‘niet’) gaat anders dan het ‘niet’ in gewone taal vooraf aan de uitspraak waar het betrekking op heeft. De propositie ‘Het schilderij hangt hier’ korten we vervolgens af tot de letter p, zodat we ten slotte uitkomen op de uitdrukking ¬p. Het symbool ¬ noemen we het negatieteken. De uitdrukking ¬p noemen we de negatie van p.

Disjunctie

In plaats van: ‘De afstandsbediening is kapot of de tv werkt niet goed.’ schrijven we: De afstandsbediening is kapot ∨ ¬ de tv werkt goed. Het symbool ∨ (het logische ‘of’) staat hier op de plaats waar het gewone ‘of’ ook staat. De overgebleven uitspraken ‘De afstandsbediening is kapot’ en ‘De tv werkt goed’ korten we af tot respectievelijk p en q, zodat we ten slotte uitkomen op p ∨ ¬q. Het symbool ∨ is de schreefloze letter ‘v’, afkomstig van het Latijnse woord ‘vel’ voor ‘of’. Het symbool ∨ wordt het disjunctieteken genoemd. Door ∨ worden twee proposities verbonden: het resultaat (zoals p ∨ ¬q) heet een disjunctie en de proposities die door ∨ verbonden worden (zoals p en ¬q in p ∨ ¬q), heten disjuncten. Hierna zullen we zien dat we met ∨ de zogenaamde inclusieve disjunctie op het oog hebben: p ∨ q is dan ook het geval als zowel p als q het geval zijn.

Conjunctie

De uitspraak ‘Gabriela tennist en Judith schaakt’ kan in propositielogica worden weergegeven door p ∧ q, waarbij p staat voor ‘Gabriela tennist’ en q voor ‘Judith schaakt’. Keren we het disjunctieteken om, dan krijgen we ∧, het logische ‘en’. Het symbool ∧ wordt het conjunctieteken genoemd. Door ∧ worden twee proposities verbonden: het resultaat (zoals p ∧ q hiervoor) heet een conjunctie en de proposities die door ∧ verbonden worden, heten conjuncten. Het ‘en’ uit de gewone taal bevat eigenaardigheden die we niet in de propositielogica willen opnemen. Zo betekent ‘Ze kwam binnen en ze deed het licht uit’ iets anders dan ‘Ze deed het licht uit en ze kwam binnen’. Het ‘en’ uit de gewone taal betekent vaak dat de gebeurtenis uit de tweede zinshelft later plaatsvindt dan die uit de eerste zinshelft. Dat soort bijzonderheden kunnen we niet uitdrukken in de propositielogica.

14

Hoofdstuk 2

Implicatie

Propositielogica, waarheid en classificeren

De uitspraak ‘Als er stroom loopt, (dan) wordt de draad warm’ kan in propositielogica worden weergegeven als p → q, waarbij p staat voor ‘Er loopt stroom’ en q voor ‘De draad wordt warm’. Het symbool → wordt het implicatieteken genoemd. Door → worden twee proposities verbonden: het resultaat (zoals p → q hiervoor) heet een implicatie.

Equivalentie

De uitspraak ‘A ⊂ B desda A ∩ B = A’ wordt in propositielogica weergegeven als p ↔ q, waarin p staat voor ‘A ⊂ B’ en q voor ‘A ∩ B = A’. De afkorting ‘desda’ staat voor ‘dan en slechts dan’, een standaardterm in wiskundige bewijzen. Het symbool ↔ wordt het equivalentieteken genoemd. Door ↔ worden twee proposities verbonden: het resultaat (zoals p ↔ q hiervoor) noemen we een equivalentie. De speciale symbolen van de propositielogica (¬, ∧, ∨, →, ↔) worden connectieven (logische voegwoorden) genoemd. In de volgende tabel vatten we de schrijfwijze, de uitspraak en de naam van de connectieven samen. Er zijn ook andere notaties in omloop, zoals de u misschien wel bekende & voor ∧, en ⊃ voor →, maar de symbolen in de tabel zijn het meest gangbaar. TABEL 2.1

Connectieven in de propositielogica

connectief

uitspraak

naam

¬ ∧ ∨ → ↔

niet en of als ..., (dan) desda

negatieteken conjunctieteken disjunctieteken implicatieteken equivalentieteken

Naast de connectieven bevatten de uitdrukkingen van de propositielogica letters en haakjes. De letters geven (niet verder deelbare) proposities aan, en heten daarom propositieletters. We gebruiken hier meestal de letters p, q, r, ... voor, soms vergezeld van een index ( p1 , q7 , ...). Bij de vertaling van concrete uitspraken uit de wiskunde of de gewone taal in propositielogica moeten we wel steeds aangeven welke propositieletter bij welke propositie hoort. Daarnaast zijn er haakjes nodig, omdat anders bijvoorbeeld p ∨ ¬q ∧ p op meerdere manieren gelezen zou kunnen worden, en dat willen we natuurlijk niet. Met haakjes erbij hebben we dit probleem niet: p ∨ (¬q ∧ p) en (p ∨ ¬q) ∧ p zijn wel goede uitdrukkingen. Misschien denkt u dat ook ¬p ∨ q geen goede uitdrukking is, maar hier werkt een spelregel die zegt dat negatietekens sterker binden dan de overige connectieven, net zoals in de gewone rekenkunde machtsverheffen voorafgaat aan de overige

15

Logica in actie

bewerkingen. Dus als we toch haakjes hadden willen zetten, dan bedoelden we met ¬p ∨ q alleen (¬p) ∨ q en niet ¬(p ∨ q).

2.3

Propositielogische formules

Wiskundigen voeren vaak notaties in die worden toegevoegd aan gewone natuurlijke taal, zodat een soort technisch jargon ontstaan, net zoals in onze eerdere voorbeelden van taal met symbolen. Logici gaan meestal nog een stapje verder, en introduceren geheel ‘formele talen’ die op zichzelf bestudeerd kunnen worden. Voor de propositielogica werkt dit als volgt. Logica en grammatica

De formules p ∨ ¬q en q → ¬p zijn correct opgebouwd, maar een uitdrukking als p ∨ ¬q ∧ p was dat niet. Ook allerlei onzinrijtjes als p ∨ ¬ en pq willen we uitsluiten. De verzameling formules van de propositielogica kan formeel worden gedefinieerd in een zogenaamde inductieve definitie. Daarmee kunnen we dan precies uit elkaar houden wat wel en wat niet correcte formules zijn.

Inductieve definitie

Een inductieve definitie is een manier om een verzameling objecten te construeren uit een aantal bouwstenen of basiselementen. Zo’n inductieve definitie bestaat uit drie onderdelen: basisstap, inductiestap, afsluitende stap. Eerst moeten we in zo’n definitie aangeven wat de eenvoudigste elementen uit de verzameling zijn. Dit noemen we de basisstap van de inductieve definitie. Daarnaast moeten we aangeven hoe we uit sommige elementen andere kunnen construeren. Dit heet de inductiestap. De truc van een inductieve definitie is dat die ‘sommige elementen’ niet per sé basiselementen hoeven te zijn! We kunnen bijvoorbeeld de verzameling van de natuurlijke getallen met zo’n inductieve definitie definiëren. Dit gaat als volgt: 0 is een natuurlijk getal. Als n een natuurlijk getal is, dan is n + 1 ook een natuurlijk getal. Hoe zien we nu in dat, bijvoorbeeld, 3 een natuurlijk getal is? Eerst moeten we 3 schrijven als 1 + 1 + 1. Dit mag: we beschouwen ‘3’ gewoon als de afkorting van 1 + 1 + 1. Dan redeneren we als volgt: 1 + 1 + 1 is een natuurlijk getal, als 1 + 1 een natuurlijk getal is (een ‘+ 1’ minder); 1 + 1 is een natuurlijk getal als 1 een natuurlijk getal is (nog een ‘+ 1’ minder); 1 is een natuurlijk getal als 0 een natuurlijk getal is (nog een ‘+ 1’ minder, en voor 0 + 1 schrijven we 1). En ja hoor, 0 is een natuurlijk getal want dat hebben we net afgesproken! Dus 3 is ook een natuurlijk getal. De afsluitende stap ten slotte zegt dat ‘niets anders dan wat met de basisstap en de inductiestap geconstrueerd kan worden in de verzameling zit’.

Formules

De verzameling formules van de propositielogica kan worden vastgelegd in zo’n inductieve definitie: we weten wat de eenvoudigste formules zijn (de propositieletters) en hoe we van formules naar ingewikkelder formules kunnen komen (door formules middels connectieven te verbinden).

16

Hoofdstuk 2

Propositielogica, waarheid en classificeren

In de volgende definitie gebruiken we naast propositieletters (p, q, r, ... ), connectieven (¬, ∧, ...) en haakjes ook de Griekse letters ϕ (fi) en ψ (psi). Deze Griekse letters duiden willekeurige formules aan, ook wel formulevariabelen genoemd. DEFINITIE 2.1

Formules van de propositielogica – Elke propositieletter (p, q, r, ...) is een formule. – Als ϕ een formule is, dan is ¬ϕ ook een formule. – Als ϕ en ψ formules zijn, dan zijn (ϕ ∧ ψ) , (ϕ ∨ ψ) , (ϕ → ψ) en (ϕ ↔ ψ) ook formules. – Er zijn geen andere formules. De eerste regel uit de definitie is de basis, de tweede en derde zijn de inductiestappen en in de laatste regel wordt de uitsluiting geformuleerd. Alle formules die geen losse propositieletters zijn, zijn samengestelde formules. Als we goed naar de definitie kijken, zien we dat eerdere formules zoals p ∨ ¬q eigenlijk niet helemaal correct zijn: er had (p ∨ ¬q) moeten staan. Haakjes die helemaal aan de buitenkant van de formule staan en bij elkaar horen, worden meestal weggelaten. De rol van haakjes is namelijk om ambigue interpretatie van rijtjes symbolen uit te sluiten. In dit geval is geen verwarring mogelijk.

VOORBEELD 2.1

Van de volgende rijtjes symbolen zijn de linker allemaal formules en de rechter geen formules: q ¬p q∧q p → (q ∨ ¬p) ¬¬(p ∨ (q ↔ ¬(p ∧ q)))

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

◊

Het wybertje ‘◊’ in de rechterkantlijn geeft het einde van het voorbeeld aan. Deelformule

Als we nog eens kijken hoe een formule volgens de definitie is opgebouwd, dan zien we hoe hiervoor eerst andere formules moeten worden gemaakt. Al deze formules treden op in de uiteindelijk geproduceerde formules, en om die reden worden ze deelformules genoemd (een andere gangbare term hiervoor is subformules). Bijvoorbeeld, de vijf deelformules van de formule (p ∧ q) → r zijn: p, q, r, p ∧ q, en (p ∧ q) → r. Een formule is dus ook een deelformule van zichzelf.

17

Logica in actie

De formulering ‘Een deelformule van een formule ϕ is een stuk (een deelrijtje) van ϕ dat zelf een formule is’ is niet juist. Bijvoorbeeld, de formule p ∨ q is een deelrijtje van de formule ¬p ∨ q, maar geen deelformule van ¬p ∨ q. Bereik van een connectief

Een ander begrip dat direct ontleend kan worden aan de definitie van formules, is het bereik van een connectief. Het bereik van een connectief bestaat uit het deel (of de delen) van de formule waar het connectief betrekking op heeft. Bijvoorbeeld, het bereik van ∧ in r ∨ (¬q ∧ p) bestaat uit de formules ¬q en p, en het bereik van ∨ bestaat uit de formules r en ¬q ∧ p.

2.4

Waarheidstabellen

In de vorige paragraaf hebben we de vorm van de propositielogische formules bekeken, nu gaan we hun betekenis onderzoeken. Net als voor de zinnen in de gewone taal is die betekenis voor logische formules gelegen in de waarheidswaarde: we weten wat een formule betekent als we kunnen zeggen in welke situaties de formule waar is. Maar hoe wordt de waarheidswaarde van een formule nu berekend? Om vlot met waarheidswaarden te kunnen rekenen, is het handig ‘waar’ weer te geven door 1 en ‘onwaar’ door 0, net als in digitale computers, waarvan de bits ook met nullen en enen worden voorgesteld. De berekening van de waarheidswaarde van samengestelde formules vindt plaats in de vorm van tabellen, de zogenaamde waarheidstabellen. We laten nu de connectieven één voor één de revue passeren om hun effect op de waarheidswaarde vast te stellen. Negatie

De formule ¬p is waar wanneer p onwaar is, en omgekeerd. Omdat proposities óf waar óf onwaar zijn, volgt hier meteen uit wanneer ¬p onwaar is: als p waar is. We vatten dit samen in de volgende waarheidstabel. p

¬p

1 0

0 1

Dit gedrag van de negatie vertoont grote overeenkomst met dat van het woordje ‘niet’ in de gewone taal. ‘Het regent niet’ is immers precies dan waar als ‘Het regent’ onwaar is. Voor de logische negatie geldt hetzelfde, en dat blijft zo als we de negatie voor een samengestelde formule zetten. Meer in het algemeen is dus voor een willekeurige ϕ de formule ¬ϕ waar precies dan als ϕ onwaar is.

18

Hoofdstuk 2

Propositielogica, waarheid en classificeren

Hierdoor krijgt de waarheidstabel voor negatie de volgende vorm:

VOORBEELD 2.2

ϕ

¬ϕ

1 0

0 1

Met de waarheidstabel van de negatie kunnen we de waarheidswaarden van sommige samengestelde formules uitrekenen. De waarheidstabel voor de formule ¬¬p is: p

¬p

¬¬p

1 0

0 1

1 0

Deze tabel komt als volgt tot stand. De waarheidswaarde van ¬¬p wordt bepaald door de waarheidswaarde van p: we zetten p linksboven in de tabel. Nu kan p waar of onwaar zijn: deze waarden zetten we in de linkerkolom onder p. Vervolgens berekenen we de waarheidswaarden van de deelformule ¬p. De waarheidstabel voor ¬ leert dat ¬p waarheidswaarde 0 (onwaar) heeft als p waarheidswaarde 1 heeft, en 1 (waar) als p waarheidswaarde 0 heeft. Deze waarden schrijven we in de middelste kolom, onder ¬p. Ten slotte verkrijgen we hieruit, weer met de waarheidstabel voor negatie, de waarheidswaarden van de hele formule, nu in de rechterkolom. ◊ Conjunctie

De formule p ∧ q is alleen waar als zowel p als q waar zijn. Algemener: een conjunctie ϕ ∧ ψ is waar als zowel ϕ als ψ waar zijn, en in alle andere gevallen onwaar. Dit wordt weergegeven door de volgende waarheidstabel (ϕ en ψ zijn weer willekeurige formules): ϕ

ψ

ϕ∧ψ

1 1 0 0

1 0 1 0

1 0 0 0

In gewone taal heeft ‘en’ vaak een vergelijkbaar effect. ‘Marie werkt en Kees zorgt voor de kinderen’ is waar als ‘Marie werkt’ en ‘Kees zorgt voor de kinderen’ beide waar zijn, en ook alleen dan waar.

19

Logica in actie

VOORBEELD 2.3

Hoe vinden we nu met behulp van de waarheidstabel van ∧ de waarheidstabel voor een ingewikkelder formule als, zeg, p ∧ ¬q? De formule p ∧ ¬q bevat twee verschillende propositieletters, p en q: die zetten we weer linksboven in de tabel. Elk van die propositieletters kan twee waarheidswaarden krijgen, dus er zijn in totaal 2 × 2 = 4 combinaties van waarheidswaarden mogelijk. Hierdoor krijgen we een tabel met vier rijen van waarheidswaarden. Voor elke deelformule gaan we nu de waarheidswaarde berekenen, te beginnen met de kleinste deelformules. Dat zijn de propositieletters, waarvan we de waarheidswaarden al kennen. Daarna komt de deelformule ¬q. Dat komt neer op het ‘omdraaien’ van de waarheidswaarde van q. Ten slotte vinden we de waarheidswaarden van de hele formule door (rij voor rij) de waarheidswaarden die onder p en onder ¬q staan te combineren, met behulp van de waarheidstabel van ∧. De waarheidstabel voor p ∧ ¬q wordt dus: p

q

¬q

p ∧ ¬q

1 1 0 0

1 0 1 0

0 1 0 1

0 1 0 0

Het resultaat is dat p ∧ ¬q waar is als p waar en q onwaar is. In alle andere gevallen is p ∧ ¬q onwaar. ◊ Disjunctie

De waarheidstabel voor een disjunctie ϕ ∨ ψ is: ϕ

ψ

ϕ∨ψ

1 1 0 0

1 0 1 0

1 1 1 0

Het logische ‘of’ is de zogenaamde inclusieve disjunctie, die we al zijn tegengekomen in gevallen als ‘De afstandsbediening of de tv is kapot’. In de gewone taal wordt de inclusieve disjunctie ook wel door ‘en/of’ uitgedrukt. Hierbij kan het een of het ander het geval zijn, of beide. De exclusieve disjunctie (‘óf ... óf ...’), die we zagen in een zin als ‘Voor je verjaardag krijg je een racefiets of autorijlessen’, waarbij of het een of het ander het geval is, maar niet beide, kan overigens ook in de propositielogica worden weergegeven.

20

Hoofdstuk 2

Propositielogica, waarheid en classificeren

Wanneer de formules langer worden, groeit het aantal deelformules ook, zodat de methode om alle deelformules apart in een kolom te zetten van de waarheidstabel, erg bewerkelijk kan worden. Handiger is het dan een compactere notatie te gebruiken. In plaats van de deelformules steeds opnieuw op te schrijven, plaatsen we de enen en nullen onder het connectief dat bereik heeft over de rest van deze deelformule. De volgorde waarin de waarheidswaarden zijn berekend, geven we voor de duidelijkheid met kleine cursieve cijfertjes aan. VOORBEELD 2.4

Implicatie

De waarheidstabel voor (p ∧ ¬q) ∨ q op de nieuwe manier is: p

q

(p

∧

¬

q)

∨

q

1 1 0 0

1 0 1 0

1 1 0 0

0 1 0 0

0 1 0 1

1 0 1 0

1 1 1 0

1 0 1 0

1

3

2

1

4

1

◊

De waarheidstabel voor een implicatie ϕ → ψ ziet er zó uit: ϕ

ψ

ϕ→ψ

1 1 0 0

1 0 1 0

1 0 1 1

Een implicatie vertoont overeenkomst met als-dan-zinnen uit de gewone taal. De zin ‘Als het regent, dan worden de straten nat’ is duidelijk onwaar als het enerzijds regent en anderzijds de straten niet nat worden. Daarom geven we ϕ → ψ de waarheidswaarde 0 in het geval ϕ waar en ψ onwaar is. Dit is ook het enige geval waarin de implicatie onwaar wordt. Als ϕ en ψ beide waar zijn, dan is de implicatie waar, zoals aan het voorbeeld te zien is. Lastiger is het geval waarin ϕ onwaar is. Als ϕ onwaar is, dan is de implicatie altijd waar, onafhankelijk van de waarheid van ψ. De implicatie kan dan nooit onwaar zijn, want een tegenvoorbeeld kunnen we in dat geval niet vinden: voor een tegenvoorbeeld moet ϕ waar en ψ onwaar zijn. Dat een implicatie ϕ → ψ waar is als ϕ onwaar is stuit veel mensen tegen de borst (en al heel lang). Dit komt omdat het een conflict kan opleveren met de gewone taal, waarin we gewend zijn ‘als ..., dan ...’ in een oorzaakgevolg-situatie te gebruiken. Als de oorzaak onwaar is, lijkt het irrelevant

21

Logica in actie

om over het gevolg na te denken, en in zo’n geval vinden we de implicatie dus onwaar! ‘Als de maan van groene kaas is, dan zakken de beurskoersen’ is onzin, en zou daarom niet waar zijn. De beurskoersen blijven niettemin zakken. In de propositielogica noemen we zo’n implicatie daarom wel waar. Logici zijn overigens nog lang niet uitgedacht over andere vormen van implicatie, want een zekere spanning met de natuurlijke taal is vaak een bijzonder effectieve bron van interessante onderzoeksvragen. VOORBEELD 2.5

De waarheidstabel voor de formule (p → q) → (¬p → ¬q) is: p

q

(p

→

q)

→

(¬

p

→

¬

q)

1 1 0 0

1 0 1 0

1 1 0 0

1 0 1 1

1 0 1 0

1 1 0 1

0 0 1 1

1 1 0 0

1 1 0 1

0 1 0 1

1 0 1 0

1

2

1

4

2

1

3

2

1

Deze formule is dus alleen onwaar als p onwaar is en q waar. Equivalentie

We willen uiteraard dat een equivalentie ϕ ↔ ψ juist dan waar is als ϕ en ψ dezelfde waarheidswaarde hebben, dat wil zeggen óf allebei waar óf allebei onwaar. Hiermee ligt de waarheidstabel voor equivalentie voor de hand: ϕ

ψ

ϕ↔ψ

1 1 0 0

1 0 1 0

1 0 0 1

In gewone taal wordt ‘als’ ook vaak in de betekenis van ‘desda’ gebruikt, bijvoorbeeld in ‘Je mag tv kijken als je huiswerk af is’. Volgens sommigen heeft ook ‘mits’ deze betekenis. Wanneer we expliciet willen aangeven dat we met een equivalentie en niet met een implicatie te maken hebben, moeten we onze toevlucht nemen tot min of meer moeizame constructies als ‘precies dan als’ en ‘dan en slechts dan als’ (desda). Die laatste formulering is in de wiskunde heel gebruikelijk.

22

◊

Hoofdstuk 2

VOORBEELD 2.6

Propositielogica, waarheid en classificeren

De waarheidstabel voor de formule ¬(p ∧ q) ↔ (¬p ∧ ¬q) is: p

q

¬

(p

∧

q)

↔

(¬

p

∧

¬

q)

1 1 0 0

1 0 1 0

0 1 1 1

1 1 0 0

1 0 0 0

1 0 1 0

1 0 0 1

0 0 1 1

1 1 0 0

0 0 0 1

0 1 0 1

1 0 1 0

3

1

2

1

4

2

1

3

2

1

2.5

◊

De kracht van de propositielogica

De propositielogica is hiervoor omschreven als een spel met waarheidswaarden en als een taaltje gebaseerd op (preciseringen van) woorden als ‘niet’ en ‘of’. Dat lijkt allemaal nogal bescheiden. Hoewel we in hoofdstuk 4 inderdaad een krachtiger logica zullen leren kennen, de predikaatlogica, moet hier toch op een paar sterke punten gewezen worden. In de eerste plaats is de propositielogica de basis voor veel logische systemen en als zodanig al heel belangrijk. Voorts is de propositielogica sterker dan we misschien zouden denken. Dat blijkt als we proberen nog andere (‘sterkere’) connectieven toe te voegen. Logica als classificeren

Als we een situatie uit het dagelijks leven beschrijven in propositielogische termen, dan zijn we soms geneigd dat alleen te zien als een andere weergave dan die in beweringen in natuurlijke taal. Maar we kunnen onze formalisatie ook op zich laten staan als een manier om verschillende situaties te classificeren - bij iedere situatie ‘van een bepaalde klasse of type’ hoort dan een aparte formele beschrijving. Op de voorgrond staat dan welke waardering van propositieletters door zo’n formele beschrijving vastgelegd wordt. De propositielogica is met name belangrijk omdat classificatie van situaties voorkomt in elke vorm van redeneren en ordening van informatie.

Andere connectieven

In de voorgaande paragrafen hebben we een aantal connectieven bestudeerd. Zijn ze dit nu allemaal? Zonder twijfel zijn ¬, ∧, ∨, → en ↔ de meest bekende connectieven van de propositielogica. Daarnaast worden er voor diverse doeleinden nog wel eens andere connectieven van stal gehaald. Een voorbeeld daarvan is de exclusieve disjunctie. Hiervoor schrijven we ‘eor’. De formule ϕ eor ψ drukt uit dat óf ϕ óf ψ waar is, maar dat ze niet allebei waar zijn. Zoals gezegd is dit anders dan de disjunctie ∨, waarbij een van beide disjuncten waar kan zijn, maar ze ook allebei waar mogen zijn.

23

Logica in actie

Bij eor hoort dus de volgende waarheidstabel: ϕ

ψ

ϕ eor ψ

1 1 0 0

1 0 1 0

0 1 1 0

Het is nu opmerkelijk, dat we deze exclusieve disjunctie ook kunnen beschrijven in termen van twee formulevariabelen ϕ en ψ en de connectieven ¬, ∧ en ∨, die we al hadden, namelijk als (ϕ ∧ ¬ψ) ∨ (¬ϕ ∧ ψ). Een waarheidstabel van deze formule is: ϕ

ψ

(ϕ

∧

¬

ψ)

∨

(¬

ϕ

∧

ψ)

1 1 0 0

1 0 1 0

1 1 0 0

0 1 0 0

0 1 0 1

1 0 1 0

0 1 1 0

0 0 1 1

1 1 0 0

0 0 1 0

1 0 1 0

1

3

2

1

4

2

1

3

1

En uiteraard vinden we in de kolom van het hoofdconnectief ∨ de nullen en enen op dezelfde plaats als in de waarheidstabel voor eor. Het nieuwe connectief eor is dus niet echt nodig. Dit is een illustratie van een veel algemener feit. Het komt hierop neer dat alle mogelijke waarheidstabellen al bij een of andere formule horen die we kunnen formuleren met de connectieven ¬, ∧, ∨, → en ↔. Iets preciezer gezegd: alle mogelijke verdelingen van waarheidswaarden treden op als laatst verkregen kolom in de waarheidstabel van een formule die alleen van de standaardconnectieven gebruik maakt (en uiteraard van propositieletters en haakjes). We hoeven zelfs niet van alle standaardconnectieven gebruik te maken: met alleen ¬ en ∨ kan het bijvoorbeeld ook. De andere connectieven dienen dan uitsluitend voor ons gemak. Kan het ook met slechts één connectief? Ja, dat kan! Met het connectief genaamd ‘nand’, dat de volgende waarheidstabel heeft, kunnen alle andere connectieven worden gedefinieerd. Kunt u dit ook?

24

Hoofdstuk 2

Propositielogica, waarheid en classificeren

ϕ

ψ

ϕ nand ψ

1 1 0 0

1 0 1 0

0 1 1 1

Uit de tabel blijkt dat ϕ nand ψ staat voor ‘niet zowel ϕ als ψ‘; nand is dan ook een samentrekking van het Engelse ‘not’ (niet) en ‘and’ (en). De propositielogica is een alomtegenwoordig en rijk logisch systeem, en in hoofdstuk 7 zullen we zelfs zien dat er nog steeds fundamentele open vragen zijn rond de werking van het ‘waarheidsrekenen’ dat we hier hebben uitgelegd. Dit systeem wordt dan ook universeel toegepast. Met name is het de basis van het ontwerpen van en redeneren over Boolese schakelingen en binair tellen en rekenen, en als zodanig een bouwsteen van iedere computer. Samenvatting Een formele taal is van belang om precisie te krijgen in formuleren en verwerken van informatie, voor het geven van een glasheldere grammatica. Dit leidt tot een helder wiskundig systeem waarvan de soms verrassende eigenschappen op zichzelf bestudeerd kunnen worden. Dit is een belangrijk methodologisch idee, dat ook in andere disciplines, zoals de wiskunde, de informatica en de taalkunde, grote invloed heeft gekregen. De taal van de propositielogica wordt gevormd door formules. Zulke formules zijn opgebouwd uit propositieletters (p, q, ...), haakjes en connectieven. De connectieven zijn: connectief

uitspraak

naam

¬ ∧ ∨ → ↔

niet en of als ..., (dan) desda

negatieteken conjunctieteken disjunctieteken implicatieteken equivalentieteken

Behalve het negatieteken, dat maar met één formule combineert tot een nieuwe formule ¬ϕ, combineren de connectieven altijd twee formules:

25

Logica in actie

(ϕ ∧ ψ) noemen we een conjunctie, (ϕ ∨ ψ) een disjunctie, (ϕ → ψ) een implicatie en (ϕ ↔ ψ) een equivalentie. Formules die optreden bij de inductieve opbouw van een formule, noemen we deelformules van die formule. De deelformules van een formule ϕ die door een connectief worden gecombineerd tot een nieuwe deelformule van ϕ, vormen het bereik van dat connectief. De betekenis van de formules is gelegen in hun waarheidstabellen. Waarheidstabellen classificeren situaties. Die waarheidstabellen zijn op systematische wijze op te stellen wanneer de waarheidstabellen van de connectieven bekend zijn. Deze zijn: ϕ

ψ

¬ϕ

ϕ∧ψ

ϕ∨ψ

ϕ→ψ

ϕ↔ψ

1 1 0 0

1 0 1 0

0 0 1 1

1 0 0 0

1 1 1 0

1 0 1 1

1 0 0 1

Opgaven OPGAVE 2.1

Welke van de volgende rijtjes symbolen zijn formules en welke niet? Als een rijtje geen formule is, geef dan aan waarom. Als een rijtje wel een formule is, schrijf dan op hoe deze formule moet worden uitgesproken. – ∧p∧q – p∨p – (p → q) ↔ ¬(¬q → ¬p) – p∧∨q

OPGAVE 2.2

Maak de waarheidstabellen voor de formule (p → q) ∨ (q → p) en voor de formule ((p ∨ ¬q) ∧ r) ↔ (¬(p ∧ r) ∨ q).

OPGAVE 2.3

Gegeven zijn de volgende proposities: – p: Jan gaat naar het feest. – q: Marie gaat naar het feest. Zet nu de volgende uitspraken om in formules van de propositielogica: – Marie noch Jan gaat naar het feest. – Of Marie óf Jan gaat naar het feest. – Jan gaat naar het feest, tenzij Marie er naar toe gaat.

OPGAVE 2.4

Gegeven is dat de volgende uitspraak in een bepaalde situatie waar is: ‘Als Jan gaat, gaat Marie in ieder geval, en Piet gaat alleen als Jan niet gaat.’ Wie gaan er nu? Zet de uitspraak eerst om in een formule en stel de waarheidstabel van deze formule op.

26

HOOFDSTUK 3 Wie A zegt moet B zeggen Logici ontwerpen niet alleen systemen om bestaande vormen van redeneren te analyseren, ze bestuderen ook de eigenschappen van die systemen op zich. De propositielogica is daarvan een uitstekend voorbeeld, want we kunnen dit systeem gebruiken om nu stelselmatige wetmatigheden aan het licht te brengen. Wat maakt bijvoorbeeld de formule ¬(p ∧ ¬p) zo bijzonder? Dat is vooral het feit dat de formule niet onwaar kan worden, anders gezegd: dat de formule waar is, of p nu waar is of niet. Dit kunnen we aflezen uit de waarheidstabel van de formule. Deze eigenschap komt bij veel formules voor en is van groot belang, zowel voor de theorie als voor diverse toepassingen. Een andere wetmatigheid heeft te maken met redeneringen. Een redenering van de vorm ‘uit p ∨ ¬q en q kan men p afleiden’ vonden we correct (geldig), en we kunnen uitzoeken welke eigenschap van de waarheidstabellen van de formules in kwestie hiervoor verantwoordelijk is. Door op zo’n wiskundige manier te denken kunnen we dus precies definiëren wat geldigheid is, maar we kunnen hiermee ook allerlei mooie patronen zien in geldig redeneren die anders onzichtbaar zouden blijven. Voorbeelden die we zullen zien zijn de dualiteit van conjunctie en disjunctie in de aanwezigheid van negatie, en het systematisch aan elkaar schakelen van implicaties.

3.1

Tautologie

Door middel van waarheidstabellen kunnen we onderzoeken onder welke voorwaarden een formule waar is. Twee gevallen springen er duidelijk uit: formules die altijd waar zijn en formules die altijd onwaar zijn. Met ‘altijd’ bedoelen we: bij elke toekenning van waarheidswaarden aan propositieletters.

27

Logica in actie

VOORBEELD 3.1

De formule p ∨ ¬p is waar, ongeacht de waarheidswaarde van p. Dit is direct te zien aan de waarheidstabel: p

p

∨

¬

p

1 0

1 0

1 1

0 1

1 0

1

3

2

1

De waarheidswaarden van de hele formule staan in de kolom onder ∨, die in stap 3 berekend worden. In deze kolom staan alleen enen, zodat de formule altijd waar is. Elke uitspraak van deze vorm is dus altijd waar. Vanaf nu geven we trouwens de stappen waarin de waarheidstabel wordt opgesteld (de onderste rij in de tabel) niet meer aan. ◊ VOORBEELD 3.2

De formule (p ∧ (p → q)) → q is waar, welke waarheidswaarde we ook voor p en q kiezen. p

q

(p

∧

(p

→

q))

→

q

1 1 0 0

1 0 1 0

1 1 0 0

1 0 0 0

1 1 0 0

1 0 1 1

1 0 1 0

1 1 1 1

1 0 1 0

◊

Zo’n toekenning van waarheidswaarden aan propositieletters heet een ‘waardering’. Een waardering w is een functie van propositieletters naar waarheidswaarden, dat wil zeggen w: {p, q, r, ...} → {0, 1}. En een waardering die een formule waar maakt noemen we een model voor die formule. Je zou ook kunnen zeggen dat die waardering ‘model staat’ voor die formule. Een formule is vervulbaar als deze ten minste één model heeft. DEFINITIE 3.1

Een tautologie is een formule van de propositielogica die waar is voor elke waardering. Bij iedere rij in een waarheidstabel hoort dus een waardering. De formules in de laatste twee voorbeelden, die voor iedere waardering waar zijn, zijn tautologieën. Bij een tautologie is iedere waardering ook model voor die formule. Om na te gaan of een formule een tautologie is, dienen we dus een waarheidstabel voor de formule op te stellen, en vervolgens te kijken of de kolom onder het connectief met het grootste bereik alleen maar enen bevat.

28

Hoofdstuk 3

Wie A zegt moet B zeggen

De tegenhanger van een tautologie is een formule die voor iedere waardering onwaar is. Dit heet een contradictie. VOORBEELD 3.3

De formule p ∧ ¬p is onwaar, ongeacht de waarheidswaarde van p. p

p

∧

¬

p

1 0

1 0

0 0

0 1

1 0

◊

In de hoofdkolom van de waarheidstabel van een contradictie staan dus alleen maar nullen. Het is duidelijk dat een formule niet zowel een contradictie als een tautologie kan zijn. Er is wel een verband: ¬ϕ is een contradictie, precies dan als ϕ een tautologie is, en ϕ is een contradictie, precies dan als ¬ϕ een tautologie is. Er bestaan ook formules die geen van beide zijn. Een eenvoudige propositieletter p voldoet daar al aan! Een ander voorbeeld is als volgt. VOORBEELD 3.4

De formule p ∧ ¬q is waar voor één waardering, en onwaar voor de overige waarderingen. p

q

p

∧

¬

q

1 1 0 0

1 0 1 0

1 1 0 0

0 1 0 0

0 1 0 1

1 0 1 0

◊

Bepaalde vormen van tautologieën keren steeds weer terug. Het is immers alleen de vorm van de propositie die haar geldig maakt. Daarom zijn naast p ∨ ¬p ook q ∨ ¬q en ((p ∧ q) ∨ r) ∨ ¬((p ∧ q) ∨ r) tautologieën. Kortom, alle formules van de vorm ϕ ∨ ¬ ϕ zijn tautologieën. Deze wet heet het principe van uitgesloten derde. In het Latijn is dit: ‘tertium non datur’, hetgeen betekent “een derde wordt niet gegeven”. Andere tautologieën zijn: – – – – – –

ϕ ↔ ¬¬ϕ (ϕ ∧ ¬ϕ) → ψ (ϕ ∧ (ϕ → ψ)) → ψ ¬(ϕ ∧ ψ) ↔ (¬ϕ ∨ ¬ψ) ¬(ϕ ∨ ψ) ↔ (¬ϕ ∧ ¬ψ) (ϕ → ψ) ↔ (¬ψ → ¬ ϕ)

Dit kunt u desgewenst met waarheidstabellen aantonen.

29

Logica in actie

We hoeven nu niet meer een omvangrijke waarheidstabel voor bijvoorbeeld ((p ∧ q) → (¬r ∨ s)) ↔ ¬¬((p ∧ q) → (¬r ∨ s)) op te stellen; het volstaat om te herkennen dat deze formule de vorm ϕ ↔ ¬¬ϕ heeft. Verum en falsum

Het is handig om een hele korte formule te hebben die een tautologie is. Soms wordt het speciale symbool ⊤ ingevoerd als afkorting voor p ∨ ¬p. Dit ⊤ staat voor, in het Engels: ‘true’. In het Latijn spreken we van ‘verum’. Voor contradicties geldt net zoiets. De formule die altijd onwaar is wordt weergegeven met het symbool ⊥. Dit staat voor, in het Engels, ‘false’; of, zo u wilt, in het Latijn, ‘falsum’. Visueel kunnen we hier een ‘omgekeerde ⊤’ in zien: de waarheid op zijn kop, dus. Logisch gevolg

3.2

Met de hier ontwikkelde begrippen zijn we nu in staat om een precieze logische definitie te geven van wat we intuïtief een correcte redenering noemen. Welke eigenschap van de waarheidstabellen van de betrokken formules is hiervoor verantwoordelijk? Om dit te achterhalen, beschouwen we een eenvoudige redenering: uit ‘Jan is een goede schaker en Karin een goede dammer’ kan worden geconcludeerd: ‘Jan is een goede schaker’. Het uitgangspunt is ‘Jan is een goede schaker en Karin een goede dammer’ en de conclusie is ‘Jan is een goede schaker’. Hier is geen speld tussen te krijgen: de redenering is correct. Zij nu p: ‘Jan is een goede schaker’ en q: ‘Karin is een goede dammer’. We maken vervolgens de waarheidstabellen van uitgangspunt (p ∧ q) en conclusie (p): p

q

p

∧

q

p

1 1 0 0

1 0 1 0

1 1 0 0

1 0 0 0 ↑

1 0 1 0

1 1 0 0 ↑

We scheiden het uitgangspunt (of de uitgangspunten) van de conclusie door een onderbreking in de tabel. Vergelijken we de aangegeven kolommen, dan valt op dat het uitgangspunt en de conclusie niet altijd waar zijn, en niet dezelfde waarheidswaarde hoeven te hebben, maar dat, en dit is essentieel: – als het uitgangspunt waar is, dan is ook de conclusie waar. We spreken van logisch gevolg of van ‘geldige gevolgtrekking’.

30

Hoofdstuk 3

Wie A zegt moet B zeggen

DEFINITIE 3.2

Logisch gevolg De formule ψ is een logisch gevolg van ϕ 1 , ..., ϕ n als elke waardering die alle ϕ 1 , ..., ϕ n waar maakt, ook ψ waar maakt. We schrijven hiervoor ϕ 1 , ..., ϕ n ⇒ ψ. Als ψ niet een logisch gevolg van ϕ 1 , ..., ϕ n is, schrijven we ϕ 1 , ..., ϕ n ⇒/ ψ.

VOORBEELD 3.5

De redenering in het vorige voorbeeld kunnen we weergeven als p ∧ q ⇒ p, dat wil zeggen: p is een logisch gevolg van p ∧ q. Immers, er was blijkens de tabel maar één waardering die p ∧ q waar maakte, en die maakt inderdaad de conclusie p ook waar. In dit voorbeeld is n = 1 en is ϕ 1 de formule p ∧ q. ◊

VOORBEELD 3.6

We herhalen de redenering van het begin van hoofdstuk 2: ‘De afstandsbediening is kapot of de tv werkt niet goed. Maar de tv werkt wel goed. Dus de afstandsbediening is kapot.’ We kiezen nu p: ‘De afstandsbediening is kapot’ en q: ‘De tv werkt goed’. We gaan nu kijken of p een logisch gevolg is van p ∨ ¬q en q samen. p

q

p

∨

¬

q

q

p

1 1 0 0

1 0 1 0

1 1 0 0

1 1 0 1

0 1 0 1

1 0 1 0

1 0 1 0

1 1 0 0

Uit de tabel blijkt dat de beide uitgangspunten alleen tegelijk waar (onderstreepte enen) zijn als p en q waar zijn. Met andere woorden: we hoeven slechts naar de eerste rij waarheidswaarden te kijken, en daar is de conclusie ook waar. Kortom: p ∨ ¬q, q ⇒ p. In dit voorbeeld is n = 2, ϕ 1 de formule p ∨ ¬q en ϕ 2 de formule q. ◊ Merk op dat in de definitie van geldig gevolg staat: elke waardering die de uitgangspunten waar maakt, moet de conclusie waar zijn. Het is niet voldoende dat er een waardering bestaat die zowel uitgangspunt als conclusie waar maakt. VOORBEELD 3.7

Uit ‘Er komen meer wegen in Nederland precies dan als Nederland geasfalteerd raakt’ is het niet correct te concluderen dat er meer wegen in Nederland komen. Formeel: p ↔ q ⇒/ p, dat wil zeggen: p is geen logisch gevolg van p ↔ q. Er is wel een waardering die het uitgangspunt en de conclusie waarmaakt, namelijk de waardering die p en q allebei waarmaakt. Maar er is ook een waardering die p ↔ q waarmaakt, maar niet de conclusie, namelijk de waardering die p en q allebei onwaar maakt. ◊

31

Logica in actie

Als twee formules uit elkaar volgen spreken we van logische equivalentie: als ϕ ⇒ ψ en ψ ⇒ ϕ dan schrijven we ϕ ⇔ ψ , en we noemen de formules ϕ en ψ dan logisch equivalent. Er is een nauwe relatie tussen implicatie en logisch gevolg. De formule ( ϕ 1 ∧ ... ∧ ϕ n ) → ψ is een tautologie precies dan als ϕ 1 , ..., ϕ n ⇒ ψ. Bijvoorbeeld, de tautologie ((p → q) ∧ (q → r)) → (p → r) correspondeert met de gevolgtrekking p → q, q → r ⇒ p → r. Toch mogen de tekens → en ⇒ niet door elkaar worden gehaald. Het wezenlijke verschil is dat → deel uitmaakt van de propositielogische taal, en ⇒ niet. Schrijven we ϕ ⇒ ψ, dan stelt dit dat ψ inderdaad volgt uit ϕ, terwijl als we ϕ → ψ opschrijven, deze formule best onwaar kan zijn. Net zoiets geldt voor het verschil tussen het equivalentiesymbool ↔ en het begrip logische equivalentie. VOORBEELD 3.8

Logische equivalenties zijn nuttig voor het zoveel mogelijk vereenvoudigen van een formule. Dit kan ook bij het programmeren van pas komen. Om computertijd en programmeertijd te besparen, doen we er goed aan eerst zoveel mogelijk een programma te vereenvoudigen. Zo kunnen we als niet ((x = 1 of y < 0) en (y < 0 of niet x = 1)) dan x := x + y

zonder probleem vervangen door het simpeler (>= betekent ≥) als y >= 0 dan x := x + y

We kunnen namelijk door middel van logische equivalentie uitrekenen dat niet ((x = 1 of y < 0) en (y < 0 of niet x = 1)) niet ((x = 1 of y < 0) en (niet x = 1 of y < 0)) niet ((x = 1 en niet x = 1) of y < 0) niet (y < 0) (y >= 0)

⇔ ⇔ ⇔ ⇔

Met x := x + y wordt aangegeven dat aan de variabele x een nieuwe waarde wordt toegekend, namelijk de som van de waarden die x en y tot op dat moment hadden. ◊

32

Hoofdstuk 3

DEFINITIE 3.3

Wie A zegt moet B zeggen

Een aantal bekende vormen van gevolgtrekkingen zijn: naam

vorm van de gevolgtrekking

ex falso modus ponens modus tollens contrapositie reductio ad absurdum hypothetisch syllogisme disjunctief syllogisme

ϕ, ¬ϕ ⇒ ψ ϕ, ϕ → ψ ⇒ ψ ϕ → ψ, ¬ψ ⇒ ¬ϕ ϕ → ψ ⇒ ¬ψ → ¬ϕ als ϕ, ¬ψ ⇒ ⊥ , dan ϕ ⇒ ψ ϕ → ψ, ψ → χ ⇒ ϕ → χ ϕ → ψ, ¬ϕ → ψ ⇒ ψ

Deze regels worden (vaak stilzwijgend) gebruikt bij wiskundige bewijzen. Ex falso is een gangbare afkorting van ‘ex falso sequitur quodlibet’ (Latijn: uit een contradictie volgt alles wat u maar wilt). Reductio ad absurdum (Latijn: het reduceren tot een absurde - tegenstrijdige - bewering) is niet een logisch gevolg, maar een relatie tussen logische gevolgen. In de tabel hebben we een derde Griekse letter ingevoerd voor willekeurige formules: χ, spreek uit ‘chi’. VOORBEELD 3.9

We kunnen nu de vorm herkennen van de bewijzen uit hoofdstuk 1. In stelling 1.2 bewezen we dat de wortel van 2 geen breuk is. Laat p staan voor de bewering ‘de wortel van twee is een breuk’. Het bewijs verliep als volgt: we namen aan dat de wortel van twee een breuk was, p dus, en leidden daaruit een tegenspraak af: ⊥. Daarmee toonden we aan dat de wortel van 2 niet een breuk was: ¬p. Dit is een voorbeeld van een ‘reductio ad absurdum’. Deze heeft de vorm “als ϕ, ¬ψ ⇒ ⊥, dan ϕ ⇒ ψ”. In dit geval kunnen we voor ϕ de ‘de getaltheorie’ nemen (die we verder niet zullen detailleren; hieronder valt bijvoorbeeld dat we een deling kunnen uitvoeren, en factoren 2 tegelijk uit de teller en de noemer kunnen verwijderen). Voor ψ nemen we ¬p. Voor ¬ψ krijgen we dan ¬¬p, en dit is equivalent met p. De concrete redenering wordt daarmee: “uit ϕ, p ⇒ ⊥, volgt ϕ ⇒ ¬p”. ◊

VOORBEELD 3.10 In stelling 1.3 uit hoofdstuk 1 bewezen we dat er irrationale getallen x en y

bestaan waarvoor x y rationaal is. Laat p staan voor de bewering ‘ ( 2 ) 2 is rationaal’ en laat q staan voor de bewering ‘er zijn irrationale getallen x en y waarvoor x y rationaal is’. Het bewijs verliep als volgt. We weten dat ( 2 ) 2 ofwel rationaal is, of niet. Dit is van de vorm p ∨ ¬p (en zelfs exclusieve disjunctie, maar dat maakt hier niet uit). Uit p volgt q, want dan nemen we x = y = 2 . Maar uit ¬p volgt eveneens q, want dan nemen we x = ( 2 ) 2 en y = 2 . Hiermee was het bewijs klaar, dat wil zeggen: hieruit volgde q. Er is hier dus sprake van een instantie van het disjunctief syllogisme, namelijk: p → q, ¬p → q ⇒ q. ◊

33

Logica in actie

3.3

Van gevolgtrekking tot informatieverwerking

De propositielogica werd oorspronkelijk ontworpen als rekensysteem voor geldig redeneren. Maar zoals vaak gebeurt met wetenschappelijke theorieen, blijkt hun reikwijdte achteraf veel groter dan aanvankelijk werd gedacht, of zelfs bedoeld. Zoals we meteen aan het begin van hoofdstuk 1 al zagen, vloeit informatie op veel meer manieren dan alleen het maken van gevolgtrekkingen. We krijgen informatie binnen door observatie en communicatie, en trekken daaruit dan pas conclusies. Dat verwerken van binnenkomende informatie op zich kan eveneens worden gemodelleerd in de propositielogica, namelijk door middel van ‘updates’ op verzamelingen modellen. Propositielogica is dus niet alleen een theorie van gevolgtrekken, maar ook van informatieverwerking. In deze paragraaf schetsen we hoe dit in zijn werk gaat. In een gevolgtrekking ϕ 1 , ..., ϕ n ⇒ ψ trekken we een conclusie uit verzameling aannames. De volgorde van die aannames doet er eigenlijk weinig toe. Gezien het verband met de tautologie ( ϕ 1 ∧ ... ∧ ϕ n ) → ψ mag de volgorde er zelfs niet toe doen, omdat in een conjunctie de volgorde van de conjuncten irrelevant is. Maar die aannames moeten we eerst wel binnen krijgen. Dit proces kunnen we nu heel natuurlijk weergeven als toenemende inperking van mogelijkheden, dat wil zeggen: van de mogelijke waarderingen die echt het geval kunnen zijn. We beginnen met alle waarderingen. Formule ϕ 1 beperkt deze verzameling al wat, namelijk tot de modellen van ϕ 1 . Als nu ϕ 2 eveneens vereist is, beperken we ons nog wat meer, namelijk tot de modellen van ϕ 1 die eveneens modellen van ϕ 2 zijn. Enzovoorts. Als we in dit proces een ϕ i tegen het lijf lopen die alle resterende modellen elimineert, weten we ‘dat we te ver zijn gegaan’: niet alle systeemeisen kunnen tegelijk vervuld worden. We zullen onze eisen dus ergens moeten herzien. Als we daarentegen wel alle eisen ϕ 1 , ..., ϕ n kunnen vervullen, kunnen we daarna verifiëren of een gewenste systeemeigenschap ψ geldt door na te gaan of ψ opgaat in alle resterende mogelijkheden. Dit geeft een verband tussen modeleliminatie en gevolgtrekking. Als we slechts een enkele mogelijkheid overhouden, dan is dat te zien als het bereiken van totale informatie over de situatie waar het ons om te doen was. Dit idee van informatieverwerving als ‘modeleliminatie’ is heel algemeen, en het komt in allerlei wetenschappen voor. Meer algemeen is een dynamisch perspectief op informatieverwerking en gevolgtrekkingen ook van toepassing op de predikaatlogische modellen die we in de komende twee hoofdstukken gaan introduceren. De methode van modeleliminatie zullen we met name zien terugkeren bij de bestudering van kennis en informatie in taalgebruik en communicatie, het onderwerp van de kennislogica in hoofdstuk 6. In dat geval blijkt de volgorde waarin we de informatie verwerken er ineens wel toe te doen, en geldt dus niet

34

Hoofdstuk 3

Wie A zegt moet B zeggen

meer voor alle ϕ 1 en ϕ 2 dat eerst ϕ 1 verwerken en dan ϕ 2 verwerken hetzelfde oplevert als eerst ϕ 2 verwerken en dan ϕ 1 verwerken. VOORBEELD 3.11 We verwerken eerst de informatie p ∨ ¬q. Deze formule heeft drie model-

len. Daarna wordt bekend dat p ↔ q. We houden nog twee van drie modellen over. Ten slotte wordt bekend dat p. Hiermee resteert nog één model. Uit deze drie formules volgt dat p ∧ q. p

q

p ∨ ¬q

p↔q

p

p∧q

1 1 0 0

1 0 1 0

1 1 0 1

1 0 0 1

1 1 0 0

1 0 0 0

3.4

◊

Feitelijk redeneren

Hoe verhoudt de logica zich tot de realiteit van ons gedrag? Behalve de leer van correcte informatieve handelingen is er dan in elk geval ook de analyse van incorrecte redeneringen. Er zijn immers allerlei redeneringen die in natuurlijke taal wel correct lijken, maar dat toch niet zijn. Een goed logisch systeem moet ook fouten kunnen analyseren, en voorspellen waar deze optreden, de zogenaamde drogredenen (in het Engels: ‘fallacies’). Met name de argumentatietheorie houdt zich bezig met de analyse van drogredenen. We volstaan met een aantal voorbeelden. VOORBEELD 3.12 Bevestiging van het gevolg

We gaan weer terug naar het voorbeeld in het begin van het hoofdstuk 2: ‘Het schilderij hangt hier niet als het gestolen is. Het schilderij hangt hier niet. Dus is het gestolen.’ Deze ongeldige redenering heeft de vorm p → ¬q, ¬q ⇒/ p. De redenering is ongeldig omdat de waardering die p en q onwaar maakt, de uitgangspunten waarmaakt maar niet de conclusie. De redenering lijkt geldig omdat deze zowel op ‘modus ponens’ lijkt als op ‘modus tollens’ (zie definitie 3.3). ◊

VOORBEELD 3.13 Verborgen aanname

“De tweede voornaam van Barack Obama is Hussein. Hij is dus moslim! Je moet dus niet op hem stemmen bij de presidentsverkiezingen.” Deze redenering bevat twee verborgen aannames. De eerste is “Iemand die Hussein als voornaam heeft is een moslim.” Deze aanname is niet gerechtvaardigd, want dit hoeft niet het geval te zijn. En president Obama is in feite geen moslim. De tweede verborgen aanname is “Als iemand moslim is

35

Logica in actie

dan kan hij/zij geen kandidaat zijn voor de presidentsverkiezingen” of (het blijft gissen ...) “Als iemand moslim is dan zou hij/zij geen kandidaat mogen zijn voor de presidentsverkiezingen”. Het eerste is wederom onwaar, omdat in de Amerikaanse grondwet is vastgelegd dat geloofsovertuiging politiek niet in de weg mag staan. Het tweede lijkt ons ook onwaar - de vraag is natuurlijk of de meerderheid van de Amerikaanse bevolking daar nu, in 2009, zo over denkt. We wachten tot de presidentsverkiezingen in 2020, en de eerste islamitische Amerikaanse presidentskandidaat. ◊ VOORBEELD 3.13 Cirkelredenering

De cirkelredenering staat bekend onder de Latijnse naam ‘petitio principii’. De algemene vorm van een cirkelredenering is ϕ 1 → ϕ 2 , ϕ 2 → ϕ 3 , ..., ϕ n → ϕ 1 ⇒/ ϕ 1 , en het kortst door de bocht is hier ϕ 1 → ϕ 1 ⇒/ ϕ 1 : uit de triviale implicatie dat een bewering zichzelf impliceert volgt de bewering zelf. Bijvoorbeeld: “Ik ben de baas omdat ik het hier voor het zeggen heb.” Of anders deze: “Waar je die kerktoren ziet staan moet het centrum van Venlo wel zijn, want dat is echt zo’n centrumkerk.” In het Engels staat deze drogreden bekend als ‘Begging the Question’. ◊ Overigens willen we bepaald niet zeggen dat fouten en drogredenen kenmerkend zijn voor wat een logicus ziet als hij kijkt naar feitelijk redeneren van mensen. De laatste jaren groeit juist een interessant grensgebied tussen de logica en de cognitieve psychologie, waarbij gezocht wordt naar rijkere formele modellen van ons redeneren, dat veel meer omvat dan alleen overgangen van aannames naar conclusies. Logische systemen worden zelfs hier en daar gebruikt in het moderne hersenonderzoek, als bron van toetsbare hypotheses over de echte ‘werkplaats’ van ons redeneren, de menselijke hersenen. Samenvatting Een tautologie is een formule van de propositielogica die waar is voor elke waardering. Een waardering die een formule waar maakt is een model van die formule. Een contradictie is een formule die onwaar is voor elke waardering. Een formule is vervulbaar als deze een model heeft. Een formule ψ is een logisch gevolg van formules ϕ 1 , ..., ϕ n als elke waardering die alle ϕ 1 , ..., ϕ n waar maakt, ook ψ waar maakt. We schrijven ϕ 1 , ..., ϕ n ⇒ ψ. De formule ψ heet de conclusie van de gevolgtrekking en de formules ϕ 1 , ..., ϕ n de uitgangspunten of aannames. Als twee formules uit elkaar volgen, dat wil zeggen, zowel ϕ ⇒ ψ als ψ ⇒ ϕ , dan noemen we ze logisch equivalent en we schrijven hiervoor ϕ ⇔ ψ. Verzamelingen waarderingen fungeren ook als informatietoestanden, en een update met nieuwe informatie ϕ vindt plaats door krimp van zo’n verzameling tot de waarderingen daarbinnen die aan ϕ voldoen.

36

Hoofdstuk 3

Wie A zegt moet B zeggen

Opgaven OPGAVE 3.1

Ga voor elk van de volgende formules na of het een tautologie of een contradictie is. – p ↔ ¬p – p → (q → p) – ¬((p → q) → p)

OPGAVE 3.2

Bewijs met een waarheidstabel dat (p ∧ q) → p een tautologie is. Welk logisch gevolg hangt samen met deze tautologie? Hoe is dit gevolg ook direct in te zien?

OPGAVE 3.3

Toon door middel van waarheidstabellen aan dat p → q, ¬q ⇒ ¬p.

OPGAVE 3.4

Los opgave 2.4 op door de twee gegeven beweringen op te vatten als achtereenvolgende updates op de beginverzameling van alle waarderingen. Hoeveel waarderingen zijn er over na de informatie “Als Jan gaat, dan gaat Marie”? En hoeveel als daarna de informatie komt dat “Piet gaat alleen als Jan niet gaat”?

OPGAVE 3.5

Wat is er mis met de volgende redenering: “Papa, waarom gaat de zon onder?” “Omdat de zon om de aarde draait, jongen.” “En waarom is dat dan?” “Ja, anders zou ‘ie toch stilstaan boven ons, niet?”

37

Logica in actie

38

HOOFDSTUK 4 Predikaatlogica, modellen en programma’s De taal van de propositielogica is voor veel toepassingen te arm. Dat bleek al in de Klassieke Oudheid, waar logici allerlei redeneerpatronen vonden die te maken hebben met de manier waarop wij in natuurlijke taal objecten beschrijven, en hun eigenschappen en relaties. Dan gaan andere uitdrukkingen een sleutelrol spelen dan connectieven als “niet” of “en”, met name de kwantoren “alle” en “sommige”. Maar net als in hoofdstuk 2 komt deze noodzaak tot uitbreiding het scherpst naar voren als we kijken naar wiskundig redeneren, en dus beginnen we ook weer daar om te zien wat voor rijker logisch systeem we nu nodig hebben. In de wiskunde doen we graag algemene uitspraken over objecten uit een oneindige verzameling en van de logica verlangen we dat we deze uitspraken heel precies kunnen weergeven, en er de juiste gevolgen uit af kunnen leiden. De propositielogica is hiervoor niet altijd geschikt. Bijvoorbeeld de uitspraak: ‘elk even getal groter dan 2 is de som van twee priemgetallen’ (het zogenaamde vermoeden van Goldbach) kan niet goed worden weergegeven in propositielogica. Wat bedoelen we hier met ‘goed weergeven’? Om dat te zien, doen we een klein ‘gedachte-experiment’: stel dat we wel een geschikte formule uit de propositielogica hadden, hoe zou die er uit moeten zien? Aangezien er in de uitspraak geen voegwoorden te onderscheiden zijn, zouden we de uitspraak als een propositieletter moeten weergeven, zeg door ‘p’. Beschouw nu de uitspraak: ‘1998 is de som van twee priemgetallen’ Dit volgt uit het vermoeden van Goldbach, dat wil zeggen, als het vermoeden van Goldbach juist is, dan is 1998 inderdaad te schrijven als de som van twee priemgetallen. Maar ‘1998 is de som van twee priemgetallen’ is een andere uitspraak dan het vermoeden van Goldbach. Er zit niets anders op dan hiervoor een andere propositieletter te kiezen, zeg q. Maar dan doet zich het probleem voor dat p ⇒/ q, dat wil zeggen: q is geen logisch gevolg van p, want p kan waar zijn terwijl q onwaar is. Het antwoord op de vraag of q een logisch gevolg is van p, staat namelijk los van de relatie tussen de

39

Logica in actie

uitspraken waar p en q vertalingen van zouden moeten zijn: de symbolen p en q zijn bij wijze van spreken ‘losgeweekt’ van de getaltheoretische context. De conclusie is dus dat p geen goede weergave is van het vermoeden van Goldbach, en eigenlijk lag dat ook wel voor de hand: de interne structuur van de uitspraak is niet in de formule p terug te vinden. Een andere poging om ‘Goldbach’ in propositielogica weer te geven is: laat pi staan voor ‘i is de som van twee priemgetallen’. Dan zouden we het vermoeden van Goldbach door een oneindig lange conjunctie kunnen weergeven: p4 ∧ p6 ∧ p8 ∧ p10 ∧ .... Dit zou inderdaad p1998 tot gevolg hebben. Maar een oneindig lange conjunctie is geen ‘formule’ volgens definitie 2.1 van de taal van de propositielogica. We kunnen namelijk eenvoudig inzien dat iedere formule een eindig aantal symbolen bevat. Lange conjuncties mag, maar oneindige niet. Dus ook deze weg loopt in eerste instantie dood. Het systeem van de predikaatlogica, waarmee we in de komende hoofdstukken kennismaken, heeft een veel grotere uitdrukkingskracht dan de propositielogica, waar ze een verfijning en uitbreiding van is. Het vermoeden van Goldbach en zijn gevolgen kunnen we in predikaatlogica wél goed weergeven. We maken eerst kennis met de taal van de predikaatlogica en met een methode om situaties aan te geven waarin een predikaatlogische formule waar is. In het volgende hoofdstuk kijken we naar het interpreteren van predikaatlogische formules, naar predikaatlogisch gevolg, en naar toepassingen van de predikaatlogica in de informatica.

4.1

Bouwstenen van de predikaatlogica

In de propositielogica konden we een eenvoudige uitspraak als ‘Judith schaakt’ alleen maar weergeven door een propositieletter. In de predikaatlogica kunnen we de interne structuur van zulke uitspraken zichtbaar maken. VOORBEELD 4.1

‘Judith schaakt’ wordt in predikaatlogica weergegeven als S(j). Hierin staat S voor de eigenschap ‘schaken’ die toekomt aan het object ‘Judith’, dat met j is aangeduid (‘object’ wordt hier in algemene zin gebruikt: daaronder vallen ook menselijke individuen). De eigenschap staat voorop, het object er tussen haakjes achter. ◊ De predikaatlogica bevat uitdrukkingen die predikaten (dat wil zeggen: eigenschappen van objecten en relaties tussen objecten) aangeven: dat noemen we predikaatsymbolen. Daarnaast zien we namen voor objecten: de constanten. In het voorbeeld is S dus een predikaatsymbool en j een constante. Voor predikaatsymbolen gebruiken we hoofdletters A, ..., Z of speciale symbolen zoals ‘=’. Voor constanten worden kleine letters a, ..., t en ook wel getallen gebruikt. De letters u, ..., z gebruiken we als variabelen.

40

Hoofdstuk 4

Predikaatlogica, modellen en programma’s

We kiezen over het algemeen letters die makkelijk te onthouden zijn, bijvoorbeeld de beginletter van het met het predikaatsymbool overeenkomstige woord. Maar logisch gezien is er geen enkel verband tussen een letter en de daarmee bedoelde eigenschap (en eigenlijk is dit evenmin zo als we getallen gebruiken als constante symbolen), dus dit verband moeten we expliciet aangeven door middel van een zogeheten vertaalsleutel. VOORBEELD 4.2

De uitspraken: – Marie is wiskundige – 5 is een priemgetal kunnen in predikaatlogica worden weergegeven door respectievelijk: – W(m) – P(5) Daarbij is gebruik gemaakt van de volgende vertaalsleutel: – m: Marie – 5: het getal vijf – W: is wiskundige – P: is een priemgetal In het vervolg laten we het vermelden van de vertaalsleutel vaak achterwege wanneer deze erg voor de hand ligt. De predikaatsymbolen in dit voorbeeld zijn dus W en P en de constanten zijn m en 5. Ook zullen we meestal zeggen dat we de constante 5 vertalen als het getal 5, als ‘zichzelf’, als het ware; ook al is daar formeel een verschil tussen. ◊ Ook relaties, zowel in wiskundige als in andere zin, kunnen we logisch aanduiden met predikaatsymbolen. Het volgende voorbeeld laat zien dat we dan ook weer moeiteloos van wiskundige taal op natuurlijke taal kunnen overstappen.

VOORBEELD 4.3

De uitspraken: – Jan houdt van Marie – 5 is groter dan 3 kunnen in predikaatlogica worden vertaald als: – H(j, m) – G(5, 3) Merk op dat ook hier de predikaatsymbolen voorop staan, gevolgd door de objecten tussen haakjes en door komma’s gescheiden. De weergave G(5, 3) wijkt echter wel erg van de wiskundige praktijk af. In plaats van G gebruiken we dan altijd het symbool ‘>’; en dat wordt gewoon tussen de constanten in geschreven, zodat we de volgende bekende notatie gebruiken: – 5>3 ◊ Ook andere gangbare relaties zoals gelijkheid ‘=’, kleiner dan ‘<’ en groter dan of gelijk aan ‘≥’, worden door de bekende symbolen weergegeven en tussen de constanten geschreven in plaats van ervoor.

41

Logica in actie

Predikaatsymbolen zoals P en W in voorbeeld 4.2 worden door slechts één constante gevolgd: zulke predikaatsymbolen worden éénplaatsig genoemd. De predikaatsymbolen in voorbeeld 4.3 hebben twee constanten bij zich: we noemen deze tweeplaatsig. Eigenschappen worden dus in de regel door 1-plaatsige predikaatsymbolen weergegeven, binaire relaties door 2-plaatsige. Hier houdt het niet mee op: er zijn ook 3-plaatsige, 4-plaatsige en in het algemeen n-plaatsige predikaatsymbolen. VOORBEELD 4.4

De uitspraken: – 1/2 ligt tussen 0 en 1 – Marie geeft Jan ‘De Aanslag’ – punt D heeft dezelfde afstand tot P, Q en R kunnen in predikaatlogica worden weergegeven door: – T(1/2, 0, 1) – G(m, j, a) – A(d, p, q, r)

◊

Naast constanten, die elk een bepaald vast object aanduiden, willen we ook graag over symbolen beschikken die verschillende objecten kunnen aanduiden. VOORBEELD 4.5

De uitspraken: – x is groter dan 3. – Marie houdt van hem. kunnen worden weergegeven door: – x>3 – H(m, x) In beide gevallen hangt het van de situatie af wat ‘x’ (of ‘hem’) is. Bijvoorbeeld, als x = 5, dan krijgen we 5 > 3 , maar als x = 10, dan krijgen we 10 > 3. ◊

Variabelen

Net als in de wiskunde noemen we x een variabele. De letters y en z, en soms ook u en v, worden eveneens gebruikt als variabele, eventueel vergezeld van een accent (x’) of een index (x0). Zo’n ‘variabele constante’ x (een naamgeving waar we niet omheen kunnen, ook al lijkt het tegenstrijdig) lijkt dus wat op de propositionele formulevariabelen zoals ϕ en ψ. Er is echter een belangrijk verschil: variabele constanten zoals x gaan echt deel uitmaken van de predikaatlogische taal. Terwijl formulevariabelen niet meer dan ‘plaatsvervangende’ formules zijn, die we later nog kunnen concretiseren om er echte formules van te maken. In de predikaatlogica hebben we geen propositieletters. Het is wel van belang dat we beschikken over haakjes en connectieven. Met behulp van de connectieven ¬, ∧, ∨, → en ↔ kunnen we nu ook ingewikkelder uitspraken weergeven in predikaatlogica. Dit zou je ook ‘vertalen’ kunnen noemen.

42

Hoofdstuk 4

Predikaatlogica, modellen en programma’s

VOORBEELD 4.6

De uitspraken: – Jan houdt van Marie, maar Marie niet van Jan – x is groter dan 0 of y is kleiner dan 1 – als x groter is dan 3 en een priemgetal is, dan is x oneven kunnen worden vertaald als: – H(j, m) ∧ ¬H(m, j) – x>0∨y<1 – (x > 3 ∧ P(x)) → O(x) De laatste uitspraak gaat dus over een specifieke, zij het nog onbekende waarde voor x. Ze wordt ook vaak algemener opgevat, namelijk als: ‘voor elke x geldt, dat als x groter is dan 3 en een priemgetal, dan is x oneven’. Dat bedoelen we hier niet, maar dat kunnen we wel in predikaatlogica uitdrukken, en daar vervolgen we nu mee. ◊

Universele kwantor

Algemene feiten van het soort ‘voor elke x geldt dat als x een priemgetal groter dan 3 is, dan is x oneven’ zijn heel precies uit te drukken in predikaatlogica. De formule (x > 3 ∧ P(x)) → O(x) voldoet echter niet, want daarin heeft x nog steeds een specifieke (maar een ‘verzwegen’) waarde. Wat we expliciet moeten aangeven, is dat we hier alle mogelijke waarden voor x op het oog hebben. Dit doen we door de zogenaamde kwantor ∀ (spreek uit: ‘voor elke ...’ of ‘voor alle ...’) en de betreffende variabele voor de formule te zetten, resulterend in: ∀x (x > 3 ∧ P(x)) → O(x) Het symbool ∀ wordt (al dan niet in combinatie met een variabele) de universele kwantor of al-kwantor genoemd.

VOORBEELD 4.7

Om de uitspraak ‘Alle wiskundigen schaken’ in predikaatlogica weer te geven, herschrijven we de uitspraak in vormen die het mogelijk maken de tot nu toe geïntroduceerde begrippen te gebruiken. We gaan daarbij stukje bij beetje te werk. De stukjes die aangepakt worden, zijn steeds onderstreept. Alle wiskundigen schaken ∀x (als x wiskundige is, dan schaakt x ) ∀x (x is wiskundige → x schaakt) ∀x (W(x) → S(x))

◊

Ook voor meer ingewikkelde gevallen kunnen we deze methode gebruiken, maar nog belangrijker is dat je een patroon in de predikaatlogische formules ontdekt. We vervolgen met nog een ander voorbeeld. VOORBEELD 4.8

De uitspraken: – alle natuurlijke getallen zijn groter dan of gelijk aan 0 – elk natuurlijk getal is groter dan elk negatief geheel getal

43

Logica in actie

kunnen worden weergegeven door de volgende formules: – ∀x (N(x) → x ≥ 0) – ∀x (N(x) → ∀y ((Z(y) ∀y < 0) → x > y)) We zien dat de universele kwantor hier in beide gevallen met een implicatie optreedt. Voor ‘x is een natuurlijk getal’ kunnen we natuurlijk ook x ∈ ¥ schrijven, en voor ‘x is een geheel getal’: x ∈ ¢ . Die meer vertrouwde schrijfwijzen komen op hetzelfde neer. ◊ Het patroon ∀x (... → ...) komt ontzettend vaak voor. Dat is geen toeval, want vaak willen we iets uitdrukken als ‘voor alle dingen die aan een bepaalde eis voldoen, geldt dat ...’. Die eis komt dan links van het implicatieteken te staan. Dit is geen wet van Meden en Perzen: formules als ∀x W(x) en ∀x ∀y R(x, y) zijn zonder meer correct en kunnen heel zinvolle uitspraken zijn. Existentiële kwantor

Een ander type uitspraak is van de vorm ‘Er is een ...’. De predikaatlogica is daarom uitgerust met een tweede kwantor, de existentiële kwantor. Daarbij moet ∃x (spreek uit: ‘er is een x ‘) worden opgevat als ‘voor minstens één x’.

VOORBEELD 4.9

De uitspraken: – Jan houdt van iemand – Marie is groter dan haar vaders vader – 2 is het enige even priemgetal kunnen worden weergegeven door de volgende formules: – ∃x H(j, x) – ∃x (V(x, m) ∧ ∃y (V(y, x) ∧ m > y)) – E(2) ∧ P(2) ∧ ¬∃x (x ≠ 2 ∧ E(x) ∧ P(x)) Informeel gesproken is bij de tweede uitspraak x Maries vader en y Maries opa van vaderskant. Wat we hier niet hebben uitgedrukt, is dat Marie maar één vader heeft, enzovoorts. We kunnen dit wel uitdrukken, namelijk zoals in de derde formule, maar het wordt dan een tamelijk ingewikkelde formule. Bij de derde uitspraak moeten we bedenken dat deze neerkomt op ‘2 is een even priemgetal en er zijn geen andere even priemgetallen’. Net als in de propositielogica geldt hier dat er equivalente formules gegeven kunnen worden; zo kunnen we voor de laatste formule ook de vertaling ∀x ((E(x) ∧ P(x)) ↔ x = 2) geven. ◊ Ook in dit voorbeeld zien we een patroon opduiken: de existentiële kwantor gaat vaak vergezeld van een conjunctie. En hoewel ook hier geldt dat ∃ best zonder ∧ kan optreden (zoals in ∃x V(x)), zien we inderdaad het patroon ∃x (... ∧ ...) heel regelmatig terugkeren. Net zoals bepaalde uitspraken vaak universeel worden opgevat, zien we dat andere zoals ‘Marie houdt van hem’ door sommigen eerder existentieel worden opgevat, dat wil zeggen: gelezen worden als ‘er is iemand waar Marie van houdt’. Ook ‘x is groter dan 3 en y is kleiner dan 4’ zal soms

44

Hoofdstuk 4

Predikaatlogica, modellen en programma’s

existentieel worden gelezen. Toch is het duidelijk dat we dit niet altijd willen: denk bijvoorbeeld aan een probleem dat we aan het oplossen zijn waarbij we de te zoeken grootheden x en y genoemd hebben. We willen dan wel degelijk de waarden van x en y achterhalen, en niet alleen maar beweren dat zulke waarden bestaan. Zonder overdrijving kunnen we stellen dat het vooral de kwantoren zijn die de predikaatlogica haar uitdrukkingskracht verlenen. We laten de kracht van de predikaatlogica nog even zien aan de hand van het vermoeden van Goldbach (zie ook het begin van dit hoofdstuk). VOORBEELD 4.10 Het vermoeden van Goldbach kunnen we weergeven door:

∀x ((E(x) ∧ x > 2) → ∃y ∃z (P(y) ∧ P(z) ∧ S(x, y, z))) We hebben hier van een nieuw 3-plaatsig predikaatsymbool S gebruik gemaakt, waarbij S(x, y, z) staat voor ‘x is de som van y en z ‘.

◊

Dit voorbeeld illustreert dat we in predikaatlogica inderdaad aardig wat wiskunde kunnen weergeven. Goldbach’s vermoeden is een openstaand probleem uit de getaltheorie, en we zouden kunnen denken dat we misschien met logica kunnen uitzoeken of het vermoeden waar is of niet. Wie dat denkt, komt bedrogen uit. De formule geeft weliswaar de globale logische structuur van het vermoeden weer, maar de predikaatsymbolen die erin voorkomen, hebben nog geen specifieke eigenschappen: voor de logica zou E net zo goed kunnen staan voor ‘een getal zijn dat met het cijfer 1 begint’. VOORBEELD 4.11 De uitspraak ‘Ze kwam binnen en deed het licht uit’ kan niet goed door

propositielogica worden weergegeven. Een conjunctie p ∧ q doet geen recht aan de tijdsordening. Het betekent namelijk iets anders dan, andersom, ‘Ze deed het licht uit en kwam binnen’. Om dezelfde reden doet ook een vertaling in predikaatlogica als B(x) ∧ L(x) er geen recht aan. Het effect van de tijdsordening kunnen we verwerken door B en L tweeplaatsig te maken, B(x, y) te laten betekenen ‘x komt binnen op tijdstip y’, en L(x’, y’) te laten betekenen ‘x’ doet het licht uit op tijdstip y’’. Voor het gemak gebruiken we de variabelen t0, t1 en t2. Laat < een ordening op tijdstippen zijn. De uitspraak ‘Ze kwam binnen en deed het licht uit’ is dan te vertalen als: ∃t1 ∃t2 (t1 < t2 ∧ t2 < t0 ∧ B(x, t1) ∧ L(x, t2)) Hierbij geeft de variabele t0 het ‘nu’ van de uitspraak weer.

◊

45

Logica in actie

4.2

Formules van de predikaatlogica

Net als bij de propositielogica, kunnen we nu alle eerdere notaties samenvoegen tot een welgedefinieerde formele taal. We bespreken hier enkele belangrijke aspecten van de ‘grammatica’ van dit systeem, die een aantal interessante verschijnselen vertoont. Zowel variabelen als constanten noemen we termen. Daar valt nog meer onder, zoals ‘1 + 1’ in 1 + 1 = 2 en zowel ‘f(x)’ als ‘x2’ in f(x) = x2, maar daaraan gaan we grotendeels voorbij. We hebben nu alles in gereedheid om een inductieve definitie te geven van predikaatlogische formules. VOORBEELD 4.12 Deze definitie ligt voor de hand als we kijken naar de opbouw van een

uitdrukking als ¬∃x (P(x) ∧ ∀y (P(y) → y ≤ x)): P(x), P(y), y ≤ x P(y) → y ≤ x ∀y (P(y) → y ≤ x) P(x) ∧ ∀y (P(y) → y ≤ x) ∃x (P(x) ∧ ∀y (P(y) → y ≤ x)) ¬∃x (P(x) ∧ ∀y (P(y) → y ≤ x))

Met de predikaatsymbolen P en ≤ en de variabelen x en y maken we eerst de eenvoudige formules van de eerste regel. Vervolgens kunnen we die formules combineren met connectieven en kwantoren, zodat we ten slotte op de beoogde formule uitkomen. ◊ DEFINITIE 4.1

De formules van de predikaatlogica worden als volgt gedefinieerd: – Als P een n-plaatsig predikaatsymbool is en t1, ..., tn zijn termen, dan is P(t1, ..., tn) een formule. – Als ϕ een formule is, dan is ¬ϕ een formule. – Als ϕ en ψ formules zijn, dan zijn (ϕ ∧ ψ) , (ϕ ∨ ψ) , (ϕ → ψ) en (ϕ ↔ ψ) formules. – Als ϕ een formule is en v een variabele, dan zijn ∀v ϕ en ∃v ϕ formules – Er zijn geen andere formules. De basisstap van deze definitie, die predikaatsymbolen combineert met termen, levert zogenaamde atomaire formules. E(3) en x < y zijn voorbeelden van atomaire formules. Atomaire formules zijn enigszins vergelijkbaar met de propositieletters uit de propositielogica: ze zijn de kleinste predikaatlogische formules. Net als in de natuurkunde kunnen we deze ‘atomen’ wel verder splitsen, alleen hebben we dan geen atomen meer maar termen en predikaatsymbolen. Een aantal gangbare predikaatsymbolen schrijven we zoals gezegd niet ‘voorop’, maar ‘middenin’. Een speciaal geval hiervan is

46

Hoofdstuk 4

Predikaatlogica, modellen en programma’s

het identiteitsteken ‘=’. Voor elk paar termen t en t’ is dus t = t’ een formule. Verder zullen we ook symbolen als < en ≥ blijven gebruiken. De formules die we met de overige stappen kunnen maken, zijn samengestelde formules. Aan de stappen voor de connectieven zien we duidelijk dat de predikaatlogica een uitbreiding is van de propositielogica. Merk ook nog op dat de stap voor de kwantoren geen enkele beperking stelt op de formule ϕ: ∀x P(3) is een goede formule, ook al komt x niet in P(3) voor. VOORBEELD 4.13 Termen en functies

In voorbeeld 4.10 hebben we het predikaatsymbool S gebruikt waar we eerder het teken ‘+’ verwacht hadden. In de rekenkunde combineert ‘+’ twee getallen tot een nieuw getal, maar we hebben hier nog geen manier aangegeven om twee constanten of variabelen op een dergelijke manier te verbinden. Bijvoorbeeld P(x, y) drukt een relatie tussen x en y uit, en geen bewerking op x en y. Om bewerkingen als optellen direct in predikaatlogica weer te geven, kunnen we ook ‘+’ in de logische taal opnemen; ‘+’ heet dan een functiesymbool. Net als bij de predikaatsymbolen kennen we eenplaatsige, tweeplaatsige, en in het algemeen n-plaatsige functiesymbolen. Het symbool ‘+’ is een tweeplaatsig functiesymbool, en 2 zijn eenplaatsige functiesymbolen. ‘Marie is groter dan haar vaders vader’ uit voorbeeld 4.9 kunnen we ook weergeven als m > f(f(m)), met f voor: ‘de vader van’. Het vermoeden van Goldbach kunnen we ook weergeven door: ∀x ((E(x) ∧ x > 2) → ∃y ∃z (P(y) ∧ P(z) ∧ x = y + z)) Merk op dat als we in de logica 1 + 1 schrijven, dit niet gelijk is aan 2: het eerste is een rijtje van drie symbolen, en het laatste bestaat uit slechts een enkel symbool. Het gaat er vooralsnog niet om hoe we dit soort rijtjes symbolen interpreteren. Ook uitdrukkingen als y + z, f(f(m)), en 24 heten in de predikaatlogische taal termen, en anders dan variabelen en constanten zijn het samengestelde termen. We kunnen de taal van de predikaatlogica eenvoudig hiermee uitbreiden, maar in het vervolg gebruiken we termen alleen informeel. ◊ Hiermee is de taal van de predikaatlogica voldoende omschreven. Net als voor de propositielogica bestaan ook voor de predikaatlogica de begrippen ‘deelformule’ en ‘bereik’. Een formule is een deelformule van een formule als die bij de opbouw van die formule gebruikt is; elke formule is tevens een deelformule van zichzelf. In de definitie van predikaatlogische formule zijn de ϕ’s en ψ’s in de diverse stappen dus steeds deelformules. Het bereik van een kwantor is, net als bij de connectieven, het deel van de formule waarop het betrekking heeft.

47

Logica in actie

VOORBEELD 4.14 De deelformules van ¬∃x (P(x) ∧ ∀y (P(y) → y ≤ x)) zijn:

– ¬∃x (P(x) ∧ ∀y (P(y) → y ≤ x)) – ∃x (P(x) ∧ ∀y (P(y) → y ≤ x)) – (P(x) ∧ ∀y (P(y) → y ≤ x)) – P(x) – ∀y (P(y) → y ≤ x) – P(y) → y ≤ x – P(y) – y≤x Merk op dat, bijvoorbeeld, P(y) geen deelformules heeft: y is wel een deel van P(y), maar dit is een term waarmee het predikaat P(y) is opgebouwd. ◊

VOORBEELD 4.15 Het bereik van de kwantor ∀x is onderstreept:

∀x (P(x) → ∃y R(x, y)) ∀x P(x) → ∃y R(z, y)

◊

Vrije en gebonden In een formule als ∀x x2 > y spelen de variabelen x en y een totaal verschilvariabelen lende rol. De formule drukt uit dat alle kwadraten groter zijn dan een

bepaalde waarde y. Die waarde van y mogen we (als er verder geen beperkingen zijn) vrij kiezen; x daarentegen heeft hier geen specifieke waarde: het moet gewoon voor alle getallen zo zijn.

Een variabele v die in een formule voorkomt, is vrij als deze niet binnen het bereik van ∀v of ∃v ligt. Een variabele die niet vrij is, heet gebonden. Dus in de formule ∀x x2 > y is y vrij en x gebonden. Meerdere kwantoren

Bij veel formules komt een kwantor binnen het bereik van een andere kwantor voor. In welke volgorde dat gebeurt, kan veel uitmaken voor de betekenis van de formule.

VOORBEELD 4.16 Een manier om uit te drukken dat er geen grootste priemgetal bestaat, is

∀x (P(x) → ∃y (P(y) ∧ y > x)) en de uitspraak dat er wel een kleinste priemgetal bestaat, kan worden uitgedrukt door ∃y (P(y) ∧ ∀x (P(x) → x ≥ y)) VOORBEELD 4.17 De formule ∃x ∀y x < y drukt uit dat er minstens één x is die kleiner is dan

◊

iedere y; x hangt hier dus niet van y af, maar y wel van x. Daarentegen drukt ∀y ∃x x < y uit dat er voor alle y een x te vinden is die kleiner is dan y. Hier hangt x dus juist wel van y af. In natuurlijke taal is soms onduidelijk welke van beide bedoeld wordt, en dat kan een groot verschil uitmaken. Een standaardvoorbeeld in de logische literatuur is ‘every man loves a

48

Hoofdstuk 4

Predikaatlogica, modellen en programma’s

woman’ (inderdaad, bijna alle logici uit de 20ste eeuw zijn mannen). Dit kan zowel betekenen dat, gegeven een man, er een vrouw is waar die man van houdt; maar het kan ook betekenen dat er een unieke vrouw is waar alle mannen van houden. En daarvoor is het typische voorbeeld in de jaren 1950: Marilyn Monroe. Dit klinkt allemaal wel oubollig maar pas deze analyse nu maar eens toe op ‘Ieder kind wil een spelcomputer voor Sinterklaas’, ‘Iedereen kan premier van Nederland worden’, of ‘Iedere student wil een diploma’. ◊ De predikaatlogische taal is al zoveel sterker dan de propositielogische taal dat het voor veel doeleinden in wiskunde en informatica volstaat. In het volgende hoofdstuk zullen we hiervan verschillende voorbeelden laten zien. Nogmaals formele taal en natuurlijke taal

Leerboeken spreken vaak van ‘vertalen’ van natuurlijke taal in predikaatlogica, alsof de logische taal een soort concurrent van de gewone zou zijn. Dit is echter in het geheel niet de bedoeling van het instrumentarium dat hier is ontwikkeld. Predikaatlogische formules geven een deel van de logische structuur van gewone taal weer, maar zeker niet alles. Ze fungeren eerder als een aangescherpt ‘model’ van wat een bewering informatief zegt, of, zoals de Amsterdamse logicus Frank Veltman het soms uitdrukt, een ‘cartoon’. Wel is waar dat, zo bezien, een rijker systeem als predikaatlogica een veel rijkere vergelijking mogelijk maakt tussen logische theorie en de feitelijke praktijk van menselijk taalgebruik en redeneren. Samenvatting De taal van de predikaatlogica kan spreken over objecten, hun eigenschappen, en hun onderlinge relaties. Ze heeft de volgende grammatica, die al veel interessanter is dan die van de propositielogica, en die invloed heeft op de syntaxis van natuurlijke talen en programmeertalen. Formules zijn opgebouwd uit predikaatsymbolen (zoals P, Q, ..., = , < ), haakjes, variabelen en constanten (en complexer termen die we grotendeels buiten beschouwing laten), connectieven en kwantoren. Er zijn twee (soorten) kwantoren in de predikaatlogica: kwantor

uitspraak

naam

∀ ∃

voor elke er is een

universele kwantor existentiële kwantor

Als ϕ een formule is, dan zijn ∀x ϕ en ∃x ϕ eveneens formules. Het bereik van een kwantor bestaat uit die deelformule waarmee die kwantor combineert tot een formule. Een variabele x komt vrij voor in een formule als die

49

Logica in actie

niet binnen het bereik van een kwantor ∀x of ∃x ligt. Een variabele die niet vrij is, is gebonden. De volle kracht van de predikaatlogica wordt pas ontketend als we kwantoren herhalen, met patronen zoals “voor alle ... er is een...”. Opgaven OPGAVE 4.1

Welke van de volgende uitdrukkingen zijn formules en welke niet? Indien niet een formule, geef dan aan waarom. Indien het wel een formule is, geef aan wat de formule uitdrukt. – ∃x ∀y x = y – ∀x x ≥ y → ∃z y = z – ∀x ∧ ∃z R(x, z) – ∀x x ∧ ∃z z > y – ∀x ∀y ∃z (x > y ∨ y > z)

OPGAVE 4.2

Gegeven is een verzameling V waarop een kleiner-of-gelijk-relatie ≤ is gedefinieerd. Geef de volgende uitspraken weer in predikaatlogische formules met als predikaatsymbolen alleen V en ≤. – Er is een kleinste element in V. – Er is geen grootste element in V. – Er is een maximaal element in V (dat wil zeggen: een element dat niet kleiner is dan enig ander element).

OPGAVE 4.3

Geef in de volgende formules het bereik aan van ∀y, en geef aan welke variabelen vrij en gebonden zijn. (Uitdrukkingen als y + z en y + x zijn zoals gezegd eveneens termen, maar anders dan constanten en variabelen samengestelde termen.) – ∀x ∀y ∃z y + z = x – ∀y ∃z y + z = x – ∀y ∃z y < z ∧ y > x – P(y) → ∀y ∃z y < z

50

HOOFDSTUK 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 omstandigheden 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 predikaatlogische 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 informatief 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.

51

Logica in actie

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 waarheidstabellen van de connectieven nog steeds een rol spelen, kunnen we de waarheidswaarden 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 waarheidswaarden van de deelformules. Wel kunnen we situaties aangeven waarin formules waar zijn. We illustreren dit aan de hand van een eenvoudig 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 aangeduide 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 kunnen 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 propositielogica 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 propositielogica. 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 formules 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

52

Hoofdstuk 5

Predikaatlogica en informatica

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 predikaaten 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 predikaatlogisch model

Een atomaire formule zoals R(a,b) is waar in een model als, gegeven de vertaalsleutel voor a, b en R, de met R in het model corresponderende 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 linkerobject 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 zichzelf 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.

53

Logica in actie

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) onwaar 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 toekennen, 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 interpretatie 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.

54

Hoofdstuk 5

Predikaatlogica en informatica

– ∀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 formule, 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 propositielogica: 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.

55

Logica in actie

Vat in dit model het predikaatsymbool P op als de verzameling priemgetallen {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 vermoeden 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 uitdrukkingen 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, bijvoorbeeld, 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:

56

Hoofdstuk 5

Predikaatlogica en informatica

∀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 veranderingen te beschrijven, zowel informatieveranderingen (die in het volgende hoofdstuk aan bod komen) als feitelijke veranderingen in de wereld (waarbij de waardering van atomaire beweringen telkens verschuift). Een mooi en belangrijk voorbeeld daarvan zijn rekenprocessen, waarbij geheugentoestanden van een computer stapsgewijs veranderen door het uitvoeren van opeenvolgende instructies van een programmeur. Tijdens de uitvoering 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 computerprogramma 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}

◊

57

Logica in actie

Correctheidsbewering

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 programma 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 whiskyglas, 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 hulpvariabele handig. 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

58

Hoofdstuk 5

Predikaatlogica en informatica

waarden a en b hebben, dan zijn die waarden achteraf inderdaad omgewisseld. 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 inzien. Om ruimte te besparen, schrijven we het effect van een programmaregel 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 correctheidsbewering: {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:

59

Logica in actie

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 programma te kunnen bewijzen. In deze methode leiden we correctheidsbeweringen van hele programma’s af door de correctheidsbeweringen van opvolgende opdrachten aan elkaar te koppelen, zoals we bij de voorbeelden hiervoor al informeel hebben gedaan. Predikaatlogica en Tijdens de uitvoering van een computerprogramma speelt dus ten eerste programmaeen 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 programmaverwerking 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.

60

Hoofdstuk 5

Predikaatlogica en informatica

Samenvatting Voor het bepalen van de waarheidswaarde van een formule spelen in de predikaatlogica modellen dezelfde rol als waarderingen in de propositielogica. 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 waaraan 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. Opgaven OPGAVE 5.1

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))

OPGAVE 5.2

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.

61

Logica in actie

OPGAVE 5.3

Geef bij het volgende programma de specificaties die gelden na iedere opdracht. 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,

62

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

HOOFDSTUK 6 Kennis en communicatie De traditionele logica richtte zich voornamelijk op producten van menselijk activiteit, zoals formules, formele gevolgtrekkingen, of bewijzen. De handelende persoon zelf bleef daarbij grotendeels buiten zicht. Maar de laatste decennia is zich een wending aan het voltrekken waarbij informatieverwerkende processen en de daarbij betrokken actoren zelf tot onderwerp van logische theorie worden. De oorsprong van deze wending ligt deels in de filosofie, in de studie van kennis en rationeel handelen, deels ook in de informatica en kunstmatige intelligentie, waar ‘computers’ langzamerhand minder belangrijk zijn dan netwerken van ‘agents’ die samenwerken en allerlei intelligent gedrag vertonen. Dit hangt ook nog eens samen met een stroming in de cognitiewetenschap. Traditioneel wordt gedacht dat het ‘rationele’ of ‘intelligente’ van mensen schuilt in hun vermogens tot redeneren, of andere vermogens die men in isolement kan uitoefenen. Maar het lijkt er steeds meer op dat het wezenlijk biologisch onderscheidende kenmerk van menselijke intelligentie ons vermogen is tot coördinatie en interactie met anderen, of dat nu samenwerking of tegenwerking betreft. Zelfs in de wiskunde zijn de ‘piekmomenten’ argumentatie en discussie tijdens een research seminar. Intelligente interactie is bepaald geen eenvoudig verschijnsel, en vele aspecten ervan zijn dan ook nog heel slecht begrepen. Niettemin zullen we in de volgende hoofdstukken laten zien hoe de logica heel goed in staat is een bijdrage te leveren aan de analyse van bredere scenario’s met complexe ‘meetings of the minds’. Een correcte redenering als ‘uit p en p → q volgt q’ lezen we als ‘als p waar is en als p → q waar is, dan is q ook waar’. Maar ‘waar’ voor wie? Er moet toch een denkende persoon achter zitten die deze redenering als het ware in zijn hoofd maakt. We kunnen het dus ook lezen als ‘als ik p weet is en als ik p → q weet, dan weet ik ook q’. En als u p niet weet, maar alleen p → q weet, dan kunt u niet die conclusie q trekken - maar ik dus wel. Veel logische processen betreffen meer dan een persoon; zelfs redeneren doe je vaak in gezelschap, en dan heet het argumentatie. We kunnen dan over elkaars kennis gaan redeneren, bijvoorbeeld wanneer ik u vertel ‘U weet niet dat ik in Nieuw-Zeeland woon!’ En na u dit verteld te hebben, weet u het wel. Is dat niet paradoxaal? Dit hoofdstuk gaat over de logica van kennis, inclusief kennisverandering als gevolg van communicatieve handelingen zoals het ‘vertellen’ waarvan hiervoor sprake was. Het belangrijke verschil met de voorgaande systemen

63

Logica in actie

is dat we deze kennis ook in de logische taal uit moeten gaan drukken. Dit kan in de modale kennislogica. Vanwege het aspect van het redeneren over de kennis van anderen is dit een heel belangrijke generalisatie van de logische systemen die we totnutoe gezien hebben. Een van de thema’s die we in dit hoofdstuk zullen zien terugkomen, is hoe achtereenvolgende informatieverwerkende stappen steeds opnieuw de logische specificatie van een systeem kunnen inperken of zelfs veranderen. De personen waarvan we de kennis beschrijven noemen we actoren (in het Engels: agent). Bij actoren kan men zich personen maar ook processoren voorstellen. Met kennislogica kan men zogenaamde multi-actorsystemen (‘multi-agent systems’) specificeren. Een multi-actorsysteem is een aantal communicerende computer- of informatiesystemen die - om het even netjes te zeggen - doelgerichte en autonome interactie hebben met elkaar en met een welgedefinieerde omgeving. Daarin spelen kennis en geloof van de actoren een grote rol, noties die meer filosofisch dan wiskundig klinken, maar die heel goed logisch zijn te beschrijven. VOORBEELD 6.1

Een multi-actorsysteem voor voetbal bestaat uit 22 ‘actoren’ (spelers). Een voetballer kan alleen spelers in zijn gezichtsveld waarnemen. Speler a neemt aan dat speler b, een tegenstander, zich achter hem bevindt, omdat dit in de vorige toestand van het spel het geval was, voordat a de bal toegespeeld kreeg. Dit is een redelijke aanname, waarvan a weet dat deze onwaar kan zijn geworden. In werkelijkheid bleek b zich inmiddels elders op het veld te bevinden, buiten a’s gezichtsveld. De spelsituatie waarin b achter a is, is voor a niet te onderscheiden van de situatie waarin b niet achter hem is. Speler a ziet speler c - uit zijn eigen team - voor zich, en speelt c de bal toe om te verhinderen dat b de bal neemt. Wat blijkt: de toegespeelde speler krijgt de bal wel, alleen was het niet c maar d - gelukkig van hetzelfde team: a geloofde dat het c was, maar moet nu zijn kennis herzien. In een ander scenario mist speler c de bal, omdat a en c geen oogcontact hadden tijdens het schot van a: ze hadden geen gemeenschappelijke kennis van de situatie die tot dit schot leidde. ◊ De studie van multi-actorsystemen is een snel groeiend vakgebied op zich. De kennislogica waarmee we de kennis van dergelijke actoren kunnen specificeren presenteren we in dit hoofdstuk.

6.1

Taal en betekenis van de kennislogica

Logica en communicatie is vaak heel concreet te bestuderen in situaties die we allemaal goed kennen, zoals kaartspelletjes waarbij onze informatie gaandeweg verandert.

64

Hoofdstuk 6

VOORBEELD 6.2

Kennis en communicatie

U houdt drie kaarten in handen. De kaarten zijn rood, wit, en blauw. Nu draait u ze om. De achterkanten zijn, zoals bij speelkaarten te doen gebruikelijk, niet van elkaar te onderscheiden. U schudt de kaarten, en trekt een kaart. Dit is de rode kaart. Van de andere twee kaarten legt u er één links voor u op tafel, en de andere kaart rechts voor u. Welke van de twee is nu de witte kaart, en welke de blauwe? Laat p staan voor de propositie ‘de linkerkaart is de witte kaart’. Dan zijn er twee mogelijkheden: p is waar, of p is onwaar. In het laatste geval is de kaart links voor u de blauwe kaart, en de rechterkaart de witte kaart. U kunt deze twee situaties niet van elkaar onderscheiden, ook al (wat u niet weet) is de werkelijke situatie dat de linkerkaart wit is. ◊ Een mogelijke situatie kunnen we identificeren met een propositielogische waardering. Er zijn dus twee mogelijke situaties. Als p waar is hebben we de waardering w zodat w(p) = 1 en als p onwaar is hebben we de waardering w’ zodat w’(p) = 0. Voordat u onder de kaarten op tafel gekeken hebt, kan het dus zo zijn dat de linkerkaart wit is, maar dat u het toch voor voorstelbaar houdt dat deze blauw is. Met andere woorden: u vindt dat best mogelijk. De uitspraak ‘het is mogelijk dat de linkerkaart op tafel blauw is’, heeft als bijzondere eigenschap dat ze waar is onafhankelijk van de waarheid van ‘de linkerkaart op tafel is blauw’; of anders gezegd, de waarheid ervan is geen functie van de waarheid van de bewering ‘de linkerkaart op tafel is blauw’. ‘Het is mogelijk dat’ is dus niet een propositioneel connectief zoals ‘en’, ‘of’, en ‘als, ..., dan’. Voor die connectieven geldt immers dat we weten of de hele bewering waar is, wanneer we weten of de subformules die door het connectief verbonden worden waar zijn. Voor propositielogische connectieven is er een waarheidsfunctie. De logica waarin we ‘het is mogelijk dat’ expliciet in de taal modelleren, is een zogenaamde modale logica, en ‘het is mogelijk dat’ noemen we een modaliteit of modale operator. Er zijn meerdere modale logica’s. Wij presenteren de zogenaamde kennislogica of epistemische logica. In al die modale logica’s speelt het een essentiële rol dat gegeven de werkelijke situatie meerdere situaties mogelijk kunnen zijn. Die mogelijke situaties noemen we ook wel voorstelbaar.

Voorstelbaar

We kunnen de onzekerheid over de werkelijke situatie in voorbeeld 6.2 weergeven als een binaire relatie tussen situaties. De werkelijke situatie is w. Vanuit die situatie kunt u zich voorstellen dat w’ de situatie is. ‘Gegeven w, is w’ voorstelbaar’ kunnen we zien als ‘het paar (w, w’) is in de relatie R’, waarbij R een tweeplaatsige relatie is. Deze relatie heet de voorstelbaarheidsrelatie. De relatie R bevat nog meer paren van situaties. U sluit immers ook niet uit dat w zelf het geval is. Dus het paar (w, w) zit ook in de relatie R. Evenzo, als w’ het geval was geweest, zijn zowel w als w’ voorstelbaar: (w’, w) en (w’, w’) zitten ook in R.

65

Logica in actie

We kunnen een en ander weergeven op dezelfde manier als in een model voor de predikaatlogica. Alleen zijn de objecten nu waarderingen, en staan ze niet voor individuen of getallen, zoals Jan, Piet, 1, 2 en 3. In een plaatje is het als volgt:

‘Voorstelbaar’ moeten we hier vrij nauw opvatten. Het betekent dus eerder ‘voorstelbaar gegeven mijn beperkte waarneming en onvolledige kennis van de wereld om mij heen’ dan ‘in principe denkbeeldig in mijn fantasie’. VOORBEELD 6.3

Ik kan me niet voorstellen dat mijn gebrilde gesprekspartner tegenover me geen bril op heeft: ik zie immers dat hij wel een bril draagt. Maar van de mij onbekende binnenkomer die achter mij met een luide roep “Hi, mate” het café binnenwandelt, kan ik me zowel voorstellen dat zij een bril draagt, als dat zij geen bril draagt. ◊ Onzekerheid over de feitelijke situatie beschrijven we vaak met beweringen waarin ‘weten’ of ‘niet weten’ gebruikt wordt: ‘ik weet niet of de witte kaart links of rechts ligt’, ‘ik weet dat een van beide kaarten voor me wit is’, en ‘ik weet niet of de binnenkomer een bril draagt’. Deze modaliteit gaan we nu in logische taal weergeven. Voor ‘ik weet dat ϕ’ schrijven we Kϕ. De letter K komt van het Engelse ‘Know’. We kunnen deze logische operatie weer in combinatie met de reeds bekende propositionele connectieven gebruiken. Bijvoorbeeld ¬Kϕ voor ‘het is niet zo dat ik ϕ weet’, dat wil zeggen, ‘ik weet niet dat ϕ’. Ten slotte staat ¬K¬ϕ voor ‘ik weet niet dat ϕ niet zo is’ waarvoor we meestal zeggen ‘ik houd voor mogelijk dat ϕ’ of ‘ik kan me voorstellen dat ϕ’. Een zin als ‘ik weet niet of de binnenkomer een bril draagt’ is eigenlijk een afkorting van ‘ik weet niet dat de binnenkomer een bril draagt en ik weet ook niet dat de binnenkomer niet een bril draagt’, dat wil zeggen, als p voor brildragen staat: ¬Kp ∧ ¬K¬p.

DEFINITIE 6.1

Taal en betekenis van de kennislogica Aan de inductieve definitie van de taal van de propositielogica voegen we nog één inductieve clausule toe: als ϕ een formule is, dan is Kϕ dat ook. Dit definieert de taal van de kennislogica. Deze taal kunnen we interpreteren op modellen waarvan de afzonderlijke elementen (‘situaties’) voor propositielogische waarderingen staan. Tussen deze situaties is een voorstelbaarheidsrelatie gegeven. Een bewering Kϕ is waar in een gegeven situatie als ϕ waar is in alle vanuit de gegeven situatie voorstelbare situaties.

66

Hoofdstuk 6

Kennis en communicatie

VOORBEELD 6.4

In voorbeeld 6.2 gaven we de bewering ‘de linkerkaart is wit’ weer door p. Neem verder aan dat de linkerkaart ook echt wit is. Stel dat ‘ik’ de actor is. We kunnen nu de volgende beweringen onderscheiden (over de situatie w): – Ik weet dat de linkerkaart wit is: Kp. Dit is onwaar als de werkelijke situatie w is, want ik kan me een situatie w’ voorstellen waarin de linkerkaart blauw is (dus ¬p waar). – Ik weet niet of de linkerkaart wit is: ¬Kp ∧ ¬K¬p. Dit is waar als de werkelijke situatie w is. Ik kan me van daaruit een situatie w’ voorstellen waarin de linkerkaart blauw is, maar ik kan me ook een situatie w voorstellen waarin de linkerkaart wit is. – Ik ben me ervan bewust dat ik niet weet of de linkerkaart wit is: K(¬Kp ∧ ¬K¬p). Ook dit is waar in situatie w. Namelijk omdat de door de eerste K-operator gebonden bewering ¬Kp ∧ ¬K¬p waar is in iedere vanuit w voorstelbare situatie, namelijk zowel in w (zie de vorige bewering) als in w’ (en dit gaat net zo ...). ◊

VOORBEELD 6.5

We gaan weer voetballen. Ik heb geen ogen in mijn achterhoofd. Ik denk zeker te weten dat van het andere team Jan achter mij staat. Maar in feite staat Nicolien achter me. Laat ‘Jan staat achter me’ worden gerepresenteerd door de propositie p. Dan kunnen we deze situatie weergeven als volgt:

Propositie p is alleen waar in w’. De werkelijke situatie is w: p is onwaar. De enige voorstelbare situatie is die in w’: er is een pijl van w naar w’, en geen andere pijl vanuit w. Dus ik ‘weet’ dat Jan achter me staat. In dat geval spreken we liever van ‘denken te weten’, of ‘geloven’. Want in werkelijkheid staat Nicolien achter me. Dit kan ik me echter niet voorstellen. Tevens hebben we een pijl van w’ naar zichzelf in de figuur. Deze is er, omdat ik, ondanks dat mijn kennis dus eigenlijk foutief is, mij bewust ben van wat ik geloof en niet geloof: de bewering KKp is eveneens waar in situatie w. Dit geeft weer dat ik weet dat ik weet dat Jan achter me staat, oftewel, in termen die we intuïtief voor zo’n scenario gebruiken, ik ben me ervan bewust dat ik geloof dat Jan achter me staat. Als je iets weet, dan ‘hoort’ het waar te zijn, daarom spreken we hier liever van ‘menen te weten’ of ‘geloven’. ◊ 6.2

Kennislogica voor meer dan een actor

We kunnen kennislogica bestuderen voor een enkele persoon. Maar de kracht van dit systeem schuilt er nu juist in dat we ook het samenspel van meerdere personen kunnen beschrijven. En juist dit laatste is essentieel om communicatie te begrijpen. Door u een vraag te stellen geef ik u doorgaans de informatie dat ik het antwoord niet weet. En zelfs, dat ik het u vraag

67

Logica in actie

betekent dat ik denk dat u het antwoord weet: mijn kennis over uw kennis is dus van wezenlijk belang om ons gedrag te regelen. In de cognitiewetenschap heet dit belangrijke verschijnsel ‘theory of mind’, het vermogen je in de informatie van een ander te verplaatsen. Daarbij komen zelfs hogere ‘stapelingen’ voor dan 2, zoals we spoedig zullen zien. Nu de formele details voor kennis van meerdere actoren. Als we de kennisoperator K indiceren, waarbij Kiϕ betekent: ‘persoon/processor i weet dat ϕ’, kunnen we de eventueel van elkaar verschillende kennis van meerdere actoren beschrijven. Met iedere kennisoperator Ki correspondeert dan een voorstelbaarheidsrelatie Ri. Met ‘stapeling’ van verschillende operatoren Ki kunnen we uitdrukken dat processoren kennis over elkaar hebben. Bijvoorbeeld, Ka¬Kbp wil zeggen dat processor a weet dat processor b propositie p (zoals ‘de lokale variabele x heeft waarde 3’) niet weet, terwijl Ka(Kbp ∨ Kb¬p) tot uitdrukking brengt dat a weet of b p weet. Dit soort interactie is van belang in informaticatoepassingen, waar men kennislogica gebruikt om te redeneren over het effect van communicatieprotocollen tussen processoren. Hoe kan een kennislogisch model voor meerdere actoren er uitzien? Bijvoorbeeld, als processor a toegang heeft tot alle informatie van processor b, komt dit overeen met het axioma Kbϕ → KaKbϕ. Een andere, niet ongebruikelijke situatie is die waarin ieder proces alleen zijn eigen toestand kent (bijvoorbeeld, de waarde van een variabele die in dat proces is opgeslagen of berekend wordt), en dat dit gemeenschappelijke kennis is voor alle processen. Zoiets staat wel bekend als distributief systeem. VOORBEELD 6.6

68

Distributieve systemen Er zijn twee processoren a en b. Propositieletter p beschrijft dat de waarde van processor a gelijk aan 1 is, en ¬p dat deze waarde 0 is. Propositieletter q beschrijft de toestand van processor b. Beide processoren kennen alleen hun eigen toestand. Dit komt overeen met het volgende model. Hierin hebben we de situaties namen gegeven die al ‘verraden’ wat daar de waardering is: we schrijven 10 wanneer p waar en q onwaar is, enzovoorts. Als we een verbinding labelen met a of b, bedoelen we dat het begin- en eindpunt van deze pijl in de relatie Ra dan wel Rb zit. In plaats van een pijl van 00 naar 10 en een pijl van 10 naar 00 tekenen we een pijl met twee gepunte uiteinden. In plaats van een a-pijl van 10 naar zichzelf en een b-pijl van 10 naar zichzelf tekenen we maar een pijl van 10 naar zichzelf, die voor beide staat.

Hoofdstuk 6

Kennis en communicatie

In situatie 11 van het model geldt bijvoorbeeld dat Kap (processor a weet dat zijn toestand 1 is), dat Ka¬Kbp (a weet dat b dat niet weet), en dat ¬Ka¬Kbq (a houdt voor mogelijk dat b weet dat q waar is). Dat de processen a en b hun eigen toestand kennen wordt uitgedrukt door p → Kap en ¬p → Ka¬p, en door q → Kaq en ¬q → Ka¬q. U kunt ook nagaan dat het model het schema ¬Ka¬Kbϕ → Kb¬Ka¬ϕ waar maakt. ◊ VOORBEELD 6.7

Kaartverdelingen Drie spelers 1, 2 en 3 trekken elk een kaart uit een pak van drie kaarten rood, wit en blauw. Met rwb geven we de kaartverdeling weer waarbij speler 1 rood heeft, speler 2 wit, en speler 3 blauw, enzovoorts. Er zijn zes mogelijke kaartverdelingen. Dit zijn dus de verschillende mogelijke situaties. Spelers kunnen alleen hun eigen kaart inzien. Van de anderen zien ze dat die ook maar één kaart hebben, en ze weten dat dat niet hun eigen kaart kan zijn. De kennis van de spelers is weer te geven in het model hierna. Alle situaties zijn voorstelbaar als ze werkelijk het geval zijn, voor alle spelers: de reflexieve pijlen hebben we daarom niet weergegeven.

Stel propositieletter r1 staat voor ‘speler 1 heeft de rode kaart’, enzovoorts. In situatie rwb geldt bijvoorbeeld dat K1r1 (speler 1 kent zijn eigen kaart) en dat K1(w2 ∨ b2) (speler 1 weet dat 2 de witte of de blauwe kaart heeft). Overal in het model geldt dat r1 → ¬K3K1(w2 ∨ b2) (als 1 de rode kaart heeft, dan weet 3 niet dat 1 weet dat 2 de witte of de blauwe kaart heeft). Dit voorbeeld is een generalisatie van het drie-kaartenvoorbeeld in voorbeeld 6.2, waarbij de kenner speler 1 is, de kaart linksvoor op tafel de kaart is die door speler 2 wordt vastgehouden, en de kaart rechtsvoor door speler 3 wordt vastgehouden. De tafel kan niet denken, maar de spelers wel! De propositie p die in dat voorbeeld stond voor ‘de linkerkaart voor mij is wit’ hebben we nu gerepresenteerd als w2. Het bovenste deel rwb ←1→ rbw van de figuur geeft precies de situatie in voorbeeld 6.2 weer. ◊

69

Logica in actie

6.3

Communicatie

In een gegeven situatie waarin we kennis gemodelleerd hebben kan nieuwe informatie binnenkomen, hetzij van buiten af, hetzij door communicatie van de actoren onderling. Een speciale vorm van communicatie is een zogenaamde publieke bekendmaking. We nemen daarvoor aan dat de nieuwe informatie hardop uitgesproken wordt in aanwezigheid van alle actoren die we in het systeem gemodelleerd hebben, zodat ze het allemaal horen, en van elkaar weten dat ze het allemaal horen, enzovoort. Een ander voorbeeld van een dergelijke gebeurtenis is als we allemaal tegelijk een observatie doen, bijvoorbeeld dat de zon ondergaat boven de Noordzee. Deze nieuwe informatie verwerken we door de gegeven situatie aan te passen. De aanpassing bestaat uit een mechanisme dat we al hebben gezien in hoofdstuk 3 over propositielogica: we verwijderen alle situaties uit het model waarin de verstrekte informatie onwaar is. We spreken ook wel van een ‘update’ van het model. We kunnen verschillende updates ook achtereenvolgens uitvoeren, wat steeds opnieuw weer tot kennisverandering kan leiden. Leren gebeurt in vele stappen. VOORBEELD 6.8

In situatie rwb van het model van voorbeeld 6.7 zegt speler 1: “Ik heb rood.” Dit komt overeen met een update op r1. We beperken het model nu tot de situaties waarin 1 rood heeft. Dit zijn alle situaties in het model waar r1 waar is: rwb en rbw. Het resultaat is als volgt. We tekenen de reflexieve pijlen deze keer wel, voor alle duidelijkheid.

In deze structuur geldt dat zowel 2 als 3 nu weten wat de kaartverdeling is. Er is nu immers geen alternatief meer. Speler 2 heeft de kaartverdeling geleerd omdat situatie bwr nu niet meer mogelijk is. Speler 3 heeft de kaartverdeling geleerd omdat situatie wrb nu niet meer mogelijk is. ◊ Oppervlakkig gezien lijkt ‘publiekelijk zeggen dat ϕ geldt’ nogal veel op ‘waarmaken dat ϕ’. Maar dat is niet zo. Het volgende voorbeeld laat dit zien: een bewering ϕ kan waar zijn, en onwaar worden omdat je zegt dat het waar is. Dit klinkt raar. Het komt omdat je ook dingen mag zeggen over je eigen kennis en die van andere spelers. VOORBEELD 6.9

70

In situatie rwb van het model van voorbeeld 6.7 zegt speler 1: “Speler 2 weet niet dat ik rood heb.” Zo’n mededeling is alleen informatief als speler 1 hiermee eigenlijk bedoelt: “Ik heb rood en speler 2 weet dit niet.” Dit is dus een update op r1 ∧ ¬K2r1. Deze bewering is alleen waar in rwb en in rbw. Het resulterende model is dus opnieuw het model hiervoor. Hierna geldt dat speler 2 wel weet dat 1 rood heeft: K2r1.

Hoofdstuk 6

Kennis en communicatie

Na uitvoer van de update geldt dus het tegendeel van de uitgesproken bewering r1 ∧ ¬K2r1, want ¬(r1 ∧ ¬K2r1) is logisch equivalent met ¬r1 ∨ ¬K2r1), en dat volgt uit K2r1.

◊

We zien dus dat informatieoverdracht in communicatie verrassende eigenschappen heeft. Maar om die systematisch bij te houden dient dan ook juist ons logische systeem. We besluiten met nog een voorbeeld van update tussen meerdere actoren. VOORBEELD 6.10 Ten slotte het resultaat als in de beginsituatie speler 1 zegt “Ik heb de witte

kaart niet.” Deze bewering is waar in de situaties rwb, rbw, brw, en bwr. Het resulterende model is nu:

In dit model geldt dat in situatie rwb speler 3 wél weet wat de kaartverdeling is, maar dat speler 2 dat nog steeds niet weet. Dit is begrijpelijk, want omdat speler 2 de witte kaart heeft, was de uitspraak van speler 1 voor hem niet zo informatief: dat wist ‘ie al! Maar speler 2 heeft toch iets geleerd, bijvoorbeeld dat speler 3 nu weet wat de kaartverdeling is. ◊ Samenvatting In de kennislogica beschrijven we de kennis van verschillende actoren of processen over de feiten en over elkaar. De kennislogica is een uitbreiding van de propositielogica. In de logische taal is er nu ook een constructie Kϕ die staat voor ‘de actor weet dat ϕ’, die het mogelijk maakt kennis van verschillende actoren gezamenlijk te beschrijven. De kennislogica wordt geïnterpreteerd op relationele structuren die bestaan uit mogelijke situaties. Iedere situatie wordt gekarakteriseerd door een waardering. Vanuit een gegeven situatie kunnen andere situaties voorstelbaar zijn. De formule Kϕ is waar in een gegeven situatie als ϕ waar is in alle vanuit die situatie voorstelbare situaties. Met name kan deze logica ook situaties beschrijven met ‘gestapelde kennis’, waarbij verschillende actoren verschillende informatie over elkaar hebben: hetgeen de basis is van succesvolle menselijke communicatie en interactie. We kunnen met dit soort modellen ook informatieve handelingen beschrijven die kennis veranderen, met name bekendmakin-

71

Logica in actie

gen (‘updates’), die alle situaties elimineren waarin de meegedeelde formule onwaar is. Opgaven OPGAVE 6.1

Geef de volgende beweringen weer in logische taal, en laat zien dat ze in toestand rwb van voorbeeld 6.7 waar zijn. Met ‘kan zich voorstellen’ bedoelen we ‘weet niet dat niet’. – Speler 1 weet niet dat speler 2 wit heeft. – Speler 1 weet niet of speler 2 wit heeft. – Speler 1 kan zich voorstellen dat speler 3 zich kan voorstellen dat speler 1 niet de rode kaart heeft.

OPGAVE 6.2

Gegeven is het model voor drie spelers 1, 2, en 3 die ieder een van de kaarten r, w en b vasthouden. – Bereken dat K1(K2r2 ∨ K2w2 ∨ K2b2) overal geldt (speler 1 weet dat speler 2 zijn eigen kaart kent). – Als bij de kaartverdeling rwb speler 1 zegt dat hij wit niet heeft, dan weet daarna 3 wel maar 2 nog steeds niet dat 1 rood heeft; speler 1 kan zich echter voorstellen dat 2 dat wel weet. Laat door toepassing van definitie 6.1 zien dat in de resulterende structuur (zie voorbeeld 6.10) de volgende formules inderdaad allemaal waar zijn: K3r1, ¬K2r1, ¬K1¬K2r1.

OPGAVE 6.3

Er zijn twee actoren a en b, waarvan a een stip op het voorhoofd heeft. Als je een stip op het voorhoofd hebt, kun je dat niet bij jezelf zien maar wel bij anderen. Eerst zegt een buitenstaander: “Ten minste een van jullie is bestipt.” Dan zegt a dat hij weet dat hij bestipt is. Maak een model voor de situatie waaruit dit volgt. De begintoestand bestaat uit vier verschillende situaties, namelijk voor alle combinaties van bestipt en niet bestipt zijn voor de twee actoren. Stel dat in dit geval zowel a als b bestipt zijn. Nadat de buitenstaander zegt: “Ten minste een van jullie is bestipt,” zegt a: “Ik weet niet of ik bestipt ben.” Daarna zegt b dat hij weet dat hij bestipt is. Leg uit waarom de beweringen naar waarheid gemaakt konden worden en bereken de achtereenvolgende updates.

72

HOOFDSTUK 7 Complexiteit van berekeningen We hebben nu al een paar keer gezien dat logica nauw verbonden is met processen die informatie bewerken en overdragen. Het proces bij uitstek met deze informatieve functie is rekenen, en daarom gaan we deze connectie in dit hoofdstuk eens wat preciezer aan het licht brengen. Niet alleen omdat het onderwerp praktisch van belang is in de informatietechnologie, maar ook omdat dit samenhangt met diepe vragen over complexiteit van processen van de meest uiteenlopende aard. Redeneren en rekenen liggen dicht bij elkaar. De twintigste-eeuwse contacten tussen logica en informatica gaan terug op een oudere historische traditie van redeneermachines. Zo werken de digitale circuits van een moderne computer in wezen volgens de negentiende-eeuwse propositielogica van George Boole. Maar naast dit rekenaspect is er nog een tweede kant aan het contact tussen logica en informatica. De logische talen die we gezien hebben geven manieren om diverse soorten van informatie exact uit te drukken: propositioneel, met kwantoren, en modaal (en er zijn nog vele andere mogelijkheden). Daarmee wordt die informatie voor berekening vatbaar. In dit hoofdstuk staat dat genre van berekening centraal. In de informatica gaat het om het juiste samenspel tussen de geschikte weergave of representatie van informatie (in getalstructuren, gegevensbanken, of andere vormen) en efficiënte berekening met die gegevens, met andere woorden om de interactie tussen, in het Engels: ‘representation + computation’. En in ons cognitief gedrag vindt een vergelijkbaar samenspel plaats van informatieverwerking met een beperkte hoeveelheid tijd en aandacht. Deze balans kan men goed bestuderen in het gedrag van logische systemen, die een evenwicht moeten vinden tussen logische uitdrukkingskracht en rekencomplexiteit. In het algemeen geldt: hoe rijker de taal, hoe moeilijker het rekenproces voor de centrale logische taken. De bedoeling van dit hoofdstuk is om enig inzicht te geven in deze balans, die vooral typerend is voor logische systemen die ontwikkeld zijn in de buurt van de informatica. In paragraaf 7.1 introduceren we de relevante logische taken: bewijzen, vervullen, evalueren en vergelijken. In de paragrafen 7.2 en 7.3 geven we enige voorbeelden van de complexiteit van taken in de standaard logische systemen die we gezien hebben.

73

Logica in actie

7.1

Bewijzen, vervullen, evalueren en vergelijken

In dit boek zijn heel uiteenlopende logische taken besproken. Het berekenen van een waarheidswaarde van een formule in een gegeven model is zo’n taak, maar ook het vinden van een model voor een gegeven stel formules. We zetten een aantal van deze taken nog eens iets uitvoeriger op een rij. Om te beginnen hebben we bewijstaken. Bewijstaken Veel theoretische en praktische problemen komen erop neer dat bepaald (theorem proving) moet worden of een bewering uit een andere volgt. We kunnen dit bijvoor-

beeld zien bij het automatisch vinden van wiskundige stellingen die volgen uit gegeven axioma’s. Zo kunnen we een bewijs van de stelling van Pythagoras (hoofdstuk 1) in principe mechanisch vinden gegeven een aantal basisaannames (de postulaten van Euclides) en de afleidingsregel ‘modus ponens’ (ϕ, ϕ → ψ ⇒ ψ). Dit soort logische geldigheidsvragen wordt gesteld binnen het kader van een formeel bewijssysteem en de gangbare term hiervoor is stellingbewijzen (in het Engels: ‘theorem proving’). Aan de complexiteit van bewijzen besteden we geen aandacht, behoudens een voorbeeld.

VOORBEELD 7.1

Als p bekend is dan kunnen we met twee implicaties p → q en q → r, en de ‘modus ponens’-regel bewijzen dat r. Eerst volgt uit p en p → q dat q, en uit q en q → r volgt dan r. Dat zijn maar twee stappen, lekker snel dus en niet zo complex. Een probleem in zo’n bewijs is dat q niet voorkomt in de aanname p en ook niet in de te bewijzen conclusie r, en dat het daarom toch heel complex kan worden, namelijk omdat we uit meerdere beschikbare implicaties nu juist p → q en q → r moeten selecteren, en niet twee van tienduizenden andere beschikbare implicaties p → q1, p → q2, ... De complexiteit van bewijzen heeft dus niet alleen te maken met de lengte van het bewijs dat we uiteindelijk vinden, maar ook (en zelfs vooral) met de duur van de zoektocht naar zo’n bewijs. Een ander kort bewijs is dat van p ∧ r ⇒ p ∨ q: uit p ∧ r volgt p, en uit p volgt de zwakkere disjunctie p ∨ q. In dit bewijs is de tussenstap p een deelformule van het uitgangspunt en een deelformule van de te bewijzen conclusie. Als we bij het zoeken naar bewijzen zo’n restrictie kunnen aannemen, is het zoeken veel sneller te verrichten. Zulke bewijzen heten ‘cut-free’ (zonder snede), de stap p → q, q → r ⇒ p → r waarin propositieletter q links wel staat maar rechts niet kunnen we zien als het ‘wegsnijden’ van q. ◊

Vervulbaarheidstaken (satisfiability)

In gewone conversatie ‘bewijzen’ we zelden formeel. Het gaat er dan meer om, consistente informatie te verstrekken. Dit ‘consistency management’ heeft als logische kernvraag of een gegeven verzameling beweringen een model heeft. Dit is de zogenaamde vervulbaarheid van die verzameling, in het Engels: ‘satisfiability’. Dezelfde vraag doet zich in een ander jasje voor bij ontwerpen, bijvoorbeeld het ontwerp van een digitaal circuit dat moet

74

Hoofdstuk 7

Complexiteit van berekeningen

voldoen aan vooraf gegeven Boolese specificaties, of dat van een multiactorsysteem dat moet voldoen aan vooraf gegeven kennislogische eisen. Evaluatietaken (model checking)

In wezen eenvoudiger dan vervulbaarheidstaken, maar ook zeer nuttig, zijn evaluatietaken (ook wel bekend onder de naam verificatietaken). Hoe bepalen we de waarheidswaarde van een formule in een model? Dit is de controle of een gegeven structuur voldoet aan zekere eisen die we van tevoren hebben gesteld. In het Engels: ‘model checking’. Het checken van specificaties voor een gegeven proces is van deze aard, evenals het bepalen van eigenschappen van een circuit van Boolese schakelingen.

VOORBEELD 7.2

Logische taken kunnen ook tezamen voorkomen in eenzelfde situatie. Zo moet in de rechtszaal de aanklager bewijzen dat de beklaagde schuldig is: een bewijstaak voor een conclusie uit de voorliggende gegevens. Maar de verdediger heeft slechts de vervulbaarheidstaak om een scenario te schetsen dat past bij die gegevens, maar waarin zijn cliënt onschuldig is. Ook evaluatietaken kunnen voorkomen, namelijk bij het vaststellen van het toelaatbare bewijsmateriaal. ◊

Vergelijkingstaken (model comparison)

Er zijn nog heel andere genres taken. Heel belangrijk zijn bijvoorbeeld vergelijkingstaken. Wanneer zijn twee Boolese circuits equivalent, of twee modellen voor de predikaatlogica, of twee multi-actorsystemen - in die zin dat ze dezelfde formules van de relevante taal waar maken? Dit soort informatie is cruciaal bij het vereenvoudigen van voorgestelde machines of informatieprocessen.

VOORBEELD 7.3

De onderstaande figuur bevat twee verschillende modellen, die toch dezelfde informatie uitdrukken, namelijk dat zowel actor a als actor b niet weet of p (en dat ze dit ook van elkaar weten, enzovoort).

We kunnen dit inzien door bijvoorbeeld in de p-situatie linksboven te beginnen, en dan met een a-pijl naar de ¬p-situatie rechtsboven te gaan. In de rechterfiguur kunnen we zo’n overgang simuleren door in de p-situatie onder te beginnen, en naar de ¬p-situatie boven te gaan met een a-pijl. Dit kunnen we vanuit iedere situatie doen, voor a-pijlen en b-pijlen, waarbij we bovendien ervoor blijven zorgen dat de waarheidswaarde van p blijft corresponderen: of allebei waar, of allebei onwaar. Evenzo kunnen we een stap die we eerst rechts maken links simuleren. Zo’n simulatie twee kanten op heet een bisimulatie. Als dit kan, dan volgt hieruit dat iedere kennislo-

75

Logica in actie

gische formule die rechts waar is, ook links waar is, en andersom. De modellen hebben dus dezelfde informatie-inhoud: we kunnen ze niet van elkaar onderscheiden in de taal van de kennislogica. ◊ Hoe moeilijk zijn logische taken?

7.2

Onze volgende vraag betreft de moeilijkheid van deze logische taken. Een evaluatietaak in de propositielogica, dat wil zeggen het uitrekenen van een waarheidswaarde in een waarheidstabel, lijkt op het eerste gezicht eenvoudig, en gelukkig is dat ook inderdaad zo. Een rij in een waarheidstabel komt overeen met een propositielogische waardering. In die rij vullen we één voor één de waarheidswaarden in voor alle subformules van een gegeven formule. Dit kost ons evenveel ‘tijd’ (stappen) als het aantal subformules van die formule. En het aantal subformules is weer ongeveer gelijk aan de lengte van die formule: het aantal symbolen. Men zegt wel dat deze evaluatietaak in de orde van grootte is van de lengte van de formule. Evaluatie in de propositielogica kost dus zogenaamde lineaire tijd, gemeten in de lengte van de invoerformule. Daarentegen is het is veel lastiger om te bepalen of een formule een model heeft (satisfiability), omdat we nu in het ergste geval alle rijen in de waarheidstabel zullen moeten nagaan. Dit is een exponentieel aantal, namelijk alle combinaties van nullen en enen voor de propositieletters in de formule. VOORBEELD 7.4

We kijken nog eens naar de waarheidstabel voor de formule p ∧ ¬q van voorbeeld 3.4 p

q

p

∧

¬

q

1 1 0 0

1 0 1 0

1 1 0 0

0 1 0 0

0 1 0 1

1 0 1 0

Hierin komen twee propositieletters voor. Deze formule is vervulbaar want er is een waardering waarvoor de formule waar is, namelijk als p waar is en q onwaar. Om te bepalen of een formule waarin twee propositieletters voorkomen vervulbaar is, moeten we in het ergste geval vier rijen (namelijk twee tot de macht van deze twee propositieletters) van de waarheidstabel onderzoeken. Maar voor deze formule zijn we bij de tweede rij al klaar! Complexiteitsanalyses gaan altijd uit van het ergste dat ons kan overkomen. In de praktijk kan het meevallen. Om te bepalen dat de waardering waarin p waar en q onwaar is, een model is van de formule (‘model checking’) moeten we één keer de waarde van

76

Hoofdstuk 7

Complexiteit van berekeningen

een negatie bepalen, namelijk de negatie van q, en één keer de waarde van een conjunctie, die van p en ¬q. De lengte van een formule is het aantal symbolen waar de formule uit bestaat. De formule p ∧ ¬q bestaat uit vier symbolen, of zes, als we de haakjes van de conjunctie meetellen, als in (p ∧ ¬q). Een formule kan natuurlijk nooit meer logische connectieven hebben dan het aantal symbolen. In het ergste geval is het aantal symbolen de lengte van de formule min één, zoals in ¬¬¬¬¬¬p. Daarom kost een evaluatietaak in de propositielogica lineaire tijd. ◊ VOORBEELD 7.5

Nu willen we bepalen of de formule p1 ∧ p2 ∧ ... ∧ p99 ∧ (p100 ∧ ¬p100) vervulbaar is. Hierin komen 100 propositieletters voor. Als we blind gaan zoeken, moeten we dus een waarheidstabel met 2100 rijen gaan aflopen; 2100 is ongeveer 1030 (want 210 = 1024) dus met een minuut rekentijd per rij komen we dan met gemak boven de ouderdom van het heelal uit. Niettemin ziet u meteen dat de formule onvervulbaar is, vanwege de contradictie p100 ∧ ¬p100 aan het eind. En dit ‘zien’ is ook met geringe mechanische moeite uit te voeren. Er zijn vele methoden om sneller vervulbaarheid te bepalen. Dit is zelfs een belangrijk specialisme in de informatica (Boolean satisfiability checking, SAT checking). ◊ Soortgelijke vragen rijzen bij de rijkere taal van de predikaatlogica. Hoe moeilijk is het bijvoorbeeld om voor een formule ∀x ∃y R(x, y) met twee kwantoren te bepalen of deze waar is in een gegeven model van n objecten? Op het eerste gezicht is het antwoord hierop: dit duurt n2 stappen. In het ergste geval moeten we namelijk alle (n) objecten één voor één voor x invullen, en voor elk daarvan weer alle (n) objecten proberen als mogelijke y. In het algemeen verwachten we dus exponentiële tijd voor de evaluatie van een formule met kwantoren, als we het model en die formule als invoerparameters nemen: namelijk het aantal objecten van het model tot de macht van de grootste ‘nesting’ van kwantoren in de formule. Maar ook hier kunnen verrassingen optreden die tot lagere complexiteit leiden! Het nu volgende voorbeeld bevat zo’n verrassing.

VOORBEELD 7.6

Vind de beroemdheid Dit instructieve voorbeeld is van Anne Kaldewaij. Een ‘beroemdheid’ is iemand die niemand anders kent, maar wel door ieder ander wordt gekend. Hoe bepalen we zo snel mogelijk of een groep een beroemdheid heeft, en wie dat is? Het gaat hier om de vraag of in een gegeven model de predikaatlogische formule ∃x ∀y (y ≠ x → (K(y, x) ∧ ¬K(x, y))) waar is. Omdat er een stapeling van twee kwantoren is, zou men verwachten dat dit kwadratische tijd kost. Het kan echter lineair! We geven daartoe aan iedereen een rood balletje, voor ‘potentiële beroemdheid’. Nu herhalen we de volgende procedure: Zolang er nog minstens twee mensen met rode balletjes zijn, pak er dan twee, zeg x en y, en kijk of x de persoon y kent. Zo ja, neem dan x het rode

77

Logica in actie

balletje af, zo nee, neem y het balletje af. De unieke overblijver met een balletje wordt nu nog even getest op de eigenschap beroemdheid te zijn. Dit hele proces loopt hoogstens drie keer door het domein: namelijk twee keer om de overblijver met het rode balletje te bepalen (twee objecten kiezen, net zo vaak als het aantal objecten), en één keer om voor alle anderen te testen of zij die overblijver kennen en de overblijver hen niet kent. Daarmee is de complexiteit lineair. ◊ Van de complexiteit van vergelijkingstaken geven we geen concreet voorbeeld. We formuleren nog eens de drie besproken typische taken van een logische taal: – Model checking (verificatie/evaluatie): Gegeven een model en een formule, is de formule waar in het model? – Satisfiability (vervulbaarheid): Gegeven een formule, is er een model dat de formule waarmaakt? – Model comparison (vergelijking): Gegeven twee modellen, maken deze dezelfde formules waar? Als we de precieze rekencomplexiteit van al deze taken kennen, dan hebben we een redelijk ‘profiel’ van het computationele gedrag van zo’n logisch systeem. We zullen alleen wat voorbeelden geven van de complexiteit van dit soort kwesties voor de logische talen van dit boek. Maar voordat we dat kunnen doen, moeten we natuurlijk wel iets preciezer zijn over wat we bedoelen met rekencomplexiteit! Dit is op zich al een belangrijk vakspecialisme in de praktische en theoretische informatica.

7.3

Computationale complexiteit

Een taak is effectief opgelost als je er een algoritme voor kunt schrijven, misschien als programma in een of andere programmeertaal. Bij een JA/NEE-vraag ‘P?’ wordt de bewering P als invoer aan een mechanische procedure gegeven die na een eindig aantal stappen steeds het juiste antwoord geeft. Een voorbeeld van zo’n vraag is: kunnen we uit een beginsituatie een gewenste eindsituatie bereiken via een eindig aantal stappen? Heel veel taken in de informatica, zoals het bevragen van gegevensbanken, of zoektaken in de kunstmatige intelligentie, komen neer op het bepalen van dergelijke ‘bereikbaarheid’ van een doel uit een beginpunt. VOORBEELD 7.7

Graph reachability (bereikbaarheid in een graaf) Gegeven is een eindige gerichte graaf G en twee knopen s (‘beginknoop’) en t (‘eindknoop’). Is er een pad van s naar t? Deze vraag is te beantwoorden met het volgende algoritme: R wordt de verzameling rode knopen. Kleur om te beginnen alleen s rood. B wordt de verzameling blauwe knopen. Deze is in eerste instantie leeg.

78

Hoofdstuk 7

Complexiteit van berekeningen

Herhaal nu de volgende procedure: pak een rode knoop uit R, verf deze blauw (voeg deze aan B toe), en vervang die knoop in R door al zijn (directe) opvolgers in de graaf, ‘tenzij je ze al gehad hebt’, dat wil zeggen: tenzij ze al rood of blauw zijn. Met andere woorden: verf alle niet gekleurde opvolgers rood. Als er niet zulke opvolgers zijn, dan krimpt R dus. Stop als R leeg is. Als t nu blauw is, dan is t bereikbaar uit s, en anders niet. Dit algoritme is correct en eindigt in kwadratische tijd ten opzichte van het aantal knopen van de graaf. Dit kunnen we als volgt inzien. Stel n is het aantal knopen in de graaf. Ten hoogste iedere knoop verkleurt een keer van rood naar blauw, ieder van die knopen heeft ten hoogste alle andere knopen als opvolger, en aan het eind moeten we nog even de verzameling B doorlopen, die ten hoogste alle knopen bevat. In totaal zijn dit hooguit n(n – 1) + n stappen. Omdat voor grote n de lineaire factoren verwaarloosbaar zijn ten opzichte van kwadraten, en n en n – 1 dan bijna hetzelfde zijn, zeggen we: de orde van grootte is n2. ◊ De kunst van efficiënt programmeren loopt via dergelijke slimme representaties met lage complexiteit. Vergelijk dit ook met voorbeeld 7.6 van ‘vind de beroemdheid’. Graden van groei

Als een antwoord op een JA/NEE-vraag ‘P?’ altijd in eindig veel stappen puur mechanisch bepaald kan worden noemen we het probleem beslisbaar. Het is dan immers te ‘beslissen’ (uit te maken) of het antwoord op deze vraag JA dan wel NEE is. De complexiteit van zo’n beslisbare procedure is een functie van de lengte van de invoer van die procedure (zoals bij een propositielogische formule: het aantal symbolen). Daarbij speelt het aantal rekenstappen een belangrijke rol. Dit wordt de tijdscomplexiteit van het probleem genoemd. We hebben al gezien dat het aantal rekenstappen lineair kan zijn in de invoer, en ook dat het een groter polynoom kan zijn dan lineair, bijvoorbeeld kwadratisch, zoals in voorbeeld 7.7. Beide noemen we van polynomiale complexiteit. Als de rekencomplexiteit polynomiaal is ten opzichte van de invoer noemen we een probleem in de klasse P (waarbij P inderdaad voor polynomiaal staat). Als x de invoerlengte is, dan is bijvoorbeeld ax + b lineair en ax3 derdegraads, en beide zijn polynomen, dus deze problemen zitten allebei in P. Als de rekencomplexiteit daarentegen exponentieel is als functie van de invoerlengte vinden we het ‘heel complex’. Deze klasse noemen we Exptime: deze exponentiële tijd ziet er ten minste uit als ax. Oudere lezers herinneren zich nog de groeigrafieken van de ‘Club van Rome’ in de zeventiger jaren, die aangaven hoe vervuiling en andere doemscenario’s op deze akelig snelle manier toenamen. En het kan zelfs nog erger dan Exptime, zoals bijvoorbeeld in x! en in 2 2 x . Er zitten ook nog complexiteitsklassen tussen polynomiaal en exponentieel, maar daar gaan we niet op in.

79

Logica in actie

VOORBEELD 7.8

Graph reachability, GR, is in P, omdat voor een gegeven graaf G de procedure altijd eindigt na hooguit een aantal stappen van een kwadratische orde van grootte (namelijk n(n – 1) + n). ◊ Een logische analogie kan helpen deze begrippen nog iets beter te begrijpen. Hiervoor zagen we al dat propositielogische evaluatie in P zit. Testen op propositielogische vervulbaarheid leek exponentiële complexiteit te hebben maar zit in feite in een lagere complexiteitsklasse, tussen P en Exptime in. Zelfs als een taak in P zit, blijft een algoritme van lineaire tijd prettiger dan één van kwadratische tijd, enzovoorts: een polynoom van lagere graad is altijd weer beter dan een van hogere graad. De kunst van het programmeren bestaat doorgaans uit het geschikt kiezen van datastructuren en instructies, om zo laag mogelijk in rekencomplexiteit uit te komen. Problemen in P gelden als doenlijk (in het Engels: ‘tractable’) en alles daarbuiten als ondoenlijk (‘intractable’), hetgeen overigens niemand verhindert allerlei speciale gevallen toch op de computer op te lossen.

Onbeslisbaarheid

Het kan dus, zoals we al zagen, nog veel erger qua complexiteit. En sommige problemen zijn helemaal niet met een algoritmische methode op te lossen: deze heten onbeslisbaar. Wie zou niet graag willen kunnen vermijden dat zijn computer vastloopt? Dit is het Stopprobleem: ‘Bepaal bij een willekeurig programma en willekeurige invoer, of het programma voor die invoer termineert.’ In het Engels is het probleem bekend als het ‘Halting problem’. Het is nu een feit dat dit Stopprobleem onbeslisbaar is. Dit feit werd bewezen door Alan Turing in 1936. Er zijn dus geen wondermiddelen die automatisch ongewenst gedrag van onze computers detecteren. Nog zo’n onbeslisbare vraag is bijvoorbeeld die naar de equivalentie van twee gegeven programma’s, bijvoorbeeld in een eenvoudige imperatieve programmeertaal: geven ze op alle invoer dezelfde waarden? De oudste voorbeelden van onbeslisbare problemen komen uit de logica.

VOORBEELD 7.9

Predikaatlogica is onbeslisbaar In de propositielogica hebben we een beslissingsprocedure om te bepalen of een gegeven formule een tautologie is, of niet: maak de waarheidstabel, loop alle waarderingen langs en bepaal de waarde van de hele formule voor die waardering, en als er overal énen staan, is het een tautologie. Maar in de predikaatlogica bestaat zo’n procedure niet. (We laten details achterwege.) Het resultaat dat de predikaatlogica onbeslisbaar is danken we aan Alonzo Church, die hiertoe gebruik maakte van de beroemde Stelling van Gödel. Hoe zit het dan met bijvoorbeeld onze kennislogica, die qua kracht in lag tussen de propositielogica en de predikaatlogica? Deze blijkt weer beslisbaar, maar wel met een wezenlijk complexer algoritme dan voor de propositielogica. ◊

80

Hoofdstuk 7

Complexiteit van berekeningen

De algemene moraal is deze: niet elk eenvoudig formuleerbaar probleem inzake redeneren, rekenen of informatieverwerking heeft een mechanische oplossing! Ook hier merken we weer op dat de praktijk toch enig optimisme wettigt. Zelfs onbeslisbare problemen kunnen systematisch worden aangepakt. Er zijn namelijk allerlei bewijsmethodes voor de predikaatlogica, waarmee we ‘meestal’ wel uit de voeten kunnen. In dit verband maken we nog een opmerking. Onze voorbeelden in dit hoofdstuk geven slechts bovengrenzen: hoeveel tijd- of ruimtestappen hebben we hoogstens nodig, in het ergste geval? Om een probleem precies te plaatsen in de complexiteitshiërarchie moeten we ook een ondergrens geven: hoeveel stappen kan de oplossing minstens vergen, wat is de minimale complexiteit? Maar in het algemeen wordt het gedrag van een algoritme in de praktijk bepaald door rekentijd op willekeurige invoer, zodat we eerder zouden moeten spreken over een gemiddelde complexiteit. Deze verdere kwesties laten we hier terzijde. Tegen deze achtergrond eindigen we met een meer theoretische kwestie. Hoe moeilijk is het vervulbaarheids- of geldigheidsprobleem van de propositielogica nu werkelijk? Moet het exponentieel, of wordt er wellicht toch nog een slim algoritme gevonden dat het in polynomiale tijd afkan? Deze vraag staat bekend als het ‘P = NP’ probleem, dat voorkomt op de lijst van ‘Tien Meest Beroemde Open Vragen van de Wiskunde’, in 2000 gepubliceerd door het Cray Institute. Het is opmerkelijk dat een zo eenvoudig logisch systeem als de propositielogica, in wezen al bekend sinds de Klassieke Oudheid, nog zulke nieuwe vragen weet op te werpen. Samenvatting Een probleem is beslisbaar als een antwoord op een JA/NEE-vraag ‘P?’ altijd in eindig veel stappen puur mechanisch bepaald kan worden. De complexiteit van zo’n beslissingsprocedure is een functie van de lengte van de invoer van die procedure. Daarbij speelt het aantal rekenstappen (tijdscomplexiteit) een rol. Wat betreft het aantal rekenstappen is lineair minder complex dan (vanaf tweedegraads) polynomiaal, en polynomiaal minder complex dan exponentieel. Al deze genres complexiteit komen voor in de propositielogica, en overigens ook in de kennislogica van hoofdstuk 6. Sommige belangrijke problemen zijn zelfs onbeslisbaar, dat wil zeggen dat geen enkel programmeerbaar algoritme, hoe ingewikkeld ook, ze kan oplossen. Bijvoorbeeld, het is onbeslisbaar of bij een willekeurig programma en willekeurige invoer, het programma voor die invoer termineert. Dit staat bekend als het Stopprobleem. Maar ook logische geldigheid in systemen als de predikaatlogica is van deze hoge complexiteit.

81

Logica in actie

Opgaven OPGAVE 7.1

Voer het ‘graph reachability’ algoritme van voorbeeld 7.7 uit voor de volgende graaf. Als beginknoop s neemt u knoop 1 in de figuur. Als eindknoop t neemt u knoop 4.

OPGAVE 7.2

Voer het ‘vind de bekendheid’ algoritme van voorbeeld 7.6 uit voor de volgende graaf.

82

HOOFDSTUK 8 Spel en logica van interactie Spelen zijn een typisch menselijke activiteit, lopend vanaf kaartspelen of voetbal tot spelpatronen in algemeen economisch en sociaal gedrag. De Nederlandse historicus Johan Huizinga schreef er een beroemd boek over, met de mooie titel Homo Ludens. Maar ook wiskundigen zijn reeds vele malen in de geschiedenis door spelen geïnspireerd tot het opstellen van belangrijke theorieën. Zo komt het begrip waarschijnlijkheid uit de zestiende-eeuwse studie van kansspelen en weddenschappen. In de 20ste eeuw ontstond de ‘speltheorie’ als algemene analyse van rationeel gedrag van personen in interactie. Er zijn ook vele relaties tussen logica en speltheorie, waarvan we er een zullen bespreken aan het eind van dit hoofdstuk. Daarmee is dit laatste thema in dit boek een vooruitblik op een bredere rol van de moderne logica als studie van intelligente interactie tussen mensen die communiceren, debatteren, en samen actie ondernemen om hun doelen te bereiken.

8.1 VOORBEELD 8.1

Winnende strategieën

Het Blokkadespel Gegeven is een netwerk met plaatsen (aangegeven door punten) en paden (verbindingen tussen punten), en met een of andere startplaats. Er zijn twee spelers. ‘Loper’ is eerst aan zet, en moet proberen alle plaatsen in het netwerk te bezoeken langs openstaande paden, waarbij hij telkens een pad kiest vanuit zijn laatste plaats. ‘Remmer’ mag na elke stap van Loper een willekeurig pad verwijderen uit het netwerk. En zo verder, om en om. Het spel stopt als een speler geen zet meer kan doen. In dat geval heeft Loper gewonnen als elke plaats is bezocht, anders wint Remmer. U kunt zich voorstellen dat Loper de gemiddelde NS-reiziger is, die probeert een reis langs verschillende stations te maken, en dat Remmer de NSbedrijfsvoering voorstelt, die probeert zo efficiënt mogelijk verbindingen buiten werking te stellen.

83

Logica in actie

Laten we eens zo’n spel bekijken:

Een mogelijk spelverloop is: Loper loopt van - naar

Remmer verwijdert een lijn van - naar

1-3 3-4 4-3

3-2 4-2 1-2

Het is duidelijk dat Loper verliest, want 2 is nu onbereikbaar geworden. Maar bekijk nu eens het volgende verloop: Loper loopt van - naar

Remmer verwijdert een lijn van - naar

1-2 2-4 4-3

2-3 4-3

In dit geval heeft Loper gewonnen! In de meeste spelen kunnen beide spelers winnen of verliezen, afhankelijk van hoe ze spelen. Maar dit is niet alles. Want dit spel is welbeschouwd essentieel in het voordeel van Remmer. We zeggen dan ook: ‘Remmer kan altijd winnen, hoe Loper ook speelt!’ Immers, als Loper naar 3 gaat, dan heeft Remmer genoeg tijd om in drie beurten punt 2 te ‘isoleren’. Maar als Loper eerst naar punt 2 gaat, dan werkt het volgende. Laat Remmer in zijn eerste twee beurten de verbindingen tussen 3 en 4 weghalen. Dit dwingt Loper terug te keren op weg naar 3 of 4, en Remmer heeft dan tijd om één van deze twee plaatsen te isoleren. ◊ Strategie en De handelwijze van Remmer hiervoor, die op elk mogelijk gedrag van de winnende strategie tegenpartij een passend antwoord geeft, heet een strategie. In het algemeen

is een strategie een serie zetten, of acties, waarbij elke volgende zet een der mogelijke keuzes is die de speler kan maken in de gegeven spelsituatie op dat moment. Een strategie die garandeert dat een speler altijd wint (hoe de ander ook speelt) heet een winnende strategie (of winstrategie).

84

Hoofdstuk 8

VOORBEELD 8.2

Spel en logica van interactie

Om nader te begrijpen wat een winstrategie is gaan we na welke speler een winnende strategie heeft in een Blokkadespel dat als volgt begint:

In dit geval heeft nu juist Loper een winnende strategie! We schetsen de redenering. Om te winnen, moet Loper eerst naar 2 gaan. Aldaar afkappen van een 2 - 3 of 2 - 4 helpt Remmer niet: Loper kan toch naar 3 en 4 komen. Weghalen van de twee 3 - 4 paden boven, zoals eerder, helpt dit keer echter ook niet - want dit laat Loper net genoeg tijd om eerst naar 4 te gaan en dan via 2 ook nog naar 3 te komen. ◊ Nulsom–spel

Volgens een stelling uit 1913 van de wiskundige Zermelo is er in elk eindig spel van het zogenaamde type ‘nul-som’ - en elke versie van Blokkade is zo’n spelsoort - één speler met een winnende strategie. Een nulsom-spel is een spel waarbij voor elke eindtoestand geen twee verliezers of twee winnaars zijn. Er is één winnaar en één verliezer. Zo’n spel noemen we gedetermineerd als we voordat we beginnen te spelen al kunnen bepalen wie er kan winnen.

STELLING 8.1

Stelling van Zermelo Elk eindig nulsom-spel is gedetermineerd. Deze verrassend sterke stelling is redelijk eenvoudig te bewijzen. We illustreren de stelling aan de hand van een spelboom voor het Nim-spel. Een spelboom is een boom die: (i) als wortel de beginsituatie van een spel heeft, (ii) die in iedere knoop waarin speler i aan de beurt is m kinderen heeft die staan voor de speltoestanden die resulteren uit alle mogelijke zetten voor die speler, (iii) en die als bladeren de eindtoestanden van het spel heeft.

85

Logica in actie

VOORBEELD 8.3

Het Nim-spel Het spel begint met een aantal stapeltjes lucifers. Er zijn twee spelers, A en B. Speler A begint. De speler die de beurt heeft, kiest één van de stapeltjes uit, waarna er minstens één lucifer van dat stapeltje moet worden weggenomen. De laatste speler die een lucifer wegneemt is de winnaar. De algemene manier om de winnende strategie te bepalen is om de volledige spelboom langs te gaan. Hier is bijvoorbeeld de spelboom van de beginsituatie 1 - 2 - 1.

In elke toestand is aangegeven wie aan de beurt is, en dus wordt in elke eindtoestand de beurtspeler ook de verliezer. De eindtoestanden die voor A gewonnen zijn kleuren we zwart en de eindtoestanden die vóór B gewonnen zijn kleuren we wit. Nu kunnen we ook de toestanden voor de eindtoestanden inkleuren als indicator van de speler die kan winnen: de speler met de winstrategie. Als er voor de beurtspeler in de voorlaatste toestand een winnende eindtoestand is dan heeft hij als winstrategie de specifieke zet die tot die eindtoestand leidt. We kleuren die toestand overeenkomstig. Mocht er voor hem geen enkele winnende eindtoestand zijn dan kleuren we de gegeven voorlaatste toestand als wintoestand voor de tegenspeler. Met deze kleuring kunnen we nu deze voorlaatste toestand in feite opvatten als een eindtoestand met een winnaar en een verliezer (gegeven dat ze geen domme zetten doen). Zo kunnen we vervolgen en de gehele spelboom inkleuren door volgens hetzelfde procedé stap voor stap naar boven toe de toestanden in te kleuren. De kleur van de begintoestand geeft dan de speler aan die een winnende strategie heeft. In dit geval is dat speler A: deze kan immers ervoor kiezen het stapeltje met twee lucifers weg te halen, waarna we in de meest rechtse vervolgsituatie eronder terechtkomen. De strategie voor de winnende speler, na kleuring van de spelboom, is om te kiezen voor een vervolgtoestand met zijn eigen kleur als hij aan de beurt is. We hebben dus niet alleen bepaald wie kan winnen, maar we hebben tegelijkertijd ook nog een keer de winstrategie geconstrueerd. ◊

86

Hoofdstuk 8

Spel en logica van interactie

De stelling van Zermelo heeft maar weinig directe praktische betekenis. Het probleem is natuurlijk de omvang van de spelboom, en het terugrekenen vanuit de eindtoestanden is doorgaans ondoenlijk. Zermelo was zelf voornamelijk geïnteresseerd in spelen als schaken waarbij ook remise mogelijk is. In deze spelen garandeert zijn stelling dat één van beide spelers een strategie heeft om niet te verliezen. Het verschil tussen theorie en praktijk voor het schaakspel is immens. Een eeuw na het oorspronkelijke resultaat is nog steeds niet bekend welke speler deze nietverliezende strategie heeft. Er zijn ruwweg twintig mogelijkheden per zet, en het totaal aantal mogelijk toegestane posities van de schaakstukken op het schaakbord is ongeveer 10120. Dit getal komt ongeveer overeen met het aantal elementaire deeltjes in het zichtbare heelal! Niettemin is de denktrant in het hier gegeven bewijs wel richtinggevend voor de tegenwoordig gebruikte geoptimalizeerde methoden om spelen op te lossen. VOORBEELD 8.4

In het Nim-spel is evenwel een elegante short-cut te geven om te bepalen wie er zal winnen. Laat n1, n2, … de aantallen lucifers zijn in stapeltjes. Het idee is nu deze getallen binair te schrijven en wel onder elkaar. Stel we beginnen met drie stapels met n1 = 5, n2 = 9 en n3 = 4 lucifers. Of, in binaire notatie n1 = 101, n2 = 1001 en n3 = 100. We tellen nu het totaal aantal enen op de n-de plaats van deze getallen en zetten die in een tabel eronder: n1 n2 n3

1

1 0 1

0 0 0

1 1 0

1

2

0

2

In het voorbeeld geeft dit 1, 2, 0 en 2 enen. Een spel heet gebalanceerd als voor iedere positie in de binaire notatie het totaal aantal enen even of nul is. Anders noemen we het spel ongebalanceerd. In het gegeven geval is het spel ongebalanceerd omdat er maar één 1 staat op de meest linkse plaats. Nu zijn er de volgende drie belangrijke feiten: – Een gebalanceerd spel zal na iedere toegestane zet veranderen in een ongebalanceerd spel. Immers het aantal lucifers in één stapel zal gewijzigd worden, zodat in één rij sommigen enen in nullen veranderen en vice versa. Als in iedere kolom het aantal enen even was zal dat na de zet niet langer het geval kunnen zijn. – Een ongebalanceerd spel kan met één toegestane zet veranderd worden in een gebalanceerd spel. Neem de hoogste (meest linkse) positie p waarin het aantal enen oneven is. Laat ni het getal zijn dat op die positie een 1 heeft. Van deze stapel met ni lucifers gaan we nu lucifers afhalen. Om dit aantal te bepalen doorlopen we de binaire representatie van dit getal vanaf de positie p naar rechts. Om te beginnen vervangen we de 1 op de p-de plaats door een 0. We gaan nu een positie naar rechts. Als dit een kolom

87

Logica in actie

met een even aantal enen is, doen we niets. Als dit echter eveneens een kolom met een oneven aantal enen is, maken we er een 0 van als er een 1 stond en maken we er een 1 van als er een 0 stond. We herhalen nu deze procedure totdat we bij de kleinste (meest rechtse) positie zijn. In binaire notatie is het resultaat een getal n 'i . Neem nu ni - n 'i lucifers weg van de stapel met ni lucifers om een gebalanceerd spel te bereiken. – Een speler die aan zet is in een gebalanceerd spel zal nooit met die zet kunnen winnen, omdat er voor een gebalanceerd spel altijd minstens twee stapels moeten zijn. De winnende strategie is dus om van een ongebalanceerd spel altijd een gebalanceerd spel te maken. Daarna kan de tegenstander het spel niet uitmaken. Dit betekent dat de speler die begint een winnende strategie heeft als de beginsituatie ongebalanceerd is.

8.2

◊

Spelen met voorkeuren

In toepassingen van speltheorie op echte situaties, volstaan deze ‘kale’ spelen niet langer. Mensen hebben in het algemeen veel ingewikkelder voorkeuren tussen uitkomsten dan ‘winnen’ versus ‘verliezen’. VOORBEELD 8.5

Verkiezingen Marie, Natasha en Ofelia hebben een vrijkaartje over voor het Toonloos Ensemble. Ze kunnen stemmen over een keuze tussen Michael, Niemand en Otto om mee te nemen. Hun voorkeuren liggen als volgt: Marie 1 2 3

Natasha

Ofelia

Michael Niemand Otto Niemand Michael Michael Otto Otto Niemand

Eerst wordt gestemd over Michael of Otto, daarna over de resterende mogelijkheid hieruit of Niemand. Hoe moeten de dames stemmen? De volgende boom in de volgende figuur geeft de mogelijkheden weer. Als iedereen stemt volgens zijn voorkeur, dan wint Michael in de eerste ronde met twee tegen één, en vervolgens wint Michael ook tegen Niemand, eveneens met twee tegen één. Maar als Natasha dit voorziet, dan kan ze beter haar stemgedrag in de eerste ronde veranderen - en tegen haar eigen voorkeur in stemmen!

88

Hoofdstuk 8

Spel en logica van interactie

Immers, als ze in die ronde stemt voor Otto in plaats van voor (haar voorkeur) Michael, dan wordt in die ronde Otto gekozen, waarna bij meerderheidsstemming daarna Niemand wint, hetgeen haar eerste voorkeur was. Zo bereikt ze dan uiteindelijk toch wat ze wil. Maar de andere spelers kunnen deze redenering ook zelf van te voren bedenken, en kunnen dus ook hun stemgedrag daarop aanpassen. Is hier een beste oplossing te vinden? We denken op dezelfde manier als in voorbeeld 8.3 over het Nim-spel. We beginnen onderaan de spelboom en redeneren terug. (Dit proces heet ‘backwards induction’.) In het laatste stadium weet elke speler wat er is gebeurd, en resteert slechts één eindkeuze. Afwijken van de eigen voorkeur heeft dan geen zin, dus bijvoorbeeld bij een keuze tussen Niemand en Otto komt Niemand uit de bus, en bij Niemand versus Michael juist Michael. Maar dan kunnen spelers in het stadium daarvoor van dit gedrag uitgaan:

Dit betekent dat een speler in de eerste ronde voor Michael moet stemmen als zij Michael verkiest boven Niemand en dat een speler in de eerste ronde voor Otto moet stemmen als ze Niemand verkiest boven Otto. In dat geval stemmen verstandige spelers aan het begin als volgt (en we zien dat in de eerste ronde dus zowel Natasha als Ofelia tegen hun ‘echte’ voorkeur in stemmen): Marie

Natasha

Ofelia

Michael

Otto

Michael

Het resultaat is: Michael mag mee naar het concert.

◊

89

Logica in actie

8.3

Strategisch evenwicht

We bekijken een spel met twee personen. Voor ieder paar van strategieën van de twee spelers zal er een unieke uitkomst zijn die verkregen wordt door de twee strategieën tegen elkaar te laten spelen. Deze uitkomst kan door beide spelers geëvalueerd worden. DEFINITIE 8.1

Nash-evenwicht Een tweetal strategieën, voor beide spelers één, is in Nash-evenwicht als geen van beide spelers de uitkomst kan verbeteren door van strategie te veranderen, aangenomen dat de andere speler niet van strategie verandert. De definitie verwijst naar John Nash, aan wiens leven zelfs een film is gewijd: “A Beautiful Mind”. Ze sluit met name niet uit dat de uitkomst verbetert als beide spelers tegelijk van strategie veranderen! We zullen hier voorbeelden van zien. Idealiter correspondeert zo’n evenwicht met stabiel gedrag voor rationele spelers. Met meer spelers is de definitie van strategisch evenwicht in wezen hetzelfde. In het bovenstaande verkiezingsspel gaat men eenvoudig na dat het zojuist gegeven stemgedrag voor de drie spelers een Nash-evenwicht vormt. Het verkiezingvoorbeeld was een ander soort spel dan het eerdere Blokkade, of het schaakspel. Spelers moesten namelijk in elke ronde tegelijk zetten, zonder te weten wat de anderen doen in dezelfde beurt. Veel voorbeelden in de speltheorie zijn van deze aard, met name zogenaamde ‘strategische spelen’, die worden weergegeven door een matrix van uitkomsten, waarbij de rijen de strategie van de eerste speler geven en de kolommen de strategie van de tweede speler. Een paar getallen (i, j) in de matrix geeft de uitkomsten die de rijspeler en kolomspeler (in die volgorde) aan de relevante uitkomst toekennen. Hier zijn een aantal beroemde 2 × 2 voorbeelden: twee spelers en twee strategieën, waarbij de strategieën uit één zet bestaan.

VOORBEELD 8.6

Prisoners’ Dilemma Een onvervalste evergreen. In de klassieke opzet betreft het twee arrestanten, verdachte 1 en verdachte 2. Er is niet genoeg bewijsmateriaal voor een zware veroordeling. Als beiden blijven zwijgen krijgen ze ieder maar één jaar gevangenisstraf. Als echter (precies) één van beiden bekent, dan gaat deze vrijuit en de andere gaat voor tien jaar de gevangenis is. Als beiden bekennen krijgen ze ieder vijf jaar straf. Hier is de matrix die het probleem weergeeft.

zwijg beken

90

zwijg

beken

(–1, –1) (0, –10)

(–10, 0) (–5, –5)

Hoofdstuk 8

Spel en logica van interactie

In dit geval is er een duidelijk Nash-evenwicht, namelijk (beken, beken). Het is een Nash-evenwicht omdat: als verdachte 2 ‘beken’ kiest, dan is voor verdachte 1 de opbrengst –5 (eerste argument) in (–5, –5) beter dan de opbrengst –10 in (–10, 0), dus is het voor verdachte 1 beter ook de keuze ‘beken’ te houden; en als verdachte 1 ‘beken’ kiest, is het voor verdachte 2 om diezelfde reden ook beter de keuze ‘beken’ te houden, want voor 2 geldt ook dat de opbrengst –10 in uitkomst (0, –10) slechter is dan de opbrengst –5 in (–5, –5). De situatie is natuurlijk symmetrisch voor 1 en 2, maar dat hoeft niet altijd het geval te zijn. Het paar (beken, beken) is het enige Nash-evenwicht in dit voorbeeld. Namelijk: (zwijg, zwijg) is geen Nash-evenwicht, want als 2 zwijg kiest is het voor 1 beter om beken te kiezen: opbrengst 0 in plaats van –1. En (beken, zwijg) is ook geen Nash-evenwicht, want als 1 beken kiest is het voor 2 beter om van keuze te wisselen en ook beken te kiezen: opbrengst –5 in plaats van –10! Evenzo is (zwijg, beken) geen Nash-evenwicht. Het zal er dus op uitdraaien dat ze vijf jaar gevangenisstraf oplopen. De twee spelers worden dus niet geleid tot coöperatief gedrag, terwijl dat ze tot collectief zwijgen had kunnen aanzetten wat maar één jaar gevangenisstraf voor beiden had betekend. ◊ In het voorgaande voorbeeld is het zelfs ongeacht wat verdachte 2 doet, voor verdachte 1 altijd gunstiger om te bekennen. Als er voor een gegeven speler een strategie is die altijd te verkiezen is onafhankelijk van wat de andere spelers doen, dan spreken we van een dominante strategie. Verdachte 1 heeft dus een dominante strategie. Hetzelfde geldt in dit voorbeeld trouwens voor verdachte 2. VOORBEELD 8.7

Voorbeeld 8.6 kan in verschillende andere vormen geformuleerd worden. Een typisch voorbeeld daarvan is niet-coöperatief gedrag tussen concurrerende bedrijven. Stel Coca Cola en Pepsi hebben een afspraak gemaakt om frisdrank tegen een hoge prijs te verkopen. De winst is dan (in een bepaalde eenheid) zes voor iedere fabrikant. Maar ieder van beide heeft de mogelijkheid deze afspraak te schenden en tegen een lagere prijs te verkopen. In dat geval zal degene met de lage prijs acht eenheden verdienen, tegen twee voor de fabrikant van het hooggeprijste product. Als beide partijen de afspraak schenden blijft slechts een winst van drie voor ieder over. De situatie kan worden weergegeven in de volgende tabel.

hoog laag

hoog

laag

(6, 6) (8, 2)

(2, 8) (3, 3)

91

Logica in actie

Ook hier is de niet-coöperatieve versie (laag, laag) de evenwichtssituatie. Rationeel gedrag voorspelt dus dat beide partijen de afspraak zullen schenden. Kartelvorming had hier voor een veel beter resultaat voor beide partijen gezorgd. ◊ VOORBEELD 8.8

In een derde variant bekijken we de samenwerking tussen twee studenten Johan en Robbert die samen een scriptie moeten schrijven. Er zijn twee mogelijkheden: hard werken en alles op tijd afmaken, of lui zijn en zien waar het schip strandt. Als beiden hard werken is de winst (6, 6). Als beiden lui zijn is het resultaat (3, 3). De grootste uitkomst is voor Robbert het grootst (8) als hij niets doet en Johan de scriptie met veel extra werk laat afmaken (voor de daarom magere beloning van 2), en vice versa. Dit geeft exact de vorige tabel. Het Nash-evenwicht voorspelt dus dat samenwerking bij scripties zou moeten stranden. Gelukkig is dit niet waar, en dat komt omdat je daarna nog wel eens met dezelfde persoon zou moeten kunnen samenwerken. Maar dat is een heel ander verhaal, waarin we bepaalde spelen eindig vaak of oneindig vaak herhalen: we definiëren daarmee dus eigenlijk een ander spel. In dat geval kan ‘je allebei inspannen’ (gelukkig) toch een evenwichtssituatie zijn. ◊ In al deze gevallen is communicatie een duidelijke manier om tot coöperatief gedrag te komen (en, zoals aangestipt, maakt herhaaldelijk het spel spelen ook een verschil). Als de twee arrestanten informatie kunnen uitwisselen en elkaar genoeg vertrouwen kunnen ze afspreken beiden te zwijgen. In het geval van kartelvorming zijn dit soort (geheime) prijsafspraken nu juist verboden en aan inspectie onderhevig. Maar dat komt omdat het evenwicht ‘(laag, laag)’ overeenkomt met de situatie van vrije concurrentie die het meest in het belang van de consument geacht wordt.

8.4

Logica en spel

We hebben nu een aantal voorbeelden gezien van de formele analyse van spelsituaties, waarin we wiskundig precieze conclusies over rationeel spelgedrag kunnen maken. Tot zover leek het echter weinig met logica te maken te hebben. Er zijn echter vele verbanden en overeenkomsten tussen logica en speltheorie. De globale overeenkomst is dat veel in de logica gezien kan worden als een nulsom-spel tussen twee spelers: de uitkomsten zijn ‘waar’ en ‘onwaar’, de ene speler probeert gelijk te krijgen, en de andere speler probeert het ongelijk van de ene speler te bereiken. Zetten in zo’n spel komen overeen met het aanvoeren van argumenten voor en tegen een bepaalde conclusie. En net als in de rechtspraak en in de retorica gaat het niet alleen om gelijk hebben maar ook om gelijk krijgen, en speelt het een rol hoeveel zetten je kunt doen (hoeveel argumenten de verdediging kan aanvoeren) binnen de beperkte tijd die je hebt om je gelijk te kunnen halen. Logische spelen voor meer dan twee spelers en meer dan twee posities zijn

92

Hoofdstuk 8

Spel en logica van interactie

nauwelijks bestudeerd, hoewel een debat naast twee partijen natuurlijk best nog een ‘scheidsrechter’ zou kunnen hebben. De argumentatietheorie, die teruggaat op de voorgeschiedenis van de logica in de Griekse oudheid, getuigt van dit karakter van de logica als spel. Dit werd opnieuw een levendig vakgebied na het werk van Lorenzen in de jaren 1950. Ook uit die tijd dateren spelen waarin een predikaatlogische formule ‘waar bewezen kan worden’ in het licht van tegenzetten door een logische tegenstander. Voor wie het programma ‘Tarski’s World’ wel eens heeft gezien: in dit programma is een voorbeeld hiervan het zogenaamde ‘Hintikka game’ dat je met de computer kunt spelen. Er zijn ook spelen om de modelvergelijkingstaak uit het vorige hoofdstuk spelenderwijs uit te voeren. Een van deze benaderingen staat bekend als Ehrenfeucht-Fraïssé-spelen. Gegeven twee structuren die bestaan uit een verzameling objecten met relaties daartussen, probeert in dat spel een ‘Spoiler’ (Bederver) te bewijzen dat ze verschillend zijn, en een ‘Duplicator’ (Verdubbelaar) dat ze hetzelfde zijn. We beperken ons tot één voorbeeld om dit toe te lichten. VOORBEELD 8.9

Gegeven zijn de twee modellen Drie (links) en Vier (rechts), in onderstaande figuur.

Een spelverloop is als volgt. Van tevoren wordt afgesproken hoeveel zetten het spel duurt. Bijvoorbeeld: twee zetten. Bederver kiest nu een model en een punt in dat model, bijvoorbeeld het model links en het punt 3. Verdubbelaar moet dan een punt in het andere model kiezen. Als hij goed speelt, kiest hij het punt dat hij het meest vindt lijken op de keuze van Bederver. Bijvoorbeeld, Verdubbelaar kiest rechts het punt d. Nu mag Bederver opnieuw een model kiezen en een punt daarin, bijvoorbeeld opnieuw links en daarin punt 1. Daarna moet Verdubbelaar in het andere model opnieuw een punt kiezen, bijvoorbeeld a. Beide spelers hebben nu twee zetten gedaan en het spel is uit. We beperken beide modellen nu tot de geselecteerde punten, met behoud van alle verbindingen tussen die punten. Met andere woorden, links houden we 1 → 3, en rechts houden we a → d. Als er nu geen structureel verschil is tussen de beide modellen, dan heeft Verdubbelaar gewonnen; hij is er immers in geslaagd de structuur te

93

Logica in actie

verdubbelen, dat wil zeggen precies hetzelfde te krijgen. Anders heeft Bederver gewonnen: zij heeft de poging van Verdubbelaar om de structuur te kopiëren succesvol weten te bederven. In dit voorbeeld heeft Verdubbelaar gewonnen: er is (alleen) een pijl van 1 naar 3, maar ook (alleen) een pijl van a naar d. Daarbij is tevens van belang dat 1 met a correspondeert (de keuzes in de eerste zet) en 3 met d correspondeert (de keuzes in de tweede zet). Als de uitkomst rechts niet a → d, maar d ← a was geweest (het resultaat van het spelverloop waarbij Verdubbelaar eerst a en dan d had gekozen), dan had Bederver toch gewonnen: er is immers een pijl van 1 naar 3, maar niet van d naar a. Bederver en Verdubbelaar spelen nog een keer. Ze mogen nu ieder vier zetten doen. Het spel verloopt als volgt: B

V

1 d 2 3

a 3 b d

Opnieuw wint Verdubbelaar! Maar nu heeft Bederver het toch niet goed gespeeld. Bederver had namelijk beter een andere laatste zet kunnen doen: B

V

1 d 2 c

a 3 b 3

Nu heeft Bederver (terecht!) gewonnen, want er is een pijl van d naar c maar geen pijl van 3 naar 3. Bederver moet dus niet zomaar wat doen, maar een goede strategie opzetten om het spel te kunnen winnen. Dit spel kan gespeeld worden met de modellen voor de predikaatlogica uit hoofdstuk 4 maar ook met de modellen voor de modale logica zoals die in voorbeeld 7.3 in het hoofdstuk over complexiteit. Bij de twee modellen in dat voorbeeld kan Bederver nooit winnen. Dat is daarmee een andere manier om te bewijzen dat die modellen dezelfde informatie-inhoud hebben. ◊ In dit laatste voorbeeld zien we opnieuw verschillende logische thema’s bij elkaar komen, en doorvlochten worden met speltheorie. Het uitvoeren van een spel tussen Bederver en Verdubbelaar kunnen we weergeven in een

94

Hoofdstuk 8

Spel en logica van interactie

spelboom, met uitkomsten winnen en verliezen, en de Stelling van Zermelo toont aan dat de uitkomst van zo’n spel gedetermineerd moet zijn. En het bepalen of twee modellen dezelfde informatie-inhoud hebben, is zoals al gezegd een vergelijkingstaak (model comparison) uit hoofdstuk 7 - waarbij van het grootste belang is wat de complexiteit is om zo’n taak uit te voeren. Kort gezegd, logische taken hebben een spelkarakter, en daarmee past de logica ook goed bij de analyse van spelen.

8.5

Het ultimatumspel

Net als bij gewoon redeneren is er ook bij spelmodellen een vraag naar de aansluiting bij feitelijk menselijk gedrag. En dan blijken duidelijke discrepanties tussen speltheorie en praktijk. In het bijzonder is het niet duidelijk dat mensen in alle omstandigheden zich uitsluitend door rationele overwegingen laten leiden van eigenbelang. Een goed voorbeeld is het ultimatumspel dat recent veel in de belangstelling heeft gestaan. In dit spel met twee spelers wordt een aanzienlijke som, zeg 100.000 euro aan speler 1 gegeven. Speler 1 mag dit bedrag over de twee spelers verdelen. Vervolgens mag speler 2 besluiten of beide spelers de toegekende bedragen mogen houden of niet. Dat wil zeggen, als speler 2 akkoord is krijgt hij het percentage dat speler 1 hem heeft toegedacht en mag speler 1 de rest houden. Als speler 2 niet akkoord is krijgen beide spelers helemaal niets. Het spel wordt slechts één keer gespeeld en de spelers zijn onbekenden en zullen elkaar ook niet opnieuw ontmoeten. De rationele keuzetheorie zegt dat speler 2 altijd moet accepteren zolang hij maar iets krijgt toegewezen, ongeacht hoe klein het bedrag is. Zelfs als speler 1 maar één euro ‘fooi’ geeft en zelf de resterende 99.999 houdt, kan speler 2 toch een winst van één boeken. Het alternatief is namelijk helemaal niets. Toch zal in de praktijk speler 2 geneigd zijn nee te zeggen als het toegewezen bedrag laag is. Een percentage van minstens 30 % wordt als redelijk ervaren. Eén van de mogelijke verklaringen is dat wij mensen toch zo geprogrammeerd zijn dat we rekening houden met het lange termijn effect van de beslissing. Het zou wel eens zo kunnen zijn dat onze reputatie een deuk oploopt als we een belachelijk lage fooi accepteren. We zouden de naam krijgen ‘goedkoop’ te zijn, en dat zou ons later duur kunnen komen te staan. Juist het feit dat we dit soort extra redeneringen willen begrijpen, brengt dan de logica weer ‘in het spel’: nog onlangs kreeg Robert Aumann de Nobelprijs voor de Economie voor zijn baanbrekende werk aan onder meer systemen van kennislogica die analyseren op grond van welke informatie over elkaar, spelers hun spelgedrag kiezen.

95

Logica in actie

Samenvatting Een spel wordt gespeeld door verschillende spelers, die tegelijk of na elkaar zetten doen. Een manier van spelen die garandeert dat je altijd wint, wat de tegenstander ook doet, is een winstrategie. In een nulsom-spel zijn maar twee uitkomsten mogelijk: winnen en verliezen. Er is maar één winnaar. De stelling van Zermelo zegt dat ieder eindig nulsom-spel gedetermineerd is. Een gebruikelijke representatie voor spelen waarbij de spelers tegelijkertijd zetten doen is een m × n matrix waarin de uitkomsten staan voor ieder van de m strategieën van de ene speler in combinatie met ieder van de n strategieën van de andere speler. Een strategieënpaar voor twee spelers is in Nash-evenwicht als geen van beide spelers de uitkomst kan verbeteren door van strategie te veranderen als de andere speler niet van strategie verandert. Er zijn vele verbanden tussen logica en speltheorie. Zo is er de globale overeenkomst dat veel in de logica gezien kan worden als een nulsom-spel tussen twee spelers: de uitkomsten zijn ‘waar’ en ‘onwaar’, de ene speler probeert gelijk te krijgen, en de andere speler probeert het ongelijk van de ene speler te bereiken. Zetten in zo’n spel komen overeen met het aanvoeren van argumenten voor en tegen een bepaalde conclusie. Maar ook wordt de logica tegenwoordig gebruikt om informatie en redeneren te analyseren van actoren die een optimaal gedrag nastreven in elk willekeurig spel, of dat nu een logisch doel heeft of niet. Opgaven OPGAVE 8.1

Bewijs dat er in voorbeeld 8.2 voor Loper geen winnende strategie is waarbij hij eerst naar knoop 3 gaat.

OPGAVE 8.2

Beschouw de volgende beginsituatie voor het Nim-spel (zie voorbeeld 8.3). n1 n2 n3

1

1 0 1

0 0 1

1 1 0

Is deze situatie gebalanceerd of niet? Wie kan dus winnen? Geef een mogelijk spelverloop.

96

Hoofdstuk 8

OPGAVE 8.3

Spel en logica van interactie

Een andere bekende vorm van het Prisoners’ Dilemma is de wapenwedloop, met als strategieën ‘ontwapen’ en ‘bewapen’. Bijvoorbeeld in onderstaande vorm.

ontwapenen bewapenen

ontwapenen

bewapenen

(3, 3) (4, 0)

(0, 4) (1, 1)

De partijen worden naar het Nash-evenwicht ‘bewapenen’ gedreven, ook al is het in ieders belang te ontwapenen. Een variatie hierop is als volgt:

ontwapenen bewapenen

ontwapenen

bewapenen

(3, 3) (4, 0)

(0, 4) (–10, –10)

Met andere woorden: de uitkomst van ‘allebei bewapenen’ is hier sterk negatief voor beide partijen (MAD: ‘mutually assured destruction’). Laat zien dat (bewapenen, bewapenen) nu geen Nash-evenwicht meer is. Is een van de andere combinaties nu wel een Nash-evenwicht? OPGAVE 8.4

Neem de modellen van voorbeeld 6.7 en voorbeeld 6.10. Laat met een Ehrenfeucht-Fraïssé-spel van twee zetten zien dat deze niet dezelfde informatie bevatten. (Vergeet niet dat alle toestanden ook reflexieve pijlen hebben).

97

Logica in actie

98

Tot besluit De lezer heeft nu veel thema’s van logisch belang langs zien komen. We hebben daarbij gestreefd naar een balans tussen klassieke thema’s rond geldig redeneren, zoals waarheid en bewijzen, en moderne visies op logica als de studie van informatie, rekenprocessen, en interactie in conversatie of spel. In de hoofdstukken over propositielogica introduceerden we een fundamentele taal waarin we volledige zinnen door een enkele propositieletter weergeven en ons verder alleen bekommeren om de logische verbanden tussen zinsdelen zoals ‘en’, ‘of’, en ‘dan en slechts dan als’. We konden hier ook mee rekenen, met gebruikmaking van equivalenties zoals dat ¬¬p equivalent is met p. Dit binair rekenen vormt de basis van iedere computer. De predikaatlogica was een natuurlijke uitbreiding op de propositielogica waarin de individuele proposities ook interne structuur hebben, en we de namen van objecten die in die proposities voorkomen ook kunnen onderscheiden, in hun relatie tot elkaar. Die relatie stond traditioneel bekend als het prediceren van dergelijke objecten, en vandaar de naam voor die logica. Met universele en existentiële kwantoren konden we heel wat eigenschappen van relationele structuren tot uitdrukking brengen, en zelfs getaltheorie uitdrukken, zoals de bewering dat er geen grootste priemgetal is. In feite kan de predikaatlogica zelfs de wiskundige verzamelingenleer weergeven, en is daarmee geschikt als sterke grondslagentheorie. Maar dit systeem dient even goed de moderne informatica, en een toepassing was het gebruik van correctheidsbeweringen die het effect van computerprogramma’s op logische wijze omschrijven. Een heel andere uitbreiding van de propositielogica is de kennislogica die gebruikt kan worden om informatie van actoren weer te geven, en de veranderingen die daarin optreden door communicatie. Hiermee drukken we uit dat logica wordt gedaan door een kennend subject, dat zelfs over de kennis van andere actoren kan redeneren. Deze wederkerige kennis vormt het web van verwachtingen dat ons gedrag stuurt en op zijn plaats houdt. Een van de vele verrassende verschijnselen op dit gebied was dat het uitspreken van een bewering deze onwaar kan maken: duidelijker kunnen we niet maken dat logica vooral in actie bestudeerd moet worden en geen statisch geheel is. We besteedden vervolgens ook aparte aandacht aan de duur van logische processen, zoals hoe lang het duurt om een waarheidstabel door te rekenen, of om te controleren of een redenering geldig is. Dit gebeurde in het hoofdstuk over computationele complexiteit.

99

Logica in actie

Ten slotte hielden we ons bezig met spelen, waarin de logica eveneens tot uitdrukking gebracht kan worden, door iemand die een zin waar wil maken een spel te laten spelen met iemand die een zin onwaar wil maken: ‘echte’ waarheid betekent dan dat er een winnende strategie is om het waar te maken. Maar je moet het wel goed spelen, anders kun je toch verliezen, net als in de rechtszaal. Er zijn veel zaken van modern logisch belang waaraan we in dit boek voorbij zijn gegaan. Veel daarvan liggen in het spanningsveld tussen logica als theorie van correct redeneren en correcte informatieverwerking, en de realiteit van menselijk gedrag op deze gebieden, vaak met gebruik van onze gewone taal. Verbanden tussen logica en natuurlijke taal, al dan niet problematisch, worden in veel leerboeken besproken, maar hier hebben we andere accenten gekozen. Naast taalgebruik noemen we een drietal verdere aspecten van menselijk gedrag die raken aan de huidige logica. Om te beginnen zijn mensen van vlees en bloed beperkt in hun redeneermogelijkheden: een denkstap kost tijd en moeite. Dat valt met name op als we er vele honderden of duizenden moeten uitvoeren. De cognitiewetenschap bestudeert architecturen met dergelijke beperkingen, die ver af liggen van de idealiseringen in onze logische systemen, zowel klassieke voor bewijzen als moderne voor kennis en communicatie. Hoe we de juiste aansluiting moeten vinden tussen de logische theorie die streeft naar correctheid, en de beperkingen van onze cognitieve vermogens is een fundamentele open vraag. Van groot belang bij deze realiteiten van alledaags redeneren op grond van nieuwe informatie is het voorlopige karakter. Ik geloof dat p het geval is op grond van mijn huidige informatie, en concludeer daaruit voorlopig weer andere dingen onder gebruik van verdere redelijke veronderstellingen. Maar ik weet ook dat nieuwe informatie deze verwachtingen teniet kan doen, zodat ik mijn opvattingen moet herzien. Processen van herziening van eerdere conclusies, die in de klassieke logica en wiskunde helemaal niet voorkwamen, zijn een belangrijk thema in de moderne logica. In feite gaat het er niet om, zelfs voor een logicus, om altijd gelijk te hebben, maar om optimaal te leren van verrassende nieuwe feiten! Zo zijn er nog veel meer verbanden tussen logica en cognitiewetenschap, en zelfs tussen logica en ontwikkelingspsychologie: hoe leert een kind nu eigenlijk redeneren? Een logisch systeem beschrijft een ideale expertise, maar kan zo’n systeem worden aangeleerd? En in verband hiermee, wanneer kan een kind zich verplaatsen in het standpunt van iemand anders? Hoewel iedereen wel mensen kent die dit helemaal nooit hebben geleerd, tonen psychologische experimenten aan dat deze ‘theory of mind’ zich doorgaans rond het vierde levensjaar begint te vormen. En die vorm van intelligentie is natuurlijk essentieel voor de interactieve aspecten van de logica zoals we in onze latere hoofdstukken hebben besproken.

100

Hoofdstuk 8

Spel en logica van interactie

Terugkerend naar wat er dan wel in dit boek staat, blijkt ook daar reeds een breed panorama. De logica begon als wiskundige studie van redeneerpatronen, en toonde daarmee de kracht aan van ‘denken over denken’. De resultaten van die studie zijn inmiddels breed uitgewaaierd, van de wiskunde en filosofie tot de informatica en taalkunde - waarbij het werkterrein zich verbreedt tot een veel bredere studie van informatie en rekenprocessen. Wat ons perspectief op ‘Logica in actie’ daaraan nog eens heeft toegevoegd is een verdere rol voor de logica als studie van intelligente interactie die nieuwe verbanden legt met alle genoemde gebieden, maar ook via thema’s als communicatie en spel met nieuwe disciplines zoals de psychologie, economie, en de cognitiewetenschap. Nu kan men dit alles nog wetenschap voor wetenschappers noemen. Is een technisch vak als de logica ook nuttig in de praktijk, en het verbeteren van ons menselijk gedrag? Hier keren we nog even terug naar de prijs die aanleiding was voor dit boekje. Spinoza was een voorvechter van het gebruik van wiskundige methoden op menselijk gedrag, getuige zijn hoofdwerk Ethica More Geometrico Demonstrata. En dit werk bevat passages die goed lijken aan te sluiten bij dit boek, waarbij zelfs nog een levend verschijnsel als emotie te pas komt: “Wanneer de geest zichzelf in zijn vermogen tot handelen beschouwt, verblijdt hij zich [...]”. Maar dat gaat dan wel om een abstracte vreugde: “Blijheid is ’s mensen overgang van geringer tot groter volmaaktheid”. Komt de moderne logica voorbij haar abstracties de werkelijkheid in? Die vraag laten wij over aan de lezers van dit boek.

101

Logica in actie

102

Uitwerkingen van de opgaven Uitwerkingen van de opgaven bij hoofdstuk 2 ∧ p ∧ q is geen formule: uitgezonderd het negatieteken kan een connectief in onze propositielogica niet voorop staan (zie definitie). – p ∨ p is een formule (ook al is de disjunctie in feite overbodig); spreek uit: ‘p of p’. – (p → q) ↔ ¬(¬q → ¬p) is ook een formule; spreek uit: ‘als p dan q’, tussen haakjes, dan en slechts dan als niet, tussen haakjes, als niet q dan niet p’. – p ∧ ∨ q is geen formule, connectieven anders dan ¬ kunnen volgens de definitie van formule nooit direct naast elkaar staan.

2.1

–

2.2

De waarheidstabel voor de formule (p → q) ∨ (q → p) is: p

q

(p

→

q)

∨

(q

→

p)

1 1 0 0

1 0 1 0

1 1 0 0

1 0 1 1

1 0 1 0

1 1 1 1

1 0 1 0

1 1 0 1

1 1 0 0

1

2

1

3

1

2

1

De waarheidstabel voor de formule ((p ∨ ¬q) ∧ r) ↔ (¬(p ∧ r) ∨ q) is: p

q

r

((p ∨

¬

q)

∧

r)

↔ (¬ (p

∧

r)

∨

q)

1 1 1 1 0 0 0 0

1 1 0 0 1 1 0 0

1 0 1 0 1 0 1 0

1 1 1 1 0 0 0 0

1 1 1 1 0 0 1 1

0 0 1 1 0 0 1 1

1 1 0 0 1 1 0 0

1 0 1 0 0 0 1 0

1 0 1 0 1 0 1 0

1 0 0 0 0 0 1 0

0 1 0 1 1 1 1 1

1 1 1 1 0 0 0 0

1 0 1 0 0 0 0 0

1 0 1 0 1 0 1 0

1 1 0 1 1 1 1 1

1 1 0 0 1 1 0 0

1

3

2

1

4

1

5

3

1

2

1

4

1

103

Logica in actie

‘Marie noch Jan gaat naar het feest.’ Goed zijn bijvoorbeeld ¬q ∧ ¬p of ¬p ∧ ¬q. – ‘Of Marie óf Jan gaat naar het feest.’ Heel direct wordt dit (q ∧ ¬p) ∨ (p ∧ ¬q) . Eveneens goed is p ↔ ¬q. – ‘Jan gaat naar het feest, tenzij Marie er naar toe gaat.’ Dit hangt af van hoe we ‘tenzij’ opvatten: in de zin van ‘als niet’ opgevat, wordt de vertaling ¬q → p , en opgevat als ‘desda niet’ wordt het p ↔ ¬q . (Dit komt dus neer op het verschil tussen inclusieve en exclusieve disjunctie, vergelijk ook met het vorige onderdeel van deze opgave.)

2.3

–

2.4

Zij p: ‘Jan gaat’, q: ‘Marie gaat’ en r: ‘Piet gaat’. De uitspraak ‘Als Jan gaat, gaat Marie in ieder geval, en Piet gaat alleen als Jan niet gaat’ kan dan in propositielogica worden uitgedrukt door: (p → q) ∧ (r → ¬p). (Soms wordt ‘alleen als’ niet als →, maar als ↔ opgevat - die mogelijkheid laten we hier buiten beschouwing.) De waarheidstabel voor deze formule is: p

q

r

(p

→

q)

∧

(r

→

¬

p)

1 1 1 1 0 0 0 0

1 1 0 0 1 1 0 0

1 0 1 0 1 0 1 0

1 1 1 1 0 0 0 0

1 1 0 0 1 1 1 1

1 1 0 0 1 1 0 0

0 1 0 0 1 1 1 1

1 0 1 0 1 0 1 0

0 1 0 1 1 1 1 1

0 0 0 0 1 1 1 1

1 1 1 1 0 0 0 0

1

2

1

4

1

3

2

1

De gevallen waarin de formule waar is, zijn in de tabel uit de kolom boven 4 te halen. Het zijn die gevallen (rijen) waarin een 1 staat in de kolom boven 4. Voor deze gevallen kan uit de kolommen onder p, q en r worden afgeleid dat óf Jan en Marie gaan, maar Piet niet, óf Jan gaat niet. Uitwerkingen van de opgaven bij hoofdstuk 3 3.1

104

De waarheidstabel van p ↔ ¬p is: p

p

↔ ¬

p

1 0

1 0

0 0 ↑

1 0

0 1

Uitwerkingen van de opgaven

De aangegeven kolom bevat slechts nullen, dus p ↔ ¬p is een contradictie. De waarheidstabel van p → (q → p) is: p

q

p

→

(q

→

p)

1 1 0 0

1 0 1 0

1 1 0 0

1 1 1 1 ↑

1 0 1 0

1 1 0 1

1 1 0 0

De aangegeven kolom bevat slechts enen, dus p → (q → p) is een tautologie. De waarheidstabel van ¬((p → q) → p) is: p

q

¬

((p →

q)

→

p)

1 1 0 0

1 0 1 0

0 0 1 1 ↑

1 1 0 0

1 0 1 0

1 1 0 0

1 1 0 0

1 0 1 1

De aangegeven kolom bevat niet slechts enen of nullen, dus de formule ¬((p → q) → p) is geen tautologie en ook geen contradictie. Omdat er een waardering is waarvoor de formule waar is, is deze vervulbaar. (Een formule die geen tautologie en ook geen contradictie is wordt ook wel een contingentie genoemd.) 3.2

De waarheidstabel van (p ∧ q) → p is: p

q

(p

∧

q)

→

p

1 1 0 0

1 0 1 0

1 1 0 0

1 0 0 0

1 0 1 0

1 1 1 1 ↑

1 1 0 0

105

Logica in actie

De aangegeven kolom bevat slechts enen, dus (p ∧ q) → p is een tautologie. Deze tautologie hangt samen met de geldige gevolgtrekking p, q ⇒ p. Dit is natuurlijk ook direct te zien: als p en q immers waar zijn, is p zeker waar. 3.3

De waarheidstabellen voor p → q, ¬q en ¬p zijn: p

q

p

→

q

¬

q

¬

p

1 1 0 0

1 0 1 0

1 1 0 0

1 0 1 1

1 0 1 0

0 1 0 1

1 0 1 0

0 0 1 1

1 1 0 0

Alleen in de laatste rij zijn beide uitgangspunten waar, maar dan is de conclusie dat ook. We hebben de betreffende 1-en onderstreept. Dus p → q, ¬q ⇒ ¬p. 3.4

We beginnen met 8 verschillende waarderingen. Na verwerking van de informatie “Als Jan gaat, dan gaat Marie” zijn er hiervan nog 6 over (namelijk de zes waarbij in de kolom voor (p → q) in de uitwerking van opgave 2.4 een 1 staat). Na verwerking van “Piet gaat alleen als Jan niet gaat”, vervalt er van deze 6 waarderingen nog één (namelijk de waardering waarin p, q, en r alledrie waar zijn) en blijven er dus nog 5 waarderingen over.

3.5

De redenering is: “Papa, waarom gaat de zon onder?” “Omdat de zon om de aarde draait, jongen.” “En waarom is dat dan?” “Ja, anders zou ‘ie toch stilstaan boven ons, niet?” Laat propositieletter p staan voor de propositie ‘de zon gaat onder’, en laat propositieletter q staan voor de propositie ‘de zon draait om de aarde’. Voor het gemak vertalen we ‘de zon staat stil’ als ‘de zon gaat niet onder’, dus als ¬p . In een zin als ‘a omdat b’ zeggen we eigenlijk: a is waar, en b impliceert a. De redenering ‘De zon gaat onder omdat de zon om de aarde draait’ komt dus overeen met q, q → p ⇒ p. De redenering ‘Anders zou ‘ie toch stilstaan’ komt overeen met p, ¬q → ¬p ⇒ q. Deze beide redeneringen zijn correct. Samen krijgen we dus de incorrecte redenering ¬q → ¬p, q → p ⇒/ p. Dit is een voorbeeld van de drogreden ‘cirkelredenering’. De redenering komt namelijk overeen met p → q, q → p ⇒/ p. Uitwerkingen van de opgaven bij hoofdstuk 4

4.1

106

– ∃x ∀y x = y is wel een formule, spreek uit: ‘Er is een x waarvoor voor elke y geldt dat x gelijk is aan y’, met andere woorden: er is precies één object.

Uitwerkingen van de opgaven

– ∀x x ≥ y → ∃z y = z is wel een formule. Het maakt niet uit dat y een vrije variabele is. Dit drukt uit: “Als iedere x groter dan of gelijk aan y is, dan is er een z gelijk aan y.” – ∀x ∧ ∃z R(x, z) is geen formule. De conjunctie ∧ moet zowel links als rechts een deelformule hebben, maar dit is alleen rechts het geval. – ∀x x ∧ ∃z z > y is geen formule. Nu heeft de conjunctie links een variabele. Een variabele is geen deelformule, maar een term. – ∀x ∀y ∃z (x > y ∨ y > z) is wel een formule, spreek uit: ‘Voor alle x (en) voor alle y is er een z waarvoor x groter is dan y of y groter is dan z.’ In plaats van ‘voor alle x en voor alle y’ zeggen we ook ‘voor alle x en y’ (dat komt ook omdat bij universele kwantoren de volgorde niet uitmaakt.) 4.2

Gegeven is een verzameling V waarop een kleiner-of-gelijk-relatie ≤ is gedefinieerd. – Er is een kleinste element in V: ∃x (V(x) ∧ ∀y (V(y) → x ≤ y)) – Er is geen grootste element in V: ¬∃x (V(x) ∧ ∀y (V(y) → y ≤ x)) – Er is een maximaal element in V: ∃x (V(x) ∧ ∀y ((V(y) ∧ x ≠ y) → ¬(x ≤ y)))

4.3

We geven het bereik aan van de kwantor ∀y door onderstreping. – ∀x ∀y ∃z y + z = x: geen vrije variabelen. – ∀y ∃z y + z = x: x is vrij. – ∀y ∃z y < z ∧ y > x: x en laatste voorkomen van y (dus in y > x) zijn vrij. – P(y) → ∀y ∃z y < z: eerste voorkomen van y is vrij. Uitwerkingen van de opgaven bij hoofdstuk 5

5.1

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 woorden: er is geen grootste priemgetal. En dit is waar.

5.2

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

107

Logica in actie

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 objecten 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. 5.3

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. 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}

Uitwerkingen van de opgaven bij hoofdstuk 6 6.1

108

In logische taal zijn de beweringen: – ¬K1w2 – ¬(K1w2 ∨ K1¬w2) – ¬K1¬¬K3¬¬r1 De eerste bewering is waar, omdat K1w2 onwaar is. En dat is onwaar, omdat er een toestand voorstelbaar is voor speler 1 waarin w2 onwaar is, namelijk de toestand rbw. De tweede bewering is waar, omdat K1w2 ∨ K1¬w2 onwaar is. In het eerste deel van de opgave zagen we al dat K1w2 onwaar is in toe-

Uitwerkingen van de opgaven

stand rwb. Maar K1¬w2 is eveneens onwaar daar: speler 1 kan zich namelijk ook een toestand voorstellen waarin ¬w2 onwaar is, en dus w2 waar: dit is namelijk het geval in de werkelijke toestand rwb. De derde bewering is waar, omdat speler 1 zich vanuit rwb toestand rwb kan voorstellen, van waaruit speler 3 zich toestand wrb kan voorstellen, waarin 1 niet rood heeft (maar wit). Een ander bewijs van deze bewering is dat speler 1 zich vanuit rwb toestand rbw kan voorstellen, van waaruit speler 3 zich toestand brw kan voorstellen, waarin 1 evenmin rood heeft (maar blauw). 6.2

Gegeven is het model voor drie spelers 1, 2, en 3 die ieder een van de kaarten r, w en b vasthouden. – We laten zien dat K1(K2r2 ∨ K2w2 ∨ K2b2) geldt in situatie rwb. De andere gevallen gaan evenzo. In rwb is het waar dat K1(K2r2 ∨ K2w2 ∨ K2b2) als de formule die door K1 gebonden wordt waar is in alle voor speler 1 voorstelbare situaties. Dit zijn rwb en rbw. In situatie rwb is K2r2 ∨ K2w2 ∨ K2b2 waar als een van de drie disjuncten daar waar is. Omdat speler 2 in die situatie de witte kaart heeft, proberen we het disjunct K2w2 waar te maken. De formule K2w2 is waar in situatie rwb, als de formule w2 die door K2 gebonden wordt waar is in alle voor speler 2 vanuit rwb voorstelbare situaties. Dit zijn rwb en bwr. In rwb is w2 waar, want de waardering van propositieletter w2 in die situatie is 1. We hebben hiermee aangetoond dat in situatie rwb de formule K2r2 ∨ K2w2 ∨ K2b2 waar is. In de andere voorstelbare situatie, rbw, kunnen we eveneens aantonen dat K2r2 ∨ K2w2 ∨ K2b2 waar is, maar in dit geval omdat het conjunct K2b2 waar is. De andere vijf situaties van het model gaan net zo. – In situatie rwb is K3r1 waar, omdat rwb de enige situatie is die speler 3 zich kan voorstellen, en in die situatie r1 waar is: 1 heeft inderdaad de rode kaart. – In situatie rwb is ¬K2r1 waar, omdat het niet zo is dat K2r1 daarin waar is. Er is namelijk een voor speler 2 voorstelbare situatie, bwr, waarin r1 onwaar is: speler 1 houdt in bwr de blauwe kaart vast, niet de rode kaart. Speler 1 weet echter niet dat speler 2 dit niet weet (¬K1¬K2r1). Dit komt omdat speler twee situatie rbw voor mogelijk houdt, waarin speler 2 wel weet dat speler 1 weet dat haar kaart de rode is. – Ten slotte is in situatie rwb formule ¬K1¬K2r1 waar. Deze drukt uit dat speler 1 zich kan voorstellen dat (niet weet dat niet) K2r1 waar is. Dit is inderdaad het geval, want in de voor 1 voorstelbare situatie rbw is K2r1 inderdaad waar, omdat r1 daar waar is in de enige voor speler 2 voorstelbare situaties rbw.

6.3

De beginsituatie beschrijft precies een distributief systeem als in voorbeeld 6.6, met één verschil: in een distributief systeem weet een proces alleen zijn eigen toestand. In het geval van bestipte actoren is die eigen toestand eigenlijk de stip die de actor ziet op het voorhoofd van de ander. Omdat dat fysiek deel uitmaakt van die andere persoon, zou je als het ware net zo goed kunnen zeggen dat die actor nu juist de toestand van de ander kent in

109

Logica in actie

plaats van zijn eigen toestand. Het is lood om oud ijzer. De figuur die deze situatie weergeeft is als volgt:

Ten opzichte van de figuur in voorbeeld 6.6 zijn alleen de voorstelbaarheidsrelaties voor a en b verwisseld; 10 staat voor stip op a’s voorhoofd, geen stip op b’s voorhoofd. Speler/actor a kan situaties 10 en 00 niet van elkaar onderscheiden, waarin zij ziet dat b geen stip heeft, maar zelf of wel of niet een stip heeft. Etc. De mededeling van de buitenstaander elimineert de situatie 00 uit het model. Het resultaat is dus:

In de situatie 10 geldt nu dat a zich geen alternatief kan voorstellen; a weet dus dat zij bestipt is. Als daarentegen zowel a als b bestipt zijn, hebben beiden nog onzekerheid over de situatie. (Met andere woorden: voor elk geldt, dat ze een stip zien. De mededeling van de buitenstaander is zowel waar als alleen de ander een stip heeft, als wanneer ze allebei een stip hebben. Onzekerheid dus.) Nu zegt a : “Ik weet niet of ik bestipt ben.” Dit is de formule ¬(Kap ∨ Ka¬p) . Merk nu op dat deze formule alleen waar is in situaties 01 en 11. We verwerken deze uitspraak dus door het model te beperken tot deze twee situaties:

In het resterende model weet b dat hij bestipt is. Vanuit de werkelijke situatie 11 kan hij zich immers geen andere situatie meer voorstellen.

110

Uitwerkingen van de opgaven

Uitwerkingen van de opgaven bij hoofdstuk 7 7.1

We voeren het ‘graph reachability’ algoritme van voorbeeld 7.7 uit voor de gegeven graaf, met s als beginknoop en t als eindknoop. R is de verzamelingen rode knopen, B is de verzameling blauwe knopen. Om te beginnen is R = {1} en B = ∅. De handeling waarbij we een rode knoop uit R selecteren, blauw maken, en zijn opvolgers rood, noemen we een stap. Merk op dat de selectie van een rode knoop in een stap nondeterministisch (onbepaald) is. We kiezen dus gewoon een rode knoop niet per se de eerste als we de elementen van de verzamelingen R van links naar rechts lezen. Het is mogelijk dat u in uw antwoord een andere keuze gemaakt heeft, maar dat uw antwoord toch goed is. R = {1}

B=∅

R = {2, 3, 7}

B = {1}

R = {3, 4, 7}

B = {1, 2}

R = {4, 5, 6, 7}

B = {1, 2, 3}

R = {4, 5, 7}

B = {1, 2, 3, 6}

R = {5, 7}

B = {1, 2, 3, 4, 6}

R = {5}

B = {1, 2, 3, 4, 6, 7}

R=∅

B = {1, 2, 3, 4, 5, 6, 7}

Kies 1, de opvolgers zijn 2, 3 en 7. Kies 2, de opvolgers zijn 1, 3, en 4; 4 heeft geen kleur. Kies 3, de opvolgers zijn 2, 4, 5, en 6; 5 en 6 hebben geen kleur. Kies 6, alle knopen zijn inmiddels gekleurd. Kies 4. Kies 7. Kies 5.

De knoop t = 4 maakt deel uit van de verzameling B. Dus t is vanuit s bereikbaar. Merk op dat we het algoritme niet stoppen op het moment dat 4 in de verzameling B komt, maar dat het algoritme volgens afspraak pas termineert als de verzameling R leeg is. 7.2

We voeren het ‘vind de bekendheid’ algoritme van voorbeeld 7.6 uit voor de gegeven graaf. De verzameling punten (of mensen) met rode balletjes is R. De keuze voor twee uit R is non-deterministisch (net als in de vorige opgave). We geven de keuze aan in het overzicht hierna - u heeft wellicht een andere keuze gemaakt! R = {1, 2, 3, 4} R = {1, 2, 3}

Kies 2 en 4, 2 kent 4 niet, neem dus 4 rood af.

111

Logica in actie

Kies 1 en 3, 1 kent 3, neem dus 1 rood af.

R = {2, 3}

‘Kies’ 2 en 3, 2 kent 3, neem dus 2 rood af.

R = {3}

We moeten nu testen of de unieke overblijver (er is altijd een unieke overblijver!) een beroemdheid is. Dit is zo, want (1, 3), (2, 3), (4, 3) zitten alledrie in K, maar (3, 3) zit niet in K. Uitwerkingen van de opgaven bij hoofdstuk 8 8.1

In voorbeeld 8.2 heeft Loper geen winnende strategie waarbij hij eerst naar knoop 3 gaat. Stel dat Loper naar knoop 3 gaat. Wat kan Remmer doen om te verhinderen dat Loper 4 en 2 kan bereiken? Het verwijderen van 1 - 3 of 1 - 2 is zinloos omdat dit niet verhindert dat Loper via de snellere 3 - 2 toch bij 2 kan komen. (U kunt dit eventueel tot in detail uitspelen, als dit u nog niet overtuigt.) De andere mogelijkheden zijn: 3 - 2, 2 - 4, of 3 - 4 verwijderen. Als Remmer 3 - 2 verwijdert, gaat Loper met de resterende 3 - 2 naar 2. Daarna kan Remmer 2 - 4 verwijderen, of niet. Zo niet, dan doet Loper 2 - 4: gewonnen. Zo wel, dan gaat Loper over 3 - 2 terug naar 3, waarna er nog twee verbindingen 3 - 4 resteren. Hiervan kan Remmer er maar één verwijderen. Loper's volgende zet is dan 3 - 4. Wederom gewonnen. Echter... laat Remmer nu eens 4 - 2 verwijderen. Als Loper eerst 3 - 2 doet, verwijdert Remmer een 3 - 4, en nadat Loper een 2 - 3 terugdoet, verwijdert Remmer de andere 3 - 4. Stuck! Als Loper in plaats daarvan eerst 3 - 4 doet, verwijdert Remmer een 3 - 2, en nadat Loper dan noodgedwongen terugkeert met 4 - 3, verwijdert Remmer de andere 3 - 2. Loper kan nu nog doorgaan via 3 - 1, waarna Remmer 1 - 2 verwijdert. Ook hier heeft Remmer gewonnen. (We hadden natuurlijk ook meteen met dit geval kunnen beginnen waarin Remmer 4 - 2 verwijdert, zodat we het geval 3 - 2 niet meer hoefden te bespreken; maar zo was het spannender.)

8.2

De beginsituatie is: n1 n2 n3

1

1 0 1

0 0 1

1 1 0

1

2

1

2

We hebben onder iedere kolom het aantal 1-en geteld. Deze situatie is ongebalanceerd, want er zijn posities waarin het aantal 1-en oneven is. Dit

112

Uitwerkingen van de opgaven

betekent dat speler 1 kan winnen. Hiervoor moet die speler natuurlijk van deze ongebalanceerde situatie een gebalanceerde maken! Hiervoor moet speler 1 in één keer de twee oneven kolommen even zien te maken. Dit kan door van stapel n2 drie lucifers over te laten (1 haalt er dus zes weg). De spelsituatie is nu: n1 n2 n3

1 1

0 1 1

1 1 0

2

2

2

Deze situatie is gebalanceerd. Wat 2 ook doet, de situatie zal nu ongebalanceerd worden. Om het spel niet al te lang te laten duren (en waarom zouden we ook, want 1 en 2 weten toch al hoe het moet aflopen), laten we 2 het stapeltje n1 weghalen. De situatie is nu: n2 n3

1

1 1

1 0

1

2

1

Hierop antwoord 1 met het verwijderen van drie lucifers van de stapel n3 met zes. (En dit is de enige manier waarop 1 kan winnen!) De situatie wordt nu: n2 n3

1 1

1 1

2

2

Speler 2 heeft er genoeg van, en verwijdert stapel n2, waarna speler 1 stapel n3 verwijdert. Speler 1 heeft inderdaad gewonnen. 8.3

Gegeven is de strategische matrix:

ontwapenen bewapenen

ontwapenen

bewapenen

(3, 3) (4, 0)

(0, 4) (–10, –10)

113

Logica in actie

Het strategiepaar (bewapenen, bewapenen) is geen Nash-evenwicht. Laat 1 de rijspeler zijn en 2 de kolomspeler. Stel dat 1 aanneemt dat 2 ‘bewapenen’ kiest. Als 1 in plaats van ‘bewapenen’ voor ‘ontwapenen’ kiest, is de winst 0 in plaats van –10. Het is dan dus beter te ontwapenen. Het strategiepaar (bewapenen, bewapenen) is dus geen Nash-evenwicht. Neem nu het paar (ontwapenen, ontwapenen). Als 1 aanneemt dat 2 ontwapent, dan heeft het voor 1 zin te gaan bewapenen, omdat haar uitkomst dan 4 is in plaats van 3. Dus (ontwapenen, ontwapenen) is evenmin een Nash-evenwicht. We onderzoeken nu het paar (bewapenen, ontwapenen). Stel nu dat 2 aanneemt dat 1 voor bewapenen kiest. Voor 2 heeft het dan geen zin van strategie te veranderen, omdat zijn uitkomst in het alternatief (bewapenen, bewapenen) dan nog lager is: –10 in plaats van 0. Voor 1 heeft het ook geen zin van strategie te veranderen, omdat de alternatieve opbrengt 3 in (ontwapenen, ontwapenen) kleiner is dan 4. Het paar (bewapenen, ontwapenen) is dus een Nash-evenwicht. Evenzo is het paar (ontwapenen, bewapenen) een Nash-evenwicht. Ook al hebben we nu twee Nash-evenwichten, het lijkt op grond hiervan nog niet duidelijk wat nu voor 1 en 2 de beste strategie is. Een antwoord hierop is te geven als we het begrip ‘gemengde strategie’ erbij betrekken dit voert hier echter te ver. 8.4

114

Bederver kan (bijvoorbeeld) als volgt in twee zetten winnen: Bederver kiest rwb in 6.10. Verdubbelaar kiest rwb in 6.7. Bederver kiest wrb in 6.10. Verdubbelaar kiest rbw in 6.7. Er is nu een structureel verschil, want er is wel een 3-pijl van rwb naar wrb in de restrictie van 6.10 tot de twee gekozen toestanden, maar er is niet een 3-pijl van rwb naar rbw in de restrictie van 6.10 tot de twee gekozen toestanden. Merk op dat na de tweede keuze van Bederver Verdubbelaar echt niet kan winnen, want de andere keuze rwb voor Verdubbelaar leidt evenmin tot succes.

Register actor 64 afsluitende stap 16 al-kwantor 43 argumentatietheorie 35 atomaire formule 46 backwards induction 89 basisstap 16 bereik 18, 47 beslisbaar 80 bevestiging van het gevolg 35 bewijs 2 bewijstaak 74 bisimulatie 76 Boole vi, 73 Church 80 cirkelredenering 36 conjunct 14 conjunctie 14 conjunctieteken 14 connectieven 15 constante 40 contingentie 105 contradictie 29 correctheidsbewering 58 deelformule 17, 47 disjunct 14 disjunctie 14 disjunctieteken 14 distributief systeem 68 doenlijk 80 dominante strategie 91 drogreden 35 éénplaatsig 42 Ehrenfeucht-Fraïssé-spel 93 epistemische logica 65 equivalentie 15 equivalentieteken 15 Euclides vi, 2 evaluatietaak 75

exclusieve disjunctie 23 existentiebewijs 7 existentiële kwantor 44 falsum 30 formule 17, 46 formulevariabele 17 Frege vii functiesymbool 47 gebonden variabele 48 Gelfond-Schneider 8 gevolg 30, 56 Gödel vii, 80 Goldbach 39, 45 haakjes 17 halting problem 80 implicatie 15 implicatieteken 15 inductiestap 16 inductieve definitie 16 intractable 80 kennislogica 65 kwantor 43, 44 Leibniz vii lineaire tijd 76 logisch gevolg 30, 56 logisch programmeren 61 logische equivalentie 32 loodlijn 4 modale logica 65 modale operator 65 modaliteit 65 model 28, 53 model checking 75 modeleliminatie 34 multi-actorsysteem 64

115

Logica in actie

nand 24 Nash-evenwicht 90 negatie 14 negatieteken 14 n-plaatsig 42 nulsom-spel 85 onbeslisbaar 80 ondoenlijk 80 predikaat 40 predikaatlogisch gevolg 56 predikaatsymbool 40 principe van uitgesloten derde 29 prisoners’ dilemma 90 programmaspecificatie 58 Prolog 60 propositie 12 propositieletter 15 propositielogische connectieven 15 publieke bekendmaking 70 Pythagoras 2 rationale getallen 5 samengestelde formules 17, 47 satisfiability 74 specificatie 58 spel 83 spelboom 85 stelling 2 stelling van Gelfond-Schneider 8 stelling van Pythagoras 2 stelling van Zermelo 85 stellingbewijzen 74

116

stopprobleem 80 strategie 84 strategisch spel 90 tautologie 28 term 46 theorem proving 74 theory of mind 68 tijdscomplexiteit 79 toekenningsopdracht 57 tractable 80 tweeplaatsig 42 universele kwantor 43 update 34, 70 variabele 42 verborgen aanname 35 vergelijkingstaak 75 verificatietaak 75 vermoeden van Goldbach 39, 45 verum 30 vervulbaar 28, 55, 74 voorstelbaar 65 voorstelbaarheidsrelatie 65 vrije variabele 48 waardering 28 waarheid 18, 52 waarheidsfunctioneel 13 winnende strategie 84 winstrategie 84 Zermelo 85