title: Expansion de Shannon
text: # Expansion de 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 $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.
  
  ## 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 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
  
  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 :
  
  