Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Vorlesung 4/kontrolle

Aus Wikiversity



Die Ableitungsbeziehung

Die syntaktische Entsprechung zur Folgerungsbeziehung ist die folgende Ableitungsbeziehung.


Definition  Referenznummer erstellen

Es sei eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge und sei . Man sagt, dass aus ableitbar ist, geschrieben

wenn es endlich viele Ausdrücke derart gibt, dass

gilt.

Die vorgegebene Ausdrucksmenge kann endlich oder unendlich sein, in der Ableitungsbeziehung kommen aber stets nur endlich viele Ausdrücke aus vor (eine „unendliche Konjunktion“ ist gar nicht definiert). Die Menge der aus einer gegebenen Ausdrucksmenge ableitbaren Ausdrücke bezeichnet man mit , also

Wegen (nach Lemma 3.11) gilt . Bei sagt man, dass abgeschlossenen unter Ableitungen ist. Die aus der leeren Menge ableitbaren Ausdrücke sind gerade die (syntaktischen) Tautologien.

Aus den (Grund- oder abgeleiteten) Tautologien ergeben sich direkt Regeln für die Ableitungsbeziehung.


Lemma Referenznummer erstellen

Es sei eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge .

Dann gelten folgende Regeln für die Ableitungsbeziehung (dabei seien Aussagen).

  1. Konjunktionsregel: genau dann, wenn und .
  2. Kettenschlussregel: Wenn und , dann auch .
  3. Modus ponens: Wenn und , dann ist auch .
  4. Wenn , so auch .
  5. Wenn und , dann auch .
  6. Widerspruchsregel: Wenn und , dann auch .
  7. Fallunterscheidungsregel: Wenn und , dann auch .

Beweis

Siehe Aufgabe 4.6.



Definition  Referenznummer erstellen

Eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge heißt widersprüchlich, wenn es einen Ausdruck mit und gibt. Eine nicht widersprüchliche Ausdrucksmenge heißt widerspruchsfrei.

Nach Fakt *****  (6) kann man aus einer widersprüchlichen Aussagenmenge jede Aussage ableiten.



Der Vollständigkeitssatz der Aussagenlogik I

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, der deutlich schwieriger ist und der später folgen wird.


Definition  Referenznummer erstellen

Eine Teilmenge zu einer Menge an Aussagenvariablen heißt maximal widerspruchsfrei, wenn widerspruchsfrei ist und jede echt größere Menge widersprüchlich ist.



Lemma Referenznummer erstellen

Es sei die Sprache der Aussagenlogik zu einer Aussagenvariablenmenge und es sei eine Wahrheitsbelegung der Variablen mit zugehöriger Interpretation .

Dann ist maximal widerspruchsfrei.

Beweis

Siehe Aufgabe 4.15.



Lemma  Lemma 4.6 ändern

Es sei eine Menge an Aussagenvariablen und eine maximal widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik. Dann gelten folgende Aussagen.

  1. Für jedes ist entweder oder .
  2. Aus folgt .
  3. Es ist genau dann, wenn und .
  4. Es ist genau dann, wenn oder .

Beweis  

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

als auch

gelten. Dies bedeutet nach Aufgabe 4.9

und

woraus aufgrund der Fallunterscheidungsregel

folgt. Dies bedeutet aber, dass widersprüchlich ist.
(2). Es sei . Nach (1) ist oder . Das zweite kann nicht sein, da sich daraus sofort ein Widerspruch ergeben würde. Also ist .
(3) folgt aus (2) und der Konjunktionsregel.
(4). Aufgrund von (1) und Aufgabe ***** {{:Kurs:Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Aussagenlogik/Syntaktische Tautologien/Implikation/Durch Negation und Konjunktion/Aufgabe/Aufgabereferenznummer/Aussagenlogik/Syntaktische Tautologien/Implikation/Durch Negation und Konjunktion/Aufgabe/Aufgabereferenznummer}} müssen wir die Äquivalenz genau dann, wenn und zeigen. Dies ergibt sich aus (3).



