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

Moderne Termlogik

Der Kalkül der Termlogik

Negation und indirekte Ableitungen

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 $P \land \neg P$ . 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 $A a b$ und $O a b$ bzw. $E a b$ und $I a b$ als sich jeweils widersprechende Paare auf und schreiben dafür

$\begin{matrix} C (A x y) & : = & O x y, & C (O x y) & : = & A x y \\ C (E x y) & : = & I x y, & C (I x y) & : = & E x y \end{matrix}$

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

Gilt

$Φ \cup {C (P)} ⊢ Q$ und $Φ \cup {C (P)} ⊢ C (Q)$ dann gilt: $Φ ⊢ P$ .

Im Kontext von Sequenzen entspricht dies der folgenden

Definition:

Gegeben eine Menge $Φ$ von Urteilen, die Annahmen (oder Voraussetzungen).
Eine endliche Folge (Sequenz) von Urteilen $< Φ_{0}, C (P), . . . ., ., Q, C (Q) >$ heisst "Indirekte Ableitung von $P$ aus $Φ$ ", wenn

$Φ_{0}$ eine Teilmenge von $Φ$ ist
alle Elemente, die nach $ℂ (P)$ kommen (d.h., die in der Sequenz rechts von $C (P)$ stehen; insbesondere die beiden letzten Element $Q$ und $C (Q)$ ) entweder Wiederholungen von Elementen aus $Φ_{0} \cup {C (p)}$ sind oder aus vorhergehenden Elementen durch eine der Regeln $R_{1}, R_{2}, R_{3}, R_{4}$ erzeugt werden.

In der häufigsten Form dieses Beweises verwendet man ein $Q$ , das in $Φ$ enthalten ist; dann ist $Φ \cup {C (P)} ⊢ Q$ auf jeden Fall erfüllt und muss nicht extra erwähnt werden; der Widerspruchsbeweis hat dann die Gestalt

Aus

$Q \in Φ$ und $Φ \cup {C (P)} ⊢ C (Q)$ ,

folgt

$Φ ⊢ P$ .

Wenn also aus der Aussagenmenge $Φ$ , zusammen mit der Aussage $C (P)$ , die Aussage $C (Q)$ folgt, so folgt $P$ aus $Φ$ .

Beispiel. Es soll $P = O b c$ aus $Φ = {A a b, O a c}$ hergeleitet werden.

$\begin{matrix} 1 . & A a b & A n n a h m e \\ 2 . & O a c & A n n a h m e & = Q \\ 3 . & A b c & A n n a h m e & = C (O b c) \\ 4 . & A a c & 1, 3 & R 3 & = C (Q) \\ 5 . & X & 2, 4 & W i d e r s p r u c h! \\ 6 . & O b c & 3, 5 & R e d u c t i o \end{matrix}$

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 $A a b, O a c ⊢ O b c$ . 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 $Φ ⊢ P$ eine direkte Ableitung von P aus $Φ$ . Dann gilt sicher (weil die Anzahl der Voraussetzungen vergrössert wird), auch (direkt)

$Φ \cup {C (P)} ⊢ P$

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

$Φ \cup {C (P)} ⊢ C (P)$

Nach der Definition der indirekten Ableitung ist also $P$ indirekt aus $Φ$ ableitbar:

$Φ ⊢ P$

.

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