Kapitel 3 - Aussagenlogik
 
 
 
3.1 Die Sprache der Aussagenlogik zurück

Die Formalisierung der Logik hat die Konstruktion einer formalen Sprache zum Ziel, mit deren Hilfe jene Struktureigenschaften von Schlüssen exakt formalisiert werden solllen, die ihre Gültigkeit oder Falschheit bedingen. In Analogie zur linguistischen Analyse natürlicher Sprachen besteht die Konstruktion einer formalen Sprache aus der Angabe einer Syntax sowie einer Semantik: Die Syntax einer formalen Sprache ist ein Regelsystem, das Bildungsregeln für die wohlgeformten Ausdrücke dieser Sprache beschreibt. Die Semantik einer solchen Sprache weist jedem ihrer Ausdrücke eine Bedeutung zu, d. h. einen Ausdruck einer formalen Sprache, welche die Semantik der betrachteten Sprache formalisiert. Die Zuweisung einer Bedeutung zu einem zusammengesetzten Ausdruck vollzieht sich folgendermaßen:

    "The meaning of a complex expression is a function of the meanings of its parts and of the syntactic rules by which they are combined." (Partee et al. 1990:318)

Dieses Prinzip wird rekursiv auf die Bedeutungen der Teilausdrücke angewandt, bis man an den atomaren Ausdrücken anlangt. Dieses Vorgehen einer funktionalen Ableitung der Bedeutung eines komplexen Ausdrucks aus den Bedeutungen seiner Teilausdrücke beruht auf dem sogenannten Kompositionalitätsprinzip der Bedeutung, das Frege zugeschrieben wird, der es aber nicht explizit erwähnt.

Wenn nun aber die Logik die Formalisierung von Schlüssen zum Ziel hat, die wir mit Hilfe natürlicher Sprachen ausdrücken, so muss die Logik gerade von jenen Operationen Gebrauch machen, die sie zu formalisieren beabsichtigt. Wenn wir nämlich die Logik als formale Sprache konstruieren bzw. definieren, so geschieht dies mit Hilfe einer natürlichen Sprache, z. B. mit Hilfe des Deutschen.

Wie kann dieser scheinbare Widerspruch aufgelöst werden? Die Lösung des Problems stammt von Taski (siehe Tarski 1977), der zwei Sprachebenen unterscheidet: Die Objektsprache als Ebene der formalen Logik wird mit Hilfe einer Metasprache, die sozusagen auf einer Ebene oberhalb der Objektsprache liegt, eingeführt. Als Metasprache dient uns im folgenden das Deutsche. Treten in einem metasprachlichen Ausdruck objektsprachliche Termini auf, die zugleich Elemente der Metasprache sind, so werden diese mittels " ‘‘ " und " ’’ " besonders gekennzeichnet. So wird etwa mit einem ‘‘und’’ ein objektsprachliches Zeichen markiert.

Bereits bei der Einführung in die Mengenlehre haben wir gesehen, dass beim Aufbau einer formalen Sprache zunächst ihre primitiven oder auch atomaren Einheiten, aus denen sich alle anderen Ausdrücke dieser Sprache zusammen der Sprache zusammensetzen, einzuführen sind. Die Wahl der primitiven Einheiten restringiert selbstverständlich die Ausdrucksstärke der konstruierten Sprache. Die Aristotelische Logik benannte Begriffe, Urteile und Schlüsse als die atomaren Einheiten der Logik. Diese Dreiteilung der Grundbegriffe der Logik wurde im wesentlichen durch das Mittelalter hindurch bis heute beibehalten.

    Ein Satz ist eine Rede, die etwas von etwas bejaht oder verneint. Sie entweder allgemein oder partikulär oder unbestimmt. Allgemein nenne ich sie, wenn etwas jedem oder keine zukommt, partikulär, wenn es irgend einem oder irgend einem nicht oder nicht jedem zukommt, unbestimmt, wenn die Rede etwas zukommen oder nicht zukommen lässt ohne den Zusatz allgemein oder partikulär (so dass sie es unbestimmt lässt, in welcher von beiden Weisen es zu nehmen ist), wie z. B. in dem Satz: Das Konträre fällt unter die selbe Wissenschaft, oder: Die Lust ist kein Gut. [...]

    Begriff [...] nenne ich die Bestandteile, in die der Satz als in Prädikat und Subjekt der Prädikation sich auflöst, mag nun das Sein bei der Bejahung hinzugesetzt oder bei der Verneinung, wo es Nichtsein wird, ausgeschieden werden.

    Ein Schluss ist eine Rede, in der, wenn etwas gesetzt wird, etwas von dem Gesetzten Verschiedenes notwendig dadurch folgt, dass dieses ist. Mit dem Ausdruck: Dadurch, dass dieses ist, meine ich, dass die Folge seinetwegen eintritt, und damit, dass sie seinetwegen eintritt, dass es sonst keines, von außen zu nehmenden Begriffs bedarf, damit sich ihre Notwendigkeit ergibt.

    Vollkommen nenne ich einen Schluss, der, damit seine Notwendigkeit einleuchtet, außer den Voraussetzungen keiner weiteren Bestimmung bedarf, unvollkommen eine solchen, der noch einer oder mehrerer weiterer Bestimmungen bedarf, die zwar wegen der zugrunde liegenden Begriffe notwendig gelten, aber nicht in den Vordersätzen enthalten sind.

