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

Beweis

Es seien ${}p_{1},\ldots ,p_{n}$ die in ${}\alpha$ vorkommenden Aussagenvariablen. Es sei

${}\gamma =\pm p_{1}\wedge \ldots \wedge \pm p_{n}\,$

eine fixierte Konjunktion dieser (negierten) Aussagenvariablen. Da ${}\alpha$ eine Tautologie ist, ist auch

$\gamma \rightarrow \alpha$

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

$\vdash \gamma \rightarrow \alpha ,$

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

$\vdash \alpha .$

Zur bewiesenen Aussage