Sommaire

Sommaire i

Liste des Figures iii

1 Algèbre de Boole 1
1.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Algèbre de Boole . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 Etats logiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.3 Variables logiques . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.4 Fonctions logiques . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Opérateurs logiques élémentaires . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Opérateur logique NON . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 Opérateur logique ET . . . . . . . . . . . . . . . . . . . . . . 3
1.2.3 Opérateur logique OU . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Opérateurs logiques composés . . . . . . . . . . . . . . . . . . . . . . 5
1.3.1 Opérateur logique NON-ET . . . . . . . . . . . . . . . . . . . 5
1.3.2 Opérateur logique NON-OU . . . . . . . . . . . . . . . . . . . 6
1.3.3 Opérateur logique OU-EXCLUSIF . . . . . . . . . . . . . . . 7
1.4 Lois fondamentales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.1 Propriétés monovariables . . . . . . . . . . . . . . . . . . . . 7
1.4.2 Propriétés multivariables . . . . . . . . . . . . . . . . . . . . 8
1.4.3 Théorème de Consensus . . . . . . . . . . . . . . . . . . . . . 9
1.5 Théorème de DE MORGAN . . . . . . . . . . . . . . . . . . . . . . . 9
1.5.1 Enoncé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5.2 Application 1 du théorème . . . . . . . . . . . . . . . . . . . 9
1.5.3 Application 2 du théorème . . . . . . . . . . . . . . . . . . . 9
1.6 Représentation des fonctions logiques . . . . . . . . . . . . . . . . . . 10
1.6.1 Table de vérité (TdV) . . . . . . . . . . . . . . . . . . . . . . 10
1.6.2 Forme canonique . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.6.3 Tableau de Karnaugh . . . . . . . . . . . . . . . . . . . . . . 12
1.6.4 Logigramme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.6.5 Chronogramme . . . . . . . . . . . . . . . . . . . . . . . . . . 14

i
 Liste des Figures

1.1 Symboles et schéma électrique élémentaire de l’opérateur logique NON 3

1.2 Symboles et schéma électrique élémentaire de l’opérateur logique ET 4
1.3 Symboles et schéma électrique élémentaire de l’opérateur logique OU 5
1.4 Symboles et schéma électrique élémentaire de l’opérateur NON-ET . 6
1.5 Symboles et schéma électrique élémentaire de l’opérateur NON-OU . 6
1.6 Symboles de l’opérateur logique OU-EXCLUSIF . . . . . . . . . . . 7

iii
 Liste des tableaux

1.1 Table de vérité de l’opérateur logique NON . . . . . . . . . . . . . . 3

1.2 Table de vérité de l’opérateur logique ET . . . . . . . . . . . . . . . 3
1.3 Table de vérité de l’opérateur logique OU . . . . . . . . . . . . . . . 4
1.4 Table de vérité de l’opérateur logique NON-ET . . . . . . . . . . . . 5
1.5 Table de vérité de l’opérateur logique NON-OU . . . . . . . . . . . . 6
1.6 Table de vérité de l’opérateur logique OU-EXCLUSIF . . . . . . . . 7

v
 Chapitre 1

Algèbre de Boole

1.1 Définitions
1.1.1 Algèbre de Boole
George Boole, philosophe et mathématicien irlandais du 19ème siècle est l’auteur
d’une théorie sur l’art de construire un raisonnement logique au moyen de propo-
sitions qui ont une seule réponse OUI (VRAI) ou NON (FAUX). Il est le premier,
avec de Morgan, à essayer de fonder la logique mathématique indépendamment de
la philosophie. Pour cela, il crée une algèbre binaire n’acceptant que deux valeurs
numériques, 0 ou 1. 1 pour une proposition toujours vraie, et 0 une proposition
fausse. Il définit des lois (ET et OU) sur cette algèbre satisfaisant un certain
nombre de propriétés (distributivité, commutativité,...). L’ensemble des opérations
formelles appliquées à ces propositions forme une structure mathématique appelée
algèbre de Boole. A son époque, il s’agissait de développement purement théorique
car on ignorait l’importance qu’allait prendre cette algèbre avec l’informatique.
Les concepts de la logique booléenne ont été ensuite appliqués aux circuits
électroniques par Claude Shannon. Cette algèbre est applicable à l’étude des
systèmes possédant deux états s’excluant mutuellement. Dans la logique positive
(la plus couramment utilisée), on associe OUI à 1 et NON à 0. Dans la logique
négative, c’est l’inverse. L’algèbre booléenne binaire est à la base de la mise en oeu-
vre de tous les systèmes numériques : ordinateurs, systèmes numériques portables,
systèmes de communication numériques, etc. Elle permet entre autres de simplifier
les fonctions logiques, et donc les circuits électroniques associés.

