L'algèbre de Boole : apprendre à calculer avec le vrai et le faux

Lire une table de vérité ne suffit pas. Pour concevoir un circuit, il faut savoir calculer avec ces expressions : les écrire, les transformer, les simplifier, et surtout vérifier qu'on n'a pas changé leur sens.

L'enjeu est concret : dans un circuit, une expression plus courte demande moins de portes, donc un composant plus petit, moins cher et moins gourmand.

L'article suit un fil en trois temps. On apprend d'abord à calculer (parties 1 à 5 : lire, évaluer, démontrer, simplifier). On apprend ensuite à nier une expression (partie 6 : lois de De Morgan). On construit enfin le composant qui réalise une expression, la porte logique, avec ses symboles normalisés (partie 7). Les parties 8 et 9 ouvrent des pistes et rappellent les limites.

Il s'adresse à deux publics : les débutants, qui suivent le fil principal avec des exemples chiffrés, et les spécialistes, qui trouveront des approfondissements dans les encadrés « Pour aller plus loin ». Chaque terme est défini à sa première apparition et repris dans le glossaire.

01Rappel express : variables, opérations, tables de vérité

Une variable booléenne est une grandeur qui ne vaut que 0 (faux) ou 1 (vrai). On l'associe à une question à réponse oui ou non : A = « la porte est ouverte », B = « il pleut ».

Trois opérations de base, que nous connaissons dans le langage courant :

• NON (négation, notée ¬A) : inverse la valeur.
• ET (conjonction, notée A·B) : vaut 1 seulement si les deux valent 1.
• OU (disjonction, notée A+B) : vaut 1 si au moins une des deux vaut 1.

Une table de vérité liste toutes les combinaisons des entrées et la sortie correspondante :

