Hardware Reference
In-Depth Information
fahren eingeführt, das logische Ausdrücke als Konjunktionsmengen modelliert
und diese systematisch minimiert.
Eine Konjunktion ist ein logischer Ausdruck, der direkte und negierte Ein-
gabevariablen UND-verknüpft, z.B.
x
3
^ x
2
^x
1
^ x
0
= x
3
x
2
x
1
x
0
(K
1010
)
| {z }
verkürzteSchreibweisen
Ein Minterm ist eine vollständige Konjunktion, die alle Eingabevariablen ent-
weder in direkter oder in negierter Form enthält.
Satz 2.1 (Überführung in Konjunktionsmengen) Jede logische Funkti-
on lässt sich durch eine ODER-Verknüpfung einer Menge von Mintermen oder
die negierte ODER-Verknüpfung der Komplementmenge zu dieser Menge dar-
stellen.
Die Beweisidee hierzu lautet, dass sich jede logische Funktion durch eine
Wertetabelle darstellen lässt. Jeder Zeile einer Wertetabelle ist ein Minterm
zugeordnet, der genau für den Eingabewert dieser Zeile »1« und sonst »0« ist
(vgl. Abb. 2.36).
x
2
x
1
x
0
Minterm
y x
2
x
1
x
0
Minterm
y
0 0
0
x
2
x
1
x
0
(K
000
)
0
1 0 0
x
2
x
1
x
0
(K
100
)
1
0 0
1
x
2
x
1
x
0
(K
001
)
1
1 0 1
x
2
x
1
x
0
(K
101
)
1
0 1
0
x
2
x
1
x
0
(K
010
)
0
1 1 0
x
2
x
1
x
0
(K
110
)
1
0 1
1
x
2
x
1
x
0
(K
011
)
0
1 1 1
x
2
x
1
x
0
(K
111
)
0
Abb. 2.36. Wertetabelle mit den den Zeilen zugeordneten Mintermen
Es gibt zwei Möglichkeiten, einen Ausdruck aus einer Menge von Min-
termen zu konstruieren:
• Entwicklung nach den Einsen: ODER-Verknüpfung aller Minterme, denen
der Funktionswert »1« zugeordnet ist.
• Entwicklung nach den Nullen: ODER-Verknüpfung der Minterme, denen
der Funktionswert »0« zugeordnet ist und abschließende Negation.
Aus Abb. 2.36 lassen sich z.B. die folgenden Konjunktionsmengen und Aus-
drücke ablesen:
• Entwicklung nach den Einsen:
fK
001
; K
100
; K
101
; K
110
g) y = x
2
x
1
x
0
_x
2
x
1
x
0
_x
2
x
1
x
0
_x
2
x
1
x
0
• Entwicklung nach den Nullen:
