UE Electronique

Electronique numérique

ALGEBRE DE BOOLE

ALGEBRE DE BOOLE ....................................................................................................................................... 1

1. LES OBJECTIFS D’APPRENTISSAGE .................................................................................................. 2
2. LES CONCEPTS ......................................................................................................................................... 3
2.1. INTRODUCTION ..................................................................................................................................... 3
2.2. PROPRIETES DE L’ALGEBRE DE BOOLE.................................................................................................. 3
2.2.1. Définitions ....................................................................................................................................... 3
2.2.2. Table de vérité d’une fonction logique ............................................................................................ 3
2.2.3. Les fonctions logiques élémentaires ................................................................................................ 3
2.3. REPRESENTATION DES FONCTIONS LOGIQUES ....................................................................................... 9
2.3.1. Formes algébriques disjonctives, conjonctives, canoniques ........................................................... 9
2.3.2. Représentations de référence d’une fonction logique ................................................................... 10
2.3.3. Critères de choix d’une représentation ......................................................................................... 10
3. EXERCICES D’APPLICATION ............................................................................................................. 12
3.1. TABLE DE VERITE ET FORMES CANONIQUES ........................................................................................ 12
3.2. THEOREME DE DE MORGAN ............................................................................................................... 12
3.3. FORME CANONIQUE (1) ....................................................................................................................... 12
3.4. FORME CANONIQUE (2) ....................................................................................................................... 12

4. POUR ALLER PLUS LOIN ..................................................................................................................... 13

4.1.1. Opérateurs complets ..................................................................................................................... 13

1
 UE Electronique
Electronique numérique
Algèbre de Boole

1. LES OBJECTIFS D’APPRENTISSAGE

OA1 : Représenter une fonction logique décrite par une proposition logique sous la
forme d’une table de vérité, ou sous ses formes canoniques.
OA2 : Appliquer des propriétés et des théorèmes tirés de l’algèbre de Boole.
OA3 : Choisir la forme conjonctive ou disjonctive d’une fonction logique pour
minimiser les ressources matérielles nécessaires à l’implantation matérielle de la
fonction.

Enjeu : Notion de complexité dans un processeur matériel de traitement de

l’information.

2
 2. LES CONCEPTS

2.1. INTRODUCTION
Le fonctionnement des systèmes numériques repose sur la manipulation de
variables et fonctions dont les valeurs sont représentées par des grandeurs
physiques dites binaires car ne pouvant prendre que deux valeurs (généralement
notées 0 et 1). La structure mathématique permettant de formaliser les opérations de
manipulation de ces grandeurs binaires est dite algèbre de commutation ou plus
communément algèbre de Boole. Nous nous intéressons dans ce chapitre aux
bases et aux propriétés fondamentales de l’algèbre de Boole indispensables à la
compréhension du fonctionnement des systèmes numériques.

2.2. PROPRIETES DE L’ALGEBRE DE BOOLE

2.2.1. Définitions
Dans l’algèbre de commutation, une variable ne peut prendre que 0 ou 1 comme
valeur possible. Une telle variable est dite variable logique, variable binaire, ou
variable booléenne. De même, une fonction de n variables logiques ne peut
prendre comme valeur que 0 ou 1. Elle est dite fonction logique, fonction binaire,
ou fonction booléenne.

2.2.2. Table de vérité d’une fonction logique

C’est une table donnant l’état logique de la fonction pour chacune des combinaisons
des états de ses variables. Une fonction de n variables est représentée par une table
de vérité à n+1 colonnes et au plus 2n lignes. Le tableau 2.1 donne la forme générale
d’une fonction de deux variables logiques.
A B F(A,B)
0 0 F(0,0)
0 1 F(0,1)
1 0 F(1,0)
1 1 F(1,1)
tableau 2.1 : forme générale de la table de vérité d’une fonction
de deux variables logiques

2.2.3. Les fonctions logiques élémentaires

Trois fonctions suffisent pour définir une algèbre de Boole : la complémentation, le
produit logique, et l’addition logique.

[Link]. La fonction de complémentation ou fonction NON

Le complément de la variable A se note A (lire « A barre » ou « non A »). A vaut 1
(respectivement 0) si et seulement si A vaut 0 (respectivement 1). On parle encore
de fonction d’inversion logique. Le tableau 2.2 donne la table de vérité de la
fonction de complémentation. Les symboles usuellement utilisés pour représenter
graphiquement l’opérateur correspondant, appelé inverseur, sont ceux de la
figure 2.1.

3
 1
A A
0 1 (a) (b)
1 0
figure 2.1 : symboles logiques d’un inverseur
tableau 2.2 : table de vérité de la
(a) notation usuelle (ancienne notation US)
fonction NON
(b) notation normalisée IEEE (ancienne notation européenne)

[Link]. La fonction produit logique ou fonction ET

Le produit logique de 2 variables se note A.B, AB, ou bien encore AB (lire « A et
B »). A.B vaut 1 si et seulement si A et B valent 1. Le tableau 2.3 donne la table de
vérité de la fonction ET, et la figure 2.2 les symboles logiques de l’opérateur associé.
A A
A B A.B A.B & A.B
B B
0 0 0
0 1 0 (a) (b)
1 0 0
1 1 1 figure 2.2 : symboles logiques de l’opérateur
ET.
tableau 2.3 : table de vérité de la fonction ET
(a) notation usuelle
(b) notation normalisée IEEE

[Link]. La fonction addition logique ou fonction OU

L’addition logique de 2 variables se note A+B ou AB (lire « A ou B »). A+B vaut 0 si
et seulement si A et B valent 0. Le tableau 2.4 donne la table de vérité de la fonction
OU, et la figure 2.3 les symboles logiques de l’opérateur associé.

A B A+B
0 0 0
0 1 1
1 0 1
1 1 1
tableau 2.4 : table de vérité de la fonction OU

(a) (b)

figure 2.3 : symboles logiques de l’opérateur OU.

(a) notation usuelle
(b) notation normalisée IEEE

4
 [Link]. Propriétés des fonctions NON, ET, et OU
 Commutativité des fonctions ET et OU :

AB  BA
A B  B A

 Associativité des fonctions ET et OU :

A( BC )  ( AB )C  ABC
A  ( B  C )  ( A  B)  C  A  B  C

 Eléments neutres pour les fonctions ET et OU

A.1  1. A  A
A0 0 A A

 Eléments absorbants pour les fonctions ET et OU

A.0  0. A  0
A  1  1 A  1

 Propriété d’idempotence des fonctions ET et OU

A. A  A
A A A

 Propriétés de l’inversion logique

AA
A. A  0
A  A 1

 Distributivité de ET par rapport à OU

A( B  C )  AB  AC
( A  B ) C  AC  BC

 Distributivité de OU par rapport à ET

A  BC  ( A  B )( A  C )
AB  C  ( A  C )( B  C )

 Autres relations utiles se déduisant des précédentes (relations de

simplification)
A  AB  A
A( A  B )  A
A  AB  A  B
A( A  B )  AB

5
  Théorème de De Morgan

A  B  A. B
A. B  A  B

Ce théorème se généralise à un nombre quelconque de variables :

 Xi   Xi
i i

 Xi   Xi
i i
N. B. On notera que l’analogie entre l’addition logique (resp. produit logique) et
l’addition (resp. multiplication) de l’arithmétique classique se limite à un nombre
très restreint de propriétés.

[Link]. Opérateurs secondaires

Dans les circuits logiques, on utilise également des opérateurs qui sont des
combinaisons des fonctions ET, OU, et NON.

(a) La fonction NON ET ou NAND : A. B

La table de vérité de la fonction NON ET se déduit immédiatement de celle de la
fonction ET par inversion du résultat (tableau 2.5).

A B A. B
0 0 1
0 1 1
1 0 1
1 1 0
tableau 2.5 : table de vérité de la
fonction NON ET

