Niveau conseillé : Bac+1 / Bac+2 — Cycle préparatoire, BTS, BUT, Licence

Présentation du chapitre

L’algèbre de Boole est l’outil mathématique utilisé pour décrire les systèmes logiques. À la différence de l’algèbre usuelle, ses variables ne prennent que deux valeurs, 0 et 1, et ses opérations fondamentales sont le complément, le produit logique et la somme logique. Les lois booléennes permettent de transformer une expression sans modifier sa fonction.

Ces transformations servent à vérifier des identités, à adapter un circuit à une technologie donnée, à réduire le nombre de portes et à construire des descriptions normalisées. Les théorèmes de De Morgan jouent un rôle central, car ils permettent de déplacer les inversions et de convertir des structures ET–OU en structures NAND ou NOR.

Le chapitre introduit ensuite les mintermes et les maxtermes. À partir d’une table de vérité, toute fonction peut être écrite sous une forme canonique somme de produits ou produit de sommes. La dernière partie formalise les méthodes de passage entre table de vérité, expression logique et circuit.

Objectifs pédagogiques

Prérequis

• connaître les variables binaires et les valeurs logiques 0 et 1 ;
• maîtriser les portes NON, ET, OU, NAND, NOR, XOR et XNOR ;
• savoir construire une table de vérité contenant 2ⁿ lignes ;
• lire une expression logique et respecter les parenthèses ;
• identifier les entrées, sorties et signaux intermédiaires d’un circuit.

Notations utilisées

Organisation du chapitre

Figure 1 — Résumé des principales lois de l’algèbre de Boole.

5.1. Lois fondamentales

5.1.1. Nature des opérations booléennes

Une identité booléenne est une égalité vraie pour toutes les valeurs possibles des variables. Elle ne décrit pas seulement un cas particulier : elle permet de remplacer une expression par une autre expression équivalente dans n’importe quel circuit. Deux expressions sont équivalentes lorsqu’elles produisent toujours la même sortie.

E₁ ≡ E₂ si et seulement si  E₁ = E₂ pour toutes les combinaisons des variables

Une loi peut être démontrée par raisonnement algébrique ou par table de vérité. La table de vérité est une méthode exhaustive : on calcule les deux membres ligne par ligne et on vérifie que leurs colonnes finales sont identiques.

5.1.2. Élément neutre

Un élément neutre ne modifie pas la variable à laquelle il est associé. Pour la somme logique, l’élément neutre est 0. Pour le produit logique, l’élément neutre est 1.

A + 0 = A    et     A · 1 = A

5.1.3. Élément absorbant

Un élément absorbant impose à lui seul le résultat de l’opération. Pour une somme logique, la présence d’un 1 rend immédiatement le résultat égal à 1. Pour un produit logique, la présence d’un 0 rend immédiatement le résultat égal à 0.

A + 1 = 1    et     A · 0 = 0

5.1.4. Idempotence

Répéter une même variable dans une somme ou dans un produit ne change pas le résultat. En logique, l’information « A est vraie deux fois » n’est pas différente de « A est vraie ».

A + A = A    et     A · A = A

5.1.5. Complémentarité

Une variable et son complément ne peuvent pas être simultanément vrais. En revanche, l’une des deux valeurs est toujours vraie. Cette propriété produit deux identités essentielles.

A + ¬A = 1    et     A · ¬A = 0

5.1.6. Commutativité

L’ordre des variables ne modifie ni une somme logique ni un produit logique. Cette loi autorise le réarrangement des termes afin de rapprocher les variables identiques ou complémentaires.

A + B = B + A     et    A · B = B · A

5.1.7. Associativité

Lorsque plusieurs opérations identiques se suivent, la manière de les regrouper ne modifie pas le résultat. Une porte à plusieurs entrées peut donc être décomposée en plusieurs portes à deux entrées sans changer la fonction idéale.

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

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

5.1.8. Distributivité

L’algèbre de Boole possède deux formes de distributivité. La première ressemble à la distributivité de l’algèbre ordinaire. La seconde, propre à la structure duale de l’algèbre de Boole, permet de distribuer une somme sur un produit.

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

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

5.1.9. Double négation

Complémenter deux fois une variable restitue sa valeur initiale. Dans un circuit idéal, deux inverseurs en cascade réalisent donc une fonction tampon logique.

¬(¬A) = A

5.1.10. Principe de dualité

Chaque identité booléenne possède une identité duale obtenue en échangeant simultanément les opérateurs + et · ainsi que les constantes 0 et 1. Les variables et leurs compléments restent inchangés.

5.1.11. Identités dérivées utiles

Certaines identités non listées parmi les lois de base sont fréquemment utilisées pour réduire une expression. Elles peuvent être démontrées à partir des lois précédentes.

5.1.12. Exemple complet de transformation algébrique

Simplifier la fonction F = A·B + A·¬B + ¬A·B.

La fonction simplifiée F = A+B peut être réalisée par une seule porte OU au lieu de trois produits, deux inverseurs et une somme dans l’expression initiale.

5.2. Théorèmes de De Morgan

5.2.1. Complément d’un produit

Le complément d’un produit logique est égal à la somme logique des compléments. Autrement dit, la condition « il n’est pas vrai que A et B soient tous les deux vrais » équivaut à « A est faux ou B est faux ».

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

5.2.2. Complément d’une somme

Le complément d’une somme logique est égal au produit logique des compléments. La condition « ni A ni B » exige que A soit faux et que B soit faux.

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

Figure 2 — Les deux théorèmes de De Morgan et la règle de transformation.

5.2.3. Généralisation à plusieurs variables

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

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

La règle s’applique à n’importe quel nombre de variables. Il faut complémenter chaque terme et remplacer chaque opérateur ET par OU, ou chaque opérateur OU par ET.

5.2.4. Méthode de transformation d’une expression

1. Repérer la barre de complément ou le symbole ¬ et déterminer exactement la sous-expression concernée.

2. Changer l’opérateur principal de la sous-expression : ET devient OU, OU devient ET.

3. Complémenter chacun des opérandes de cet opérateur.

4. Poursuivre récursivement lorsque les opérandes sont eux-mêmes des expressions composées.

5. Supprimer les doubles négations éventuelles.

6. Ajouter des parenthèses pour préserver l’ordre des opérations.

5.2.5. Utilisation pour transformer un circuit

Dans un schéma logique, un petit cercle sur une entrée ou une sortie représente une inversion. La règle dite de déplacement des bulles consiste à déplacer une inversion à travers une porte en changeant le type de porte : une porte ET devient une porte OU, et inversement. Cette transformation est une lecture graphique des théorèmes de De Morgan.

5.2.6. Réalisation avec NAND et NOR

Les formes somme de produits se prêtent naturellement à une réalisation NAND–NAND. Chaque produit est calculé par une NAND ; la NAND finale réalise la somme grâce à De Morgan. De manière duale, une forme produit de sommes se prête à une réalisation NOR–NOR.

5.2.7. Erreurs fréquentes avec De Morgan

5.3. Formes canoniques

5.3.1. Définition d’une forme canonique

Une forme canonique est une écriture normalisée dans laquelle chaque terme contient toutes les variables de la fonction, chacune apparaissant exactement une fois, sous forme directe ou complémentée. Pour n variables, il existe 2ⁿ mintermes et 2ⁿ maxtermes.

Nombre de mintermes = nombre de maxtermes = 2ⁿ

Les formes canoniques ne sont pas nécessairement minimales. Leur intérêt est d’être obtenues mécaniquement à partir de la table de vérité et de fournir une description complète de la fonction.

5.3.2. Mintermes

Un minterme est un produit logique contenant toutes les variables. Il vaut 1 pour une seule combinaison d’entrée. Pour construire le minterme associé à une ligne, une variable est écrite directement lorsque son bit vaut 1 et complémentée lorsque son bit vaut 0.

Règle du minterme : bit 1 → variable directe ; bit 0 → variable complémentée

Figure 3 — Règles de construction d’un minterme et d’un maxterme.

5.3.3. Maxtermes

