Mathematik: Logik: Aussagenlogik

Aus Wikibooks
Zur Navigation springen Zur Suche springen


Einleitung[Bearbeiten]

Die Aussagenlogik ist ein erster Schritt, die in der Mathematik – aber nicht nur da! – verwendeten logischen Schlussweisen zu rechtfertigen. Sind beispielsweise die Aussagen (1) und (2)

(1)  
(2)  

bereits bewiesen, so gilt auch die Aussage (3):

(3)  

(1) und (2) sind die Prämissen des Schlusses, (3) die Konklusion. Der Schluss selbst heisst Modus Ponens. Üblich sind auch andere Schreibweisen, zum Beispiel als sogenannte Schnittregel:

Ein anderes Beispiel ist das Beweisverfahren durch Widerspruch. Angenommen soll bewiesen werden. Man nimmt nun das Gegenteil an, also dass richtig sei. Daraus wird solange weiter geschlossen, bis man auf einen Widerspruch stößt, beispielsweise auf . Also muss doch richtig sein. Solche Beweise werden indirekte Beweise genannt.

Die Aussagenlogik ist ein einfaches System und die Grundlage für weitere logische Systeme, auch für solche, die in der Mathematik zwar behandelt, aber in der Regel nicht verwendet werden.

Geschichte[Bearbeiten]

Schon im 4. Jahrhundert vor Christus formulierte der griechische Philosoph Aristoteles den Satz vom Widerspruch, der besagt, dass eine Aussage und ihr Gegenteil nicht beide wahr sein können, und den Satz vom ausgeschlossenen Dritten, der besagt, dass eine beliebige Aussage oder ihre Verneinung wahr ist. Auch der indirekten Beweis findet sich in seinen Schriften. Chrysoppis von Soloi definierte im 3. Jahrhundert vor Christus Aussagen als Wahr oder Falsch und verwendete eine Semantik, die den heutigen Wahrheitstafeln entspricht. Die erste Formalisierung der Aussagenlogik entwickelte 1847 der englische Mathematiker George Boole. Den ersten Kalkül entwickelte 1879 Gottlob Frege. 1910 verwendete Bertrand Russell die heute noch übliche Notation.

Eine formale Sprache (Syntax)[Bearbeiten]

Eine formale Sprache besteht aus einem Alphabet und einer Grammatik. Das Alphabet bestimmt dabei, welche Zeichen Bestandteil der Sprache sind; es wird manchmal auch als Vokabular oder Lexikon bezeichnet. Die Grammatik bestimmt hingegen, wie die Zeichen zu Wörtern zusammengesetzt werden können.

Alphabet[Bearbeiten]

In der Aussagenlogik gibt es 3 Arten von Zeichen:

  1. Aussagenkonstante , , , ...
  2. Junktoren , , , , , ,
  3. Klammern ,

Die Junktoren heissen Verum (), Falsum (), Negation (), Konjunktion (), Disjunktion (), Subjunktion () und Bijunktion ().

Grammatik[Bearbeiten]

Genauso wenig wie in einer natürlichen Sprache wie Deutsch ergibt nicht jede beliebige Zeichenreihe ein korrektes Wort. Zeichenreihen, die nach den Regeln der Grammatik aufgebaut sind, heissen wohlgeformt. Die Wörter der Aussagenlogik werden Aussagen oder Formeln genannt. Damit eine Anordnung von Zeichen eine Formel in der Aussagenlogik bildet, muss sie nach den folgenden Regeln aufgebaut sein:

  1. Jede Aussagenkonstante ist eine Formel, und sind Formeln.
  2. Ist eine Formel, so ist auch eine Formel.
  3. Sind sowohl als auch Formeln, so sind auch , , und Formeln.

Es gibt keine weiteren Zeichenreihen, die Formeln sind, alle Formeln sind schrittweise nach diesen Regeln aufgebaut!

Die Anzahl der Formeln, die auf diese Weise gebildet werden können, hängt von der Anzahl der Aussagenkonstanten ab. Wenn diese höchstens abzählbar ist, gibt es auch nur abzählbar viele Formeln. Gibt es mehr, nämlich -viele mit , dann hat die Sprache -viele Formeln.

Beispiele[Bearbeiten]

Keine Formeln[Bearbeiten]

Die folgenden Zeichenreihen sind keine Formeln, denn sie lassen sich nicht nach den Regeln der Grammatik erzeugen:

