Kleines Nachschlagewerk Informatik
Vereinfachung von Schaltnetzen
Vereinfachung mit Boolescher Algebra
Zur Vereinfachung sei auf die Gesetze der booleschen Algebra verwiesen. Ein Beispiel soll dies demonstrieren.

Eine Schaltung ist gegeben durch den Ausdruck



Gemäß Distributivgesetz lassen sich E1 und E3 ausklammern. Der Rest ist nach dem Gesetz der komplementären Elemente 1. Eine UND-Verknüpfung mit 1 ändert nichts (Gesetz der neutralen Elemente) und somit bleibt es bei E1 und nicht E3.



Verfahren von Quine-McCluskey
Obiges Beispiel lässt sich oft finden und automatisieren. Allgemein kann man sagen: Wenn a und b oder a und nicht b, dann a.

Weiterhin betrachtet man sich Schaltwerttabellen. Jede Zeile ist eine UND-Verknüpfung. Danach werden alle Zeilen, die 1 ergeben, ODER-verknüpft. Unterscheiden sich zwei Zeilen in nur einer Stelle, so kann diese Stelle eliminiert werden.

Ein Beispiel soll dies demonstrieren. Eine Schaltung sei durch folgende Schaltwerttabelle gegeben:
E1E2E3A
0000
0010
0101
0111
1000
1011
1100
1111
Die zugehörige Schaltfunktion lautet:



Die Terme, die eins ergeben, packt man in eine Tabelle. Diese Terme ordnet man nach der Anzahl von Einsen. Denn man kann - wie schon gezeigt - nur Terme zusammen fassen, die sich in nur einer Stelle unterscheiden.

Am besten markiert man die Blöcke mit gleicher Zahl an Einsen (hier aus technischen Gründen weggelassen).

NummerE1E2E3
1111
2101
3011
4010


Die Nummer eins kann man mit 2 und mit 3, die zwei mit vier und die drei mit vier vergleichen. Die Tabelle wird mit den vereinfachten Termen nach rechts erweitert. Stellen, die weggefallen sind, bekommen ein x.
NummerE1E2E31. SchrittE1E2E3
1111121x1
210113x11
30113401x
4010    


In der neuen Generation sind keine Terme, die sich in einer Stelle unterscheiden. Bei komplexeren Schaltungen können durchaus noch zwei bis drei derartige Schritte folgen. Es passiert oft, dass zwei Terme ein Ergebnis erzeugen, welches in der Tabelle schon vorkommt. Das ist üblich, man streicht die Dopplung einfach raus.

Eine Probe zeigt, dass man mit Term 12 die letzten beiden, mit Term 34 die ersten beiden Terme der Tabelle findet. Wozu braucht man dann noch 13? Man braucht 13 tatsächlich nicht, denn die 1 für E2 findet man in 34, die 1 für E3 in 12. Um solche Überschneidungen zu erkennen, lohnt es sich, das Ergebnis tabellarisch aufzuschreiben und dort ein Kreuz zu machen, wo ein Term eine Variable erfasst.

TermE1E2E3
12xx
13xx
34xx 


Ohne 13 wirft die Tabelle bei Licht von oben den gleichen Schatten. Es ergibt sich als Ergebnis: