Folgerung aus Kompaktheitssatz beweisen

Question

Wie zeige ich, dass: Aus Σ folgt A genau dann wenn: Σ∪{¬A} nicht erfüllbar ist?

Answer 1

Aus Σ folgt A

Beweis durch Widerspruch, dass dann Σ∪{¬A} unerfüllbar ist.

Sei B eine Variablenbelegung, die jede Formel aus Σ∪{¬A} erfüllt.

Dann erfüllt B einerseits ¬A wegen ¬A ∈ Σ∪{¬A}.

Außerdem erfüllt B jede Formel aus Σ wegen Σ⊆Σ∪{¬A}. Laut Voraussetzung erfüllt dann B auch A.

Eine Variablenbelegung kann nicht sowohl A als auch ¬A erfüllen. Eine Variablenbelegung, die Σ∪{¬A} erfüllt, existiert also nicht. Also ist Σ∪{¬A} nicht erfüllbar.

wenn Σ∪{¬A} nicht erfüllbar ist

Beweis dass A aus Σ folgt durch Fallunterscheidung über die Erfüllbakeit von Σ.

Fall 1. Σ ist erfüllbar. Sei B eine Variablenbelegung, die Σ erfüllt. Dann erfüllt B auch A, weil B nicht ¬A erfüllt. Also folgt A aus Σ.

Fall 2. Σ ist nicht erfüllbar. Dann folgt A aus Σ, weil es keine Variablenbelegung gibt, die Σ erfüllt.

Comments

Der erste Beweis durch Widerspruch lässt sich sehr gut verstehen.

Zum Verständnis hab ich den zweiten Beweis nochmal aufgeschrieben:

Der zweite Beweis bedeutet also: wenn Σ∪{¬A} nicht erfüllbar ist, dann weil eine Teilmenge von Σ nicht erfüllbar ist. Dann muss es daran liegen, dass {¬A} nicht erfüllbar ist oder Σ nicht erfüllbar ist.

Fall 1 bedeutet dann: Wenn wir annehmen, dass Σ∪{¬A} nicht erfüllbar ist und sagen Σ ist in diesem Fall erfüllbar dann muss {¬A} nicht erfüllbar sein. Weil {¬A} nicht erfüllbar ist folgt daraus das A erfüllbar sein muss.

Fall 2 bedeutet dann: Wenn wir annehmen, dass Σ∪{¬A} nicht erfüllbar ist und sagen Σ ist in diesem Fall nicht erfüllbar, dann sehen wir aus der Voraussetzung direkt: Σ ist in sich widersprüchlich und aus einem Widerspruch kann man alles folgern. Ex falso quodlibet.

Vielen Dank für die Beweise @oswald!

---

Wenn wir annehmen, dass Σ∪{¬A} nicht erfüllbar ist und sagen Σ ist in diesem Fall erfüllbar dann muss {¬A} nicht erfüllbar sein

{¬A} kann unter den gegebenen Voraussetzungen durchaus erfüllbar sein. Entscheidend ist, dass keine Belegung, die Σ erfüllt, auch {¬A} erfüllt. Beispiel: A = v, Σ = {A}. Dann ist Σ∪{¬A} = {A, ¬A} unerfüllbar, obwohl sowohl Σ als auch {¬A} erfüllbar sind. Σ und {¬A} sind aber nicht durch die gleiche Belegung erfüllbar.