Aufgabe 2 - Boolesche Algebra

Aufgabenstellung

Gegeben ist die nachfolgende Logikfunktion als kanonisch disjunktive Normalform (KDNF):

y =x₃x₂x₁x₀∪x₃x₂x₁x₀∪x₃x₂x₁x₀∪x₃x₂x₁x₀∪x₃x₂x₁x₀∪x₃x₂x₁x₀

a)

Ermitteln Sie die Wertigkeiten (Dezimalwerte) der gegebenen Elementarkonjunktionen von y. Stellen Sie die KDNF noch einmal mit geordneten Wertigkeiten (aufsteigend oder absteigend) dar.

4 Pkt.

b)

Vereinfachen Sie die gegebene Schaltfunktion und ermitteln Sie die minimierte disjunktive Normalform (DNF) rechnerisch mithilfe der Gesetze der boolschen Algebra.

4 Pkt.

c)

Stellen Sie das KV-Diagramm für die Funktion y auf, ermitteln Sie daraus durch Blockbildung/Blockeinkreisen die minimierte DNF für y und vergleichen Sie Ihr Ergebnis mit der vorab rechnerisch ermittelten Funktion.

4 Pkt.

d)

Bestimmen Sie mithilfe des KV-Diagramms und Blockbildung/Blockeinkreisen die minimierte konjunktive Normalform (KNF) von y.

4 Pkt.

e)

Bestimmen Sie eine NAND-Form für y.

4 Pkt.

Σ 20 Pkt.

Lösung

a) Wertigkeiten der Elementarkonjunktionen

Die Variablen x₃, x₂, x₁ und x₀ haben die Wertigkeiten 8, 4, 2 und 1. Eine nicht negierte Variable erhält den Bitwert 1. Eine negierte Variable erhält den Bitwert 0.

Elementarkonjunktion	Binärwert	Dezimalwert
¬x3 ¬x2 ¬x1 ¬x0	0000	0
x3 ¬x2 x1 ¬x0	1010	10
x3 x2 ¬x1 ¬x0	1100	12
x3 ¬x2 ¬x1 ¬x0	1000	8
¬x3 ¬x2 x1 ¬x0	0010	2
¬x3 x2 x1 ¬x0	0110	6

Tabelle 2.1: Wertigkeiten der Elementarkonjunktionen in der vorgegebenen Reihenfolge (eigene Berechnung).

Aufsteigend geordnet ergeben sich die Wertigkeiten 0, 2, 6, 8, 10 und 12. Die geordnete KDNF lautet:

y =x₃x₂x₁x₀∪x₃x₂x₁x₀∪x₃x₂x₁x₀∪x₃x₂x₁x₀∪x₃x₂x₁x₀∪x₃x₂x₁x₀

In der kompakten Indexschreibweise kann sie so angegeben werden:

y = K⁴(0, 2, 6, 8, 10, 12)

b) Rechnerische Vereinfachung zur minimierten DNF

Für die Vereinfachung werden die Terme m2 und m8 jeweils zweimal verwendet. Das ist nach dem Idempotenzgesetz erlaubt und ändert die Funktion nicht.

y = (m0 ∪ m2 ∪ m8 ∪ m10)
  ∪ (m2 ∪ m6)
  ∪ (m8 ∪ m12)

Zuerst werden die vier Terme m0, m2, m8 und m10 vereinfacht:

m0 ∪ m2
= ¬x3 ¬x2 ¬x0 (¬x1 ∪ x1)
= ¬x3 ¬x2 ¬x0

m8 ∪ m10
= x3 ¬x2 ¬x0 (¬x1 ∪ x1)
= x3 ¬x2 ¬x0

m0 ∪ m2 ∪ m8 ∪ m10
= ¬x2 ¬x0 (¬x3 ∪ x3)
= ¬x2 ¬x0

Für die Terme m2 und m6 ergibt sich:

m2 ∪ m6
= ¬x3 x1 ¬x0 (¬x2 ∪ x2)
= ¬x3 x1 ¬x0

Die Terme m8 und m12 werden auf die gleiche Weise zusammengefasst:

m8 ∪ m12
= x3 ¬x1 ¬x0 (¬x2 ∪ x2)
= x3 ¬x1 ¬x0

Damit lautet die minimierte DNF:

y =x₂x₀∪x₃x₁x₀∪x₃x₁x₀

c) KV-Diagramm und minimierte DNF

Die Einsen werden in die Felder 0, 2, 6, 8, 10 und 12 eingetragen. Zeilen und Spalten sind in der Gray-Code-Reihenfolge 00, 01, 11 und 10 angeordnet.

x₃x₂x₁x₀

00

01

11

10

00

1m0I

0m1

0m3

1m2III

01

0m4

0m5

0m7

1m6II

11

1m12III

0m13

0m15

0m14

10

1m8IIII

0m9

0m11

1m10I

I m0, m2, m8, m10II m2, m6III m8, m12

Abbildung 2.1: KV-Diagramm mit Blockbildung für die Einsfelder (eigene Darstellung).

Die Einsfelder lassen sich in drei Blöcke aufteilen:

1. Block I enthält die Felder 0, 2, 8 und 10. Die Randfelder des KV-Diagramms gelten als benachbart. In diesem Block bleiben x2 = 0 und x0 = 0 gleich. Daraus folgt der Term ¬x2 ¬x0.
2. Block II enthält die Felder 2 und 6. Hier bleiben x3 = 0, x1 = 1 und x0 = 0 gleich. Daraus folgt der Term ¬x3 x1 ¬x0.
3. Block III enthält die Felder 8 und 12. Hier bleiben x3 = 1, x1 = 0 und x0 = 0 gleich. Daraus folgt der Term x3 ¬x1 ¬x0.

Aus den drei Blöcken entsteht dieselbe DNF wie bei der rechnerischen Vereinfachung:

y =x₂x₀∪x₃x₁x₀∪x₃x₁x₀

d) Minimierte KNF

Für die KNF werden die Nullfelder zusammengefasst. Die Nullen liegen in den Feldern 1, 3, 4, 5, 7, 9, 11, 13, 14 und 15.

x₃x₂x₁x₀

00

01

11

10

00

1m0

0m1A

0m3A

1m2

01

0m4B

0m5AB

0m7A

1m6

11

1m12

0m13A

0m15AC

0m14C

10

1m8

0m9A

0m11A

1m10

A m1, m3, m5, m7, m9, m11, m13, m15B m4, m5C m14, m15

Abbildung 2.2: KV-Diagramm mit Blockbildung für die Nullfelder (eigene Darstellung).

Die Nullfelder werden in drei Blöcke aufgeteilt:

1. Block A enthält alle ungeraden Felder. In diesem Block gilt immer x0 = 1. Für die negierte Funktion entsteht daraus der Term x0.
2. Block B enthält die Felder 4 und 5. Hier gelten x3 = 0, x2 = 1 und x1 = 0. Daraus entsteht der Term ¬x3 x2 ¬x1.
3. Block C enthält die Felder 14 und 15. Hier gelten x3 = 1, x2 = 1 und x1 = 1. Daraus entsteht der Term x3 x2 x1.

Damit lautet die minimierte DNF der negierten Funktion:

y =x₀∪x₃x₂x₁∪x₃x₂x₁

Durch die Negation der gesamten Funktion und die Anwendung des De-Morgan-Gesetzes entsteht die minimierte KNF:

y =x₀∩(x₃ ∪ x₂ ∪ x₁)∩(x₃ ∪ x₂ ∪ x₁)

e) NAND-Form

Als Ausgangspunkt dient die minimierte DNF aus den Teilaufgaben b und c. Die Funktion wird doppelt negiert. Anschließend wird das De-Morgan-Gesetz angewendet.

y =x₂x₀ ∩ x₃x₁x₀ ∩ x₃x₁x₀

Die drei inneren negierten UND-Verknüpfungen werden jeweils mit einem NAND-Glied gebildet. Ihre Ausgänge werden an ein weiteres NAND-Glied angeschlossen. Falls auch die negierten Eingangsvariablen nur mit NAND-Gliedern erzeugt werden sollen, gilt zum Beispiel:

¬x2 = NAND(x2, x2)