1.1.2 Etats logiques

En électronique numérique, on ne peut produire et traiter que des signaux discrets
à deux états, appelés respectivement vrai-faux, ou haut-bas, ou mieux encore 1-0.
Nous utiliserons les symboles 1 et 0 dans la suite de ce cours.

1.1.3 Variables logiques

Une variable logique est une variable qui ne peut prendre que deux valeurs 1 ou
0. Cette variable est qualifiée de booléennes, du nom du mathématicien anglais G.
Boole qui a développé en 1854 l’algèbre correspondante. On dit aussi que chaque
variable logique est un bit, contraction de l’anglais binary digit qui signifie chiffre
binaire.

1
2 1. ALGÈBRE DE BOOLE

Exemples :
ˆ Un interrupteur peut être soit fermée (1 logique), soit ouvert (0 logique). Il
possède donc deux états possibles de fonctionnement.

ˆ Une lampe possède également deux états possibles de fonctionnement qui sont
éteinte (0 logique) ou allumée (1 logique).

ˆ Un moteur possède également deux états possibles de fonctionnement qui sont

en marche (1 logique) ou arrêté (0 logique).

ˆ Une affirmation soit elle est vraie (1 logique) ou fausse (0 logique).

ˆ Une grandeur physique peut être soit supérieure à un seuil fixé (1 logique) ou
inférieure (0 logique).
L’association des variables logiques munie d’un certain nombre d’opérateurs donne
naissance à des fonctions logiques.

1.1.4 Fonctions logiques

Une fonction logique est une fonction d’une ou de plusieurs variables logiques, com-
binées entre elles par les trois opérateurs logiques élémentaire : NON, OU et ET.
Tout circuit logique peut être décrit par des fonctions logiques et/ou une table de
vérité, et être réalisé à partir d’opérateurs logiques élémentaires ou composées.

1.2 Opérateurs logiques élémentaires

Les fonctions logiques peuvent être représentées schématiquement par des opérateurs
logiques, encore appelés portes logiques. Chaque opérateur est représenté par un
symbole et sa fonction est définie par une table de vérité.
Comme nous le verrons, une représentation simple de l’opération que réalise de
tels opérateurs est fournie par la table de vérité, laquelle est construite à partir des
valeurs 1 ou 0 que peuvent prendre les variables booléennes. Précisément, cette
table se présente sous la forme d’un tableau, dont les colonnes de gauche affichent
les valeurs des variables d’entrée, e1 , e2 , . . ., alors que la dernière colonne à droite
donne la sortie S correspondante.

1.2.1 Opérateur logique NON

L’opérateur logique NON (NOT en anglais) réalise la complémentation ou l’inversion
d’une variable:
S=x
On l’appelle aussi inverseur. Sa table de vérité, est donnée sur le tableau 1.1.
Le symbole de l’inverseur, selon la norme européenne, est représenté sur la figure
1.1a. De même, la figure 1.1b représente le symbole de l’inverseur, selon la norme
1.2. OPÉRATEURS LOGIQUES ÉLÉMENTAIRES 3

x S
0 1
1 0

Tableau 1.1: Table de vérité de l’opérateur logique NON

américain. Un petit cercle en sortie (norme américain), ou un triangle (norme

européenne), exprime la négation de la fonction réalisée.

E x S
x 1 S x S

(a) Symbole européen (b) Symbole américain R

(c) Schéma électrique

Figure 1.1: Symboles et schéma électrique élémentaire de l’opérateur logique NON

Un schéma électrique élémentaire permet de réaliser cette opération (figure 1.1c):

la lampe indique l’état de la sortie et l’interrupteur celui de l’entrée; pour la lampe,
l’état 1 correspond à l’illumination et l’état 0 à l’extinction; pour l’interrupteur,
l’état 1 correspond à la fermeture et l’état 0 à l’ouverture.
Si l’interrupteur est dans l’état 1-fermé, la lampe est dans l’état complémentaire
0-extinction; de même, si l’interrupteur est dans l’état 0-ouvert, la lampe est dans
l’état complémentaire 1-illumination.

1.2.2 Opérateur logique ET

L’opérateur ET (AND en anglais) est également appelée ”produit logique”, ou ”in-
tersection logique”. Sa notation algébrique utilise le symbole de la multiplication
arithmétique. Pour deux variables x et y, on a :

S = x.y

Sa table de vérité est celle représentée par le tableau 1.2.

x y S = x.y
0 0 0
0 1 0
1 0 0
1 1 1

Tableau 1.2: Table de vérité de l’opérateur logique ET

4 1. ALGÈBRE DE BOOLE

Ses symboles (1.2a et 1.2b) et le circuit électrique simple associé (1.2c) sont
représentés sur la figure 1.2. Rappellent qu’il est nécessaire que toutes les entrées
soient égales à 1 pour que la sortie vaille aussi 1. Notons que l’opération logique
ET peut comporter plus de deux entrées.

x y

x x E S
y & S S
y
(a) Symbole européen (b) Symbole américain
R

(c) Schéma électrique

Figure 1.2: Symboles et schéma électrique élémentaire de l’opérateur logique ET

1.2.3 Opérateur logique OU

L’opérateur logique OU (OR en anglais) est également appelée ”somme logique”, ou

”union logique”. Sa notation algébrique utilise le symbole de la somme arithmétique.
Pour deux variables x et y, on a :

S =x+y

Sa table de vérité est donc celle qui figure sur le tableau 1.3.

x y S =x+y
0 0 0
0 1 1
1 0 1
1 1 1

Tableau 1.3: Table de vérité de l’opérateur logique OU

Sur la figure 1.3, on a représenté ses symboles (1.3a et 1.3b), ainsi que le circuit
électrique simple associé (1.3c). On voit aisément qu’il faut que l’une au moins des
entrées soit égale à 1 pour qu’en sortie on ait 1 aussi. Comme ET, l’opération OU
peut comporter plus de deux entrées.
1.3. OPÉRATEURS LOGIQUES COMPOSÉS 5

y
x x
≥1 S S E S
y y
(a) Symbole européen (b) Symbole américain
R

(c) Schéma électrique

Figure 1.3: Symboles et schéma électrique élémentaire de l’opérateur logique OU

1.3 Opérateurs logiques composés

Les opérateurs composées (ou combinées, ou induits) sont obtenues en combinant

entre eux les opérateurs élémentaires NON, ET et OU. L’ensemble des opérateurs
élémentaires et des opérateurs combinées NON-ET, NON-OU et OU-EXCLUSIF
définissent un ensemble complet d’opérateurs.

1.3.1 Opérateur logique NON-ET

L’opérateur NON-ET, (NAND en anglais, contraction de NOT et AND), donne en

sortie, le complémentaire de l’opérateur ET de x et y:

S = x.y

La table de vérité est explicitée dans le tableau 1.4.

x y S = x.y
0 0 1
0 1 1
1 0 1
1 1 0

Tableau 1.4: Table de vérité de l’opérateur logique NON-ET

Le symbole est celui de ET avec le petit cercle en sortie qui indique la négation
de l’opération (voir figure 1.4b). Notons que la sortie ne vaut 0 que si toutes les
entrées valent 1 (voir figure 1.4c); en outre, la porte NON-ET peut, elle aussi,
comporter plus de deux entrées.
6 1. ALGÈBRE DE BOOLE

