Logik: Aussagenlogik


EinleitungBearbeiten

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.

GeschichteBearbeiten

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.

AlphabetBearbeiten

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 ( ).

GrammatikBearbeiten

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.

BeispieleBearbeiten

Keine FormelnBearbeiten

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

FormelnBearbeiten

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  

KlammerersparnisBearbeiten

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, BewertungBearbeiten

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, FalsumBearbeiten

  ist Wahr zugeordnet,   ist Falsch zugeordnet.

NegationBearbeiten

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

KonjunktionBearbeiten

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

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

DisjunktionBearbeiten

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

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

SubjunktionBearbeiten

  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

BijunktionBearbeiten

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

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

ZusammenfassungBearbeiten

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    
  3.  
  4.  
  5.  
  6.  
  7.  

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 FolgerungBearbeiten

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.

SchreibweisenBearbeiten

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  . ✔

TautologienBearbeiten

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 AlgebraBearbeiten

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:

         
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 JunktorenBearbeiten

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

Definierbarkeit von JunktorenBearbeiten

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-OderBearbeiten

  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   oder   verwendet.

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

ShefferstrichBearbeiten

  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-NochBearbeiten

  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 JunktorenBearbeiten

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ülBearbeiten

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)"

DefinitionenBearbeiten

SequenzBearbeiten

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!

GrundregelnBearbeiten

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
   

AbleitbarkeitBearbeiten

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  .

StrukturregelnBearbeiten

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 RegelnBearbeiten

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 Subjunktion betrachten wir als definierten Junktor  . Für sie gelten folgende Regeln:

Regeln für die Subjunktion
   

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 Subjunktionsregel auf 1.
4.   Rechte Subjunktionsregel auf 2.
5.   Rechte Konjunktionsregel auf 3. und 4.
6.   Definition von  

Beweis beendet. ✔

KorrektheitBearbeiten

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 Voraussetzung 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 Bewertung die   erfüllt. Dann belegt   auch   und   mit Wahr, also gibt es nach Vorausstzung 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ändigkeitssatzBearbeiten

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 und fü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 Induktionsvoraussetzung 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   Falsch.
  • Gelte  . Nach Lemma 3 Punkt 7. und Induktionsvoraussetzung 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 SchnittregelBearbeiten

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 Voraussetzung, dass   eine Formel aus   erfüllt. Also gilt  . ✔

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

KompaktheitssatzBearbeiten

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. ↯

EinzelnachweiseBearbeiten

  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