L'algèbre de Boole
George Boole, 1815-1864
George Boole, mathématicien irlandais, publie en 1854 "An Investigation of the Laws of Thought" — un système algébrique pour raisonner sur la logique formelle. Un siècle plus tard, Claude Shannon démontre que cette algèbre s'applique parfaitement aux circuits électroniques. Chaque opération logique devient une porte, chaque variable booléenne devient un niveau de tension.
L'algèbre de Boole permet de simplifier des expressions logiques, ce qui se traduit directement par des circuits plus simples, moins coûteux et plus rapides.
Les axiomes de base
| Opération OR (+) | Opération AND (·) |
|---|---|
| 0 + 0 = 0 | 0 · 0 = 0 |
| 0 + 1 = 1 | 0 · 1 = 0 |
| 1 + 0 = 1 | 1 · 0 = 0 |
| 1 + 1 = 1 | 1 · 1 = 1 |
Note : en algèbre de Boole, 1 + 1 = 1 (pas 2 !). Le OR logique n'est pas une addition arithmétique.
Les lois fondamentales
| Loi | Forme OR | Forme AND |
|---|---|---|
| Commutativité | A + B = B + A | A · B = B · A |
| Associativité | 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) |
| Identité | A + 0 = A | A · 1 = A |
| Annulation | A + 1 = 1 | A · 0 = 0 |
| Idempotence | A + A = A | A · A = A |
| Complémentarité | A + Ā = 1 | A · Ā = 0 |
| Double négation | NOT(NOT A) = A | |
| Absorption | A + A·B = A | A·(A + B) = A |
Les théorèmes de De Morgan
Auguste De Morgan (1806-1871) énonce deux théorèmes fondamentaux qui permettent de transformer des expressions AND en OR et vice-versa :
En français :
- Théorème 1 : "NON (A ET B)" = "NON-A OU NON-B"
Exemple : "l'alarme ne se déclenche pas si la porte ET la fenêtre sont ouvertes" équivaut à "l'alarme ne se déclenche pas si la porte n'est PAS ouverte OU la fenêtre n'est PAS ouverte". - Théorème 2 : "NON (A OU B)" = "NON-A ET NON-B"
Exemple : "ni l'un ni l'autre" = "pas l'un ET pas l'autre".
Simplification d'une expression : exemple pas à pas
Simplifions l'expression : F = A·B + A·B̄ + Ā·B
De 3 termes et 5 portes, on passe à 1 seul OR. C'est l'intérêt de l'algèbre de Boole dans la conception de circuits.
Vérification avec la table de vérité
| A | B | A·B + A·B̄ + Ā·B | A + B |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
Les colonnes sont identiques : la simplification est correcte.
- L'algèbre de Boole est un outil mathématique pour raisonner sur les 0 et 1.
- Idempotence : A + A = A et A · A = A (pas d'accumulation comme en arithmétique).
- Complémentarité : A + Ā = 1 et A · Ā = 0 (toujours !)
- De Morgan 1 : NOT(A·B) = Ā + B̄ — briser une AND → OR des compléments.
- De Morgan 2 : NOT(A+B) = Ā · B̄ — briser une OR → AND des compléments.
- Simplifier une expression = réduire le nombre de portes dans le circuit physique.