Logik: Prädikatenlogik

Dieses Kapitel wird gerade überarbeitet!

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)   ${\boldsymbol {3\;}}{\mathsf {ist\;eine\;Primzahl.}}$

(2)   ${\mathsf {Fritz\;ist\;gr{\ddot {o}}sser\;als\;Erna.}}$

(3)   ${\boldsymbol {7+x=5}}$

In diesen Aussagen gibt es sogenannte Individuenkonstante nämlich: $3,5,7$, ${\mathsf {Fritz}}$ und ${\mathsf {Erna}}$. 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\;Primzahl}}$ ist ein Prädikat, ebenso ${\mathsf {\dots \;ist\;gr{\ddot {o}}sser\;als\;\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 $\forall$ (für alle ...) und der Existenzquantor $\exists$ (es gibt ...). Beispiele:

(4)   ${\mathsf {Alle\;Menschen\;sind\;sterblich.}}$

(5)   ${\boldsymbol {\exists x(7+x=5)}}$

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 $\top$, $\bot$, $\neg$, $\land$, $\lor$, $\rightarrow$, $\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 $\forall$, $\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, $\top$ und $\bot$ sind Formeln.
2. Ist $\phi$ eine Formel, so ist auch $\neg \phi$ eine Formel.
3. Sind sowohl $\phi \,$ als auch $\psi \,$ Formeln, so sind auch $(\phi \wedge \psi )$, $(\phi \vee \psi )$, $(\phi \rightarrow \psi )$ und $(\phi \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},\dotsc ,t_{n}$ Terme, so ist $F(t_{1},t_{2},t_{3},\dotsc ,t_{n})$ ein Term.
6. Ist $P$ ein $n$-stelliges Prädikat, und sind $t_{1},t_{2},t_{3},\dotsc ,t_{n}$ Terme, so ist $P(t_{1},t_{2},t_{3},\dotsc ,t_{n})$ eine Formel.
7. Sind $s$ und $t$ Terme, so ist $(s=t)$ eine Formel.
8. Ist $\phi$ eine Formel und $x$ eine Variable, so sind $\forall x\phi$ und $\exists x\phi$ 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 $\exists x\,P(x)$ Formeln nach den Regeln 6. und 8. Mit der Regel 3. können wir daraus die Formel $(P(c)\rightarrow \exists x\,P(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,\,7\,Fritz,\,Erna,\,Berlin,\,Dresden,\,M{\ddot {u}}nchen,\,Deutschland$
• Funktionszeichen: $Hauptstadt$ (1-stellig), $+$ (2-stellig)
• Prädikate: $Primzahl$ (einstellig), $Mensch$ (1-stellig), $sterblich$ (einstellig), $\geq$ (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
$\geq (Fritz,Erna)$	Formel	nach Regel 6
$\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
$\geq (Berlin)$	-	$\geq$ ist ein 2-stelliges Prädikat
$\geq (Berlin,M{\ddot {u}}nchen)$	Formel	nach Regel 6
$\forall x=y$	-	es fehlt die Variable des Quantors
$\forall x\,(Mensch(x)\rightarrow sterblich(x))$	Formel	nach den Regeln 6, 2 und 8
$\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. $\forall$ und $\exists$ binden stärker als die Junktoren,
4. $\land$ und $\lor$ binden stärker als $\rightarrow$ und $\leftrightarrow$,
5. $\rightarrow$ bindet stärker als $\leftrightarrow$.

Ist $c$ eine Individuenkonstante, so ist $\exists x\,x=c\land \phi$ wie folgt zu lesen: $\exists x\,(x=c)\land \phi$. 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: $\phi \land \psi \land \theta$. 2-stellige Funktionszeichen und 2-stellige Prädikate schreiben wir zwischen die Argumente: $3+x$ und $Fritz\geq 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 ${\mathcal {J}}$

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

Es gilt also für eine Bewertung ${\mathcal {J}}$:

1. ${\mathfrak {B}}\neq \varnothing$
2. ${\mathcal {J}}(c)\in {\mathfrak {B}}$
3. ${\mathcal {J}}(F):{\mathfrak {B}}^{n}\longmapsto {\mathfrak {B}}$
4. ${\mathcal {J}}(R)\subseteq {\mathfrak {B}}^{n}$
5. ${\mathcal {J}}(x)\in {\mathfrak {B}}$
6. ${\mathcal {J}}(\alpha )\in \{{\mathsf {W}},{\mathsf {F}}}\$

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

1. ${\mathcal {J}}(F(x_{1},x_{2},x_{3},\dots ,x_{n}))={\mathcal {J}}(F)({\mathcal {J}}(x_{1}),{\mathcal {J}}(x_{2}),{\mathcal {J}}(x_{3}),\dots ,{\mathcal {J}}(x_{n}))$
2. ${\mathcal {J}}(R(x_{1},x_{2},x_{3},\dots ,x_{n}))={\begin{cases}{\mathsf {W}},&({\mathcal {J}}(x_{1}),{\mathcal {J}}(x_{2}),{\mathcal {J}}(x_{3}),\dots ,{\mathcal {J}}(x_{n}))\in {\mathfrak {B}}^{n}\\{\mathsf {F}},&{\text{sonst}}\end{cases}}$
3. ${\mathcal {J}}(a=b)={\begin{cases}{\mathsf {W}},&{\text{wenn }}{\mathcal {J}}(a)={\mathcal {J}}(b)\\{\mathsf {F}},&{\text{sonst}}\end{cases}}$
4. ${\mathcal {J}}(\top )={\mathsf {W}}$   und   ${\mathcal {J}}(\bot )={\mathsf {F}}$
5. ${\mathcal {J}}(\neg \phi )={\begin{cases}{\mathsf {W}},&{\text{wenn }}{\mathcal {J}}(\phi )={\mathsf {F}}\\{\mathsf {F}},&{\text{sonst}}\end{cases}}$
6. ${\mathcal {J}}(\phi \land \psi )={\begin{cases}{\mathsf {W}},&{\text{wenn }}{\mathcal {J}}(\phi )={\mathsf {W}}{\text{ und }}{\mathcal {J}}(\psi )={\mathsf {W}}\\{\mathsf {F}},&{\text{sonst}}\end{cases}}$
7. ${\mathcal {J}}(\phi \lor \psi )={\begin{cases}{\mathsf {W}},&{\text{wenn }}{\mathcal {J}}(\phi )={\mathsf {W}}{\text{ und }}{\mathcal {J}}(\psi )={\mathsf {W}}\\{\mathsf {F}},&{\text{sonst}}\end{cases}}$
8. ${\mathcal {J}}(\phi \rightarrow \psi )={\begin{cases}{\mathsf {W}},&{\text{sonst}}\\{\mathsf {F}},&{\text{wenn }}{\mathcal {J}}(\phi )={\mathsf {W}}{\text{ und }}{\mathcal {J}}(\psi )={\mathsf {F}}\end{cases}}$
9. ${\mathcal {J}}(\phi \leftrightarrow \psi )={\begin{cases}{\mathsf {W}},&{\text{wenn }}{\mathcal {J}}(\phi )={\mathcal {J}}(\psi )\\{\mathsf {F}},&{\text{sonst}}\end{cases}}$
10. ${\mathcal {J}}(\forall x\phi )={\begin{cases}{\mathsf {W}},&{\text{wenn für alle }}c\in {\mathfrak {B}}{\text{ gilt: }}{\mathcal {J_{c}^{x}}}(\phi )={\mathsf {W}}\\{\mathsf {F}},&{\text{sonst}}\end{cases}}$
11. ${\mathcal {J}}(\exists x\phi )={\begin{cases}{\mathsf {W}},&{\text{wenn es ein }}c\in {\mathfrak {B}}{\text{ gibt mit: }}{\mathcal {J_{c}^{x}}}(\phi )={\mathsf {W}}\\{\mathsf {F}},&{\text{sonst}}\end{cases}}$

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:

${\mathcal {J}}$ erfüllt eine Formel $\varphi$, wenn ${\mathcal {J}}$ der Formel $\varphi$ den Wert Wahr zuordnet. ${\mathcal {J}}$ erfüllt die Formelmenge $\Gamma$, wenn ${\mathcal {J}}$ alle Formeln aus $\Gamma$ mit Wahr belegt. Eine andere Redeweise lautet: ${\mathcal {J}}$ ist ein Modell von $\varphi$ bzw. von $\Gamma$.

${\mathcal {J}}$ widerlegt eine Formel $\varphi$, wenn ${\mathcal {J}}$ die Formel $\varphi$ mit Falsch bewertet. ${\mathcal {J}}$ wird dann auch Gegenbeispiel für $\varphi$ genannt.

Logische Folgerung

Auch die Definitionen und Sätze zur logischen Folgerung $\models$ können aus der Aussagenlogik übernommen werden:

Definition: Seien $\Gamma$ und $\Delta$ Formelmengen.

Dann folgt $\Delta$ aus $\Gamma$, wenn für alle Bewertungen gilt: sind alle Formeln aus $\Gamma$ Wahr, dann ist wenigstens eine Formel aus $\Delta$ Wahr.

Schreibweisen: $\Gamma \models \Delta$ (aus $\Gamma$ folgt $\Delta$) und $\Gamma \nvDash \Delta$ (aus $\Gamma$ folgt nicht $\Delta$).

Damit $\Gamma \nvDash \Delta$ gilt, muss es also eine Bewertung ${\mathcal {J}}$ geben, die alle Formeln aus $\Gamma$ mit ${\mathsf {W}}$ und alle Formeln aus $\Delta$ mit ${\mathsf {F}}$ belegt.

Schreibweisen

Statt $\lbrace \varphi _{1},\varphi _{2},...,\varphi _{n}\rbrace \models \lbrace \psi _{1},\psi _{2},...,\psi _{m}\rbrace$ schreiben wir einfach $\varphi _{1},\varphi _{2},...,\varphi _{n}\models \psi _{1},\psi _{2},...,\psi _{m}$, lassen also die Klammern $\lbrace \;\rbrace$ weg.

Mit   $\Gamma ,\varphi \models \Delta ,\psi$   ist   $\Gamma \cup \lbrace \varphi \rbrace \models \Delta \cup \lbrace \psi \rbrace$   gemeint.

Ein wichtiger Spezialfall ist   $\Gamma \models \varphi$   (aus $\Gamma$ folgt $\varphi$).

$\models \varphi$   steht für   $\varnothing \models \varphi$   ($\varnothing$ ist die leere Menge).

Beweis:
Es gelte $\Gamma ,\varphi \models \psi ,\Delta$ und es sei ${\mathcal {J}}$ eine Bewertung, die alle Formeln aus $\Gamma$ Wahr macht.
Wenn ${\mathcal {J}}$ die Formel $\varphi$ mit Falsch bewertet, sind wir fertig, weil dann ${\mathcal {J}}$ die Formel $\varphi \rightarrow \psi$ erfüllt. Wenn ${\mathcal {J}}$ die Formel $\varphi$ mit Wahr bewertet, ist es nach Voraussetzung die Formel $\psi$ oder eine Formel aus $\Delta$ Wahr. Im zweiten Fall ist nichts weiter zu zeigen und im ersten Fall ist auch $\varphi \rightarrow \psi$ Wahr.

Gelte nun umgekehrt $\Gamma \models \varphi \rightarrow \psi ,\Delta$ und ${\mathcal {J}}$ erfülle alle Formeln aus $\Gamma$.
Wenn ${\mathcal {J}}$ eine Formel aus $\Delta$ Wahr macht, sind wir fertig. Wenn ${\mathcal {J}}$ die Formel $\varphi \rightarrow \psi$ Wahr macht, gibt es zwei Möglichkeiten: ${\mathcal {J}}$ bewertet $\varphi$ mit Falsch, dann ist alles klar. Bewertet ${\mathcal {J}}$ die Formel $\varphi$ mit Wahr, bewertet sie auch die Formel $\psi$ mit Wahr. Also gilt $\Gamma ,\varphi \models \psi ,\Delta$. ✔