46
ALGÈBRE DE BOOLE 1 L’algèbre de Boole ou calcul booléen est une ensemble de règles utilisées pour simplifier les expressions logiques sans pour autant changer leur fonctionnalité. C’est la partie des mathématiques qui s'intéresse à une approche algébrique de la logique, vue en termes de variables, d'opérateurs et de fonctions sur les variables logiques. Elle utilise des techniques algébriques pour traiter les expressions à deux, trois ou quatre variables du calcul propositionnel. Elle fut lancée en 1854 par le mathématicien britannique George Boole. Aujourd'hui, l'algèbre de Boole trouve de nombreuses applications en informatique et dans la conception des circuits électroniques. Elle fut utilisée la première fois pour les circuits de commutation téléphoniques par Claude Elwood Shannon. L’algèbre de Boole étant à cheval entre la mathématique, l’electronique et l’informatique, il nous arrive de trouver des notation, des signes différentes, mais qui expriment la même chose.

ALGÈBRE DE BOOLE - unis.sn

  • Upload
    others

  • View
    5

  • Download
    0

Embed Size (px)

Citation preview

Page 1: ALGÈBRE DE BOOLE - unis.sn

ALGÈBRE DE BOOLE

1

L’algèbre de Boole ou calcul booléen est une ensemble de règlesutilisées pour simplifier les expressions logiques sans pour autantchanger leur fonctionnalité.

C’est la partie des mathématiques qui s'intéresse à une approchealgébrique de la logique, vue en termes de variables, d'opérateurset de fonctions sur les variables logiques.

Elle utilise des techniques algébriques pour traiter les expressions àdeux, trois ou quatre variables du calcul propositionnel. Elle futlancée en 1854 par le mathématicien britannique George Boole.

Aujourd'hui, l'algèbre de Boole trouve de nombreuses applicationsen informatique et dans la conception des circuits électroniques.Elle fut utilisée la première fois pour les circuits de commutationtéléphoniques par Claude Elwood Shannon.

L’algèbre de Boole étant à cheval entre la mathématique,l’electronique et l’informatique, il nous arrive de trouver desnotation, des signes différentes, mais qui expriment la mêmechose.

Page 2: ALGÈBRE DE BOOLE - unis.sn

ALGÈBRE DE BOOLE

2

Nous pouvons introduire l’algèbre de Boole à partir de la théorie desEnsembles.

Soit deux ensembles E={a,b,c,d,e} et F={a,b,c}. Nous pouvons dire queF est un-sous ensemble de E. L’ensemble E qui a 5 éléments compte2Card(E) = 25 = 32 sous-ensembles dont lui-même E, appelé ensembleuniversel et un autre sous-ensemble qui ne contient aucun élément,l’ensemble vide.

Parmi les sous-ensembles de E, nous pouvons avoir un autre sous-ensemble G={d,e} qui est le complément de F. L’Union de F et de Gdonne E et l’intersection de F et de G donne l’ensemble vide, étantdonné que ces deux sous-ensembles n’ont aucun élément en commun.

F G = E , F G = ∅ , F=non G , G=non F

Même si d’autres opérations sur les ensembles existent, nous ne nousintéressons que par les 3 opérations que sont l’Union, l’Intersection etle Complément.

Ces trois opérations en algèbre de Boole peuvent être remplacées par laNégation (le Complément), la Multiplication (l’Intersection) et l’Addition(l’Union).

F+G =1 F. G = 0 F = G’ G=F’

Nous pouvons aussi symboliser l’Ensemble universel qui contient tous leséléments par 1 et l’ensemble vide qui ne contient aucun élément par 0.

a b

c d

e

E ={a,b,c,d,e}

a b

a b d

= c d

c e

e

F ={a,b,c,} U G ={d,e} = E ={a,b,c,d,e} E ={a,b,c,d,e}

a b d

=

c e

F ={a,b,c,} G ={d,e} = ∅ E ={a,b,c,d,e}

Page 3: ALGÈBRE DE BOOLE - unis.sn

ALGÈBRE DE BOOLE

3

Propriétés des opérateurs logiques

• Associativité : l’ordre des opérations n’est pas important s’ils ont la même priorité.

(A+B)+C=A+(B+C) = A+B+C

(A.B).C=A.(B.C) = A.B.C

• Commutativité : l’ordre de la variable n’est pasimportant. Commencer la formule par A ou par Brevient au même.

A+B=B+A

A.A=B.A

• Distributivité : Cette loi gère l’ouverture desparenthèses. Pour aller de la distributivité del’addition par rapport à la multiplication vers ladistributivité de la multiplication par rapport àl’addition, il suffit de changer les « . » par les« + » et vise versa.

A(B+C) = AB+AC

A+(BC) = (A+B)(A+C)

• Idempotence : La variable additionnée ou multipliéepar elle garde toujours sa valeur.

A+A+A+A = A

A.A.A.A = A

• L’identité : La variable additionnée par 0 ou multiplié par 1 reste inchangé, identique à elle-même

A+0 =A

A.1=A

. Absorption : A absorbe B et reste A

A+AB =A (A+A)(A+B)=A(A+B)=AA+AB=A(1+B)=A

A.(A+B) =A

AA+AB = A+AB = A(1+B)=A

Page 4: ALGÈBRE DE BOOLE - unis.sn

ALGÈBRE DE BOOLE

4

Propriétés des opérateurs logiques

• Éléments neutres: Une variable multipliée par 0 donne 0 et additionnée par 1 donne 1

A.0 = 0

A+1=1

• La double négation : La négation de la négation donne la variable

A’’ = A

• Simplification A+A’B = A+B

La distributivité donne (A+A’)(A+B) = 1 (A+B) = A+B

A(A’+B) = A.B

La distributivité donne (AA’)+(AB) = 0+ AB + AB

(A+B).(A+B’)= A

La distributivité donne (A+B).(A+B’)= A+BB’=A+0=A

• Redondance A.B+A’.C=A.B + A’C + BC

• Complémentarité: La variable additionnée à son complementdonne 1, multiplé à con complément donne 0

A+A’=1 A.A’=0

Ou Exclusif

AB=A’B+AB’ A’ A=1

AB=AB+(AB)’ A’ 0=A

AB=(AB+A’B’)’ A 1=A’

AB=(A+B).(A’+B’) A’ B’=A B

A A A ….= 0, le nombre de A est pair

A A A ….= A, le nombre de A est impair

A⨀𝐁=(A.B)+(A’B’)

A⨀A=1 A⨀A’=0 A⨀1=A A⨀0= A’

A⨀A⨀A ….= A, le nombre de A est impair

A⨀A⨀A⨀A ….= 1, le nombre de A est pair

ABC = A⨀B⨀C si le nombre des entrées est impair

ABC = (A⨀B⨀C)’ si le nombre des entrées est pair

(AB)’=AB’ = BA’ = A⨀𝐁

Loi de Morgan

𝑨 + 𝑩 + 𝑪 = 𝑨 .𝑩.𝑪

𝑨. 𝑩. 𝑪 = 𝑨 +𝑩 + 𝑪

Page 5: ALGÈBRE DE BOOLE - unis.sn

ALGÈBRE DE BOOLE

5

La loi de Morgan

𝑨 + 𝑩 + 𝑪 = 𝑨 .𝑩.𝑪

𝑨. 𝑩. 𝑪 = 𝑨 +𝑩 + 𝑪

Pour vérifier le premier théorème nous remarquons que si toutes les entrées sont à 1, les deux membres de l'équation sont nuls. Cependant si une au moins des entrées est à 0 les deux membres de l'équation sont égaux à 1. Il y a donc égalité quels que soient les états des diverses entrées.