Von George Boole (1815 - 1864) und Augustus De Morgan (1806 - 1871) stammt die für die formale Logik grundlegende algebraische Behandlung der klassischen Logik: Begriffe und Sätze (Urteile) wurden durch Variablen ersetzt sowie Schlüsse durch algebraische Operationen beschrieben. Friedrich Ludwig Gottlob Frege (1848 - 1925) entwickelte die Idee der Formalisierung der Logik via Kalkül weiter. Seine primitiven Einheiten sind Gedanken, die entweder wahr oder falsch sein können. Bertrand Russell (1870 - 1972) und Alfred N. Whitehead (1861 - 1947) nannten ihre primitiven Einheiten Propositionen, die das umfassen, was ein Aussagesatz ausdrückt. Propositionen sind Äquivalenzklassen der Relation "Der Satz Si hat dieselbe Bedeutung wie der Satz Sj". Propositionen, die keine anderen Propositionen enthalten, heißen atomar. Atomare Propositionen sind die logischen Atome der Aussagenlogik. Die "Wörter" der Aussagenlogik sind durch Variablen, die atomare Propositionen symbolisieren, sowie durch eine Reihe logischer Symbole gegeben.

Definition 3.1.1 Sei ATOM = { p, q, r, ... } die Menge der atomaren bzw. elementaren Propositionen. Sei ferner SYMB = { , (, ), ¬, )} die Menge der Symbole. Das Alphabet der propositionalen Logik ist dann die Menge LPROP = ATOM SYMB.

