Apprendre › Chapitre 2

Algèbre de Boole : lois, De Morgan et simplification

7 min de lecture · Équipe bitGateLab

L'algèbre de Boole est le langage qui sert à décrire et à transformer les circuits numériques. Chaque expression correspond à un assemblage de portes, et chaque loi appliquée pour la simplifier se traduit par des portes économisées. Vous allez revoir ici les postulats, les lois les plus utiles, les théorèmes de De Morgan et la manière de simplifier une expression pas à pas, en justifiant chaque opération.

Variables et opérations

Une variable booléenne ne prend que les valeurs 0 et 1. Il existe trois opérations de base : le complément (A, porte NOT), le produit logique (A·B ou AB, porte AND) et la somme logique (A + B, porte OR). En l'absence de parenthèses, l'ordre de priorité est le suivant : d'abord le complément, puis le produit et enfin la somme. Ainsi, A + BC signifie A + (B·C), comme en algèbre ordinaire.

Postulats

Toute l'algèbre repose sur quelques postulats. Remarquez qu'ils vont par paires : l'un pour la somme, l'autre pour le produit.

Postulat	Forme avec la somme	Forme avec le produit
Élément neutre	A + 0 = A	A · 1 = A
Commutativité	A + B = B + A	AB = BA
Distributivité	A + BC = (A + B)(A + C)	A(B + C) = AB + AC
Complément	A + A = 1	A · A = 0

Principe de dualité : si une égalité est vraie, celle que l'on obtient en échangeant + et ·, ainsi que 0 et 1 (sans toucher aux variables ni à leurs barres), l'est aussi. C'est pourquoi chaque loi possède une version « jumelle ». Observez la distributivité de la somme, A + BC = (A + B)(A + C) : elle n'existe pas dans l'algèbre des nombres réels, mais ici elle est parfaitement valable.

Lois et théorèmes utiles

Des postulats se déduisent les règles suivantes, celles que vous utiliserez le plus pour simplifier :

Loi	Forme avec la somme	Forme avec le produit
Idempotence	A + A = A	AA = A
Élément absorbant	A + 1 = 1	A · 0 = 0
Involution	A = A
Associativité	A + (B + C) = (A + B) + C	A(BC) = (AB)C
Absorption	A + AB = A	A(A + B) = A
Absorption du complément	A + AB = A + B	A(A + B) = AB
Adjacence	AB + AB = A	(A + B)(A + B) = A
Consensus	AB + AC + BC = AB + AC	(A + B)(A + C)(B + C) = (A + B)(A + C)

Chacune de ces lois peut se vérifier avec une table de vérité : si les deux colonnes coïncident sur toutes les lignes, l'égalité est vraie. Par exemple, pour A + AB = A : avec A = 0, les deux membres valent 0 quel que soit B ; avec A = 1, tous deux valent 1. L'absorption du complément se démontre ainsi : A + AB = (A + A)(A + B) = 1·(A + B) = A + B, en utilisant la distributivité de la somme.

Théorèmes de De Morgan

Ces deux théorèmes vous indiquent comment « casser » une longue barre :