x
x x E S
y & S S y
y
(a) Symbole européen (b) Symbole américain R
(c) Schéma électrique

Figure 1.4: Symboles et schéma électrique élémentaire de l’opérateur NON-ET

1.3.2 Opérateur logique NON-OU

L’opérateur NON-OU, (NOR en anglais, de la contraction de NOT et OR), donne

en sortie le complémentaire de l’opérateur OU des entrées x et y:

S =x+y

On peut lire sa table de vérité sur le tableau 1.5.

x y S =x+y
0 0 1
0 1 0
1 0 0
1 1 0

Tableau 1.5: Table de vérité de l’opérateur logique NON-OU

Le circuit électrique simple associé, ainsi que ses symboles, sont dessinés sur la
figure 1.5. En ajoutant un petit cercle à la sortie de la porte OU, on traduit la
négation.

x x E x y S
y ≥1 S S
y
(a) Symbole européen (b) Symbole américain R
(c) Schéma électrique

Figure 1.5: Symboles et schéma électrique élémentaire de l’opérateur NON-OU

Notons que la porte NON-OU peut comporter plus de deux entrées et que la
sortie ne vaut 1 que si toutes les entrées sont dans l’état 0.
1.4. LOIS FONDAMENTALES 7

1.3.3 Opérateur logique OU-EXCLUSIF

Avec l’opérateur OU-EXCLUSIF (XOR en anglais), la sortie ne prend la valeur 1
que si les entrées x et y ont des valeurs différentes:

S = x.y + x.y = (x + y).(x + y) on la note également : S = x ⊕ y

On en déduit la table de vérité de cet opérateur (1.6).

x y S =x⊕y
0 0 0
0 1 1
1 0 1
1 1 0

Tableau 1.6: Table de vérité de l’opérateur logique OU-EXCLUSIF

Les symboles de cet opérateur sont représentés sur la figure 1.6.

x x
y =1 S S
y
(a) Symbole européen (b) Symbole américain

Figure 1.6: Symboles de l’opérateur logique OU-EXCLUSIF

1.4 Lois fondamentales

1.4.1 Propriétés monovariables
Elément neutre

Les opérateurs ET et OU admettent comme éléments neutres respectivement 1 et

0:
x.1 = x
x+0=x

Elément nul

A chaque opérateur correspond un élément nul (appelé aussi élément absorbant)

qui, lorsqu’il est opéré avec une variable quelconque x, donne un résultat identique
à cet élément nul :
x+1=1
x.0 = 0
8 1. ALGÈBRE DE BOOLE

Idempotence
Les opérateurs ET et OU sont idempotentes. Le résultat de ces opérateurs sur deux
variables identiques, est égal à cette même variable :

x+x=x
x.x = x

Complémentarité
x+x=1
x.x = 0

Involution
Le complément du complément d’une variable x est égal à cette variable :

x=x

1.4.2 Propriétés multivariables

Soit x, y et z trois variables booléennes.

Associativité
Les opérateurs +, . et ⊕ sont associatives :

x + y + z = (x + y) + z = x + (y + z)
x.y.z = (x.y).z = x.(y.z)
x ⊕ y ⊕ z = (x ⊕ y) ⊕ z = x ⊕ (y ⊕ z)

Commutativité
Les opérateurs +, . et ⊕ sont commutatives :

x+y =y+x
x.y = y.x
x⊕y =y⊕x

Distributivité
Chacun des opérateurs + et . est distributive sur l’autre :

x.(y + z) = x.y + x.z

x + (y.z) = (x + y).(x + z)

On peut remarquer que cette propriété est particulière dans l’algèbre booléenne
puisqu’ici les deux expressions sont vraies, alors que seule la première l’est dans
l’algèbre ordinaire.
1.5. THÉORÈME DE DE MORGAN 9

Absorption
Il y a absorption lorsqu’une variable en entrée s’impose en sortie, quelles que soient
les valeurs des autres entrées :
x + x.y = x
x.(x + y) = x

