Logik:Klausuren/08.02.2003/2.8 Aufgabe

1. Aufgabenstellung

Eine aussagenlogische Formel liege in Implikationsnormalform vor, wenn sie nur die Junktoren $ \neg\; $ und $ \rightarrow; $ enthält.

a) Beweisen Sie: Es gibt einen Algorithmus, der jede aussagenlogische Formel in Implikationsnormalform transformiert. Beschränken Sie sich dabei auf Formeln, die nur die Junktoren $ \neg;\ \rightarrow;\ \and;\ $ und $ \or; $ enthalten.

b) Transformieren Sie die aussagenlogische Formel $ F = ((p \and q) \or \neg((p \or \neg q)\and p)); $ durch Anwendung des von Ihnen vorgeschlagenen Transformationsalgorithmus in Implikationsnormalform.

2. Lösung

a)

Da man mit $ \neg\; $ und $ \or\; $ alle Wahrheitsfunktionen aufbauen kann, reicht es zu zeigen, dass man diese Funktionen mit $ \neg\; $ und $ \rightarrow\; $ simulieren kann um alle Wahrheitsfunktionen zu erhalten.

Da das $ \neg\; $ verwendet werden darf, muss nur das $ \or\; $ simuliert werden:

$ F\; $	$ G\; $	$ (F \or G)\; $	$ (\neg F \rightarrow G)\; $
w	w	w	w
w	f	w	w
f	w	w	w
f	f	f	f

Jetzt den Algorithmus spezifizieren (z.B. analog zum Klauselform-Algorithmus., siehe Beweis zu Satz 3.23) und dann zeigen, dass der Algorithmus. korrekt ist und terminiert (sollte vermutlich in der Klausur nur angedeutet werden).

b)

$ F = ((p \and q) \or \neg ((p \or \neg q) \and p))\; $
$ \equiv (\neg (p \and q) \rightarrow \neg ((p \or \neg q) \and p))\; $
$ \equiv ((\neg p \or \neg q) \rightarrow (\neg (p \or \neg q) \or \neg p))\; $
$ \equiv ((p \rightarrow \neg q) \rightarrow ((p \or \neg q) \rightarrow \neg p))\; $
$ \equiv ((p \rightarrow \neg q) \rightarrow ((\neg p \rightarrow \neg q) \rightarrow \neg p))\; $

4. Alternativen/Diskussion/Hinweise etc.

---

zur Klausur 08.02.2003
Aufgaben-Kategorie AL - Äquivalenz und NormalformenAufgaben-Kategorie Sonstige