Moderne Termlogik: Der Kalkül der Termlogik: Negation und indirekte Ableitungen

Moderne Termlogik Bearbeiten

Der Kalkül der Termlogik Bearbeiten

Negation und indirekte Ableitungen Bearbeiten

Die Methode des indirekten Beweises geht auf Aristoteles zurück. Die Idee dabei ist, aus einer Annahme einen Widerspruch herzuleiten; wenn das gelingt, ist das Gegenteil dieser Annahme richtig.

Bevor wir dieses Vorgehen in eine formal handhabbare Form fassen, müssen wir die Begriffe Widerspruch und Gegenteil definieren. In der Aussagenlogik ist ein Widerspruch (oder Kontradiktion) eine Aussage, die unter keinen Umständen wahr sein kann; typisch dafür ist  . Der Widerspruch ist also das logische Gegenstück zur Tautologie, also einer Aussage, die unter allen Umständen wahr ist.

Da wir im Kalkül der Termlogik bisher kein Negationszeichen eingeführt haben (und es für alles Folgende auch nicht benötigen), müssen wir hier anders vorgehen: Wir fassen die Urteile   und   bzw.   und   als sich jeweils widersprechende Paare auf und schreiben dafür

 

Die Methode des indirekten Beweises (reductio ad absurdum) geht jetzt folgendermassen. Um aus einer Menge   von Annahmen eine Folgerung   abzuleiten, nehmen wir das Gegenteil, nämlich   mit zu den Annahmen hinzu. Dann versuchen wir, aus dieser so erweiterten Menge von Annahmen mittels direkter Ableitung einen Widerspruch herzuleiten.

Gilt

  und   dann gilt:  .

Im Kontext von Sequenzen entspricht dies der folgenden

Definition:

  • Gegeben eine Menge   von Urteilen, die Annahmen (oder Voraussetzungen).
  • Eine endliche Folge (Sequenz) von Urteilen   heisst "Indirekte Ableitung von   aus  ", wenn
  1.   eine Teilmenge von   ist
  2. alle Elemente, die nach   kommen (d.h., die in der Sequenz rechts von   stehen; insbesondere die beiden letzten Element   und  ) entweder Wiederholungen von Elementen aus   sind oder aus vorhergehenden Elementen durch eine der Regeln   erzeugt werden.


In der häufigsten Form dieses Beweises verwendet man ein  , das in   enthalten ist; dann ist   auf jeden Fall erfüllt und muss nicht extra erwähnt werden; der Widerspruchsbeweis hat dann die Gestalt

Aus

  und  ,

folgt

 .

Wenn also aus der Aussagenmenge  , zusammen mit der Aussage  , die Aussage   folgt, so folgt   aus   .

  • Beispiel. Es soll   aus   hergeleitet werden.

 

Dabei zeigt das X in Zeile 5 an, dass ein Widerspruch auftritt; hier in Gestalt der Zeilen 2 und 4.

Für die Folgerung durch indirekte Ableitung gibt es kein neues Symbol, sondern es wird auch   verwendet. Nach der indirekten Ableitung im vorigen Beispiel gilt also  . Die Begründung für die Verwendung ein und des selben Symbols liegt in der folgenden Tatsache:


Satz: Jede direkte Folgerung kann auch durch indirekte Ableitung gewonnen werden.

Beweis: Sei   eine direkte Ableitung von P aus  . Dann gilt sicher (weil die Anzahl der Voraussetzungen vergrössert wird), auch (direkt)

 

Ausserdem (weil C(P) unter den Voraussetzungen steht), gilt (wieder direkt)

 

Nach der Definition der indirekten Ableitung ist also   indirekt aus   ableitbar:

 

.