Semantik: Zusammenfassung und Herausforderungen

Zusammenfassung

Diese Lektion schließt die Einheit über die Semantik ab. Sie rekonstruiert die deduktive Kette, die von der Fortsetzung einer Belegung auf alle Formeln und vom Koinzidenzlemma zur Folgerung, zur Äquivalenz und zu deren beiden Arbeitssätzen führt, der Ersetzung und der uniformen Substitution; von dort zu den Gesetzen für beliebig viele Glieder, zur funktionalen Vollständigkeit und zu den Junktorenmengen, und von dort zu den Normalformen, ihrem Algorithmus und den Schaltungen, wobei bei jedem Glied angegeben wird, welche Ergebnisse es verwendet und in welcher Lektion es bewiesen wird. Sie unterscheidet, was die Einheit bewiesen hat, von dem, was sie aus den vorangehenden übernommen hat, entscheidet auf drei Weisen ein Argument, das der Kurs seit der ersten Einheit mitführt, und erklärt, warum die Frage, die die Einheit offenlässt, nämlich ob das unter jeder Belegung Wahre mit dem Ableitbaren übereinstimmt, zur Metatheorie führt. Sie wiederholt in ihrem Abschlusstest die Fertigkeiten des Eingangstests und endet mit sechs Herausforderungen, schwieriger als die Aufgaben der Lektionen, die verlangen, die Werkzeuge mehrerer von ihnen zu verbinden.

Lernziele

Die logische Ordnung der Ergebnisse der Einheit rekonstruieren und dabei die früheren Ergebnisse, auf die sich jedes stützt, und die Lektion, in der es bewiesen wird, bestimmen.
Erklären, wie die rekursive Fortsetzung, das Koinzidenzlemma, die semantische Ersetzung und die verallgemeinerten Gesetze zur funktionalen Vollständigkeit, zur Existenz der Normalformen und zur Korrektheit und Termination ihres Algorithmus führen.
Unterscheiden, was die Einheit bewiesen hat, von dem, was sie aus den vorangehenden übernommen hat, und von dem, was sie der Metatheorie überlassen hat, insbesondere die Übereinstimmung der semantischen Folgerung mit der Ableitbarkeit und die Kompaktheit.
Aufgaben lösen, die das Rechnen mit Werten, die Folgerung, die uniforme Substitution, die Junktorenmengen, die Normalformen und die Schaltungen verbinden.

Was die Einheit erreicht hat

Die Einheit hatte sich vorgenommen, den Formeln der in der ersten Einheit aufgebauten Sprache eine Bedeutung zu geben, ohne das deduktive System der zweiten anzutasten, und aus dieser Bedeutung Verfahren zu gewinnen, um die Fragen zu entscheiden, die die Logik über sie stellt: ob eine Formel allgemeingültig ist, ob sie erfüllbar ist, ob sie aus anderen folgt, ob sie dasselbe sagt wie eine andere. Das Vorhaben ist mit einigen Vorbehalten erfüllt worden, jeder an seiner Stelle erklärt: die Zweiwertigkeit und die Wahrheitsfunktionalität, die nicht bewiesen, sondern gewählt werden und deren Preis die Lektion über die Formalisierung gezeigt hat; die eindeutige Lesbarkeit, die Definition durch Rekursion, die Induktion und die offiziellen Abkürzungen, die in der ersten Einheit bewiesen oder festgelegt wurden und hier verwendet werden; und die unentbehrlichen Tatsachen über Mengen und Funktionen, an die dort erinnert wurde, wo sie gebraucht wurden. Mit diesen Vorbehalten lässt sich der zurückgelegte Weg als eine einzige deduktive Kette in sechs Abschnitten lesen, einem pro Lektion.

Der Wert einer Formel

