Semantische Folgerung und Äquivalenz

Was aus der vorigen Lektion verwendet wird

Die Lektion über die Semantik der Aussagenlogik hat den Formeln eine Bedeutung gegeben, und diese Lektion setzt sie als bekannt voraus. Eine Belegung ist eine Funktion $v\colon V \to \{0, 1\}$, die jeder Variablen einen Wahrheitswert zuordnet, $1$ (wahr) oder $0$ (falsch). Nach dem Satz über die Definition durch Rekursion über Formeln aus der Lektion über die Induktion setzt sich jede Belegung auf eindeutige Weise auf alle Formeln fort, und zwar durch die Klausel des Peirce-Pfeils, die einzige, die nötig ist, weil die Sprache nur einen Junktor hat:

Wegen der Eindeutigkeit der Fortsetzung schreibt man $v(\varphi)$ auch für den Wert der Fortsetzung; der Buchstabe $v$ ohne Index bezeichnet stets eine Belegung (und $v'$, $w$, $u$ weitere), während die Variablen stets ihren Index tragen. Wie in der Lektion über die Formalisierung benennen $p$, $q$, $r$, $s$ und $t$ die Variablen $v_1$ bis $v_5$, und $V(\varphi)$ ist die Menge der Variablen von $\varphi$. Man sagt, dass $v$ die Formel $\varphi$ erfüllt, und schreibt $v \models \varphi$, wenn $v(\varphi) = 1$, und dass sie sie widerlegt, $v \not\models \varphi$, wenn $v(\varphi) = 0$. Eine Formel ist allgemeingültig (oder eine Tautologie), und man schreibt $\models \varphi$, wenn jede Belegung sie erfüllt; erfüllbar, wenn irgendeine sie erfüllt; unerfüllbar (oder eine Kontradiktion), wenn keine sie erfüllt; kontingent, wenn sie erfüllbar ist, ohne allgemeingültig zu sein. Eine Belegung erfüllt eine Menge $\Gamma$ von Formeln, $v \models \Gamma$, wenn sie jede von ihnen erfüllt, und $\Gamma$ ist erfüllbar, wenn irgendeine Belegung sie erfüllt, und andernfalls unerfüllbar. Schließlich setzt man $\top := (v_1 \rightarrow v_1)$ und $\bot := \neg\top$, sodass $v(\top) = 1$ und $v(\bot) = 0$ für jede Belegung.

Aus jener Lektion werden außerdem zwei Ergebnisse verwendet. Das erste ist das Koinzidenzlemma: Wenn zwei Belegungen auf den Variablen von $\varphi$ übereinstimmen, stimmen sie auf $\varphi$ überein; danach hängt der Wert einer Formel mit $n$ Variablen nur von $2^{n}$ Kombinationen ab, und ihre Wahrheitstafel ist endlich. Das zweite ist der Satz über die Werte der abgeleiteten Junktoren, der aus den offiziellen Abkürzungen den Wert jedes Junktors als Polynom in den Werten der Komponenten berechnet. Wenn $a = v(\varphi)$ und $b = v(\psi)$:

Die Beweise dieser Lektion bestehen fast alle darin, Wahrheitswerte zu vergleichen, und diese Polynome erlauben es, dies durch eine Rechnung statt durch ein Durchgehen von Fällen zu tun. Ihre einzige zusätzliche Regel ist, dass $0$ und $1$ die einzigen Zahlen sind, die mit ihrem Quadrat übereinstimmen: Wenn $x$ den Wert $0$ oder $1$ hat, dann $x^{2} = x$ und $x(1 - x) = 0$. Es empfiehlt sich außerdem, drei weitere Schreibweisen derselben Werte zur Hand zu haben, die man durch Ausmultiplizieren der Produkte erhält:

Die erste ist die Klausel des Peirce-Pfeils (das Produkt von $1 - a$ und $1 - b$ ist genau dann $1$, wenn $a = b = 0$); die zweite besagt, dass die Disjunktion nur dann $0$ ist, wenn beide Komponenten $0$ sind; die dritte, dass das Bikonditional $1$ ist, wenn $a = b$ (weil $1 - 2a + 2a^{2} = 1$), und $0$, wenn $a \neq b$ (weil dann $a + b = 1$ und $ab = 0$).