Moderne Termlogik: Termlogik und Prädikatenkalkül: Die Übersetzungstechnik

Moderne Termlogik

Termlogik und Prädikatenkalkül

Die Übersetzungstechnik

Es ist, wie schon im vorigen Abschnitt angedeutet, naheliegend, die Forderung der Existenz von Elementen $α$ mit der Eigenschaft $a (α)$ explizit in die Definition von $A a b$ mit aufzunehmen. So erhält man die Übersetzung

$A a b : = \forall α (a (α) \Rightarrow b (α)) \land \exists α (a (α))$

Es lässt sich nun zeigen, dass bei dieser Definition die gewünschte Beziehung

$A a b ⊢ I b a$

gilt; leider hat diese Änderung aber zur Folge, dass andere, bei der ursprünglichen Interpretation gültigen Beziehungen nicht mehr richtig sind - so z.B. die Beziehung

$C (A a b) = O a b$ .

Um diese Beziehung zu "retten", muss auch die Definition von $O a b$ geändert werden, und das hat wieder Konsequenzen, die momentan unabsehbar sind.

Wir werden nun den Vorgang der Übersetzung der Urteile in die Prädikatenlogik allgemein behandeln.

Dazu verwenden wir elementare Ergebnisse aus der Prädikatenlogik. Um zu einer einheitlichen Dartsekkung der vier Urteilsformen zu kommen, schreiben wir die Urteile, die wir im vorigen Abschnitt definiert haben, in einer normierten Gestalt. Wir benutzen dabei die Tatsache, dass sich der Allquantor $\forall$ durch den Existenzquantor $\exists$ ausdrücken lässt:

$\forall x F x = \neg \exists x (\neg F x)$

Zur Schreibweise: Im Rahmen der Behandlung der Termlogik im Rahmen der Prädikatenlogik ist es günstiger, statt der Bezeichnung $a$ und $b$ für die Terme die Prädikatenvariablen $S$ und $P$ zu verwenden. Wir schreiben also

$A (S, P)$ statt $A a b$ usw.

Wir führen außerdem die folgenden Abkürzungen ein:

$\begin{matrix} p & = & \exists x (S x \land P x) \\ q & = & \exists x (S x \land \neg P x) \\ r & = & \exists x (\neg S x \land P x) \\ s & = & \exists x (\neg S x \land \neg P x) \end{matrix}$

Aus diesen vier Bausteinen können 16 Aussageformen der folgenden Gestalt gebildet werden:

$π \land κ \land ρ \land σ$ ,

wobei

$π \in {p, \neg q}, κ \in {q, \neg q}, ρ \in {r, \neg r}, σ \in {s, \neg s} .$

Hiermit lassen sich nun die vier ursprünglichen Urteilsformen wie folgt darstellen:

$\begin{matrix} A a b & = & A (S, P) & = & \forall x (S x \Rightarrow P x) & = & \neg \exists x (S x \land \neg P x) & = & \neg q \\ E a b & = & E (S, P) & = & \neg \exists x (S x \land P x) & = & \neg p \\ I a b & = & I (S, P) & = & \exists x (S x \land P x) & = & p \\ O a b & = & O (S, P) & = & \neg \forall x (S x \Rightarrow P x) & = & \exists x (S x \land \neg P x) & = & q \end{matrix}$

Unter einer Disjunktiven Normalform verstehen wir die Disjunktion von Ausdrücken (ohne Wiederholung) der Gestalt

$π \land κ \land ρ \land σ$ ,

wobei

$π \in {p, \neg q}, κ \in {q, \neg q}, ρ \in {r, \neg r}, σ \in {s, \neg s} .$

So ist z.B.

$(p \land \neg q \land r \land s) \lor (\neg p \land \neg q \land r \land s) \lor (p \land \neg q \land \neg r \land s)$

so eine Normalform.

Es gibt daher exakt $2^{16}$ unterschiedliche Normalformen.