, , , .
Zeichenreihe Begründung
nach Regel 2 muss auf das Zeichen eine Formel folgen
nach Regel 3 treten und immer zusammen mit Klammern auf
mehrere Aussagenkonstante können nicht hintereinander stehen
hier fehlen die Aussenklammern

Formeln[Bearbeiten]

Die folgenden Zeichenreihen sind Formeln:

, , , .

Formel Begründung
ist eine Aussagenkonstante, also nach Regel 1 eine Formel, Regel 2 liefert dann
und sind Aussagenkonstanten, Regel 2 liefert
, und sind Aussagenkonstanten, nach Regel 2 ist Formel und somit auch
, und sind Aussagenkonstanten, nach Regel 2 ist Formel und daher auch

Klammerersparnis[Bearbeiten]

Wie die letzten beiden Beispiele zeigen, sind Klammern erforderlich, um eindeutig festzustellen, wie eine Formel aufgebaut ist. Einige Klammern können aber eingespart werden, ohne die Lesbarkeit zu beeinträchtigen. Es werden folgende Regeln vereinbart:

  1. Aussenklammern können weggelassen werden,
  2. und binden stärker als und ,
  3. bindet stärker als .

Beispiele: nach 1 ist eine Abkürzung für die Formel , nach 1 und 2 lesen wir als .

Die Bedeutung (Semantik)[Bearbeiten]

Den Formeln der Aussagenlogik haben eine Bedeutung: sie sind Wahr oder Falsch. Dabei hängt die Bedeutung der mit Junktoren gebildeten Formeln von den beiden Teilformeln ab, aus denen sie gebildet ist. Da alle Formeln letztlich aus Aussagenkonstanten aufgebaut sind, hängt der Wahrheitswert einer Formel von den Wahrheitswerten ihrer Aussagenkonstanten ab. Eine Interpretation ordnet jeder Aussagenkonstante einen der beiden Wahrheitswerte Wahr oder Falsch zu. Eine solche Zuordnung wird auch Bewertung oder Modell genannt.

Interpretation, Bewertung[Bearbeiten]

Sei eine Zuordnung der Aussagenkonstanten zu den Werten Wahr (kurz: W) und Falsch (kurz: F) gegeben. Dann wird diese Zuordnung wie folgt auf die Formeln fortgesetzt:

Verum, Falsum[Bearbeiten]

ist Wahr zugeordnet, ist Falsch zugeordnet.

Negation[Bearbeiten]

Ist Wahr, so ist Falsch, ist Falsch so ist Wahr. Das lässt sich in einer sogenannten Wahrheitstafel wie folgt darstellen:

W F
F W

Konjunktion[Bearbeiten]

ist nur dann Wahr, wenn beide Teilformeln und wahr sind:

W W W
W F F
F W F
F F F

Disjunktion[Bearbeiten]

ist schon dann Wahr, wenn eine der beiden Teilformeln und Wahr ist:

W W W
W F W
F W W
F F F

Subjunktion[Bearbeiten]

ist Wahr, wenn die Formel Falsch ist oder wenn die Formel Wahr ist:

W W W
W F F
F W W
F F W

Bijunktion[Bearbeiten]

ist nur dann Wahr, wenn beide Formeln und den gleichen Wahrheitswert haben:

W W W
W F F
F W F
F F W

Zusammenfassung[Bearbeiten]

Die so erweiterte Zuordnung wird Interpretation oder Bewertung, in manchen Zusammenhängen auch Modell genannt.

Definition:

Eine Bewertung ordnet allen Formeln wie folgt einen Wahrheitswert aus zu:
  1. für alle Aussagkonstanten
  2.   und  

Redeweisen:

erfüllt eine Formel , wenn der Formel den Wert Wahr zuordnet. erfüllt die Formelmenge , wenn alle Formeln aus mit Wahr belegt. Eine andere Redeweise lautet: ist ein Modell von bzw. von .

widerlegt eine Formel , wenn die Formel mit Falsch bewertet. wird dann auch Gegenbeispiel für genannt.

Logische Folgerung[Bearbeiten]

Definition: Seien und Formelmengen.

Dann folgt aus , wenn für alle Bewertungen gilt: sind alle Formeln aus Wahr, dann ist wenigstens eine Formel aus Wahr.
Schreibweisen: (aus folgt ) und (aus folgt nicht ).

