Blatt 7 - KNF vs KDNF

Hallo zusammen,
wahrscheinlich ne ganz blöde Frage, aber wo liegt der Unterschied zwischen KNF und KDNF. Im Script wird KDNF als kanonische disjunktive Normalform übersetzt, aber KNF???
Wenn ich gerade dabei bin:
OBDD, also BDD kenn ich, das sind Binary Decision Diagrams und für was steht denn jetzt das "O"??
Was hat man unter Variablenordnung zu verstehen? Soll das die Reihenfolge sein, in der die Variablen im BDD abgeprüft werden?

Danke schonmal für etwas Hilfe

Norbert

Also

OBDD = ordered binary decision diagrams; sprich geordnete BDD´s. Heißt also man soll hier ein reduziertes, geordnetes BDD formen.

Die Variablenordnung ergibt sich dann ja eigentlich, denn bei den geordneten BDD´s ist es dann ja so, dass man da ne bestimmte reihenfolge hat.
Also ganz oben stehen die x1, drunter die x2 und dann die x3.

KNF heißt zwar Kanonische NormalForm
was damit aber gemeint ist, weiß ich auch net so wirklich.

... (wenn ich das richtig in Erinnerung habe), daß aus Konvention zu OBDDs oft auch nur noch BDDs gesagt wird...

KNF bedeutet:
Konjunktive Normalform

DNF war:
Disjunktive Normalform

kDNF war die kanonische DNF

ebenso gibts auch kKNF!

Eigentlich gibt es in der Interpretation keinen Unterschied. Eine KNF ist eine Formel die eine große Disjkuntion (OR Verknüpfung) von Disjunktionen (AND Verknüpfung) von Monomen. Eine kanonische Darstellung ist mehr oder wenig die Definition der Funktion, das kannst du dir vorstellen als die gar nicht gekürzte Form einer Formel. Erst durch Quine-McCluskey und/oder andere Verfahren erhalten wir eine reduzierte Form, die nicht mehr kanonisch ist, die jedoch das gleiche aussagt, wie die große Formel. Als kanonisch kannst du dir die voll geklammerte boolsche Funktion der Aufgabe des Farmers auf dem Blatt 6.

... von Disjunktionen (AND Verknüpfung) ...

Du meinst wohl Konjunktionen :)