Logica in actie [Lecture notes] [PDF]

Zitiervorschau

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 ‘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 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 ( 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