DNF und KNF aus Logikgatter oder KV-Diagramm

[Maren K. (maren_knappig)]

Hallo Zusammen,

ich habe einmal eine Prinzipelle Frage zu der DNF und KNF Form.

Meines Wissens nach gelangt man am schnellsten zur disjunktiven 
Normalform, wenn man alle Zeilenkombinationen der Wahrheitstabelle 
herausgreift, bei der die Ausgangsvariable den Wert 1 annimmt. Alle 
Eingangsvariablen jeder Zeile werden in Eigenform (falls der Wert 1 ist) 
oder negierter Form (falls der Wert 0 ist) konjunktiv verknüpft. Die 
sich so ergebenden Vollkonjunktionen oder Minterme werden disjunktiv 
verknüpft.

In anderen Quellen wird die DNF als eine Art "ausgeklammerte" Form der 
Logikfunktion dargestellt, bei der die diskunktiv verknüpften 
Teilfunktionen jeweils nicht jede Eingangsvariable enthalten müssen.

Beispiel:

Eingangsvariablen x0,x1,x2,x3 muss die DNF nun in jeder Teilfunktion 
immer und ausnahmslos alle Eingangsvariablen enthalten?

oder wäre y= x0^x1^x2^x3 v -x0^x1^-x3 ebenfalls eine DNF?


Zudem frage ich mich, wie ich aus dem KV Diagramm direkt auf eine 
@@minimierte@@@ Form der DNF schließen kann. Was ist in diesem 
Zusammenhang mit minimiert gemeint?

Ich habe einmal zwei Wege in die PDF Datei eingefügt, die ich gegangen 
bin. Allerdings habe ich zwei unterschiedliche Ergebnisse raus. Ich bin 
mir nicht ganz sicher, was nun richtig ist. Könnten Sie mir auf die 
Sprünge helfen? Bei der KNF sehe ich es genau umgekehrt. Dabei müssen 
die Eingangsvariablen Verknpüft werden bei der die Ausgangsvariable den 
Wert 0 annehmen, ist das richtig? Allerdings würde mich hier auch die 
Vereinfachungsstrategie interessieren.

[Egon D. (Gast)]

Maren K. schrieb:

> Eingangsvariablen x0,x1,x2,x3 muss die DNF nun
> in jeder Teilfunktion immer und ausnahmslos alle
> Eingangsvariablen enthalten?

Nein.

Es gibt im Allgemeinen viele (verschiedene) Normal-
formen für dieselbe logische Funktion, aber die
spezielle Normalform, die in jedem Teilterm alle
Variablen enthält, ist eindeutig -- sie wird wegen
dieses Alleinstellungsmerkmals "kanonische
Normalform" genannt.


> oder wäre y= x0^x1^x2^x3 v -x0^x1^-x3 ebenfalls
> eine DNF?

Ja.


> Zudem frage ich mich, wie ich aus dem KV Diagramm
> direkt auf eine @@minimierte@@@ Form der DNF schließen
> kann. Was ist in diesem Zusammenhang mit minimiert
> gemeint?

Eine "möglichst einfache" Gleichung -- wobei dieses
"möglichst einfach" nicht allgemeingültig definiert
ist.


> Ich habe einmal zwei Wege in die PDF Datei eingefügt,
> die ich gegangen bin. Allerdings habe ich zwei
> unterschiedliche Ergebnisse raus.

Naja, da Du einmal die Funktion für Y und einmal für
/Y aufgeschrieben hast, ist es kein Wunder, dass die
Terme verschieden aussehen. Wahrscheinlich sind sie
identisch, wenn Du einen nach deMorgan umformst.


> Bei der KNF sehe ich es genau umgekehrt. Dabei müssen
> die Eingangsvariablen Verknpüft werden bei der die
> Ausgangsvariable den Wert 0 annehmen, ist das richtig?

Habe ich sehr lange nicht gemacht :)
Ich glaube schon, ja.


> Allerdings würde mich hier auch die
> Vereinfachungsstrategie interessieren.

Darüber sind ganze Bücher geschrieben worden. Rein
pragmatisch gesehen kann man mit der Gleichung, der
Wahrheitswertetabelle, Binär-/Ternärvektorlisten oder
dem Karnaugh-Veitch-Diagramm arbeiten. KV-Diagramm
klappt mit Übung bis 6 Variablen und ist am beliebtesten.
Die Listenalgorithmen funktionieren für fast beliebig
viele Variablen und lassen sich gut vom Rechner ausführen,
sind aber für Handrechnung nur bedingt geeignet.
Beliebt ist Minimierung nach Quine/McClusky; müsste ich
mich aber erst wieder einlesen.

[Maren K. (maren_knappig)]

Super vielen Dank für deinen Hinweis mit y und /y. Ich habe habe die 
Übersicht verloren. Nun habe ich alles gelöst denke ich. Ich weiß auch 
jetzt, dass die KDNF die Form ist, bei der alle Eingangsvariablen in 
jeder Teilfunktion enthalten sein müssen.