Die Lektion über die Semantik der Aussagenlogik hat eine Belegung als eine Funktion von den Variablen in $\{0, 1\}$ definiert und mit dem Satz über die Definition durch Rekursion über Formeln bewiesen, dass sie sich mit einer einzigen Klausel eindeutig auf alle Formeln fortsetzen lässt: $v((\varphi \downarrow \psi)) = (1 - v(\varphi))(1 - v(\psi))$ . Aus den offiziellen Abkürzungen hat sie, ohne irgendetwas weiter festzusetzen, den Wert jedes definierten Junktors berechnet, geschrieben als Polynom in den Werten der Komponenten, und damit die Tafel der Implikation, die hier ein Satz ist. Sie hat durch Induktion über die Komplexität das Koinzidenzlemma bewiesen, aus dem folgt, dass die Wahrheitstafel mit ihren $2^{n}$ Zeilen alles enthält, was die unendlich vielen Belegungen über eine Formel mit $n$ Variablen sagen; sie hat die Erfüllung, die Allgemeingültigkeit, die Erfüllbarkeit, die Kontradiktion und die Kontingenz definiert, klargestellt, dass $\not\models \varphi$ besagt, dass $\varphi$ nicht allgemeingültig ist, und nicht, dass sie eine Kontradiktion ist, $\top := (v_{1} \rightarrow v_{1})$ und $\bot := \neg\top$ festgelegt und die Entscheidbarkeit der Allgemeingültigkeit und der Erfüllbarkeit gewonnen, mit exponentiellem Aufwand, den die gelenkte Suche nach einer widerlegenden Belegung verringert, ohne ihn zu beseitigen.

Folgerung und Äquivalenz

Die Lektion über semantische Folgerung und Äquivalenz hat die Folgerung aus einer endlichen oder unendlichen Prämissenmenge definiert und bewiesen, dass sie die strukturellen Eigenschaften der Deduktion besitzt (Reflexivität, Monotonie, Schnitt und Transitivität), mit Beweisen, die über die Belegungen gehen, statt Zeilen zu handhaben. Das semantische Deduktionstheorem, $\Gamma \cup \{\varphi\} \models \psi \Leftrightarrow \Gamma \models (\varphi \rightarrow \psi)$ , wurde auf die einzige falsche Zeile der Implikation zurückgeführt, und die Folgerung auf die Unerfüllbarkeit: $\Gamma \models \varphi \Leftrightarrow \Gamma \cup \{\neg\varphi\}$ ist unerfüllbar. Die semantische Äquivalenz, definiert als Gleichheit der Werte, erwies sich als übereinstimmend mit der wechselseitigen Folgerung und mit der Allgemeingültigkeit des Bikonditionals. Ihre beiden Arbeitssätze wurden durch Induktion über die Komplexität bewiesen: die Ersetzung eines Vorkommens einer Teilformel durch eine äquivalente, mit dem Fall des Gesamtvorkommens, der nicht weggelassen werden darf, und die uniforme Substitution beliebiger Formeln für Variablen, die Allgemeingültigkeit, Äquivalenz und Folgerung erhält. Mit ihnen lassen sich die Gesetze des Katalogs, nachgewiesen als Identitäten zwischen Polynomen, an jeder Stelle jeder Formel anwenden und verketten.

Gesetze für beliebig viele Glieder

Die Lektion über die verallgemeinerten De-Morgan- und Distributivgesetze hat durch Rekursion, mit Linksklammerung, die Konjunktion und die Disjunktion von $n$ Formeln definiert und durch Induktion über die Anzahl der Glieder das Wertlemma bewiesen, das besagt, dass eine Konjunktion genau dann wahr ist, wenn alle ihre Glieder es sind, und eine Disjunktion genau dann, wenn eines es ist. Mit ihm und mit der Verträglichkeit der Junktoren mit der Äquivalenz hat sie die verallgemeinerte Assoziativität gewonnen, die mit einer Kette von Äquivalenzen bewiesen wurde, damit sie auch für die beweisbare Äquivalenz gilt, die Unabhängigkeit von Reihenfolge und Wiederholungen, die verallgemeinerten De-Morgan-Gesetze und die verallgemeinerte Distributivität, deren Induktion über zwei Indizes so angelegt wurde, dass die Induktionsvoraussetzung alle Längen der zweiten Liste abdeckt; das duale Gesetz wurde mit De Morgan gewonnen, ohne die doppelte Induktion zu wiederholen.

Wahrheitsfunktionen

Die Lektion über funktionale Vollständigkeit ist den umgekehrten Weg gegangen, von der Tafel zur Formel. Sie hat die Wahrheitsfunktionen von $n$ Argumenten gezählt, $2^{2^{n}}$ , gezeigt, dass jede Formel genau eine von ihnen darstellt und dass zwei Formeln genau dann äquivalent sind, wenn sie dieselbe darstellen, und den Satz von der funktionalen Vollständigkeit bewiesen: Die Konjunktion einer Zeile ist genau auf ihrer Zeile wahr, und die Disjunktion der Konjunktionen der Zeilen, auf denen die Funktion den Wert $1$ hat, stellt sie dar. Da diese Formel eine Zeichenkette aus Kreisen und Scheiben ist, genügt der Peirce-Pfeil für sich allein; mit dem Kriterium des Peirce-Pfeils genügen auch $\{\neg, \wedge\}$ , $\{\neg, \vee\}$ , $\{\neg, \rightarrow\}$ und der Sheffer-Strich; und mit dem Abschlussprinzip hat sie bewiesen, dass alle Formeln von $\{\wedge, \vee, \rightarrow, \leftrightarrow\}$ die $1$ erhalten, sodass diese Menge nicht genügt.

