ENSETP/TI/ET ELECTRONIQUE NUMERIQUE M.

GUEYE

ELEMENTS DE LOGIQUE COMBINATOIRE

I/ FONCTIONS/OPERATEURS LOGIQUES - ALGEBRE DE BOOLE
1-1 DEFINITIONS
1-1-1 Variable logique et fonction logique
Une variable logique est une variable qui peut prendre deux états : "0" ou "1"; "faux" ou "vrai".
Une fonction logique de variables logiques est une fonction dont les valeurs peuvent être les
deux états "0" ou "1" ; "faux" ou "vrai".
1-1-2 Opérateurs logiques élémentaires
Les opérateurs logiques élémentaires servent à construire les fonctions logiques. En algèbre
classique on distingue quatre opérateurs de base : +, -, *, / ; en algèbre de Boole ils sont au
nombre de trois : ET, OU, NON ou encore « intersection », « union », « complément ».
Exemple : la fonction f est vraie si a est vrai ou si b et c sont vrais ou si d est faux s’écrit :

𝑓 = 𝑂𝑈 𝑎, 𝐸𝑇(𝑏, 𝑐), 𝑁𝑂𝑁(𝑑) 𝑜𝑢 𝑒𝑛𝑐𝑜𝑟𝑒 𝑓 = 𝑎 + 𝑏𝑐 + 𝑑

1-1-3 Opérateurs logiques complets

On peut montrer qu’il est possible de synthétiser les trois opérateurs de base avec un seul type
d’opérateur que l’on appelle alors « opérateur complet ».
Il existe deux opérateurs complets : le ET-NON ou NAND et le OU-NON ou NOR.
1-2 Ecriture des fonctions logiques
Une fonction logique, définie par son expression, peut être représentée de plusieurs manières.
1-2-1 Table de vérité
Les combinaisons de n variables logiques sont limitées à 2n du fait que les variables ne peuvent
prendre que deux valeurs. On peut ainsi représenter la fonction logique à l’aide d’un tableau
faisant
Exemple : f(a,b) = a + b signifie : f = 1 si a = 1 ou b = 1 ou a = b = 1 (voir table de vérité tableau
ci-dessous).

a b a+b
0 0 0
0 1 1
1 0 1
1 1 1

La table de vérité comporte 2n lignes (une pour chaque combinaison des variables d’entrée)

𝑓(0,0) = 0; 𝑓(0,1) = 1; 𝑓(1,0) = 1; 𝑓(1,1) = 1

1-3 Fonction élémentaires

1-3-1 Opérateur OUI ou SI
L'état de la sortie est égal à l'état de l'entrée, cette fonction ne présente pas d'intérêt d'un point
de vue logique mais peut être utile d'un point de vue technologique.

1
ENSETP/TI/ET ELECTRONIQUE NUMERIQUE M. GUEYE

1-3-2 Opérateur NON ou NOT:

C’est une opération définie sur une seule variable. La sortie prend la valeur que n’a pas l’entrée.
On dit que la sortie est l’inverse ou le complément de l’entrée.

2
ENSETP/TI/ET ELECTRONIQUE NUMERIQUE M. GUEYE

1-3-3 Opération ET (AND) :

C’est une opération sur 2 variables d’entrée au moins. Dans le cas simple de 2 entrées a et b, la
sortie est vraie (égale à 1) si a ET b sont vraies aussi.

Opérateur Table de Vérité Symbole

ET ou AND (norme IEEE) norme IEC)
a b L
0 0 0
0 1 0
1 0 0
1 1 1

Equation Chronogramme

F = A.B

1-3-4 Opération OU (OR) :

C’est une opération sur 2 variables d’entrée au moins. Dans le cas simple de 2 entrées a et b, la
sortie est vraie (égale à 1) si seulement a OU b est vraie. Cette opération est dite OU inclusive,
car on inclut le cas (a = b = 1 ; F = 1).

Opérateur Table de Vérité Symbole

OU ou OR (norme IEEE) norme IEC)

3
ENSETP/TI/ET ELECTRONIQUE NUMERIQUE M. GUEYE

a b L
0 0 0
0 1 1
1 0 1
1 1 1

Equation Chronogramme

F=A+B

1-3-5 Opération ET NON ou (NAND) :

C’est une opération sur 2 variables d’entrée au moins. Dans le cas simple de 2 entrées a et b, la
sortie est vraie (égale à 1) si seulement l’une des entrées a ou b est égale à “0”. C’est le
complément de l’opérateur AND.

Opérateur Table de Vérité Symbole

ET-NON ou (norme IEEE) norme IEC)
NAND a b L
0 0 1
0 1 1
1 0 1
1 1 0

Equation Chronogramme