Damit gilt, muss es also eine Bewertung geben, die alle Formeln aus mit und alle Formeln aus mit belegt.

Schreibweisen[Bearbeiten]

Statt schreiben wir einfach , lassen also die Klammern weg.
Mit     ist     gemeint.
Ein wichtiger Spezialfall ist     (aus folgt ).
  steht für     ( ist die leere Menge).


Satz: Es gilt     genau dann, wenn  

Beweis:
Es gelte und es sei eine Bewertung, die alle Formeln aus Wahr macht.
Wenn die Formel mit Falsch bewertet, sind wir fertig, weil dann die Formel erfüllt. Wenn die Formel mit Wahr bewertet, ist es nach Voraussetzung die Formel oder eine Formel aus Wahr. Im zweiten Fall ist nichts weiter zu zeigen und im ersten Fall ist auch Wahr.

Gelte nun umgekehrt und erfülle alle Formeln aus .
Wenn eine Formel aus Wahr macht, sind wir fertig. Wenn die Formel Wahr macht, gibt es zwei Möglichkeiten: bewertet mit Falsch, dann ist alles klar. Bewertet die Formel mit Wahr, bewertet sie auch die Formel mit Wahr. Also gilt . ✔

Tautologien[Bearbeiten]

Eine Formel ist eine Tautologie, wenn sie bei allen Bewertungen Wahr ist, symbolisch: . Man sagt auch ist logisch wahr oder allgemeingültig.

Folgende Sätze gelten, wie man leicht mit Hilfe der Wahrheitstafeln nachprüft:

(Satz vom Widerspruch)
(Satz vom ausgeschlossenen Dritten)
(Modus ponens)
(Kontraposition)
(Ex falso Quodlibet, aus Falschem folgt alles)

Als Beispiel hier die Wahrheitstafel für die Kontraposition, die häufig für Beweise genutzt wird:

W W W W F W W F W
W F F W W F F F W
F W W W F W W W F
F W F W W F W W F
1 7 2 9 5 3 8 6 4

In der letzten Zeile ist die Reihenfolge angegeben, in der die Spalten ausgefüllt werden. Sie entspricht dem Aufbau der Formeln!

Boolesche Algebra[Bearbeiten]

Weitere Sätze für die Junktoren ,, , und :

(Idempotenz)
(Kommutativität)
(Assoziativität)
(Distributivität)
(De Morgansche Gesetze)
(Neutrales Element)
(Komplement)

Diese Sätze gelten ebenfalls, wenn man die Junktoren mit und mit vertauscht. Eine Struktur, in der diese Sätze gelten, wird Boolesche Algebra genannt. Die Potenzmenge ist die Menge aller Teilmengen der Grundmenge . Sie bildet zusammen mit , , , und (Grundmenge, leere Menge, Durchschnitt, Vereinigung und Komplement relativ zu ) ebenfalls eine Boolesche Algebra. Die Wirkung der Operatoren kann in sogenannten Venn-Diagrmmen veranschaulicht werden:

Venn1111.svg Venn0000.svg Venn0001.svg Venn0111.svg Venn1010.svg
Grundmenge Leere Menge Durchschnitt Vereinigung Komplement

In der letzten Zeile haben wir den entsprechenden Junktor notiert. Hat nur ein Element ist auch ein Modell der Aussagenlogik!

Weitere Junktoren[Bearbeiten]

Es gibt weitere Junktoren ausser denen, die wir bisher behandelt haben.

Definierbarkeit von Junktoren[Bearbeiten]

Die Junktoren unserer Sprache lassen sich teilweise aufeinander zurückführen. So gilt beispielsweise, wie man mit einer Wahrheitstafel leicht beweist:

Wir könnten also die Subjunktion zunächst aus der Sprache der Aussagenlogik weglassen und durch die folgende Definition wieder einführen:

Definition:

Auch die Bijunktion und sogar die Disjunktion sind mit Hilfe von und definierbar:

Definition:
Definition:

Hätten wir in unserer Sprache nur und , würden wir zunächst definieren, dann und schliesslich .

Es ist auch möglich, weitere Junktoren zu definieren, beispielsweise die umgekehrte Subjunktion :

Definition:

Entweder-Oder[Bearbeiten]

ist nur dann Wahr, wenn genau eine der beiden Teilformeln Wahr ist. Es wird daher auch Exklusives Oder genannt. Als Symbol für diesen Junktor wird auch verwendet.

