Erfüllbarkeit Aussagenlogik.

Question

Aufgabe:

Text erkannt:

(4) Seien \( G \) und \( H \) Formeln. Beweisen oder widerlegen Sie:
(i) \( \Sigma=\{(G \rightarrow H),(H \rightarrow G)\} \) ist genau dann erfüllbar, wenn \( \Sigma^{\prime}=\{G, H\} \) erfüllbar ist.
(ii) \( \Sigma=\{(\neg H) \rightarrow G, H \rightarrow G\} \) ist genau dann erfüllbar, wenn \( \Sigma^{\prime}=\{G, H\} \) erfüllbar ist.

Problem/Ansatz:

Hallo, ich habe diese Aufgabe.

Mein Ansatz:

(i) ich prüfe zuerst ∑(Erfüllbar) ⇒ ∑' (Erfüllbar) Dann Rückrichtung.

∑ = {(G ⇒ H), (H⇒G)} ⇔ ∑ = {(H ⇔G)}. ∑ ist also erfüllt, wenn G und H den selben Wahrheitswert haben.

Für Fall1 (G = Wahr und H = Wahr) ist ∑' erfüllt.

Für Fall2 (G = Falsch und H = Falsch) ist ∑' nicht erfüllt, da G und H Falsch

Wiederspruch, daher muss Rückrichtung nicht gezeigt werden.

(ii) ich prüfe wieder zuerst ∑(Erfüllbar) ⇒ ∑' (Erfüllbar)

∑ = {(¬H ⇒ G), (H ⇒ G) }lässt sich schreiben als ∑ = {(¬(¬H) ∨ G), (¬H ∨ G)} bzw. {(H∨G), (¬H∨G)}.

Wenn G wahr ist, ist ∑ ist also unabhängig vom Wahrheitswert H erfüllt.

Fall1: (H = Wahr und G = Wahr) dann ist ∑' erfüllt.

Fall2: (H = Falsch und G = Wahr) dann ist ∑' nicht erfüllt.

Dies führt dann zu einem Widerspruch.

Meine Frage ist nun, ob ich die Sache mit der "Erfüllbarkeit" richtig verstanden habe. In der Vorlesung haben wir gesagt, dass eine Formel erfüllbar ist, wenn es mind. eine Interpretation f(G) gibt, die wahr ist.

Ich verstehe in dieser Aufgabe nicht ganz, wann was erfüllbar ist. Zudem kann ich die Schreibweise nicht ganz deuten (∑={G,H} bedeutet dass {(G∧H)} ??)

Außerdem frage ich mich, ob für jede Interpretation in der ∑ erfüllbar ist, ∑' erfüllbar sein muss oder ob es reicht (bezogen auf die Aufgabenstellung), wenn eine Interpretation von ∑ Wahr ist in der auch ∑' wahr ist.

Danke schonmal im Voraus für eure Antworten!

LG.

Answer 1

Die gute Nachricht ist, dass du in beiden Teilaufgaben zu dem korrekten Ergebnis gekommen bist.

Du gehst aber ziemlich rücksichtslos mit der Notation um.

∑ = {(G ⇒ H), (H⇒G)} ⇔ ∑ = {(H ⇔G)}.

Verwende "→" anstatt "⇒".

Verwende "H ↔ G" anstatt "H ⇔ G".

Außerdem hier noch mal auf deutsch, was die Aussage

∑ = {(G ⇒ H), (H⇒G)} ⇔ ∑ = {(H ⇔G)}

bedeutet: "Die Menge ∑ besteht aus den zwei Formeln (G ⇒ H) und (H⇒G) genau dann wenn die Menge ∑ lediglich die Formel (H ⇔G) enthält".

Diese Aussage ist offensichtlich falsch. Einerseits soll ∑ die Mächtigkeit 2 haben, andereseits soll ∑ die Mächtigkeit 1 haben. Das geht nicht.

wann was erfüllbar ist.

Eine Formel F ist erfüllbar, wenn es eine Interpretation I gibt, unter der die Formel wahr ist. Eine solche Interpretation heißt Modell von F. In Zeichen:

        I ⊨ F

ausgesprochen "I ist Modell von F".

Eine Formelmenge M ist erfüllbar, wenn es eine Interpretation I gibt, unter der jede Formel von M wahr ist. Eine solche Interpretation heißt Modell von M, in Zeichen I ⊨ M.

Damit lässt sich (i) wie folgt lösen:

Behauptung. Die Äquivalenz gilt nicht.

Beweis. Seien G und H unerfüllbar. Dann ist Σ' unerfüllbar.

Sei I eine Interpretation, die auf G und H passt.

Dann ist I ⊨ (G→H) weil I ⊭ G und I ⊨ (H→G) weil I ⊭ H ist.

Also ist I ⊨ Σ und somit ist Σ erfüllbar.

q.e.d.

Natürlich wäre es als Beweis ebenso möglich, konkrete Formeln G und H explizit anzugeben.