====== Vereinfachung von logischen Funktionen mit KV-Diagrammen ====== 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 **K**arnaugh und Edward W. **V**eitch (1952/53). ===== Beispiel 1: Zwei Variablen ===== Wir starten bei einer logischen Funktion, deren Wahrheitstafel gegeben ist: {{ :faecher:informatik:oberstufe:techinf:formale_logik:kv_diagramme:2024-09-25_11-47.png |}} ==== Schritt 1: Wertetabelle als Matrix ==== 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: {{ :faecher:informatik:oberstufe:techinf:formale_logik:kv_diagramme:kv01.png |}} ==== Schritt 2: Zusammenhängende "wahr"-Bereiche finden ==== 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|Regeln]] zu beachten, dazu später mehr. Eine Möglichkeit für das gegebene Beispiel ist folgende: {{ :faecher:informatik:oberstufe:techinf:formale_logik:kv_diagramme:kv03.png |}} 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)$. ==== Ergänzung: Überlappende Bereiche sind erlaubt ==== 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. {{ :faecher:informatik:oberstufe:techinf:formale_logik:kv_diagramme:kv05.png |}} * 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)$. ====== Regeln ====== Wie angesprochen muss man bei der Auswahl der zusammenhängen Bereiche mit Einsen einige Regeln beachten: - Die **Bereiche** müssen **rechteckig** sein - Die Rechtecke dürfen sich **überlappen** (müssen aber nicht). - Die **Anzahl der Einsen** in einem Rechteck muss eine **Zweierpotenz** sein - also 1, 2, 4, 8 oder 16. - Rechteckige Bereiche können auch "**über die Ränder hinaus**" bestehen. ===== Beispiel 2: Drei Variablen ===== {{ :faecher:informatik:oberstufe:techinf:formale_logik:kv_diagramme:kv06.png |}} ==== Schritt 1: Wertetabelle als Matrix ==== 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: {{ kv07.png |}} ==== Schritt 2: Zusammenhängende "wahr"-Bereiche finden ==== 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 ((Keine Zweierpotenz!)), aber man kann zwei überlappende Rechtecke mit jeweils 2 Einsen bilden. {{ kv08.png |}} 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)$ ===== Beispiel 3: Vier Variablen ===== 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. {{ :faecher:informatik:oberstufe:techinf:formale_logik:kv_diagramme:2024-09-27_14-53.png |}} ---- {{:aufgabe.png?nolink |}} === (A1) === Lies die Funktionswerte für die Eingabewerte 1010, 1110 und 0101 aus der Matrix ab. ++++ Lösung | {{ :faecher:informatik:oberstufe:techinf:formale_logik:kv_diagramme:kv10.png |}} ++++ ---- {{:aufgabe.png?nolink |}} === (A2) === 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 | Denkbare Bereiche sehen so aus: {{ :faecher:informatik:oberstufe:techinf:formale_logik:kv_diagramme:kv11.png |}} ++++ ++++ Lösungshinweis - Logische Ausdrücke | * Grün: $\lnot x_3 \land x_4 \land x_2$ * Blau: $x_1 \land \lnot x_3$ * Orange: $\lnot x_1 \land x_3 \land \lnot x_4$ ++++ ++++ Lösungsvorschlag | $f=(\lnot x_3 \land x_4 \land x_2) \lor (x_1 \land \lnot x_3) \lor (\lnot x_1 \land x_3 \land \lnot x_4)$ ++++ ---- {{simplefilelist>.:*}}