Zum Inhalt springen

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

Aus Wikibooks

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:

.