Normalformen

Die Lektion über Normalformen hat in jeder Klasse äquivalenter Formeln Vertreter fester Gestalt gewählt. Sie hat die Literale, die Klauseln und die Elementarkonjunktionen definiert und bewiesen, dass die Negation einer Normalform zu ihrer dualen äquivalent ist, die jede Konjunktion in eine Disjunktion und jedes Literal in sein Gegenstück verwandelt. Sie hat aus der Tafel die kanonischen Normalformen gebildet, die nach Festlegung der Variablen eindeutig sind, und die Existenz beider Normalformen auf zwei Weisen bewiesen: über die Tafel, als Korollar der funktionalen Vollständigkeit, und durch Induktion über die Komplexität, mit dem einzigen Fall des Peirce-Pfeils, der zur Konjunktion der Negationen seiner Komponenten äquivalent ist, und mit einer Induktionsvoraussetzung, die beide Formen zugleich verlangt, weil die Negation sie vertauscht. Sie hat schließlich gezeigt, dass sich die Allgemeingültigkeit einer konjunktiven Form und die Erfüllbarkeit einer disjunktiven auf einen Blick an ihren komplementären Paaren ablesen lassen.

Der Algorithmus und die Schaltungen

Die Lektion über den Normalform-Algorithmus und seine Anwendungen hat den zweiten Existenzbeweis in ein Verfahren verwandelt, das auf Schreibweisen wirkt: die Junktoren außer $\neg$ , $\wedge$ und $\vee$ beseitigen, die Negationen bis zu den Variablen hinabschieben und distribuieren. Sie hat seine Korrektheit mit der Ersetzung in einer Schreibweise bewiesen, die den Ersetzungssatz an die Abkürzungen anpasst, und seine Termination mit drei Maßen, die bei jedem Schritt abnehmen und deren letztes die Konjunktion als Produkt liest; sie hat außerdem bewiesen, dass die konjunktive Form von $\bigvee_{i=1}^{n} (p_i \wedge q_i)$ notwendig $2^{n}$ Klauseln hat, sodass das Wachstum kein Mangel des Algorithmus ist. Danach hat sie die Normalformen einer Blackbox aus ihrer Tafel gewonnen, sie durch Verschmelzen benachbarter Zeilen verkürzt und in Schaltungen aus Schaltern umgewandelt, deren Leitfähigkeit der Wert ihrer Formel ist.

Die folgende Abbildung fasst die sechs Abschnitte zu einer einzigen Kette zusammen. Jeder Knoten der Spalte ist eine Definition oder ein Ergebnis, numeriert nach der logischen Ordnung und durch einen Bogen mit den früheren Gliedern verbunden, die sein Beweis verwendet; um sie herum schweben die Stützen, das heißt die Prinzipien und Werkzeuge, auf die die Kette immer wieder zurückgreift, jede durch eine durchgezogene Linie mit den Gliedern verbunden, die sich auf sie stützen, und durch eine gepunktete mit dem Glied, in dem sie festgestellt wird, außer denen, die diese Kette nicht beweist (die eindeutige Lesbarkeit mit der Rekursion, die Induktion und die offiziellen Abkürzungen, aus der ersten Einheit), die als Ringe gezeichnet sind. Ein Klick auf eine Stütze hebt alle Glieder hervor, die sie verwenden, und jedes Glied verweist auf die Lektion, in der es bewiesen wird. Man beachte, dass die Induktion und die Werte der Junktoren die meistbesuchten Stützen der Einheit sind und dass das Wertlemma, obwohl es in der dritten Lektion bewiesen wird, fast alles trägt, was die letzten drei über Konjunktionen und Disjunktionen sagen.

Stützen der Kette

