Logik:Klausuren/08.02.2003/2.5 Aufgabe

1. Aufgabenstellung

Gelten die folgenden Aussagen? Beweisen Sie jeweils Ihre Antwort.

a) Wenn die aussagenlogischen Formeln $ F[G], G\; $ und $ H\; $ erfüllbar sind, dann ist auch $ F[G/H]\; $ erfüllbar.
b) Seien $ F\; $ eine allgemeingültige, $ G\; $ eine unerfüllbare und $ H\; $ eine erfüllbare aussagenlogische Formel. Dann gilt $ F[G] \equiv F[G/((H \and G) \and (H \or G))] $.
c) Wenn $ G \rightarrow H\; $ dann gilt $ F[G] \rightarrow F[G/H]\; $.

2. Lösung

a) Aussage falsch, Gegenbeispiel:

$ F=(\neg p \and q)\; $,
$ G=p\; $,
$ H=q\; $

$ F[G/H]=(\neg q \and q)\; $

b) Aussage richtig:

Da $ F[G]\; $ allgemeingültig und $ G\; $ unerfüllbar, ist auch $ F[G/((H \and G) \and (H \or G))] $ allgemeingültig wenn $ ((H \and G) \and (H \or G)) $ ebenfalls unerfüllbar:

$ ((H \and G) \and (H \or G))^I $
$ = ((H \and G)^I \and ^* (H \or G)^I) $
$ = ((H^I \and ^* f) \and ^* (H^I \or ^* f)) $
$ = (f \and ^* (H^I \or ^* f)) $
$ = f\; $

(Satz 3.18: Wenn G und H semantisch äquivalent, dann auch F[G] und F[G/H] - Achtung: dieses H bezeichnet die gesamte Formel, die G ersetzt; auf die Aufgabe bezogen also $ ((H \and G) \and (H \or G)) $!)

c) Aussage falsch, Gegenbeispiel:

$ G=(p \and \neg p)\; $ ($ G^I = f\; $)
$ H=(p \or\neg p)\; $ ($ H^I = w\; $)

$ F = ((p \and \neg p) \rightarrow (p \leftrightarrow\neg p)) $

$ F[G] = (G \rightarrow (p \leftrightarrow\neg p))\; $ ($ F[G]^I = w\; $)
$ F[G/H] = (H \rightarrow (p \leftrightarrow\neg p))\; $ ($ F[G/H]^I = f\; $)

$ (G \rightarrow H)^I = w\; $)
$ (F[G] \rightarrow F[G/H])^I = f\; $)

4. Alternativen/Diskussion/Hinweise etc.

---

zur Klausur 08.02.2003
Aufgaben-Kategorie AL - Interpretationen und ModelleAufgaben-Kategorie AL - Äquivalenz und Normalformen