Definition: Unter einer monadischen Transkription der Aristotelischen Syllogistik verstehen wir eine Menge von vier beliebig gewählten geschlossenen Formeln, die zusammen genau zwei monadische Prädikatsymbole S und P enthalten. Wir bezeichnen diese Formeln mit A(S,P), E(S,P), I(S,P) und O(S,P).

Theorem von Behmann^[1]: Sei F eine geschlossene Formel der monadischen Prädikatenlogik mit zwei Prädikaten S und P. Dann kann F effektiv in eine equivalente Formel F1 in disjunktiver Normalform (DNF) transformiert werden.

Ein Beispiel. Wir wollen die am Anfang dieses Abschnitts aufgeführte Formel in die Disjunktive Normalform transformieren. Wir schreiben sie zunächst in der Form

$\forall x (S x \Rightarrow P x) \land \exists x (S x) = \neg \exists x (S x \land \neg P x)) \land \exists x (S x)$

Der erste Teil ist einfach; er entspricht dem Term $\neg q$ . Der zweite Teil, $\exists x (S x)$ lässt sich wie folgt umschreiben:

$\exists x (S x) = \exists x (S x \land P x) \lor \exists x (S x \land \neg P x) = p \lor \neg q$

.

Insgesamt erhält man also

$\forall x (S x \Rightarrow P x) \land \exists x (S x) = \neg \exists x (S x \land \neg P x)) \land \exists x (S x) = \neg q \land (p \lor \neg q) = p \land \neg q .$

Für die Normalform fehlen noch die Terme $r$ und $s$ , die man dadurch berücksichtigt, dass man die folgende Disjunktion (die stets wahr ist), hinzufügt:

$(r \land s) \lor (r \land \neg s) \lor (\neg r \land s) \lor (\neg r \land \neg s)$

Insgesamt erhält man damit die Normalform

$(p \land \neg q) \lor ((r \land s) \lor (r \land \neg s) \lor (\neg r \land s) \lor (\neg r \land \neg s)) = (p \land \neg q \land r \land s) \lor (p \land \neg q \land r \land \neg s) \lor (p \land \neg q \land \neg r \land s) \lor (p \land \neg q \land \neg r \land \neg s)$

Alle möglichen Formalisierungen der Termlogik mit Hilfe der Prädikatnlogik erhält man auf die folgende Weise:

Man wählt 4 unterschiedliche Disjunktive Normalformen $D_{1} (p, q, r, s), D_{2} (p, q, r, s), D_{3} (p, q, r, s), D_{4} (p, q, r, s)$
Man definiert die vier Urteilsformen durch

$\begin{matrix} A (S, P) & = & D_{1} (p, q, r, s) \\ E (S, P) & = & D_{2} (p, q, r, s) \\ I (S, P) & = & D_{3} (p, q, r, s) \\ O (S, P) & = & D_{4} (p, q, r, s) \end{matrix}$

Danach kann man untersuchen, ob die bzw. welche Gesetze der Termlogik erfüllt sind. So muss man z.B. prüfen, ob

$A (S, P) \Rightarrow I (P, S)$

eine Tautologie ist; d.h. ob die Implikation

$D_{1} (p, q, r, s) \Rightarrow D_{3} (p, q, r, s)$

gilt. Dies ist für die klassische, auf Frege zurückgehende Formalisierung, bei der

$D_{1} (p, q, r, s) = - q, D_{3} (p, q, r, s) = p$

gilt, z.B. nicht richtig.

Wie wir gesehen haben, ist bei der am Anfang dieses Abschnitts aufgeführten Interpretation

$D_{1} (p, q, r, s) = p \land \neg q, D_{3} (p, q, r, s) = p,$

also ist hier

$A (S, P) \Rightarrow I (P, S)$

erfüllt.

↑ H. Behmann. Beiträge zur Algebra der Logik, insbesondere zum Entscheidungsproblem. Mathematische Annalen, 86:342–372, 1922.

[1] H. Behmann. Beiträge zur Algebra der Logik, insbesondere zum Entscheidungsproblem. Mathematische Annalen, 86:342–372, 1922.

[1]

Moderne Termlogik: Termlogik und Prädikatenkalkül: Die Übersetzungstechnik