A A
A.B & A.B
B B

(a) (b)

figure 2.4 : symboles logiques de l’opérateur NON ET.

(a) notation usuelle
(b) notation normalisée IEEE

6
 (b) La fonction NON OU ou NOR : A  B
La table de vérité de la fonction NON OU se déduit immédiatement de celle de la
fonction OU par inversion du résultat (tableau 2.6).

A B A B
0 0 1
0 1 0
1 0 0
1 1 0
tableau 2.6 : table de vérité de la fonction NON OU

(a) (b)

figure 2.5 : symboles logiques de l’opérateur NON OU, (a) notation usuelle, (b) notation
normalisée IEEE

(c) Quelques propriétés des fonctions NON ET et NON OU

Les propriétés des fonctions NON ET et NON OU se déduisent des propriétés des
fonctions élémentaires NON, ET, et OU.
AB  BA A B  B A
( AB ) C  A( BC )  ABC mais ABC  ABC
( A  B )  C  A  ( B  C )  A  B  C mais A  B  C  A  B  C
A.1  A A 1 0
A. 0  1 A0 A
A. A  A A A A
A. A  1 A  A0

(d) La fonction OU exclusif (abrégé OUEX ou XOR) : A  B  A. B  A. B

A B AB
0 0 0
0 1 1
1 0 1
1 1 0
tableau 2.7 : table de vérité de la fonction OU exclusif

7
 =1

(a) (b)

figure 2.6 : symboles logiques de l’opérateur OU exclusif.

(a) notation usuelle
(b) notation normalisée IEEE

 Propriétés de la fonction OU exclusif

A  B  B  A (commutativité)
A  ( B  C )  ( A  B )  C  A  B  C (associativité)
A0  A A 1 A
A A  0 A A 1
A B  A  B
 Utilisations courantes de la fonction OU exclusif

 Détection de deux éléments binaires différents,

A B 1  A  B
 Détection d’un nombre de variables impair,

A  B  C...  1   A, B, C,... contient un nombre impair de 1

 Somme modulo 2 de deux éléments binaires.

(e) La fonction ET inclusif (abrégé XNOR) : A B  A  B  A. B  A . B

A B A B
0 0 1
0 1 0
1 0 0
1 1 1
tableau 2.8 : table de vérité de la fonction ET inclusif

A B =1 A B

(a) (b)

figure 2.7 : symboles logiques de l’opérateur ET inclusif.

(a) notation usuelle
(b) notation normalisée IEEE

8
  Propriétés de la fonction ET inclusif

Les propriétés du ET inclusif se déduisent aisément des propriétés de la fonction OU

exclusif en remarquant que
A B  A B  A B  A B
 Utilisations courantes de l’opérateur ET inclusif

 Détection de deux éléments binaires égaux,

A B 1  A  B
 Détection d’un nombre de variables pair,

A  B  C...  1   A, B, C,... contient un nombre pair de 1

2.3. REPRESENTATION DES FONCTIONS LOGIQUES

2.3.1. Formes algébriques disjonctives, conjonctives, canoniques
Considérons la table de vérité de la fonction booléenne F de 3 variables A, B, et C,
définie par le tableau 2.9.
A B C numéro de la F(A,B,C) F( A, B, C )
combinaison
0 0 0 0 1 0
0 0 1 1 1 0
0 1 0 2 0 1
0 1 1 3 0 1
1 0 0 4 1 0
1 0 1 5 1 0
1 1 0 6 1 0
1 1 1 7 0 1

tableau 2.9 : table de vérité d’une fonction booléenne F de 3 variables

On peut extraire une expression de F en exprimant les combinaisons des variables

