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

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

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