Le second théorème se vérifie de la même manière : si toutes lesentrées sont à 0 les deux membres de l'équation sont à 1, par contre siau moins une des entrées est à 1 les deux expressions sont à 0.

Les théorèmes de De Morgan montrent qu'une fonction ET peut êtrefabriquée à partir des fonctions OU et NON. De même une fonctionOU peut être obtenue à partir des fonctions ET et NON.

De même, à partir des théorèmes de De Morgan nous pouvonsmontrer qu'une porte ET en logique positive fonctionne comme uneporte OU en logique négative et vice versa.

A

S

B

(A’ + B’)’ = A’’. B’’ = A . B

(A’ . B’)’ = A’’+ B’’ = A + B

Page 6: ALGÈBRE DE BOOLE - unis.sn

ALGÈBRE DE BOOLE

6

Le théorème de redondance ou de consensusPour appliquer le théorème de redondance ou de consensus, il fautréunir les 4 conditions suivantes.

1. La fonction doit avoir 3 variables2. Chaque variable doit être répétée 2 fois en normal ou en

complément3. Une variable doit être complémentée4. Choisir les termes où se trouve la variable complémentée (si 2

variables sont complémentées on choisi la variable qui n’est pascomplémentée)

Soit la fonction logique S = AB+A’C+BC

3 variables A, B, CA est répété 2 fois dans le premier terme et le deuxième termeB est répété 2 fois dans le premier terme et le troisième termeC est répété 2 fois dans le deuxième terme et le troisième terme

La variable complémentée est A S = AB+A’C

le terme redondant BC ayant été enlevé

Démonstration du théorème

S=AB+A’C+BCJe mets un élément neutre 1 au dernier terme

S=AB+A’C+BC.1Je remplace le 1 par A+A’

S=AB+A’C+BC (A+A’)En utilisant la distributivité, j’éclate le troisièmeterne BC (A+A’) qui donne BCA+BCA’

S=AB+A’C+BCA+BCA’

S=AB(1+C)+A’C(1+B)

S=AB+A’C

2 variables sont complémentées on choisila variable qui n’est pas complémentée

(A+B).(A’+C).(B+C) donne (A+B).(A’+C)

A’B’+AC’+B’C’ donne A’B’+AC’ car B et Csont complémentées.

Page 7: ALGÈBRE DE BOOLE - unis.sn

ALGÈBRE DE BOOLE

7

Théorème de la dualitéChaque expression logique possède une expression duale qui est la fonction booléenne obtenue en échangeant les opérateurset les valeurs logiques dans l’expression d’origine. Les 0 sont échangés par des 1, La fonction logique OU est échangées par lafonction logique ET.

Les propriétés des opérateurs booléens peuvent être classées dans leurs formes duales

Opérateur + Opérateur .

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

Communtativité x+y=y+x x.y=y.x

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

Elément neutre x+0=x x+1=1 x.1=x x.0=0

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

Théorème d’idempotence x+x=x x.x=x

Théorème d’involution x’’=x x’’=x

Théorème de Morgan (x+y+z+…)’=x’.y’.z’…… (x.y.z.…)’=x’+y’+z’……

Multiplication et factorisation (x+y).(x’+z)=xz+x’y (x.y)+(x’.z)=(x+z).(x’+y)

Théorème du consensus xy+yz+x’z=xy+x’z (x+y).(y+z).(x’+z)=(x+y).(x’+z)

Page 8: ALGÈBRE DE BOOLE - unis.sn

ALGÈBRE DE BOOLE

8

Les expressions autodualesChaque expression logique possède une expression duale qui est la fonction booléenne obtenue en échangeant les opérateurset les valeurs logiques dans l’expression d’origine. Les 0 sont échangés par des 1, La fonction logique OU est échangées par lafonction logique ET.

Pour toute fonction logique, la duale de la duale renvoie à lafonction.

F=ABC’+A’BC+ABC La fonction duale F’=(A+B+C’).(A’+B+C).(A+B+C)

La duale de la duale donne F’’=F=ABC’+A’BC+ABC =F

Pour certaine fonctions duales, leur dual donne la même fonction, nous disons que ces fonctions sont autoduales

G=AB+BC+AC

G’=(A+B).(B+C).(A+C) La loi de la distributivité, nous donne x+yz = (x+y)(x+z)

G’=(B+AC)(A+C)= BA+BC+AC+AC= BA+BC+AC = G

Le nombre d’expressions logiques autoduales pour n variable =22n-1

Pour une fonction à deux variables le nombre d’expressions duales est égale à 22n-1

= 222-1

=4

Parmi les 16 expréssions 0 1 A A’ B B’ A.B A’.B B’AB’A’ A+B A+B’ A’+B A’+B’ A’B+AB’ A’B+A’B’,

les 4 expressions suivantes sont autoduales A, B, A’ et B’

Page 9: ALGÈBRE DE BOOLE - unis.sn

ALGÈBRE DE BOOLE

9

Les expressions complémentaires

Pour chercher le complément d’une expréssion logique, il faut appliquer la procedure suivantes

• Complémenter les variables

• Remplacer les 0 par les 1 et les 1 par les 0

• Remplacer les opérateur OU (+) par les opérateur ET (.) et les opérateurs ET (.) par les OU (+)

F=A’B+AB’ (fonction XOR) F’=(A+B’)(A’+B) = AA’+AB+B’A’+B’B = AB+A’B’ (Fonction XNOR)

Démonstration par la loi de Morgan

F’=(A’B+AB’)’ . Prenons L= A’B et M=AB’,

nous aurons F’=(L+M)’=L’.M’ = (A’B)’.(AB’)’

F’= (A+B’)(A’+B)= AA’+AB+B’A’+B’B = AB+A’B’ (Fonction XNOR)

G=ABC+A’BC+AB’C

G’= (A’+B’+C’)(A+B’+C’)(A’+B+C’)

Page 10: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

10

Exercice. Vérifiez les équations suivantes

(a’+b)’ = ab’

(ab’)’ = a’+b

