0 Daumen
1k Aufrufe

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.

Avatar von

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.

1 Antwort

+5 Daumen

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$$

Avatar von

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community