Embed Size (px)
Citation preview
Algèbre de BOOLE
Laurent JEANPIERRE <[email protected]>
D’après le cours de Pascal FOUGERAY
IUT de CAEN – Campus 3
Contenu du cours
Introduction
Portes logiques de base
Propriétés intéressantes
Résolution d’un problème logique
Équivalence entre circuits
Définitions
Algèbre binaire Variables booléennes :
ne prennent que deux valeurs VRAI ou FAUX.
Opérateurs décrits par une table de vérité
Opérateurs réalisés par des portes logiques
George BOOLE (1815-1864)
Contenu du cours
Introduction
Portes logiques de base
Propriétés intéressantes
Résolution d’un problème logique
Équivalence entre circuits
Opération suiveuse (OUI)
Table de Symbole Équationvérité
S = X
X S
0 0
1 1
Table de Symbole Équationvérité
_
S = ¬X = X
Remarque : La barre oblique est utilisée dans tous les symboles pour représenter la fonction de négation
Opération inverseuse (NON)
X S
0 1
1 0
Table de Symbole Équationvérité
S = A.B = A\B = A^B
Opération produit (ET)
A B S
0 0 0
1 0 0
0 1 0
1 1 1
Table de Symbole Équationvérité
S = A+B = A[B = A_B
Opération somme (OU)
A B S
0 0 0
1 0 1
0 1 1
1 1 1
Table de Symbole Équationvérité
___ ____ ____
S = A.B = A\B = A^B
Opération NON-ET (NAND)
A B S
0 0 1
1 0 1
0 1 1
1 1 0
Table de Symbole Équationvérité
____ ____ ____
S = A+B = A[B = A_B
Opération NON-OU (NOR)
A B S
0 0 1
1 0 0
0 1 0
1 1 0
Table de Symbole Équationvérité
S = A⊕B
Opération dilemme (OU exclusif, XOR)
A B S
0 0 0
1 0 1
0 1 1
1 1 0
Table de Symbole Équationvérité
____S = A⊕B
Opération NON OU exclusif (NEXOR)
A B S
0 0 1
1 0 0
0 1 0
1 1 1
Contenu du cours
Introduction
Portes logiques de base
Propriétés intéressantes
Résolution d’un problème logique
Équivalence entre circuits
Propriétés algébriques
Lois ET OU Lois ET OU
Identité 1.A = A 0+A = A Nullité 0.A = 0 1+A = 1
Associativité(A.B).C
=A.(B.C)
(A+B)+C=
A+(B+C)Commutativité A.B = B.A A+B = B+A
Distributivité A.(B+C) = A.B + A.C Idempotence A.A = A A+A = A
InversionAbsorption
(1)A.(A+B) = A A+A.B = A
Absorption
(2)Loi de
De Morgan
Contenu du cours
Introduction
Portes logiques de base
Propriétés intéressantes
Résolution d’un problème logique
Équivalence entre circuits
Les problèmes logiques
1 Problème Plusieurs variables
Expressions possibles : Français Table de vérité Équations Circuits logiques
Exemple : Fonction majorité F(A,B,C) = 1
majorité de 1
Table de vérité
A B C F
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Fonction Majorité (équations)
F = ¬A . B . C + A . ¬B . C + A . B . ¬C + A . B . C
F = A.B + A.C + B.CF = A . (B+C) + B.C…
Table de vérité
A B C F
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Tableaux de Karnaugh
Représentation compacte (non unique) Couramment utilisé pour 3/4 variables Utilise un code de Gray Cherche les regroupements maximaux
FA=0 A=1
B=1 B=0 B=1
C=0D=0
D=1
C=1D=0
F=1
F=¬CF=B
F=D.¬BF=B.¬D
F=C.D.¬BF=B.C.¬A
F=A.B.C.¬D
Contenu du cours
Introduction
Portes logiques de base
Propriétés intéressantes
Résolution d’un problème logique
Équivalence entre circuits
Équivalence de circuits
Il est possible de réaliser toutes les fonctions logiques avec des NAND ou de NOR
Il suffit de remarquer que : ¬(X . X) = ¬X et ¬(X + X) = ¬X ¬¬X = X A+B = ¬¬(A+B) = (¬A NAND ¬B) Loi de De Morgan A . B = ¬¬(A . B) = (¬A NOR ¬B) Loi de De Morgan
Ce principe est utilisé dans les CPLD et les FPGA (voir le cours sur la conception).
Ex : XOR avec des NAND
A⊕B = A.¬B + B.¬A = ¬(¬(A.¬B) . ¬(B.¬A )) A⊕B = (A nand ¬B) nand (B nand ¬A) A⊕B = (A nand (A nand B)) nand
(B nand (A nand B))
Ex : NEXOR avec des NOR