Ces opérations se réalisent avec des interrupteurs : en série pour le ET, en parallèle pour le OU (voir l'article sur le binaire).

Une quatrième opération est très utilisée : le OU exclusif (XOR, noté A⊕B). Il vaut 1 quand les deux entrées sont différentes : l'une ou l'autre, mais pas les deux. Nous verrons qu'il se construit avec les trois premières.

02Lire une expression : l'ordre de priorité

Quand on écrit une expression comme A + B·C, il faut savoir par où commencer. Comme en arithmétique, où la multiplication passe avant l'addition, on applique dans l'ordre : NON, puis ET, puis OU. Ainsi A + B·C signifie A + (B·C).

Vérification chiffrée : avec A = 1, B = 0, C = 0. On calcule d'abord B·C = 0·0 = 0, puis A + 0 = 1. Si on avait lu à tort (A + B)·C, on aurait trouvé (1 + 0)·0 = 0. Les deux lectures donnent des résultats différents, d'où l'importance de la priorité, et des parenthèses en cas de doute.

Méthode pour évaluer une expression : remplacer les variables par leurs valeurs, calculer d'abord les NON, puis les parenthèses et les ET, puis les OU. Avec un peu d'habitude, on le fait de tête.

03Attention : ce n'est pas l'algèbre du collège

• 1 + 1 = 1 (« vrai OU vrai » reste « vrai »). Il n'y a pas de 2 en algèbre de Boole : il n'existe que 0 et 1.
• A·A = A et A + A = A : répéter une condition ne change rien. « Il pleut ET il pleut » revient à « il pleut ».
• A + B·C = (A + B)·(A + C) : la distributivité marche « dans les deux sens », ce qui n'est pas vrai pour les nombres ordinaires. Vérifions avec A = 1, B = 0, C = 0 : à gauche 1 + 0·0 = 1 ; à droite (1+0)·(1+0) = 1·1 = 1. Avec A = 0, B = 1, C = 1 : à gauche 0 + 1 = 1 ; à droite (0+1)·(0+1) = 1. Et un cas qui donne 0, avec A = 0, B = 1, C = 0 : à gauche 0 + 1·0 = 0 ; à droite (0+1)·(0+0) = 1·0 = 0.

Trois cas ne suffisent pas à prouver une règle. La table complète des 8 combinaisons, elle, le prouve : les colonnes « A + B·C » et « (A + B)·(A + C) » sont identiques sur toutes les lignes.

04Les règles de calcul, expliquées

Ces règles s'appellent des lois. On les retrouve, avec des noms parfois légèrement différents, dans tous les cours d'algèbre de Boole.

Deux façons de prouver une règle

1. Par table de vérité : on teste tous les cas. Prenons l'absorption A + A·B = A :

Avec n variables, il y a 2 puissance n lignes : 4 lignes pour 2 variables, 8 pour 3, 16 pour 4. C'est la méthode la plus sûre, mais elle devient longue quand n grandit.

2. Par calcul : on applique les règles du tableau, pas à pas :

A + A·B = A·1 + A·B (élément neutre) = A·(1 + B) (distributivité) = A·1 (1 + B = 1, élément absorbant) = A (élément neutre).

Le calcul est plus court, mais il demande de savoir quelle règle appliquer. D'où l'intérêt des exemples qui suivent.

05Trois exemples guidés et une méthode

Exemple 1 : simplifier une expression

On veut simplifier A·B + A·¬B.

1. On met A en facteur (distributivité à l'envers) : A·(B + ¬B).
2. Or B + ¬B = 1 (complément : l'un des deux vaut forcément 1).
3. Donc A·1 = A (élément neutre).

L'expression se réduit à A : B n'avait aucune influence. Concrètement : « la porte est ouverte et il pleut, ou la porte est ouverte et il ne pleut pas » revient à « la porte est ouverte ».

Exemple 2 : une alarme de maison

Une alarme doit sonner si elle est armée (E) ET si une porte est ouverte (P) OU une fenêtre est brisée (V). On peut l'écrire de deux façons équivalentes :

• Forme factorisée : S = E·(P + V). Elle demande 2 portes (un OU, puis un ET).
• Forme développée : S = E·P + E·V. Elle demande 3 portes (deux ET, puis un OU).

Vérification chiffrée : E = 1, P = 0, V = 1. Forme factorisée : 1·(0+1) = 1·1 = 1. Forme développée : 1·0 + 1·1 = 0 + 1 = 1. Même résultat, mais la première coûte une porte de moins. Multipliée par des millions de circuits, cette économie compte : c'est exactement ce que Shannon cherchait à faire avec les relais.

Exemple 3 : de la table de vérité à l'expression (le vote à la majorité)

Un circuit doit sortir 1 quand au moins deux de ses trois entrées A, B, C valent 1. Sa table de vérité :

Étape 1 : écrire un terme par ligne où la sortie vaut 1. Chaque terme est un ET qui n'est vrai que pour cette combinaison (on nie les variables qui valent 0) :

M = ¬A·B·C + A·¬B·C + A·B·¬C + A·B·C

Étape 2 : simplifier. On utilise l'idempotence pour écrire le dernier terme A·B·C trois fois (le résultat ne change pas), puis on regroupe par paires :

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

Résultat : M = A·B + A·C + B·C. Trois ET et deux OU au lieu de quatre termes de trois variables. Cette fonction « majorité » n'est pas un jouet : c'est la retenue d'un additionneur complet (partie 7).

Méthode : simplifier en 5 étapes

1. Regarder. Repérer les termes (séparés par des +) et les facteurs qu'ils ont en commun.
2. Réordonner. Avec la commutativité et l'associativité, placer côte à côte les termes qui se ressemblent.
3. Chercher une paire. Deux termes qui ne diffèrent que par une variable (A·B + A·¬B) : mettre en facteur, appliquer le complément (B + ¬B = 1), puis le neutre.
4. Chercher un cas particulier. Absorption (A + A·B), idempotence (A + A), élément nul (A·0, A + 1), double négation, et les lois de De Morgan pour toute négation placée sur une parenthèse. Ces lois disent comment nier une expression composée : nier un ET donne le OU des négations, nier un OU donne le ET des négations, soit ¬(A·B) = ¬A + ¬B et ¬(A + B) = ¬A·¬B. Elles sont expliquées et vérifiées en partie 6.
5. Vérifier. Tester le résultat sur au moins deux jeux de valeurs, ou par une table de vérité complète. Une simplification non vérifiée n'est pas une simplification.

Exemple. Simplifier B·A + A·¬B. (2) Commutativité : B·A = A·B, donc A·B + A·¬B. (3) Paire : A·(B + ¬B) = A·1 = A. (5) Vérification : A = 1, B = 0 → 0 + 1 = 1 = A ; A = 0, B = 1 → 0 + 0 = 0 = A. Réponse : A.

06Les lois de De Morgan : nier une phrase composée

Ces deux lois disent comment nier un ET ou un OU :

• ¬(A·B) = ¬A + ¬B
• ¬(A+B) = ¬A · ¬B

Un moyen mnémotechnique anglais résume la méthode : « break the line, change the sign » (« casser la barre, changer le signe »). On « casse » la négation, on la place sur chaque variable, et on échange ET et OU.

En français : nier « il pleut ET il vente » donne « il ne pleut pas OU il ne vente pas » (il suffit que l'un des deux manque). Et nier « je prends du thé OU du café » donne « je ne prends pas de thé ET pas de café » (ni l'un ni l'autre).

Vérification chiffrée pour la première loi : avec A = 1 et B = 0, le premier membre vaut ¬(1·0) = ¬0 = 1 ; le second ¬1 + ¬0 = 0 + 1 = 1. Avec A = 1 et B = 1 : ¬(1·1) = 0 et ¬1 + ¬1 = 0 + 0 = 0.

Où l'utilise-t-on ? Dans la conception de circuits (pour transformer un ET en OU et réduire les types de portes), mais aussi dans les moteurs de recherche et les programmes : chercher les documents qui ne contiennent pas « chats » ET « chiens » revient à chercher ceux qui ne contiennent pas « chats » OU pas « chiens ».

07Des règles aux portes logiques

Une porte logique est un circuit électronique qui réalise une opération booléenne : elle prend un ou plusieurs bits en entrée et fournit un bit en sortie. L'algèbre de Boole donne les règles, les portes les réalisent en matériel.

Les portes usuelles

• NON (inverseur) : une entrée, sortie inversée.
• NAND = « NON-ET » : l'inverse du ET. NOR = « NON-OU » : l'inverse du OU.
• XOR : vaut 1 si les deux entrées sont différentes. On le construit avec les trois opérations de base : A⊕B = A·¬B + ¬A·B. Vérification : A = 1, B = 0 → 1·1 + 0·0 = 1 ; A = 1, B = 1 → 1·0 + 0·1 = 0.

Les symboles des portes

Sur un schéma de circuit, chaque porte a un symbole. Ceux ci-dessous sont les symboles à « formes distinctives » de la norme ANSI/IEEE 91-1984. La norme internationale CEI 60617-12 propose aussi des symboles rectangulaires, et les deux familles coexistent. Trois règles de lecture : la forme donne la fonction de base (dos plat pour le ET, dos creusé pour le OU, triangle pour le NON) ; un petit cercle, la bulle, sur une sortie signifie « inversé » ; le XOR se reconnaît au trait courbe supplémentaire à l'entrée du symbole du OU.

À quoi servent-elles ? Additionner deux bits

La colonne « Somme » est exactement la table du XOR, et la colonne « Retenue » celle du ET. Deux portes suffisent donc à construire un demi-additionneur. Il est « demi » car il ne sait pas recevoir une retenue venant de la colonne précédente.

Un additionneur complet reçoit trois bits : A, B et la retenue entrante. Sa somme est un XOR des trois, et sa retenue sortante vaut 1 si au moins deux des trois entrées valent 1 : c'est la fonction « majorité » de l'exemple 3. En chaînant des additionneurs complets, on additionne des nombres de plusieurs bits. Claude Shannon présentait déjà un additionneur en base deux à la fin de son mémoire de 1937.

Exemple chiffré : 5 + 3 sur 4 bits. 0101 + 0011 : colonne de droite 1+1 = 0, retenue 1 ; deuxième colonne 0+1+1 = 0, retenue 1 ; troisième colonne 1+0+1 = 0, retenue 1 ; quatrième colonne 0+0+1 = 1. Résultat : 1000, soit 8. Le calcul est bon.

Au-delà de l'addition

Combinées, les portes réalisent aussi des comparateurs (A est-il égal à B ?), des multiplexeurs (choisir une entrée parmi plusieurs, comme un aiguillage) et des décodeurs (activer une ligne selon un code). L'unité de calcul d'un processeur est un assemblage de ces briques.

08Pour aller plus loin

09Limites et idées reçues

• Le « + » n'est pas une addition. C'est la confusion la plus fréquente : 1 + 1 = 1 en algèbre de Boole.
• Une table de vérité décrit un instant. Elle ne dit rien du temps : une expression booléenne n'a pas de mémoire. C'est la bascule, objet du prochain article de la série, qui apporte la mémoire.
• Tous les noms de règles ne sont pas universels. Certaines règles (comme A·B + A·¬B = A) portent des noms différents selon les cours, ou aucun nom. L'important est de savoir les vérifier, pas de les réciter.
• Boole ne pensait pas à des ordinateurs. Il voulait décrire les lois de la pensée ; ce sont Shannon, Nakashima et d'autres qui ont montré, dans les années 1930, que la même algèbre décrit des circuits.

10Conclusion

L'algèbre de Boole est une algèbre étonnamment simple : deux valeurs, trois opérations, une dizaine de règles, et la possibilité de tout vérifier par une table de vérité. Elle permet de simplifier une expression sans changer son sens, donc de construire des circuits plus petits et d'écrire des conditions plus claires. La page d'exercices corrigés (à paraître) permettra de vérifier que les règles sont acquises, pas à pas.

Mais une expression booléenne ne retient rien : elle calcule un résultat à partir des entrées présentes. Pour qu'un circuit se souvienne, il faut un composant d'un autre type. C'est le sujet du prochain article de la série : la bascule, ou comment une donnée devient mémoire.

11Glossaire

• Absorption : règle A + A·B = A (et sa duale A·(A + B) = A).
• Additionneur complet : circuit qui additionne trois bits (A, B et la retenue entrante).
• Algèbre de Boole : algèbre où les variables ne valent que 0 ou 1, avec les opérations ET, OU, NON.
• Associativité : (A·B)·C = A·(B·C) et (A + B) + C = A + (B + C) ; les parenthèses d'une suite de ET ou de OU n'importent pas.
• Commutativité : A·B = B·A et A + B = B + A ; l'ordre n'importe pas.
• Complément : règles A·¬A = 0 et A + ¬A = 1.
• De Morgan (lois de) : règles pour nier un ET ou un OU : ¬(A·B) = ¬A + ¬B et ¬(A+B) = ¬A·¬B.
• Demi-additionneur : circuit qui additionne deux bits ; somme = XOR, retenue = ET.
• Distributivité : A·(B + C) = A·B + A·C, et aussi A + B·C = (A + B)·(A + C).
• Double négation : ¬(¬A) = A.
• Dualité : principe selon lequel une règle reste vraie si l'on échange ET et OU, ainsi que 0 et 1.
• Élément absorbant (ou nul) : A·0 = 0 et A + 1 = 1.
• Élément neutre : A·1 = A et A + 0 = A.
• Forme normale disjonctive : expression écrite comme une somme (OU) de produits (ET), un terme par ligne à 1 de la table de vérité.
• Idempotence : règles A·A = A et A + A = A.
• Multiplexeur : circuit qui choisit une entrée parmi plusieurs, comme un aiguillage.
• NAND, NOR : portes « NON-ET » et « NON-OU », inverses du ET et du OU.
• Porte logique : circuit réalisant une opération booléenne.
• Table de vérité : tableau des sorties pour toutes les entrées possibles.
• Tableau de Karnaugh : grille qui présente une table de vérité de façon à repérer d'un coup d'œil les simplifications.
• Variable booléenne : grandeur qui ne vaut que 0 ou 1.
• XOR (OU exclusif) : vaut 1 si les deux entrées diffèrent ; A⊕B = A·¬B + ¬A·B.