Aussagenlogik/Vollständigkeitssatz/Textabschnitt

Wir zeigen, dass für die Aussagenlogik die Ableitbarkeitsbeziehung mit der Folgerungsbeziehung übereinstimmt. Im Beweisaufbau orientieren wir uns an dem Vollständigkeitssatz für die Prädikatenlogik.

Definition

Eine Teilmenge ${}\Gamma \subseteq L^{V}$ zu einer Menge ${}V$ an Aussagenvariablen heißt maximal widerspruchsfrei, wenn ${}\Gamma$ widerspruchsfrei ist und jede echt größere Menge ${}\Gamma \subset \Gamma '$ widersprüchlich ist.

Lemma

Es sei ${}L^{V}$ die Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$ und es sei ${}\lambda$ eine Wahrheitsbelegung der Variablen mit zugehöriger Interpretation ${}I$.

Dann ist ${}I^{\vDash }$ maximal widerspruchsfrei.

Beweis

Siehe Aufgabe.

$\Box$

Lemma

Es sei ${}V$ eine Menge an Aussagenvariablen und ${}\Gamma \subseteq L^{V}$ eine maximal widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik. Dann gelten folgende Aussagen.

1. Für jedes ${}\alpha \in L^{V}$ ist entweder ${}\alpha \in \Gamma$ oder ${}\neg \alpha \in \Gamma$.
2. Aus ${}\Gamma \vdash \alpha$ folgt ${}\alpha \in \Gamma$.
3. Es ist ${}\alpha \wedge \beta \in \Gamma$ genau dann, wenn ${}\alpha \in \Gamma$ und ${}\beta \in \Gamma$.
4. Es ist ${}\alpha \rightarrow \beta \in \Gamma$ genau dann, wenn ${}\alpha \not \in \Gamma$ oder ${}\beta \in \Gamma$.

Beweis

(1). Wegen der Widerspruchsfreiheit können nicht sowohl ${}\alpha$ als auch ${}\neg \alpha$ zu ${}\Gamma$ gehören. Wenn weder ${}\alpha$ noch ${}\neg \alpha$ zu ${}\Gamma$ gehören, so ist entweder ${}\Gamma \cup \{\alpha \}$ oder ${}\Gamma \cup \{\neg \alpha \}$ widerspruchsfrei. Wären nämlich beide widersprüchlich, so würde für einen beliebigen Ausdruck ${}\beta$ sowohl

$\Gamma \cup \{\alpha \}\vdash \beta$

als auch

$\Gamma \cup \{\neg \alpha \}\vdash \beta$

gelten. Dies bedeutet nach Aufgabe

$\Gamma \vdash \alpha \rightarrow \beta$

und

$\Gamma \vdash \neg \alpha \rightarrow \beta ,$

woraus aufgrund der Fallunterscheidungsregel

$\Gamma \vdash \beta$

folgt. Dies bedeutet aber, dass ${}\Gamma$ widersprüchlich ist.
(2). Es sei ${}\Gamma \vdash \alpha$. Nach (1) ist ${}\alpha \in \Gamma$ oder ${}\neg \alpha \in \Gamma$. Das zweite kann nicht sein, da sich daraus sofort ein Widerspruch ergeben würde. Also ist ${}\alpha \in \Gamma$.
(3) folgt aus (2) und der Konjunktionsregel.
(4). Aufgrund von (1) und Aufgabe müssen wir die Äquivalenz ${}\neg {\left(\alpha \rightarrow \beta \right)}\in \Gamma$ genau dann, wenn ${}\alpha \in \Gamma$ und ${}\neg \beta \in \Gamma$ zeigen. Dies ergibt sich aus (3).

$\Box$

Oben haben wir gesehen, dass Interpretationen maximal widerspruchsfreie Ausdrucksmengen liefern. Davon gilt auch die Umkehrung.

Lemma

Es sei ${}V$ eine Menge an Aussagenvariablen und ${}\Gamma \subseteq L^{V}$ eine maximal widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik.

Dann ist ${}\Gamma$ erfüllbar.

Beweis

Da ${}\Gamma$ maximal widerspruchsfrei ist, gilt nach Fakt  (1) für jede Aussagenvariable die Alternative ${}p\in \Gamma$ oder ${}\neg p\in \Gamma$. Wir betrachten die Wahrheitsbelegung

${}\lambda (p)={\begin{cases}1\,,{\text{ falls }}p\in \Gamma \,,\\0\,,{\text{ falls }}\neg p\in \Gamma \,,\end{cases}}\,$

mit der zugehörigen Interpretation ${}I$. Wir behaupten

${}I^{\vDash }=\Gamma \,,$

