Waarheid van formules

Als we een aantal atomaire uitspraken hebben die we tot een formule samenvoegen, kunnen we proberen te beslissen of de hele formule waar of onwaar is.

Waarheid van een uitspraak

Eerst maken we duidelijk wat de waarheidswaarde van een uitspraak is. Bij een uitspraak p moeten we kunnen beslissen of ze waar of onwaar is. Een ware uitspraak heeft waarheidswaarde 1 en een onware uitspraak waarheidswaarde 0.

Een waarheidswaardetoekenning is dan een voorschrift e dat aan een gegeven uitspraak 0 of 1 toekent. Als we e(p) schrijven, willen we weten of de uitspraak p waar is. Als p de uitspraak “twee keer twee is vier” is, dan is e(p) = 1, omdat dit een ware uitspraak is. Als q de uitspraak “Daan is een vrouw” is, dan is e(q) = 0, omdat Daan geen vrouw is. e is dus een functie die ons teruggeeft of een uitspraak waar is.

Hierbij moeten we beseffen dat e geen magische functie is die alles in de wereld weet. De functie doet wat wij zeggen. Ze weet niet of Daan een man of een vrouw is. Aan het begin van de berekening moeten wij vastleggen hoe de toekenningsfunctie zich gedraagt. Als we haar vertellen dat Daan een vrouw is, geeft ze ons e(q) = 1.

Waarheid van logische voegwoorden

Om de waarheid van een formule te kunnen bepalen, moeten we weten hoe we de waarheid van logische voegwoorden vaststellen. Dus als we de toekenningen e(p) en e(q) kennen, wat is dan de waarheidswaarde van de formules p ∧ q, p ⇒ q enzovoort?

Elk logisch voegwoord gedraagt zich anders en wordt voor iets anders gebruikt, dus we behandelen elk voegwoord apart.

Waarheid van de conjunctie

De conjunctie schrijven we p ∧ q en lezen we “p en tegelijk q”. Neem als voorbeeld de formule “Nederland ligt in West-Europa en tegelijk is de hoofdstad Amsterdam”. Wanneer is deze hele zin waar?

Het voegwoord “en tegelijk” zelf helpt ons om de waarheid te bepalen. Het zegt uitdrukkelijk dat zowel de uitspraak links als de uitspraak rechts waar moet zijn. Als dus beide uitspraken p en q waar zijn, dus e(p) = 1 en e(q) = 1, dan is ook de hele conjunctie waar. In het andere geval, waarin een van de uitspraken onwaar is of beide onwaar zijn, is de hele formule onwaar.

Een voorbeeld van een conjunctie die niet waar is: “De Rijn is een rivier en tegelijk stroomt de Rijn door Rusland”. Het klopt dat de Rijn een rivier is, maar het klopt niet dat hij door Rusland stroomt, dus de hele conjunctie is niet waar.

Dit staat overzichtelijk in de volgende tabel:

$$\begin{array}{ccc}p& q& p\wedge q\\ 1& 1& 1\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 0\end{array}$$

In de eerste twee kolommen staan de waarheidswaarden van de uitspraken p en q en in de derde de waarheidswaarde van de formule p ∧ q.

Waarheid van de disjunctie

De disjunctie schrijven we p ∨ q en lezen we “p of q”. Een voorbeeld: “Rusland ligt in Europa of in Azië.” Wanneer is de hele zin waar?

Bij een disjunctie is het genoeg dat minstens één van de mogelijkheden waar is. Het voegwoord “of” laat ons kiezen: het is genoeg dat het linkerdeel of het rechterdeel waar is. Het enige kleine verschil met gewoon taalgebruik is dat het logische “of” ook waar is als beide uitspraken tegelijk waar zijn. Dat is niet gebruikelijk: in de omgangstaal gebruiken we “of” vaak uitsluitend, dus “ofwel … ofwel …”.

Daar bestaat een klassieke grap over: een gezin kiest bij een autodealer een nieuwe auto. Vader zegt tegen de verkoper: “We hebben besloten dat we een blauwe of een rode auto nemen.” De verkoper verkocht hun allebei de auto's. Dit illustreert het verschil tussen het logische en het gesproken “of”: vader bedoelde waarschijnlijk dat ze precies één van die auto's zouden kiezen, terwijl de verkoper het een geldige mogelijkheid vond om hun beide auto's te verkopen.

De vorige zin over Rusland is waar, omdat beide uitspraken waar zijn. De zin “het getal 7 is deelbaar door 3 of het getal 7 is een priemgetal” is waar, omdat zeven een priemgetal is. Het is dan wel niet deelbaar door drie, maar dat maakt ons niet uit. De tabel met waarheidswaarden:

