- Entwicklungssatz von Shannon
-
Der Entwicklungssatz von Claude Shannon ist ein Satz über Boolesche Funktionen, der die Shannon-Zerlegung verwendet. Er lautet wie folgt:
y = f(x1,...,xi,...,xn) = Diese Formel sieht zunächst etwas kompliziert aus. Die Aussage betrifft eine n-stellige Boolesche Funktion f und dabei insbesondere deren Parameter xi. Man sagt auch, die Funktion f wird durch Anwendung des Satzes "nach xi entwickelt". Wiederholt man die Anwendung des Satzes für eine beliebige Funktion f auf alle ihre n Parameter, so gelangt man zu einer Darstellung der Funktion, welche ausschließlich die Operatoren ∧, ∨ und ¬ verwendet.
Mit anderen Worten: Die rekursive Anwendung des Entwicklungssatzes von Shannon liefert einen Beweis, dass sich ausnahmslos jede Boolesche Funktion mittels der Operatoren ∧, ∨ und ¬ ausdrücken lässt. Darüber hinaus kann der Entwicklungssatz etwa zur Herleitung klammerfreier Ausdrücke verwendet werden.
Beispiel
Gegeben sei die Boolesche Funktion .
Diese soll zunächst nach x1, dann nach x2 und schließlich nach x3 entwickelt werden:
y (Entwicklung nach x1) (Entwicklung nach x2) (Entwicklung nach x3) (Anwendung des Distributivgesetzes) Als Diagramm
Man kann die Umformung auch als Multiplexer aus einem Nicht-Gatter, zwei UND sowie einem ODER-Gatter verstehen. Das Signal, nach dem die Zerlegung durchgeführt wird, ist das Steuersignal für den Multiplexer. Gemultiplext werden die beiden Ausgänge der gedoppelten Logik, wobei die eine Logik an dem entwickelten Eingang mit einer "1" beaufschlagt wird, während die andere mit einer "0" beaufschlagt wird. Als Diagram dargestellt, sieht dies forlgendermaßen aus:
Siehe auch
Wikimedia Foundation.