Algèbre de Boole

oerge Boole (1815-1864), mathématicien autodidacte anglais, a développé une algèbre permettant de manipuler les propositions logiques au moyen d’équations mathématiques où les énoncés VRAI et FAUX sont représentés par les valeurs 1 et 0, tandis que les opérateurs ET et OU deviennent des opérateurs algébriques de multiplication et d’addition. Le présent chapitre est consacré à cette algèbre, présentant dans un premier temps les postulats, les axiomes et les théorèmes qui en découlent. Une partie du chapitre est également consacrée à la manipulation de cette algèbre logique, suivie d’une illustration des applications possibles pour les besoins des circuits logiques. Pour ce faire, une introduction des fondements des portes logiques est présentée.

2.1   Notions théoriques

Dans cette section, nous allons aborder les notions théoriques de base de l’algèbre de Boole. Nous commençons par les axiomes et les postulats de l’algèbre de Boole, puis nous présenterons quelques théorèmes usuels et les démonstrations qui leur sont associées. Nous montrerons ensuite comment ces démonstrations peuvent être exprimées au moyen de tables de vérité.

2.1.1  Axiomes et postulats

Une algèbre de Boole est constituée de :

1. un ensemble E,

2. deux éléments particuliers de E : 0 et 1 (correspondant respectivement à FAUX et VRAI),

3. deux opérations binaires sur E : + et · (correspondant respectivement au OU et ET logiques),

4. une opération unaire sur E : ¯  (correspondant à la négation logique).

On acceptera les postulats suivant :

Ces postulats correspondent, à toute fin utile, aux définitions des opérations logiques sur les éléments 0 et 1 de E. On pourra noter que dans le cas des opérations binaires, ( · ) et ( + ), ces postulats correspondent aux résultats de l’arithmétique usuelle, sauf dans le cas du postulat (5) où 1+1=1.

De ces postulats découlent les axiomes suivants. Soient a, b et c des éléments de E :

Commutativité	a+b = b+a	a·b = b·a
Associativité	(a+b)+c = a+(b+c)	(a·b) ·c = a·(b·c)
Distributivité	a·(b+c) = a·b+a·c	a+(b·c) = (a+b) ·(a+c)
Élément neutre	a+0 = a	a·1 = a
Complémentation	a+ = 1	a· = 0

2.1.2  Principe de dualité

Chaque axiome et chaque postulat possède un équivalent dual, où les éléments 0 sont remplacés par des 1, les 1 par des 0, les ( · ) par des ( + ) et vice et versa. Aussi, tout théorème de l’algèbre de Boole a son équivalent dual. Le théorème dual est formulé à partir du théorème de base en remplaçant les éléments 0 par des 1 (respectivement, les 1 par des 0) et les ( · ) par des ( + ) (respectivement, les ( + ) par des ( · )). Par exemple, considérons le théorème suivant :

            Soit a élément de E, alors a+a = a.

La preuve de ce théorème va comme suit :

a+a = 1ּa+1ּa	d’après l’axiome de l’élément neutre
a+a = aּ(1+1)	d’après l’axiome de distributivité
a+a = aּ1	d’après le postulat (5)
a+a = a	d’après l’axiome de l’élément neutre ; CQFD

Aussi, on peut immédiatement déduire de ce théorème son dual, ce dernier s’exprimant comme suit :

            Soit a élément de E, alors aּa = a

Il a suffit simplement de changer l’opérateur (+) par l’opérateur (∙). Bien sûr, il est possible de démontrer ce second théorème de nouveau, mais le fait d’avoir prouvé le premier suffit pour accepter le second en se référant au principe de dualité. La preuve de ce second théorème montre d’ailleurs la symétrie avec la démonstration précédente, le principe de dualité s’appliquant ici à chaque ligne :