1.4.3 Théorème de Consensus

xy + xz + yz = xy + xz
(x + y)(x + z)(y + z) = (x + y)(x + z)
Les termes yz et y + z sont les termes consensus. Ils peuvent être simplifiés.

1.5 Théorème de DE MORGAN

1.5.1 Enoncé
Les deux théorèmes de De Morgan, du nom du logicien anglais du XIXe siècle A.
De Morgan qui les a établis, sont les suivantes :
ˆ La négation d’un porduit de variables est égale à la somme des négations de
ces variables
abc = a + b + c

ˆ La négation d’une somme de variables est égale au produit des négations de

ces variables
a + b + c = a.b.c

1.5.2 Application 1 du théorème

Le théorème de De Morgan permet de transformer une somme de produit en un
produit de somme et inversement.
Exemple:
Z = ab + cd + ad
Z = Z = ab + cd + ad
En appliquant le théorème de De Morgan:
Z = (a + b)(c + d)(a + d)

1.5.3 Application 2 du théorème

Grâce à ce théorème, on peut démontrer que les opérateurs NOR et NAND sont
des opérateurs universels, autrement dit, on peut réaliser n’importe quelle fonc-
tion logique uniquement avec l’un de ces opérateurs. Il suffit de démontrer que les
opérateurs fondamentaux (NON, ET, OU) peuvent être remplacés par une combi-
naison de NOR ou de NAND.
10 1. ALGÈBRE DE BOOLE

Démonstration pour l’opérateur NAND

NON

x S x S
⇔
S = x = xx

ET
x x
S S
y y
⇔
S = x.y = x.y

OU

S
x
S y
y
⇔
S = x + y = x + y = x.y

1.6 Représentation des fonctions logiques

Une fonction logique est une fonction d’une ou de plusieurs variables logiques,
représentée par une expression algébrique faisant intervenir les variables logiques
dont elle dépend et les opérateurs fondamentaux.
Exemples
f1 (x, y, z) = xy + xzy, f2 (x, y, z) = x ⊕ y + xz

1.6.1 Table de vérité (TdV)

Elle permet de connaı̂tre systématiquement les états que peut prendre une fonction
logique pour toutes les combinaisons des variables. Pour n variables, nous aurons
2n combinaisons différentes.
Exemples:

ˆ Pour une variable, la TdV aura 21 = 2 lignes

ˆ Pour deux variables, la TdV aura 22 = 4 lignes

1.6. REPRÉSENTATION DES FONCTIONS LOGIQUES 11

ˆ Pour trois variables, la TdV aura 23 = 8 lignes

ˆ Pour quatre variables, la TdV aura 24 = 16 lignes

La partie gauche de la table de vérité contient toutes les combinaisons des vari-
ables (entrées).
La partie droite contient la valeur prise par la fonction pour chaque combinaison
(sortie).
Exemple: TdV à trois variables

a b c f (a, b, c)
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1

Pour la réalisation de la TdV, on remarque que la variable c (poids faible) change

à chaque ligne, la variable b change toutes les deux lignes, a toutes les quatre lignes,
etc. . .

1.6.2 Forme canonique

Toute fonction peut être représentée sous sa forme canonique. Sous cette forme,
chaque terme est constitué de toutes les variables de la fonction. Lorsqu’une
équation est écrite à partir de sa table de vérité, elle est dans une forme canon-
ique. Ils existent plusieurs formes canoniques : les plus utilisées sont la première et
la deuxième forme.

1ère Forme Canonique ou Forme disjonctive (Sommes de Produits)

On cherche dans la table de vérité toutes les combinaisons pour lesquelles la fonction
est égale à 1. A chacune de ces combinaisons on fait correspondre un produit dans
lequel les variables ayant la valeur 0 sont complémentées et les variables ayant la
valeur 1 non complémentées. La fonction est alors la somme de tous ces produits.
Exemple : Soit la fonction S définit par la table de vérité suivante :

