REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE

REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE

MINISTERE DE L’ENSEIGNEMENT SUPERIEUR ET DE LA RECHERCHE SCIENTIFIQUE
MINISTERE DE L’ENSEIGNEMENT SUPERIEUR ET DE LA RECHERCHE SCIENTIFIQUE
UNIVERSITE M’HAMED BOUGARA-BOUMERDES
UNIVERSITE M’HAMED BOUGARA-BOUMERDES

Module: Logique Combinatoire et Séquentielle

Chapitre 2: ALGEBRE DE BOOLE ET

SIMPLIFICATION DES FONCTIONS LOGIQUES

Chargée du Module: Dr Y, GUERBAI Maitre de Conférence A

E-Mail: y,guerbai@hotmail,com
• L’algèbre de Boole
• Opérateurs de base
• Propriétés et les fonctions combinatoires

11
 Introduction
• Les machines numériques (ordinateur, tablette, téléphone…)
sont constituées d’un ensemble de circuits électroniques.

• Chaque circuit fournit une fonction logique bien déterminée;

opérations logiques ou arithmétiques (addition, soustraction,
comparaison ,….).

A
F(A,B)
Circuit
B

• Une fonction logique de base est réalisée à l’aide des portes

logiques qui permettent d'effectuer des opérations
élémentaires. 12
 Introduction
4
• Ces portes logiques sont aujourd'hui réalisées à
l'aide de transistors.

• Pour concevoir et réaliser ce circuit on doit avoir un

modèle mathématique de la fonction réalisée par ce
circuit .
• Ce modèle doit prendre en considération le système
binaire.
• Le modèle mathématique utilisé est celui de Boole.
 Algèbre de Boole
5

1854 : Georges Boole propose une algèbre

Propositions vraies ou fausses

et opérateurs possibles Algèbre de Boole

Étude des systèmes binaires :

Possédant deux états s’excluant mutuellement
C’est le cas des systèmes numériques
(des sous ensembles : les circuits logiques)
 Algèbre
6 binaire
On se limite : Base de l’algèbre de Boole
Propriétés indispensables aux systèmes logiques
Définitions :

• États logiques : 0 et 1, Vrai et Faux, H et L

(purement symbolique)

• Variable logique : Symbole pouvant prendre

comme valeur des états logiques (A,b,c, Out ...)

• Fonction logique : Expression de variables et d’opérateurs

( f = not(a)^ (c OR r.t) )
 Calcul
7 propositionnel
Algèbre de Boole sur [0,1] = algèbre binaire
Structure d’algèbre de Boole
• 2 lois de composition interne (LCI)
• 1 application unaire

2 LCI : ET, OU
• Somme (OU, Réunion, Disjonction)
s=a+b=avb
• Produit (ET, intersection, Conjonction)
s = a . b = ab =a^b

Application unaire :
•Not (complémentation, inversion, négation, non) s = a =
not(a) = a
 Fonctions
8 logiques
Fonction logique à n variables f(a,b,c,d,...,n)
[0,1]n [0,1]

• Une fonction logique ne peut prendre que deux valeurs

• Les cas possibles forment un ensemble fini ( 2n)

• Descriptions, preuves possibles par énumération

comparer f(a,b,c,..n) et g(a,b,c,..,n)
= comparer les tables représentant f et g

La table de fonction logique = table de vérité

9

Opérateurs logiques de base

 OU ( OR
• 10
Le ) binaire ( deux variables) ,
OU est un opérateur à pour
rôle de réaliser la somme logique entre deux variables
logiques.
• Le OU fait la disjonction entre deux variables.
• Le OU est défini par F(A,B)= A + B ( il ne faut pas
confondre avec la somme arithmétique )

A B A+ B
0 0 0
0 1 1
1 0 1
1 1 1
 ET ( AND
11
)
• Le ET est un opérateur binaire ( deux variables) , à
pour rôle de réaliser le Produit logique entre deux
variables booléennes.
• Le ET fait la conjonction entre deux variables.

