Logik: Prädikatenlogik

Vorbemerkungen

Die Prädikatenlogik ist eine Erweiterung der Aussagenlogik. In der Aussagenlogik werden mit Junktoren zusammengesetzte Aussagen betrachtet. Die Aussagen selbst werden nicht näher untersucht. Das erfolgt nun in der Prädikatenlogik: wie werden Aussagen gebildet? Dazu drei einfache Beispiele:

(1)   $3𝗂𝗌𝗍𝖾𝗂𝗇𝖾𝖯𝗋𝗂𝗆𝗓𝖺𝗁𝗅\mathsf{.}$

(2)   $𝖥𝗋𝗂𝗍𝗓𝗂𝗌𝗍𝗀𝗋\ddot{𝗈}𝗌𝗌𝖾𝗋𝖺𝗅𝗌𝖤𝗋𝗇𝖺\mathsf{.}$

(3)   $7\mathit{+}𝒙\mathit{=}5$

In diesen Aussagen gibt es sogenannte Individuenkonstante nämlich: $3,5,7$, $𝖥𝗋𝗂𝗍𝗓$ und $𝖤𝗋𝗇𝖺$. Das sind Namen, die bestimmte Zahlen bzw. Menschen oder Gegenstände bezeichnen. In der Prädikatenlogik werden diese Objekte Individuen genannt. Im Beispiel (3) kommt die Variable $x$ vor. Variable bezeichnen auch Individuen, aber es ist nicht festgelegt welche das genau sein sollen. Üblich ist deshalb auch der Ausdruck Unbekannte. Des Weiteren kommen Prädikate vor: $\mathsf{\dots }𝗂𝗌𝗍𝖯𝗋𝗂𝗆𝗓𝖺𝗁𝗅$ ist ein Prädikat, ebenso $\mathsf{\dots }𝗂𝗌𝗍𝗀𝗋\ddot{𝗈}𝗌𝗌𝖾𝗋𝖺𝗅𝗌\mathsf{\dots }$. Prädikate bezeichnen Eigenschaften die auf Individuen zutreffen können oder nicht. Zu Prädikaten gehören Leerstellen, die mit drei Punkten $\dots$ gekennzeichnet sind. Die Anzahl der Leerstellen ist die Stellenzahl des Prädikats.

Schliesslich kommt im Beispiel (3) das Funktionszeichen $+$ und das Gleichheitszeichen $=$ vor. Wie die Prädikate haben die Funktionszeichen Leerstellen, in die Namen für Individuen eingesetzt werden. Funktionszeichen haben also auch eine Stellenzahl. Aber während die Prädikate mit den eingesetzten Namen Aussagen ergeben, liefern die Funktionszeichen mit den Namen wieder einen Namen für ein Individuum. Das Gleicheitszeichen verbindet ebenfalls zwei Namen und macht daraus eine Aussage.

Aber das ist noch nicht alles: zur Prädikatenlogik gehören auch noch die Quantoren, und zwar der Allquantor $\mathrm{\forall }$ (für alle ...) und der Existenzquantor $\mathrm{\exists }$ (es gibt ...). Beispiele:

(4)   $𝖠𝗅𝗅𝖾𝖬𝖾𝗇𝗌𝖼𝗁𝖾𝗇𝗌𝗂𝗇𝖽𝗌𝗍𝖾𝗋𝖻𝗅𝗂𝖼𝗁\mathsf{.}$

(5)   $\mathrm{\exists }𝒙\mathit{(}7\mathit{+}𝒙\mathit{=}5\mathit{)}$

Geschichte

Entwickelt wurde die Prädikatenlogik von Gottlob Frege und Charles Sanders Peirce unabhängig voneinander. Frege entwickelte sein System der Prädikatenlogik in der 1879 erschienenen Begriffsschrift. Freges Notation sah damals sehr anders aus als die heutige, sie bestand aus mit Linien verbundenen Prädikaten, die auch abzweigen konnten, außerdem gab es in seiner Notaion weniger Junktoren und keinen Existenzquantor, trotzdem konnte man mit seiner Prädikatenlogik alles sagen, was man auch mit der modernen ausdrücken kann, auch wenn es teilweise etwas umständlicher ist. Peirces Notation ähnelte aber schon der modernen.