aּa = (0+a)ּ(0+a)	d’après l’axiome de l’élément neutre
aּa = a+(0ּ0)	d’après l’axiome de distributivité
aּa = a+0	d’après le postulat (1)
aּa = a	d’après l’axiome de l’élément neutre ; CQFD

Soulignons, pour les besoins de clarté, que l’inversion elle n’a pas à être inversée, et ne doit surtout pas l’être. Par exemple, considérons le théorème suivant :

            Soient a et b des éléments de E, alors a+ּb = a+b

On en déduit par le principe de dualité le théorème suivant :

            Soient a et b des éléments de E, alors aּ(+b ) = aּb

Comme on peut le constater, l’opération d’inversion a été conservée alors que les opérations binaires ont été interchangées.

2.1.3  Théorèmes de base

Nous allons considérer maintenant quelques-uns des théorèmes que nous aurons à utiliser abondamment pour nos besoins particuliers. Le cas échéant, les théorèmes sont présentés par paire suivant le principe de dualité. Soient a et b des éléments de E, alors :

	Forme 1	Forme 2	Nom (si existe)
1	= a	—	Involution
2	a+a = a	a·a = a	Idempotence
3	a+1 = 1	a·0 = 0	Élément absorbant
4	a+a·b = a	a· (a+b) = a	Absorption
5	= ּ	= +	de Morgan
6	a+ּb = a+b	aּ(+b ) = aּb	—

Pour certains de ces théorèmes[1], nous allons donner ici la démonstration d’une des deux formes, l’autre pouvant être déduite par le principe de dualité. Considérons à cet effet les théorèmes (3), (4) et (6) :

Théorème (3) :

Soit a élément de E, alors a+1=1

Preuve :

a+1 = a+(a+)	d’après l’axiome de complémentation
a+1 = (a+a)+	d’après l’axiome de l’associativité
a+1 = a+	d’après le théorème (2)
a+1=1	d’après l’axiome de complémentation ; CQFD

——————————

Pour le théorème (4), nous allons considérer la seconde forme :

 Soient a et b éléments de E, alors aּ(a+b)=a

Preuve :

aּ(a+b) = (a+0)ּ(a+b)	d’après l’axiome de l’élément neutre
aּ(a+b) =  a+(0ּb)	d’après l’axiome de la distributivité
aּ(a+b) = a+0	d’après le théorème (3)
aּ(a+b) = a	d’après l’axiome de l’élément neutre ; CQFD

Soulignons que cette démonstration peut sembler contre intuitive à cause de la deuxième forme de l’axiome de la distributivité. Il est fortement suggéré au lecteur de reprendre cette démonstration pour la première forme du théorème (4) afin de mieux saisir l’artifice du passage de la première à la seconde ligne de la démonstration.

——————————

Pour le théorème (6), nous allons considérer la seconde forme afin de confronter encore une fois le lecteur aux propriétés quelque peu contre-intuitives de l’algèbre de Boole :

 Soient a et b éléments de E, alors aּ(+b )=aּb

Preuve :

aּ(+b) = (a+0)ּ(+b )	d’après l’axiome de l’élément neutre
aּ(+b) = (a+bּ)ּ(+b )	d’après l’axiome de la complémentation
aּ(+b) = ( a+b )ּ( a+)ּ(+b )	d’après l’axiome de la distributivité
aּ(+b) = ( a+b )ּ( a+b )ּ(a+)ּ (+b)	d’après le théorème (2)
aּ(+b) = ( a+b )ּ( a+)ּ( a+b )ּ(+b)	d’après l’axiome de la commutativité
aּ(+b) = ( a+ bּ)( aּ+b )	d’après l’axiome de la distributivité (2 fois)
aּ(+b) = ( a+ 0 )( 0+b )	d’après l’axiome de la complémentation (2 fois)
aּ(+b) = aּb	d’après l’axiome de l’élément neutre (2 fois); CQFD

