Aussagenlogik/Ausdrucksmenge abgeschlossen und Alternative für Variablen/Maximal widerspruchsfrei/Fakt/Beweis

Aus Wikiversity
Wechseln zu: Navigation, Suche
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 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 bewiesenen Aussage