Shannon-Zerlegung

Die Shannon-Zerlegung (Shannon-Expansion) stellt eine Möglichkeit dar, Boolesche Funktionen mithilfe ihrer sogenannten Kofaktoren darzustellen.

Eine beliebige Boolesche Funktion F(x₁,x₂,...,x_n) kann damit folgendermaßen angeschrieben werden:

$F(x_1, x_2, ..., x_n) = x_i * F(x_1, x_2, ..., x_n)_{x_i} + \neg x_i * F(x_1, x_2, ..., x_n) _{\neg x_i}$, $i \in [1, ..., n]$

wobei die sogenannten Kofaktoren der Funktion F(x,x₂,...,x_n) wie folgt definiert sind:

$F(x_1, x_2, ..., x_n)_{x_i}$ ist die ursprüngliche Funktion F(x₁,x₂,...,x_n) wobei die Variable x_i mit dem Wert 1 substituiert wird.

$F(x_1, x_2, ..., x_n)_{\neg x_i}$ ist die ursprüngliche Funktion F(x₁,x₂,...,x_n) wobei die Variable x_i mit dem Wert 0 substituiert wird.

Diese Zerlegung wird auch als if-then-else-Normalform (INF) bezeichnet.

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.

Siehe auch

• Entwicklungssatz von Shannon