Aussagenlogik/Tautologie und Erfüllbarkeit/Fakt/Beweis

Beweis

Wir beweisen die kontraponierte Aussage, dass ${}\alpha$ genau dann keine Tautologie ist, wenn ${}\neg \alpha$ erfüllbar ist. Dass keine Tautologie vorliegt, bedeutet, dass es eine Wahrheitsbelegung ${}\lambda$ derart gibt, dass

${}I^{\lambda }(\alpha )=0\,.$

Dies bedeutet aber

${}I^{\lambda }(\neg \alpha )=1\,,$

was gerade die Erfüllbarkeit von ${}\neg \alpha$ besagt.

Zur bewiesenen Aussage