W W F
W F W
F W W
F F F
Satz:
Satz:

Shefferstrich[Bearbeiten]

ist Wahr, wenn einer der beiden Teilformeln nicht Wahr ist. Dieser Junktor wird auch Nand (nicht und) genannt und mit dem Symbol bezeichnet.

W W F
W F W
F W W
F F W
Satz:

Der Shefferstrich wurde benannt nach dem amerikanischen Mathematiker Henry Maurice Sheffer, der zeigte, dass sich die anderen Junktoren mit Hilfe des Shefferstrich definieren lassen. Es gilt nämlich:

Damit lassen sich und definieren und somait auch die anderen Junktoren.

Weder-Noch[Bearbeiten]

ist Wahr, wenn beide Teilformeln Falsch ist. Dieser Junktor wird nach dem amerikanischen Mathematiker Charles S. Peirce Peircepfeil oder Nor (nicht oder) genannt.

W W F
W F F
F W F
F F W
Satz:

Auch mit dem Peircepfeil lassen sich und definieren:

Zweistellige Junktoren[Bearbeiten]

Junktoren verbinden unterschiedlich viele Teilformeln zu einer neuen Formel. Bei , , und sind es zwei, bei nur eine. Man sagt ein Junktor ist 2-stellig bzw. 1-stellig. und sind 0-stellig, sie haben überhaupt keine Teilformeln.

Es gibt vier verschiedene einstellige Junktoren. Von diesen ist nur die Negation in Spalte 3 von Interesse.

1 2 3 4
W W W F F
F W F W F
Junktor:

Die folgende Wahrheitstafel zeigt, dass es genau 16 verschiedene zweistellige Junktoren gibt. Soweit es ein gebräuchliches Symbol für einen Junktor gibt, ist es in der letzten Zeile eingetragen:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
W W W W W W W W W W F F F F F F F F
W F W W W W F F F F W W W W F F F F
F W W W F F W W F F W W F F W W F F
F F W F W F W F W F W F W F W F W F
Junktor:

Für die bisher nicht behandelten Junktoren geben wir im Folgenden eine Definition an. Dabei steht als Platzhalter für den Junktor, wenn kein Symbol angegeben ist.

Definition für Spalte 1:
Definition für Spalte 4:
Definition für Spalte 6:
Definition für Spalte 11:
Definition für Spalte 12:
Definition für Spalte 13:
Definition für Spalte 14:
Definition für Spalte 16:
Satz: Mit , und sind alle Junktoren definierbar.

Beweis: Sei ein beliebiger Junktor mit den Teilformeln ,, ..., . Für jede Zeile i, mit i = 1, ..., m, in denen wahr wird, bilden wir die Formel

, wobei

Dann definieren wir

Als Beispiel zeigen wir, wie das dreistellige Entweder-Oder definiert werden kann, das nur dann Wahr ist wenn genau eine der drei Teilformeln , oder Wahr ist:

Der Sequenzenkalkül[Bearbeiten]

Ein Kalkül ist ein formalisiertes Regelsystem, in dem aus Zeichenreihen mit Hilfe von Regeln weitere Zeichenreihen erzeugt werden können. Beispielsweise ist die eingangs definierte aussagenlogische Sprache ein Kalkül. Mit Hilfe der Grammatik werden die Zeichenreihen erzeugt, die Formeln sind. Wichtig dabei ist, dass die Regeln ohne Kenntnis irgend einer Bedeutung angewendet werden können. Die Anwendung einer Regel erfolgt rein schematisch und sollte auch von einer Maschine durchgeführt werden können.

Auch die Ermittlung der Wahrheitswerte von mit Junktoren zusammengesetzten Formeln mit Hilfe von Wahrheitstafeln ist ein Kalkül.

In diesem Abschnitt werden wir einen Kalkül vorstellen, mit dem die gültigen Formeln der Aussagenlogik erzeugt werden können. Er wurde 1934 vom deutschen Mathematiker Gerhard Gentzen entwickelt, der ihn als "Kalkül des natürlichen Schliessens" bezeichnete. Er wird Sequenzenkalkül genannt, weil die Zeichenreihen ursprünglich als Folgen von Formeln notiert werden.

Im Weiteren legen wir eine Sprache mit -vielen Formeln zu Grunde und betrachten die Implikation und die Bijunktion als definierte Junktoren, siehe Abschnitt "Eine formale Sprache (Syntax)"