AEindeutige Lesbarkeit und Rekursion. Ist $\sigI\varphi\psi = \sigI\varphi'\psi'$ , wobei die vier Zeichenketten Formeln sind, so gilt $\varphi = \varphi'$ und $\psi = \psi'$ ; daher definiert eine Regel, die den Wert von $\sigI\varphi\psi$ aus $\varphi$ , aus $\psi$ und aus deren Werten berechnet, eine einzige Funktion auf den Formeln. Bewiesen in der ersten Einheit. In dieser Einheit ohne Beweis angenommen.
BInduktion. Einfache und starke Induktion über die natürlichen Zahlen und Induktion über die Komplexität der Formeln, deren einzige Fälle die Variablen und der Peirce-Pfeil $(\varphi \downarrow \psi)$ sind. Bewiesen in der ersten Einheit. In dieser Einheit ohne Beweis angenommen.
COffizielle Abkürzungen. $\neg\varphi := (\varphi \downarrow \varphi)$ , $(\varphi \vee \psi) := \neg(\varphi \downarrow \psi)$ , $(\varphi \wedge \psi) := \neg(\neg\varphi \vee \neg\psi)$ , $(\varphi \rightarrow \psi) := (\neg\varphi \vee \psi)$ , $(\varphi \leftrightarrow \psi) := ((\varphi \rightarrow \psi) \wedge (\psi \rightarrow \varphi))$ und $(\varphi \veebar \psi) := \neg(\varphi \leftrightarrow \psi)$ . Festgelegt in der ersten Einheit. In dieser Einheit ohne Beweis angenommen.
DWerte der Junktoren. Mit $a = v(\varphi)$ und $b = v(\psi)$ : $v(\neg\varphi) = 1 - a$ , $v((\varphi \vee \psi)) = a + b - ab$ , $v((\varphi \wedge \psi)) = ab$ , $v((\varphi \rightarrow \psi)) = 1 - a(1 - b)$ , $v((\varphi \leftrightarrow \psi)) = ab + (1 - a)(1 - b)$ und $v((\varphi \veebar \psi)) = a + b - 2ab$ , wobei $a^{2} = a$ . Begründet in: 1. Fortsetzung einer Belegung.
EKoinzidenzlemma. Stimmen zwei Belegungen auf den Variablen von $\varphi$ überein, so geben sie $\varphi$ denselben Wert; deshalb sagt die Tafel mit $2^{n}$ Zeilen alles. Begründet in: 2. Koinzidenzlemma und Tafeln.
FSemantische Ersetzung. Ist $\theta \eqsem \theta'$ und entsteht $\chi'$ aus $\chi$ , indem ein Vorkommen von $\theta$ durch $\theta'$ ersetzt wird, so gilt $\chi \eqsem \chi'$ . Begründet in: 7. Semantischer Ersetzungssatz.
GÄquivalenzgesetze. Doppelte Negation, Idempotenz, Kommutativität, Assoziativität, Distributivität, De Morgan, Absorption, Identität, Dominanz, Tertium non datur und Satz vom Widerspruch, für beliebige Formeln. Begründet in: 9. Äquivalenzgesetze.
HWertlemma. $v\left( \bigwedge_{i=1}^{n} \varphi_i \right) = 1$ genau dann, wenn $v(\varphi_i) = 1$ für alle $i$ ; $v\left( \bigvee_{i=1}^{n} \varphi_i \right) = 1$ genau dann, wenn $v(\varphi_i) = 1$ für ein $i$ . Begründet in: 10. Wertlemma und Verträglichkeit.

Abschnitt 1 Der Wert einer Formel
- Den Wert einer Formel mit der Klausel des Peirce-Pfeils berechnen und aus den Abkürzungen den jedes definierten Junktors herleiten.
- Das Koinzidenzlemma beweisen und mit ihm begründen, dass eine Tafel mit $2^{n}$ Zeilen genügt.
- Formeln und Mengen einordnen, ohne $\not\models \varphi$ mit der Kontradiktion zu verwechseln, und die Allgemeingültigkeit durch die Suche nach einer widerlegenden Belegung entscheiden.
1. Fortsetzung einer Belegung. Jede Belegung $v$ lässt sich mit der Klausel $v((\varphi \downarrow \psi)) = (1 - v(\varphi))(1 - v(\psi))$ eindeutig auf alle Formeln fortsetzen; durch Auflösen der Abkürzungen berechnet man den Wert von $\neg$ , $\vee$ , $\wedge$ , $\rightarrow$ , $\leftrightarrow$ und $\veebar$ .
  Stützt sich auf: A (Eindeutige Lesbarkeit und Rekursion), C (Offizielle Abkürzungen). Bewiesen in: Semantik der Aussagenlogik.
