Lösung 8
Aufgabe 1
Gegeben ist die folgende WHT. Minimieren Sie diese nach den Regeln der boolschen Algebra. Nutzen Sie - wie in der Theorie gezeigt - die Idee der Substitution und folgende Gesetze:
- Kommutativgesetz
- Distributivgesetz
- Komplementärgesetz
- Neutralitätsgesetz
| IN | ¦ | OUT | ||
| A | B | C | ¦ | X |
|---|---|---|---|---|
| 0 | 0 | 0 | ¦ | 1 |
| 0 | 0 | 1 | ¦ | 0 |
| 0 | 1 | 0 | ¦ | 1 |
| 0 | 1 | 1 | ¦ | 0 |
| 1 | 0 | 0 | ¦ | 1 |
| 1 | 0 | 1 | ¦ | 0 |
| 1 | 1 | 0 | ¦ | 0 |
| 1 | 1 | 1 | ¦ | 1 |
Lösung als DNF
X = (\(\neg\)A\(\wedge\)\(\neg\)B\(\wedge\)\(\neg\)C) \(\vee\) (\(\neg\)A\(\wedge\)B\(\wedge\)\(\neg\)C) \(\vee\) (A\(\wedge\)\(\neg\)B\(\wedge\)\(\neg\)C) \(\vee\) (A\(\wedge\)B\(\wedge\)C)
Anwenden von Kommutativ-, Distributiv-, Komplementär- und Neutralitätsgesetz.
Wir stellen die Terme mittels Kommutativgesetz um, so dass wir ein „passendes“ Paar erkennen können…
X = (\(\neg\)A\(\wedge\)\(\neg\)B\(\wedge\)\(\neg\)C) \(\vee\) (A\(\wedge\)\(\neg\)B\(\wedge\)\(\neg\)C) \(\vee\) (\(\neg\)A\(\wedge\)B\(\wedge\)\(\neg\)C) \(\vee\) (A\(\wedge\)B\(\wedge\)C)
…und wenden das Distributivgesetz an. Dabei substituieren wir (gedanklich) den Term (\(\neg\)B\(\wedge\)\(\neg\)C).
(\(\neg\)A\(\wedge\)\(\neg\)B\(\wedge\)\(\neg\)C) \(\vee\) (A\(\wedge\)\(\neg\)B\(\wedge\)\(\neg\)C)
und erhalten ( \(\neg\)A\(\vee\)A) \(\wedge\) (\(\neg\)B\(\wedge\)\(\neg\)C) = 1 \(\wedge\) (\(\neg\)B\(\wedge\)\(\neg\)C) \(\Rightarrow\) (\(\neg\)B\(\wedge\)\(\neg\)C)
Wir stellen den Ausdruck erneut um und finden wieder ein Paar, auf das wir das Distributivgesetz anwenden können.
X = (\(\neg\)A\(\wedge\)\(\neg\)B\(\wedge\)\(\neg\)C) \(\vee\) (\(\neg\)A\(\wedge\)B\(\wedge\)\(\neg\)C) \(\vee\) (A\(\wedge\)\(\neg\)B\(\wedge\)\(\neg\)C) \(\vee\) (A\(\wedge\)B\(\wedge\)C)
Hier wird der Term (\(\neg\)A\(\wedge\)\(\neg\)C) (gedanklich) substituiert.
(\(\neg\)A\(\wedge\)\(\neg\)B\(\wedge\)\(\neg\)C) \(\vee\) (\(\neg\)A\(\wedge\)B\(\wedge\)\(\neg\)C) = (\(\neg\)B\(\wedge\)\(\neg\)A\(\wedge\)\(\neg\)C) \(\vee\) (B\(\wedge\)\(\neg\)A\(\wedge\)\(\neg\)C)
(\(\neg\)B\(\vee\)B) \(\wedge\) (\(\neg\)A\(\wedge\)\(\neg\)C) = 1 \(\wedge\) (\(\neg\)A\(\wedge\)\(\neg\)C) \(\Rightarrow\) (\(\neg\)A\(\wedge\)\(\neg\)C)
Der Term (A\(\wedge\)B\(\wedge\)C) kann mit keinem anderen Term minimiert werden und bleibt so stehen. Somit ergibt sich für die minimierte Lösung
X = (\(\neg\)B\(\wedge\)\(\neg\)C) \(\vee\) (\(\neg\)A\(\wedge\)\(\neg\)C) \(\vee\) (A\(\wedge\)B\(\wedge\)C)
Lösung als KNF
X = (A\(\vee\)B\(\vee\)\(\neg\)C) \(\wedge\) (A\(\vee\)\(\neg\)B\(\vee\)\(\neg\)C) \(\wedge\) (\(\neg\)A\(\vee\)B\(\vee\)\(\neg\)C) \(\wedge\) (\(\neg\)A\(\vee\)\(\neg\)B\(\vee\)C)
Anwenden von Kommutativ-, Distributiv-, Komplementär- und Neutralitätsgesetz.
Wir stellen die Terme mittels Kommutativgesetz um, so dass wir ein “passendes” Paar erkennen können…
X = (A\(\vee\)B\(\vee\)\(\neg\)C) \(\wedge\) (\(\neg\)A\(\vee\)B\(\vee\)\(\neg\)C) \(\wedge\) (A\(\vee\)\(\neg\)B\(\vee\)\(\neg\)C) \(\wedge\) (\(\neg\)A\(\vee\)\(\neg\)B\(\vee\)C)
…und wenden das Distributivgesetz an. Dabei substituieren wir (gedanklich) den Term (B\(\vee\)\(\neg\)C).
(A\(\vee\)B\(\vee\)\(\neg\)C) \(\wedge\) (\(\neg\)A\(\vee\)B\(\vee\)\(\neg\)C)
und erhalten (A\(\wedge\)\(\neg\)A) \(\vee\) (B\(\vee\)\(\neg\)C) = 0 \(\wedge\) (B\(\vee\)\(\neg\)C) \(\Rightarrow\) (B\(\vee\)\(\neg\)C)
Wir stellen den Ausdruck erneut um und finden wieder ein Paar, auf das wir das Distributivgesetz anwenden können.
X = (A\(\vee\)B\(\vee\)\(\neg\)C) \(\wedge\) (A\(\vee\)\(\neg\)B\(\vee\)\(\neg\)C) \(\wedge\) (\(\neg\)A\(\vee\)B\(\vee\)\(\neg\)C) \(\wedge\) (\(\neg\)A\(\vee\)\(\neg\)B\(\vee\)C)
Hier wird der Term (A\(\vee\)\(\neg\)C) (gedanklich) substituiert.
(A\(\vee\)B\(\vee\)\(\neg\)C) \(\wedge\) (A\(\vee\)\(\neg\)B\(\vee\)\(\neg\)C) = (A\(\vee\)\(\neg\)C\(\vee\)B) \(\wedge\) (A\(\vee\)\(\neg\)C\(\vee\)\(\neg\)B)
(B\(\wedge\)\(\neg\)B) \(\vee\) (A\(\vee\)\(\neg\)C) = 0 \(\vee\) (A\(\vee\)\(\neg\)C) \(\Rightarrow\) (A\(\vee\)\(\neg\)C)
Der Term (\(\neg\)A\(\vee\)\(\neg\)B\(\vee\)C) kann mit keinem anderen Term minimiert werden und bleibt so stehen. Somit ergibt sich für die minimierte Lösung
X = (B\(\vee\)\(\neg\)C) \(\wedge\) (A\(\vee\)\(\neg\)C) \(\wedge\) (\(\neg\)A\(\vee\)\(\neg\)B\(\vee\)C)
Hinweis:
Terme können immer paarweise minimiert werden. Bei 4 und mehr Variablen kann es so aber zu einer Überdeckung kommen. D.h. dass es Terme gibt, die redundante Werte liefern. In diesem Fall prüft man das Ergebnis und schaut, ob man wiederum den bereits minimierten Ausdruck minimierne kann. Das führt man solange fort, bis ein Ausdruck vorliegt, bei dem keine Minimierung mehr möglich ist.
Aufgabe 2
Erstellen Sie anhand der WHT mittels KV-Diagramm einen minimierten boolschen Ausdruck für X. Sie können selber wählen, ob das Ergebnis als DNF oder KNF angeschreiben wird.
| IN | ¦ | OUT | |
| A | B | ¦ | X |
|---|---|---|---|
| 0 | 0 | ¦ | 0 |
| 0 | 1 | ¦ | 1 |
| 1 | 0 | ¦ | 0 |
| 1 | 1 | ¦ | 0 |
| DNF | KNF | |
 |  |
