Logik:Klausuren/07.02.2004/1.3 Aufgabe

1. Aufgabenstellung

Gegeben sei die aussagenlogische Formel $ F = (((p \and q) \rightarrow r) \rightarrow p) \rightarrow q) $.

a) Ist die Formel eine Tautologie? Beweisen Sie Ihre Antwort.

b) Sei $ G\; $ eine beliebige unerfüllbare aussagenlogische Formel und $ F\; $ wie oben angegeben. Beweisen Sie, dass $ \{ G\} \models F $ gilt.

c) Sei $ F\; $ die oben angegebene Formel. Gilt für jede beliebige erfüllbare aussagenlogische Formel $ G\; $ eine der Beziehungen $ \{ G\} \models F $ oder $ \{ F\} \models G $ ? Beweisen Sie Ihre Antwort.

2. Lösung

a)

Keine Tautologie, Beweis durch Gegenbeispiel:

Interpretation $ I\; $ mit $ p^I = w\; $, $ q^I = r^I = f\; $:

$ (((p \and q) \rightarrow r) \rightarrow p) \rightarrow q)^I $

$ \equiv ((((p \and q) \rightarrow r) \rightarrow p)^I \rightarrow * q^I) $

$ \equiv ((((p \and q)\rightarrow r)^I \rightarrow * p^I) \rightarrow * f) $

$ \equiv ((((p \and q)^I \rightarrow * r^I)\rightarrow * w)\rightarrow * f) $

$ \equiv ((((p^I \and * q^I)\rightarrow * f)\rightarrow * w)\rightarrow * f) $

$ \equiv ((((w \and * f)\rightarrow * f)\rightarrow * w)\rightarrow * f) $

$ \equiv (((f\rightarrow * f)\rightarrow * w)\rightarrow * f) $

$ \equiv ((w\rightarrow * w)\rightarrow * f) $

$ \equiv (w\rightarrow * f) $

$ \equiv f $

b)

zu zeigen: für alle $ I\; $ mit $ G^I = w\; $ folgt $ F^I = w\; $.

Da $ G^I = f\; $ für alle $ I\; $, folgt: es gibt kein $ I\; $ mit $ G^I = w\; $. Somit kann $ F\; $ beliebige Werte annehmen und $ \{ G\} \models F $ gilt.

c)

Keine Richtung gilt.
Gegenbeispiel: Wähle $ G = p\; $ mit $ G\; $ ist erfüllbar

I) $ p^I = w, q^I = r^I = f\; $
Dann $ G^I = w, F^I = f\; $ (nach 1.3 a)
$ \Rightarrow $ $ \{ G\} \models F $ gilt nicht

II) $ p^I = f, q^I = r^I = w\; $
Dann $ G^I = f, F^I = w\; $
$ \Rightarrow $ $ \{ F\} \models G $ gilt nicht

4. Alternativen/Diskussion/Hinweise etc.

c) Beide Aussagen gelten nicht.

(i) $ \{ G\} \models F $ gdw. $ (G \rightarrow F) $ist Tautologie
Gegenbeispiel:
$ G = (p \or \neg p) $ erfüllbar
$ p^I = r^I = w, q^I = f\; $
$ (G^I \rightarrow * F^I) = (w \rightarrow * f) = f $, also Aussage keine Tautologie, also keine aussagenlogische Konsequenz

(ii) $ \{ F\} \models G $ gdw. $ (F \rightarrow G) $ist Tautologie
Gegenbeispiel:
$ G = p\; $ erfüllbar
$ p^I = r^I = f, q^I = w\; $
$ (G^I \rightarrow * F^I) = (w \rightarrow * f) = f $, also Aussage keine Tautologie, also keine aussagenlogische Konsequenz

---

zur Klausur 07.02.2004
Aufgaben-Kategorie AL - Interpretationen und Modelle