Lemma  Lemma 4.7 ändern

Es sei eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge . Es sei widerspruchsfrei, abgeschlossen unter Ableitungen und für jede Aussagenvariable gelte oder .

Dann ist maximal widerspruchsfrei.

Beweis  

Wir zeigen zuerst durch Induktion über den Aufbau der Sprache, dass für jedes die Alternative oder gilt. Daraus folgt die maximale Widerspruchsfreiheit. Für eine Aussagenvariable ist dies Teil der Voraussetzung. Bei folgt wegen die Aussage aus der Induktionsvoraussetzung, da abgeschlossen unter Ableitungen ist. Es sei nun . Bei und ist wegen der Ableitungsabgeschlossenheit auch . Wenn hingegen ist, so folgt nach der Induktionsvoraussetzung . Aufgrund der Tautologie ergibt sich . Der Beweis für die Implikation verläuft ähnlich, siehe Aufgabe 4.16.

Zum Nachweis, dass maximal widerspruchsfrei ist, sei angenommen. Nach dem, was wir eben bewiesen haben, gilt dann . Dann ist aber und somit ist diese erweiterte Menge widersprüchlich.


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


Lemma  Lemma 4.8 ändern

Es sei eine Menge an Aussagenvariablen und eine maximal widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik.

Dann ist erfüllbar.

Beweis  

Da maximal widerspruchsfrei ist, gilt nach Lemma 4.6  (1) für jede Aussagenvariable die Alternative oder . Wir betrachten die Wahrheitsbelegung

mit der zugehörigen Interpretation . Wir behaupten

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



Auffüllungsstrategien

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 Lemma von Zorn.



Lemma  Lemma 4.9 ändern

Es sei eine abzählbare Menge an Aussagenvariablen und eine widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik.

Dann kann man durch sukzessive Hinzunahme von entweder oder und durch Abschluss unter der Ableitungsbeziehung zu einer maximal widerspruchsfreien Teilmenge ergänzen.

Beweis  

Es sei , , eine (surjektive, aber nicht notwendigerweise injektive) Aufzählung der Aussagenvariablen. Die Voraussetzung bedeutet, dass keinen Widerspruch enthält. Wir konstruieren eine (endliche oder abzählbar unendliche) Folge von aufsteigenden widerspruchsfreien Teilmengen , wobei in für jede Variable , , die Alternative entweder oder gilt. Das Konstruktionsverfahren definieren und diese Aussage beweisen wir durch Induktion über . Für ist dies richtig. Es sei schon konstruiert. Bei oder setzen wir

Wegen der Widerspruchsfreiheit von können nicht sowohl als auch zu gehören. Wenn weder noch zu gehören, so setzen wir

(man könnte genauso gut hinzunehmen). Nach Konstruktion ist abgeschlossen unter der Ableitungsbeziehung und erfüllt die (Oder)-Alternative für alle Variablen , . Wenn widersprüchlich wäre, so gelte insbesondere . Dann würde aber auch gelten und somit nach der Fallunterscheidungsregel auch , also 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

Diese Menge ist widerspruchsfrei, da andernfalls schon eines der einen Widerspruch enthalten würde, und auch abgeschlossen unter Ableitungen, da dies für die einzelnen gilt und eine Ableitung nur endlich viele Voraussetzungen besitzt. Ferner gilt für jedes die Alternative oder . Damit sind die Voraussetzungen von Lemma 4.7 erfüllt und ist maximal widerspruchsfrei.



Beispiel  Referenznummer erstellen

Wir betrachten die Aussagenvariablenmenge und die Ausdrucksmenge

Diese wollen wir zu einer maximal widerspruchsfreien Menge gemäß Lemma 4.9 ergänzen. Wenn wir im ersten Schritt hinzunehmen, so ergibt sich sukzessive für alle . Es ist dann schon maximal widerspruchsfrei. Wählt man hingegen im ersten Schritt , so gehört weder noch zu . Beim zweiten Schritt hat man dann die Freiheit, ob man oder zur Definition von hinzunimmt, und so weiter.