Expansion de Shannon

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

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.

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

Application[modifier | modifier le code]

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 principales, 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)={\bar {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)={\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[modifier | modifier le code]

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)={\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 ${\bar {X}}\cdot {\bar {Y}}$ est associé à $f(0,0,Z)$ , le terme ${\bar {X}}\cdot Y$ est associé à $f(0,1,Z)$ , 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 :

Notes et références[modifier | modifier le code]

↑ C. E. Shannon, « The synthesis of two-terminal switching circuits », The Bell System Technical Journal, vol. 28, n^o 1,‎ janvier 1949, p. 59–98 (ISSN 0005-8580, DOI 10.1002/j.1538-7305.1949.tb03624.x, lire en ligne, consulté le 18 janvier 2018)

Portail de la logique

[1] C. E. Shannon, « The synthesis of two-terminal switching circuits », The Bell System Technical Journal, vol. 28, n^o 1,‎ janvier 1949, p. 59–98 (ISSN 0005-8580, DOI 10.1002/j.1538-7305.1949.tb03624.x, lire en ligne, consulté le 18 janvier 2018)

[1]