Cette démonstration peut sembler plus difficile que les précédentes. Il est peut-être bon de noter que nombre de lignes pourraient être économisées si on s’épargnait l’écriture explicite d’axiome dirons-nous plus évidents,  tels que la commutativité et la complémentation.

Une fois encore, il est fortement suggéré au lecteur de reprendre cette démonstration pour la première forme du théorème (6) afin de mieux le maîtriser.

2.1.4  Considérations sur la notation

Dans ces notes, la notation algébrique sera parfois abrégée pour en alléger l’écriture. Les variables sont le plus souvent représentées par des lettres de l’alphabet (ex. a, b, c, x, y, etc…), aussi le symbole de multiplication booléenne (ּ) sera souvent omis. Ainsi, on écrira ab plutôt que aּb.

De plus, la multiplication aura préséance sur l’addition, ainsi a+bc signifiera pour nous (a)+( bּc ) et non pas  ( a + b )ּ( c ). Aussi, des parenthèses seront introduites pour éviter l’ambiguïté le cas échéant, comme nous l’avons fait précédemment sans l’énoncer formellement.

Concernant les parenthèses, il sera également fréquent d’omettre le symbole de multiplication booléenne (ּ) pour exprimer la conjonction (ET) de deux expressions booléennes délimitées par des parenthèses. Par exemple, on écrira ( a + b )( c + d ) plutôt que ( a + b )ּ( c + d ).

De plus, lorsque nous ferons des démonstrations, il n’est pas rare que nous fassions l’économie d’une référence explicite aux noms des axiomes et des théorèmes qui auront à intervenir. Ceci ne doit cependant pas nous épargner la rigueur du raisonnement : ainsi, il est une pratique fallacieuse de démontrer un théorème en faisant usage de son dual quand ce dernier a été introduit sans preuve[2] !

Finalement, peut-être est-il bon de noter que ces règles de notation sont généralement courantes en l’algèbre et en arithmétique, et ne devraient poser aucune difficulté d’assimilation au lecteur déjà familier avec la manipulation d’expressions mathématiques.

2.1.5  Décomposition de Shannon

Lorsque Shannon introduisit l’algèbre en vue d’une utilisation dans le cadre des circuits à relais, il ajouta une notion importante, connue aujourd’hui sous le nom de la décomposition de Shannon. La décomposition de Shannon est très utile pour la simplification des fonctions logiques, et elle nous servira pour mieux comprendre le fonctionnement de certains circuits usuels vus plus loin dans ce cours. De plus, elle permet de poser des démonstrations élégantes pour des théorèmes récalcitrants, comme ce sera exposé ici.

La décomposition de Shannon s’énonce comme suit :

Soient f  une fonction logique[3] de paramètres x₁, x₂, … x_n, alors :

f (x₁, x₂, …, x_n) =  f (0, x₂, …, x_n)+ x₁ f (1, x₂, …, x_n)

Preuve :

            Si x₁ = 0, le côté gauche de l’égalité vaut f (0, x₂, …, x_n), alors que le côté droit vaut :

f (0, x₂, …, x_n)+ x₁ f (1, x₂, …, x_n) = 1ּf (0, x₂, …, x_n)+ 0 ּf (1, x₂, …, x_n)

f (0, x₂, …, x_n)+ x₁ f (1, x₂, …, x_n) = f (0, x₂, …, x_n)

            Si x₁ = 1, le côté gauche de l’égalité vaut f (1, x₂, …, x_n), alors que le côté droit vaut :

f (0, x₂, …, x_n)+ x₁ f (1, x₂, …, x_n) = 0ּf (0, x₂, …, x_n)+ 1 ּf (1, x₂, …, x_n)

f (0, x₂, …, x_n)+ x₁ f (1, x₂, …, x_n) = f (1, x₂, …, x_n)