A, B, et C pour lesquelles F est égale à 1 : F vaut 1 pour les combinaisons 0, 1, 4, 5,
et 6, c’est-à-dire si A B C  1, A B C  1 , AB C  1 , AB C  1, ou ABC  1. La fonction F
peut donc s’écrire sous la forme :
F( A, B, C)  A B C  A B C  AB C  AB C  ABC
Dans cet exemple, si A=B=C=0, alors F=1 car A B C  1. Toutes les autres
combinaisons de variables d’entrée sont égales à 0.
L’expression obtenue est une somme logique de produits logiques, il s’agit d’une
forme algébrique disjonctive. Les produits logiques font intervenir toutes les
variables, sous leur forme directe ou complémentée. Ces produits élémentaires sont
appelés mintermes. Pour n variables logiques, il existe 2n mintermes différents,
chaque minterme étant égal à 1 pour une seule combinaison des n variables. La
représentation d’une fonction sous la forme d’une somme de mintermes est dite
forme canonique disjonctive ou première forme canonique.

9
On peut extraire une seconde expression de F en exprimant les combinaisons des
variables A, B, et C pour lesquelles F est égale à 0. F vaut 0 pour les combinaisons
2, 3, et 7, ce qui peut encore s’écrire :
F( A, B, C)  ( A  B  C).( A  B  C ).( A  B  C )
En effet, si 𝐵 = 1 et 𝐴 = 𝐶 = 0 (ce qui correspond à la combinaison 2), alors
𝐴 + 𝐵̅ + 𝐶 = 0 et donc 𝐹 = 0. Idem pour les combinaisons 3 et 7.
On peut également commencer par exprimer 𝐹̅ = 𝐴̅. 𝐵. 𝐶̅ + 𝐴̅. 𝐵. 𝐶 + 𝐴. 𝐵. 𝐶. En effet,
𝐹 = 0 si 𝐵 = 1 et 𝐴 = 𝐶 = 0 . Puis appliquer le théorème de De Morgan sur cette
expression pour obtenir 𝐹.
Comme pour la forme conjonctive, toutes les autres combinaisons sont, dans ce cas,
égales à un. Cette nouvelle expression a une forme duale de la précédente. C’est un
produit logique de sommes logiques, il s’agit d’une forme algébrique conjonctive.
Les sommes logiques composant le produit font intervenir toutes les variables, sous
leur forme directe ou complémentée. Elles sont appelées maxtermes. Pour n
variables logiques, il existe 2n maxtermes différents, chaque maxterme étant égal à 0
pour une seule combinaison des n variables. La représentation d’une fonction sous
la forme d’un produit de maxtermes est dite forme canonique conjonctive ou
seconde forme canonique.

2.3.2. Représentations de référence d’une fonction logique

Parmi les différentes représentations des fonctions logiques étudiées dans ce
chapitre, trois d’entre elles peuvent être considérées comme des représentations de
référence en raison de leur unicité :
 la table de vérité,
 les deux formes canoniques.
En effet, deux fonctions logiques sont égales si et seulement si leurs tables de vérité
ou leurs formes canoniques sont identiques.

2.3.3. Critères de choix d’une représentation

L’un des deux types de représentation, forme disjonctive ou conjonctive, peut être
préférable à l’autre si des contraintes sont imposées sur la réalisation matérielle des
fonctions. En particulier, dans le cas de l’utilisation de circuits logiques réalisant les
fonctions logiques élémentaires, le type de circuits disponibles peut favoriser une des
deux formes.
Ainsi, la forme disjonctive est bien adaptée à une réalisation à base d’opérateurs
NON ET. En effet, soit F une fonction de 4 variables écrite sous la forme disjonctive
suivante (non canonique dans le cas traité, puisque les produits ne sont pas des
mintermes) :
F( A, B, C, D)  A. B  CD
Pour réaliser cette fonction à l’aide d’opérateurs NON ET et d’inverseurs, il faut dans
un premier temps transformer la fonction pour l’écrire sous la forme d’une
combinaison de fonctions élementaires NON ET et d’inversion (application du
théorème de De Morgan):
F( A, B, C, D)  A. B  CD  A. B  CD  A. B. CD

