Aussagenlogik/Ausdrucksmenge abgeschlossen und Alternative für Variablen/Maximal widerspruchsfrei/Fakt/Beweis/Aufgabe/Lösung

Aus Wikiversity
Zur Navigation springen Zur Suche springen

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 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. Nachdem, was wir eben bewiesen haben, gilt dann . Dann ist aber und somit ist diese erweiterte Menge widersprüchlich.
Zur gelösten Aufgabe