NNF und KNF Aussagen. Gegeben ist die Formel ψ = (¬A → (D ∧ E))) → ¬(¬E ∧ B)

Question

a) Gegeben sei die Formel ψ = (¬A → (D ∧ E))) → ¬(¬E ∧ B). Formen Sie ψ schrittweise um in

• eine äquivalente Formel ψ´ in NNF,
• sowie eine äquivalente Formel ψ" in KNF.
Verwenden Sie dazu die Äquivalenzumformungen. Geben Sie bei jedem Schritt an,
welche Äquivalenzumformung Sie anwenden. 

b) Wir betrachten nun die Formel ϕ = (¬(A → B)∨(A∧B)) → A.

Mit Hilfe einer Wahrheitstabelle lässt sich leicht zeigen, dass ϕ eine Tautologie ist, also, dass ϕ ≡ > gilt.                              Zeigen Sie diese Äquivalenz unter Verwendung der Äquivalenzumformungen. Begründen Sie für jeden Schritt, warum die Äquivalenz gilt.

Comments

https://www.stacklounge.de/5029/nnf-und-knf-aussagen-gegeben-ist-die-formel-a-d-e-e-b ein Duplikat oder nicht? 

Theoretische Informatik oder Mathematik?

---

Es ist die informatik.

Answer 1

Aloha :)

Ich verwende \(\cdot\) anstelle von \(\land\) und \(+\) anstelle von \(\lor\), außerdem soll AND Vorrang vor OR haben, also \(\cdot\) vor \(+\), wie man es gewohnt ist (das spart Klammern). Die Implikation \(A\to B\) ist gleichbedeutend mit \(\overline A+B\), weil man aus etwas Wahrem nichts Falsches folgern kann. Damit vereinfachen wir zunächst die Funktion:

$$\Psi=\left(\overline A\to DE\right)\to\overline{\overline EB}=\left(\overline{\overline A}+DE\right)\to\left(\overline{\overline E}+\overline B\right)=$$$$\phantom{\Psi}=\left(A+DE\right)\to\left(E+\overline B\right)$$$$\phantom{\Psi}=\overline{A+DE}+(E+\overline B)=\overline A\cdot\overline{DE}+E+\overline B=\overline A\cdot\left(\overline D+\overline E\right)+E+\overline B$$$$\phantom{\Psi}=\overline A\cdot\overline D+\overline A\cdot\overline E+E+\overline B=\overline A\cdot\overline D+\overline A\cdot\overline E+(\overline A+A)E+\overline B$$$$\phantom{\Psi}=\overline A\cdot\overline D+\overline A\cdot(\overline E+E)+AE+\overline B=\overline A\cdot\overline D+\overline A+AE+\overline B$$$$\phantom{\Psi}=\overline A\cdot(\overline D+1)+AE+\overline B$$$$\phantom{\Psi}=\overline A+\overline B+AE$$

Das kann man tabellarisch darstellen:

A	B	D	E	Ergebnis	Klausel
0	0	0	0	1	\(\overline A\cdot\overline B\cdot\overline D\cdot\overline E\)
0	0	0	1	1	\(\overline A\cdot\overline B\cdot\overline D\cdot E\)
0	0	1	0	1	\(\overline A\cdot\overline B\cdot D\cdot\overline E\)
0	0	1	1	1	\(\overline A\cdot\overline B\cdot D\cdot E\)
0	1	0	0	1	\(\overline A\cdot B\cdot\overline D\cdot\overline E\)
0	1	0	1	1	\(\overline A\cdot B\cdot\overline D\cdot E\)
0	1	1	0	1	\(\overline A\cdot B\cdot D\cdot\overline E\)
0	1	1	1	1	\(\overline A\cdot B\cdot D\cdot E\)
1	0	0	0	1	\(A\cdot\overline B\cdot\overline D\cdot\overline E\)
1	0	0	1	1	\(A\cdot\overline B\cdot\overline D\cdot E\)
1	0	1	0	1	\(A\cdot\overline B\cdot D\cdot\overline E\)
1	0	1	1	1	\(A\cdot\overline B\cdot D\cdot E\)
1	1	0	0	0	\(\overline A+\overline B+D+E\)
1	1	0	1	1	\(A\cdot B\cdot\overline D\cdot E\)
1	1	1	0	0	\(\overline A+\overline B+\overline D+E\)
1	1	1	1	1	\(A\cdot B\cdot D\cdot E\)

Alle blauen Klauseln zum Ergebnis \(0\) ergeben die KNF:$$\Psi=(\overline A+\overline B+D+E)\cdot(\overline A+\overline B+\overline D+E)$$Alle schwarzen Klauseln zum Ergebnis \(1\) ergeben die DNF:$$\Psi=\overline A\cdot\overline B\cdot\overline D\cdot\overline E+\overline A\cdot\overline B\cdot\overline D\cdot E+\overline A\cdot\overline B\cdot D\cdot\overline E+\cdots$$

Comments

Danke für die schöne Antwort, nur habe ich bei der Frage ein Klammer vergessen aber trotzdem kann ich mit dieser Antwort mein Fehler selbst korrigieren.