was wir über den Aufbau der Sprache beweisen. Der Induktionsanfang ist durch die gewählte Belegung gesichert, der Induktionsschritt folgt aus Fakt.

$\Box$

Wir wollen zeigen, dass jede widerspruchsfreie Ausdrucksmenge erfüllbar ist. Die Strategie ist hierbei, sie zu einer maximal widerspruchsfreien Ausdrucksmenge aufzufüllen und dann die vorstehende Aussage anzuwenden. Wir unterscheiden die beiden Fälle, wo die Aussagenvariablenmenge abzählbar ist und den allgemeinen Fall einer beliebigen Aussagenvariablenmenge. Letzteres erfordert stärkere mengentheoretische Hilfsmittel, nämlich das Fakt.

Lemma

Es sei ${}V$ eine abzählbare Menge an Aussagenvariablen und ${}\Gamma \subseteq L^{V}$ eine widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik.

Dann kann man ${}\Gamma$ durch sukzessive Hinzunahme von entweder ${}p_{n}$ oder ${}\neg p_{n}$ und durch Abschluss unter der Ableitungsbeziehung zu einer maximal widerspruchsfreien Teilmenge ${}\Gamma '\supseteq \Gamma$ ergänzen.

Beweis

Es sei ${}p_{n}$, ${}n\in \mathbb {N} _{+}$, eine (surjektive, aber nicht notwendigerweise injektive) Aufzählung der Aussagenvariablen. Die Voraussetzung bedeutet, dass ${}\Gamma _{0}:=\Gamma ^{\vdash }$ keinen Widerspruch enthält. Wir konstruieren eine (endliche oder abzählbar unendliche) Folge von aufsteigenden widerspruchsfreien Teilmengen ${}\Gamma _{n}\subseteq \Gamma _{n+1}$, wobei in ${}\Gamma _{n}$ für jede Variable ${}p_{i}$, ${}1\leq i\leq n$, die Alternative entweder ${}p_{i}\in \Gamma _{n}$ oder${}\neg p_{i}\in \Gamma _{n}$ gilt. Das Konstruktionsverfahren definieren und diese Aussage beweisen wir durch Induktion über ${}n\in \mathbb {N}$. Für ${}\Gamma _{0}$ ist dies richtig. Es sei ${}\Gamma _{n}$ schon konstruiert. Bei ${}p_{n+1}\in \Gamma _{n}$ oder ${}\neg p_{n+1}\in \Gamma _{n}$ setzen wir

${}\Gamma _{n+1}:=\Gamma _{n}\,.$

Wegen der Widerspruchsfreiheit von ${}\Gamma _{n}$ können nicht sowohl ${}p_{n+1}$ als auch ${}\neg p_{n+1}$ zu ${}\Gamma _{n}$ gehören. Wenn weder ${}p_{n+1}$ noch ${}\neg p_{n+1}$ zu ${}\Gamma _{n}$ gehören, so setzen wir

${}\Gamma _{n+1}:={\left(\Gamma _{n}\cup {p_{n+1}}\right)}^{\vdash }\,$

(man könnte genauso gut ${}\neg p_{n+1}$ hinzunehmen). Nach Konstruktion ist ${}\Gamma _{n+1}$ abgeschlossen unter der Ableitungsbeziehung und erfüllt die (Oder)-Alternative für alle Variablen ${}p_{i}$, ${}i\leq n+1$. Wenn ${}\Gamma _{n+1}$ widersprüchlich wäre, so gelte insbesondere ${}\Gamma _{n}\cup \{p_{n+1}\}\vdash \neg p_{n+1}$. Dann würde aber auch ${}\Gamma _{n}\vdash p_{n+1}\rightarrow \neg p_{n+1}$ gelten und somit nach der Fallunterscheidungsregel auch ${}\Gamma _{n}\vdash \neg p_{n+1}$, also ${}\neg p_{n+1}\in \Gamma _{n}$ im Widerspruch zu dem Fall, in dem wir uns befinden. Daher liegt für die Aussagenvariablen auch die Entweder-Oder-Alternative vor.

Mit dieser induktiven Definition setzen wir

${}\Gamma ':=\bigcup _{n\in \mathbb {N} }\Gamma _{n}\,.$

Diese Menge ${}\Gamma '$ ist widerspruchsfrei, da andernfalls schon eines der ${}\Gamma _{n}$ einen Widerspruch enthalten würde, und auch abgeschlossen unter Ableitungen, da dies für die einzelnen ${}\Gamma _{n}$ gilt und eine Ableitung nur endlich viele Voraussetzungen besitzt. Ferner gilt für jedes ${}n\in \mathbb {N}$ die Alternative ${}p_{n}\in \Gamma '$ oder ${}\neg p_{n}\in \Gamma '$. Damit sind die Voraussetzungen von Fakt erfüllt und ${}\Gamma '$ ist maximal widerspruchsfrei.

