Mit dem schematischen Vorgehen beim Ermitteln der KNF bzw. DNF erhält man zwar korrekte logische Terme, häufig sind diese jedoch lang und unhandlich.

Wie kann man effizient kurze Terme zu logischen Funktionen aus ihren Wahrheitstafeln erhalten?

Eine Methode dafür sind sogenannte "KV-Diagramme", benannt nach den nach Maurice Karnaugh und Edward W. Veitch (1952/53).

Wir starten bei einer logischen Funktion, deren Wahrheitstafel gegeben ist:

Als erstes überführt man die Wertetabelle in eine Matrix: An den Seiten stehen die Variablen und alle möglichen Werte (also jeweils "wahr/1" und "falsch/0"). Im Inneren der Matrix wird für die jeweiligen Kombinationen der Eingabewerte der Funktionswert eingetragen:

Nun sucht man in den Funktionswerten nach möglichst großen, zusammenhängenden rechteckigen Bereichen, die aus "wahr"-Werten (also "Einsen") bestehen.

• Wir müssen alle wahr Werte einbeziehen
• Es sind einige Regeln zu beachten, dazu später mehr.

Eine Möglichkeit für das gegebene Beispiel ist folgende:

Jetzt kann man gut ablesen, welche logischen Bedingungen jeweils die farbig markierten "wahr"-Werte festlegen:

• Grün: A ist 0, B ist egal - die logische Bedingung, um alle "grünen" Einsen zu erhalten, lautet also $\lnot A$.
• Rot: A ist 1, B ist 0 - die Bedingung ist also $A \land \lnot B$.
• Um alle "wahr"-Werte des Diagramms zu erhalten, muss man diese beiden Bedingungen mit "oder" verknüpfen - ein korrekter logischer Ausdruck für die gegebene Wahrheitstafel ist also $(A \land \lnot B) \lor (\lnot A)$.

Ei der Regeln, die man anwenden kann ist, dass sich die rechteckigen Bereiche überlappen dürfen - dann wird durch die oder Verknüpfung aller Teilausdrücke am Ende zwar gelegentlich eine "1" mehrfach erfasst, der logische Ausdruck wird aber einfacher, da man weniger Bedingungen benötigt, um die Bereiche zu adressieren.

• Grün: A ist 0, B ist egal - die logische Bedingung, um alle "grünen" Einsen zu erhalten, lautet also $\lnot A$.
• Rot: B ist 0, A ist egal - die Bedingung ist jetzt also $\lnot B$ - das ist kürzer als beim ersten Versuch!
• Um alle "wahr"-Werte des Diagramms zu erhalten, muss man diese beiden Bedingungen mit "oder" verknüpfen - ein korrekter logischer Ausdruck für die gegebene Wahrheitstafel ist also $(\lnot A) \lor (\lnot B)$.

Wie angesprochen muss man bei der Auswahl der zusammenhängen Bereiche mit Einsen einige Regeln beachten:

Da man nun 3 Eingabevariablen hat, muss man bei der Darstellung in einer zweidimensionalen Matrix zu einem kleinen "Trick" greifen:

Man schreibt die Kombination zweier Variablen auf eine Achse der Matrix, die dritte Variable auf die andere Achse:

Damit erhält man für die gegebene Wahrheitstafel die folgende Matrix mit den markierten Rechtecken. Man sieh auch nochmal: Die drei benachbarten "wahr" Werte können nicht zu einem Rechteck zusammengefasst werden ¹⁾, aber man kann zwei überlappende Rechtecke mit jeweils 2 Einsen bilden.

Nun ermitteln wir die Ausdrücke für die drei rechteckigen Bereiche:

• Rot: Ist der kleinste Bereich, für diesen benötigt man die meisten Bedingungen, hier: $\lnot x_1 \land \lnot x_2 \land x_3$
• Blau: $x_2 \land \lnot x_3$ ($x_1$ ist egal)
• Grün: $x_1 \land \lnot x_3$ ($x_2$ ist egal)
• Alle drei Bereiche durch "oder" verknüpft: $(\lnot x_1 \land \lnot x_2 \land x_3) \lor (x_2 \land \lnot x_3) \lor (x_1 \land \lnot x_3)$

Bei logischen Funktionen mit 4 Eingangsvariablen geht man genauso vor, wie bei solchen mit 3 Variablen - jetzt stehen auf beiden Achsen jeweils die Kombination zweier Variablen. Dabei ist auch die Regel zu beachten, dass man jeweils nur ein Bit zwischen den benachbarten Kombinationen verändern darf.

Lies die Funktionswerte für die Eingabewerte 1010, 1110 und 0101 aus der Matrix ab.

Lösung

Suche in der Matrix möglichst große, regelkonforme zusammenhängende Bereiche mit "wahr"-Werten und ermittle einen möglichst einfachen logischen Ausdruck für die gegebene Funktion. Denke daran, dass die Bereiche auch "über die Ränder hinaus" gebildet werden können.

Lösungshinweis - Bereiche

Lösungshinweis - Logische Ausdrücke

Lösungsvorschlag