• Le ET est défini par : F(A,B)= A . B

A B A. B
0 0 0
0 1 0
1 0 0
1 1 1
 NON ( négation
12 )

• NON : est un opérateur unaire ( une seule variable) qui à

pour rôle d’inverser la valeur d’une variable .

F(A)= Non A = A
( lire : A barre )

0 1

1 0
 Tables de vérité de ET, OU, NON
13

b b
a 0 1 a 0 1 a
0 0 1 0 0 0 0 1
1 1 1 1 0 1 1 0
s=a+b s=a.b s= a
S est vrai si a OU b S est vrai si a ET b S est vrai
est vrai. sont vrais. si a est faux
ab s ab s a s
00 0 00 0 0 1
01 1 01 0 1 0
10 1 10 0
11 1 11 1
 Deux autres opérateurs :
14 NAND,NOR
b 0 1 b 0
a a 1
0 1 1 0 1 0
1 1 0 1 0 0
s = a b = a.b s = a b = a+b

S est vrai si a OU b S est vrai si ni a, ni b

est faux. ne sont vrais.

NAND (Not-AND) NOR (Not-OR)

NAND et NOR ne sont pas associatifs

 Encore un opérateur :
XOR

S est vrai si a OU b est vrai mais pas les deux.

XOR (Ou-Exclusif) vaut 1 si a est différent de b

Opérateur de différence (disjonction)
15
Encore un opérateur : XOR

16
 Système binaire

• Dans le système binaire, pour exprimer n’importe quelle valeur

on utilise uniquement 2 symboles : { 0 , 1}

La base
( 1101)2
Un bit

( 1 01 101 1)2
Le bit du poids forts Le bit du poids faible

. Un nombre dans la base 2 peut être écrit aussi sous la forme polynomiale

17
 Système binaire
Sur 4 Bits
Exemple
Sur 3 Bits
• Sur un seul bit : 0 , 1 Binaire Décimal
2 1 0
222 0000 0
Binaire Décimal 0001 1
• Sur 2 bits : 0010 2
000 0
Binaire Décimal 0011 3
001 1 0100 4
00 0
010 2 0101 5
01 1 0110 6
011 3
10 2 0111 7
100 4
11 3 1000 8
101 5 1001 9

2120 110 6 1010 10

1011 11
4 combinaisons= 22 111 7
1100 12
1101 13
8 combinaisons= 23 1110 14
1111 15

16 combinaisons= 24
19

Simplification des fonctions logiques

 Simplification /optimisation ?
20

Méthodes «classiques» de simplifications :

- pas de solution unique

- indépendant de la technologie
- le temps n’est pas pris en compte

La simplification «mathématique» n’est pas toujours

optimale en regard des critères d’optimisation
technologiques.
 Simplification des fonctions logiques
21
• L’objectif de la simplification des fonctions logiques est de :
– réduire le nombre de termes dans une fonction
– et de réduire le nombre de variables dans un terme

• Cela afin de réduire le nombre de portes logiques utilisées 

réduire le coût du circuit

• Plusieurs méthodes existent pour la simplification :

1) Les méthodes algébriques

2) Les méthodes graphiques : ( ex : tableaux de
karnaugh )
 Propriétés de ET,OU,NON

1) Les méthodes algébriques

• Commutativité • Idempotence
a+b = b+a a+a = a
a.b = b.a a.a = a
• Associativité • Absorption
a+(b+c) = (a+b)+c a+a.b = a
a.(b.c) = (a.b).c a.(a+b) = a
• Distributivité • Involution
a.(b+c) = a.b+a.c a=a
a+(b.c) = (a+b).(a+c)
 Propriétés de ET,OU,NON
Les méthodes algébriques
• Théorème de "De Morgan"
• Elément neutre a+b = a . b
a+0 = a
a.b = a + b
a.1 = a
• Elément absorbant x x
i i
i i
a+1 =1
a.0 = 0 x x
i
i
i
i