Definitionen[Bearbeiten]

Sequenz[Bearbeiten]

Definition: Seien und Formelmengen.

Dann nennen wir eine Sequenz oder Beweiszeile.

Schreibweisen

Statt schreiben wir einfach , lassen also die Klammern weg.
Mit     ist     gemeint.
Ein wichtiger Spezialfall ist     (aus folgt ).
  steht für     ( ist die leere Menge).

Anmerkung: Die Ähnlichkeit von und ist kein Zufall, sondern beabsichtigt!

Grundregeln[Bearbeiten]

Der Kalkül für die Aussagenlogik hat folgende Regeln:

Annahmenregel
Regeln für Verum und Falsum
Regeln für die Negation
Regeln für die Konjunktion
Regeln für die Disjunktion

Ableitbarkeit[Bearbeiten]

Definition: Eine Sequenz heisst ableitbar, wenn es eine endliche Folge von Sequenzen

1.  
2.  
3.  
n.  

mit endlichen Formelmengen und gibt, bei der jede Zeile aus den vorangehenden Zeilen durch eine Regel entsteht und für die letzte Zeile und gilt.
Eine solche Folge heisst ein Beweis für .

Strukturregeln[Bearbeiten]

Nach Definition von sind und Mengen. Daraus ergeben sich einige Regeln, die Strukturregeln genannt werden. Von diesen Regeln werden wir im Weiteren stillschweigend Gebrauch machen.

Satz:

Verdünnungsregel

Beweis: Nach Voraussetzung gibt es eine Ableitung für . In dieser Ableitung können wir überall durch ersetzen und erhalten so . Die andere Regel wird entsprechend bewiesen. ✔

Satz:

Vertauschung

Beweis: Links von steht immer dieselbe Menge . Im anderen Fall steht rechts .✔ Satz:

Wiederholung

Beweis: Links von steht immer dieselbe Menge . Im anderen Fall steht rechts .✔

Weitere Regeln[Bearbeiten]

Wir zeigen einige Regeln, die aus den gegebenen Regeln abgeleitet werden können. Auch diese Regeln können dann in weiteren Beweisen verwendet werden, ohne dass die Menge der ableitbaren Sequenzen zu vergrössern.

Die Implikation betrachten wir als definierten Junktor . Für sie gelten folgende Regeln:

Regeln für die Implikation

Beweis:

1. Voraussetzung
2. Voraussetzung
3. linke Negationsregel
4. linke Disjunktionsregel auf 3. und 1.
5. Definition von
1. Voraussetzung
2. rechte Negationsregel
3. rechte Disjunktionssregel
4. Definition von

Beweis beendet. ✔


Die Bijunktion betrachten wir als definierten Junktor .

Für sie gelten folgende Regeln:

Regeln für die Bijunktion

Beweis:

1. Voraussetzung
2. Voraussetzung
3. Annahmenregel
4. Linke Subjunktionsregel auf 3. und 2.
5. Annahmenregel
6. Linke Subjunktionsregel auf 1. und 5.
7. Linke Subjunktionsregel auf 6. und 4.
8. Linke Konjunktionsregel auf 7.
9. Definition von
1. Voraussetzung
2. Voraussetzung
3. Rechte Implikationsregel auf 1.
4. Rechte Implikationsregel auf 2.
5. Rechte Konjunktionsregel auf 3. und 4.
6. Definition von

Beweis beendet. ✔

Korrektheit[Bearbeiten]

Definition: Eine Sequenz heisst korrekt, wenn auch gilt.

Satz: Ist     ableitbar, so gilt   .

Beweis:

Wir führen den Beweis durch Induktion über den Aufbau der Grundregeln für den Sequenzenkalkül.
Induktionsanfang: Die Annahmenregel ist offensichtlich korrekt, also: . Da alle Bewertungen die Formel mit Falsch und mit Wahr bewerten sind auch die Regeln für Falsum und Verum korrekt: und
Induktionsschluss: Zu zeigen ist, dass die Regeln für die Junktoren , und die Korrektheit erhalten: sind die Sequenzen korrekt, so auch die erzeugte Sequenz.
Negation:
Gelte nun und sei eine beliebige Bewertung die erfüllt. Dann erfüllt auch und belegt mit Falsch. Nach Vorraussetzung gibt es daher eine Formel aus , die mit Wahr belegt. Das kann aber nicht sein, also ist aus . Das zeigt .
Sei nun und eine Bewertung die erfüllt. Belegt mit Falsch, sind wir fertig, denn dann belegt mit Wahr. Wenn mit Wahr bewertet, gibt es nach Voraussetzung eine Formel aus die mit Wahr bewertet. Insgesamt gilt .
Konjunktion:
Sei nun und eine Belegung die erfüllt. Dann belegt auch und mit Wahr, also gibt es nach Vorrausstzung eine Formel aus die mit Wahr belegt. Das zeigt .
Sei nun und und erfüllt . Erfüllt eine Formel aus ist nichts mehr zu zeigen. Ist das nicht der Fall, erfüllt und und somit auch . Also ist .
Disjunktion:
Gelte nun und und erfüllt , Dann erfüllt oder . In beiden Fällen ergibt sich mit der Voraussetzung, dass es eine Formel aus gibt, die von erfüllt wird. Daher gilt .
Sei schliesslich und erfülle . Dann folgt aus der Voraussetzung, dass , oder eine Formel aus erfüllt. erfüllt aber dann auch eine Formel aus und somit gilt . ✔

Der Vollständigkeitssatz[Bearbeiten]

Die Korrektheit des Kalküls besagt, dass nur gültige Sequenzen abgeleitet werden können. Von grosser Bedeutung ist, dass auf diese Weise alle logischen Folgerungen abgeleitet werden können! Es gilt also auch die Umkehrung der Korrektheit:

Satz: Gilt   ,   so ist     ableitbar.

Das Ableiten ist ein maschinell prüfbares Verfahren, das in endlich vielen Schritten aus endlich vielen Formeln eine korrekte Folgerung erzeugt. Das ist genau das, was in der Mathematik als Beweis gilt. Der Satz besagt also, dass sich alle logischen Folgerungen auf diese Weise beweisen lassen.

Wir beweisen den Satz nach einer Idee des amerikanischen Logikers Leon Henkin. Dazu nehmen wir an, dass gilt und konstruieren ein Bewertung , die zeigt: macht also alle Formeln aus wahr und alle Formeln aus falsch. Wir vergrössern und zu und , so dass diese maximal sind aber weiterhin gilt. Mit diesen Formelmengen wird dann die Bewertung definiert.[1]

Beweis:

Wir zeigen die Kontraposition. Sei also , d.h. aus ist nicht ableitbar, und die Mächtigkeit der Sprache. Weiterhin sei mit eine Aufzählung aller Formeln. Wir definieren rekursiv und für .

  • und .
  • Für Limeszahlen sei: und .
  • Für Nachfolgerzahlen werden drei Fälle unterschieden:
    • wenn , dann und
    • wenn und , dann und
    • wenn und , dann und

Wir werden später sehen, dass der letzte Fall nicht auftritt und setzen nun: und

Lemma 1: Es gilt   .

Beweis: Durch Induktion über folgt: für alle . Für gilt das nach Voraussetzung undfür Nachfolgerzahlen nach Konstruktion. Gälte für Limeszahlen , dann gälte für ein , denn für die Ableitung werden nur endlich viele Formeln aus und benötigt. Das widerspricht aber der Induktionsvoraussetzung für .

Insbesondere gilt also .✔

Lemma 2: und sind maximal, d.h. es gilt für eine beliebige Formel :
    •   und
    • .

Beweis: Die eine Richtung () folgt mit der Nichtableitbarkeit nach Lemma 1.

Sei und der Index von in der Aufzählung aller Formeln. Dann ist , sonst wäre . Also gilt .

Sei nun . Ist , dann folgt mit der Annahmenregel . Sei also und der Index von . Dann ist und , sonst wäre . Also gilt auch in diesem Fall . ✔

Lemma 3: Abgeschlossenheit von und nach unten, d.h. für beliebige Formeln und gilt:
    • 1.  
    • 2.   und
    • 3.   wenn , dann
    • 4.   wenn , dann
    • 5.   wenn , dann und
    • 6.   wenn , dann oder
    • 7.   wenn , dann oder
    • 8.   wenn , dann und