2. Koinzidenzlemma und Tafeln. Stimmen $v$ und $v'$ auf $V(\varphi)$ überein, so gilt $v(\varphi) = v'(\varphi)$ , durch Induktion über die Komplexität; daher sind die Werte von $\varphi$ unter allen Belegungen genau die der $2^{n}$ Zeilen ihrer Tafel.
  Verwendet: 1. Fortsetzung einer Belegung. Stützt sich auf: B (Induktion). Bewiesen in: Semantik der Aussagenlogik.
3. Einteilung und Entscheidung. Jede Formel ist genau eines von dreien: allgemeingültig, kontingent oder eine Kontradiktion; $\varphi$ ist genau dann allgemeingültig, wenn $\neg\varphi$ eine Kontradiktion ist, und sie ist genau dann eine Kontradiktion, wenn $\models \neg\varphi$ . $\top$ und das Tertium non datur sind allgemeingültig, $\bot$ ist eine Kontradiktion, und Allgemeingültigkeit und Erfüllbarkeit werden durch Durchlaufen der Zeilen entschieden.
  Stützt sich auf: D (Werte der Junktoren), E (Koinzidenzlemma). Bewiesen in: Semantik der Aussagenlogik.
Abschnitt 2 Folgerung und Äquivalenz
- Folgerungen aus endlichen oder unendlichen Mengen entscheiden, indem man ein Gegenmodell angibt oder beweist, dass es keines gibt.
- Das semantische Deduktionstheorem und die Rückführung der Folgerung auf die Unerfüllbarkeit anwenden.
- Die Ersetzung eines Vorkommens von der uniformen Substitution unterscheiden und beide durch Induktion über die Komplexität beweisen.
- Äquivalenzen durch Ketten herstellen und dabei jedes Gesetz richtig benennen.
1. Die Folgerung und ihre Eigenschaften. $\Gamma \models \varphi$ , wenn jede Belegung, die $\Gamma$ erfüllt, auch $\varphi$ erfüllt; $\emptyset \models \varphi$ genau dann, wenn $\models \varphi$ ; Reflexivität, Monotonie, Schnitt und Transitivität gelten, und aus einer unerfüllbaren Menge folgt jede Formel.
  Verwendet: 3. Einteilung und Entscheidung. Bewiesen in: Semantische Folgerung und Äquivalenz.
2. Semantische Deduktion und Unerfüllbarkeit. $\Gamma \cup \{\varphi\} \models \psi \Leftrightarrow \Gamma \models (\varphi \rightarrow \psi)$ , durch die einzige falsche Zeile der Implikation; $\{\varphi_1, \ldots, \varphi_n\} \models \psi \Leftrightarrow\; \models (\varphi_1 \rightarrow (\varphi_2 \rightarrow \cdots (\varphi_n \rightarrow \psi) \cdots))$ ; und $\Gamma \models \varphi$ genau dann, wenn $\Gamma \cup \{\neg\varphi\}$ unerfüllbar ist.
  Verwendet: 4. Die Folgerung und ihre Eigenschaften. Stützt sich auf: D (Werte der Junktoren). Bewiesen in: Semantische Folgerung und Äquivalenz.
3. Semantische Äquivalenz. $\varphi \eqsem \psi$ genau dann, wenn $\varphi \models \psi$ und $\psi \models \varphi$ , genau dann, wenn $\models (\varphi \leftrightarrow \psi)$ ; die Äquivalenz ist reflexiv, symmetrisch und transitiv, und zwei äquivalente Formeln sind als Prämissen und als Konklusionen austauschbar.
  Verwendet: 4. Die Folgerung und ihre Eigenschaften. Stützt sich auf: D (Werte der Junktoren). Bewiesen in: Semantische Folgerung und Äquivalenz.
4. Semantischer Ersetzungssatz. Ist $\theta \eqsem \theta'$ und ersetzt man in $\chi$ ein Vorkommen von $\theta$ durch $\theta'$ , das Gesamtvorkommen eingeschlossen, so erhält man eine zu $\chi$ äquivalente Formel; ebenso bei der Substitution aller Vorkommen auf einmal.
  Verwendet: 1. Fortsetzung einer Belegung, 6. Semantische Äquivalenz. Stützt sich auf: A (Eindeutige Lesbarkeit und Rekursion), B (Induktion). Bewiesen in: Semantische Folgerung und Äquivalenz.