((a’(b+c)’)’ = a+b+c

((a’b+(ac)’)’=ac

((ab’)+c’)’=c(a’+b) ou a’c+bc

Quelle est l’expression qui ne

représente pas la porte XNOR

(A) xy+x’y’

(B) x⊕y’

(C) x’⊕y

(D) x’⊕y’

xy+x’y’ = x⊙y (A)

x⊕y’ = xy’’+x’y’= xy+x’y’= x⊙y (B)

x’⊕y = x’’y+x’y’= xy=x’y’= x⊙y (C)

x’⊕y’ =x’’y’+x’y’’=xy’+x’y= x⊕y (D)

Réponse: (D)

x’⊕y’ = x”y’ + x’y” = xy’ + x’y = x⊕y ≠ x⊙y

Page 11: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2Somme des Produits (SOP)

Une fonction canonique peut s’écrire de deuxmanières.

La manière la plus courante est la somme desproduits SOP (Sum Of Products) qui utilise lesminterms.

Pour écrire la fonction canonique de cette table devérité. Il faut considérer les valeurs vraies (1) de lasortie F et faire la somme des produits.

La forme canonique écrite à partir de la table estconsidérée comme la forme standard.

F=x’yz+xy’z+xyz’+xyz

F(x,y,z)= m3+m5+m6+m7

F(x,y,z)= Sm(3,5,6,7)

Cette forme canonique peut être simplifiée pourdonner une forme canonique minimale = xy+yz+zx

Produit des Sommes (POS)

La deuxième façon est le produit des sommes POS

(Product Of Sums) qui utilise les maxterms.

Pour écrire la fonction canonique de cette table de

vérité. Il faut considérer les valeurs fausses (0) de la

sortie F et faire le produit des sommes.

Nous allons mettre x pour x égale 0 et x’ pour x=1

Nous allons mettre y pour y égale 0 et x’ pour x=1

Nous allons mettre z pour z égale 0 et x’ pour x=1

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

F(x,y,z)=M0.M1.M2.M4

F(x,y,z)= PM(0,1,2,4)

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

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

Forme canonique d’une fonction logique

x y z F

m0 0 0 0 0

m1 0 0 1 0

m2 0 1 0 0

m3 0 1 1 1

m4 1 0 0 0

m5 1 0 1 1

m6 1 1 0 1

m7 1 1 1 1

x y z F

M0 0 0 0 0

M1 0 0 1 0

M2 0 1 0 0

M3 0 1 1 1

M4 1 0 0 0

M5 1 0 1 1

M6 1 1 0 1

M7 1 1 1 1

Page 12: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2Somme des Produits (SOP)

F= A’B’C’+ A’BC’+A’BC+ABC’+ABC

F(A,B,C)= m0+m2+m3+m6+m7

F(x,y,z)= Sm(0,2,3,6,7)

Cette forme canonique peut être simplifiée pourdonner une forme canonique minimale.

F= A’B’C’+ A’BC’+A’BC+ABC’+ABC

Nous pouvons factoriser par A’B et AB

F= A’B’C’+ A’B (C’+C)+AB (C’+C)

F= A’B’C’+ A’B +AB

F= A’B’C’+ B(A’ +A)

F= A’B’C’+ B Avec la distributivité

F= B+B’A’C’ = (B+B’).(B+A’C’)= 1.B+A’C’

F= B+A’C’

Produit des Sommes (POS)

F=(A+B+C’). (A’+B+C). (A’+B+C’).

F(A,B,C)=M1.M4.M5

F(A,B,C)= PM(1,4,5)

Cette forme canonique peut être simplifiée

pour donner une forme canonique minimale.

F=(A+B+C’). (A’+B+C). (A’+B+C’)

Nous pouvons factoriser par A’+B

F=(A+B+C’). (A’+B)+(C.C’)

F=(A+B+C’). (A’+B)

F=B+((A+C’).A’) = B+(AA’+C’A’)=B+C’A’

F=B+C’A’ que nous allons mettre en POS

F=(B+C’)(B+A’) = (A’+B)(B+C’)

Nous remarquerons que Y en SOP et Y en

POS donnent le même résultat, F= B+A’C’

Équivalence des deux formes canonique d’une fonction logique

m M A B C Y

m0 M0 0 0 0 1

m1 M1 0 0 1 0

m2 M2 0 1 0 1

m3 M3 0 1 1 1

m4 M4 1 0 0 0

m5 M5 1 0 1 0

m6 M6 1 1 0 1

m7 M7 1 1 1 1

Page 13: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2Pour partir de la forme canonique minimale à la forme canonique standard, il faut faire les étapes suivantes:

1. Identifier les variables

2. Voir les variables manquants dans chaque term

3. Remplacer les variables manquant par l’élément neutre 1.

S=A+B’C

1.Nous avons les 3 variables A, B et C

2. Il manque B et C au premier terme. Il manque A au deuxième terme

S=A.1.1+B’C.1

Le premier 1 du premier terme peut être remplacé par (B+B’) et le deuxième 1 du premier terme par (C+C’)

Le 1 du deuxième terme peut être remplacé par (A+A’)

S=A. (B+B’) . (C+C’)+B’C. (A+A’)(AB+AB’)(C+C’)+B’CA+B’CA’ = ABC+ABC’+AB’C+AB’C’+B’CA+B’CA’ = ABC+ABC’+AB’C+AB’C’+ B’CA’

Pour chaque minterms nous constatons la présence de toutes les variables

De la forme canonique minimal à la Forme canonique standard (SOP)

Page 14: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2Pour partir de la forme canonique minimale à la forme canonique standard, il faut faire les étapes suivantes:

1. Identifier les variables

2. Voir les variables manquants dans chaque term

3. Remplacer les variables manquant par l’élément neutre 0.

S=(A+B+C’).(A’+C)

1.Nous avons les 3 variables A, B et C

2. Toutes les variables sont présentes au premier terme. Il manque B au deuxième terme

S=(A+B+C’).(A’+C+0)

Le premier 0 du deuxième terme peut être remplacé par (B.B’)

S=(A+B+C’).(A’+C+BB’)

Si nous prenons A’+C = X, nous allons avoir S=(A+B+C’).(X+BB’) = (A+B+C’).(X+B)(X+B’)

(A+B+C’).(A’+C+B).(A’+C +B’) Formule très importante: Le nombre d’expressions logiques pour n variable =2

2n

De la forme canonique minimal à la Forme canonique standard (POS)

Page 15: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2La forme canonique produit des sommes d’une fonction logique de n variables peut s’écrire comme suit :

(CNn)2 = (a2n

-1a2n

-2……a2a1a0)2

Comme les nombres sont écrites en binaire, il possible de les convertir en décimal, octal ou hexadécimal pour réduire lalongueur. : (CNn)10 = ∑ ak . 2k . Ce nombre est appelé nombre caractéristiques de la fonction booléenne.

Il est plus facile d’exprimer une fonction booléenne par son nombre caractéristique que de l’exprimer en succession de« 1 ». Nous utiliserons les lettres B, O, D et pour exprimer respectivement la base binaire, octale, décimale ethexadécimal de l’écriture du nombre caractéristiques.

D3= 42 veut dire que le nombre caractéristique de la fonction booléenne à 3 variables est 42 en décimal.

Nous devons pour écrire la forme canonique, convertir 42 en binaire sur 23 (8) positions, ce qui nous donne

(42)10 = (0 0 1 0 1 0 1 0)2

= (a7 a6 a5 a4 a3 a2 a1 a°) 2

= (a1, a3 , a5) =

F = x’y’z+x’yz+xy’z = z(x’y’+x’y+xy’) = z(x’(y+y’)+xy’) = z(x’+xy’) = z(x’+y’) = zx’+zy’

H2 = E, nous avons une fonction booléenne à deux variable x et y exprimé en hexadécimale. E donne en binaire (1 1 1 0)

F = (a3 a2 a1 a°) 2 = (a1, a2 , a3) = F’= a0 = x’y’ = (x+y)’ donnant F= x+y

Nombre caractéristique d’une expression logique

Page 16: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2Connaissant une fonction booléenne, nous pouvons chercher son nombre caractéristique.

F(x,y,z) = zy+z’x

Nous allons faire la table de vérité et évaluer la fonction F(x,y,z) = zy+z’x

F = (a7 a6 a5 a4 a3 a2 a1 a°) 2

( 1 1 0 0 1 0 1 0 ) qui donne D3 = 202 et H3 = CA

Une autre possibilité de traiter le problème est de passer de la forme canonique minimale à la forme canonique standardou fondamentale

Nombre caractéristique d’une expression logique

minterms x y z F= yz+xz'

m0 0 0 0 0

m1 0 0 1 1

m2 0 1 0 0

m3 0 1 1 1

m4 1 0 0 0

m5 1 0 1 0

m6 1 1 0 1

m7 1 1 1 1

Page 17: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2La forme canonique minimale de la fonction S=A+B’C. Combien de mintermes comptent sa forme canonique logique

1. Nous avons les 3 variables A, B et C

2. Seule la variable A est présente au premier minterme et les variables B et C au deuxième minterme.

Nous allons compléter le premier minterm en y ajoutant les deux variables B et C manquants et le deuxième minterme en y ajoutant la variable A manquante. Ces variables seront remplacées par des 1.

Nous aurons S=A.1.1+B’C.1 = A.(B+B’).(C+C’)+B’C(A+A’)

S=A.1.1+B’C.1 = A.(B+B’).(C+C’)+B’C(A+A’) = (AB+AB’).(C+C’)+B’CA+B’CA’ = ABC+ABC’+AB’C+AB’C’+B’CA+B’CA’

S=ABC+ABC’+AB’C+AB’C’+B’CA’

La forme canonique standard compte 5 mintermes

Combien d’expression logiques pouvons nous avoir avec deux variables A et B. Généralisez cette formule pour n variables.

A+0=A A’+0=A’ B+0=B B’+0=B’ A.A’=B.B’=0 A.B A’.B B’A B’A’

A+1=B+1=A’+1=B’+1=1 A+B A+B’ A’+B A’+B’ A’B+AB’ A’B+A’B’

Nous pouvons avoir 16 expressions logiques

Formule très importante: Le nombre d’expressions logiques pour n variable =22n

Avec 3 variables nous pouvons avoir 223

= 256 et avec 4 variables avoir 224

= 256 x256= 65 536 expressions logiques

Exercices

Page 18: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

18

Simplification des fonctions logiques

Simplifier une expression booléenne c'est lui trouver une formeplus condensée, faisant intervenir moins d'opérateurs etconduisant à une réalisation matérielle plus compacte.

On peut simplifier une fonction logique par les quatre méthodessuivantes:

• La manipulation analytique ou algébrique• La méthodes des consensus ou de redondance• La représentation graphique de Karnaugh• La méthode tabulaire de Quine-Mc Clauskey

Simplification algébriquePour utiliser la méthode algébrique, il faut maitriser les identitésremarquables sur les propriétés des fonctions logiques dont lesplus utilisés sont:

A.(B+C)=AB+AC A+(BC) = (A+B).(A+C)

A+AB = A A.(A+B) = A

(A+B).(A+B’) = A A+A’B = A+B

A+A’=1 AA’=0 A+1=1 A.1=A A+0=A

AAA=A A+A+A=A

Page 19: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

19

x y z 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

F=x'yz+xy'z+xyz'+xyzF=x'yz+xzy'+xyz'+xyzSachant que A+A+A..=ANous allons ajouter deux mintermescomportant xz et xyF=x'yz+xzy'+xyz'+xyz+xzy+xyzF=yz(x+x') +xz(y'+y) +xy (z’+z)F=yz+xz+xy

Page 20: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

20

Exercices Simplifiez les équations booléennes suivantes :

a+abc = a(1+bc) = a

a[b(a+b)] = a[ba+bb] = a(ba+b) = a(b(1+a)) = ab

(a’+b)+ab = a’+b+ab = a’+b(1+a) = a’b

(a+b’+c)+ab’+c = a+b’+c+ab’+c = a+b’+ab’+c = a+b’(1+a)+c = a+b’+c

(ab+bc)(ac+bc) = abac+abbc+bcac+bcbc = abc+abc+abc+bc = abc+bc = bc(a+1)=bc

x’yz+xy’z+xyz’+xyz Etant donné que a+a=a nous pouvons augmenter deux xyz.

Nous aurons x’yz+xy’z+xyz’+xyz+xyz+xyz = yz(x+x’)+xz(y+y’)+xy(z+z’) = yz+xz+xy

x+x’y Pour simplifier cette équation, nous allons utiliser la deuxième loi de la distributivité que nous ne trouvons pas en algèbre classique : a+bc = (a+b)(a+c)

ainsi x+x’y va donner (x+x’)(x+y) = x+y

x’y’z+x’yz+xy’ = x’z(y’+y)+xy’=x’z+xy’

Page 21: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

21

Simplification par la méthode de redondance ou de consensus

Nous voulons par cette méthode vérifier que

AB+A’C+BC=AB+A’C

Pour utiliser cette méthode, il faut suivre les étapes suivantes:

• La fonction doit avoir 3 variables

• Chaque variable doit être répétée deux fois soit en mode normale ou complémenté

• Une des variable doit être complémentée

• Prendre la seule variable complémentée ou la seule variable non complémentée.

AB+A’C+BCNous avons trois variables A, B et C

A, B et C sont répétés deux fois

La variable A est complémentée au niveau du deuxièmeminterm. Nous prenons les minterms ou se trouve lavariable complémentée, ce qui nous donne AB+A’C

Démonstration

AB+A’C+BC=AB+A’C+BC.1

AB+A’C+BC=AB+A’C+BC(A+A’)

AB+A’C+BC=AB+A’C+BCA+BCA’)

AB(1+C)+A’C(1+B) = AB+AC’

A’B’+AC’+B’C’ donne A’B’+AC’. Cette fois-ci, nous allons prendre la variable non complémentée, car les deux autres variables sont complémentées.

Page 22: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

22

Simplification par la méthode de Karnaugh

• les cases constituant un bloc doivent être adjacentes.

• les blocs doivent être de forme rectangulaire.

• le nombre de cases d'un bloc doit être une puissance de 2.

• les blocs devront contenir le plus de cases possibles (tout en respectant bien sûr les contraintes ci-dessus).

• les blocs peuvent se chevaucher.

Page 23: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

23

La méthode de Karnaugh est basée sur l’inspection visuellede tableaux disposés de façon à ce que deux casesadjacentes en ligne et en colonne ne différent que par l’étatd’une variable et d’une seule.

Si une fonction dépend de n variables, il y a 2n possibilités deproduits. Chacun de ces produits est représenté par une casedans un tableau.

Il suffit de bien observer comment les tableaux sontnumérotés. D’une case à sa voisine, une seule variablechange d’état.

La méthode de Karnaugh est basée sur l’application du théorème d’unification suivant:

AB + Aഥ𝐁 = A (B+ ഥ𝐁 ) = A

F(A,B,C,D)=G(A,C,D).B+G(A,C,D).B’ = G(A,C,D)

Pour simplifier par la méthode de Karnaugh, nous allons observer le étapessuivantes:

• Remplir la tables de vérité

• Faire l’équation canonique

• Dessiner le tableau de Karnaugh

• Remplir les cases du tableau de Karnaugh

• Regrouper les cellules adjacentes

• Simplifier les regroupements

• Retenir l’équation finale

Les combinaisons sont placées dans l’ordre du codagebinaire réfléchi (codage Gray) afin que les produitsadjacents se trouvent dans des cases voisines ou dans lescases extrêmes.

On peut alors faire des regroupements de 2, 4, 8, 16 etc.

Pour 5 variables, deux représentations sont possibles. Letableau de Karnaugh peut être traité comme deux tableaux4x4 superposés ou un seul tableau de 4x8.

Il est important d’observez la façon dont les tableaux sontnumérotées en lignes et en colonnes.

D'une case à sa voisine une seule variable change d'état.

Le passage de la table de vérité au tableau de Karnaughconsiste à remplir chaque case avec leur valeur de lafonction pour le produit correspondant. Pour ne pasencombrer le tableau, il ne faut mettre que les 1.

La simplification consiste à rassembler les casesadjacentes contenant des « 1 »par groupe de 2, 4, 8 ou 16,ensuite les factoriser.

Le tableau de Karnaugh peut aussi être utilisée poursimplifier une équation canonique POS, dans ce cas cesont les « 0 » que nous allons regrouper.

Simplification par la méthode de Karnaugh

Page 24: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

24

A B A B A B A B 0 0 0 1 1 1 1 0

m0 m1 m3 m2 m0 m1 m3 m2

A B A A A B 0 1

B m0 m1 0 m0 m1

B m2 m3 1 m2 m3

Tableau à deux variables

Le tableau à deux variables,

n=2, comporte 2n cases , 22= 4

Ce tableau donne :

Une seule possibilité de

regrouper 4 cellules adjacents

{m0, m1,m2,m3}

Quatre possibités de regrouper

deux cellules adjacents

{m0,m1}, {m2,m3}, {m0,m2},{m1,m3}

Page 25: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

25

A B C A B A B A B A B

C m0 m1 m3 m2

C m4 m5 m7 m6

A B C 00 01 11 10

0 m0 m1 m3 m2

1 m4 m5 m7 m6

Le tableau à trois variables, n=3 comporte 2n

cases , 23= 8

Ce tableau donne :

une seule possibilité de regrouper 8 cellules (

mintermes) adjacents

{m0, m1, m3, m2, m4, m5, m7, m6},

Six possibilités de regrouper 4 cellules

(mintermes) adjacents

{m0, m1, m3, m2}, {m4, m5, m7, m6},

{m0, m1, m4, m5}, {m1, m3, m5, m7},

{m3, m2, m7, m6}, {m2, m0, m6, m4},

Douze possibilités de regrouper 2 cellules

(mintermes) adjacents : {m0,m1), {m1,m3),

{m3,m2), {m2,m0), {m4,m5), {m5,m7),

{m7,m6), {m6,m4), {m0,m4), {m1,m5),

{m3,m7), {m2,m6),

Tableau à trois variables

Page 26: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

26

Exercices

Quelles sont les combinaisons de mintermespeuvent remplacer la function suivante :f(P, Q, R) = PQ + QR’ + PR’

(A) m2 + m4 + m6 + m7(B) m0 + m1 + m3 + m5(C) m0 + m1 + m6 + m7(D) m2 + m3 + m4 + m5

Réponse A:

Il faut faire la table de verité de chercher f

Tableau à trois variables minterm

s P Q R PQ QR' PR' F

m0 0 0 0 0 0 0m1 0 0 1 0 0 0m2 0 1 0 0 1 0 1m3 0 1 1 0 0 0m4 1 0 0 0 0 1 1m5 1 0 1 0 0 0m6 1 1 0 1 1 1 1m7 1 1 1 1 0 0 1

P QR Q'R' Q'R QR QR'

P' m0 m1 m3 m2 1

P m4 1 m5 m6 1 m7 1

PR'+PQ+QR'

Page 27: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

27

Exercices

Soit f1 = ∑𝑚 (4,5,6,7,8)Soit f3 = ∑𝑚 (1,6,15)Soit f = ∑𝑚 (1,6,8,15)

Trouvez f2

A = ∑𝑚 4,6B = ∑𝑚 (4,8)C = ∑𝑚 (6,8)D = ∑𝑚 (4,6,8)

Réponse C.

minterms f1 f2 f3 f

m0 0 0 0 0

m1 0 X 1 1

m2 0 X 0 0

m3 0 X 0 0

m4 1 0 0 0

m5 1 0 0 0

m6 1 X 1 1

m7 1 0 0 0

m8 1 1 0 1

m9 0 X 0 0

m10 0 X 0 0

m11 0 X 0 0

m12 0 X 0 0

m13 0 X 0 0

m14 0 X 0 0

m15 0 X 1 1

f

f1

f3

f2

Page 28: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

28

Soit l’expression booléenne suivante:

F(P,Q,R,S)= PQ + P'QR + P'QR’S

Trouver la forme canonique POS minimale

(A) PQ + QR + QS

(B) P + Q + R + S

(C) P’ + Q’ + R’ + S’

(D) P’R + P’R’S + P

Réponse : (A)

DémonstrationF(P, Q, R, S) = PQ + P'QR + P'QR'S =

PQ + P'QR + P'QR'S =

Q(P+P'R + P'R'S) =

Q(P+R + R'S) = Q(P+ R+R'S) = Q(P+R+S) =

Q(P+R + S) =

PQ + QR + QS

A noter que A+AB=A et A+A’B = A+B.

Page 29: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

29

Tableau à quatre variables

.

A B C D A B A B A B A B

C D m0 m1 m3 m2

C D m4 m5 m7 m6

C D m12 m13 m15 m14

C D m8 m9 m11 m10

A B C D 00 01 11 10

00 m0 m1 m3 m2

01 m4 m5 m7 m6

11 m12 m13 m15 m14

10 m8 m9 m11 m10

Le tableau à quatre variables, n=4 comporte 2n cases ,

24= 16

Ce tableau donne :

une seule possibilité de regrouper 16 cellules (

mintermes) adjacents

{m0, m1, m3, m2, m4, m5, m7, m6, m8, m9, m10, m11,

m12, m13, m14, m15}

8 possibilités de regrouper 8 cellules (mintermes)

adjacents

{m0, m1, m3, m2, m4, m5, m7, m6},

{m0, m1, m3, m2, m8, m9, m11, m10},

{m4, m5, m7, m6, m12, m13, m15, m14},

{m8, m9, m10 m11, m12, m13, m15, m14},

{m0, m4, m12 m8, m1, m5, m13, m9},

{m0, m4, m12 m8, m2, m6, m14, m10},

{m3, m7, m15 m11, m1, m5, m13, m9},

{m3, m7, m15 m15, m2, m6, m14, m10},

32 possibilités de regrouper 2 mintermes adjacents :

{m0,m1), {m0,m4), {m0,m2), {m0,m8),

{m1,m3}, {m1,m5}, {m1,m9},

{m3,m2}, {m3,m7}, {m3,m11},

{m2,m6}, {m2,m10},

{m4,m5}, {m4,m6}, {m4,m12}

{m5,m7}, {m5,m13}

{m7,m6],{m7,m15)

{m6,m14)

{m12,m8},{m12,m13},{m12,m14}

{m13,m15},{m13,m9}

{m15,m14},{m15,m11}

{m14,m10}

{m8,m9},{m8,m10}

{m9,m11}

{m11,m10}

Page 30: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

30

Tableau à quatre variables ( n=4, 2n cases = 16)

F(A,B,C,D)= Sm(0,2,3,7,11,13,14,15)

F = I + II + III + IV

F= AB + ഥ𝐁 ҧ𝐂 ഥ𝐃+ ACD+ BCD

NB. un impliquant de 2 « 1 » vous débarrassez d’une variableun impliquant de 4 « 1 » vous débarrassez de 2 variablesun impliquant de 8 « 1 » vous débarrassez de 3 variablesun impliquant de 16 « 1 » vous débarrassez de 4 variables

ABCD ഥ𝑨 ഥ𝐁 ഥ𝑨 B AB Aഥ𝐁

ത𝐂 ഥ𝐃 1 1 1

ത𝐂 D 1

C D 1 1 1

C ഥ𝐃 1

I

IIIIV

II

Tableau à quatre variables ( n=4, 2n cases = 16)

F(A,B,C,D)= Sm(0,2,3,5,7,8,11,14,15)

F = I + II + III + IV

F= AB + ഥ𝐁 ഥ𝐃 + AC+ B ҧ𝐂 D

NB. un impliquant de 2 « 1 » vous débarrassez d’une variableun impliquant de 4 « 1 » vous débarrassez de 2 variablesun impliquant de 8 « 1 » vous débarrassez de 3 variablesun impliquant de 16 « 1 » vous débarrassez de 4 variables

ABCD ഥ𝑨 ഥ𝐁 ഥ𝑨 B AB Aഥ𝐁

ത𝐂 ഥ𝐃 1 1 1

ത𝐂 D 1 1

C D 1 1

C ഥ𝐃 1 1 1

I

II

III

IV

Page 31: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

31

Tableau à 5 variables (n=5, 2n cases = 32 cases)

Pour résoudre ce problème on va le décomposer en 2tableaux à 4 variables en appliquant le théorèmed’expansion (SHANNON).

F(A,B,C,D,E)=E’.F(A,B,C,D,0)+ E.F(A,B,C,D,1)

Même si l’utilisation de la méthode de Karnaugh au-delà 5 variable devient onéreux, le théorèmed’expansion de SHANNON reste applicable quelque soitle nombre de variables.

F(A,B,C, … ,Z)=Z’.F(A,B,C, … ,0)+ Z.F(A,B,C, … ,1)

Essayons de simplifier la fonction

F(A,B,C,D,E)=Sm(4, 5, 6, 7, 24, 25, 26, 27)

F=C'DE'+CD’E ou A’BE’+AB’E

F=A'BE'+AB'E

F(A,B,C,D,E)=∑m(4, 5, 6, 7, 24, 25, 26, 27)

E

E'

AB'E

A'BE'

A'B' m0 m1 m3 m2

ABCD C'D' C'D CD CD'

A'B

AB'

A'B m4 1 m5 1 m7 1 m6 1AB m12 m13 m15 m14

AB' m8 m9 m11 m10

C'D' C'D CD CD'

A'B' m16 m17 m19 m18

ABCD

AB m28 m29 m31 m30

m241 m251 m271 m261

m20 m21 m23 m22

F=C'DE'+CD'E

E

E'

CD'E

C'DE'

A'B' m0 m4 m12 m8

ABCD C'D' C'D CD CD'

A'B

AB'

A'B m1 m5 m13 m9

AB m3 m7 m15 m11

AB' m2 m6 m14 m10

C'D' C'D CD CD'

A'B' m16 m20 m28 m24

ABCD

AB m19 m23 m31 m27

m18 m22 m30 m26

m17 m21 m29 m25

Page 32: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

32

E EA B C D A B A B A B A B A B C D A B A B A B A B

C D m0 m1 m3 m2 C D m0 m1 m3 m2

C D m4 m5 m7 m6 C D m4 m5 m7 m6

C D m12 m13 m15 m14 C D m12 m13 m15 m14

C D m8 m9 m11 m10 C D m8 m9 m11 m10

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

00 m0 m1 m3 m2 00 m0 m1 m3 m2

01 m4 m5 m7 m6 01 m4 m5 m7 m6

11 m12 m13 m15 m14 11 m12 m13 m15 m14

10 m8 m9 m11 m10 10 m8 m9 m11 m10

Tableau à 5 variables ( n=5, 2n cases = 32 cases)

Le tableau à quatre variables, n=5 comporte 2n cases , 25= 32

Ce tableau donne une seule possibilité de regrouper 32 cellules (

mintermes) adjacents

{m0, m1, m3, m2, m4, m5, m7, m6, m8, m9, m10, m11, m12, m13, m14,

m15, m16, m17, m18, m19, m20, m21, m23, m22, m28, m29, m31, m30,

m24, m25, m27, m26}

2 possibilités de regrouper 16 cellules (mintermes) adjacents

{m0, m1, m3, m2, m4, m5, m7, m6, m8, m9, m10, m11, m12, m13, m14, m15}

{m16 m17, m18, m19, m20, m21, m23, m22, m28, m29, m31, m30, m24, m25,

m27, m26}

{m0, m1, m3, m2, m4, m5, m7, m6},

{m0, m1, m3, m2, m8, m9, m11, m10},

{m4, m5, m7, m6, m12, m13, m15, m14},

{m8, m9, m10 m11, m12, m13, m15, m14},

{m0, m4, m12 m8, m1, m5, m13, m9},

{m0, m4, m12 m8, m2, m6, m14, m10},

{m3, m7, m15 m11, m1, m5, m13, m9},

{m3, m7, m15 m15, m2, m6, m14, m10},

32 possibilités de regrouper 2 cellules (mintermes) adjacents : {m0,m1), {m0,m4),

{m0,m2), {m0,m8),

{m1,m3}, {m1,m5}, {m1,m9},

{m3,m2}, {m3,m7}, {m3,m11},

{m2,m6}, {m2,m10},

Page 33: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

33

Tableau à 5 variables ( n=5, 2n cases = 32 cases) m A B C D E F0 0 0 0 0 0 11 0 0 0 0 1 02 0 0 0 1 0 13 0 0 0 1 1 14 0 0 1 0 0 05 0 0 1 0 1 16 0 0 1 1 0 07 0 0 1 1 1 18 0 1 0 0 0 19 0 1 0 0 1 010 0 1 0 1 0 111 0 1 0 1 1 112 0 1 1 0 0 013 0 1 1 0 1 014 0 1 1 1 0 115 0 1 1 1 1 10 1 0 0 0 0 11 1 0 0 0 1 02 1 0 0 1 0 13 1 0 0 1 1 04 1 0 1 0 0 05 1 0 1 0 1 06 1 0 1 1 0 07 1 0 1 1 1 08 1 1 0 0 0 19 1 1 0 0 1 010 1 1 0 1 0 111 1 1 0 1 1 112 1 1 1 0 0 013 1 1 1 0 1 114 1 1 1 1 0 115 1 1 1 1 1 1

ABC

DE

F=1+2+3+4+5

F=C'E'+BD+A'DE+A'B'CE+ABCE

A

A'

13 1 15 1 14 1

9 11 1 1 1

1 3 2 1

5 7 6

13 15 1 14 1

9 11 1 10 1

1 3 1 2 1

5 1 7 1 6

B C

BC'

0 1

4

12

8 1

0 1

4

12

8 1

B'C'

B'C

B C

BC'

B'C'

B'C

D'E' D'E DE DE'

A'

A

DE D'E' D'E DE DE'BC

B C 28 29 1 31 1 30 1

BC' 24 1 25 27 1 26 1

18 1

B'C 20 21 23 22

BC' 8 1 9 11 1 10 1

B'C' 16 1 17 19

7 1 6

B C 12 13 15 1 14 1

DE'

B'C' 0 1 1 3 1 2 1

B'C 4 5 1

BC DE D'E' D'E DE

Page 34: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

34

Tableau à 5 variables ( n=5, 2n cases = 32 cases)

m A B C D E F

0 0 0 0 0 0 1

1 0 0 0 0 1 0

2 0 0 0 1 0 1

3 0 0 0 1 1 1

4 0 0 1 0 0 0

5 0 0 1 0 1 1

6 0 0 1 1 0 0

7 0 0 1 1 1 1

8 0 1 0 0 0 1

9 0 1 0 0 1 0

10 0 1 0 1 0 1

11 0 1 0 1 1 1

12 0 1 1 0 0 0

13 0 1 1 0 1 0

14 0 1 1 1 0 1

15 0 1 1 1 1 1

16 1 0 0 0 0 1

17 1 0 0 0 1 0

18 1 0 0 1 0 1

19 1 0 0 1 1 0

20 1 0 1 0 0 0

21 1 0 1 0 1 0

22 1 0 1 1 0 0

23 1 0 1 1 1 0

24 1 1 0 0 0 1

25 1 1 0 0 1 0

26 1 1 0 1 0 1

27 1 1 0 1 1 1

28 1 1 1 0 0 0

29 1 1 1 0 1 1

30 1 1 1 1 0 1

31 1 1 1 1 1 1

Nous pouvons aussi regrouper 3,2,10,11à la place de 3,7,11,15

ABC

DE

F=1+2+3+4+5

F=C'E'+BD+A'C'D+A'B'CE+ABCE

A

A'

29 1 31 1 30 1

25 27 1 26 1

17 19 18 1

21 23 22

13 15 1 14 1

9 11 1 10 1

1 3 1 2 1

5 1 7 1 6

B C

BC'

0 1

4

12

8 1

16 1

20

28

24 1

B'C'

B'C

B C

BC'

B'C'

B'C

D'E' D'E DE DE'

Nous pouvons aussi regrouper 3,2,10,11à la place de 3,7,11,15

ABC

DE

F=1+2+3+4+5

F=C'E'+BD+A'C'D+A'B'CE+ABCE

A

A'

29 1 31 1 30 1

25 27 1 26 1

17 19 18 1

21 23 22

13 15 1 14 1

9 11 1 10 1

1 3 1 2 1

5 1 7 1 6

B C

BC'

0 1

4

12

8 1

16 1

20

28

24 1

B'C'

B'C

B C

BC'

B'C'

B'C

D'E' D'E DE DE'

A'

A

DE D'E' D'E DE DE'BC

B C 28 29 1 31 1 30 1

BC' 24 1 25 27 1 26 1

18 1

B'C 20 21 23 22

BC' 8 1 9 11 1 10 1

B'C' 16 1 17 19

7 1 6

B C 12 13 15 1 14 1

DE'

B'C' 0 1 1 3 1 2 1

B'C 4 5 1

BC DE D'E' D'E DE

Page 35: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

35

Tableau à 6 variables ( n=6, 2n cases = 64 cases)

Pour résoudre ce problème on va le décomposer en 4tableaux à 4 variables en appliquant le théorèmed’expansion (SHANNON).

F(A,B,C,D,E)=E’.F(A,B,C,D,0)+ E.F(A,B,C,D,1)

Il est à noter que les 4 tableaux superposent et se plient.

Si nous prenons la cellule m0, celles qui lui sontadjacentes sont : m1, m2, m4, m8 dans le premiertableau (A=0,B=0), mais aussi m16, m17, m18, m24 dansle tableau 2 (A=0,B=1), m48, m49, m50, m56 dans letables 3 (A=1, B=1) et m32, m33, m34, m40 du tableau 4(A=1, B=0).

Nous pouvons alors faire un regroupement de 16 pourm4, m5, m7, m6, m20, m21, m23, m22, m52, m53, m55,m54, m36, m37, m39 et m38 ce qui nous donne C’D.

Nous avons aussi un regroupement de 8 pour m5, m7,m13, m15, m21, m23, m29 et m31 qui ont en communA=0 et FD, ce qui nous donne A’FD

A=0 B=0

A=0 B=1

A=1 B=1

A=1 B=0

E'

EFCD C'D' C'D CD CD'

E'F' m0 m4 1 m12 m8 1

E'F m1 m5 1 m13 1 m9

EF m3 m7 1 m15 1 m11

EF' m2 m6 1 m14 m10 1

CD'

E'F' m16 m20 1 m28 m24

E

EFCD C'D' C'D CD

EF' m18 1 m22 1 m30 1 m26 1

EFCD

E'F m17 m21 1 m29 1 m25

EF m19 m23 1 m31 1 m27

C'D' C'D CD CD'

E'F' m48 m52 1 m60 1 m56

m44 m40 1

EF' m50 m54 1 m62 m58

EFCD

E'F m49 1 m53 1 m61 1 m57

EF m51 m55 1 m63 m59

EF' m34 m38 1 m46 m42 1

F(A,B,C,D,E)=∑m(4, 5, 6, 7, 8, 10,13,15,18,20, 21, 22, 23, 26, 29, 30, 31, 33, 36, 37, 38, 39, 40, 42, 49, 52, 53, 54, 55, 60, 61)

C'D+A'DF+B'CD'F'+A'BEF'+AC'E'F+ABDE'

E'F m33 1 m37 1 m45 m41

EF m35 m39 1 m47 m43

C'D' C'D CD CD'

E'F' m32 m36 1

Page 36: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

36

Les don’t care dans Karnaugh F(A, B, C)= Sm(2,3,4,5) +Sd(6,7)

F = I + II

F = A+C

Remplacer les don’t care par des 1 dans SOP

Remplacer les don’t care par des 0 dans POS

I

II

ABC ഥ𝐀 ഥ𝐁 ഥ𝐀 B AB Aഥ𝐁

ത𝐂 1 1

C 1 1 X X

Page 37: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

37

Karnaugh utilisant les maxtermsF(A,B,C)= Sm(2,3,4,5) +Sm(6,7)

F’ = I + II

F’= A’C’+BC’

F’’= (A’C’+BC’)’ = (A’C’)’.(BC’)’ = (A+C)(B’+C) = C+AB’

III

ABC A’B’ A’B AB AB’

C’ 0 0 0 1

C 1 1 1 1

Karnaugh utilisant les mintermsF(A,B,C)= Sm(2,3,4,5) +Sm(6,7)

F’ = I + II

F’= C+AB’

ABC A’B’ A’B AB AB’

C’ 0 0 0 1

C 1 1 1 1

Page 38: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

rD2

38

ABCD ഥ𝐀 ഥ𝐁 ഥ𝐀 B AB Aഥ𝐁

ത𝐂 ഥ𝐃0 1 1

3 1 2

ത𝐂 D 45 1 7

6 1

C D 12 1 1315 1 14

C ഥ𝐃 89 1 11

10 1

A'B'C'D'+A'B'CD+A'BC'D+A'BCD'+ABC'D'+ABCD+AB'C'D+AB'CD'

Je factorise par D’ et D après avoir regroupé tous les termes qui ont D’ d’un coté et tous

les termes qui ont D de l’autre.

=(A'B'C'D'+A'BCD'+ABC'D'+AB'CD')+(A'B'CD+A'BC'D+ABCD+AB'C'D)

=D'(A'B'C'+A'BC+ABC'+AB'C)+D(A'B'C+A'BC'+ABC+AB'C')

A l’intérieur des facteurs de D’ et D, je factorise par C’ et C en regroupant tous les termes

qui ont C’ d’un côté et tous les termes qui ont C de l’autre.

=D'(C'[A'B'+AB]+C[A'B+AB'])+D(C[A'B'+AB]+C'[A'B+AB'])

Sachant que A'B+AB'=AxorB et que A'B' + AB= A xnor B, nous aurons :

=D'(C'[A xnor B]+C[A xor B]) + D(C[A xnor B]+C'[A xor B])

Sachant que xnor = ( xor )', je remplace [A xnor B] par [A xor B]’

=D'(C'[A xor B]'+C[A xor B]) + D(C[A xor B]'+C'[A xor B])

=D'([A xor B] xnor C)+ D([A xor B] xor C)

=D' [A xor B xor C ]' + D[A xor B xor C]

=A xor B xor C xnor D

Si dans un tableau de Karnaugh,

nous voyons que les 1 se présentent

sous la configuration d’un jeu

d’échec, l’équation finale donne

f(A,B,C,D) =A ⊕ B ⊕ C ⊕ D

Démonstration de la configuration d’échec dans un tableau de Karnaugh

Page 39: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

39

Les impliquantsLes impliquants dans le diagramme de Karnaugh

Un impliquant est un groupe de «1» regroupé par 1,2, 4, 8, 16, 32 ..

Nous voyons qu’un «1» isolé est considéré commeun impliquant, car nous allons l’utiliser pour établirune expression.

Un prime impliquant (PI) est le groupe le plusimportant obtenu dans un tableau de Karnaugh.

Un prime impliquant essentiel (EPI) et un primeimpliquant qui a en son sein un «1» qu’on ne peutcombiner que d’une seule façon.

Les impliquants qui se trouvent aux extrémités sontdes EPI (Essential Prime Impliquant), car un des« 1 », celui d’en haut, qu’ils renferment ne peuventpas être combinés autrement.

L’impliquant qui est au milieu est un PI, mais pas unEPI, car les «1» qui le composent peuvent êtrecombinés de deux façons différentes.

ABCD A’B’ A’B AB AB’

C’D’ 1

C’D 1 1

CD 1 1

CD’ 1

Page 40: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

40

Au delà de 3 ou 4 variable la simplificationalgébrique devient difficile, il faut donc utiliserla méthode de Karnaugh qui peu nous aider àsimplifier jusqu’à 5 variables. Pour simplifierune fonction de plus de 5 variables, nousfaisons appel à la méthode tabulaire de Quine-Mc Clauskey.

Soit une fonction S=Sm(0,1,3,7,8,9,11,15)

1. Nous allons faire un table des valeursbinaires des mintermes.

2. Nous allons dresser un tableau de 3colonnes où nous allons regrouper lesmintermes qui comptent le même nombrede «1», (m0), (m1, m8), (m3, m9),(m7,m11),(m15)

3. Nous allons ensuite faire un autre tableau,toujours avec 3 colonnes en comparant lestableaux n par les n+1. Nous allonsregrouper (match), les mintermes qui nesont différents que d’une collonne.

Minterm ABCD

0 0000

1 0001

3 0011

7 0111

8 1000

9 1001

11 1011

15 1111

Simplification par la méthode de Quine-Mc Clauskey

Groupe MintermsABCD

0 m0 0000

1m1 0001

m8 1000

2m3 0011

m9 1001

3m7 0111

m11 1011

4 m15 1111

Groupe MintermsABCD

0 m0 0000

1m1 0001

m8 1000

2m3 0011

m9 1001

3m7 0111

m11 1011

4 m15 1111

4. Nous allons ensuite faireun autre tableau pourmatérialiser les comparaisonde m0 avec m1 et m8, lescomparaisons de m1,m8avec m3,m9, lescomparaison de m3,m9 avecm7,m11, les comparaison dem7,m11 avec m15

Groupe Match Pairs ABCD

0m0-m1 000-

m0-m8 -000

1m1-m3 00-1

m1-m9 -001

m8-m9 100-

2m3-m7 0-11

m3-m11 -011

m9-m11 10-1

3m7-m15 -111

m11-m15 1-11

Page 41: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

41

5. Nous allons ensuite faire la comparaisonm0-m1 et m0-m8 avec m1-m3, m1-m9,m8-m9, la comparaison de m1-m3, m1-m9,m8-m9 avec m3-m7, m3-m11,m9-m11, lacomparaison de m3-m7, m3-m11,m9-m11avec m7-m15 et m11-m15

6. Nous allons faire une dernier tableau de ncolonnes pur trouver le résultat définitif

qui est B’C’+CDNous pouvons vérifier ce résultat par letableau de Karnaugh suivant:

Simplification par la méthode de Quine-Mc ClauskeyGroupe Match Pairs ABCD

0m0-m1 000-

m0-m8 -000

1m1-m3 00-1

m1-m9 -001

m8-m9 100-

2m3-m7 0-11

m3-m11 -011

m9-m11 10-1

3m7-m15 -111

m11-m15 1-11

Groupe Match Pairs ABCD Implicants

0m0-m1 - m8-m9 -00-

B'C'm0-m8 - m1-m9 -00-

1m1-m3 - m9-m11 -01-

B'Cm1-m9 - m5-m11 -01-

2m3-m7 - m11-m15 --11

BCm9-m11 - m7-m15 --11

PI Minterm 0 1 3 7 8 9 11 15 RESULTAT

B'C' 0,1,8,9 X X X X B'C'

B'D 1,3,9,11 X X X X

CD 3,7,11,15 X X X X CD

CD

ABC’D’ C’D CD CD’

A’B’ 1 1 1

A’B 1

AB 1

AB’ 1 1 1

Page 42: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

42

Les dont care sont des inconnus qui peuventêtre remplacés par des «1» dans une fonctioncanonique SOP (SOmme des Produits), ou pardes « 0 » dans une fonction canonique POS(Produite des Sommes).

Ces dont care qui sont utilisés dans la méthodede Karnaugh, sont aussi utilisés dans laméthode de QM (Quine – Mc Clauskey) etpermettent de simplifier d’avantage lesfonctions logiques.

Ces dont cares sont utilisés dans tous lesétapes qui vont de 1 à 5. Ils ne sont cependantpas utilisés au moment de la recherche durésultats final

F(ABCD)=Sm(4,6,9,10,11,13) Sd(2,12,15)

Nous allons utiliser Karnaugh pour vérifier lerésultats avant d’utiliser la méthode de QM

Simplification par la méthode de Quine-Mc Clauskey avec des dont cares

ABCD ഥ𝐀 ഥ𝐁 ഥ𝐀 B A B A ഥ𝐁

ҧ𝐂 ഥ𝐃 0 4 1 12 X 8

ҧ𝐂 D 1 5 13 1 9 1

C D 3 7 15 X11 1

C ഥ𝐃 2 X 6 1 14 10 1

F= AD+A’BD′+AB′C

Minterm ABCD

4 0100

6 0110

9 1001

10 1010

11 1011

13 1101

Minterm ABCD

2 0010

12 1100

15 1111

G Minterm ABCD

1m2 0010

m4 0100

2

m6 0110

m9 1001

m10 1010

m12 1100

3m11 1011

m13 1101

4 m15 1111

4 6 9 10 11 13

A'CD' X

B'CD' X

A'BD' X X

BC'D' X

AB'C X X

ABC' X

AD X X X

AD+AB'C=A'BD'

Minterms ABCD

2,6 0-10

2,1 -010

4,6 01-0

4,12 -100

9,11 10-1≠

9,13 1-01≠

10,11 101-

12,13 110-

11,15 1-11≠

13,15 11-1≠

9,13,11,14 1--1

Page 43: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

43

Exercices

Utiliser le tableau de Karnaugh pour simplifier les fonctions suivantes

• a+b+a’b=b

• a’b’c’+a’b’c+ab’c’+ab’c=b’

• abc+a’b’c+a’b’c’=a’b’+abc

• a’b’c’d’+a’bc’d’+abc’d’+ab’c’d’ = c’d’

• abcd+ab’cd+abc’d+ab’c’d=ad

• a’b’cd+a’b’cd’+ab’cd+c’d’=a’b’c+b’cd’+c’d’

• abc’d’+ab’cd’+abcd’+a’cd’=cd’+abd’

Page 44: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

44

ExercicesQuelle est la plus petite base du nombre 11C.0 et trouvez son équivalent en base 10.

Le nombre le plus grand de cette base est C, sa base minimale est alors C+1 soit 13. 11C.0 13 en base 10 nous donne 1x132+1x131+12x130.0x13-1 = 194

Faites l’opération logique suivante : FE35 xor CB15.

Nous devons convertir les nombres hexadécimaux en binaire avant de faire d’effectuer la fonction logique binaire xor. Nous aurons alors

1111 1110 0011 0101

xor

1100 1011 0001 0101

0011 0101 0010 0000

3 5 2 0

Page 45: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

45

ExercicesCherchez le complément de F de 2BFD

Chercher le complément de 2BFD revient à trouver le résultat de la soustraction de FFFF-2BFD

FFFF

-

2BFD

D402

Combien de 1 compte un nombre décimal.

Faire en sorte que le nombre décimale soit une somme de 2n. Chaque 2n représente un 1.

2027 en binaire donne 211 210 29 28 27 26 25 24 23 22 21 20

2048 1024 512 256 128 64 32 16 8 4 2 1

1 1 1 1 1 1 0 1 0 1 1

Page 46: ALGÈBRE DE BOOLE - unis.sn

LES FONCTIONS LOGIQUES

r2

46

On dispose de 3 boutons de commande

des feux rouge (r), orange (o) et vert

(v) qui permettent d’allumer les

lampes Rouge (R), Orange (O) et verte

(V). Le rouge est prioritaire sur le

orange qui est prioritaire sur le vert.

Construire la table de vérité, simplifier

la fonction par la méthode de

Karnaugh et faire le logigramme.

r o v R O V

0 0 0 0 0 0

0 0 1 0 0 1

0 1 0 0 1 0

0 1 1 0 1 0

1 0 0 1 0 0

1 0 1 1 0 0

1 1 0 1 0 0

1 1 1 1 0 0

Boutons Feux

entrées sorties