Logik:Klausuren/08.02.2003/2.8 Aufgabe

Aus Tudwiki
Wechseln zu: Navigation, Suche

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))\; $

3. Lösungsweg

4. Alternativen/Diskussion/Hinweise etc.


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