Verallgemeinerte De-Morgan- und Distributivgesetze

Gesetze für beliebig viele Glieder

Die Lektion über semantische Folgerung und Äquivalenz hat die Äquivalenzgesetze für zwei Glieder aufgestellt: unter ihnen die Kommutativität und die Assoziativität von $\wedge$ und von $\vee$, die De-Morgan-Gesetze und die beiden Distributivitäten. Nun ist eine Formel in disjunktiver Normalform eine Disjunktion von Konjunktionen mit jeweils so vielen Gliedern wie nötig, und eine Formel in diese Form zu bringen verlangt, Konjunktionen und Disjunktionen beliebiger Länge zu negieren, umzugruppieren und zu distribuieren. Wenn dem so ist, genügen die binären Gesetze in ihrer jetzigen Form nicht: Man muss sie auf $n$ Glieder ausdehnen, und zwar ein für alle Mal für alle $n$.

Für jedes feste $n$ könnte das De-Morgan-Gesetz mit $n$ Gliedern durch eine Wahrheitstafel mit $2^n$ Zeilen nachgeprüft werden, geschrieben mit $n$ Variablen, und die uniforme Substitution der vorigen Lektion, angewandt auf das Bikonditional zwischen beiden Seiten, würde es auf beliebige Formeln ausdehnen. Aber es gibt unendlich viele Werte von $n$, und keine Anzahl von Tafeln erschöpft sie. Daraus folgt, dass die Behauptung „für jedes $n$“ keine Äquivalenz zwischen zwei Formeln ist, sondern eine Aussage über unendlich viele Äquivalenzen, formuliert in der Metasprache; ihr Beweis ist, wie die Beweise der Lektion über die Induktion über die natürlichen Zahlen und über Formeln, ein externer Beweis, und ihr Werkzeug ist die Induktion über die Anzahl der Glieder. Auch die Notation $\bigwedge_{i=1}^{n} \varphi_i$ gehört zur Metasprache: Sie ist kein neues Zeichen der Sprache, sondern ein Name für eine Zeichenkette aus Kreisen und Scheiben, ebenso wie $(\varphi \wedge \psi)$ einer ist.

Es empfiehlt sich, von Anfang an drei Beziehungen festzuhalten, die nicht verwechselt werden dürfen. Die Gleichheit $\alpha = \beta$ besagt, dass $\alpha$ und $\beta$ dieselbe Zeichenkette sind; die Definitionen, die mit $:=$ geschrieben werden, führen Namen für Zeichenketten ein, und was man durch Auflösen einer Definition erhält, ist gleich, nicht bloß äquivalent. Die semantische Äquivalenz $\alpha \eqsem \beta$ besagt, dass $v(\alpha) = v(\beta)$ für jede Belegung $v$ gilt. Die beweisbare Äquivalenz $\alpha \dashv\vdash \beta$ der Einheit über die Deduktion besagt, dass jede der beiden aus der anderen ableitbar ist. Diese Lektion arbeitet mit den ersten beiden; die dritte erscheint nur in einer Bemerkung.

Was verwendet wird

Aus der Lektion über die Semantik der Aussagenlogik übernimmt man die Belegungen, Funktionen von den Variablen $v_1, v_2, \ldots$ nach $\{0, 1\}$, und ihre Fortsetzung auf alle Formeln, die mit demselben Buchstaben $v$ geschrieben wird; den Wert der abgeleiteten Junktoren, berechnet aus den offiziellen Abkürzungen: $v(\neg\varphi) = 1 - v(\varphi)$, $v((\varphi \wedge \psi)) = v(\varphi)\,v(\psi)$, so dass die Konjunktion genau dann den Wert $1$ hat, wenn ihre beiden Komponenten den Wert $1$ haben, und $v((\varphi \vee \psi)) = 1$ genau dann, wenn $v(\varphi) = 1$ oder $v(\psi) = 1$; das Koinzidenzlemma (stimmen zwei Belegungen auf den Variablen einer Formel überein, so stimmen sie auf der Formel überein); und die Formeln $\top$ und $\bot$, eine feste Tautologie und eine feste Kontradiktion. Aus der Lektion über semantische Folgerung und Äquivalenz übernimmt man, dass $\eqsem$ reflexiv, symmetrisch und transitiv ist, den semantischen Ersetzungssatz und den Katalog der Gesetze mit ihren Namen: Kommutativität, $(\varphi \wedge \psi) \eqsem (\psi \wedge \varphi)$ und $(\varphi \vee \psi) \eqsem (\psi \vee \varphi)$; Assoziativität, $(\varphi \wedge (\psi \wedge \chi)) \eqsem ((\varphi \wedge \psi) \wedge \chi)$ und ihr Gegenstück für $\vee$; De Morgan, $\neg(\varphi \wedge \psi) \eqsem (\neg\varphi \vee \neg\psi)$ und $\neg(\varphi \vee \psi) \eqsem (\neg\varphi \wedge \neg\psi)$; Distributivität, $(\varphi \wedge (\psi \vee \chi)) \eqsem ((\varphi \wedge \psi) \vee (\varphi \wedge \chi))$ und $(\varphi \vee (\psi \wedge \chi)) \eqsem ((\varphi \vee \psi) \wedge (\varphi \vee \chi))$; doppelte Negation, $\neg\neg\varphi \eqsem \varphi$; Idempotenz, $(\varphi \vee \varphi) \eqsem \varphi$; Identität, $(\varphi \wedge \top) \eqsem \varphi$; und Tertium non datur, $\models (\varphi \vee \neg\varphi)$. Die Gesetze gelten für beliebige Formeln $\varphi$, $\psi$, $\chi$, die Metavariablen sind.

In jedem Schritt der folgenden Beweise wird ein Teil einer Formel durch einen äquivalenten ersetzt. Der semantische Ersetzungssatz erlaubt das für jeweils ein Vorkommen; das folgende Lemma, ein Spezialfall davon, liefert es auf einmal für die Teile einer Negation, einer Konjunktion oder einer Disjunktion. Es ist zu beachten, dass dies keine syntaktische Trivialität ist: $\neg\alpha$ ist die Zeichenkette $(\alpha \downarrow \alpha)$, in der $\alpha$ zweimal vorkommt, und $(\alpha \wedge \beta)$ enthält daher acht Vorkommen von $\alpha$ und acht von $\beta$.