Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Kanonische Disjunktive Normalform

Kanonische Disjunktive Normalform

Universität / Fachhochschule

Tags: Aussagenlogik, Normalform (p->q)->r))^((p->q)->r)

Satego85 aktiv_icon

11:38 Uhr, 17.10.2010

Hallo an das Mathe Forum.

Ich habe hier eine Aufgabe zur Aussagenlogik, genauer gesagt zur

"Kanonischen" Disjunktiven Normalform".

Folgende Aussage soll in die Kanoische Disjunktive Normalform geführt werden:

(p \to (q \to r)) \land ((p \to q) \to r)

Mit der Wertetabelle komme ich auf die Lösung, nur ich habe Schwierigkeiten beim hinführen in die Normalform.

Der 1. Schritt, die Implikation auflösen, ist auch noch kein Problem.

Für eure Hilfe zum Lösungsweg wäre ich sehr dankbar.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

teppich aktiv_icon

18:50 Uhr, 18.10.2010

Eine boolsche Funktion f liegt in disjunktiver Normalform vor, wenn die Formel eine Disjunktion von Konjunktionen von Literalen ist.
Also

f = \underset{i}{⋁} (\underset{j}{⋀} x_{i, j})

gilt. (

x_{i, j}

darf hierbei natürlich auch negiert sein)
Die kanonische Diskunktive Normalform ist eine Normalform, bei der in jedem Konjunktionsterm alle Variablen genau einmal vorkommen.
(Die KDNF ist eindeutig. Die Konjunktionsterme sind gerade die Minterme der Funktion.)

Der erste Schritt ist also eine Überführung der Funktion f in diskjunktive Normalform. Also soweit wie möglich vereinfachen und zusammenfassen

\begin{array}{rcl} f & = & (p \Rightarrow (q \Rightarrow r)) & \land & ((p \Rightarrow q) \Rightarrow r) \\ = & (\bar{p} \lor (\bar{q} \lor r)) & \land & (\bar{(\bar{p} \lor q) \lor r)} \\ = & (\bar{p} \lor \bar{q} \lor r) & \land & ((p \land \bar{q}) \lor r) \\ = & (\bar{p} \land ((p \land \bar{q}) \lor r)) & \lor & (\bar{q} \land ((p \land \bar{q}) \lor r)) & \lor & (r \land ((p \land \bar{q}) \lor r)) \\ = & (\bar{p} \land (p \land \bar{q})) \lor (\bar{p} \land r) & \lor & (\bar{q} \land p \land \bar{q}) \lor (\bar{q} \land r) & \lor & (r \land p \land \bar{q}) \lor (r \land r) \\ = & 0 \lor (\bar{p} \land r) & \lor & (p \land \bar{q}) \lor (\bar{q} \land r) & \lor & (p \land \bar{q} \land r) \lor (r) \end{array}

Dies ist bereits eine DNF. Um von hier zu einer KDNF zu kommen, müssen in jedem Konjunktionsterm alle Variablen einmal vorkommen. Das erreichen wir, indem wir jede fehlende Variable einmal negiert und einmal nicht negiert hinzufügen:
So wird beispielsweise durch ergänzen von

q

bzw.

\bar{q}

aus

(\bar{p} \land r) = (\bar{p} \land q \land r) \lor (\bar{p} \land \bar{q} \land r)

. Fehlen mehrere, so ist es möglich alle Kombinationen der fehlenden Variablen zu ergänzen, oder Schrittweise jeweils eine:

(r) = (p \land r) \lor (\bar{p} \land r) = (p \land q \land r) \lor (p \land \bar{q} \land r) \lor (\bar{p} \land q \land r) \lor (\bar{p} \land \bar{q} \land r)

Formen wir alle Konjunktionsterme derart um, so erhalten wir bereits die DKNF.

Satego85 aktiv_icon

20:22 Uhr, 18.10.2010

Die Rettung des heutigen Abend! Ich danke vielmals für die ausführliche Erklärung. Hat mir sehr weiter geholfen.

805674

805006

	Status: nicht eingeloggt	Noch nicht registriert?