Expansion de Shannon

Cet article ou cette section d'article est rédigé entièrement ou presque entièrement à partir d'une seule source (juillet 2018).

N'hésitez pas à modifier cet article pour améliorer sa vérifiabilité en apportant de nouvelles références dans des notes de bas de page.

Pour les articles homonymes, voir Shannon.

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 ${\displaystyle F}$ : ${\displaystyle F=x\cdot F_{x}+{\bar {x}}\cdot F_{\bar {x}}}$ où ${\displaystyle F}$ est une formule booléenne, ${\displaystyle x}$ est une variable, ${\displaystyle {\bar {x}}}$ est la négation de ${\displaystyle x}$, et les formules ${\displaystyle F_{x}}$ et ${\displaystyle F_{\bar {x}}}$ sont obtenus à partir de ${\displaystyle F}$ en affectant ${\displaystyle x}$ à ${\displaystyle 1}$ et ${\displaystyle 0}$ respectivement^[1].

Application

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

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

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

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

${\displaystyle f(X,Y,Z)={\bar {X}}\cdot {\bar {Y}}\cdot f(0,0,Z)+{\bar {X}}\cdot Y\cdot f(0,1,Z)+X\cdot {\bar {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 :

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

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

${\displaystyle X}$	${\displaystyle Y}$	${\displaystyle f(X,Y,Z)}$
0	0	${\displaystyle f(0,0,Z)}$
0	1	${\displaystyle f(0,1,Z)}$
1	0	${\displaystyle f(1,0,Z)}$
1	1	${\displaystyle f(1,1,Z)}$

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

Notes et références

• Portail de la logique