5. Uniforme Substitution. Ist $w(v_n) = v(\sigma(v_n))$ , so gilt $v(\sigma(\chi)) = w(\chi)$ ; daher gilt, wenn $\models \chi$ , auch $\models \sigma(\chi)$ , und die Substitution erhält Äquivalenz und Folgerung, aber weder Erfüllbarkeit noch Kontingenz.
  Verwendet: 1. Fortsetzung einer Belegung, 4. Die Folgerung und ihre Eigenschaften, 6. Semantische Äquivalenz. Stützt sich auf: A (Eindeutige Lesbarkeit und Rekursion), B (Induktion). Bewiesen in: Semantische Folgerung und Äquivalenz.
6. Äquivalenzgesetze. Die Gesetze des Katalogs werden als Identitäten zwischen Polynomen mit $a^{2} = a$ nachgewiesen; mit der Ersetzung und der Transitivität lassen sie sich auf Teilformeln anwenden und verketten.
  Verwendet: 3. Einteilung und Entscheidung, 6. Semantische Äquivalenz. Stützt sich auf: D (Werte der Junktoren), F (Semantische Ersetzung). Bewiesen in: Semantische Folgerung und Äquivalenz.
Abschnitt 3 Gesetze für beliebig viele Glieder
- Konjunktionen und Disjunktionen von $n$ Gliedern als linksgeklammerte Zeichenketten auflösen und ihren Wert berechnen.
- Durch Induktion über die Anzahl der Glieder die verallgemeinerte Assoziativität, die Unabhängigkeit von der Reihenfolge und die verallgemeinerten De-Morgan-Gesetze beweisen.
- Die verallgemeinerte Distributivität mit einer Induktion über zwei Indizes beweisen und die Glieder zählen, die sie erzeugt.
1. Wertlemma und Verträglichkeit. Ist $\alpha \eqsem \alpha'$ und $\beta \eqsem \beta'$ , so gilt $\neg\alpha \eqsem \neg\alpha'$ , $(\alpha \wedge \beta) \eqsem (\alpha' \wedge \beta')$ und $(\alpha \vee \beta) \eqsem (\alpha' \vee \beta')$ ; eine Konjunktion von $n$ Gliedern hat genau dann den Wert $1$ , wenn alle ihre Glieder den Wert $1$ haben, eine Disjunktion genau dann, wenn ein Glied den Wert $1$ hat, und äquivalente Glieder ergeben äquivalente Konjunktionen und Disjunktionen.
  Verwendet: 6. Semantische Äquivalenz. Stützt sich auf: D (Werte der Junktoren), B (Induktion). Bewiesen in: Verallgemeinerte De-Morgan- und Distributivgesetze.
2. Assoziativität und Reihenfolge. Die Konjunktion der Konjunktionen zweier Listen ist zu der ihrer Verkettung äquivalent, und jede Gruppierung ist zur linksgeklammerten äquivalent; zwei Listen mit denselben Gliedern ergeben äquivalente Konjunktionen und Disjunktionen, unabhängig von Reihenfolge und Wiederholungen.
  Stützt sich auf: H (Wertlemma), G (Äquivalenzgesetze), B (Induktion). Bewiesen in: Verallgemeinerte De-Morgan- und Distributivgesetze.
3. Verallgemeinerte De-Morgan-Gesetze. $\neg \bigwedge_{i=1}^{n} \varphi_i \eqsem \bigvee_{i=1}^{n} \neg\varphi_i$ und $\neg \bigvee_{i=1}^{n} \varphi_i \eqsem \bigwedge_{i=1}^{n} \neg\varphi_i$ , indem man das zweistellige Gesetz auf die letzte Verknüpfung und die Induktionsvoraussetzung auf das Innere anwendet.
  Stützt sich auf: H (Wertlemma), G (Äquivalenzgesetze), B (Induktion). Bewiesen in: Verallgemeinerte De-Morgan- und Distributivgesetze.
4. Verallgemeinerte Distributivität. $\left( \bigvee_{i=1}^{n} \varphi_i \right) \wedge \left( \bigvee_{j=1}^{m} \psi_j \right) \eqsem \bigvee_{i,j} (\varphi_i \wedge \psi_j)$ , mit $nm$ Gliedern in lexikographischer Reihenfolge; und ihr duales Gesetz, das die Disjunktion zweier Konjunktionen distribuiert, mit De Morgan.
  Verwendet: 11. Assoziativität und Reihenfolge, 12. Verallgemeinerte De-Morgan-Gesetze. Stützt sich auf: H (Wertlemma), G (Äquivalenzgesetze), B (Induktion). Bewiesen in: Verallgemeinerte De-Morgan- und Distributivgesetze.
