Voorbeelden bij propositielogica

In dit artikel laten we een aantal formules en hun mogelijke toekenningen zien met behulp van de waarheidstabel.

Eerste voorbeeld

We proberen te achterhalen wanneer deze formule waar is: ϕ = (p ∧ q) ∨ ¬q. We schrijven de propositiesymbolen p en q in de tabel:

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

Daarna schrijven we in de tabel het eerste deel van de formule: (p ∧ q), de negatie ¬q en dan de hele formule:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Nu berekenen we de waarden voor de derde kolom, dat is een eenvoudige conjunctie, en ook voor de negatie. Daar vullen we gewoon de omgekeerde waarden in van die in de tweede kolom:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}$$

Tot slot berekenen we de waarden in de laatste kolom. Dat is de hele formule. Volgens onze tabel berekenen we dus de disjunctie “tussen de derde en de vierde kolom”. Het resultaat:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0& 1\\ 1& 0& 0& 1& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 1\end{array}$$

Tweede voorbeeld

Dezelfde opdracht, een andere formule: ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q). We zien dat in de formule de propositiesymbolen p en q en hun negaties voorkomen. Daarom maken we eerst een tabel met twee symbolen en hun negaties:

$$\begin{array}{cccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q\\ 1& 1& 0& 0\\ 1& 0& 0& 1\\ 0& 1& 1& 0\\ 0& 0& 1& 1\end{array}$$

Vervolgens voegen we de formules p ∧ ¬q en ¬p ⇒ q toe, die we nu gemakkelijk kunnen evalueren, omdat we in de tabel zowel de toekenningen van de afzonderlijke uitspraken als van hun negaties hebben. De tabel ziet er zo uit:

$$\begin{array}{cccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)\\ 1& 1& 0& 0& 0& 1\\ 1& 0& 0& 1& 1& 1\\ 0& 1& 1& 0& 0& 1\\ 0& 0& 1& 1& 0& 0\end{array}$$

Als laatste moeten we nog de hele formule evalueren, en dat is de equivalentie tussen de laatste twee kolommen:

$$\begin{array}{ccccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)& \varphi \\ 1& 1& 0& 0& 0& 1& 0\\ 1& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 0\\ 0& 0& 1& 1& 0& 0& 1\end{array}$$

Derde voorbeeld

Het derde voorbeeld is wat ingewikkelder: we nemen drie propositiesymbolen, waardoor de berekening van de tabel omvangrijker wordt. De formule ziet er zo uit: ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)).

Omdat we drie propositiesymbolen hebben, is het totale aantal mogelijke toekenningen gelijk aan acht:

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

Verder gaan we net zo te werk als in het vorige geval: we evalueren elke kolom in alle acht de rijen. De hele tabel ziet er zo uit:

$$\begin{array}{ccccccccc}p& q& r& \mathrm{\neg }p& (p\Rightarrow q)& (\mathrm{\neg }p\vee q)& \mathrm{\neg }(p\Rightarrow q)& (r\iff (\mathrm{\neg }p\vee q))& \varphi \\ 1& 1& 1& 0& 1& 1& 0& 1& 0\\ 1& 1& 0& 0& 1& 1& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 0& 1& 0\\ 0& 1& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 1& 1& 1& 1& 0& 1& 0\\ 0& 0& 0& 1& 1& 1& 0& 0& 0\end{array}$$

Vierde voorbeeld

Dit voorbeeld geven we niet als gewone formule, maar als contextopgave. Drie vrienden die naar een groot feest willen waar een dj muziek draait, mogen elkaar niet zo en stellen voorwaarden waaronder ze naar het feest gaan. Ze heten Mees, Jesse en Pim. De regels zijn als volgt:

1. Als Mees gaat, dan gaat ook Jesse.
2. Pim komt naar het feest of, als Mees komt, dan komt Jesse niet.
3. Pim komt dan en slechts dan als Mees niet komt of Jesse niet komt.

De vraag is: kunnen ze alle drie naar het feest komen? Zo niet, wie kan er dan naar het feest gaan zonder een van de regels te overtreden?

Eerst moeten we de bovenstaande zinnen omschrijven naar propositiesymbolen en formules. We noemen de propositiesymbolen M, J en P (Mees, Jesse, Pim) en elk symbool staat voor een uitspraak als “Mees gaat naar het feest”. De eerste regel kunnen we zo schrijven: M ⇒ J, dus “als M, dan J”, ofwel “als Mees naar het feest gaat, dan gaat Jesse naar het feest”.

De tweede regel schrijven we zo. De regel begint met de zin “Pim komt naar het feest of…”, dus we hebben duidelijk een disjunctie nodig. Voorlopig schrijven we dit: P ∨ … Het volgende deel van de zin zegt: “als Mees komt, dan komt Jesse niet”. Dat is een implicatie, waarbij we aan de rechterkant ook nog een negatie moeten gebruiken. “Jesse komt niet” = ¬J. De hele implicatie ziet er zo uit: M ⇒ ¬J. Die voegen we toe aan de vorige disjunctie: P ∨ (M ⇒ ¬J).