A · B = A + B (le complément d'un produit est la somme des compléments).
A + B = A · B (le complément d'une somme est le produit des compléments).

La règle pratique : en coupant la barre, changez l'opération qui se trouvait dessous (· en + ou + en ·) et complémentez chaque terme. Elle fonctionne quel que soit le nombre de variables : ABC = A + B + C.

A	B	AB	A + B	A + B	AB
0	0	1	1	1	1
0	1	1	1	0	0
1	0	1	1	0	0
1	1	0	0	0	0

Du point de vue des circuits, De Morgan dit qu'une NAND équivaut à une OR avec des petits cercles d'inversion sur les entrées, et qu'une NOR équivaut à une AND avec des petits cercles sur les entrées. C'est la base de la conversion de n'importe quel schéma en NAND seules ou en NOR seules, comme expliqué dans portes logiques.

Exemple 1 : appliquer De Morgan. Simplifiez F = AB + C.

La longue barre couvre une somme : AB + C = AB · C.
Cassez la barre du produit : AB = A + B.
Résultat : F = (A + B)C = AC + BC.

Vérification avec A = 1, B = 1, C = 0 : l'expression d'origine donne 1 + 0 = 0 ; le résultat donne (0 + 0)·1 = 0. Avec A = 0, B = 1, C = 0 : expression d'origine 0 + 0 = 1 ; résultat (1 + 0)·1 = 1.

Simplification algébrique pas à pas

Simplifier, c'est réduire le nombre de termes et de littéraux (chaque apparition d'une variable, complémentée ou non). Moins de littéraux, c'est moins d'entrées de portes. Il n'existe pas d'algorithme unique en algèbre pure ; les tactiques suivantes fonctionnent presque toujours :

Cherchez des paires de termes qui ne diffèrent que par une seule variable et appliquez l'adjacence.
Mettez en facteur et cherchez un A + A = 1 caché.
Si un terme est contenu dans un autre, éliminez-le par absorption.
Vous pouvez dupliquer un terme (idempotence) pour le combiner avec deux voisins différents.

Exemple 2. Simplifiez F = AB + AB + AB.

Factorisez les deux premiers termes : AB + AB = A(B + B) = A·1 = A.
Il reste F = A + AB.
Absorption du complément : A + AB = A + B.

F = A + B. Vous êtes passé de trois portes AND, une OR à trois entrées et deux inverseurs à une seule OR.

Exemple 3 : fonction majorité. Simplifiez F = ABC + ABC + ABC + ABC.

Par idempotence, ABC = ABC + ABC + ABC. Écrivez trois copies afin de combiner chacune avec un voisin.
ABC + ABC = BC(A + A) = BC.
ABC + ABC = AC(B + B) = AC.
ABC + ABC = AB(C + C) = AB.

F = AB + AC + BC. Elle vaut 1 lorsqu'au moins deux des trois entrées valent 1 : c'est un circuit de vote. Vous verrez que c'est aussi la sortie de retenue de l'additionneur complet.

Exemple 4 : distributivité de la somme. Simplifiez F = (A + B)(A + C).

Développez : AA + AC + AB + BC = A + AC + AB + BC.
Mettez A en facteur : A(1 + C + B) + BC.
Élément absorbant : 1 + C + B = 1, il reste donc A + BC.

C'est précisément le postulat de distributivité de la somme, lu à l'envers.

Erreurs fréquentes

Appliquer De Morgan sans changer l'opération : AB n'est pas AB, mais A + B.
« Simplifier » des termes de part et d'autre comme en algèbre ordinaire. En algèbre de Boole, il n'y a ni soustraction ni division : de A + B = A + C, on ne peut pas déduire que B = C.
Oublier la priorité des opérations : A + BC n'est pas (A + B)C.
Ne casser qu'une partie d'une longue barre. La barre de AB + C porte sur toute la somme ; travaillez de la barre la plus extérieure vers l'intérieur.
S'arrêter trop tôt. Après chaque étape, vérifiez s'il reste un terme à absorber ou un terme de consensus redondant.

Essayez dans le simulateur

Une simplification correcte donne un circuit qui a exactement la même table de vérité que l'original. Le simulateur vous permet de le vérifier sans dresser la table à la main.

Dans l'éditeur, réalisez le circuit d'origine d'un exemple, comme AB + AB + AB, avec ses entrées et sa sortie.
Générez sa table de vérité et notez-la.
Sur une autre sortie du même schéma, réalisez la version simplifiée (A + B) avec les mêmes entrées.
Faites passer les entrées par toutes les combinaisons et observez que les deux sorties coïncident toujours.
Demandez l'expression simplifiée à partir de la table et comparez-la à celle que vous avez obtenue à la main.

Exercices

Simplifiez F = AB + AB + AB.
Réponse
AB + AB = A. Ensuite A + AB = A + B (absorption du complément). F = A + B = AB : c'est une NAND.
Simplifiez F = A + B.
Réponse
De Morgan : A · B = AB.
Simplifiez F = A(A + B) + B(B + C).
Réponse
Par absorption, A(A + B) = A et B(B + C) = B. F = A + B.
Démontrez le théorème du consensus : AB + AC + BC = AB + AC.
Réponse
Écrivez BC = BC(A + A) = ABC + ABC. Alors AB + ABC = AB (absorption) et AC + ABC = AC (absorption). Il reste AB + AC.