$$\begin{array}{ccc}p& q& p\vee q\\ 1& 1& 1\\ 1& 0& 1\\ 0& 1& 1\\ 0& 0& 0\end{array}$$

Waarheid van de implicatie

De implicatie schrijven we p ⇒ q en lezen we “als p, dan q”. Een voorbeeld van een implicatie is de zin “als we veel ijs eten, dan krijgen we buikpijn”. Wanneer is de zin waar?

De logische implicatie is het verraderlijkste van alle voegwoorden. Ook in de omgangstaal wordt ze vaak niet goed begrepen en verward met de equivalentie. Laten we proberen de vraag te beantwoorden of ook de omgekeerde implicatie geldt: q ⇒ p.

We weten dat we buikpijn krijgen als we veel ijs eten. Geldt ook dat we veel ijs hebben gegeten als we buikpijn hebben? Dat geldt zeker niet. We kunnen iets heel anders hebben gegeten en toch ziek zijn geworden, of we kunnen van iets heel anders buikpijn hebben. De omgekeerde implicatie hoeft dus niet automatisch te gelden. Als p ⇒ q geldt en tegelijk q ⇒ p, dan is het een equivalentie, zie hieronder.

Een ander voorbeeld: “als het morgen regent, dan neemt Daan een paraplu mee”. En nu vertel ik je dat Daan een paraplu bij zich had. De vraag is: heeft het die dag geregend? Veel mensen zeggen meteen dat het natuurlijk geregend heeft, want Daan nam een paraplu mee toen het zou gaan regenen. Maar zo is de oorspronkelijke zin niet opgebouwd!

Daan kan in werkelijkheid een paraplu hebben meegenomen om een andere reden, waar wij niets van weten. Misschien neemt Daan altijd een paraplu mee als hij zijn oma bezoekt, omdat zij die graag leent. Of hij heeft besloten een nieuwe paraplu te kopen en wil de oude weggooien. Dat zijn allemaal volkomen legitieme redenen waarom Daan een paraplu kan hebben meegenomen, ook al hoefde het niet te regenen.

Nu kunnen we de vraag beantwoorden wanneer een implicatie waar is. Als beide uitspraken waar zijn, is de implicatie zeker waar: “als 42 een natuurlijk getal is, dan is het positief”. Beide uitspraken zijn waar, dus de hele implicatie is waar. Een ander voorbeeld is de implicatie “als 42 een natuurlijk getal is, dan is het negatief”. Deze implicatie is niet waar, omdat we proberen uit iets wat waar is iets af te leiden wat niet waar is.

Tot slot blijven de gevallen over waarin de eerste uitspraak onwaar is. Dan maakt de waarheid van de tweede uitspraak ons niet meer uit. Als we van iets onwaars uitgaan, kunnen we daarna blijven beweren wat we willen. Het zijn zinnen als “als 1 een negatief getal is, dan ben ik de koning van Nederland” of “als Rotterdam een berg is, dan is de zon blauw”. In zulke gevallen is de implicatie automatisch waar, juist omdat ze van iets onwaars uitgaat. De tabel:

$$\begin{array}{ccc}p& q& p\Rightarrow q\\ 1& 1& 1\\ 1& 0& 0\\ 0& 1& 1\\ 0& 0& 1\end{array}$$

Waarheid van de equivalentie

De equivalentie schrijven we p ⇔ q en lezen we “p dan en slechts dan als q”. Een voorbeeld van een equivalentie is “het getal x is deelbaar door twee dan en slechts dan als het even is”. Wanneer is de hele zin waar?

Bij een equivalentie verwachten we dat de twee uitspraken zo met elkaar samenhangen dat ze ofwel allebei gelden, ofwel geen van beide. Dus ofwel is het getal x even en tegelijk deelbaar door twee, ofwel is het geen van beide. Het kan niet gebeuren dat x even is maar niet deelbaar door twee.

Een voorbeeld: “Bram leest een boek dan en slechts dan als hij op de wc zit.” Om de equivalentie waar te laten zijn, moet Bram altijd een boek lezen als hij op de wc zit. En tegelijk moet hij altijd op de wc zitten als hij een boek leest. Het kan niet gebeuren dat hij bijvoorbeeld in bed een boek leest.

We kunnen de equivalentie uitdrukken met twee implicaties. p ⇔ q kunnen we dus herschrijven als p ⇒ q en tegelijk q ⇒ p. De tabel:

$$\begin{array}{ccc}p& q& p\iff q\\ 1& 1& 1\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}$$

Negatie

De negatie is een unaire bewerking. We schrijven haar met een accent p' of met dit symbool: ¬p. De negatie ontkent de oorspronkelijke bewering. Bij de uitspraak “Emma is zangeres” krijgen we als negatie de uitspraak “Het is niet waar dat Emma zangeres is” of kortweg “Emma is geen zangeres”. Vrijwel altijd kunnen we een negatie vormen door voor de uitspraak “Het is niet waar dat…” te zetten.

