Aussagenlogik/Endliche Ausdrucksmenge/Widersprüchlich/Test/Aufgabe/Lösung

In den endlich vielen Ausdrücken ${\displaystyle {}\alpha _{1},\ldots ,\alpha _{n}}$ von ${\displaystyle {}\Gamma }$ kommen insgesamt nur endlich viele Aussagenvariablen vor, sagen wir ${\displaystyle {}p_{1},\ldots ,p_{k}}$. Für jede ${\displaystyle {}\pm }$-Kombination

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

untersucht man, ob ${\displaystyle {}\Gamma \cup \{\gamma \}}$ widersprüchlich ist. Da durch ${\displaystyle {}\gamma }$ jede Aussagenvariable entweder positiv oder in ihrer Negation aus ${\displaystyle {}\Gamma \cup \{\gamma \}}$ ableitbar ist, kann man für jedes ${\displaystyle {}\alpha _{i}}$ überprüfen, ob ${\displaystyle {}\neg \alpha _{i}}$ aus ${\displaystyle {}\Gamma \cup \{\gamma \}}$ ableitbar ist. Wenn die durch ${\displaystyle {}\gamma }$ gegebene Belegung sämtliche ${\displaystyle {}\alpha _{i}}$ erfüllt, so hat man eine Belegung gefunden, die zeigt, dass ${\displaystyle {}\Gamma }$ erfüllbar und damit widerspruchsfrei ist. Im andern Fall stellt sich heraus, dass zu jedem ${\displaystyle {}\gamma }$ mindestens ein ${\displaystyle {}\alpha _{i}}$ die Belegung falsch bekommt. Nach Fakt ist ${\displaystyle {}\gamma \rightarrow \alpha _{i}}$ oder ${\displaystyle {}\gamma \rightarrow \neg \alpha _{i}}$ ableitbar, wobei im gegebenen Fall nur die zweite Möglichkeit

${\displaystyle \vdash \gamma \rightarrow \neg \alpha _{i}}$

verbleibt. Wegen ${\displaystyle {}\alpha _{i}\in \Gamma }$ erhält man also

${\displaystyle \Gamma \vdash \gamma \rightarrow q\wedge \neg q.}$

Da dies für jede Kombination ${\displaystyle {}\gamma }$ gilt, kann man mit mehrfacher Anwendung der Fallunterscheidungsregel

${\displaystyle \Gamma \vdash q\wedge \neg q}$

${\displaystyle {}\Gamma }$