Abschnitt 4 Wahrheitsfunktionen
- Die Wahrheitsfunktionen zählen und die Äquivalenz entscheiden, indem man die Funktionen vergleicht, die zwei Formeln darstellen.
- Die Formel einer Tafel bilden und jede Funktion allein mit dem Peirce-Pfeil schreiben.
- Beweisen, dass eine Junktorenmenge vollständig ist, mit dem Kriterium des Peirce-Pfeils, oder dass sie es nicht ist, mit einer Eigenschaft, die ihre Formeln erhalten.
1. Wahrheitsfunktionen. Es gibt $2^{2^{n}}$ Wahrheitsfunktionen von $n$ Argumenten; eine Formel mit Variablen unter $v_1, \ldots, v_n$ stellt genau eine von ihnen dar, $f_\varphi$ , und $\varphi \eqsem \psi \Leftrightarrow f_\varphi = f_\psi$ .
  Verwendet: 6. Semantische Äquivalenz. Stützt sich auf: E (Koinzidenzlemma). Bewiesen in: Funktionale Vollständigkeit.
2. Funktionale Vollständigkeit. Die Konjunktion einer Zeile hat genau auf ihrer Zeile den Wert $1$ ; die Disjunktion der Konjunktionen der Zeilen, auf denen $f$ den Wert $1$ hat, oder $(v_{1} \wedge \neg v_{1})$ , wenn es keine gibt, stellt $f$ dar; und jede Formel ist zur Formel ihrer Tafel äquivalent.
  Verwendet: 14. Wahrheitsfunktionen. Stützt sich auf: H (Wertlemma), D (Werte der Junktoren). Bewiesen in: Funktionale Vollständigkeit.
3. Vollständige und unvollständige Mengen. Der Peirce-Pfeil genügt, weil sich die Abkürzungen auflösen lassen; drücken die Formeln von $K$ den Wert $(1 - a)(1 - b)$ aus, so ist $K$ vollständig, und ebenso $\{\neg, \wedge\}$ , $\{\neg, \vee\}$ , $\{\neg, \rightarrow\}$ und $\{\uparrow\}$ ; die Formeln von $\{\wedge, \vee, \rightarrow, \leftrightarrow\}$ haben den Wert $1$ , wenn alle Variablen den Wert $1$ haben, und diese Menge ist nicht vollständig.
  Verwendet: 15. Funktionale Vollständigkeit. Stützt sich auf: C (Offizielle Abkürzungen), B (Induktion), D (Werte der Junktoren). Bewiesen in: Funktionale Vollständigkeit.
Abschnitt 5 Normalformen
- Literale, Klauseln und Normalformen erkennen und dabei die Gestalt der Zeichenkette von ihrer Bedeutung unterscheiden.
- Die kanonischen Normalformen aus der Tafel bilden und ihre Eindeutigkeit beweisen.
- Durch Induktion die Existenz der Normalformen beweisen, mit der Induktionsvoraussetzung, die beide verlangt.
- Auf einen Blick die Allgemeingültigkeit einer konjunktiven Form und die Erfüllbarkeit einer disjunktiven entscheiden.
1. Literale und Dualität. $\neg\ell \eqsem \ell^{*}$ ; eine Elementarkonjunktion ist genau dann erfüllbar, wenn sie kein komplementäres Paar enthält, und eine Klausel ist genau dann allgemeingültig, wenn sie eines enthält; die Negation einer Normalform ist zu ihrer dualen äquivalent, sodass die konjunktive Form von $\varphi$ die duale der disjunktiven Form von $\neg\varphi$ ist.
  Verwendet: 12. Verallgemeinerte De-Morgan-Gesetze. Stützt sich auf: G (Äquivalenzgesetze), F (Semantische Ersetzung), H (Wertlemma). Bewiesen in: Normalformen.