Dans les deux cas, les deux côtés de l’égalité prennent la même valeur. Aussi l’égalité est prouvée[4]. Notons ici que la variable « x₁ » peut être remplacée par n’importe quelle autres variable parmi les n-1 variables restantes. La décomposition peut également être appliquée récursivement sur l’ensemble des variables. De plus, en appliquant le principe de dualité, on peut trouver que, pour toute fonction logique f de paramètres
x₁, x₂, … x_n, il est possible d’écrire :

f (x₁, x₂, …, x_n) = ( + f (1, x₂, …, x_n) )(  x₁ + f (0, x₂, …, x_n) )

La preuve de cette assertion est laissée en exercice au lecteur.

Pour conclure, nous allons présenter la preuve du théorème (5) en recourant à la décomposition  de Shannon :

Soient a et b des éléments de E, alors = ּ

Preuve :

            Soit f (a, b) = , suivant la décomposition de Shannon, on note :

            f (a, b) = ּf (0, b)+ aּ f (1, b)

                       = ּf (0, b)+ aּ f (1, b)

Or,

f (0, b) =  =

f (1, b) = = = 0

Il en ressort que

f (a, b) = ּ+aּ0 = ; CQFD

2.1.6  Table de vérité

La table de vérité d’une fonction logique est un tableau énumérant les valeurs logiques d’une fonction pour les différentes combinaisons des valeurs de ses variables indépendantes (en circuits logiques, on parlera de correspondance entre la sortie et les entrées). On place donc les variables de la fonction dans les colonnes de gauche en les faisant varier de façon à couvrir l'ensemble des possibilités, la colonne la plus à droite donne les valeurs prises par la fonction pour les différentes combinaisons des valeurs d’entrée.

Pour avoir une meilleure idée, considérons les exemples suivants :

Soient A et B des variables logiques, et F₁, F₂, F₃ et F₄ des fonctions logiques faisant intervenir ces variables :

F1 = A+B	F2 =
F3 = +	F4 =

Les tables de vérité associées à ces fonctions sont :

A B F1 0 0 0 0 1 1 1 0 1 1 1 1	A B F2 0 0 1 0 1 1 1 0 1 1 1 0
A B F3 0 0 1 0 1 1 1 0 1 1 1 0	A F4 0 0 1 1

La table de vérité de F₄ suggère que :

= A.

Les tables de vérité constituent un élément important dans la manipulation des fonctions logiques. Ainsi, on dira que deux fonctions sont équivalentes si et seulement si elles possèdent la même table de vérité. Ainsi, utilisant la table de la fonction logique F₄, nous avons démontré le théorème (1), dit théorème de l’involution. De la même façon, les tables de vérité des fonctions F₂ et F₃ nous ont permis de démontrer la première forme du théorème de de Morgan.

Une table de vérité peut bien sûr comporter plus que deux variables. Par exemple, soient A, B, C et D quatre variables logiques, et considérons les fonctions logiques suivantes :

F5 = A·B+C+	F6 = A·B+ C·D
F7 = A(A+B)+ C·D	F8 = A·B+A+C·D

Les tables de vérité associées à ces fonctions sont :

A B C D F5 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 1 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1	A B C D F6 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1
A B C D F7 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1	A B C D F8 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1

2.1.7  Table de vérité des opérateurs logiques

Comme nous avons pu le voir dans la section 1 du présent chapitre, l’algèbre de Boole admet :

1. deux opérations binaires : + et · (correspondant respectivement au OU et ET logiques),

2.        une opération unaire : ¯  (correspondant à la négation logique).

Les tables de vérité de ces opérateurs sont les suivantes (où A et  B sont des variables logiques) :

A B F = A·B 0 0 0 0 1 0 1 0 0 1 1 1	A B F = A+B 0 0 0 0 1 1 1 0 1 1 1 1	A F= 0 1 1 0
Opérateur ET logique	Opérateur OU logique	Opérateur NON

