Inversionssatz von Shannon

Der Inversionssatz von Shannon ist ein bedeutender, von Claude Shannon stammender Satz in der Booleschen Algebra, der eine Verallgemeinerung der De Morganschen Gesetze für algebraische Ausdrücke mit Booleschen Größen darstellt. Demnach kann die Inversion eines jeden solchen Ausdrucks, sofern er nur mittels der Operatoren ∧, ∨ und ¬ (d. h. Konjunktion, Disjunktion und Negation) gebildet wurde, erreicht werden, indem man ∧ und ∨ vertauscht und jedes Literal negiert. Dabei werden Literale als Boolesche Größen A, B, C, … sowie ¬A, ¬B, ¬C, … verstanden, also als nicht zusammengesetzte einfache oder negierte Größen.

Formulierung des Satzes Bearbeiten

Sei $f\colon X^{n}\rightarrow X$ eine Boolesche Funktion auf $n$ Literalen $x_{1},...,x_{n}$ und dem Operatorentupel $(\lor ,\land )$ . Dann gilt^[1]

{\overline {f(x_{1},x_{2},...,x_{n},\lor ,\land )}}=f({\overline {x_{1}}},{\overline {x_{2}}},...,{\overline {x_{n}}},\land ,\lor )

Einzelnachweise Bearbeiten

↑ Roland Woitowitz, Klaus Urbanski: Digitaltechnik – Ein Lehr- und Übungsbuch. 5., neu bearbeitete und erweiterte Auflage. Springer Verlag, 2007, ISBN 978-3-540-73672-1, S. 31.

[1] Roland Woitowitz, Klaus Urbanski: Digitaltechnik – Ein Lehr- und Übungsbuch. 5., neu bearbeitete und erweiterte Auflage. Springer Verlag, 2007, ISBN 978-3-540-73672-1, S. 31.

[1]