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 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\colon X^n\rightarrow X} eine Boolesche Funktion auf $n$ Literalen 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,...,x_n} und dem Operatorentupel $(\lor ,\land )$. Dann gilt

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 \overline{f(x_1, x_2, ..., x_n, \lor, \land)} = f(\overline{x_1}, \overline{x_2}, ..., \overline{x_n}, \land, \lor)}