Expansion de Shannon

Modèle:Source unique Modèle:Voir homonymes L'expansion de Shannon est, en logique, la décomposition d'une équation booléenne selon une ou plusieurs variables principales. Elle consiste en l'identité suivante, vraie quelle que soit la fonction $F$ : $F=x\cdot F_x+\overline{x}\cdot F_{\overline{x}}$ où $F$ est une formule booléenne, $x$ est une variable, $\overline{x}$ est la négation de $x$, et les formules $F_x$ et $F_{\overline{x}}$ sont obtenus à partir de $F$ en affectant $x$ à $1$ et $0$ respectivement.

Application

Le thèorème d'expansion de Shannon s'applique en décomposant une équation en $2^n$ membres, $n$ étant le nombre de variables principales. On aura ainsi 2 membres lorsque l'on choisit une seule variable principale, 4 pour deux variables principalesModèle:Etc.

Par exemple, pour la fonction de 3 variables $f(X,Y,Z)$, si l'on choisit $X$ comme variable principale, le théorème d'expansion de Shannon donne l'égalité suivante :

$f(X,Y,Z)=\overline{X}\cdot f(0,Y,Z)+X\cdot f(1,Y,Z)$

En prenant $X$ et $Y$ comme variables principales, on obtiendra l'égalité suivante :

$f(X,Y,Z)=\overline{X}\cdot \overline{Y}\cdot f(0,0,Z)+\overline{X}\cdot Y\cdot f(0,1,Z)+X\cdot \overline{Y}\cdot f(1,0,Z)+X\cdot Y\cdot f(1,1,Z)$

Utilisation

Le théorème d'expansion de Shannon permet de séparer des variables que l'on considèrera principales, les autres étant des variables secondaires ou introduites. Il permet notamment de faire correspondre une équation avec les entrées d'un multiplexeur. En effet, une fois l'équation décomposée sous la forme de Shannon, il est possible de réaliser l'identité des variables principales avec les termes produits d'une table de vérité. Ainsi, dans l'exemple suivant :

$f(X,Y,Z)=\overline{X}\cdot \overline{Y}\cdot f(0,0,Z)+\overline{X}\cdot Y\cdot f(0,1,Z)+X\cdot \overline{Y}\cdot f(1,0,Z)+X\cdot Y\cdot f(1,1,Z)$

Le terme produit $\overline{X}\cdot \overline{Y}$ est associé à $f(0,0,Z)$, le terme $\overline{X}\cdot Y$ est associé à $f(0,1,Z)$Modèle:Etc. On peut donc construire la table de vérité suivante :

$X$	$Y$	$f(X,Y,Z)$
0	0	$f(0,0,Z)$
0	1	$f(0,1,Z)$
1	0	$f(1,0,Z)$
1	1	$f(1,1,Z)$

Cette table peut alors être mise en œuvre en utilisant un multiplexeur de la manière suivante :