Aussagenlogik/Vollständigkeitssatz/Vorbereitungen/Abzählbar/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen


Definition  

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



Lemma

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.




Lemma  

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

und

woraus aufgrund der Fallunterscheidungsregel

folgt. Dies bedeutet aber, dass widersprüchlich ist.
(2). 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 müssen wir die Äquivalenz genau dann, wenn und zeigen. Dies ergibt sich aus (3).




Lemma  

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. 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.

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  

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 Fakt  (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 Fakt.