x y S
0 0 0
0 1 1
1 0 0
1 1 1
12 1. ALGÈBRE DE BOOLE

Dans notre cas, S vant 1 pour: x = 0 et y = 1 ⇒ terme xy et pour x = 1 et

y = 1 ⇒ terme xy donc
S = xy + xy

2ème Forme Canonique ou Forme conjonctive (Produits de Sommes)

On cherche cette fois dans la table de vérité toutes les combinaisons pour lesquelles
la fonction est égale à 0. Chaque combinaison fait apparaitre une somme dans
laquelle les variables ayant la valeur 1 sont complémentées et les variables ayant la
valeur 0 non complémentées. La fonction est alors le produit de toutes ces sommes.
Exemple : On reprend l’exemple précédent. Dans ce cas, S vant 0 pour : x = 0
et y = 0 ⇒ terme (x + y) et pour x = 1 et y = 0 ⇒ terme (x + y) donc

S = (x + y)(x + y)

1.6.3 Tableau de Karnaugh

Définition

La table de Karnaugh est une représentation plus compacte de la table de vérité.

Pour une fonction de n variables, La table de Karnaugh comporte 2n cases. D’une
case à la case voisine (verticalement ou horizontalement), une seule variable change
d’état car les lignes et les colonnes sont repérées par le code binaire réfléchi (le code
Gray).
Les axes de symétrie de la table de Karnaugh sont les axes de symétrie du code
binaire réfléchi.
Les combinaisons correspondantes à des cases symétriques par rapport à l’un des
axes sont adjacentes.
Deux termes sont adjacents quand ils ne diffèrent l’un de l’autre que par une seule
variable (a.b.c et a.b.c sont adjacents).
Exemple: fonction à 2 variables

x
S
y 0 1

0 0 1

1 1 1

ˆ 1ère forme canonique: S = x.y + x.y + x.y

ˆ 2ème forme canonique: S = x + y

1.6. REPRÉSENTATION DES FONCTIONS LOGIQUES 13

Construction de la table de Karnaugh

A partir de la table de vérité

A chaque combinaison de la table de vérité correspond une case unique dans la

table de Karnaugh. Cette case reçoit la valeur de la fonction.
Exemple :

Table de vérité Table de Karnaugh correspondante

ba
00 01 11 10 S
c b a S c
0 0 0 1 0 1 0 0 1
0 0 1 0
0 1 0 1 1 0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0

S = abc + abc + abc + abc

A partir de l’expression logique de la fonction

Soit la fonction suivante :

S = a(b + c) + abc + abcd

On développe la fonction sous forme de somme de produits :

S = ab + ac + abc + abcd

Chaque terme fait apparaı̂tre un certain nombre de 1 dans la table de Karnaugh :

ˆ ab : Si a = 0 et b = 1 alors S = 1 ∀c, d: on met 1 dans les cases pourlequelles

a = 0 et b = 1.

ˆ ac : Si a = 0 et c = 0 alors S = 1 ∀b, d

ˆ abc : Si a = 1, b = 1 et C = 0 alors S = 1 ∀d

ˆ abcd : Si a = 1, b = 0, c = 1 et d = 0 alors S = 1
14 1. ALGÈBRE DE BOOLE

cd
00 01 11 10 S
ab
00 1 1 0 0

01 1 1 1 1

11 1 1 0 0

10 0 0 0 1

1.6.4 Logigramme
Un logigramme est un schéma illustrant l’expression d’une fonction logique sans
tenir compte des constituants technologiques. Le principe consiste à remplacer
chaque opérateur logique par la porte logique qui lui correspond.
Exemple 1 : Réalisation de S = x.(y + z)
x
x(y + z)
y
z

Exemple 2 : Réalisation de S = x.y + xz

x
y
xy + xz

Les deux réalisation donnent le même résultat, cependant on préfère la réalisation

x(y + z) parce qu’elle est moins coûteuse en portes logiques.

1.6.5 Chronogramme
C’est le graphe d’évolution temporelle des variables et des fonctions logiques.
Exemple : Le chronogramme de la fonction NON