Un maxterme est une somme logique contenant toutes les variables. Il vaut 0 pour une seule combinaison d’entrée. Sa règle de construction est l’inverse de celle du minterme : une variable est écrite directement lorsque le bit vaut 0 et complémentée lorsque le bit vaut 1.

Règle du maxterme : bit 0 → variable directe ; bit 1 → variable complémentée

5.3.4. Relation entre mintermes et maxtermes

Pour une même ligne i, le maxterme Mᵢ est le complément du minterme mᵢ. En effet, l’application de De Morgan au minterme inverse chaque littéral et transforme le produit en somme.

Mᵢ = ¬mᵢ    et     mᵢ = ¬Mᵢ

5.3.5. Forme canonique somme de produits

La forme canonique somme de produits, aussi appelée somme de mintermes, est obtenue en additionnant tous les mintermes associés aux lignes où la fonction vaut 1. Elle se note à l’aide du symbole Σm suivi des indices.

F = Σm(i₁, i₂, …)

1. Repérer toutes les lignes où F=1.

2. Convertir le mot d’entrée de chaque ligne en indice décimal.

3. Construire le minterme de chaque ligne.

4. Relier tous les mintermes par des opérateurs OU.

5. Écrire éventuellement la notation compacte Σm.

5.3.6. Forme canonique produit de sommes

La forme canonique produit de sommes, aussi appelée produit de maxtermes, est obtenue en multipliant tous les maxtermes associés aux lignes où la fonction vaut 0. Elle se note à l’aide du symbole ΠM suivi des indices.

F = ΠM(j₁, j₂, …)

1. Repérer toutes les lignes où F=0.

2. Convertir chaque mot d’entrée en indice décimal.

3. Construire le maxterme correspondant.

4. Relier tous les maxtermes par des opérateurs ET.

5. Écrire éventuellement la notation compacte ΠM.

Figure 4 — Procédure de construction des deux formes canoniques.

5.3.7. Exemple complet à partir d’une table de vérité

Considérons une fonction F(A,B,C) définie par la table suivante.

Les lignes où F=1 ont pour indices 1, 2, 5 et 7. La forme somme de produits est donc :

F = Σm(1,2,5,7)

F = ¬A·¬B·C + ¬A·B·¬C + A·¬B·C + A·B·C

Les lignes où F=0 ont pour indices 0, 3, 4 et 6. La forme produit de sommes est :

F = ΠM(0,3,4,6)

F = (A+B+C)(A+¬B+¬C)(¬A+B+C)(¬A+¬B+C)

5.3.8. Écriture d’une fonction directement à partir d’une table

5.3.9. Forme canonique et forme minimale

Une forme canonique contient toutes les variables dans chaque terme, alors qu’une forme simplifiée peut éliminer des variables. Par exemple, m₂+m₃ = ¬A·B·¬C + ¬A·B·C se simplifie en ¬A·B, car ¬C+C=1. La forme simplifiée est généralement plus économique à réaliser.

5.3.10. Cas particuliers et valeurs indifférentes

Dans certaines applications, quelques combinaisons d’entrée ne se produisent jamais ou leur sortie n’a pas d’importance. Elles sont notées X, d ou « don’t care ». Elles ne doivent pas être traitées comme des 0 ou des 1 imposés dans la définition initiale, mais elles peuvent être choisies de manière avantageuse lors d’une simplification ultérieure.

5.4. Passage entre différentes représentations

Figure 5 — Cycle de conversion entre les représentations d’une fonction logique.

5.4.1. De la table de vérité vers l’équation

La méthode la plus directe consiste à produire une forme canonique. Pour une somme de produits, chaque ligne où la sortie vaut 1 devient un minterme. Pour un produit de sommes, chaque ligne où la sortie vaut 0 devient un maxterme.

1. Compter les variables et vérifier que la table possède 2ⁿ lignes.

2. Choisir la forme souhaitée : Σm ou ΠM.

3. Relever les indices des lignes correspondantes.

4. Écrire les termes en appliquant la règle de polarité.

5. Combiner les termes avec l’opérateur externe approprié.

6. Vérifier l’expression sur au moins une ligne où F=1 et une ligne où F=0.

5.4.2. De l’équation vers le circuit logique

Chaque opérateur de l’expression devient une porte. Les compléments sont réalisés par des inverseurs, les produits par des portes ET et les sommes par des portes OU. Il faut respecter la structure des parenthèses et partager un signal intermédiaire lorsqu’une même sous-expression est réutilisée.

1. Identifier les compléments et placer les inverseurs nécessaires.

2. Repérer les opérations les plus internes aux parenthèses.

3. Créer une porte pour chaque sous-expression et nommer sa sortie.

4. Relier les résultats conformément aux opérations de niveau supérieur.

5. Vérifier le nombre d’entrées de chaque porte et la polarité des signaux.

6. Comparer l’équation du circuit reconstruit à l’équation de départ.

5.4.3. Du circuit vers l’équation

Pour analyser un circuit, il est déconseillé d’écrire immédiatement une expression globale. La méthode robuste consiste à nommer la sortie de chaque porte et à progresser des entrées vers la sortie.

1. Identifier les entrées primaires.

2. Nommer la sortie de chaque première porte : N₁, N₂, etc.

3. Écrire l’équation locale de chaque porte.

4. Continuer dans l’ordre de propagation jusqu’à la sortie.

5. Substituer les expressions intermédiaires si une forme globale est demandée.

6. Ajouter des parenthèses autour des sous-expressions substituées.

5.4.4. De l’équation vers la table de vérité

Pour construire une table à partir d’une expression, on énumère toutes les entrées puis on ajoute une colonne pour chaque sous-expression. Les colonnes intermédiaires réduisent les erreurs et rendent la correction vérifiable.

1. Lister les 2ⁿ combinaisons dans l’ordre binaire.

2. Créer une colonne pour chaque complément.

3. Créer ensuite les colonnes des produits et des sommes internes.

4. Calculer la sortie finale après les sous-expressions.

5. Contrôler les cas limites et les parenthèses.

Prenons F = ¬A·B + A·C.

La fonction vaut 1 sur les lignes 2, 3, 5 et 7, donc F = Σm(2,3,5,7).

5.4.5. Vérification de cohérence entre représentations

5.4.6. Erreurs fréquentes lors des conversions

5.5. Travaux dirigés

TD 1 — Établir la table de vérité d’une expression

On considère F(A,B,C)=¬A·B + A·¬C.

1. Identifier les sous-expressions nécessaires.

2. Construire les huit combinaisons de A, B et C.

3. Ajouter les colonnes ¬A, ¬C, ¬A·B et A·¬C.

4. Calculer F.

5. Donner la notation Σm et la notation ΠM de F.

TD 2 — Déterminer l’expression logique d’un circuit

Un circuit comporte une porte NAND recevant A et B, une porte NOR recevant B et C, puis une porte ET recevant les deux sorties.

1. Nommer les deux sorties intermédiaires N₁ et N₂.

2. Écrire les équations N₁ et N₂.

3. Écrire l’expression globale F.

4. Développer F avec De Morgan.

5. Construire la table de vérité pour vérifier l’expression.

TD 3 — Vérifier une identité booléenne

Vérifier l’identité A + ¬A·B = A + B par deux méthodes.

1. Méthode algébrique : utiliser la distributivité A+BC=(A+B)(A+C).

2. Méthode exhaustive : construire une table avec les deux membres.

3. Conclure sur l’équivalence et expliquer l’intérêt de l’identité pour la simplification.

TD 4 — Transformer un circuit avec De Morgan

La fonction est F = ¬[(A+B)·(C+¬D)].

1. Appliquer De Morgan au produit externe.

2. Appliquer De Morgan à chaque somme.

3. Supprimer les doubles négations.

4. Donner l’expression finale avec uniquement des sommes et des produits simples.

5. Proposer une réalisation à l’aide de portes NAND ou NOR.

TD 5 — Construire les formes canoniques

Une fonction G(A,B,C) vaut 1 lorsque le nombre de bits à 1 est au moins égal à deux.

1. Construire la table de vérité.

2. Identifier les indices des lignes où G=1.

3. Écrire G sous la forme Σm.

4. Développer la somme de mintermes.

5. Identifier les indices où G=0 et écrire la forme ΠM.

6. Comparer le nombre de termes des deux formes.

TD 6 — Problème de synthèse

Un système d’autorisation utilise trois entrées : I indique que l’utilisateur est identifié, D qu’un droit d’accès est valide et U qu’une procédure d’urgence est active. L’accès A est autorisé si l’utilisateur est identifié et possède le droit, ou si l’urgence est active.

1. Définir la fonction A(I,D,U).

2. Construire sa table de vérité.

3. Écrire ses formes canoniques Σm et ΠM.

4. Simplifier algébriquement la forme canonique.

5. Dessiner le circuit avec des portes de base.

6. Transformer le circuit en une réalisation NAND–NAND.

5.6. Activité pratique proposée

Vérification des lois et équivalence de circuits par simulation

L’activité peut être réalisée avec Logisim Evolution, Proteus, Multisim ou tout simulateur de logique numérique. Elle vise à vérifier qu’une identité algébrique correspond à une équivalence de circuits pour toutes les combinaisons d’entrée.

Synthèse du chapitre

Glossaire essentiel

Exercices d’application

Exercice 1 — Lois fondamentales

Simplifier en indiquant la loi utilisée à chaque étape :

1. F₁=A+0 ; F₂=B·1 ; F₃=C+C ; F₄=D·D.

2. F₅=A+1 ; F₆=B·0 ; F₇=C+¬C ; F₈=D·¬D.

3. F₉=A·B+B·A ; F₁₀=A+(B+A).

4. F₁₁=A·(B+¬B) ; F₁₂=(A+0)·(B+1).

Exercice 2 — Transformations algébriques

Simplifier les expressions suivantes :

1. F=A·B+A·¬B.

2. G=A+A·B.

3. H=A·(A+B).

4. K=A+¬A·B.

5. L=(A+B)(A+¬B).

6. M=A·B+¬A·B+A·¬B.

Exercice 3 — Vérification d’identités

1. Vérifier par table de vérité : A+B·C=(A+B)(A+C).

2. Vérifier par algèbre : A·B+A·¬B=A.

3. Vérifier par deux méthodes : A+¬A·B=A+B.

4. Déterminer si A·(B+C)=A·B+C est une identité. Justifier.

Exercice 4 — Théorèmes de De Morgan

Transformer et simplifier :

1. ¬(A·B·C).

2. ¬(A+B+C).

3. ¬[A·(B+C)].

4. ¬[(A+B)(C+D)].

5. ¬[A+¬(B·C)].

6. ¬{[A+¬B]·[¬C+D]}.

Exercice 5 — Mintermes et maxtermes

1. Écrire le minterme et le maxterme associés à ABC=010.

2. Écrire le minterme et le maxterme associés à ABC=111.

3. Donner l’indice de A·¬B·C·¬D.

4. Donner le mot binaire associé au maxterme ¬A+B+¬C+D.

5. Expliquer pourquoi un minterme vaut 1 sur une seule ligne.

Exercice 6 — Formes canoniques

Pour F(A,B,C)=Σm(0,2,3,6) :

1. Développer la somme de mintermes.

2. Construire la table de vérité.

3. Écrire la notation produit de maxtermes.

4. Développer la forme POS canonique.

5. Simplifier la fonction si possible.

Exercice 7 — Équation, table et circuit

On considère F=¬A·B+A·C.

1. Construire la table de vérité avec colonnes intermédiaires.

2. Donner les formes Σm et ΠM.

3. Décrire le circuit avec portes de base.

4. Écrire une réalisation NAND–NAND.

5. Vérifier la sortie pour A=1, B=0, C=1.

Exercice 8 — Analyse d’un circuit verbal

Une porte NOR reçoit A et B. Sa sortie et C alimentent une porte NAND. La sortie finale est F.

1. Nommer le signal intermédiaire N.

2. Écrire F en fonction de N et C.

3. Substituer N pour obtenir l’expression globale.

4. Appliquer De Morgan et simplifier.

5. Construire la table de vérité.

Exercice 9 — Problème de majorité

Une sortie M vaut 1 si au moins deux des trois entrées A, B et C valent 1.

1. Construire la table de vérité.

2. Écrire la forme canonique Σm.

3. Écrire la forme canonique ΠM.

4. Montrer que M=A·B+A·C+B·C.

5. Proposer un circuit logique minimal.

Exercice 10 — Système d’autorisation

Un accès est accordé si une carte C est valide et si le code P est correct, sauf lorsqu’un blocage B est actif. Une commande d’urgence U autorise toutefois l’accès indépendamment de C et P, mais seulement si B=0.

1. Définir la fonction A(C,P,B,U).

2. Factoriser l’expression obtenue.

3. Construire la table de vérité.

4. Donner la notation Σm.

5. Proposer une réalisation avec portes de base puis avec NAND.

Auto-évaluation

Corrigé synthétique

Exercice 1

F₁=A ; F₂=B ; F₃=C ; F₄=D ; F₅=1 ; F₆=0 ; F₇=1 ; F₈=0. F₉=A·B par commutativité et idempotence. F₁₀=A+B. F₁₁=A. F₁₂=A·1=A.

Exercice 2

Exercice 3

Les trois premières égalités sont des identités. Pour la quatrième, A(B+C)=AB+AC, et non AB+C. Un contre-exemple est A=0, C=1 : le membre gauche vaut 0 tandis que AB+C vaut 1.

Exercice 4

1. ¬A+¬B+¬C.

2. ¬A·¬B·¬C.

3. ¬A+¬B·¬C.

4. ¬A·¬B+¬C·¬D.

5. ¬A·(B·C).

6. ¬(A+¬B)+¬(¬C+D)=¬A·B+C·¬D.

Exercice 5

Pour 010 : m₂=¬A·B·¬C et M₂=A+¬B+C. Pour 111 : m₇=A·B·C et M₇=¬A+¬B+¬C. Le terme A·¬B·C·¬D correspond à 1010₂, donc m₁₀. Le maxterme ¬A+B+¬C+D est nul pour A=1, B=0, C=1, D=0, donc le mot est 1010 et l’indice M₁₀.

Exercice 6

F=¬A·¬B·¬C+¬A·B·¬C+¬A·B·C+A·B·¬C. Les zéros sont aux indices 1,4,5,7 : F=ΠM(1,4,5,7).

F=(A+B+¬C)(¬A+B+C)(¬A+B+¬C)(¬A+¬B+¬C)

Une simplification possible est F=¬A·¬C+¬A·B+A·B·¬C, puis F=¬A·B+B·¬C+¬A·¬C selon les regroupements. La forme exacte minimale sera étudiée plus systématiquement avec Karnaugh au chapitre suivant.

Exercice 7

La table a déjà été construite dans la section 5.4.4. F=Σm(2,3,5,7)=ΠM(0,1,4,6). Le circuit de base utilise un inverseur, deux portes ET et une porte OU. Pour A=1, B=0, C=1, F=1.

Réalisation NAND–NAND : N₁=NAND(¬A,B)=¬(¬A·B), N₂=NAND(A,C)=¬(A·C), puis F=NAND(N₁,N₂). Le complément ¬A peut être produit par NAND(A,A).

Exercice 8

N=¬(A+B). La sortie est F=¬(N·C). En substituant : F=¬[¬(A+B)·C]. Par De Morgan, F=(A+B)+¬C=A+B+¬C.

Exercice 9

M vaut 1 pour 011, 101, 110 et 111 : M=Σm(3,5,6,7). Les zéros sont 000,001,010,100 : M=ΠM(0,1,2,4). La forme simplifiée est M=A·B+A·C+B·C.

Exercice 10

L’accès est A=¬B·(C·P+U). Le blocage doit être inactif dans les deux modes. Cette forme factorisée utilise un inverseur, une porte ET pour C·P, une porte OU avec U, puis une porte ET avec ¬B.

Avec l’ordre CPBU, A=Σm(1,5,9,12,13).

Réponses de l’auto-évaluation

Vrai ; Faux ; Vrai ; Vrai ; Faux ; Vrai ; Faux ; Vrai ; Vrai ; Faux ; Vrai ; Vrai.