Übungsblatt 7

Bei Aufgabe 3
b) Geben Sie für die Funktion a einen vollständig geklammerten Booleschen Ausdruck e in disjunktiver Normalform mit Variablen aus V = {f ,w, z, k} an. Lassen Sie dabei ausnahmsweise keine Klammern und Operatorenzeichen vereinfachend weg. Zeigen Sie außerdem,
daß gilt: Psi(e) = a.

c) Bestimmen Sie auch die Darstellung von a in kanonischer DNF. Hier dürfen wieder wie gewohnt Klammern und Operatorzeichen weggelassen werden, wenn sich dadurch keine Mehrdeutigkeiten ergeben.

d) Neben der kanonischen DNF gibt es auch die kanonische konjunktive Normalform (KNF). Diese besteht aus einer Konjunktion vollständiger Klauseln, wobei man eine (vollständige) Klausel aus einem (vollständigen) Monom dadurch erhält, dass man überall ”^“ (bzw. ”·“) durch ”_“
(bzw. ”+“) substituiert. Bestimmen Sie für a nun noch eine Darstellung in kanonischer KNF.

Ich habe nun eine DNF erstellt (vollständig geklammert) wie in b) verlangt ist(Alle Minterme genommen die für a=1). Jedoch stellt sich mir die Frage wie sich die "kanonischer DNF" davon unterscheidet, und was ich machen muss um eine "kanonische konjunktive Normalform(KNF) zu bekommen. Muss ich jedes "+" in "*" und jedes "*" in "+" und dazu noch die negierten/unnegierten Variablen invertieren ?

thx im voraus

Simon

Eine Normalform ist kanonisch, wenn in jedem Minterm/Maxterm alle überhaupt vorkommenden Variablen enthalten sind.

Beispiel: (Variablen sind x1, x2)
(x1 * ~x2) + x2: ist eine DNF, aber nicht kanonisch.
(x 1* ~x2) + (x1 * x2) + (~x1 * x2): ist eine kanonische DNF
Beide Ausdrücke berechnen die gleiche Funktion f.

Was die Umwandlung von DNF in KNF angeht: Das macht man genauso, wie du es beschrieben hast.


Gruß
Bettina


---------------------------
Wer lesen kann, ist klar im Vorteil.



Edited 1 time(s). Last edit at 12/10/2005 05:24PM by braitlin.