Die Menge aller möglichen "Strings" über LPROP ist L*PROP. Eine echte Teilmenge dieser Menge (das heißt das Universum des durch LPROP determinierten freien Monoids enthält die syntaktisch wohlgeformten Ausdrücke der propositionalen Logik, die Formeln genannt werden.

Definition 3.1.2 Die Menge der wohlgeformten Formeln der Aussagenlogik der Aussagenlogik ist die kleinste Menge PROP L*PROP, für die gilt:

1. ATOM PROP;

2. aus p, q PROP folgt: ( p q ), ( p q ), ¬ p PROP.

Die Konstruktion einer wohlgeformten Formel kann mit Hilfe eines Baumes dargestellt werden, der als Blätter die atomaren Propositionen und als Wurzel den zusammengesetzten Ausdruck ausweist.

Beispiel 3.1.1 Ein Konstruktionsbaum für ( q ¬ ( p r )):

Abbildung 3.1: Ein Konstruktionsbaum für das Ausdrucksbeispiel

Definition 3.1.3 Auf der Grundlage der Operationen , , ¬ können weitere Operationen definiert werden:

1. p q iff ¬ p q;

2. p p iff p q und q p.

Man liest " p q " bzw. " p q " als " p und q " bzw. " p oder q ". " ¬ p " wird gelesen als " nicht p ", schließlich liest man " p q " bzw. " p q " als " p impliziert q " bzw. " p biimpliziert q ". " p q " bzw. " p q " ist die Konjunktion bzw. Disjunktion aus p und q, " ¬ p " heißt Negation von p, " p q " heißt Implikation von q aus p, schließlich heißt " p q " Biimplikation von q und p. Ferner sagt man: Ein Literal ist eine atomare Formel oder deren Negation.

Der Aufbau der Aussagenlogik ist durch die Angabe von Syntaxregeln natürlich nicht beendet. Der Aufbau einer Logik erfolgt vielmehr durch Angabe eines Kalküls, der ein Alphabet, eine Menge von Axiomen sowie eine Menge von Ableitungs- oder Deduktionsregeln als Komponenten enthält. Ein Kalkül verfolgt den Zweck, mit Hilfe der Axiome unter Verwendung der Deduktionsregeln Formeln aus PROP abzuleiten, die Sätze oder Theoreme genannt werden. Die Grundidee des Kalküls besteht also darin, Formeln als Theoreme aus einer gegebenen Menge von Axiomen abzuleiten, die als "wahr" betrachtet werden, und zwar unter Absehung der Bedeutungen der in den Sätzen auftretenden Aussagen. Die Ableitung der Theoreme erfolgt sozusagen rein syntaktisch, ohne Referenz auf die Semantik der verwendeten elementaren Aussagen. Man kann daher einen Kalkül auch als ein Verfahren betrachten, mit dessen Hilfe die Theoreme einer Sprache systematisch aufgezählt werden können, ohne dass der Kalkül zugleich entscheidbar zu sein braucht. Der erste Kalkül für die Aussagen- und Prädikatenlogik stammt von B. Russell und A. N. Whitehead (1910). Von Hilbert stammt der Versuch, die gesamte Mathematik mit Hilfe eines Kalküls zu formalisieren:

Der Grundgedanke meiner Beweistheorie ist folgender: Alles, was im bisherigen Sinne die Mathematik ausmacht, wird streng formalisiert, so dass die eigentliche Mathematik oder die Mathematik in engerem Sinne zu einem Bestande an Formeln wird. Diese unterscheiden sich von den gewöhnlichen Formeln der Mathematik nur dadurch, dass außer den gewöhnlichen Zeichen noch die logischen Zeichen, insbesondere die für "folgt" ( ) und für "nicht" ( ¯ ) darin vorkommen. Gewisse Formeln, die als Bausteine des formalen Gebäudes der Mathematik dienen, werden Axiome genannt. Ein Beweis ist eine Figur, die uns als solche anschaulich vorliegen muss; er besteht aus Schlüssen vermöge des Schlussschemas

wo jedes Mal die Prämissen, das heißt die betreffenden Formeln S und S I jede entweder ein Axiom ist bzw. direkt durch Einsetzung aus einem Axiom entsteht oder mit der Endformel I eines Schlusses übereinstimmt, der vorher im Beweis vorkommt bzw. durch Einsetzung aus einer solchen Endformel entsteht. Eine Formel soll beweisbar heißen, wenn sie entweder ein Axiom ist bzw. durch Einsetzen aus einem Axiom entsteht oder die Endformel eines Beweises ist.

Ein Kalkül der Aussagenlogik wäre also gegeben durch eine Teilmenge von PROP, den Axiomen, sowie durch eine Menge von Ableitungsregeln, die Operationen der Form PROP x PROP PROP darstellen. Durch diese Formalisierung wird das logische Schließen als "Manipulation" von Formeln (Symbolmanipulation) abgebildet, wobei von der Bedeutung der Formeln abgesehen wird: Aussagen werden durch Aussagenvariablen p, q, r, ... ersetzt. Ein Kerngedanke des Kalküls besteht nun darin, dass alles, was mit Hilfe des Kalküls ableitbar ist, für den Gegenstandsbereich, den der Kalkül modelliert, Gültigkeit besitzt. Im Falle des Hilbert-Programmes umfasst dieser Gegenstandsbereich denjenigen der Mathematik, das heißt dass der Hilbertsche Kalkül das mathematisch Beweisen kalkülisieren soll. Gödel (siehe u. a. Gödel 1985) hat gezeigt, dass das Hilbertsche Programm für die Mathematik nicht durchführbar ist.

Als notwendige und hinreichende Voraussetzungen für das Funktionieren eines Kalküls nennt Hilbert folgende Bedingungen:

1. Die Widerspruchsfreiheit soll garantieren, dass in einem Kalkül nicht gleichzeitig p und ¬ p ableitbar sind.

2. Die Forderung nach Vollständigkeit verlangt, dass alle Theoreme des Gegenstandsbereichs innerhalb des Kalküls ableitbar sein sollen, und umgekehrt.

3. Die Bedingung der Einfachheit garantiert, dass unter zwei Kalkülen zur Formalisierung desselben Gegenstandsbereichs derjenige ausgewählt wird, der mit der geringeren Menge an Axiomen auskommt. Es wird also von jedem Axiom verlangt, nicht mittels der übrigen Axiome ableitbar zu sein.

 
3.2 Syntaktische Ableitungen zurück

Definition 3.2.1 Die Menge AXIOM der Axiome der Aussagenlogik enthält die folgenden Formeln aus PROP:

1. p p;

2. p ( q p );

3. ( p q ) (( q r ) ( p r ));

4. ( p ( q r )) (( p → q ) ( p r ));

5. p ( p q ), q ( p q );

6. ( p r ) (( q r ) (( p q ) r ));

7. ( p q ) p, ( p q ) q;

8. ( r p ) (( r q ) ( r ( p q )));

9. (( p q ) r ) (( p r ) ( q r ), (( p r ) (q r ) (( p q ) r );

10. (( p q ) r ) (( p r ) ( q r ), (( p r ) ( q r ) (( p q ) r );

11. ( p q ) ( ¬ q ¬ p );

12. ( p ¬ p ) q;

13. ( q ( p ¬ p ).

Definition 3.2.2 Es existiert genau eine Deduktionsregel:

Man nennt diese Regel modus ponens (MP).

Anmerkung 3.2.1 Der MP ist eine Regel, die einen Schluss von den zwei Prämissen p und p q nach q formalisiert. p und q sind dabei Variablen, speziell Aussagenvariablen, für die beliebige Formeln der Aussagenlogik eingesetzt werden können. So drückt auch die folgende Deduktion den MP aus:

Entscheidend ist nur, dass die Einsetzung für p und q konsistent vorgenommen wird und dass q und q p selbst syntaktisch ableitbar sind oder Axiome darstellen (oder Voraussetzungen bilden).

Definition 3.2.3 Sei P Pot ( PROP ) und q PROP. Es gilt: P q iff q kann aus P AXIOM durch einmalige Anwendung des MP abgeleitet werden.

" " heißt syntaktischer Ableitungsoperator. Mit " *" bezeichnen wir die transitive Hülle von " ". Falls P die leere Menge ist, schreiben wir q. Oftmals schreibt man anstelle von " P *q " einfach " P q ".

Definition 3.2.4 p* =def { q | p * q }.

Die Elemente von p* heißen Ableitungen von p.

Definition 3.2.5 Sei P PROP. Es gilt dann:

1. P heißt konsistent iff es gilt nicht: P q ¬ p.

2. P heißt maximal konsistent, wenn P konsistent ist und wenn für jeden in M nicht enthaltenen Satz p gilt, dass die um p erweiterte Menge M inkonsistent wird.

Definition 3.2.6 p heißt Theorem iff * p, in kürzerer Schreibweise: p.

Beispiel 3.2.1 Es gilt: ( p q ) q p, denn:

Satz 3.2.1 Deduktionstheorem: { p } q iff p q.

Beweis: Wir haben zwei Schritte zu beweisen:

1. Aus { p } q folgt p q, denn: { p } q gilt genau dann, wenn q unter Verwendung der Menge { p } AXIOM sowie des MP in einem Schritt ableitbar ist, das heißt: { p } q iff

.

Hierin steckt aber bereits die Forderung (und Folgerung), dass p q. Falls aber q nicht (in einem Schritt) mit Hilfe von p, sondern durch Rekurs auf ein r AXIOM, r ≠ p abgeleitet wurde, dann gilt:

2. Aus p folgt, dass { p } q ableitbar ist, denn: Der Ausdruck { p } q besagt, dass p als Prämisse verwendet werden kann, um q abzuleiten. Da annahmegemäß q p gilt, haben wir genau die Struktur des MP. Man beachte, dass nicht verlangt wird, dass p ATOM, vielmehr steckt in dem Ausdruck { p } q selbst schon eine Annahme, nämlich hinsichtlich der Verwendbarkeit von p zur Ableitung von q.

Anmerkung 3.2.2 Das Deduktionstheorem ist ein sogenanntes Metatheorem. Ein Metatheorem ist kein Theorem der Aussagenlogik, sondern über die Aussagenlogik. Das Deduktionstheorem beschreibt eine abstrakte Beziehung, die zwischen bestimmten Schlüssen der Aussagenlogik gilt.

Satz 3.2.2 Sei ≈ PROP2 eine Relation, für die gilt: p ≈ q iff p q und q p. ≈ ist eine Äquivalenzrelation.

Beweis:

1. ≈ ist reflexiv, da nach Axiom (1) für alle p PROP gilt: p p.

2. ≈ ist definitionsgemäß symmetrisch.

3. ≈ ist transitiv, denn: Aus p q und q p sowie q r und r q folgt:

sowie

 

Definition 3.2.7 sei PROP≈ die Menge der Äquivalenzklassen gemäß der Relation ≈. Ferner gelte für beliebige | p |, | q | PROP≈:

1. | p | ≤ | q | iff p q;

2. | p | | q | = | p q |;

3. | p | | q | = | p q |;

4. - | p | = | ¬ p | ist dass Komplement von | p |.

< PROP≈, ≤ > ist dann eine verbandsgeordnete Menge, < PROP≈, , , — > ist eine Boolesche Algebra und heißt Lindenbaumalgebra. Es gilt noch (wegen A 12 und A 13):

= | p | - | p | und = | p | - | p |.

Satz 3.2.3 | p | | q | = inf ( | p |, | q | ).

Beweis: Nach Axiom (7) gilt ( p q ) p bzw. ( p q ) q und somit | ( p q ) | ≤ | p |sowie | ( p q ) | ≤ | q |. Ferner, falls für ein beliebiges r gilt: | r | ≤ | p | und | r | ≤ | q |, so kann mit Hilfe von Axiom (8) deduziert werden, dass { r q, r p } r ( p q ) und somit | r | ≤ | ( p q ) |.

Entsprechend zeigt man, dass | p | | q | = sup ( | p |, | q | ).

Anmerkung 3.2.3 Der hier vorgestellte Kalkül für die Aussagenlogik entspricht nicht der Hilbertschen Forderung nach Einfachheit. Man kann Kalküle für die Aussagenlogik konstruieren, die mit erheblich weniger Axiomen auskommen. Hier ein Beispiel: Die Menge AXIOM enthalte folgende Axiome:

1. p ( q p ),

2. ( p ( q r )) (( p q ) ( p r )),

3. ( ¬ p ¬ q ) ( q p ).

Als Ableitungsregel fungiert wieder der MP. Wir können dann z. B. die Beziehung AXIOM p p beweisen, das heißt p p muss nicht eigens, wie oben geschehen, als Axiom eingeführt werden:

1. Axiom (1): p (( q p ) p )

2. Axiom (2): ( p (( q p ) p )) (( p ( q p )) ( p p ))

3. MP aus 1 und 2: ( p ( q p )) ( p p )

4. Axiom: (1): p ( q p )

5. MP aus 3 und 4: p p.
3.3 Die Semantik der Aussagenlogik zurück

Definition 3.3.1 Die Semantik der Aussagenlogik wird erklärt mittels einer Funktion || || : PROP , die folgendermaßen definiert ist:

1. Für alle p, q PROP gilt: || p || = 1 iff p ist "wahr" bzw. || p || = 0 iff p ist "falsch". Ferner:

2. || p q || = 1 iff || p || = 1 und || q || = 1.

3. || p q || iff || p ||= 1 oder || q || = 1.

4. || ¬ p || = 1 iff || p || = 0.

Anmerkung 3.3.1 Wir bemerken, dass die Funktion || || insbesondere für die Formel p q festlegt, dass

|| p q || = 1 iff || ¬ p q || = 1 iff p = 0 oder q = 1

Gilt nun in jedem Falle || p || = 0, so folgt hieraus, dass die Implikation || p q || wahr ist für jedes beliebige q. Dieser Eigenschaft der Implikation wegen spricht man ach von einem "Ex falso quodlibet" - "Aus einem Widerspruch folgt Beliebiges". Symbolisiert p z. B. den propositionalen Gehalt des Satzes "Alle Kühe können fliegen.", so kann aus diesem sicherlich falschen Satz jeder beliebige Satz gefolgert werden, etwa auch: "Wenn alle Kühe fliegen können, dann ist Napoleon der Kaiser von China." || || ordnet jeder solchen Implikation den Wahrheitswert 1 zu. Wir erkennen deutlich, dass die Algebraisierung der Logik gerade von den Bedeutungen der Sätze, die sie durch Aussagenvariablen ersetzt, sollständig absieht.

Die Bedeutung einer wohlgeformten Formel p resultiert aus der Anwendung von || || auf p. Die Bedeutung einer zusammengesetzten Formel ist eine Funktion der Bedeutungen der atomaren Formeln, welche durch die Blätter des Konstruktionsbaumes für p dargestellt werden. Hinter dieser Festlegung verbirgt sich ein rekursives Prinzip: Die Bedeutung eines Ausdrucks der Aussagenlogik ist eine Funktion der Bedeutungen seiner unmittelbaren Teilausdrücke, deren Bedeutungen wiederum auf der Basis desselben Prinzips bestimmt werden. Dieses Kompositionalitätsprinzip der Bedeutung haben wir weiter oben bereits kennen gelernt. Natürliche Sprachen "verletzen" dieses Prinzip in aller Regel: Die Bestimmung der Bedeutungen natürlichsprachlicher Äußerungen eruiert die Einbeziehung ihrer ko- und kontextuellen Einbettung. Die Zuordnung von Wahrheitswerten zu den atomaren Propositionen heißt Interpretation oder auch Belegung.

Die Frage, ob eine beliebige wohlgeformte Formel p PROP unter jeder möglichen Belegung ihrer atomaren Formeln mit Wahrheitswerten wahr ist, kann durch ein einfaches Entscheidungsverfahren beantwortet werden. Hierzu bedient man sich der Methode der Wahrheitstabellen. In einer Wahrheitstabelle werden für alle möglichen Interpretationen der atomaren Formeln die resultierenden Bedeutungen des Gesamtausdrucks bestimmt:

|| p || || q || || p q || || p q || || ¬ p || || p q || || p q ||
1 1 1 1 0 1 1
1 0 0 1 0 0 0
0 1 0 1 1 1 0
0 0 0 0 1 1 1

Tabelle 1 Wahrheitswerte für die elementaren Operationen der Aussagenlogik

Definition 3.3.2 Seien p, q PROP, dann gilt:

1. p heißt Tautologie iff || p || = 1 für jede Interpretation von p;

2. p heißt erfüllbar iff es gibt mindestens eine Interpretation von p, für die gilt: || p || = 1;

3. p heißt Kontradiktion iff || p || = 0 für jede Interpretation von p.

4. p ≡ q iff ( || p || = 1 || q || = 1 ). p und q heißen dann äquivalent. "" ist ein metasprachliches Zeichen und bedeutet das selbe wie "genau dann, wenn".

Beispiel 3.3.2 Es gilt:

1. Die de Morganschen Gesetze: ¬ ( p q ) ≡ ¬ p ¬ q und ¬ ( p q ) ≡ ¬ p ¬ q.

2. ¬ ¬ p ≡ p.

Anmerkung 3.3.2 Die de Morganschen Gesetze legen es nahe, die Semantik sämtlicher bisher eingeführter aussagenlogischer Funktoren allein mit Hilfe der Negation und Implikation zu definieren. So gilt etwa:

|| p q || = || ¬ ( p ¬ q ) ||

Dass diese Äquivalenzen unmittelbar auf den syntaktischen Ableitungsoperator " " übertragbar sind, folgt aus dem Vollständigkeitssatz (s. u.). Das heißt aber, dass die Semantik der Aussagenlogik vollständig mit Hilfe der beiden Funktoren "¬" und "" erklärt werden kann. Diese Sichtweise leitet zur folgenden Definition über:

Definition 3.3.3 Eine Belegung der Formeln aus PROP heißen Bewertung, wenn für alle p, q gilt:

1. || ¬ p || = 1 iff || p || = 0, und

2. || p q || = 1 iff p = 0 oder q = 1.

Anmerkung 3.3.3 Neben den bislang eingeführten Funktoren existiert noch eine Reihe anderer zweistelliger Funktoren (genau 24 = 16 verschiedene Funktoren, da genau 16 verschiedene vierstellige Permutationen der Elemente 0, 1 mit Wiederholung und Berücksichtigung der Reihenfolge existieren). Hier ist ihre vollständige Liste:

Matrix Zeichen Name inhaltliche Bedeutung
1111 Tautologie alles (gilt in jedem Falle)
1110 Disjunktion mindestens ein (nicht keins)
1101 ← Replikation Das andere nicht ohne das eine
1100 Präzedenz jedenfalls das eine (gleichgültig ob auch das andere)
1011 Implikation das eine nicht ohne das andere
1010 Postpedenz jedenfalls das andere (gleichgültig ob auch das eine)
1001 Äquivalenz nicht eins allein (beides oder keines)
1000 Konjunktion beides
0111 | Exklusion höchstens eins (nicht beides)
0110 Kontravalenz genau eins von beiden
0101 Postnonpedenz keinesfalls das andere
0100 Postsektion das eine ohne das andere
0011 Pränonpendenz keinesfalls das eine
0010 Präsektion das andere ohne das eine
0001 † Rejektion keines (beides nicht)
0000 Antilogie nichts (gilt in keinem Falle)

Tabelle 2 Die dyadischen Funktoren der Aussagenlogik.

Beispiel 3.3.2 p ¬ p ist einen Tautologie und p ¬ p ist eine Kontradiktion, denn es gilt:

|| p || || ¬ p || || p ¬ p || || p ¬ p ||
1 0 1 0
1 0 1 0
0 1 1 0
0 1 1 0

Beispiel 3.3.4 Der semantische Ableitungsoperator " ":

p q iff ( || p || = 1 ) ( || q || = 1 )

"" ist ein metasprachliches Symbol und bedeutet das selbe wie "daraus folgt, dass". Letztere Festlegung kann folgendermaßen gelesen werden: Jede Belegung die p wahr macht, macht auch q wahr, aber nicht unbedingt umgekehrt.

Definition 3.3.5 Cons ( p ) =def { q | p q }. Die Elemente von Cons ( p ) heißen Konsequenzen von p.

Wir wollen an dieser Stelle die Widerspruchsfreiheit und Vollständigkeit das eingeführten Aussagenkalküls beweisen.

Satz 3.3.1 Widerspruchsfreiheit: Alle auf der Grundlage der Menge AXIOM und des MP beweisbaren Sätze sind Tautologien. Vollständigkeit: Alle Tautologien sind auf der Grundlage der Menge AXIOM und des MP beweisbar. Mit anderen Worten:

p q iff p q

Beweis: Zunächst zur Widerspruchsfreiheit: Alle Axiome p AXIOM sind Tautologien (einfache Verifikation mit Hilfe der Methode der Wahrheitstafeln). Der MP überführt aber Tautologien wieder in Tautologien, denn falls p p eine Tautologie ist, so erfüllt jede Belegung, die p erfüllt, das heißt für die gilt: || p || = 1, auch q. Wenn aber p eine Tautologie ist, dann erfüllen alle Belegungen p und somit auch q.

Beweisidee Nun zur Vollständigkeit: Wir erinnern uns, dass eine Menge M von Formeln konsistent heißt, falls die Beziehung M p ¬ p nicht gilt. Mit M p ¬ p kann man wegen Axiom (12) jede Formel ableiten, also insbesondere auch ¬ ( p p ). Also gilt unter der Annahme M p ¬ p auch M ¬ ( p p ). Da nun aber für jede Menge P gilt: P p p, enthält M folglich einen Widerspruch, da || p p || = 1 für jede Belegung von p p. Wir betrachten nun folgende Hilfssätze, die wir der Reihe nach beweisen wollen:

1. Falls p, dann ist die Menge { ¬ p } konstant.

2. Zu jeder konsistenten Menge M gibt es eine maximal konsistente Menge M*, die alle Sätze aus M enthält.

3. Zu jeder maximal konsistenten Menge M* gibt es eine Bewertung, die genau die Sätze aus M* erfüllt.

Wird die Geltung dieser drei Sätze einmal vorausgesetzt, so kann die Vollständigkeit des Aussagenkalküls folgendermaßen (indirekt) gezeigt werden: Ist p nicht im Aussagenkalkül beweisbar, so ist nach Satz (1) die Menge { ¬ p } konsistent. Nach Satz (2) und (3) existiert dann eine Menge M* mit einer Bewertung, die die Sätze von M* erfüllt, also insbesondere ¬ p. Dann ist aber p aussagenlogisch falsch. Also gilt: Wenn p nicht im Aussagenkalkül beweisbar ist, dann ist p aussagenlogisch falsch. Wir wollen nun (der Übung halber) zumindest die ersten beiden Hilfssätze beweisen:

1. Angenommen es gilt: p. Wenn nun { ¬ p } inkonsistent wäre, so gäbe es einen Satz q, so dass { ¬ p } ¬ ( q q ). Mit dem Deduktionstheorem erhielte man hieraus: ¬ p ¬ ( q q ). Mit dem Axiom (3) und dem MP erhielte man schließlich { q q } p im Wiederspruch zur Annahme, p sei nicht beweisbar. Also muss { ¬ p } konsistent sein.

2. Ist M nun konsistent, so kann M* hieraus folgendermaßen generiert werden: Alle Sätze aus PROP werden der Reihe nach durchnummeriert, indem sie der Länge nach und bei gleicher Länge alphabetisch geordnet werden. Es ist dann M0 = M, Mn+1 entsteht für ein beliebiges n aus M dadurch, dass der n + 1te Satz aus PROP zu der Mengen hinzu genommen wird, falls die resultierende Menge Mn+1 konsistent bleibt. Andernfalls ist Mn+1 = Mn. Es gilt dann: M* = i{0,...,∞} Mi.

Offensichtlich ist M* die maximal konsistente Menge zu M. Ferner ist M* konsistent. Wäre M* nämlich inkonsistent, so gäbe es eine endliche Teilmenge von M*, die inkonsistent wäre (wir betrachten nur endlich lange Ableitungen). Dies widerspricht aber gerade der Konstruktion von M*.

Wir können diesem Vollständigkeitssatz ein grundlegendes Aufbauprinzip formaler Sprachen, wie etwa der Aussagenlogik, entnehmen, nämlich dass die Sätze einer solchen Sprache gerade so aufgebaut sind, dass ihre syntaktische Struktur ihrer semantischen Struktur entspricht, wobei syntaktische Regeln für das Schließen angegeben werden, die den inhaltlichen Folgerungsbeziehungen entsprechen.

 
3.4 Normalformen zurück

Definition 3.4.1 Eine wohlgeformte Formel ist in konjunktiver Normalform (KNF) bzw. in disjunktiver Normalform (DNF) iff sie von der Form

P1 ... Pi ... Pn

(bzw. von der Form ( P1 ... Pi ... Pn ) ist, wobei für alle i { 1, ..., n } gilt: Pi ist eine Disjunktion (bzw. Konjunktion) von Literalen.

Satz 3.4.1 Zu jeder wohlgeformten Formel p PROP existiert eine äquivalente Formel p' PROP, das heißt p ≡ p', in konjunktiver (bzw. disjunktiver) Normalform.

Wir wollen diesen Satz an dieser Stelle nicht beweisen, sondern vielmehr einen Algorithmus zur Ableitung der KNF (bzw. DNF) einer beliebigen Formel angeben:

1. Zunächst werden alle Funktoren, die weder " ", " " noch " ¬ " entsprechen gemäß ihren Definitionsgleichungen eliminiert (das heißt dass etwa p q durch ¬ p q ersetzt wird, usw.).

2. Weiterhin ersetzt man jede Formel der Bauart

¬ ¬ p durch p,

¬ ( p q ) durch ( ¬ p ¬ q ),

¬ ( p q ) durch ( ¬ p ¬ q ),

bis keine derartige Teilformel mehr durchkommt.

3. Man ersetzt weiterhin jedes Vorkommen einer Teilformel der Bauart (bzw. des dualen Vorkommens, i. e. bei Vertauschung von " " und " ")

p ( q r ) durch ( p q ) ( p r )

bis keine derartige Teilformel mehr vorkommt.

4. Man berücksichtigt die Eigenschaft der Kommutativität und Assoziativität der Funktoren " " und " ", falls nötig.

Beispiel 3.4.1 Überführung von ( p ( q r )) s in KNF:

( p ( q r )) s ≡ ( p ( ¬ q r )) s

                                 ≡ ¬ ( p ( ¬ q r )) s

                                 ≡ ( ¬ p ¬ ( ¬ q r )) s

                                 ≡ ( ¬ p ( q ¬ r )) s

                                 ≡ (( ¬ p q ) ( ¬ p ¬ r )) s

                                 ≡ (( ¬ p q ) s ) (( ¬ p ¬ r ) s

                                 ≡ (( ¬ p q s ) ( ¬ p ¬ r s ).