Entwicklungssatz von Shannon
aus Wikipedia, der freien Enzyklopädie
Der Entwicklungssatz von Claude Shannon ist ein Satz über Boolesche Funktionen. 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 | ![= x_{1}[x_{2}\overline {x_{3}} \vee \overline {x_{2}}x_{3}] \vee \overline {x_{1}}[x_{2} \vee \overline {x_{2}}x_{3}]](../../../math/7/c/8/7c86734edad8351e46d5aa88db8cdb4e.png) (Entwicklung nach x1) |
![= x_{1}[x_{2}(\overline {x_{3}}) \vee \overline {x_{2}}(x_{3})] \vee \overline {x_{1}}[x_{2}(1) \vee \overline {x_{2}}(x_{3})]](../../../math/c/c/a/cca9eecb6be291f0dddeed79e39c84a6.png) (Entwicklung nach x2) |
|
![= x_{1}[x_{2}(\overline {x_{3}}) \vee \overline {x_{2}}(x_{3})] \vee \overline {x_{1}}[x_{2}(x_{3} \vee \overline {x_{3}}) \vee \overline {x_{2}}(x_{3})]](../../../math/4/8/c/48c8856c54aed0a1639d4cb23b3d352e.png) (Entwicklung nach x3) |
|
 (Anwendung des Distributivgesetzes) |
