modul:mathe:ma1:thema:lu04logik:aufgaben:leitprogramm:k9:l8:start

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


zum Leitprogramm

© René Probst

  • modul/mathe/ma1/thema/lu04logik/aufgaben/leitprogramm/k9/l8/start.txt
  • Last modified: 2023/11/13 08:56
  • by 127.0.0.1