L'algèbre de Boole et les portes logiques
Partie 3 sur 4
7Les lois de composition
Les lois de composition sont des règles logiques qui permettent de simplifier l’écriture des expressions algébriques. Elles sont vraies pour toutes les valeurs possibles des variables : on peut le vérifier en dressant la table de vérité des deux côtés. En voici la liste, avec un commentaire pour chacune.
7.1Associativité
(A.B).C est équivalent à A.(B.C) ; (A+B)+C est équivalent à A+(B+C). On peut donc regrouper comme on veut une suite de « et » ou de « ou » : on écrit simplement A.B.C ou A+B+C. Cela revient à brancher plus de deux interrupteurs en série ou en parallèle.
7.2Commutativité
A.B est équivalent à B.A ; A+B est équivalent à B+A. L’ordre des entrées ne compte pas.
7.3Distributivité
A.(B+C) est équivalent à A.B + A.C, et (c’est la surprise par rapport à l’arithmétique) A+(B.C) est équivalent à (A+B).(A+C). En arithmétique ordinaire, seule la première forme existe ; en algèbre de Boole, l’opération « ou » se distribue aussi sur le « et ».
7.4Idempotence
A.A est équivalent à A ; A+A est équivalent à A. Répéter une information ne la change pas : « il pleut et il pleut » dit la même chose que « il pleut ». (Cette loi n’a aucun équivalent en arithmétique : 2 + 2 n’est pas 2.)
7.5Identité
1.A est équivalent à A ; 0+A est équivalent à A. Le 1 est l’élément neutre du « et », le 0 celui du « ou » : ajouter une condition toujours vraie, ou une possibilité toujours fausse, ne change rien.
7.6Nullité
0.A est équivalent à 0 ; 1+A est équivalent à 1. Un « et » avec une condition toujours fausse est toujours faux ; un « ou » avec une possibilité toujours vraie est toujours vrai.
7.7Inversion
A./A est équivalent à 0 ; A+/A est équivalent à 1. Une chose ne peut pas être vraie et fausse à la fois (principe de non-contradiction), et elle est forcément vraie ou fausse (principe du tiers exclu). Ce sont les deux piliers de la logique classique, que l’on retrouve ici sous forme d’équations.
7.8Absorption
A.(A+B) est équivalent à A ; A+A.B est équivalent à A. Si A est vrai, la condition « A ou B » l’est déjà ; et dans « A ou (A et B) », la deuxième partie n’ajoute rien. On peut d’ailleurs démontrer l’absorption avec les autres lois.
A.(A+B) = A.A + A.B (distributivité) = A + A.B (idempotence) = A.1 + A.B (identité) = A.(1+B) (distributivité) = A.1 (nullité : 1+B = 1) = A (identité). Sur la deuxième ligne apparaît la deuxième loi d’absorption : les deux lois se démontrent l’une par l’autre.
7.9Le théorème de De Morgan
Le théorème de De Morgan (du nom du logicien britannique Augustus De Morgan, contemporain et ami de Boole) s’énonce en deux formules : /(A + B) est équivalent à /A . /B ; et /(A . B) est équivalent à /A + /B. En mots : le contraire d’un « ou » est le « et » des contraires ; le contraire d’un « et » est le « ou » des contraires. Exemple de la vie courante : « je ne prends ni le train ni le bus » (non (train ou bus)) veut dire « je ne prends pas le train et je ne prends pas le bus ». Cette loi est utilisée sans cesse : elle permet de transformer un circuit à base de ET et de OU en un circuit à base de NON ET seulement, d’où l’universalité vue en 3.5.
7.10Un exemple de simplification
Simplifions l’expression du circuit de la partie suivante : S = (A + B) . (A + /C). On développe : S = A.A + A./C + B.A + B./C. Par idempotence A.A = A, donc S = A + A./C + A.B + B./C. On met A en facteur dans les trois premiers termes : S = A.(1 + /C + B) + B./C. Or 1 + /C + B = 1 (nullité), donc S = A + B./C. L’expression de départ nécessitait deux portes OU, un NON et un ET ; la version simplifiée n’a plus qu’un NON, un ET et un OU. On a économisé une porte tout en gardant exactement la même fonction. À l’échelle d’un processeur, ces économies se comptent par millions.
Une vérification utile : on peut toujours contrôler une simplification en dressant les tables de vérité des deux formules et en vérifiant qu’elles coïncident ligne à ligne. Pour trois variables, huit lignes suffisent. C’est ce que fait un logiciel de conception lorsqu’il « prouve » que le circuit simplifié est équivalent au circuit d’origine.
7.11Les méthodes systématiques
Simplifier à la main demande de l’intuition. Pour les formules de quelques variables, une méthode graphique, le tableau de Karnaugh, présente la table de vérité sous forme de grille où les « 1 » voisins se regroupent à vue d’œil. Pour des centaines de variables, des logiciels appliquent des algorithmes qui font la même chose automatiquement. Il est utile de connaître l’existence de ces outils, même si, pour l’apprentissage, les lois ci-dessus suffisent.
Pour s’exercer
Exercice 4 : vérifier De Morgan
Dressez la table de vérité de /(A . B) et de /A + /B. Que constatez-vous ?
Voir la réponse
Pour (A,B) = (0,0) : A.B = 0, donc /(A.B) = 1 ; /A + /B = 1 + 1 = 1. Pour (0,1) : 1 et 1+0 = 1. Pour (1,0) : 1 et 0+1 = 1. Pour (1,1) : A.B = 1, donc /(A.B) = 0 ; /A + /B = 0 + 0 = 0. Les deux colonnes sont identiques (1, 1, 1, 0) : c’est la table du NON ET. Les deux formules sont équivalentes.
Exercice 5 : simplifier
Simplifiez S = A.B + A./B + /A.B.
Voir la réponse
Les deux premiers termes ont A en facteur : A.B + A./B = A.(B + /B) = A. Reste S = A + /A.B. Par distributivité, A + /A.B = (A + /A).(A + B) = 1.(A + B) = A + B. Résultat : S = A + B. (Vérification : S vaut 0 seulement si A = 0 et B = 0, comme un OU.)
8Les circuits logiques
On appelle circuit logique (ou circuit combinatoire) un ensemble de portes logiques reliées entre elles pour répondre à une expression algébrique. Il s’agit donc de transcrire en schéma l’expression que l’on a simplifiée grâce aux lois de composition.
8.1La représentation conventionnelle
Chaque porte a un symbole standard : le ET est un « D » couché dont le côté plat reçoit les entrées, le OU un croissant pointu, le NON un triangle suivi d’un petit rond (le rond signifie « inverser »). Le OU exclusif ressemble au OU, avec un double trait sur le côté des entrées. Ajouter un petit rond à la sortie d’un ET donne un NON ET, et d’un OU un NON OU. Par commodité, la figure 2 de cet article dessine les portes sous forme de boîtes étiquetées, ce qui revient au même et se lit sans connaître les symboles.
8.2Un exemple complet
L’expression (A+B).(A+/C) sera schématisée comme sur la figure 2 : une première porte OU reçoit A et B ; un NON inverse C ; une seconde porte OU reçoit A et le résultat du NON ; une porte ET combine les deux sorties de OU. Chaque fil porte un 0 ou un 1 ; on peut suivre un cas pas à pas. Avec A = 0, B = 1, C = 1 : le premier OU donne 1 ; le NON de C donne 0 ; le second OU donne 0 + 0 = 0 ; le ET donne 1 . 0 = 0. La sortie est donc 0, ce que confirme la forme simplifiée A + B./C = 0 + 1.0 = 0.
8.3Combinatoire ou séquentiel
Tous les circuits de cet article sont dits combinatoires : leur sortie ne dépend que des entrées présentes à l’instant considéré. Ils n’ont pas de mémoire. Un autre type de circuit, le circuit séquentiel, rebouche la sortie d’une porte vers l’entrée d’une autre et fabrique ainsi un petit circuit qui retient une valeur : la bascule. Une bascule retient un bit ; mille milliards de bascules, regroupées et ordonnées, forment la mémoire vive d’un ordinateur (voir la mémoire vive). Le calcul vient donc des circuits combinatoires, la mémoire des circuits séquentiels, et un processeur est un savant mélange des deux, rythmé par une horloge.
8.4Comment on conçoit aujourd’hui un circuit
Personne ne dessine plus à la main les milliards de portes d’un processeur. Les concepteurs écrivent la description du circuit dans un langage spécialisé (VHDL ou Verilog, des langages de description matérielle), qui ressemble à un langage de programmation mais décrit des fils et des portes. Un logiciel de synthèse traduit cette description en un réseau de portes, applique les lois de simplification, puis un autre logiciel place et relie les transistors sur la puce. Pour s’exercer, on utilise aussi des circuits reprogrammables (les FPGA, des puces dont les connexions internes se configurent), qui permettent d’essayer un circuit sans le faire fabriquer. Les lois de Boole sont toujours là, mais elles s’exécutent dans le logiciel.