Waarheidstabellen

Logica: Propositielogica

Waarheidstabellen

$\newcommand{\propcol}[1]{\blue{#1}}\newcommand{\compcol}[1]{\green{#1}}$ We hebben de logische operatoren en, of, niet, implicatie (als ... dan) en bi-implicatie (enkel en alleen als) gezien. We hebben ook gezien dat we met behulp van deze operatoren samengestelde proposities construeren, welke ook als waar of onwaar geëvalueerd kunnen worden. Het is echter best lastig om te zien wanneer een complexe samengestelde propositie zoals $(\neg\propcol p\rightarrow\propcol q)\land(\propcol p \lor\propcol r) \leftrightarrow(\propcol q\rightarrow \neg \propcol r)$ waar is. Om dat te kunnen doen, introduceren we waarheidstabellen. Eerst kijken we naar een voorbeeld.

Beschouw de volgende propositie "Ik heb een fiets en een auto.". Deze propositie is precies waar als de proposities "Ik heb een fiets." en "Ik heb een auto." beide waar zijn. In propositieletters kunnen we schrijven $\begin{array}{ccl}\propcol p&=&\text{ "Ik heb een fiets."}\\ \propcol q&=&\text{ "Ik heb een auto."}\\ \propcol p \land\propcol q&=&\text{ "Ik heb een fiets}\textit{ en }\text{ik heb een auto."}\end{array}$

Waarheidstabel

$\propcol p$	$\propcol q$	$\propcol p \land\propcol q$
waar	waar	waar
waar	onwaar	onwaar
onwaar	waar	onwaar
onwaar	onwaar	onwaar

De eerste twee kolommen komen overeen met de proposities $\propcol p$ en $\propcol q$ . De laatste kolom komt overeen met de samengestelde propositie $\compcol\Phi(\propcol p, \propcol q)$ . In de kolommen sommen we de waardes op van deze proposities in de verschillende gevallen.

De rijen bevatten alle mogelijke combinaties van de waardes die $\propcol p$ en $\propcol q$ kunnen aannemen. Zowel $\propcol p$ als $\propcol q$ kan waar of onwaar zijn. Daarom zijn er vier gevallen, wat leidt tot vier rijen (de rij met de koptekst niet meegerekend). De gevallen zijn lexicografisch opgesomd, waarbij waar voor onwaar komt.

Bijvoorbeeld, de invoer in de kolom behorende bij $\compcol\Phi$ en in de rij met de waardes onwaar voor $\propcol{p}$ en waar voor $\propcol{q}$ geeft de waarde van $\propcol p \land\propcol q$ aan voor deze situatie, dat is onwaar.

Eén variabele

De waarheidstabel voor één enkele propositie $\propcol p$
ziet er als volgt uit

$\propcol p$	$\propcol p$
waar	waar
onwaar	onwaar

De waarheidstabel voor de propositie $\neg \propcol{p}$
ziet er als volgt uit

$\propcol p$	$\neg \propcol p$
waar	onwaar
onwaar	waar

Er zijn exact twee mogelijkheden voor de waarde van $\propcol p$ (waar of onwaar). Voor elk van deze twee mogelijkheden zijn er twee mogelijke waardes voor de samengestelde uitdrukking met enkel $\propcol p$ . Daarom zijn er precies $2\cdot 2 = 4$ essentieel verschillende (wat heet, inequivalente) proposities met alleen $\propcol p$ . Hierboven hebben we er twee gezien.

De andere twee zijn simpelweg de proposities waar (welke altijd waar is) en onwaar (welke altijd onwaar is). Dit kan ook opgeschreven worden op een meer complexe manier, zodat het lijkt alsof ze argumenten hebben met $\propcol p$ ; bijvoorbeeld $\propcol p\lor \neg\propcol p$ voor waar en $\propcol p\land \neg\propcol p$ voor onwaar.

Hier staat het algemene geval.

Waarheidstabel

Laat $\compcol\Phi=\compcol{\Phi}\left(\propcol{p_1},\propcol{ p_2},\ldots,\propcol{p_n}\right)$ een samengestelde propositie zijn afhankelijk van $n$ variabelen $\propcol{p_1},\propcol{ p_2},\ldots,\propcol{p_n}$ .

De waarheidstabel voor $\compcol{\Phi}$ is de tabel met $n+1$ kolommen, één voor elk van de afhankelijke variabelen $\propcol{p_1},\propcol{ p_2},\ldots,\propcol{p_n}$ en een kolom voor $\compcol{\Phi}$ met daarin, voor elk van de waardes van de $\propcol{\text{variabelen}}$ , de waarde van de $\compcol{\text{samengestelde propositie}}$ .

Voor het gemak mag je direct na de eerste $n$ kolommen nog hulpkolommen toevoegen met proposities die voorkomen in $\compcol{\Phi}$ .

De invoer van een waarheidstabel zijn alle mogelijke combinaties van de waardes waar of onwaar voor de afhankelijke variabelen $\propcol{p_1},\propcol{ p_2},\ldots,\propcol{p_n}$ . Elke rij bevat één specifieke combinatie. De uitvoer zijn de bijbehorende waardes van de proposities in de hulpkolommen en in de kolom van $\compcol{\Phi}$ .

Voorbeeld

De waarheidstabel voor $\compcol{\Phi}=(\propcol p\lor \propcol q)\lor (\propcol p \land \propcol q)$ is

$\propcol p$	$\propcol q$	$\propcol p\lor \propcol q$	$\propcol p\land \propcol q$	$\compcol{\Phi}$
waar	waar	waar	waar	waar
waar	onwaar	waar	onwaar	waar
onwaar	waar	waar	onwaar	waar
onwaar	onwaar	onwaar	onwaar	onwaar

De hulpkolommen zijn die kolommen met $\propcol p\lor\propcol q$ en $\propcol p\land\propcol q$ bovenaan.
Inspectie van de tabel laat zien dat $\compcol{\Phi}$ onwaar is precies wanneer $\propcol p$ en $\propcol q$ beiden onwaar zijn.

Het is gebruikelijk om de rijen in een vaste volgorde te tonen. Meestal wordt de lexicografische volgorde aangehouden waarbij waar voor onwaar komt. In de eerste rij hebben alle variabelen $\propcol{p_1}, \propcol{p_2},\ldots,\propcol{p_n}$ de waarde waar. In de laatste rij hebben alle variabelen de waarde onwaar. Als $n\gt 1$ , dan begint de tweede rij met $n-1$ maal een invoer waar en de $n$ -de invoer onwaar, en zo verder.

De propositie $\neg\propcol p$ is waar precies wanneer $\propcol p$ onwaar is. Een voorbeeld van een negatie, in woorden, is

$\begin{array}{ccl}\propcol{p}&=&\text{ "Het regent."}\\ \neg \propcol p&=&\text{ "Het regent}\textit{ niet}\text{."}\end{array}$

$\propcol p$	$\neg\propcol p$
waar	onwaar
onwaar	waar

Conjunctie

De propositie $\propcol p \land\propcol q$ is waar precies wanneer $\propcol p$ en $\propcol q$ allebei waar zijn. Een voorbeeld van een conjunctie, in woorden, is

$\begin{array}{ccl}\propcol p&=&\text{ "Het regent."}\\ \propcol q&=&\text{ "Ik draag een regenjas."}\\ \propcol p \land\propcol q&=&\text{ "Het regent}\textit{ en }\text{ik draag een regenjas."}\end{array}$

$\propcol p$	$\propcol q$	$\propcol p \land\propcol q$
waar	waar	waar
waar	onwaar	onwaar
onwaar	waar	onwaar
onwaar	onwaar	onwaar

Disjunctie

De propositie $\propcol p\lor\propcol q$ is waar als $\propcol p$ waar is, als $\propcol q$ waar is, of als $\propcol p$ en $\propcol q$ beide waar zijn. Een voorbeeld van een disjunctie, in woorden, is

$\begin{array}{ccl}\propcol p&=&\text{ "Het regent."}\\ \propcol q&=&\text{ "Het sneeuwt."}\\ \propcol p \lor\propcol q&=&\text{ "Het regent}\textit{ of }\text{het sneeuwt."}\end{array}$

$\propcol p$	$\propcol q$	$\propcol p \lor\propcol q$
waar	waar	waar
waar	onwaar	waar
onwaar	waar	waar
onwaar	onwaar	onwaar

Implicatie

De propositie $\propcol p\rightarrow\propcol q$ is waar wanneer $\propcol p$ impliceert $\propcol q$ Dit is waar als zowel $\propcol{p}$ en $\propcol{q}$ waar zijn, en wanneer $\propcol{p}$ onwaar is. Een voorbeeld van een implicatie, in woorden, is

$\begin{array}{ccl}\propcol{p}&=&\text{ "Het regent."} \\ \propcol{q}&=&\text{ "De grond wordt nat."} \\ \propcol p\rightarrow \propcol q&=&\textit{ "Als }\text{het regent, }\textit{dan}\text{ wordt de grond nat."} \end{array}$

$\propcol{p}$	$\propcol{q}$	$\propcol{p} \rightarrow \propcol{q}$
waar	waar	waar
waar	onwaar	onwaar
onwaar	waar	waar
onwaar	onwaar	waar

Bi-implicatie

De propositie $\propcol{p}\leftrightarrow\propcol{q}$ is waar wanneer $\propcol{p}$ en $\propcol{q}$ beide dezelfde waarde hebben. Een voorbeeld van een bi-implicatie, in woorden, is

$\begin{array}{ccl}\propcol{p}&=&\text{ "De lucht is helder."}\\ \propcol{q}&=&\text{ "Er zijn geen wolken."}\\ \propcol{p} \leftrightarrow\propcol{q}&=&\text{ "De lucht is helder }\textit{als en alleen als}\\ && \quad \text{ er geen wolken zijn."}\end{array}$

$\propcol{p}$	$\propcol{q}$	$\propcol{p} \leftrightarrow \propcol{q}$
waar	waar	waar
waar	onwaar	onwaar
onwaar	waar	onwaar
onwaar	onwaar	waar

Hulpmiddel

De waarheidstabel is een hulpmiddel dat we gebruiken om proposities te evalueren. Het is belangrijk dat we weten hoe het te gebruiken. De waarheidstabel voor $\compcol{\Phi}(\propcol p,\propcol q,\propcol r)$ bepaalt het toekennen van de waardes waar of onwaar aan $\compcol{\Phi}$ voor elk van de acht gelijktijdige evaluaties van de variabelen $\propcol p$ , $\propcol q$ en $\propcol r$ . Elke rij van de tabel (de rij met koptekst telt niet mee) komt overeen met een unieke gelijktijdige evaluatie. Dus de waarheidstabel in het geval van drie variabelen heeft acht rijen.

Laat $n$ een natuurlijk getal zijn en beschouw de waarheidstabel van de samengestelde propositie $\compcol{\Phi}(\propcol{p_1},\ldots,\propcol{p_n})$ . We laten hulpkolommen buiten beschouwing.

Elk van de proposities $\propcol{p_1},\propcol{p_2},\ldots,\propcol{p_n}$ kan twee waardes aannemen, dus er zijn $2^n$ gelijktijdige evaluaties van de variabelen voorkomend in $\compcol{\Phi}$ . Elke rij van de waarheidstabel (de rij met koptekst telt niet mee) komt overeen met een unieke evaluatie, dus hebben we $2^n$ rijen. Elke rij kan gecompleteerd worden met de waarde van $\compcol{\Phi}$ in de laatste kolom, wat ons weer twee mogelijkheden geeft (waar of onwaar). Dit betekent dat er $2^{2^n}$ verschillende waarheidstabellen zijn in het geval van $n$ variabelen.

Hierboven hebben we inderdaad gezien dat voor $n=1$ , dit aantal $4$ is. Als $n=2$ , is het aantal $16$ . Voor $n=3$ , zijn er al $256$ verschillende tabellen.

Is de propositie $(p \land q) \lor p$ altijd waar?

Nee, de propositie $(p \land q) \lor p$ is niet altijd waar.

We gebruiken de volgende waarheidstabel om het antwoord te vinden.

$p$	$q$	$p\land q$	$(p \land q) \lor p$
waar	waar	waar	waar
waar	onwaar	waar	waar
onwaar	waar	waar	onwaar
onwaar	onwaar	onwaar	onwaar

We concluderen dat $(p \land q) \lor p$ niet geldt voor alle waarden van $p$ en $q$ , en daarom, is deze propositie niet altijd waar.

Nieuw voorbeeld