10
Il reste ensuite à assembler le nombre adéquat d’opérateurs élémentaires pour
réaliser F. La figure 2.8 montre un schéma de réalisation (ou logigramme) de F
utilisant 3 opérateurs NON ET et 1 inverseur. Si l’opérateur d’inversion n’est pas
disponible, il peut lui-même être réalisé à l’aide d’un opérateur NON ET, cf. §4.1.1.
A
B
F(A,B,C,D)
C

D
figure 2.8: logigramme de la fonction F à base d’opérateurs NON ET et d’un inverseur

De même, la forme conjonctive est bien adaptée à une réalisation à base

d’opérateurs NON OU. En effet, soit une fonction G de 4 variables écrite sous une
forme conjonctive :
G( A, B, C, D)  ( A  B ).( C  D)  ( A  B ).( C  D)  A  B  C  D
La fonction G peut être réalisée à l’aide de 3 opérateurs NON OU et 2 inverseurs
(figure 2.9).

B G( A,B,C,D)
C
D
figure 2.9 : logigramme de la fonction G à base d’opérateurs NON OU et d’inverseurs

Lorsqu’aucune contrainte extérieure n’impose l’une des représentations, la forme

disjonctive est traditionnellement plus utilisée que la forme conjonctive, en raison de
l’analogie de notation entre les opérations logiques et arithmétiques.
Lors de la mise en œuvre d’une fonction logique dans un circuit, deux types de
contraintes peuvent être prises en compte : optimiser la vitesse du circuit (c.-à-d.
obtenir une fréquence maximale de fonctionnement la plus grande possible) ou bien
optimiser sa complexité (c.-à-d. obtenir un encombrement sur silicium minimal).
Dans le cas où la contrainte de complexité est la plus forte, il faut utiliser le
minimum de matériel. Il est, pour cela, nécessaire de représenter la fonction à
réaliser sous une forme simplifiée, c’est-à-dire utilisant un nombre minimal
d’opérateurs. Le problème de la simplification des fonctions logiques est traité à la
séance suivante.

11
3. EXERCICES D’APPLICATION
3.1. TABLE DE VERITE ET FORMES CANONIQUES
Établir les tables de vérité des fonctions suivantes, puis les écrire sous les deux
formes canoniques :
1. F1  XY  YZ  XZ

2. F2  X  YZ  YZT

3. F3  ( X  Y )( X  Y  Z )

4. F4 (X Y Z)(X Y Z)(X Y Z )(X Y Z )(X Y Z)

3.2. THEOREME DE DE MORGAN

Complémenter les fonctions suivantes (sans simplification) :

5. F1  XY  XY  XY

6. F2  X (YZ  YZ )  XYZ  XYZ

7. F3  XY  ZT  XY  ZT

3.3. FORME CANONIQUE (1)

Écrire sous la première forme canonique les fonctions définies par les propositions
suivantes :
1. f (a, b, c)  1 si et seulement si aucune des variables A, B, C ne prend la valeur 1

2. f (a, b, c)  1 si et seulement si au plus une des variables A, B, C prend la valeur 0

3. f (a, b, c)  1 si et seulement si exactement une des variables A, B, C prend la

valeur 1

Mettre les fonctions sous la seconde forme canonique.

3.4. FORME CANONIQUE (2)

Écrire sous la seconde forme canonique la fonction définie par la proposition
suivante :
g (a, b, c)  0 si et seulement si aucune des variables A, B, C ne prend la valeur 1.
Mettre cette fonction sous la première forme canonique.

12
4. POUR ALLER PLUS LOIN
4.1.1. Opérateurs complets
Un opérateur logique est dit complet s’il permet de réaliser les trois fonctions de base
de l’algèbre de Boole et, par conséquent, toutes les fonctions logiques. Par
exemple, l’opérateur NON ET est complet. Il en est de même pour l’opérateur
NON OU.
En effet,
A  A. A
A. B  AB. AB
A  B  A  B  A . B  AA. BB
De même,
A A A
A. B  A. B  A  B  A  A  B  B
A B A B A B
En revanche, les opérateurs OU exclusif et ET inclusif, ne sont pas complets.

13