• Inverse • Théorème du Consensus

a+a = 1 a.x+b.x+a.b = a.x+b.x
a.a = 0
(a+x)(b+x)(a+b)=(a+x)(b+x)
 Algèbre de Boole : Théorèmes associés à l’algèbre

combinatoire
III. Logique
de Boole( Récapitulatif )

24
a,b,c  E2
𝑎. 𝑎 = 𝑎
 idempotence 𝑎+𝑎=𝑎
𝑎 + 𝑎. 𝑏 = 𝑎
 absorption :
𝑎. (𝑎 + 𝑏) = 𝑎

 involution : 𝑎" = 𝑎

 Théorème de Morgan : 𝑎 + 𝑏 = 𝑎. 𝑏 ; 𝑎. 𝑏 = 𝑎 + 𝑏

 Théorème de Shannon : 𝑎 + 𝑏 = 𝑎. 𝑏 + 𝑎. 𝑏 + 𝑎. 𝑏
𝑎 + 𝑎. 𝑏 = 𝑎 + 𝑏
 Consensus de 1ière espèce : Termes de
𝑎. 𝑎 + 𝑏 = 𝑎. 𝑏 Consensus
 Consensus de 2nd espèce : 𝑎. 𝑏 + 𝑏. 𝑐 = 𝑎. 𝑏 + 𝑏. 𝑐 + 𝑎. 𝑐
b variable biforme 𝑎 + 𝑏 . 𝑏 + 𝑐 = 𝑎 + 𝑏 . 𝑏 + 𝑐 . (𝑎 + 𝑐)
 Algèbre de Boole : Théorèmes associés à
l’algèbre de Boole( Récapitulatif )

 repérer les variables biformes,

 introduire le terme de Consensus de 2nd espèce s'il permet de

réduire l'expression par absorption,

 absorption,

 retirer le terme de consensus.

 Propriétés de ET,OU,NON
26

Exercice 1:
Démontrez la proposition suivante :

ABC  ABC  ABCD  AB  ACD

A B C  ABC  ABC  ABC  BC  AC  AB

 Propriétés de ET,OU,NON
27

Correction
ABC  ABC  ABCD  AB (C  C)  ABCD
 AB  ABCD
 A ( B  B (CD))
 A ( B  CD)
 AB  ACD

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

A.B.C  A.B.C  A.B.C  A.B.C  ABC  A.B.C 
B.C  A.C  A.B
 combinatoire
Algèbre de Boole : Fonctions booléennes

III. Logique
28

entrées sortie(s)
E2xE2x...xE2 dans E2.
a b s
0 0 0
0 1 1
1 0 1
1 1 0
Table de vérité

Deux façons d’exprimer une fonction booléenne :

 la forme somme de produit ou disjonctive normale ΣΠ
 la forme produit de somme ou conjonctive normale ΠΣ
 Passage de la fonction logique à la
table de vérité
◆ Pour chaque combinaison de valeurs possibles pour les
variables, on détermine la valeur booléenne de f(X)
(X = ensemble des variables)
◆ Exemple : f(a , b , c)=ab+b c+ac

2
9
Passage de la table de vérité à la fonction logique

◆ A partir de la table de vérité : fonction sous

première forme canonique
◆ Pour chaque valeur de f(X) égale à 1
◆ On définit un minterme de toutes les variables tel que
◆ Si une variable Xi = 1 on note Xi, sinon on note Xi

◆ La première forme canonique de f(X) est le OU

de ces mintermes

3
0
Passage de la table de vérité à la fonction logique

◆ A partir de la table de vérité : fonction sous

seconde forme canonique
◆ Pour chaque valeur de f(X) égale à 0
◆ On définit un minterme de toutes les variables tel que
◆ Si une variable Xi = 1 on note Xi, sinon on note Xi

◆ Le OU de ces mintermes = f(Xi)

◆ Après calcul de f(Xi), on obtient la seconde forme
canonique

