9
L’algèbre de Boole est une dérivée des mathématiques dans laquelle les variables ne peuvent prendre que deux valeurs : 0 et 1. Elle a été inventée en 1847 par le mathématicien anglais Georges Boole. Pour traduire des signaux en expressions mathématiques, on définit chaque signal élémentaire par des variables logiques et leur traitement par des fonctions logiques. Des méthodes, ou table de vérité, permettent de définir les opérations que l’on désire réaliser, et de transcrire le résultat en une expression algébrique. Grâce à des règles appelées lois de composition, ces expressions peuvent être simplifiées.
Une variable logique est une donnée binaire qui est donc représentée par les valeur 0 et 1. Les fonctions logiques acceptent plusieurs valeurs logiques en entrée et peuvent avoir deux états possibles en sortie : 0 ou 1. Les fonctions logiques de bases sont appelées portes logiques. Il s’agit de fonctions ayant une ou deux entrées et une sortie.
- La fonction OU (OR), représentée par le symbole algébrique [latex]+[/latex], positionne sa sortie à 1 si l’une ou l’autre de ses entrées est à 1
- La fonction ET (AND), représentée par le symbole algébrique [latex]\cdot[/latex], positionne sa sortie à 1 si ses deux entrées sont à 1
- La fonction OU EXCLUSIF (XOR), représentée par le symbole algébrique [latex]\oplus[/latex], positionne sa sortie à 1 si l’une ou l’autre de ses entrées est à 1 mais pas les deux simultanément
- La fonction NON (inverter), représentée par le symbole algébrique [latex]\bar{A}[/latex], positionne sa sortie à 1 si son entrée est à 0, et vice-versa
- La fonction NON OU (NOR) est la composition d’un NON et d’un OU
- La fonction NON ET (NAND) est la composition d’un NON et d’un ET
Une table de vérité est un tableau permettant de décrire toutes les possibilités de sorties en fonction des entrées.
| Nom de la porte | Entrée | Sortie | |
|---|---|---|---|
| A | B | S | |
| OR | 0 | 0 | 0 |
| 0 | 1 | 1 | |
| 1 | 0 | 1 | |
| 1 | 1 | 1 | |
Une expression algébrique peut prendre la forme [latex]S = A \cdot \bar{B}[/latex] et se traduire par la table suivante :
| A | B | C |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
L’algèbre de Boole possède des propriétés et des théorèmes qu’il convient de garder en mémoire.
Propriétés
- La commutativité, [latex]A \cdot B = B \cdot A[/latex] et [latex]A + B = B + A[/latex]
- L’associativité, [latex]\left( A \cdot B \right) \cdot C = A \cdot \left( B \cdot C \right)[/latex] et [latex]\left( A + B \right) + C = A + \left( B + C \right)[/latex]
- La priorité, sachant que, comme en arithmétique, le ET (c’est à dire la multiplication) est prioritaire devant le OU (c’est à dire l’addition), [latex]A + B \cdot C = A + \left( B \cdot C \right)[/latex]
- La distributivité, [latex]A \cdot \left( B + C \right) = \left( A \cdot B \right) + \left( A \cdot C \right) = A \cdot B + A \cdot C[/latex] et [latex]A + \left( B \cdot C \right) = \left( A + B \right) \cdot \left( A + C \right)[/latex]. Non ce n’est pas une erreur, la distributivité de l’addition existe en logique mais pas en arithmétique…
- Les éléments neutres, [latex]A \cdot 1 = A[/latex] et [latex]A + 0 = A[/latex]
- Les éléments absorbants, [latex]A \cdot 0 = 0[/latex] et [latex]A + 1 = 1[/latex]
- La complémentarité, [latex]A \cdot \bar{A} = 0[/latex] et [latex]A + \bar{A} = 1[/latex]
- L’idempotence, [latex]A \cdot A = A[/latex] et [latex]A + A = A[/latex]
Théorèmes
- Le théorème d’involution, [latex]\bar{\bar{A}} = A[/latex] et [latex]\bar{\bar{\bar{A}}} = \bar{A}[/latex]
- Le théorème d’inclusion, [latex]A \cdot B + A \cdot \bar{B} = A[/latex] et [latex]\left( A + B \right) \cdot \left(A + \bar{B} \right) = A[/latex]
- Le théorème d’allégement, [latex]A \cdot \left( \bar{A} + B \right) = A \cdot B[/latex] et [latex]A + \bar{A} \cdot B = A + B[/latex]
- Le théorème d’absorption, [latex]A \cdot \left( A + B \right) = A[/latex] et [latex]A + \left( A \cdot B \right) = A[/latex]
- Le théorème de De Morgan, [latex]NAND \left( A, B \right) = \overline{A \cdot B} = \bar{A} + \bar{B}[/latex] et [latex]NOR \left( A, B \right) = \overline{A + B} = \bar{A} \cdot \bar{B}[/latex]
