Benutzer:Jürgen-Michael Glubrecht/Aussagenlogik

Aus Wikibooks
Zur Navigation springen Zur Suche springen

Vollständigkeit der Aussagenlogik[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.
  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