Il est intéressant de relever que ces tables de vérité correspondent aux huit postulats formulés précédemment. Une façon simple de se rappeler ces tables consiste à les formuler dans le langage usuel. Le ET implique la validité de tous les impliquants, le OU la validité d’au moins un de ces derniers. Notons, sans le démontrer toutefois, que toute fonction logique peut s’écrire uniquement avec ces trois opérateurs.

2.1.8  Diagrammes de Venn et cercles d’Euler

La représentation des ensembles utilisée dans le premier chapitre est héritée de Venn, un mathématicien britannique. Cette représentation peut être utilisée pour illustrer les trois opérateurs de l’algèbre de Boole, on l’appelle aussi représentation par les cercles d’Euler.

La complémentarité (ou négation) :

L’intersection (ou la conjonction) :

L’union (ou la disjonction) :

Il est possible d’inclure jusqu’à six ensembles (six variables) et d’exprimer des énoncés logiques relativement complexes. Par exemple, la fonction est exprimée ainsi :

2.2  Notions de circuits logiques

Le lien établi entre l’algèbre de Boole et les circuits logiques date du début du XX^e siècle. Ce fut une véritable révolution dont nous connaissons largement les conséquences aujourd’hui. Il s’agissait initialement d’une application aux circuits à relais (sorte d’interrupteurs).

Si des relais obéissaient à la même commande (variable), alors une fonction logique pouvait exprimer son fonctionnement général :

2.2.1  Portes logiques

Avec l’évolution de la technologie, on inventa des composants plus versatiles que les circuits à relais, qui donnèrent naissance aux circuits logiques. On définit alors un ensemble de composants appelés portes logiques. Chaque porte correspond à une fonction logique précise, à laquelle on associe un symbole. Les portes élémentaires sont[5] :

Opérateur logique	Nom français	Nom anglais	Symbole	Table de vérité
A∙B	ET	AND		A B F 0 0 0 0 1 0 1 0 0 1 1 1
A+B	OU	OR		A B F A B F 0 0 0 0 1 1 1 0 1 1 1 1
	NON ET	NAND		A B F 0 0 1 0 1 1 1 0 1 1 1 0
	NON OU	NOR		A B F 0 0 1 0 1 0 1 0 0 1 1 0
AB	OU exclusif	XOR		A B F 0 0 0 0 1 1 1 0 1 1 1 0
= A B	NON OU exclusif	XNOR		A B F 0 0 1 0 1 0 1 0 0 1 1 1
	NON (inverseur)	NOT (inverter)		A F 0 1 1 0

Nous avons introduit le nom anglais de ces portes car il est fréquent de les rencontrer dans la littérature. De plus, nous utiliserons parfois le nom anglais d’une porte pour la désigner, par exemple dans le cas de la porte XOR.

Ces portes logiques sont les éléments de base à l’aide desquels nous pouvons exprimer toute fonction logique. Une question légitime qui se pose alors est : « Pourquoi disposons nous d’autant de portes logiques, puisque toute fonction logique peut être exprimée à l’aide des opérateurs ET, OU et NON ? »

Il y a deux raisons majeures à cela. La première est d’ordre technologique, tenant compte du fait que la réalisation d’une porte ET à l’aide de transistors présuppose l’existence d’une porte NON-ET, qui à son tour est inversée. La réciproque est tout aussi vraie pour la porte OU et la porte NON-OU. De la même façon, les portes XOR et XNOR sont très utiles et leur réalisation matérielle est plus simples que l’équivalent utilisant des portes ET, OU et NON. Cette réalité va nous amener à la notion de coût d’un circuit qui sera couverte au chapitre suivant. La seconde raison tient compte du fait que toute fonction logique peut être exprimée au moyen de NON-ET uniquement (respectivement, à l’aide de NON-OU uniquement). Cette question sera également abordée au chapitre suivant.