4
ENSETP/TI/ET ELECTRONIQUE NUMERIQUE M. GUEYE

𝑭 = 𝑨. 𝑩

1-3-6 Opération OU-NON (NOR) :

C’est une opération sur 2 variables d’entrée au moins. Dans le cas simple de 2 entrées a et b, la
sortie est vraie (égale à 1) si les deux entrées a, b sont en même temps égales à “0”. C’est le
complément de l’opérateur OR.

Opérateur Table de Vérité Symbole

OU-NON ou (norme IEEE) norme IEC)
NOR a b L
0 0 1
0 1 0
1 0 0
1 1 0

Equation Chronogramme

𝑭= 𝑨+𝑩

5
ENSETP/TI/ET ELECTRONIQUE NUMERIQUE M. GUEYE

1-3-7 Opération OU EXCLUSIF (EXOR) :

La sortie est vraie (égale à 1) si les deux entrées a, b sont dans des états logiques différents.

Opérateur Table de Vérité Symbole

OU-EXCLUSIF (norme IEEE) norme IEC)
ou EXOR a b L
0 0 0
0 1 1
𝐹 = 𝐴𝐵 + 𝐴𝐵 1 0 1
1 1 0

Equation Chronogramme

1-3-8 Opération XNOR :

La sortie est vraie (égale à 1) si les deux entrées a, b sont dans les mêmes états logiques
simultanément.
Opérateur Table de Vérité Symbole
NON-OU- (norme IEEE) norme IEC)
EXCLUSIF ou a b L
XNOR 0 0 1
0 1 0
1 0 0
1 1 1

Equation Chronogramme

6
ENSETP/TI/ET ELECTRONIQUE NUMERIQUE M. GUEYE

𝐹 = 𝐴𝐵 + 𝐴𝐵

II/ PROPRIETES DES FONCTIONS LOGIQUES

2-1 Fonction AND
- La fonction AND est commutative associative: 𝐹 = 𝑎. 𝑏 = 𝑏. 𝑎
- La fonction AND est : 𝐹 = 𝑎. (𝑏. 𝑐) = (𝑎. 𝑏). 𝑐 = 𝑎. 𝑏. 𝑐
- La fonction AND est généralisable pour n entrées.
- Identités remarquables : 0. 𝑎 = 0; 𝑎. 1 = 𝑎; 𝑎. 𝑎 = 𝑎; 𝑎. 𝑎 = 0

2-2 Fonction OU
Comme la fonction AND, la fonction OR est commutative, associative et généralisable pour n
entrées :
- Identités remarquables :
𝑎 + 0 = 𝑎; 𝑎 + 1 = 1; 𝑎 + 𝑎 = 𝑎; 𝑎 + 𝑎 = 1

2-3 Fonction NAND

- La fonction NAND est commutative :.

𝐹 = 𝑎. 𝑏 = 𝑏. 𝑎

- La fonction NAND n’est pas associative :

𝐹 = 𝑎. ( 𝑏. 𝑐) ≠ (𝑎𝑏). 𝑐 ≠ 𝑎. 𝑏. 𝑐

- La fonction NAND est généralisable pour n entrées.

- L'opérateur NAND est dit "système logique complet", car il permet de réaliser toutes
les opérations de base : NOT, AND et OR ; et par conséquent, toute fonction logique :
- Réalisation d'un inverseur :

7
ENSETP/TI/ET ELECTRONIQUE NUMERIQUE M. GUEYE

𝐹 = 𝑎. 𝑎 = 𝑎

𝐹 = 𝑎. 1 = 𝑎

- Réalisation d'une fonction AND 𝐹 = 𝑎. 𝑏 :

Théorème de De Morgan :
Ce théorème d'une grande utilité, permet de calculer le complément d'une expression
logique quelconque (somme de produits ou produit de sommes) :
𝐹 = 𝑎 + 𝑏 = 𝑎. 𝑏
𝐹 = 𝑎. 𝑏 = 𝑎 + 𝑏
D'une façon générale, Le complément d'une expression quelconque s'obtient en
complémentant les variables et en permutant les opérateurs "+" et ".".

𝐹 = 𝑎. 𝑏. 𝑑 + 𝑎. 𝑑 → 𝐹 = 𝑎. 𝑏𝑑 + 𝑎. 𝑑 = (𝑎 + 𝑏 +𝑑).(𝑎 + d)
En appliquant le théorème de De Morgan

𝐹 = 𝐹 = 𝑎. 𝑏

- Réalisation d'une fonction OR 𝐹 = 𝑎 + 𝑏 :

𝐹 = 𝐹 = 𝑎 + 𝑏 ⇒ 𝐹 = 𝑎. 𝑏

2-4 Fonction NOR