De negatie keert de waarheidswaarde om: van 0 maakt ze 1 en van 1 maakt ze 0. We kunnen dus schrijven ¬0 = 1 en ¬1 = 0.

Pas op voor enkele verraderlijke dingen. Neem de bewering “sneeuw is wit”. Wat is de negatie? Je zou kunnen denken dat het “sneeuw is zwart” is, maar dat klopt niet! Als we de vorige regel toepassen, is de negatie de uitspraak “het is niet waar dat sneeuw wit is”. Betekent dat noodzakelijk dat sneeuw zwart moet zijn? Nee, het kan bijvoorbeeld ook roze zijn.

Tabel van alle voegwoorden

$$\begin{array}{cccccc}p& q& p\wedge q& p\vee q& p\Rightarrow q& p\iff q\\ 1& 1& 1& 1& 1& 1\\ 1& 0& 0& 1& 0& 0\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 0& 0& 1& 1\end{array}$$

Waarheid van een hele formule

Nu kunnen we de waarheid bepalen van twee uitspraken die met een logisch voegwoord zijn verbonden. Een hele formule evalueren we volkomen analoog. Als we de formule (p ⇒ q) ∧ r hebben, dan krijgen we, zodra we de formule (p ⇒ q) bijvoorbeeld tot 1 hebben herleid, een gewone conjunctie 1 ∧ r, die we al kunnen oplossen.

Door de eenvoudigste logische voegwoorden stap voor stap toe te passen komen we bij de uiteindelijke waarheidswaarde van de hele formule. Hiervoor gebruiken we vaak de zogeheten waarheidstabel, die hieronder wordt beschreven.

Waarheidstabel

De waarheidstabel gebruiken we om ingewikkelder formules te evalueren. In de eerste n kolommen schrijven we de n propositiesymbolen waarmee de formule werkt, en in de volgende kolommen zetten we een voor een de deelformules die de formule bevat. Aan de hand van een voorbeeld wordt het duidelijker:

Neem de formule (p ∨ q) ∧ (q ⇒ p). Aan het begin schrijven we in de tabel alle propositiesymbolen, dus p en q, en alle combinaties van hun toekenningen:

$$\begin{array}{cc}p& q\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Vervolgens zetten we er kolommen bij voor de afzonderlijke deelformules p ∨ q en q ⇒ p.

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Nu evalueren we deze formules en vullen we nullen of enen in de kolommen in. In de tabel hebben we alle benodigde informatie. We gaan als volgt te werk: als we p ∨ q in de eerste rij evalueren, vullen we voor p een 1 in en voor q ook een 1. Zo krijgen we de uitdrukking 1 ∨ 1. De uitkomst hiervan is weer 1, dus we schrijven een één in de tabel:

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Zo vullen we stap voor stap de hele tabel in:

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1& 1& 1\\ 1& 0& 1& 1\\ 0& 1& 1& 0\\ 0& 0& 0& 1\end{array}$$

Nu moeten we nog de hele formule evalueren. Noem haar bijvoorbeeld φ = (p ∨ q) ∧ (q ⇒ p). We voegen aan de tabel een kolom met φ toe en evalueren die, waarbij we de vorige twee kolommen gebruiken.

$$\begin{array}{ccccc}p& q& p\vee q& q\Rightarrow p& \phi \\ 1& 1& 1& 1& 1\\ 1& 0& 1& 1& 1\\ 0& 1& 1& 0& 0\\ 0& 0& 0& 1& 0\end{array}$$

De tabel is nu compleet en geeft ons de waarheidswaarde van de formule bij alle mogelijke toekenningen. Als bijvoorbeeld e(p) = 1 en tegelijk e(q) = 1, dan is de formule waar. Als e(p) = 0 en e(q) = 1, dan is de formule niet waar.

Merk op dat we niet kunnen zeggen “de formule is waar”. Deze zin heeft geen betekenis, want om te kunnen zeggen dat de formule waar is, zouden we moeten zeggen bij welke toekenning de formule waar is. We kunnen dus zeggen: “formule φ is waar bij toekenning e₁ en niet waar bij toekenning e₂”.

Het enige geval waarin we kunnen zeggen dat de formule waar is, is als ze bij alle mogelijke toekenningen waar is. De formule p ∨ ¬p is bijvoorbeeld bij alle toekenningen waar, dus we kunnen zeggen dat de formule waar is. Hetzelfde geldt voor een formule die bij alle toekenningen onwaar is.

Zulke formules hebben een eigen naam. Een formule die bij alle toekenningen waar is, heet een tautologie. Een formule die bij geen enkele toekenning waar is, heet een contradictie.