www.wikidata.de-de.nina.az

Shannon Zerlegung Die oder Shannon Expansion benannt nach Claude Elwood Shannon stellt eine Möglichkeit dar boolesche Fu

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 Bearbeiten

Eine beliebige boolesche Funktion kann folgendermaßen zerlegt werden:

oder kürzer unter Verwendung der sogenannten Kofaktoren:

Die Kofaktoren und werden dabei durch partielle Auswertung von , d. h. Einsetzen der Variable definiert:

Diese Zerlegung wird auch als If-then-else-Normalform (INF) bezeichnet. Man sagt auch, die Funktion wird „nach entwickelt“. Wiederholt man die Anwendung des Satzes für eine beliebige Funktion 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 Bearbeiten

Gegeben sei die Boolesche Funktion .

Diese soll zunächst nach , dann nach und schließlich nach entwickelt werden:

(Entwicklung nach )
(Entwicklung nach )
(Entwicklung nach )
(Anwendung des Distributivgesetzes)

Darstellung als Diagramm Bearbeiten

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:

Einzelnachweise Bearbeiten

  1. C. E. Shannon: The synthesis of two-terminal switching circuits. In: Bell System Technical Journal. Band 28, Nr. 1, 1949, S. 59–98.
  2. G. Boole: The calculus of logic. In: Cambridge and Dublin Mathematical Journal. Band 3, Nr. 1848, 1848, S. 183–198 (PDF [abgerufen am 26. November 2012]).
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Shannon Zerlegung oder Shannon Expansion benannt nach Claude Elwood Shannon stellt eine Moglichkeit dar boolesche Funktionen mithilfe ihrer sogenannten Kofaktoren darzustellen Die mathematische Aussage uber diese Zerlegung wird auch als Entwicklungssatz von Shannon bezeichnet Obwohl der Satz nach Shannon benannt ist der ihn erstmals 1949 verwendete 1 wurde er bereits etwa hundert Jahre zuvor von George Boole aufgestellt 2 Inhaltsverzeichnis 1 Aussage 2 Beispiel 3 Darstellung als Diagramm 4 EinzelnachweiseAussage BearbeitenEine beliebige boolesche Funktion F x 1 x 2 x n displaystyle F x 1 x 2 ldots x n nbsp kann folgendermassen zerlegt werden F x 1 x 2 x n x i F x 1 x i 1 1 x i 1 x n x i F x 1 x i 1 0 x i 1 x n 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 nbsp oder kurzer unter Verwendung der sogenannten Kofaktoren F x 1 x 2 x n x i F x i x i F x i displaystyle F x 1 x 2 ldots x n x i F x i vee overline x i F overline x i nbsp Die Kofaktoren F x i displaystyle F x i nbsp und F x i displaystyle F overline x i nbsp werden dabei durch partielle Auswertung von F x 1 x n displaystyle F x 1 ldots x n nbsp d h Einsetzen der Variable x i displaystyle x i nbsp definiert F x i F x 1 x i 1 1 x i 1 x n F x i F x 1 x i 1 0 x i 1 x n displaystyle begin aligned F x i amp equiv F x 1 ldots x i 1 1 x i 1 ldots x n 3pt F overline x i amp equiv F x 1 ldots x i 1 0 x i 1 ldots x n end aligned nbsp Diese Zerlegung wird auch als If then else Normalform INF bezeichnet Man sagt auch die Funktion f displaystyle f nbsp wird nach x i displaystyle x i nbsp entwickelt Wiederholt man die Anwendung des Satzes fur eine beliebige Funktion f displaystyle f nbsp auf alle ihre n Parameter so gelangt man zu einer Darstellung der Funktion welche ausschliesslich die Operatoren und verwendet Die rekursive Anwendung der Shannon Zerlegung liefert also einen Beweis dass sich jede boolesche Funktion mittels der Operatoren und ausdrucken lasst Diese Zerlegung fuhrte unter anderem zur Entwicklung von binaren Entscheidungsdiagrammen und damit zu einer der Moglichkeiten der Bearbeitung des Erfullbarkeitsproblems der Aussagenlogik Daruber hinaus kann der Entwicklungssatz etwa zur Herleitung klammerfreier Ausdrucke verwendet werden Beispiel BearbeitenGegeben sei die Boolesche Funktion y f x 1 x 2 x 3 x 1 x 2 x 3 x 1 x 2 x 2 x 3 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 nbsp Diese soll zunachst nach x 1 displaystyle x 1 nbsp dann nach x 2 displaystyle x 2 nbsp und schliesslich nach x 3 displaystyle x 3 nbsp entwickelt werden y displaystyle y nbsp x 1 x 2 x 3 x 2 x 3 x 1 x 2 x 2 x 3 displaystyle 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 nbsp Entwicklung nach x 1 displaystyle x 1 nbsp x 1 x 2 x 3 x 2 x 3 x 1 x 2 1 x 2 x 3 displaystyle 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 nbsp Entwicklung nach x 2 displaystyle x 2 nbsp x 1 x 2 x 3 x 2 x 3 x 1 x 2 x 3 x 3 x 2 x 3 displaystyle 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 nbsp Entwicklung nach x 3 displaystyle x 3 nbsp x 1 x 2 x 3 x 1 x 2 x 3 x 1 x 2 x 3 x 1 x 2 x 3 x 1 x 2 x 3 displaystyle 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 nbsp Anwendung des Distributivgesetzes Darstellung als Diagramm BearbeitenMan kann die Umformung auch als Multiplexer aus einem Nicht Gatter zwei UND sowie einem ODER Gatter verstehen Das Signal nach dem die Zerlegung durchgefuhrt wird ist das Steuersignal fur den Multiplexer Gemultiplext werden die beiden Ausgange der gedoppelten Logik wobei die eine Logik an dem entwickelten Eingang mit einer 1 beaufschlagt wird wahrend die andere mit einer 0 beaufschlagt wird Als Diagramm dargestellt sieht dies folgendermassen aus nbsp Einzelnachweise Bearbeiten C E Shannon The synthesis of two terminal switching circuits In Bell System Technical Journal Band 28 Nr 1 1949 S 59 98 G Boole The calculus of logic In Cambridge and Dublin Mathematical Journal Band 3 Nr 1848 1848 S 183 198 PDF abgerufen am 26 November 2012 Abgerufen von https de wikipedia org w index php title Shannon Zerlegung amp oldid 208221975