|
| \(X = \)\(\overline{A}\) \(\wedge\) \(B\) | \(X = \)\(\overline{A}\) \(\wedge\) \(B\) |
Aufgabe 3
Erstellen Sie anhand der WHT mittels KV-Diagramm einen minimierten boolschen Ausdruck für X.Geben Sie das Ergebnis sowohl als DNF wie auch als KNF an.
| IN | ¦ | OUT | ||
| A | B | C | ¦ | X |
|---|---|---|---|---|
| 0 | 0 | 0 | ¦ | 1 |
| 0 | 0 | 1 | ¦ | 0 |
| 0 | 1 | 0 | ¦ | 0 |
| 0 | 1 | 1 | ¦ | 0 |
| 1 | 0 | 0 | ¦ | 1 |
| 1 | 0 | 1 | ¦ | 1 |
| 1 | 1 | 0 | ¦ | 0 |
| 1 | 1 | 1 | ¦ | 1 |
| DNF | KNF | |
 |  |
|
| \(X =\) (\(\overline{B}\)\(\wedge\)\(\overline{C}\)) \(\vee\) (\(A\)\(\wedge\)\(C\)) | \(X = \) (\(A\)\(\vee\)\(\overline{C}\)) \(\wedge\) (\(\overline{B}\)\(\vee\)C) |
Aufgabe 4
Erstellen Sie anhand der WHT mittels KV-Diagramm einen minimierten boolschen Ausdruck für X.Geben Sie das Ergebnis sowohl als DNF wie auch als KNF an.
| IN | ¦ | OUT | |||
| A | B | C | D | ¦ | X |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | ¦ | 1 |
| 0 | 0 | 0 | 1 | ¦ | 1 |
| 0 | 0 | 1 | 0 | ¦ | 1 |
| 0 | 0 | 1 | 1 | ¦ | 1 |
| 0 | 1 | 0 | 0 | ¦ | 1 |
| 0 | 1 | 0 | 1 | ¦ | 0 |
| 0 | 1 | 1 | 0 | ¦ | 1 |
| 0 | 1 | 1 | 1 | ¦ | 1 |
| 1 | 0 | 0 | 0 | ¦ | 1 |
| 1 | 0 | 0 | 1 | ¦ | 0 |
| 1 | 0 | 1 | 0 | ¦ | 0 |
| 1 | 0 | 1 | 1 | ¦ | 0 |
| 1 | 1 | 0 | 0 | ¦ | 1 |
| 1 | 1 | 0 | 1 | ¦ | 0 |
| 1 | 1 | 1 | 0 | ¦ | 0 |
| 1 | 1 | 1 | 1 | ¦ | 1 |
| DNF | KNF | |
 |  |
|
| \(X =\) (\(\overline{A}\)\(\wedge\)\(\overline{B}\)) \(\vee\) (\(\overline{A}\)\(\wedge\)\(\overline{D}\)) \(\vee\) (\(\overline{C}\)\(\wedge\)\(\overline{D}\)) \(\vee\) (\(B\)\(\wedge\)\(C\)\(\wedge\)\(D\)) | \(X = \) (\(\overline{A}\)\(\vee\)\(\overline{B}\)\(\vee\)\(\overline{D}\)) \(\wedge\) (\(\overline{A}\)\(\vee\)\(\overline{C}\)\(\vee\)\(D\)) \(\wedge\) (\(\overline{B}\)\(\vee\)\(C\)\(\vee\)\(\overline{D}\)) |
Aufgabe 5
Gegeben ist ein Ausruck in kanonischer Form, konkret als KKNF. Minimieren Sie diesen unter Verwendung des KV-Diagramms.
Vorgehen:
Sie können die einzelnen Terme direkt in die KV-Matritze übertragen oder aber zuerst eine WHT erstellen und den Übertrag so vornehmen.
Ausdruck:
X = (A\(\vee\)B\(\vee\)\(\neg\)C\(\vee\)D) \(\wedge\) (A\(\vee\)\(\neg\)B\(\vee\)\(\neg\)C\(\vee\)D) \(\wedge\) (\(\neg\)A\(\vee\)B\(\vee\)C\(\vee\)\(\neg\)D) \(\wedge\) (\(\neg\)A\(\vee\)B\(\vee\)C\(\vee\)D) \(\wedge\) (\(\neg\)A\(\vee\)B\(\vee\)\(\neg\)C\(\vee\)D) \(\wedge\) (\(\neg\)A\(\vee\)\(\neg\)B\(\vee\)\(\neg\)C\(\vee\)D)
| DNF | KNF | |
 |  |