De derde regel schrijven we zo om: we beginnen met “Pim komt dan en slechts dan”. Dat betekent een equivalentie: P ⇔ … Verder hebben we “Mees komt niet of Jesse komt niet”, wat we zo schrijven: ¬M ∨ ¬J. Samen: (P ⇔ (¬M ∨ ¬J)).

Nu zetten we alle formules in de tabel en berekenen we de waarden:

$$\begin{array}{cccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))\\ 1& 1& 1& 1& 1& 0\\ 1& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 1\\ 1& 0& 0& 0& 1& 0\\ 0& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0\end{array}$$

De vraag was of alle drie de jongens naar het feest kunnen gaan. Het antwoord vinden we in de eerste rij. Die komt overeen met het geval waarin alle jongens gaan, wat te zien is aan de drie enen in de eerste drie kolommen. Zijn alle voorwaarden vervuld? De eerste wel (vierde kolom), de tweede ook (vijfde kolom), maar de laatste niet (laatste kolom), daar staat een nul. Dat betekent dat als ze alle drie gaan, de derde voorwaarde niet is vervuld.

We zoeken dus de rijen waarin op de plaatsen die de voorwaarden voorstellen (dat zijn de laatste drie kolommen) alleen enen staan. Een één betekent dat de voorwaarde is vervuld. We zien dat dit in twee gevallen gebeurt: als Jesse en Pim gaan maar Mees niet, en als alleen Pim gaat.

Je kunt het ook berekenen door aan de tabel een formule ϕ toe te voegen die de conjunctie van alle drie de voorwaarden is. Die ziet er zo uit: ϕ = ((M ⇒ J) ∧ (P ∨ (M ⇒ ¬J)) ∧ (P ⇔ (¬M ∨ ¬J))). Dit stelt voor wat we willen: dat alle formules (alle voorwaarden) zijn vervuld. De tabel ziet er dan zo uit:

$$\begin{array}{ccccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))& \varphi \\ 1& 1& 1& 1& 1& 0& 0\\ 1& 1& 0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1& 1& 0\\ 1& 0& 0& 0& 1& 0& 0\\ 0& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$

Nog een paar voorbeelden van de waarheidstabel

Omdat ik een programma heb geschreven dat uit een gegeven formule automatisch de hele tabel kan opbouwen, moet ik het ook goed gebruiken, en daarom volgen hier nog een paar uitgewerkte formules:

Formule: ((a ∧ ¬b) ∨ (b ∧ (b ⇒ a))). Tabel:

$$\begin{array}{ccccc}a& b& (a\wedge \mathrm{\neg }b)& (b\wedge (b\Rightarrow a))& ((a\wedge \mathrm{\neg }b)\vee (b\wedge (b\Rightarrow a)))\\ 1& 1& 0& 1& 1\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}$$

Formule: (a ∨ ¬a) ⇔ (b ∧ ¬b). Tabel:

$$\begin{array}{ccccc}a& b& (a\vee \mathrm{\neg }a)& (b\wedge \mathrm{\neg }b)& ((a\vee \mathrm{\neg }a)\iff (b\wedge \mathrm{\neg }b))\\ 1& 1& 1& 0& 0\\ 1& 0& 1& 0& 0\\ 0& 1& 1& 0& 0\\ 0& 0& 1& 0& 0\end{array}$$

Formule: ¬(a ∨ b) ⇔ (¬b ∧ ¬a). Tabel:

$$\begin{array}{ccccc}a& b& \mathrm{\neg }(a\vee b)& (\mathrm{\neg }b\wedge \mathrm{\neg }a)& (\mathrm{\neg }(a\vee b)\iff (\mathrm{\neg }b\wedge \mathrm{\neg }a))\\ 1& 1& 0& 0& 1\\ 1& 0& 0& 0& 1\\ 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 1\end{array}$$

Formule: ϕ = (¬p ⇔ (q ∧ r)) ⇒ (p ∨ ¬(p ∧ q)). Tabel:

$$\begin{array}{cccccccc}p& q& r& (q\wedge r)& \mathrm{\neg }(p\wedge q)& (\mathrm{\neg }p\iff (q\wedge r))& (p\vee \mathrm{\neg }(p\wedge q))& \varphi \\ 1& 1& 1& 1& 0& 0& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 0& 1& 0& 1& 1& 1& 1\\ 1& 0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 0& 1& 0& 1& 1\\ 0& 0& 1& 0& 1& 0& 1& 1\\ 0& 0& 0& 0& 1& 0& 1& 1\end{array}$$

Formule: ϕ = ¬(p ⇔ ¬q) ∧ (r ⇒ ¬p) ∧ (p ∨ r). Tabel:

$$\begin{array}{ccccccc}p& q& r& \mathrm{\neg }(p\iff \mathrm{\neg }q)& (r\Rightarrow \mathrm{\neg }p)& (p\vee r)& \varphi \\ 1& 1& 1& 1& 0& 1& 0\\ 1& 1& 0& 1& 1& 1& 1\\ 1& 0& 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1& 1& 0\\ 0& 1& 1& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$