Algèbre de Boole & Logique combinatoire

Théorèmes de l'algèbre de Boole, simplification d'expressions, tables de Karnaugh.

L'algèbre de Boole

L'algèbre de Boole est le système mathématique qui sous-tend toute la logique numérique. Définie par George Boole en 1854, formalisée par Claude Shannon pour les circuits en 1937.

Trois opérations fondamentales :

AND (·) : produit logique
OR (+) : somme logique
NOT (¬) : complément

Théorèmes fondamentaux

Identités de base

Théorème	AND	OR
Identité	A · 1 = A	A + 0 = A
Null	A · 0 = 0	A + 1 = 1
Idempotence	A · A = A	A + A = A
Complément	A · Ā = 0	A + Ā = 1
Involution	¬(¬A) = A

Commutativité et associativité

A · B = B · A          A + B = B + A
(A · B) · C = A · (B · C)    (A + B) + C = A + (B + C)

Distributivité

A · (B + C) = (A · B) + (A · C)
A + (B · C) = (A + B) · (A + C)

Lois de De Morgan

Fondamentales pour la simplification et l'implémentation NAND/NOR :

¬(A · B) = ¬A + ¬B     (NOT AND = OR des compléments)
¬(A + B) = ¬A · ¬B     (NOT OR = AND des compléments)

En VHDL :

-- De Morgan 1 : NOT (A AND B) = (NOT A) OR (NOT B)
o_y <= NOT (i_a AND i_b);  -- équivalent à :
o_y <= (NOT i_a) OR (NOT i_b);
 
-- De Morgan 2 : NOT (A OR B) = (NOT A) AND (NOT B)
o_y <= NOT (i_a OR i_b);   -- équivalent à :
o_y <= (NOT i_a) AND (NOT i_b);

Simplification d'expressions

Méthode algébrique

F = A·B + A·B̄
  = A·(B + B̄)    (distributivité)
  = A·1           (complément)
  = A             (identité)

F = A·B + A·C + B·C
  = A·B + A·C + B·C·(A + Ā)     (A + Ā = 1)
  = A·B + A·C + A·B·C + Ā·B·C
  = A·B·(1 + C) + A·C + Ā·B·C
  = A·B + A·C + Ā·B·C
  = A·(B + C) + Ā·B·C

Tables de Karnaugh (K-map)

Pour les fonctions à 2-4 variables, les tables de Karnaugh permettent une simplification visuelle.

K-map 2 variables :

	B=0	B=1
A=0	F(0,0)	F(0,1)
A=1	F(1,0)	F(1,1)

Exemple — K-map 3 variables :

Fonction : F(A,B,C) = Σ(1,3,5,7) → F = C

	AB=00	AB=01	AB=11	AB=10
C=0	0	0	0	0
C=1	1	1	1	1

Le groupe de 8 → F = C

Règles des K-maps :

Regrouper les '1' en groupes de 2ⁿ (1, 2, 4, 8...)
Les groupes peuvent se chevaucher
Les bords se raccordent (torique)
Plus le groupe est grand, plus la simplification est forte

Forme canonique

Somme de produits (SOP — Sum of Products)

F = A·B·C̄ + A·B̄·C + Ā·B·C

Chaque terme (minterm) correspond à une ligne de '1' dans la table de vérité.

Produit de sommes (POS — Product of Sums)

F = (A+B+C̄) · (A+B̄+C) · (Ā+B+C)

Chaque terme (maxterm) correspond à une ligne de '0' dans la table de vérité.

Application en VHDL

-- Expression non simplifiée
o_f <= (i_a AND i_b AND NOT i_c) OR
       (i_a AND NOT i_b AND i_c) OR
       (NOT i_a AND i_b AND i_c);
 
-- Après simplification (exemple)
-- → Le synthétiseur simplifie automatiquement !
-- Vous n'avez pas besoin de simplifier manuellement
-- Le synthétiseur utilise ses propres algorithmes (ESPRESSO, etc.)

Le synthétiseur VHDL effectue la simplification logique automatiquement — il n'est pas nécessaire de simplifier à la main pour la synthèse. Cependant, comprendre la simplification aide à comprendre le hardware produit.