2. Kanonische Normalformen. Ist $\varphi$ erfüllbar, so ist sie zu ihrer disjunktiven kanonischen Normalform äquivalent, und ist sie nicht allgemeingültig, zur konjunktiven; sind die Variablen $v_1, \ldots, v_n$ festgelegt, so sind zwei kanonische Normalformen genau dann äquivalent, wenn sie dieselbe Zeichenkette sind, und zwei erfüllbare Formeln genau dann äquivalent, wenn sie dieselbe disjunktive kanonische Normalform haben.
  Verwendet: 15. Funktionale Vollständigkeit, 17. Literale und Dualität. Stützt sich auf: H (Wertlemma), E (Koinzidenzlemma). Bewiesen in: Normalformen.
3. Existenz durch Induktion. $(\varphi \downarrow \psi) \eqsem (\neg\varphi \wedge \neg\psi)$ ; die Normalformen bleiben unter Konjunktion und Disjunktion erhalten, die disjunktive Form einer Konjunktion und die konjunktive einer Disjunktion durch verallgemeinerte Distributivität; durch Induktion, mit der Induktionsvoraussetzung für beide Formen, hat jede Formel eine disjunktive und eine konjunktive Form.
  Verwendet: 17. Literale und Dualität, 11. Assoziativität und Reihenfolge, 13. Verallgemeinerte Distributivität. Stützt sich auf: B (Induktion), F (Semantische Ersetzung). Bewiesen in: Normalformen.
4. Was man auf einen Blick sieht. Eine konjunktive Form ist genau dann allgemeingültig, wenn jede Klausel ein komplementäres Paar enthält; eine disjunktive Form ist genau dann erfüllbar, wenn eine Elementarkonjunktion keines enthält.
  Verwendet: 17. Literale und Dualität. Stützt sich auf: H (Wertlemma). Bewiesen in: Normalformen.
Abschnitt 6 Der Algorithmus und die Schaltungen
- Den Umschreibungsalgorithmus anwenden und die günstige Beseitigung des Bikonditionals wählen.
- Seine Korrektheit und seine Termination beweisen und erklären, warum die konjunktive Form exponentiell wachsen kann.
- Die Normalformen einer Blackbox gewinnen und vereinfachen und mit ihnen Schaltungen aus Schaltern entwerfen.
1. Korrektheit und Termination des Algorithmus. Das Ersetzen einer Teilschreibweise durch eine äquivalente ergibt eine äquivalente Schreibweise; jede Regel ist eine Äquivalenz, und eine irreduzible Schreibweise ist eine irgendwie gruppierte Normalform; die Maße $M_1$ , $M_2$ , mit $M_2(\neg\varphi) = 2^{M_2(\varphi)}$ , und $M_3$ , mit $M_3(\varphi \wedge \psi) = M_3(\varphi)\,M_3(\psi)$ , nehmen bei jedem Schritt ab.
  Verwendet: 19. Existenz durch Induktion, 11. Assoziativität und Reihenfolge. Stützt sich auf: G (Äquivalenzgesetze), D (Werte der Junktoren), B (Induktion). Bewiesen in: Der Normalform-Algorithmus und seine Anwendungen.
2. Exponentielles Wachstum. $\bigvee_{i=1}^{n} (p_i \wedge q_i)$ ist zu einer konjunktiven Form mit $2^{n}$ Klauseln äquivalent, und jede äquivalente konjunktive Form hat mindestens $2^{n}$ nicht allgemeingültige Klauseln.
  Verwendet: 19. Existenz durch Induktion, 17. Literale und Dualität. Stützt sich auf: H (Wertlemma). Bewiesen in: Der Normalform-Algorithmus und seine Anwendungen.
3. Benachbarte Zeilen und Schaltungen. $(\kappa \wedge \ell) \vee (\kappa \wedge \ell^{*}) \eqsem \kappa$ und sein duales Gesetz; eine Serien-Parallel-Schaltung leitet im Zustand $v$ genau dann, wenn $v(\varphi_C) = 1$ , und jede Wahrheitsfunktion wird durch eine Schaltung verwirklicht.
  Verwendet: 15. Funktionale Vollständigkeit, 18. Kanonische Normalformen, 17. Literale und Dualität, 11. Assoziativität und Reihenfolge. Stützt sich auf: G (Äquivalenzgesetze), F (Semantische Ersetzung), D (Werte der Junktoren), B (Induktion). Bewiesen in: Der Normalform-Algorithmus und seine Anwendungen.

Auf dem Weg zur Metatheorie. Die Kette hält dort an, wo die Semantik für jede Frage über Formeln ein Verfahren erreicht. Es bleibt zu klären, ob das unter jeder Belegung Wahre genau das im System Ableitbare ist: Die nächste Einheit wird beide Begriffe vergleichen.