- Comme la fonction NAND, la fonction NOR n'est ni combinatoire, ni associative ; elle
est aussi généralisable pour n entrées
- L'opérateur NOR est un système logique complet, comme le NAND.

2-5 Fonction XOR

- L’opération XOR est commutative : 𝐹 = 𝑎 ⊕ 𝑏 = 𝑏 ⊕ 𝑎

8
ENSETP/TI/ET ELECTRONIQUE NUMERIQUE M. GUEYE

- L’opération XOR est associative :

𝐹 = 𝑎 ⊕ (𝑏 ⊕ 𝑐) = (𝑎 ⊕ 𝑏) ⊕ 𝑏 = 𝑎 ⊕ 𝑏 ⊕ 𝑐
- L’opération XOR n'est pas généralisable pour n entrées.

III/ PROPRIETES ET THEOREMES REMARQUABLES :

Propriétés
- Distributivité du produit par rapport à la somme;
a.(b + c) = a.b + a.c
- Distributivité de la somme par rapport au produit;
a+(b.c) = (a + b).(a + c)
- Factorisation ;
a.b + 𝑎.b = b(a + 𝑎) = b
- Loi d'absorption;
a + 𝑎.b = a + b en effet si on applique la distributivité
On a : a + 𝑎.b = (a + 𝑎 ).(a + b) = a + b

- Involution
𝑎=a
- Inclusion
ab + a.𝑏 = a (b + b).(a + b) = a
- Complémentarité
a.𝑎 = 0 ; a + 𝑎 = 1
- Idempotence
- a.a = a ; a + a = a
IV/ SIMPLIFICATION DE FONCTIONS
La simplification d’une fonction consiste à obtenir son expression la plus compacte possible
afin de minimiser le nombre d’opérateurs logiques nécessaires à sa réalisation. On distingue
deux méthodes de simplification : méthode algébrique ; méthode graphique.
4-1 Simplification algébrique
Cette technique de simplification repose sur l’utilisation des propriétés de l’algèbre de Boole et
des théorèmes fondamentaux. Elle est moins systématique que la simplification graphique mais
peut parfois donner des résultats rapidement
4-1-1 Utilisation des identités particulières
𝑎𝑏 + 𝑎𝑏 = 𝑎 (𝑎 + 𝑏)(𝑎 + 𝑏) = 𝑎
𝑎𝑏 + 𝑎 = 𝑎 𝑎(𝑎 + 𝑏) = 𝑎
𝑎 + 𝑎𝑏 = 𝑎 + 𝑏 𝑎(𝑎 + 𝑏) = 𝑎𝑏
Exemple :
𝑓 = 𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐𝑑 = 𝑎𝑏(𝑐 + 𝑐) + 𝑎𝑏𝑐𝑑 = 𝑎(𝑏 + 𝑏𝑐𝑑)
Par absorption

9
ENSETP/TI/ET ELECTRONIQUE NUMERIQUE M. GUEYE

𝑓 = 𝑎(𝑏 + 𝑐𝑑) = 𝑎𝑏 + 𝑎𝑐𝑑

4-1-2 Ajout de terme existant (utilisation de l’idempotence)
𝑓 = 𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐 = 𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐
𝑓 = 𝑏𝑐(𝑎 + 𝑎) + 𝑎𝑐 𝑏 + 𝑏 + 𝑎𝑏(𝑐 + 𝑐) = 𝑏𝑐 + 𝑎𝑐 + 𝑎𝑏

4-1-3 Suppression de terme inclus

𝑓 = 𝑎𝑏 + 𝑏𝑐 + 𝑎𝑐 = 𝑎𝑏 + 𝑏𝑐 + 𝑎𝑐 𝑏 + 𝑏 = 𝑎𝑏 + 𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐
𝑓 = 𝑎𝑏(1 + 𝑐) + 𝑏𝑐(1 + 𝑎) = 𝑎𝑏 + 𝑏𝑐

4-2 Simplification graphique

Principe
Cette méthode repose sur l’utilisation des tableaux de Karnaugh. Elle consiste à mettre en
évidence des associations du type :
𝑎𝑏 + 𝑎𝑏 = 𝑎 𝑏 + 𝑏 = 𝑎
𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐 = 𝑎𝑏(𝑐 + 𝑐) + 𝑎𝑏(𝑐 + 𝑐) = 𝑎

On remarque que les regroupements ci-dessus correspondent aux cas où l’on a 2, 4, 8, (2n en
général) cases adjacentes sur le tableau de Karnaugh, qui sont simultanément égales à 1.
- Adjacence des cases
Deux cases adjacentes sur le tableau de Karnaugh correspondent à des combinaisons
différant d’un seul bit (ceci est dû l’utilisation du code de Gray). Ceci est valable à
l’intérieur du tableau mais aussi sur ses bords : en passant du bord droit au bord gauche
ou du haut au bas il y a adjacence. Ceci revient à dire que l’on peut considérer le tableau
comme une sphère.
- Règle pratique
La règle consiste donc à « fusionner » ces 2n cases adjacentes pour trouver l’expression
résultante. On regarde la ou les variables qui change(nt) entre les cases fusionnées ; ces
variables sont alors supprimées dans la nouvelle expression simplifiée.
Exemples :
𝑓 = 𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐

𝒇=𝒃
𝑓 = 𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐

10
ENSETP/TI/ET ELECTRONIQUE NUMERIQUE M. GUEYE

𝒇 = 𝒂𝒃 + 𝒂𝒄

 On ne regroupe que 2n cases (2,4,8,16,…).

 Les regroupements sont forcément des rectangles ou carrés (compte tenu des
permutations pour les bords). Pas de « L », pas de croix, …
 L’expression sera d’autant plus compacte que l’étendue des regroupements est
grande. Pour un regroupement occupant la moitié du tableau il n’y a plus qu’une
variable, pour le quart il reste deux variables, pour un regroupement de deux
cases, il reste n-1 variables. A la limite un regroupement de tout le tableau fait
disparaître toute variable (f =1). D’une manière générale, un regroupement de 2i
cases conduit à supprimer i variables.
 Il est inutile de regrouper des « 1 » qui ont tous déjà été regroupés par ailleurs.
On parle alors de terme inclus.
4-3 Combinaisons impossibles
Parfois des combinaisons particulières des valeurs des variables ne peuvent pas se produire,
pour des raisons physiques ou technologiques. On utilise alors ces combinaisons pour simplifier
la fonction. Le principe consiste à dire que puisque la combinaison n’apparaît pas, on considère
que si elle apparaissait, elle donnerait un 1 ou un 0, selon ce qui nous arrange pour la
simplification (un ascenseur ne peut être à 2 étages au même instant).
Exemple 1 : on crée la fonction f(a,b,c,d) telle que f = 1 si 1 < N < 5 avec N codé en BCD. On
dispose de 4 bits pour coder les nombres de 0 à 9 ; or 4 bits permettent de coder jusqu’à 24 = 16
valeurs :

11
ENSETP/TI/ET ELECTRONIQUE NUMERIQUE M. GUEYE

Si on ne tient pas compte des états 10 à 15, f s’écrit

𝑓 = 𝑎𝑏𝑐 + 𝑎𝑏𝑐𝑑

En considérant que les combinaisons impossibles sont affectées arbitrairement des valeurs 0 ou
1 on peut obtenir :
𝑓 = 𝑏𝑐 + 𝑏𝑐𝑑

Règle pratique : on remplit les cases avec le symbole φ qui montre que l’on peut choisir la
valeur que l’on veut (0 ou 1) pour cette case.

12
ENSETP/TI/ET ELECTRONIQUE NUMERIQUE M. GUEYE

V/ REPRESENTATION DES FONCTIONS LOGIQUES :

Pratiquement, une fonction logique est représentée par :
- Son équation logique qui n'est qu'une association de sommes et de produits logiques ;
- Sa table de vérité ou son tableau de Karnaugh ;
- Son logigramme qui est une représentation symbolique, sous forme d'un schéma, formé
par les différentes liaisons entres les symboles des opérateurs élémentaires.
Exemple : Voilà les 3 représentations d'une certaine fonction F à 3 variables a, b et c :
- L'équation logique donnée est : 𝑓(𝑎, 𝑏, 𝑐) = 𝑐𝑎 + 𝑐𝑏;
- La table de vérité, déduite à partir de l'équation, est : On a 3 variables d'entrées → on a
23 combinaisons possibles (23 lignes de la table). D'une façon générale, on a 2n
combinaisons pour n variables d'entrée. On déduit l'équation logique de la fonction F, à
partir de la table de vérité suivant le raisonnement suivant :
 On cherche les lignes où la fonction F est égale à 1 ;
 On note la combinaison des entrées pour chacune de ces lignes ;
 On somme logiquement ces combinaisons.

F = 𝑎𝑏𝑐̅ + 𝑎𝑏𝑐 + 𝑎𝑏𝑐 + 𝑎𝑏𝑐 = 𝑎𝑏(𝑐̅ + 𝑐) + 𝑎𝑐 𝑏 + 𝑏 = 𝑎𝑏 + 𝑎𝑐

- Le logigramme déduit de l'équation est :

..
On remarque que cette petite fonction emploie différents types de portes logiques : inverseur,
AND et OR. Il est évident qu'il serait rentable de réaliser cette fonction logique avec le
minimum de matériel (circuits logiques), ce qui demande une bonne analyse du problème pour
simplifier la fonction en question.

13