|
| \(X = \) (\(\overline{A}\)\(\wedge\)\(\overline{C}\)) \(\vee\) (\(C\)\(\wedge\)\(D\)) \(\vee\) (\(B\)\(\vee\)\(\overline{C}\)) | \(X = \) (\(\overline{A}\)\(\vee\)\(B\)\(\vee\)\(C\)) \(\wedge\) (\(\overline{C}\)\(\vee\)\(D\)) |
Aufgabe 6
Lernende möchten ja gerne früher den Heimweg antreten, insbesondere dann, wenn sie so eine frühere Zugverbindung erreichen könnne. Das gilt erst recht in der Winterzeit, wenn die „Umweltbedingungen“ das Leben mitunter ein wenig erschweren.
Als Variable treten folgende Bedingungen auf:
- es regnet
- es ist dunkel
- der Zug fährt pünktlich
- es ist rutschig
Damit man früher gehen kann, muss der Zug sicher pünktlich fahren (sonst hat man ja eh mehr Zeit). Weiter genügt es nicht, dass es nur dunkel ist, es braucht schon auch Regen oder Glätte, damit die Bedingung für den Gehweg schlecht sind.
Für die Ausgangsvariable gilt:
- 0 = nicht früher gehen
- 1 = früher gehen
Erstellen Sie den Ausdruck für diese Konstellation. Wählen Sie dabei selber, ob das Ergebnis als DNF oder KNF wiedergegeben wird.
Defintion der Variablen
| Regen: | RE | 0 = kein Regen, 1 = Regen |
| Dunkel: | DU | 0 = hell, 1 = dunkel |
| Zug pünktlich: | ZP | 0 = verspätet, 1 = pünktlich |
| Rutschig: | RU | 0 = trocken, 1 = rutschig |
| Früher gehen: | FG | 0 = nein, 1 = ja |
Erstellen der WHT
| IN | ¦ | OUT | |||
| RE | DU | ZP | RU | ¦ | FG |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | ¦ | 0 |
| 0 | 0 | 0 | 1 | ¦ | 0 |
| 0 | 0 | 1 | 0 | ¦ | 0 |
| 0 | 0 | 1 | 1 | ¦ | 0 |
| 0 | 1 | 0 | 0 | ¦ | 0 |
| 0 | 1 | 0 | 1 | ¦ | 0 |
| 0 | 1 | 1 | 0 | ¦ | 0 |
| 0 | 1 | 1 | 1 | ¦ | 1 |
| 1 | 0 | 0 | 0 | ¦ | 0 |
| 1 | 0 | 0 | 1 | ¦ | 0 |
| 1 | 0 | 1 | 0 | ¦ | 0 |
| 1 | 0 | 1 | 1 | ¦ | 0 |
| 1 | 1 | 0 | 0 | ¦ | 0 |
| 1 | 1 | 0 | 1 | ¦ | 0 |
| 1 | 1 | 1 | 0 | ¦ | 1 |
| 1 | 1 | 1 | 1 | ¦ | 1 |
Übertragen in KV-Diagramm
Minimierter Ausdruck
FG = (RE\(\wedge\)DU\(\wedge\)ZP) \(\vee\) (DU\(\wedge\)ZP\(\wedge\)RU)
Hinweis:
In Python-Code würde diese Aussage dann wie folgt aussehen:
if (it_rains and is_dark and train_on_time) or (is_dark and train_on_time and is_slippery): # you can go home earlier
© René Probst