Eine formale Sprache

Für die Prädikatenlogik erweitern wir die Sprache der Aussagenlogik.

Alphabet

In der Prädikatenlogik gibt es 9 Arten von Zeichen:

1. Aussagenkonstante $\alpha$, $\beta$, $\gamma$, ...
2. Junktoren $\mathrm{\top }$, $\mathrm{\perp }$, $\mathrm{\neg }$, $\wedge$, $\vee$, $\to$, $\leftrightarrow$
3. Klammern $($, $)$
4. Individuenkonstanten $a$, $b$, $c$, ...
5. Prädikate $P$, $Q$, $R$, ...
6. Funktionszeichen $F$, $G$, $H$, ...
7. Gleichheitszeichen $=$
8. Variable $x$, $y$, $z$, ...
9. Quantoren $\mathrm{\forall }$, $\mathrm{\exists }$

Die ersten drei Arten von Zeichen entsprechen denen der Aussagenlogik.

Grammatik

In der Prädikatenlogik gibt es zwei Arten von wohlgeformten Zeichenreihen, nämmlich Formeln und Terme. Die ersten drei Regeln entsprechen denen der Aussagenlogik:

1. Jede Aussagenkonstante ist eine Formel, $\mathrm{\top }$ und $\mathrm{\perp }$ sind Formeln.
2. Ist $\varphi$ eine Formel, so ist auch $\mathrm{\neg }\varphi$ eine Formel.
3. Sind sowohl $\varphi$ als auch $\psi$ Formeln, so sind auch $(\varphi \wedge \psi )$, $(\varphi \vee \psi )$, $(\varphi \to \psi )$ und $(\varphi \leftrightarrow \psi )$ Formeln.
4. Jede Individuenkonstante und jede Variable ist ein Term.
5. Ist $F$ ein $n$-stelliges Funktionszeichen und sind $t_1,t_2,t_3,\dots ,t_n$ Terme, so ist $F(t_1,t_2,t_3,\dots ,t_n)$ ein Term.
6. Ist $P$ ein $n$-stelliges Prädikat, und sind $t_1,t_2,t_3,\dots ,t_n$ Terme, so ist $P(t_1,t_2,t_3,\dots ,t_n)$ eine Formel.
7. Sind $s$ und $t$ Terme, so ist $(s=t)$ eine Formel.
8. Ist $\varphi$ eine Formel und $x$ eine Variable, so sind $\mathrm{\forall }x\varphi$ und $\mathrm{\exists }x\varphi$ Formeln.

Es gibt keine weiteren Formeln und Terme. Aus dieser Definition ergibt sich sofort:

Die Regeln 1. bis 3. der Grammatik stimmen zwar wörtlich mit denen der Aussaglogik überein, aber ihr Anwendungsbereich ist sehr viel umfangreicher. Ist $P$ ein 1-stelliges Prädikat, $c$ eine Individuenkonstante und $x$ eine Variable, so sind beispielsweise $P(c)$ und $\mathrm{\exists }xP(x)$ Formeln nach den Regeln 6. und 8. Mit der Regel 3. können wir daraus die Formel $(P(c)\to \mathrm{\exists }xP(x))$ bilden.

Die Anzahl der Formeln und Terme hängt nun nicht allein von der Anzahl der Aussagenkonstanten ab, wie das in der Aussagenlogik war. Vielmehr hängt es auch von der Anzahl der Individuenkonstanten, der Relationen, der Funktionszeichen und der Variablen ab, wieviele Formeln und Terme es gibt.

Beispiele

In den folgenden Beispielen seien:

• Individuenkonstanten: $3,7Fritz,Erna,Berlin,Dresden,M\ddot{u}nchen,Deutschland$
• Funktionszeichen: $Hauptstadt$ (1-stellig), $+$ (2-stellig)
• Prädikate: $Primzahl$ (einstellig), $Mensch$ (1-stellig), $sterblich$ (einstellig), $\ge$ (grösser als, 2-stellig)

