Von der Wahrheitstafel zur logischen Funktion

Das folgende Beispiel soll den Weg von der Wahrheitstafel zur logischen Funktion beschreiben. Gegeben sei die Wahrheitstafel

a	b	c	OUT
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	0

Da die Zahl der Einsen überwiegt, wird die konjunktive Normalform gebildet. Dazu liefern die Zeilen 4, 6 und 8 drei Terme, die mit UND zu folgendem Ausdruck verknüpft werden:

(a v ~b v ~c) (~a v b v ~c) (~a v ~b v ~c).

Im ersten Schritt wird auf die ersten beiden Terme das Distributivgesetz angewendet und man erhält einen Ausdruck, der zur besseren Lesbarkeit geklammert wurde:

((a ~a) v (~b ~a) v (~c ~a) v (a b) v (~b b) v
(~c b) v (a ~c) v (~b ~c) v (~c ~c)) (~a v ~b v ~c).

Nach Vereinfachung der UND-Terme und der weiteren Anwendung des Distributivgesetzes erhält man folgenden Ausdruck:

(~a ~b) v (~c ~a) v (~a ~b ~c) v (~a b ~c) v
(a ~c ~b) v (~b ~c) v (a b ~c) v (b ~c) v (a ~c) v ~c.

Durch weitere Anwendung des Distributivgesetzes kann man den obigen Ausdruck umformen in

(~a ~b) v (~c ~a) v (~b ~c) v (b ~c) v ~c

und weiter in

(~a ~b) v (~c ~a) v ~c,

was sich weiter vereinfachen lässt zu

(~a ~b) v ~c.

Durch Anwendung der DeMorgan-Regel kann man diesen Ausdruck weiter in

~((a v b) c)

umwandeln. Dieser nun recht einfache Term lässt sich durch zwei Gatter darstellen. Zur Kontrolle sollte man für die gefundene logische Schaltung die Wahrheitstafel konstruieren und mit der Wahrheitstafel der Problemstellung vergleichen. Beide Tafeln müssen übereinstimmen.

Logische Funktion aus OR und NAND

Die gefundene Schaltung besteht also aus zwei Gattern, einem OR-Gatter und einem NAND-Gatter. Man benötigt zum Aufbau dieser Schaltung zwei ICs (z.B. 7432 und 7400). Möchte man den Bauteilaufwand noch weiter reduzieren, so kann man versuchen, das OR-Gatter durch eine entsprechende Kombination von NAND-Gattern zu konstruieren. Führt man dies bei dieser Schaltung durch, so kommt man auf folgende logisch äquivalente Schaltung:

Logische Funktion aus NAND-Gattern

Man sieht, dass nun zum Aufbau dieser Schaltung mehr Gatter Verwendung finden, diese jedoch alle vom gleichen Typ sind. Dadurch kann sich, wie in unserem Fall trotz der Erhöhung der Gatterzahl eine Erniedrigung der Zahl der Bauelemente ergeben. Die vier NAND-Gatter sind alle auf einem Baustein enthalten. Ein Nachteil dieser logisch äquivalenten Schaltung ist die erhöhte Durchlaufzeit des Signals, die in diesem Beispiel (bei Verwendung von LS-Bausteinen) von 25 ns auf 30 ns steigt.

Der oben beschriebene Weg zur Synthese einer logischen Funktion kann für eine größere Zahl von Eingangsvariablen relativ aufwendig werden. Verfügt man über kein Computerprogramm zur Vereinfachung logischer Ausdrücke (siehe auch C. Schneider ), so kann man auch die graphische Methode verwenden.