Beweis:

  1. folgt mit der Annahmenregel und Lemma 1.
  2. ergibt sich mit den Regeln für Verum und Falsum, sowie Lemma 1.
  3. Sei . Mit Lemma 2 folgt und mit der Linken Negationsregel . Erneut mit Lemma 2 folgt .
  4. Sei . Mit Lemma 2 folgt und mit der Rechten Negationsregel . Erneut mit Lemma 2 folgt .
  5. Sei oder . Mit Lemma 2 folgt oder , also mit Verdünnung auch . Mit der Linken Konjunktionsregel folgt und wieder mit Lemma 2: .
  6. Sei und . Mit Lemma 2 folgt und . Mit der Rechten Konjunktionsregel folgt und erneut mit Lemma 2: .
  7. Sei und . Mit Lemma 2 folgt und . Mit der Linken Disjunktionsregel folgt und mit Lemma 2; .
  8. Sei oder . Mit Lemma 2 folgt oder und mit Verdünnng . Mit der Rechten Disjunktionsregel folgt und mit Lemma 2: .

Damit ist der Beweis beendet. ✔

Die eben gezeigten Eigenschaften reichen aus, um eine Bewertung zu definieren, die beweist:.

Definition der Bewertung :

Für alle Aussagenkonstanten sei Wahr genau dann, wenn .
Lemma 4: Für alle Formeln gilt:              
    • wenn , dann ist Wahr,
    • wenn , dann ist Falsch.

Beweis durch Induktion über den Aufbau der Formeln:

  • Für Aussagenkonstanten gilt die Behauptung nach Definition von .
  • Für Verum und Falsum gilt die Behauptung wegen Lemma 3 Punkt 2.
  • Gelte . Dann gilt nach Lemma 3 Punkt 3. und nach Induktionsvoraussetzung ist Falsch. Also ist Wahr.
    Ist , ist nach Lemma 3 Punkt 4. und somit Wahr. Also ist Falsch.
  • Gelte . Nach Lemma 3 Punkt 5. und Induktionsvorraussetzung sind dann Wahr und Wahr. Also ist auch Wahr.
    Ist , ist nach Lemma 3 Punkt 6. und der Induktionsvoraussetzung Falsch oder Falsch. Damit ist auch Wahr.
  • Gelte . Nach Lemma 3 Punkt 7. und Induktionsvorraussetzung ist dann Wahr oder Wahr. Also ist auch Wahr.
    Ist , sind nach Lemma 3 Punkt 8. und der Induktionsvoraussetzung Falsch und Falsch. Daher ist auch Falsch.

Damit ist Lemma 4 bewiesen. ✔

Da ja und gilt auch:

beweist .

Zusammen mit der Korrektheit des Kalküls gilt also:

Vollständigkeisatz: ist ableitbar genau dann, wenn gilt.

Die Schnittregel[Bearbeiten]

Eine Folgerung aus der Vollständigkeit unseres Kalküls ist, das wir die Schnittregel nutzen können, ohne die Menge der logischen Folgerungen zu vergrössern. Die Schnittregel erlaubt es, Formeln "herauszuschneiden", die in der Schlusszeile nicht mehr auftauchen:

Schnittregel

Beweis: Gelte also und und efülle alle Formeln aus . Dann erfüllt wegen der ersten Voraussetzung oder eine Formel aus . Im zweiten Fall sind wir fertig. Erfüllt die Formel , so folgt aus der zweiten Vorraussetzung, dass eine Formel aus erfüllt. Also gilt . ✔

In der Mathematik wird die Schnittregel häufig in der folgenden Form verwendet: .

Kompaktheitssatz[Bearbeiten]

Kompaktheitssatz: Eine Formelmenge ist genau dann erfüllbar, wenn jede endliche Teilmenge von erfüllbar ist.

Beweis: Die Richtung "" ist trivial, denn wenn alle Formeln von erfüllt, dann natürlich auch alle endlichen Teilmengen von .

Für die Richtung "" nehmen wir an, dass alle endlichen Teilmengen von erfüllbar sind, aber selbst nicht. Dann gilt und nach dem Vollständigkeitssatz folgt . Für den Beweis werden aber nur endlich viele Formeln aus benötigt, also gibt es eine endliche Teilmenge mit: und ist nicht erfüllbar. ↯

Einzelnachweise[Bearbeiten]

  1. Jürgen-Michael Glubrecht: Ein Vollständigkeitsbeweis für schnittfreie Kalküle mit der Maximalisierungsmethode von Henkin, im Archiv für mathematische Logik und Grundlagenforschung Band 22 (1982) S. 159 - 166