Bei den graphischen Beschreibungen von Schaltfunktionen unterscheiden wir
(a) Baumartige Beschreibungen
(b) Tabellenartige Beschreibungen
(c) Kontaktnetze
(d) Schaltbilder
Wir wollen sie der Reihe nach besprechen:
(a) Entscheidungsbäume werden meist mit dem Stamm oben und den Blättern unten gezeichnet. Um den Funktionswert für einen vorgegebenen Satz von Variablen zu finden, beginnt man beim Stamm und steigt (abwärts!) in die Verzeigungen. Welcher Weg bei einer Verzweigung weiter verfolgt wird, bestimmt jeweils der Wert einer der Variablen. Bei den folgenden Entscheidungsbäumen ist an allen Knoten der linke (rote) Zweig im Falle einer 0 und der rechte (grüne) im Falle einer 1 zu wählen. Sehr einfache Beispiele sind folgende:
Identität:
Inversion:
UND:
Wenn die Entscheidungsknoten der einzelnen Variablen in allen Ästen auf der selben Ebene geordnet sind, sprechen wir von einem geordneten binären Entscheidungsbaum. Ein vollständiger Entscheidungsbaum für eine Schaltfunktion von n Variablen hat 2n Blätter. Für den Multiplexer ergibt sich:
Sind an einem Entscheidungsknoten beide Zweige gleich, so kann man den Knoten und einen der Zweige weglassen und erhält den reduzierten binären Entscheidungsbaum:
Die Anzahl der erforderlichen Knoten in einem reduzierten binären Entscheidungsbaum hängt von der Reihenfolge der Variablen ab. Dies ist im folgenden Beispiel mit 5 Variablen gut zu sehen:
Unter Verzicht auf die organisatorisch und graphisch einfache Baumstruktur lassen sich gleiche Zweige auch dann vereinigen, wenn sie nicht an dem selben Knoten hängen. Diese sog. Reduced Ordered Binary Decision Diagrams (OBDDs) haben Bedeutung erlangt beim Entwurf digitaler Systeme. Ein entscheidender Vorteil der reduzierten graphischen Beschreibungen ist ihre wesentlich geringere Komplexität gegenüber der exponentiell mit der Zahl der Variablen ansteigenden Komplexität der Funktionstabelle und damit auch der Vektor-Beschreibung. Wir gehen hier jedoch nicht tiefer darauf ein.
Es gibt weitere graphische Darstellungen von Schaltfunktionen, z.B. den Kantorovic Baum und das Datenfluss-Diagramm. Sie sind aber nicht verbreitet. Zwei weitere graphische Darstellungsformen werden wir später betrachten, nämlich Schaltbilder und Kontaktnetze.