3
1
 Exemple de calcul de la fonction logique sous
première forme

◆ A partir de la table de vérité de l'exemple

précédent
◆ f(a,b,c) = 1 quand :
◆ a = 0, b = 0 et c = 1 d'où le minterme a bc
◆ a = 1, b = 0 et c = 0 d'où le minterme a b c
◆ a = 1, b = 0 et c = 1 d'où le minterme a bc
◆ a = 1, b = 1 et c = 0 d'où le minterme a b c
◆ a = 1, b = 1 et c = 1 d'où le minterme a b c
◆ On fait le OU de ces mintermes
◆ f(a , b , c)= abc+abc+a b c+a b c+a3bc
2
Exemple de calcul de la fonction logique sous
seconde forme

◆ A partir de la table de vérité de l'exemple

précédent
◆ f(a,b,c) = 0 quand :
◆ a = 0, b = 0 et c = 0 d'où le minterme a bc
◆ a = 0, b = 1 et c = 0 d'où le minterme a bc
◆ a = 0, b = 1 et c = 1 d'où le minterme a bc
◆ On fait le OU de ces mintermes
◆ f(a,b,c)=a bc+a bc+a b c
◆ Au final :
f(a , b , c)=(a+b+c)(a+b+c)(a+b+c)
3
3
34

Simplification par la table

de Karnaugh
 Description de la table de karnaugh

•La méthode consiste à mettre en évidence par une méthode

graphique (un tableau ) tous les termes qui sont adjacents (qui
ne différent que par l’état d’une seule variable).

•Un tableau de Karnaugh = table de vérité de 2n cases avec un

changement unique entre 2 cases voisines d’où des codes
cycliques (Gray ou binaire réfléchi).

•La méthode peut s’appliquer aux fonctions logiques de 2,3,4,5 et

6 variables.

•Les tableaux de Karnaugh comportent 2n cases ( n: est le 36

nombre de variables ).
 Description de la table de karnaugh

Règles de regroupement :

- groupe de 2n cases : 1,2,4 ou 8

- en ligne, colonne, rectangle, carré, mais pas diagonale
- tous les 1, mais pas les 0 au moins une fois dans les groupements

Règles de minimisation de la fonction :

- rechercher les groupements en commençant par les cases qui n’ont

qu’une seule façon de se grouper
- rechercher les groupements les plus grands
- les groupements doivent contenir au moins un 1 non utilisé par les
autres groupements
- L’expression logique finale est la réunion ( la somme ) des
groupements après simplification et élimination des variables qui
changent d’état. 37
 Description de la table de
37karnaugh

A AB
B 0 1 C 00 01 11 10
0 0

1 1

Tableau à 2 variables Tableaux à 3 variables

 Tableaux de Karnaugh
38

f (a,c,d, ..,n) fonction logique à N entrées sera représentée par

une table à 2N lignes
un tableau à 2N cases

Code Gray ou
bc binaire réfléchi
a 00 01 11 10 =
1 seul changement
0 0 1 0 0
entre 2 codes
successifs
1 1 0 1 0

f(a,b,c)
 Tableaux de Karnaugh

39
Exemple 1 : 3 variables
AB
C 00 01 11 10
0 0 0 1 0
1 1 1 1 1

F ( A, B,C)  C  AB
 Tableaux de Karnaugh

40
Exemple 2 : 4 variables
AB
CD 00 01 11 10
00 0 0 0 1
01 1 1 1 1
11 0 0 0 0
10 0 1 0 0

F ( A , B , C , D )  C .D  A.B .C  A.B .C .D
 Tableaux de
41
Karnaugh
Exemple 3 : 4 variables
AB
CD 00 01 11 10
00 1 1
01 1 1 1
11 1
10 1 1

F( A, B,C, D)  AB  BD  BCD
 Tableaux de Karnaugh
Exemple
42 4 : 5 variables
AB AB
CD 00 01 11 10 CD 00 01 11 10
00 1 00 1
01 1 1 01 1 1
11 1 1 11 1 1
10 1 10 1 1

U=0 U= 1

F(A,B, C, D, U)  A B  A.B.D.U  A.C.D.U  A.B.D.U

 Exercic
e 43
Trouver la forme simplifiée des fonctions à partir des
deux tableaux ?

AB
CD 00 01 11 10
AB
C 00 01 11 10 00 1 1 1
0 1 1 1 01

1 1 1 1 11

10 1 1 1 1
 Logique multi-niveaux
44

On peut généraliser l’algèbre binaire à plus de 2

niveaux
b 0 1 Z X
a
0 0 X 0 X 1 logique

X 1 1 X 2 logique
1
Z déconnecté
Z 0 1 Z X
X inconnu
X X X X X
 Logique multi-niveaux
45
• Pour les cas impossibles ou interdites
il faut mettre un X dans la T.V .
•Les cas impossibles sont représentées
aussi par des X dans la table de karnaugh

AB
CD
00 01 11 10
00 1
01 1 X X
11 1 1 X X
10 1 1 1
 Tableaux de Karnaugh

• Il est possible d’utiliser les X dans des regroupements :

– Soit les prendre comme étant des 1
– Ou les prendre comme étant des 0
• Il ne faut pas former des regroupement qui contient uniquement des X

AB
CD
00 01 11 10
00 1
01 1 X X
11 1 1 X X
10 1 1 1

AB 47
 Tableaux de Karnaugh

AB
CD
00 01 11 10
00 1
01 1 X X
11 1 1 X X
10 1 1 1

A B  C D 48
 Tableaux de Karnaugh

48

AB
CD
00 01 11 10
00 1
01 1 X X
11 1 1 X X
10 1 1 1

AB  CD  BD
 Tableaux de Karnaugh

49 AB
CD
00 01 11 10
00 1
01 1 X X
11 1 1 X X
10 1 1 1

AB  CD  BD  AC
 Tableaux de Karnaugh

AB
CD
00 01 11 10
00 1
01 1 X X
11 1 1 X X
10 1 1 1

AB  CD  BD  AC  BC 51
 Représentation des fonctions
51

• Diagramme de Venn ou d’Euler

vue ensembliste
• Table de vérité
• Tableau de Karnaugh
• Équation logique ex: f(a,b)=a+b
• Chronogramme : Graphe d’évolution temporelle

a+b
 Chronogrammes

52

Plusieurs niveaux d’abstraction :

fonctionnel,

a
1 0 0 1 1 1 0 0

b
0 0 1 1 1 1 0

a+b
 Chronogrammes

53

Plusieurs niveaux d’abstraction :

temporel

a
1 1

b
1

a+b

Retard temporel
 Chronogrammes

54

Plusieurs niveaux d’abstraction :

analogique symbolique

a+b
 Réalisation en
55 électronique
0/1 représentés par des tensions, courants, charges, fréquences,
....

Classiquement TENSIONS : Niveau haut = H (le plus positif)

Niveau bas = L (B) (le plus négatif)

Association d’une information binaire à un niveau :

Convention positive H 1
(ou logique positive) L 0

Convention négative H 0
(ou logique négative) L 1
 Représentation graphique
: Norme française
56

Les portes logiques:

a a
b s b s a s
& &
ET NAND NON

a a a
b s b s b s
>1 >1 =1
OU NOR XOR
 Représentation graphique
: Norme américaine
57

Les portes logiques:

a s
a a
s s
b b NON
a s
ET NAND

a a
s a
s s
b b b
OU NOR XOR
 Schéma d’un circuit logique ( Logigramme)
58
•Un logigramme est la traduction de la fonction logique
en un schéma électronique.

•Le principe consiste à remplacer chaque opérateur

logique par la porte logique qui lui correspond.
A

Exemple 1
B F
F( A, B,C)  A.B  B.C

C
Merci pour votre attention