Le passage d’une fonction logique à un circuit logique induit certaines modifications aux notions vues précédemment. Les variables d’une fonction logique deviennent les entrées du circuit, ce circuit donnant en sortie la valeur de la fonction logique suivant la valeur des entrées. On peut ainsi connecter des portes logiques les unes aux autres pour réaliser une fonction logique. À l’inverse, trouver la fonction logique réalisée par un circuit nous permettra de le manipuler en vue de simplifications éventuelles.

2.2.3     Inversion des entrées

Il n’est pas rare de rencontrer les symboles suivant :

Il ne s’agit pas là de nouvelles portes mais des portes précédentes où l’une ou les deux entrées ont été inversées (indiqué par la présence d’un cercle d’inversion). Ainsi, nous aurons la correspondance suivante :

A	+	B
		A

2.2.4     Portes XOR et XNOR

Outre les portes NON-ET et NON-OU, nous avons introduit les portes XOR et XNOR. La formulation logique de la première correspond à un OU où les deux entrées ne peuvent être vraie en même temps, alors que celle de la seconde est une équivalence logique, l’inverse du XOR.

La fonction XOR, symbolisée par , est donnée par l’expression :

AB = B+A

      = (A+B)( +)

La fonction XNOR, symbolisée par , est donnée par l’expression :

AB = +AB

                 = (+B)(A+)

La preuve de l’égalité des deux expressions est laissée en exercice.

2.2.5     Portes à plusieurs entrées

Les portes logiques, à l’exception de l’inverseur, peuvent avoir plus que deux entrées. Il importe alors de bien comprendre comment s’exprime la fonction logique associée à ces portes logiques, surtout si la sortie est inversée — exercice qui n’est pas toujours intuitif.

Dans le cas simple de portes non inversées (à trois entrées et plus), on peut recourir à l’axiome de l’associativité. Ainsi, nous aurons

ABC=(AB)C=A(BC)	A+B+C=(A+B)+C=A+(B+C)

Le cas d’une porte XOR à trois entrées et plus obéit fort heureusement à un principe d’associativité similaire (la preuve de cette assertion est laissée en exercice) :

(AB)C=A(BC)=ABC

Dans le cas des portes inversées à plusieurs entrées, on maintient la cohérence de l’équivalence entre les portes logiques et l’algèbre de Boole en considérant que l’inversion est postérieure à l’expression logique qui la précède. Aussi aurons-nous :

	≡
	≡

2.2.6     Synthèse de circuit logique (notions)

Comme énoncé plus haut, le passage d’une fonction logique à un circuit logique induit certaines modifications aux notions de l’algèbre de Boole. Les variables d’une fonction logique deviennent les entrées du circuit, ce circuit donnant en sortie la valeur de la fonction logique suivant la valeur des entrées. Nous avons pu constater la chose lorsque nous considérions les portes logiques individuellement. Ainsi, il devient possible de connecter des portes logiques les unes aux autres pour réaliser une fonction logique; et de manière symétrique, trouver la fonction logique réalisée par un circuit nous permet de le manipuler en vue de simplifications éventuelles.

Afin d’illustrer la chose, soit la fonction logique F, impliquant les variables logiques A, B et C, telle que F soit définie par l’équation :

F = A·B+B·C +

Le circuit logique correspondant à cette fonction est le suivant :

Comme on peut le constater, cette fonction est réalisée en connectant les portes les unes aux autres. Lorsque les fils se croisent, nous ajoutons un petit cercle plein noir () pour indiquer une connexion. En l’absence de ce point noir, cette connexion est inexistante. Généralement, nous mettons l’emphase de cette absence de connexion en ajoutant une légère surélévation à l’un des deux fils impliqués (). Ce circuit peut faire intervenir une porte à trois entrées et devenir le suivant :

Ce circuit peut néanmoins être simplifié pour donner le circuit suivant :

La preuve de cette équivalence est laissée en exercice. Dans le même ordre d’idées, il est demandé de démontrer que ce circuit est différent de ce dernier :