Shannon-Zerlegung

Die Shannon-Zerlegung oder Shannon-Expansion (benannt nach Claude Elwood Shannon) stellt eine Möglichkeit dar, boolesche Funktionen mithilfe ihrer sogenannten Kofaktoren darzustellen. Die mathematische Aussage über diese Zerlegung wird auch als Entwicklungssatz von Shannon bezeichnet. Obwohl der Satz nach Shannon benannt ist, der ihn erstmals 1949 verwendete, wurde er bereits etwa hundert Jahre zuvor von George Boole aufgestellt.

Aussage

Eine beliebige boolesche Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F(x_1, x_2, \ldots, x_n)} kann folgendermaßen zerlegt werden:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F(x_1, x_2,\ldots,x_n) = x_{i}F(x_1,\ldots,x_{i-1},1,x_{i+1},\ldots,x_n) \vee \overline{x}_i F(x_1,\ldots,x_{i-1},0,x_{i+1},\ldots,x_n)}

oder kürzer unter Verwendung der sogenannten Kofaktoren:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F(x_1, x_2,\ldots,x_n) = x_{i}F_{x_i} \vee \overline{x}_i F_{\overline{x}_i}}

Die Kofaktoren Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F_{x_i}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F_{\overline{x}_i}} werden dabei durch partielle Auswertung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F(x_1, \ldots, x_n)} , d. h. Einsetzen der Variable $x_{i}$ definiert:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} F_{{x_i}} & \equiv F(x_1,\ldots,x_{i-1},1,x_{i+1},\ldots,x_n) \\[3pt] F_{\overline{x}_i} & \equiv F(x_1,\ldots,x_{i-1},0,x_{i+1},\ldots,x_n) \\ \end{align} }

Diese Zerlegung wird auch als If-then-else-Normalform (INF) bezeichnet. Man sagt auch, die Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} wird „nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i} entwickelt“. Wiederholt man die Anwendung des Satzes für eine beliebige Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} auf alle ihre n Parameter, so gelangt man zu einer Darstellung der Funktion, welche ausschließlich die Operatoren ∧, ∨ und ¬ verwendet. Die rekursive Anwendung der Shannon-Zerlegung liefert also einen Beweis, dass sich jede boolesche Funktion mittels der Operatoren ∧, ∨ und ¬ ausdrücken lässt.

Diese Zerlegung führte unter anderem zur Entwicklung von binären Entscheidungsdiagrammen und damit zu einer der Möglichkeiten der Bearbeitung des Erfüllbarkeitsproblems der Aussagenlogik. Darüber hinaus kann der Entwicklungssatz etwa zur Herleitung klammerfreier Ausdrücke verwendet werden.

Beispiel

Gegeben sei die Boolesche Funktion Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle y=f(x_{1},x_{2},x_{3})=x_{1}x_{2}{\overline {x_{3}}}\vee {\overline {x_{1}}}x_{2}\vee {\overline {x_{2}}}x_{3}} .

Diese soll zunächst nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_{1}} , dann nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_{2}} und schließlich nach $x_{3}$ 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}]$		(Entwicklung nach $x_{1}$)
	$=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})]$		(Entwicklung nach $x_{2}$)
	$=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})]$		(Entwicklung nach $x_{3}$)
	$=x_{1}x_{2}{\overline {x_{3}}}\vee x_{1}{\overline {x_{2}}}x_{3}\vee {\overline {x_{1}}}x_{2}x_{3}\vee {\overline {x_{1}}}x_{2}{\overline {x_{3}}}\vee {\overline {x_{1}}}{\overline {x_{2}}}x_{3}$		(Anwendung des Distributivgesetzes)

Darstellung 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 Diagramm dargestellt, sieht dies folgendermaßen aus: