Als je de uitwerkingen van de puzzels uit de vorige theoriepagina bekeken hebt, dan heb je gezien dat het opstellen van een waarheidstabel voor de in de gevolgtrekking voorkomende formules handig is. Het geheim hierachter is dat je een exclusief model voor de formuleverzameling van de puzzel hierin kunt aflezen. Deze theoriepagina gaat.
We kijken eerst terug naar het begrip waardering, ook wel valuatie genoemd. Een waardering is per definitie een functie die aan alle propositievariabelen een waarheidswaarden (\(0\) als de propositie onwaar is, \(1\) voor een ware propositie). Aan een (welgevormde) logische formule kun je dan volgens spelregels ook een waarheidswaarde toekennen. In onderstaande tabel hebben we het functieaspect van een waardering benadrukt door de spelregels als functievoorschriften te noteren, zodat een waardering van een formule neerkomt op een samenstelling van wiskundige functies.
Stel dat \(x\) en \(y\) de waarde \(0\) of \(1\) aan kan nemen (zoals bij een waardering van propositievariabelen), dan gelden de volgende spelregels bij gebruik van de logische connectieven: \[\begin{aligned} f_{\neg}(x)&=1-x\\[0.2cm] f_{\land}(x,y) &= \min(x,y)\\[0.2cm] f_{\lor}(x,y) &= \max(x,y)\\[0.2cm] f_{\rightarrow}(x,y) &= \max(1-x,y)\\[0.2cm] f_{\leftrightarrow}(x,y) &= \begin{cases} 1 & \text{als } x=y\\ 0 & \text{anders}\end{cases}\end{aligned}\]
Stel dat \(p\), \(q\) en \(r\) propositievariabelen ziin met waarderingen \(w(p)=0\), \(w(q)=1\), en \(w(r)=0\). We bekijken de formule \(\varphi=p\lor (q\rightarrow r)\). Dan de waardering \(w(\varphi)\) als volgt in stapje uit te rekenen: \[\begin{aligned} w(\varphi) &= w\bigl(p\lor (q\rightarrow r)\bigr)\\[0.2cm] &= f_{\lor}\bigl(w(p), w(q\rightarrow r)\bigr)\\[0.2cm] &= f_{\lor}\Bigl(0, f_{\rightarrow}(w(q),w(r)\bigr)\Bigr) \\[0.2cm] &= f_{\lor}\bigl(0, f_{\rightarrow}(1,0)\bigr) \\[0.2cm] &= f_{\lor}(0, 0) \\[0.2cm] &= 0\end{aligned}\]
Als \(v\) en \(w\) waardering zijn zodanig dat \(v(p)=w(p)\) voor elke propositievariabele \(p\) die in een logische formule \(\varphi\) voorkomt, dan geldt dat \(v(\varphi)=w(\varphi)\).
In het vervolg van deze theoriepagina gaan we belangrijke begrippen als model, tautologie, geldig gevolg en consistentie definiëren.
Een waardering \(w\) heet een model van een logische formule \(\varphi\) als geldt: \(w(\varphi)=1\). Een waardering heet een model van een formuleverzameling \(\Sigma\) als zij model is van elke formule \(\varphi\in\Sigma\). De verzameling modellen van een formuleverzameling \(\Sigma\) noteren we als \(\mathrm{MOD}(\Sigma)\). Een formuleverzameling \(\Sigma\) heet vervulbaar als de verzameling modellen van \(\Sigma\) niet leeg is, d.w.z. als er een waardering \(w\) bestaat die model is van \(\Sigma\); we zeggen dan ook wel dat \(\Sigma\) vervuld wordt door \(w\). Een formuleverzameling \(\Sigma\) heet strijdig als er geen model van \(\Sigma\) bestaat.
Als we een formuleverzameling \(\Sigma\) uitbreiden met een formule \(\varphi\), dan wordt de verzameling modellen een deelverzameling van de oorspronkelijke verzameling van bijpassende modellen. Elk model van de nieuwe formuleverzameling is een model van de oorspronkelijke formuleverzameling, maar het omgekeerde hoeft niet waar te zijn. In formuletaal: \(\mathrm{MOD}\bigl(\Sigma\cup \{\varphi\}\bigr)\subseteq \mathrm{MOD}\bigl(\Sigma\bigr)\).
In eerdere voorbeelden van logische puzzels hebben we al gezien dat elke nieuwe formule in een probleem extra informatie verschaft over de situatie. Dit betekent dat we bij uitbreiding van een formuleverzameling in het algemeen een kleinere verzameling modellen krijgen en idealiter eindigen met maar één model dat oplossing van het probleem is.
Laten we de puzzel van het feestje ter illustratie gebruiken. Er waren drie uitspraken en we geven ze maar gelijk namen:
\(u_1\): "Bob komt naar het feestje als Anna of Claudia naar het feestje komt."
\(u_2\):"Anna komt naar het feestje als Claudia niet naar het feestje komt."
\(u_3\): "Als Anna naar het feestje komt, dan komt Bob niet naar het feestje."
De gestelde vraag komt nu neer op: heeft de formuleverzameling \(\{u_1, u_2,u_3\}\) een uniek model?
We gebruiken de letters \(a\), \(b\) en \(c\) respectievelijk voor de proposities "Anna komt naar het feestje.", "Bob komt naar het feestje.", en "Claudia komt naar het feestje." We bepalen eerst alle modellen van \(\{u_1\}\), daarna van \(\{u_1,u_2\}\), en tenslotte van \(\{u_1,u_2,u_3\}\). De resultaten staan in onderstaande tabel.
| waarderingen |
model van |
| \(a\) |
\(b\) |
\(c\) |
\(\{u_1\}\) |
\(\{u_1,u_2\}\) |
\(\{u_1,u_2,u_3\}\) |
| 0 |
0 |
0 |
ja |
nee |
- |
| 0 |
0 |
1 |
nee |
- |
- |
| 0 |
1 |
0 |
ja |
nee |
- |
| 0 |
1 |
1 |
ja |
ja |
ja |
| 1 |
0 |
0 |
nee |
- |
- |
| 1 |
0 |
1 |
nee |
- |
- |
| 1 |
1 |
0 |
ja |
ja |
nee |
| 1 |
1 |
1 |
ja |
ja |
nee |
Het enige model dat overblijft van de drie uitspraken is de waardering met \(w(a)=0\), \(w(b)=1\) en \(w(c)=1\). Bob en Claudio komen naar het feestje.
De definitie van het begrip "geldig gevolg" stemt overeen met de eerdere intuïtieve beschrijving van een logisch geldige gevolgtrekking \(\psi\) op basis van één of meer premissen \(\varphi_1, \ldots, \varphi_n\). Zo'n redenering is correct, oftewel logisch geldig, dan en slechts dan als de conclusie \(\psi\) een geldig gevolg is van \(\Sigma=\{\varphi_1, \ldots, \varphi_n\}\). Dus ieder model van \(\Sigma\) is tevens een model van de conclusie \(\psi\). Als een redenering niet correct is, dan moet er een waardering \(w\) bestaan zodanig dat \(w(\varphi_1)= \ldots = w(\varphi_n)=1\), maar \(w(\psi)=0\).
Een logische formule \(\varphi\) heet een tautologie als elke waardering een model is van \(\varphi\) oftewel als voor elke waardering \(w\) geldt: \(w(\varphi)=1\).
Elke formule van de vorm \(\varphi\lor \neg\,\varphi\) is een tautologie. Ook is elke formule van de vorm \(\neg(\varphi\land \neg\,\varphi)\) is een tautologie. Dit zie je aan onderstaande waarheidstabellen \[\begin{array}{c|cccc} \varphi & \neg\,\varphi & \varphi\lor \neg\,\varphi & \varphi\land \neg\,\varphi & \neg(\varphi\land \neg\,\varphi) \\ \hline 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1\end{array}\]
Een logische formule \(\varphi\) heet een contradictie als geen enkele waardering een model is van \(\varphi\) oftewel als voor elke waardering \(w\) geldt: \(w(\varphi)=0\). De formule \(\varphi\) is een contradictie dan en slechts dan als \(\neg\,\phi\) een tautologie is. We noemen een logische formule \(\varphi\) contingent als minstens één waardering bestaat die een model is van \(\varphi\). Elke formuleverzameling kan opgedeeld worden in contradicties, contingente formules en tautologieën.
Elke formule van de vorm \(\varphi\land \neg\,\varphi\) is een contractie. Ook is elke formule van de vorm \((\varphi\rightarrow\psi)\leftrightarrow \varphi\land\neg\,\psi\) is een contradictie. Dit zie je aan onderstaande waarheidstabel \[\begin{array}{cc|ccc} \varphi & \psi & \varphi\rightarrow \psi & \varphi\land\neg\,\psi & (\varphi\rightarrow\psi)\leftrightarrow \varphi\land\neg\,\psi\\ \hline 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0\\ 1 & 0 & 0 & 1 & 0\\ 1 & 1 & 1 & 0 & 0 \end{array}\] De formule \(\varphi\lor \psi\) is een contingente formule want kies maar de waardering \(w(\varphi)=w(\psi)=1\).
Twee formules \(\varphi\) en \(\psi\) heten logisch equivalent, ook wel logisch gelijkwaardig, als de formule \(\varphi\leftrightarrow \psi\) een tautologie is. Anders gezegd voor elke waardering \(w\) geldt: \(w(\varphi)=w(\psi)\), oftewel \(\varphi\vDash \psi\) en \(\psi\vDash \varphi\).
De formules \(\varphi\) en \(\neg\,\neg\,\varphi\) zijn equivalent, oftewel \(\neg\,\neg\,\varphi\leftrightarrow \varphi\) is een tautologie. Dit volgt uit onderstaande waarheidstabel. \[\begin{array}{c|cc} \varphi & \neg\,\varphi & \varphi\leftrightarrow \neg\,\neg\,\varphi \\ \hline 0 & 0 & 1 \\ 1 & 1 & 1 \end{array}\] Voor de formules \(\varphi\) en \(\psi\) zijn de formules \(\neg(\varphi\land\psi)\) en \(\neg\,\varphi \lor \neg\,\psi\) equivalent. Dit volgt uit onderstaande waarheidstabel. \[\begin{array}{cc|cccccc} \varphi & \psi & \neg\,\varphi & \neg\psi & \varphi\land\psi & \neg(\varphi\land\psi) & \neg\,\varphi \lor \neg\,\psi & \neg(\varphi\land\psi) \leftrightarrow (\neg\,\varphi \lor \neg\,\psi) \\ \hline 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1\end{array}\] Dat de formule \(\neg(\varphi\rightarrow \psi)\leftrightarrow \varphi\land \neg\,\psi\) een tautologie is kan ook via een waarheidstabel worden aangetoond, maar handiger is misschien wel de volgende soort van berekening in metataal, met \(\iff\) als symbool voor "dan en slechts dan als" en \(\&\) symbool voor het voegwoord "en"): \[\begin{aligned} w\bigl(\neg(\varphi\rightarrow \psi)\bigr) &\iff w(\varphi\rightarrow \psi)=0\\[0.2cm] &\iff w(\varphi)=1\;\&\; w(\psi)=0\\[0.2cm] &\iff w(\varphi)=1\;\&\; w(\neg\,\psi)=1\\[0.2cm] &\iff w(\varphi\land \neg\,\psi)=1\end{aligned}\]
Het zit al in de naam "logische equivalentie" opgenomen, maar inderdaad is aan de drie kenmerken van een equivalentierelatie voldaan:
- (reflexiviteit) Elke formule \(\varphi\) is logisch equivalent met zichzelf (\(\vDash \varphi\leftrightarrow \varphi\)).
- (symmetrie) Als de formule \(\varphi\) logisch equivalent is met de formule \(\psi\), dan geldt ook dat \(\psi\) logisch equivalent is met de formule \(\varphi\) (in metataal: \(\vDash\varphi\leftrightarrow \psi\iff \vDash\psi\leftrightarrow\varphi\)).
- (transitiviteit) Als de formule \(\varphi\) logisch equivalent is met de formule \(\psi\) en \(\psi\) \(\varphi\) logisch equivalent is met de formule \(\chi\), dan is \(\varphi\) logisch equivalent met \(\chi\) (in metataal m.b.v. \(\implies\) als implicatiepijl: \(\vDash\varphi\leftrightarrow \psi\;\&\; \vDash\psi\leftrightarrow \chi \implies\vDash\varphi\leftrightarrow\chi\)).
Een formule \(\psi\) heet een geldig gevolg van een formuleverzameling \(\Sigma\) als elk model van \(\Sigma\) ook een model is van \(\psi\). Dit wordt genoteerd als \(\Sigma\vDash \psi\). Anders gezegd, de redenering dat het waar zijn van de formule \(\psi\) volgt uit formuleverzameling \(\Sigma\) is valide.
Als \(\Sigma=\{\varphi_1,\ldots, \varphi_n\}\), dan noteren we \(\Sigma\vDash \psi\) ook wel als \(\varphi_1,\ldots, \varphi_n\vDash \psi\) en zeggen we dat \(\psi\) logisch volgt uit de premissen \(\varphi_1,\ldots, \varphi_n\).
Voor de propositie \(p\), \(q\) en \(r\) geldt: \[\begin{aligned}p, p\rightarrow q&\vDash q\\[0.2cm] p, p\rightarrow q, q\rightarrow r&\vDash r\end{aligned}\]
Voor een lege formuleverzameling, d.w.z. \(\Sigma=\{\}\), dan betekent \(\{\}\vDash \psi\), afgekort tot \(\vDash \psi\), dat elke waardering een model van \(\Sigma\) is, oftewel: \(\psi\) is een tautologie.
Als de formule \(\psi\) geen geldig gevolg van de formuleverzameling \(\Sigma\) is, d.w.z. er bestaat een model van \(\Sigma\) dat geen model is van \(\psi\), dan noteren we dit als \(\Sigma\nvDash \psi\).
Bijvoorbeeld, voor proposities \(p\) en \(q\) hebben we \(q,p\rightarrow q \nvDash p\) omdat uit de waardering \(w(p)=0, w(q)=1\) via de waarheidstabel van de connectef \(\rightarrow\) volgt dat \(w( p\rightarrow q)\). Deze waardering maakt \(q\) en \(p\rightarrow q\) waar, maar \(p\) is onwaar. Dus is de waardering \(w\) een model van \(\{q,p\rightarrow q\}\), maar niet van \(p\). Deze waardering wordt een tegenvoorbeeld genoemd.
Omdat dit voorbeeld concreter te maken laten we \(p\) en \(q\) de uitspraken "De computercode is correct." en "Het programma termineert." Uit de premissen "Als de computercode correct is dan termineert het programma" en "De computercode is correct." volgt inderdaad dat het programma termineert. Maar een terminerend programma betekent nog niet dat de computercode correct is. Dat is geen geldig gevolg van de premissen..
Over geldige gevolgtrekkingen kun je in metataal (hier met het "als dan" symbool \(\implies\), een "dan en slecht dan" symbool \(\iff\) en een voegwoord "en" gesymboliseerd door \(\&\)) ook uitspraken doen. De volgende (meta-)stellingen zijn enkele voorbeelden.
Voor formules \(\phi\) en \(\psi\) geldt: \[\vDash \varphi\; \&\vDash \psi\implies \vDash \varphi\land \psi\]
Voor formules \(\phi\) en \(\psi\) geldt: \[\varphi \vDash \psi \implies \vDash \varphi\rightarrow \psi\]
Voor formules \(\varphi_1\), \(\varphi_2\) en \(\psi\) geldt: \[\begin{aligned} \varphi_1, \varphi_2\vDash \psi &\iff \varphi_1\vDash \varphi_2\rightarrow \psi\\[0.2cm] &\iff \vDash (\varphi_1\land \varphi_2)\rightarrow \psi\end{aligned}\]
Een formuleverzameling \(\Sigma\) heet (semantisch) consistent als er een model van \(\Sigma\) bestaat. Als er geen model van de formuleverzameling \(\Sigma\) bestaat dan heet \(\Sigma\) (semantisch) inconsistent. Dit laatste is vaak ongewenst, omdat afwezigheid van modellen betekent dat uit deze verzameling dan iedere formule geldig volgt, en daarmee ook de negatie ervan.
Stel dat \(p\) en \(q\) propositievariabelen zijn. Dan is \(\Sigma=\{p\rightarrow q, \neg\, p,q\}\) een vervulbare verzameling. Immers de waardering \(w(p)=0\) en \(w(q)=1\) is een model van \(\Sigma\).
De formuleverzameling \(\Sigma=\{p\rightarrow q, \neg\, p, q\}\) is daarentegen een onvervulbare verzameling. Immers, om een waardering \(w\) een model van \(\Sigma\) te laten wezen, moet gelden dat \(w(p)=0\) en \(w(q)=1\). Maar dan is \(w(p\rightarrow q)=0\).
Een formuleverzameling is (semantisch) consistent dan en slecht dan als de verzameling vervulbaar is. De begrippen consistentie en vervulbaarheid zijn dus sterk verwant. Bij het eerste begrip, consistentie, gaat het er om dat de formuleverzameling niet leidt naar een tegenspraak; het is dus gerelateerd aan bewijstheorie. Het tweede begrip, vervulbaarheid, gaat meer over het bestaan van een waardering waarvoor alle formules in de gegeven formuleverzameling de waarheidswaarde \(1\) hebben. Het gaat dus meer om het vinden van een geschikte waardering dan om het uitsluiten van een tegenspraak.
Modellen en geldig gevolg