$\Box$

Beispiel

Wir betrachten die Aussagenvariablenmenge ${}\{p_{1},p_{2},p_{3},\ldots \}$ und die Ausdrucksmenge

${}\Gamma =\{p_{1}\rightarrow p_{2},\,p_{2}\rightarrow p_{3},\,p_{3}\rightarrow p_{4},\,\ldots \}\,.$

Diese wollen wir zu einer maximal widerspruchsfreien Menge gemäß Fakt ergänzen. Wenn wir im ersten Schritt ${}p_{1}$ hinzunehmen, so ergibt sich sukzessive ${}p_{i}\in \Gamma _{1}$ für alle ${}i\in \mathbb {N}$. Es ist dann ${}\Gamma _{1}$ schon maximal widerspruchsfrei. Wählt man hingegen im ersten Schritt ${}\neg p_{1}$, so gehört weder ${}p_{2}$ noch ${}\neg p_{2}$ zu ${}\Gamma _{1}$. Beim zweiten Schritt hat man dann die Freiheit, ob man ${}p_{2}$ oder ${}\neg p_{2}$ zur Definition von ${}\Gamma _{2}$ hinzunimmt, und so weiter.

Lemma

Es sei ${}V$ eine Menge an Aussagenvariablen und ${}\Gamma \subseteq L^{V}$ eine widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik.

Dann gibt es eine maximal widerspruchsfreie Teilmenge ${}\Gamma '\subseteq L^{V}$, die ${}\Gamma$ enthält.

Beweis

Wir betrachten die Menge

${}M:={\left\{\Delta \subseteq L^{V}\mid \Delta \supseteq \Gamma ,\,\Delta {\text{ widerspruchsfrei }}\right\}}\,$

mit der durch Inklusion gegebenen Ordnung. Wegen ${}\Gamma \in M$ ist diese Menge nicht leer. Es sei ${}N\subseteq M$ eine nichtleere total geordnete Teilmenge. Die Vereinigung

${}\Theta =\bigcup _{\Delta \in N}\Delta \,$

ist ebenfalls widerspruchsfrei, da ein Widerspruch schon aus einer endlichen Teilmenge ableitbar wäre, die ganz in einem der ${}\Delta$ enthalten wäre. Also besitzt die Kette in ${}M$ eine obere Schranke. Nach dem Lemma von Zorn gibt es also in ${}M$ maximale Elemente. Ein solches ist maximal widerspruchsfrei.

$\Box$

Satz

Es sei ${}V$ eine Menge an Aussagenvariablen und ${}\Gamma \subseteq L^{V}$ eine widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik.

Dann ist ${}\Gamma$ erfüllbar.

Beweis

Nach Fakt (bzw. Fakt im abzählbaren Fall) kann man ${}\Gamma$ zu einer maximal widerspruchsfreien Ausdrucksmenge ${}\Gamma '$ auffüllen. Nach Fakt ist ${}\Gamma '$ erfüllbar, d.h., es gibt eine Wahrheitsbelegung ${}\lambda$ derart, dass unter der zugehörigen Interpretation alle Ausdrücke aus ${}\Gamma '$ gültig sind. Dann sind unter dieser Belegung insbesondere die Ausdrücke aus ${}\Gamma$ gültig.

$\Box$

Satz

Es sei ${}V$ eine Menge an Aussagenvariablen und ${}\Gamma \subseteq L^{V}$ eine Teilmenge der zugehörigen Sprache der Aussagenlogik. Es sei ${}\alpha \in L^{V}$.

Dann ist

$\Gamma \vdash \alpha {\text{ genau dann, wenn }}\Gamma \vDash \alpha .$

Beweis

Dass die Ableitungsbeziehung die Folgerungsbeziehung impliziert, wurde bereits im Rahmen der Korrektheitsüberlegungen zu den Ableitungsregeln gezeigt. Für die Umkehrung nehmen wir ${}\Gamma \not \vdash \alpha$ an. Dies bedeutet nach Aufgabe, dass ${}\Gamma \cup \{\neg \alpha \}$ widerspruchsfrei ist. Nach Fakt ist dann auch ${}\Gamma \cup \{\neg \alpha \}$ erfüllbar. Es gibt also eine Wahrheitsbelegung mit ${}I\vDash \Gamma$ und ${}I\vDash \neg \alpha$. Also ist ${}\Gamma \not \vDash \alpha$.

$\Box$