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

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

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

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

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

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

$\Gamma \vdash \gamma \rightarrow q\wedge \neg q.$

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

$\Gamma \vdash q\wedge \neg q$

zeigen. In diesem Fall ist also ${}\Gamma$ widersprüchlich.

Zur gelösten Aufgabe