Ausdruck	Art	Begründung
$Dresden$	Term	nach Regel 1, weil $Dresden$ eine Individuenkonstante ist
$+(7,x)$	Term	nach Regel 5
$Primzahl(3)$	Formel	nach Regel 6
$\ge (Fritz,Erna)$	Formel	nach Regel 6
$\mathrm{\neg }Primzahl(Fritz)$	Formel	nach Regel 6 und Regel 2
$Hauptstadt$	-	ein Funktionszeichen ist kein Term und keine Formel
$Hauptstadt(Deutschland)$	Term	nach Regel 5
$Hauptstadt(Deutschland)=Berlin$	Formel	nach Regel 7
$\ge (Berlin)$	-	$\ge$ ist ein 2-stelliges Prädikat
$\ge (Berlin,M\ddot{u}nchen)$	Formel	nach Regel 6
$\mathrm{\forall }x=y$	-	es fehlt die Variable des Quantors
$\mathrm{\forall }x(Mensch(x)\to sterblich(x))$	Formel	nach den Regeln 6, 2 und 8
$\mathrm{\exists }x(+(7,x)=5)$	Formel	nach den Regeln 5, 7 und 8

Klammerersparnis

Wir erweitern die Klammerersparnisregeln der Aussagenlogik wie folgt:

1. Aussenklammern können weggelassen werden,
2. $=$ bindet stärker als die Quantoren und die Junktoren,
3. $\mathrm{\forall }$ und $\mathrm{\exists }$ binden stärker als die Junktoren,
4. $\wedge$ und $\vee$ binden stärker als $\to$ und $\leftrightarrow$,
5. $\to$ bindet stärker als $\leftrightarrow$.

Ist $c$ eine Individuenkonstante, so ist $\mathrm{\exists }xx=c\wedge \varphi$ wie folgt zu lesen: $\mathrm{\exists }x(x=c)\wedge \varphi$. Beachte, dass sich der Quantor nur auf die unmittelbar folgende Formel bezieht, im Beispiel nur auf die Gleichung.

Schreibweisen

Wir lassen Aussenklammern und weitere Klammern weg, wenn sie inhaltlich ohne Bedeutung sind, wie beispielsweise hier: $\varphi \wedge \psi \wedge \theta$. 2-stellige Funktionszeichen und 2-stellige Prädikate schreiben wir zwischen die Argumente: $3+x$ und $Fritz\ge Erna$. Wir setzen auch zusätzliche Klammern, wenn dieses die Verständlichkeit erhöht. Aus dem Zusammenhang sollte aber immer klar hervorgehen, wie die Formel nach den ursprünglichen Regeln zusammengesetzt ist.

Die Bedeutung

In der Prädikatenlogik muss nicht nur den Formeln einer der Wahrheitswerte Wahr oder Falsch zugeordnet werden, sondern es muss auch für die Terme eine Bedeutung festgelegt werden.

Interpretation, Bewertung

Definition:

Eine Bewertung $𝒥$

1. legt eine nichtleere Menge $𝔅$ als Individuenbereich fest,
2. ordnet allen Individuenkonstanten $c$ ein Element von $𝔅$ zu,
3. ordnet jedem $n$-stelligen Funktionszeichen $F$ eine $n$-stellige Funktion von ${𝔅}^n$ in $𝔅$ zu,
4. ordnet jeder $n$-stelligen Relation $R$ eine $n$-stellige Relation über ${𝔅}^n$ zu,
5. ordnet allen Variablen $x$ ein Element aus $𝔅$ zu,
6. ordnet allen Aussagenkonstanten $\alpha$ einen Wahrheitswert $𝖶$ oder $𝖥$ zu.

Es gilt also für eine Bewertung $𝒥$:

1. $𝔅\ne \varnothing$
2. $𝒥(c)\in 𝔅$
3. $𝒥(F):{𝔅}^n⟼𝔅$
4. $𝒥(R)\subseteq {𝔅}^n$
5. $𝒥(x)\in 𝔅$
6. $𝒥(\alpha )\in \{𝖶,𝖥\}$

Insbesondere ordnet also $𝒥$ den Variablen Werte zu. Dieser Teil von $𝒥$ wird Belegung genannt. Die Bewertung $J_{𝒸}^{𝓍}$ sei wie $𝒥$ definiert, nur dass der Variablen $x$ der Wert $c$ zugeordnet wird. Wir setzen die Bewertung $𝒥$ wie folgt auf alle Terme und Formeln fort:

1. $𝒥(F(x_1,x_2,x_3,\dots ,x_n))=𝒥(F)(𝒥(x_1),𝒥(x_2),𝒥(x_3),\dots ,𝒥(x_n))$
2. $𝒥(R(x_1,x_2,x_3,\dots ,x_n))=\{\begin{array}{cc}𝖶,& (𝒥(x_1),𝒥(x_2),𝒥(x_3),\dots ,𝒥(x_n))\in {𝔅}^n\\ 𝖥,& \text{sonst}\end{array}$
3. $𝒥(a=b)=\{\begin{array}{cc}𝖶,& \text{wenn }𝒥(a)=𝒥(b)\\ 𝖥,& \text{sonst}\end{array}$
4. $𝒥(\mathrm{\top })=𝖶$   und   $𝒥(\mathrm{\perp })=𝖥$
5. $𝒥(\mathrm{\neg }\varphi )=\{\begin{array}{cc}𝖶,& \text{wenn }𝒥(\varphi )=𝖥\\ 𝖥,& \text{sonst}\end{array}$
6. $𝒥(\varphi \wedge \psi )=\{\begin{array}{cc}𝖶,& \text{wenn }𝒥(\varphi )=𝖶\text{ und }𝒥(\psi )=𝖶\\ 𝖥,& \text{sonst}\end{array}$
7. $𝒥(\varphi \vee \psi )=\{\begin{array}{cc}𝖶,& \text{wenn }𝒥(\varphi )=𝖶\text{ und }𝒥(\psi )=𝖶\\ 𝖥,& \text{sonst}\end{array}$
8. $𝒥(\varphi \to \psi )=\{\begin{array}{cc}𝖶,& \text{sonst}\\ 𝖥,& \text{wenn }𝒥(\varphi )=𝖶\text{ und }𝒥(\psi )=𝖥\end{array}$
9. $𝒥(\varphi \leftrightarrow \psi )=\{\begin{array}{cc}𝖶,& \text{wenn }𝒥(\varphi )=𝒥(\psi )\\ 𝖥,& \text{sonst}\end{array}$
10. $𝒥(\mathrm{\forall }x\varphi )=\{\begin{array}{cc}𝖶,& \text{wenn für alle }c\in 𝔅\text{ gilt: }{J}_{𝒸}^{𝓍}(\varphi )=𝖶\\ 𝖥,& \text{sonst}\end{array}$
11. $𝒥(\mathrm{\exists }x\varphi )=\{\begin{array}{cc}𝖶,& \text{wenn es ein }c\in 𝔅\text{ gibt mit: }{J}_{𝒸}^{𝓍}(\varphi )=𝖶\\ 𝖥,& \text{sonst}\end{array}$

Feststellung:

Schränken wir eine Interpretation der Prädikatenlogik auf die Formeln ein, die auch Formeln der Aussagenlogik sind, so erhalten wir eine Interpretation im Sinne der Aussagenlogik!

Redeweisen:

Für die Interpretation der Prädikatenlogik sind die gleichen Redeweisen wie bei der Aussagenlogik üblich: {{#lst:Logik: Aussagenlogik|RedeweisenInterpretation}}

Logische Folgerung

Auch die Definitionen und Sätze zur logischen Folgerung $\models$ können aus der Aussagenlogik übernommen werden: {{#lst:Logik: Aussagenlogik|LogischeFolgerung}}