Unterschied zwischen KNF und KKNF?
Was ist der Unterschied zwischen KNF (Konjunktive Normalform) und KKNF (Kanonische Konjunktiven Normalform). Gleiches gilt für DNF und KDNF
1 Antwort
Zuerst:
Disjunktion -> ODER
Konjunktion -> UND
Kanonische Normalform bedeutet, dass in den Termen der booleschen Gleichung alle Variablen vorkommen, auch wenn sie sich "wegkürzen" würden.
Nehmen wir als Beispiel ein ODER-Gatter mit zwei Eingängen A und B sowie dem Ausgang Q. Die Wahrheitstabelle würde wie folgt aussehen:
A B Q
0 0 0
0 1 1
1 0 1
1 1 1
Wenn du jetzt die Gleichung für den Ausgang Q aufschreibst, indem du jede Zeile mit Q = 1 berücksichtigst, entsteht:
Das ist eine kanonische Normalform, und zwar eine kanonische, disjunktive Normalform -> KDNF. Disjunktiv bedeutet, dass die UND-Terme ODER verknüpft sind.
Muster: "B und C" oder "B und nicht C" oder ".. und .." usw.
KDNF -> ODER-Verküpfung von UND-Termen.
Eine Kanonische, konjunktive Normalform ist das Gegenteil einer KDNF. Man spricht auch vom sog. "Maxterm". Die lässt sich auch aus der KDNF (auch Minterm genannt) konstruieren, indem man die KDNF negiert und bei den Verknüpfungen dann auftrennt.
KKNF -> UND-Verknüpfung von ODER-Termen.
Muster: "B oder C" und "B oder nicht C" und ".. oder .." usw.
Eine DNF oder KNF ist prinzipiell genau das gleiche, nur dass hier die Terme eben nicht zwangsweise aus allen Variablen bestehen.
Nehmen wir als Beispiel die obere Gleichung für Q. Man sieht, dass die negierten Variablen unnötig sind. Der Ausgang Q kommt, solange A oder B eine 1 hat, egal welchen Wert dabei die jeweilig andere Variable hat. Also:
Diese Gleichung hat in den Termen jetzt nicht mehr alle Variablen aufgeführt. Deshalb ist sie nicht mehr kanonisch. Aber sie ist weiterhin in disjunktiver Form.
Ich küsse doch dein Herz, die "Hilfreichste Antwort" hast du dir definitiv verdient.