ELE1300
Circuits
logiques
2. Algèbre de Boole
Objectifs du cours
• Connaître et comprendre
• Les mathématiques sous-jacentes à la manipulation des signaux logiques.
• Les symboles utilisés
• Être capable de
• Transformer des expressions booléennes en appliquant les théorèmes
• Dessiner un circuit à partir de son expression booléenne et réciproquement
ELE1300 - Circuits logiques 2
Mise en bouche 1
ELE1300 - Circuits logiques 3
Mise en bouche 2
ELE1300 - Circuits logiques 4
Algèbre de Boole
Une algèbre de Boole est constituée de :
un ensemble E,
deux éléments particuliers de E : 0 et 1
(correspondant respectivement à FAUX et VRAI),
deux opérations binaires sur E : + et ·
(correspondant respectivement au OU et ET logiques)
une opération unaire sur E : ¯
(correspondant à la négation (NON) logique).
ELE1300 - Circuits logiques 5
Postulats
On admet les postulats suivants :
Opérateur ET Opérateur OU Opérateur NON
(·) (+) ( )
P1. 0·0 = 0 P4. 0+0 = 0 P7. 0 1
P2. 0·1 = 0 P5. 0+1 = 1 P8. 1 0
P2.* 1·0 = 0 P5.* 1+0 = 1
P3. 1·1 = 1 P6. 1+1 = 1
ELE1300 - Circuits logiques 6
Axiomes
Pour 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+A =1 A·A =0
ELE1300 - Circuits logiques 7
Théorèmes (quelques)
A A (involution)
A A A (idempotence)
A A A
A A B A A A B A (loi d’absorption)
A A B A B
A A B A B
A B A B A B A B (loi de DeMorgan)
A11 A0 0 (élément nul)
ELE1300 - Circuits logiques 8
Principe de dualité
Deux expressions booléennes se correspondent par dualité si
on obtient la seconde en faisant les changements suivants
dans la première:
changer les + pour des ·
changer les · pour des +
changer les 0 pour des 1
changer les 1 pour des 0
Tous les théorèmes ont une forme duale.
ELE1300 - Circuits logiques 9
Application de l’algèbre de Boole
• Nous allons utiliser l’algèbre de Boole pour effectuer des
démonstration de manière analytique
Exemple 1 – Loi d’absorption
?
ELE1300 - Circuits logiques 10
Application de l’algèbre de Boole
• Nous allons utiliser l’algèbre de Boole pour effectuer des
démonstration de manière analytique
Exemple 1 – Loi d’absorption:
?
= (A+ ) (A+B) + distributif sur
= 1 (A+B) complémentation
= A+B élément neutre
ELE1300 - Circuits logiques 11
Application de l’algèbre de Boole (…)
Exemple 2:
A·B+A·C+B·C = A·B+A·C ?
ELE1300 - Circuits logiques 12
Application de l’algèbre de Boole (…)
Exemple 2:
A·B+A·C+B·C = A·B+A·C ?
A·B+A·C+B·C = A·B·1+A·C·1+B·C·1 élément neutre
= A·B·(C+C)+A·C·(B+B)+B·C·(A+A) complémentation
= A·B·C+A·B·C+A·C·B+A·C·B+B·C·A+B·C·A · distributif sur +
= A·B·C+A·B·C+A·B·C+A·B·C+A·B·C+A·B·C commutativité
… suite à la page suivante
ELE1300 - Circuits logiques 13
Application de l’algèbre de Boole (…)
= A·B·C+A·B·C+A·B·C+A·B·C+A·B·C+A·B·C
= A·B·C+A·B·C+A·B·C+A·B·C idempotence
= A·B·C+A·B·C+A·C·B+A·C·B commutativité
= A·B·(C+C)+A·C·(B+B) · distributif sur +
= A·B·(1)+A·C·(1) complémentation
= A·B+A·C élément neutre
ELE1300 - Circuits logiques 14
Application de l’algèbre de Boole (…)
Exemple 3:
A+B+C = A·B·C ?
ELE1300 - Circuits logiques 15
Application de l’algèbre de Boole (…)
Exemple 3:
A+B+C = A·B·C ?
A+B+C = (A+B)+C associativité
= (A+B) · C De Morgan
= ( A·B )·C De Morgan
= A·B·C
ELE1300 - Circuits logiques 16
Preuves de certains théorèmes
Avec la méthode de l’induction parfaite
A A A A A A (idempotence)
A A B A A A B A (loi d’absorption)
A A B A B
A B A B A B A B (loi de De Morgan)
ELE1300 - Circuits logiques 17
Preuve de l’idempotence
A A A A A A
ELE1300 - Circuits logiques 18
Preuve de la loi d’absorption
A A B A A A B A
A A B A B
ELE1300 - Circuits logiques 19
Preuve de la loi de De Morgan
A B A B A B A B
ELE1300 - Circuits logiques 20
Décomposition de Shannon
f (x1, x2, …, xn) = x1 f (0, x2, …, xn)+ x1 f (1, x2, …, xn)
Preuve:
Si x1= 0: x1 f (0, x2, …, xn)+ x1 f (1, x2, …, xn) = f (0, x2, …, xn)
Si x1=1: x1 f (0, x2, …, xn)+ x1 f (1, x2, …, xn) = f (1, x2, …, xn)
En combinant les deux résultats, on trouve que l’assertion est vraie.
ELE1300 - Circuits logiques 21
Décomposition de Shannon (dual)
f (x1, x2, …, xn) = (x1 +f (0, x2, …, xn))(x1+ f (1, x2, …, xn))
Preuve:
Si x1= 0: f (x1, x2, …, xn) = ( 0 +f (0, x2, …, xn))(1 + … = 1)
Si x1=1: f (x1, x2, …, xn) = (1 + … =1) (0 + f (1, x2, …, xn))
ELE1300 - Circuits logiques 22
Table de vérité
Si f i A1 , A2 ,..., An
A1 A2 An 1 An Si
0 0 0 0 1
0 0 0 1 1
0 0 1 0 0
1 1 1 1 1
Un tableau qui illustre la correspondance entre la valeur d’une
fonction logique et la combinaison des valeurs de ses variables
ELE1300 - Circuits logiques 23
Table de vérité (…)
Deux expressions logiques sont égales
ssi leurs tables de vérité sont identiques
Exemple : Loi de DeMorgan
A B A B A B A B
ELE1300 - Circuits logiques 24
Application aux circuits logiques
opération « + » : « OU » opération « · » : « ET »
A B A+B A B A·B
0 0 0 0 0 0
0 1 1 0 1 0
1 0 1 1 0 0
1 1 1 1 1 1
ELE1300 - Circuits logiques 25
L’inverseur
A S
A S
0 1
1 0
SA
ELE1300 - Circuits logiques 26
Différentes représentations
A A
S S
B B
A A
S S
B B
ELE1300 - Circuits logiques 27
Le ET logique
ET A NON-ET A
S S
(« AND ») B (« NAND ») B
S A B ou AB S AB
A B S A B S
0 0 0 0 0 1
0 1 0 0 1 1
1 0 0 1 0 1
1 1 1 1 1 0
ELE1300 - Circuits logiques 28
Le OU logique
OU A NON-OU A
S S
(« OR ») B (« NOR ») B
S A B S A B
A B S A B S
0 0 0 0 0 1
0 1 1 0 1 0
1 0 1 1 0 0
1 1 1 1 1 0
ELE1300 - Circuits logiques 29
Le OU exclusif
OU
A ÉQUIVALENCE A
EXCLUSIF S S
B (« XNOR ») B
(« XOR »)
S A B S A B A B
A B S A B S
0 0 0 0 0 1
0 1 1 0 1 0
1 0 1 1 0 0
1 1 0 1 1 1
ELE1300 - Circuits logiques 30
Le OU exclusif (XOR)
Propriétés et équivalences logiques…
ELE1300 - Circuits logiques 31
Portes aux entrées multiples
A1 A1
A2 S A1 A2 An A2 S A1 A2 An
An An
A1 A1
A2 S A1 A2 An A2 S A1 A2 An
An An
ELE1300 - Circuits logiques 32
Portes aux entrées multiples
A1
A2
S A1 A2 An
An
La sortie d’un XOR est vraie
si et seulement si un nombre impair d’entrées sont vraies
A1
S A1 A2 An
A2
An
La sortie d’un XNOR est fausse
si et seulement si un nombre impair d’entrées sont vraies
ELE1300 - Circuits logiques 33
D’une équation à un circuit
F = (AB+AB)+(AB+AB)
ELE1300 - Circuits logiques 34
Différentes représentations
A A B
B
S
S
A
B
ELE1300 - Circuits logiques 35
D’une équation à un circuit (…)
F = (AB+AB)+(AB+AB)
= AB+(AB+AB)+AB
= AB+AB+AB
= AB+A(B+B)
= AB + A
= A+B
A
F=A+B
B
ELE1300 - Circuits logiques 36
D’un circuit à une équation
A
F
B
C
F = AC+BC
ELE1300 - Circuits logiques 37
Analyse / Synthèse
A1 S1
A2 CIRCUIT S2 Si f i A1 , A2 ,..., An
COMBINATOIRE
An Sm
A1 A2 An 1 An Si
Problématique de la synthèse
ANALYSE 0 0 0 0 1
nombre de puces
0 0 0 1 1
nombre de portes
SYNTHÈSE 0 0 1 0 0
puissance
délais coût
1 1 1 1 1
encombrement fiabilité
ELE1300 - Circuits logiques 38
La forme canonique disjonctive
Ou « somme de produits »
Disjonctive : Forme qui tient compte de S=1
Canonique : Forme d’expression qui représente
A B C S
directement la table de vérité.
0 0 0 0 0 Synonyme : Somme de « mintermes »
1 0 0 1 1
2 0 1 0 0 S ABC ABC ABC ABC ABC
3 0 1 1 1
4 1 0 0 1
5 1 0 1 1
Autre forme :
6 1 1 0 0
S m1 m3 m4 m5 m7
7 1 1 1 1
ou bien S m 1,3, 4,5, 7
ELE1300 - Circuits logiques 39
La forme canonique conjonctive
Ou « produit de sommes »
Conjonctive : Forme qui tient compte de S=0
Synonyme : Produit de « maxtermes »
A B C S
0 0 0 0 0 S ABC ABC ABC
0 0 1 1
ABC ABC
1
S A BC
2 0 1 0 0
0 1 1 1 S A B C A B C A B C
3
4 1 0 0 1
5 1 0 1 1 Autre forme :
6 1 1 0 0
S M 0M 2M 6
7 1 1 1 1
ou bien S M 0, 2, 6
ELE1300 - Circuits logiques 40
Synthèse directe somme-de-produits
S ABC ABC ABC ABC ABC
A
B
C
ELE1300 - Circuits logiques 41
Synthèse directe produit-de-sommes
S A B C A B C A B C
A
B
C
S
ELE1300 - Circuits logiques 42
Simplification de fonctions
S ABC ABC ABC ABC ABC
AC B B AC
AB C C AB
AC B B AC
A A C C
A AB
S AB C B S
C
ELE1300 - Circuits logiques 43
L’additionneur
On peut utiliser cette méthode pour concevoir des additionneurs
Par exemple, A0 + B0 = S[1:0]
A0 B0 S1 S0
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0
1 bit + 1 bit
ELE1300 - Circuits logiques 44
L’additionneur
On peut utiliser cette méthode pour concevoir des additionneurs
Par exemple, A0 + B0 = S[1:0]
A0 B0 S1 S0 A0
B0
0 0 0 0
S0
0 1 0 1 A0
B0
1 0 0 1
A0
1 1 1 0 B0 S1
1 bit + 1 bit
ELE1300 - Circuits logiques 45
Un autre exemple : A[1:0] + B[1:0] = S[3:0]
A1 A0 B1 B0 S3 S2 S1 S0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1
A1 A0 B1 B0
0 0 1 0 0 0 1 0
0 0 1 1 0 0 1 1
0 1 0 0 0 0 0 1
0 1 0 1 0 0 1 0
… … … À refaire pour chaque sortie !
1 1 0 0 0 0 1 1
1 1 0 1 0 1 0 0
1 1 1 0 0 1 0 1
1 1 1 1 0 1 1 0
S0
2 bits + 2 bits
ELE1300 - Circuits logiques 46
Avec des portes NAND
S AB C AB C AB C
A AB
B S
C
B BB C CC
A AB
S
B B
C
C
ELE1300 - Circuits logiques 47
NAND, une porte à tout faire
A B A B AB
A A
B
A B EST ÉQUIVALENT À
B
A B A B
A AA
A A EST ÉQUIVALENT À A AA A
ELE1300 - Circuits logiques 48
NAND = forme disjonctive
S ABC ABC ABC ABC ABC
S ABC ABC ABC ABC ABC
A A
B B
C C
S S
Rappel - Loi DeMorgan :
ELE1300 - Circuits logiques 49
Avec des portes NOR
S AB C où
AB A B
A A B
B S
C
A A A
A
A A B
S
B
ELE1300 - Circuits logiques 50
NOR, une porte à tout faire
AB AB A B
A A
B
AB EST ÉQUIVALENT À
B
A B AB
A A A
A A EST ÉQUIVALENT À A A A A
ELE1300 - Circuits logiques 51
Annonces
• SuperBoole
ELE1300 - Circuits logiques 52