Aussagenlogik/Vollständigkeitssatz/Tautologie/Konstruktiv/Fakt/Beweis

Beweis

Es seien die in vorkommenden Aussagenvariablen. Es sei

eine fixierte Konjunktion dieser (negierten) Aussagenvariablen. Da eine Tautologie ist, ist auch

eine Tautologie, da ja die Gültigkeit von nicht von der Gültigkeit von abhängt. Nach Fakt ist oder . Im zweiten Fall wäre aufgrund der Korrektheit des Ableitungskalküls eine semantische Tautologie, was wegen der Erfüllbarkeit von sofort zu einem Widerspruch führt. Also ist

und zwar für jede Kombination der Negationen in . Eine komplexe Fallunterscheidung entlang der Kombinationsmöglichkeiten innerhalb von liefert dann