Gegeben: eine Funktion, die mit Hilfe von KV-Diagrammen minimiert werden soll.
„-“ steht für „NICHT“, ansonsten verwende ich „AND“, „OR“
g= -(a AND -b AND d) AND d OR -(a AND b AND c AND -d) AND c AND -d OR -a AND -b AND -c AND -d
Wie geht man denn jetzt am besten vor? Ich weiß z.B., dass man jetz die disjunktive Normalform oder die konjunktive Normalform bildet, diese in ein KV-Diagramm einträgt und dann minimiert, um das Ergebnis zu erhalten.
Allerdings fällt es mir schwer, die angegebene Funktion so zu vereinfachen, dass ich sie ins KV-Diagramm eintragen kann, sprich eine Normalform zu erzeugen.
Wer kennt sich mit sowas aus und kann helfen?
Vielen Dank im voraus…
Hi Ralf,
ich glaub die Frage gehört eher ins Informatik Forum, aber das nur am Rande.
Am Anfang minimiert man am besten durch scharfes hingucken. Generell gilt ja sowas wie 1 AND -1 = 0, oder 1 OR -1 = 1. Sachen die mehrmals vorkommen kann man natürlich weglassen, so daß sie nur noch einmal da stehen, z.B. AND -d in Deiner Funktion.
Bei der konjunktiben Normalform hast Du eine Reihe von Termen die alle durch ein AND verknüpft sind: (a OR b) AND © AND (d XOR e) …
Bei der disjunktiven Normalform sind die Terme durch ORs verknüpft: (a) OR (b AND c) OR …
Man kann die Formen ineinander überführen durch doppeltes negieren und einmal auflösen. Die wichtigste Regel dabei ist die deMorgansche, oder wie die doch gleich hies:
-(a AND b) = -a OR -b, bzw.
-(a OR b) = -a AND -b
Jetzt musst Du also die gegebene Funtion in eine Normalform umwandeln. Ich finde die konjunktive etwas intuitiver, und es war auch die während meiner Vorlesungen häufiger Benutzte Variante. Wichtig ist noch das Äquivalten zu „Punkt- vor Strichrechnung“ also AND vor OR. Als Schreibweise wurde bei uns auch * als AND und + für OR benutzt, auch um die Ähnlichkeit zur Multiplikation und Addition zu verdeutlichen.
Ausdrücke wie a AND (b OR c) kannst Du ja zu (a AND b) OR (a AND c) erweitern, bzw. ausmultiplizieren.
Aus -(a AND -b AND d) wird dann:
(-a OR b OR d)
Das mit dem nächsten term (AND d) multiplizieren:
-a AND d OR b AND d OR d AND d
Und siehe da, d AND d ist immer 1:
-a AND d OR b AND d OR 1 = 1
Somit fällt der Term schon mal raus, da ja 1 AND x = x gilt.
Das machst Du mit den restlichen Termen bis Du eine Normalform erhälst. Die kannst Du dann in Dein KV-Diagramm eintragen und minimieren.
Hoffe das hilft Dir erstmal zur Normalform. Meld Dich einfach wieder wenn noch was unklar ist.
Gruß,
Ferdinand.
erstmal vielen Dank für deine Hilfe.
ich hab noch nicht ganz verstanden, warum -(a AND -b AND d) = (-a OR b OR d) sein soll. Wenn ich da doch de Morgan anwende, müsste es nicht heißen -(a AND -b AND d) = (-a OR b OR -d )???
MOD: Überflüssiges Vollzitat gelöscht.
Hi Ralf,
wie ein Kollege bei einem Praktikum mal sagte: Du bist so gescheit! 
ich hab noch nicht ganz verstanden, warum -(a AND -b AND d) =
(-a OR b OR d) sein soll. Wenn ich da doch de Morgan anwende,
müsste es nicht heißen -(a AND -b AND d) = (-a OR b OR
-d )???
Hast völlig recht, müsste -d sein. Kannst es schon besser als ich 
Gruß,
Ferdinand
Hallo, Ferdinand!
Naja, jetz versuch ich halt mal durch Umformungen zu vereinfachen…
-(a AND -b AND d) AND d OR -(a ANd b AND c AND -d) AND c AND -d OR -a AND -b AND -c AND -d =
= -a OR b OR -d AND d OR -a OR -b OR -c OR d AND c AND -d OR -a AND -b AND -c AND -d
nach dem Komplementgesetz „x AND -x = 0“ hab ich jetz im Prinzip da stehen:
-a OR b OR „0“ …
nach dem "NULL- und EINS-Gesetz „0 OR a = a“ folgt doch jetz daraus:
-a OR b OR „0“=-a OR b, richtig???
Ich mach mal an der Stelle mit den Umformungen weiter:
Also:
…= -a OR b OR -a OR -b OR -c OR d AND -d AND c OR -a AND -b AND -c AND -d (im fett marikerten Teil habe ich sozusagen das Kommutativgesetz angewendet)
Wenn das so ok, ist kann ich doch jetz wieder was vereinfachen, dank dem Einsgesetz „d AND -d= 0“, also folgt doch:
…= -a OR b OR -a OR -b OR -c OR 0 AND c OR -a AND -b AND -c AND -d
weiter: (Anwendung von Kommutativ, 0-1-Gesetze, Komplementgesetz)
… = -a OR b OR -a OR -b OR -c AND c OR -a AND -b AND -c AND -d
= -a OR -a OR b OR -b OR -c AND c OR -c AND -a AND -b AND -d
= -a OR 1 OR 0 OR -c AND -a AND -b AND -d
= 1 OR 0 OR -c AND -a AND -b AND -d
Was mach ich denn jetzt damit? vermutlich sind ein paar Fehler drin und ich weiß nicht wo. Andere Frage wäre, was bringt es jetzt noch, wenn ich schon soweit umgeformt habe, das alles noch ins KV-Diagramm einzutragen? Ich fürchte, viel Minimierung gibts da nicht mehr… aber Minimierung mit Hilfe des KV’s war ja die eigentliche Aufgabenstellung…
Vielen Dank für deine Bemühungen…
Mit freundlichen Grüßen,
Ralf
MOD: Überflüssiges Zitat gelöscht.
Moin Ralf,
Bei Deinen Umformungen hast Du vergessen/übersehen, dass die Klammern erhalten bleiben :-/
-(a AND -b AND d) AND d OR -(a ANd b AND c AND -d) AND c AND
-d OR -a AND -b AND -c AND -d =
Ich schreib das mal grad etwas anders:
-(a -b d) d + -(a b c -d) c -d + -a -b -c -d
Jetzt die Klammern nach deMorgan behandeln (Klammeung bleibt!):
(-a + b + -d) d + (-a + -b + -c + d) c -d + -a -b -c -d
Jetzt das ganze durchmultiplizieren:
-a d + b d + -d d + -a c -d + -b c -d + -c c -d + d c -d + -a -b -c -d =
-a b + b d + -a c -d + -b c -d + -a -b -c -d
Jetzt hast Du fünf disjunktiv verknüpfte Terme, bzw. eine DNF:
-a b
b d
-a c -d
-b c -d
-a -b -c -d
Diese kannst Du in ein KV-Diagramm eintragen. Sofern ich mich nicht verrechnet habe. Danach kannst Du das ganze minimieren indem Du passend Einsen und Nullen zusammenfasst.
Hoffe Du kannst nachvollziehen, was ich versucht habe zu rechnen.
Gruß,
Ferdinand
Hallo nochmal,
deine Umformungen habe ich soweit verstanden.
Ich habs mal nachfolzogen:
nach dem ausmultiplizieren heißt es bei mir: (alle besonders betrachteten Elemente kursiv)
-ad+bd+-dd±ac-d±bc-d+-cc-d+dc-d±a-b-c-d
und jetz nochmal langsam:
nach der Formel(x AND -x=0) bzw. (x OR -x=1) fällt jetz einiges weg, so dass dann da steht:frowning:-cc-d=0-d=0)
-ad+bd±ac-d±bc-d±d+dc-d±a-b-c-d
weiter:
-ad+bd±ac-d±bc-d+c±a-b-c-d
wegen (x AND 0 = 0)ist c=0, fällt also weg, also
-ad+bd±ac-d±bc-d±a-b-c-d
also hätte ich am Ende andere disjunkte Terme, wie du:
-ad+bd±ac-d±bc-d±a-b-c-d
Also lauten meine disjunkt verknüpften Endterme, wie bei dir:
-ad
bd
-ac-d
-bc-d
-a-b-c-d
Danke für deine Hilfe!
Ich probier jetz mal alles ins KV-Diagramm einzutragen und zu minimieren.
Kurze Frage habe ich noch: Die Aufgabenstellung lautet ja, mit Hilfe des KV-Diagramms zu minimieren. Ist es dann notwendig die konjunktiv minimierte Normalform und die disjunktiv minimierte Normalform zu bilden, oder reicht eines der beiden?
bis bald,
beste Grüße,
Ralf
MOD: Überflüssiges Vollzitat gelöscht.
Hi Ralf,
genau 
Gut, dass wir das gleiche raushaben, dann wird es wahrscheinlich stimmen.
Danke für deine Hilfe!
Gern geschehen.
Ich probier jetz mal alles ins KV-Diagramm einzutragen und zu
minimieren.
Kurze Frage habe ich noch: Die Aufgabenstellung lautet ja, mit
Hilfe des KV-Diagramms zu minimieren. Ist es dann notwendig
die konjunktiv minimierte Normalform und die disjunktiv
minimierte Normalform zu bilden, oder reicht eines der beiden?
Eine reicht. Du kannst natürlich die Gegenprobe machen. Die DNF gibt Dir ja die Einsen im Diagramm und die KNF die Nullen, es dürfte also keine Überlappung geben.
Wird aber nicht viel zu minimieren geben. Wenn ich das richtig gemacht hab hast Du nachher einen Term weniger.
So long,
Ferdinand
ok, ich hab mal DNF und KNF jeweils ins KV-Diagramm eingetragen. Is jetz natürlich etwas blöd, das hier darzustellen.
Ich versuch mal das Aussehen nach dem Eintragen der DNF ins KV-Diagramm zu beschreiben. Vielleicht hast du es ja auch so!
Also: es gibt ja bei 4 Elementen ein KV-Diagramm von 2^4 Kästchen, also 16 Kästchen. Dabei habe ich in der 1. und 4. (letzten) Spalte alles 1sen stehen, zusätzlich noch in der kompletten 3. Zeile und eine 1 in der 1. Zeile, 3.Spalte (alles jeweils von links nach rechts bzw. oben nach unten gelesen). Ich hoffe, du kannst mir folgen…
naja, jetz minimier ich das um die DMF (minimierte disj. NF) zu gewinnen:
DMF=-a+ac-d±ac±a-c+bd
=-a+ac-d±a(c±c)±a-c+bd
=-a+ac-d±a±a-c+bd (-a ist doppelt, fällt daher einmal raus, oder?)
also:
=-a+ac-d±a-c+bd
Ich hoffe, du hast das gleich raus…
Für die KMF betrachte ich alle Felder, in denen noch keine 1 im KV-Diagramm steht (sind quasi Nullen).
KMF=(-a+b+c)*(-a±b+d)*(-a+c+d)*(-a+b±d)
weiter kam ich allerdings nicht…
Bis bald,
Ralf
MOD: Überflüssiges Vollzitat gelöscht.