Propositielogica beschrijft ook informatiestromen op basis van observaties of feiten die vermeld worden. Een eenvoudig voorbeeld laat zien hoe.
Beschouw een eenvoudig feestje met maar drie mogelijke genodigden Anna, Bob en Claudia. Elke genodigde komt ook daadwerkelijk naar het feestje. Welke uitnodiging kun je sturen zonder dat er een conflict ontstaat vanwege onderstaande mededelingen?
- Bob komt naar het feestje als Anna of Claudia komt.
- Anna komt naar het feestje als Claudia niet komt.
- Als Anna naar het feestje komt, dan komt Bob niet.
We gebruiken de letters \(a\), \(b\) en \(c\) respectievelijk voor "Anna komt naar het feestje.", "Bob komt naar het feestje.", en "Claudia komt naar het feestje." We zetten een streepje boven de letter als de persoon niet naar het feestje komt. De \(\bar{a}\) geeft aan dat Anna niet naar het feestje komt. Er zijn in principe \(2^3=8\) mogelijke samenstellingen van het feestje: \(abc\), \(ab\bar{c}\), \(a\bar{b}c\), \(\bar{a}bc\), \(\bar{a}\bar{b}c\), \(\bar{a}b\bar{c}\), \(a\bar{b}\bar{c}\) en \(\bar{a}\bar{b}\bar{c}\).
De eerste mededeling is de propositie \(a\lor c\rightarrow b\) en sluit de opties \(a\bar{b}c\), \(\bar{a}\bar{b}c\) en \(a\bar{b}\bar{c}\) uit.
De tweede mededeling is de propositie \(\neg\, c\rightarrow a\) en sluit nog twee opties uit: \(\bar{a}b\bar{c}\) en \(\bar{a}\bar{b}\bar{c}\).
De derde mededeling is de propositie \(a\rightarrow \neg\, b\) sluit nog twee opties uit: \(abc\) en \(ab\bar{c}\)
De enige samenstelling van het feestje die overblijft is \(\bar{a}bc\). Kortom: stuur Bob en Claudia een uitnodiging voor het feestje om conflicten te vermijden.
De redenering is formeler wanneer we een waarheidstabel voor de uitspraken \(u_1: (a\lor c)\rightarrow b\), \(u_2: \neg\,c\rightarrow a\), \(u_3: a\rightarrow \neg\,b\) en de propositie \(u_1\land u_2\land u_3\) opstellen. \[\begin{array}{ccc|cccc} a & b & c & u_1 & u_2 & u_3 & u_1\land u_2\land u_3\\ \hline 0 & 0 & 0 & 1 &0 & 1 & 0\\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 \end{array}\] Regel 4 in de tabel is de enige regel waarin in de laatste kolom de waarheidswaarde 1 (waar symboliserend) staat. Dit is de situatie dat Bob en Claudia naar het feestje komen. Hen kun je een uitnodiging sturen zonder in problemen te komen.
Je kunt met propositielogica ook raadsels oplossen!
Op een rij staan drie stoelen en drie jongens nemen elk op één van deze stoelen plaats. Een vriend van hen zegt dat hij 5 petjes bij zich: twee blauwe en drie rode. Hij zet bij elk van hen een petje op zonder dat de jongens kunnen zien welk petje ze zelf op hebben. De achterste jongen ziet de petjes van de twee jongens die voor hem zitten. De middelste ziet enkel het petje van de voorste jongen op de rij, die zelf geen enkel petje ziet.
Aan de jongen op de achterste stoel wordt gevraagd: “Weet jij welke kleur van pet je op hebt?” Hij kijkt naar de twee petjes voor zich, denkt even na en antwoord dan naar waarheid: “Nee.” Vervolgens wordt dit aan de middelste jongen gevraagd. Die ziet maar één petje voor zich, denkt na en antwoordt ook ontkennend. De voorste jongen is even stil en zegt dan: “Dan weet ik de kleur van mijn petje!”
Welke kleur is dat?
De jongen op de voorste stoel heeft een rood petje op.
We kunnen alle mogelijke petjesverdeling bekijken.: \(rrr\), \(rrb\), \(rbr\), \(brr\), \(bbr\), \(brb\) en \(rbb\), waarbij de letter \(r\) een rood petje symboliseert en \(b\) een blauw petje; bovendien staan de letters van links naar rechts op volgorde van achterste, middelste en voorste petjedrager.
Het antwoord van de jongen op de achterste stoel sluit de optie \(rbb\) uit: als hij 2 blauwe petjes ziet, dan weet hij uit de informatie van de vriend over het gebruik van drie rode en 2 blauwe petjes dat hij een rood petje heeft. Maar hij zegt dat hij het niet weet. Dus \(rbb\) kan niet.
Het antwoord van de jongen op de middelste stoel sluit de opties \(rrb\) en \(brb\) uit: als de jongen op de voorste stoel een blauw petje op heeft, dan kan hijzelf niet ook een blauw petje op hebben omdat de jongen op de achterste rij wel geweten had welk petje hij op had.
Blijven alleen maar opties over met de letter rechts gelijk aan \(r\): de jongen op de voorste stoel heeft dus een rood petje op.
In bovenstaande oplossing van het raadsel hebben we alle mogelijke petjesverdelingen bekeken en wat er van over blijft in de scenario. Maar bij grote raadsels is het aantal mogelijkheden immens. Een kortere oplossing van het raadsel zonder alle mogelijke petjesverdelingen eerst op te sommen kan als volgt gaan.
De achterste jongen ziet geen twee blauwe petjes voor zich want dan zou hij kunnen concluderen dat hij een rood petje op heeft omdat er geen petjes van een andere kleur meer beschikbaar zijn.
Dit betekent dat er drie mogelijke petjesverdelingen mogelijk zijn voor de jongens op de middelste en voorste stoel: \(rr\), \(rb\) en \(br\). Maar als de jongen op de middelste stoel een blauw petje voor zich ziet, dan weet hij de kleur van eigen petje al: als het blauw zou zijn, dan had de jongen op de achterste stoel ook al geweten hebben wat voor petje hij op heeft. De overgebleven optie \(rb\) valt ook af.
Omdat de jongen op de middelste stoel "Nee." antwoord weet de jongen op de voorste stoel dat de enige resterende mogelijkheden \(rr\) en \(br\) zijn. In beide gevallen heeft hij een rood petje op. Dus kent hij de kleur van zijn petje.
Onderstaande puzzel komt uit het boek De prinses of de tijger? van Raymond Smullyan.
De koning van een land ver weg beleeft er plezier aan om zijn gevangenen logische puzzels te laten oplossen. Verder wil hij zijn twee dochters aan een man ten huwelijk geven die de kunst van het redeneren als een meester beheerst. Een gevangene heeft de keuze om een van twee deuren te openen. Achter elke deur zit of een prinses of een tijger. Aan de deuren hangen bordjes die de gevangene informatie geven:
Deur 1: "Achter deze deur zit een prinses, en achter de andere deur een tijger."
Deur 2: "Achter een van de twee deuren zit een prinses, en achter de andere een tijger."
De koning vertelt de gevangene dat één van de twee bordjes de waarheid vertelt, maar het andere niet. Als de koning de waarheid spreekt en de gevangene liever met de prinses trouwt dan door de tijger wordt opgegeten, welke deur moet hij dan openen?
Hij moet deur 2 openen om met de prinses te trouwen.
Precies een van de twee bordjes is waar. Stel dus dat het bordje op deur 1 waar is. Dan zit achter deur 1 een prinses en achter deur 2 een tijger te wachten. Dat maakt het bordje op deur 2 ook waar, maar dat kan niet, want de koning zei dat er maar een van de twee bordjes waar was. We hebben dus een tegenspraak. Hieruit kunnen we concluderen dat het bordje op deur 1 onwaar is en het bordje op deur 2 waar, dat wil zeggen: achter een van de deuren zit een prinses en achter de andere een tijger. Omdat het bordje op deur 1 onwaar is, kan het niet zo zijn dat de prinses achter deur 1 zit en de tijger achter deur 2. De enige mogelijkheid is dus dat de prinses achter deur 2 zit en de tijger achter deur 1. De gevangene doet er dus verstandig aan deur 2 te openen.
Nu gaan we het probleem met behulp van onze logische notatie formaliseren en oplossen. Er zijn vier mogelijke situaties, want achter elke deur kan of een prinses of en tijger zitten. Laat \(p_1\) staan voor "Er zit een prinses achter deur 1." , en laat \(p_2\) staan voor "Er zit een prinses achter deur 2." De vier mogelijke situaties komen dan overeen met de vier mogelijke toekenningen van waarheidswaarden aan deze twee beweringen. De bewering op deur 1 kunnen we nu opschrijven als \[d_1: p_1\land \neg\,p_2\] terwijl de bewering op deur 2 te schrijven valt als \[d_2: (p_1\lor p_2)\land (\neg\,p_1 \lor \neg\, p_2)\] dat wil zeggen: er is een prinses in kamer 1 of 2, en er is een tijger (en dus: geen prinses) in kamer 1 of 2. Laten we deze twee formules afkorten als respectievelijk \(d_1\) en \(d_2\). De koning zegt nu dat precies een van de twee bordjes waar moet zijn, dus \[(d_1 \land \neg d_2) \lor (\neg d_1 \land d_1)\] Nu het probleem tot propositionele taal getranscribeerd is, is de vraag nu: in welke situaties is deze formule waar? De waarheidstabel voor de laatste formule geeft het antwoord: \[\begin{array}{cc|ccc} p_1 & p_2 & d_1 & d_2 & (d_1 \land \neg d_2) \lor (\neg d_1 \land d_1)\\ \hline 0 & 0 & 0 & 0 &0 \\ 0 & 1 & 0 & 1 &1 \\ 1 & 0 & 1 & 1 & 0\\ 1 & 1 & 0 & 0 & 0 \end{array}\] Er is dus maar een situatie waarin de koning de waarheid vertelt, regel 2 van de waarheidstabel, de situatie waarin de tijger achter deur 1 zit en de prinses achter deur 2.
Strikt genomen hebben we de laatste kolom niet nodig want we kunnen in de deeltabel met de eerste vier kolommen ook gewoon zien dat er maar één rij is waarin één van de uitspraken op de deuren waar is (hetgeen de koning ook zegt).
Logische puzzels
