4.

Simplification des fonctions logiques

• 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
4. Simplification des fonctions
logiques • 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 :

– La Méthode algébrique
– Les Méthodes graphiques : ( ex : table de karnaugh )
– Les méthodes programmables

56 57

56 57

5. Méthode algébrique
5.1 Règles de simplification
• Le principe consiste à appliquer les règles de l’algèbre de
Boole afin d’éliminer des variables ou des termes. • Règles 1 : regrouper des termes à l’aide des règles
• Mais il n’y a pas une démarche bien spécifique. précédentes
• Voici quelques règles les plus utilisées :
• Exemple

A .B + A .B = B ABC + AB C + A B CD = AB (C + C ) + A B CD
A + A .B = A = AB + A B CD
A + A .B = A + B = A ( B + B (CD))
( A + B) ( A + B ) = A = A ( B + CD)
A . ( A + B) = A = AB + ACD
A . ( A + B) = A . B 58 59

58 59
 • Règles 2 : Rajouter un terme déjà existant à une expression
• Règles 3 : il est possible de supprimer un terme
superflu ( un terme en plus ), c’est-à-dire déjà
inclus dans la réunion des autres termes.
• Exemple :

• Exemple 1 :
A B C + ABC + A BC + AB C =
F(A, B, C) = A B + BC + AC = AB + BC + AC ( B + B )
ABC + ABC + ABC + A BC + ABC + AB C =
= AB + BC + ACB + A BC
BC + AC + AB
= AB ( 1 + C) + BC (1 + A)
= AB + BC

60 61

60 61

Exemple 2 : il existe aussi la forme conjonctive du terme

superflu • Règles 4 : il est préférable de simplifier la forme
canonique ayant le nombre de termes minimum.

F(A, B, C) = (A + B) . (B + C) . (A + C) • Exemple :
= (A + B) . (B + C) . (A + C + B .B )
= (A + B) . (B + C) . (A + C + B) .(A + C + B ) F ( A , B , C ) = R ( 2 ,3 , 4 ,5 , 6 , 7 )
= (A + B) . (A + C + B) . (B + C) .(A + C + B ) F(A, B, C) = R( 0,1) = A . B . C + A . B . C
= (A + B) . (B + C) = A . B ( C + C)
= A .B = A + B
F(A, B, C) = F(A, B, C) = A + B = A + B

62 63

62 63
 Exercice

Démontrer la proposition suivante :

6. Simplification par la table
A.B + B.C + A.C + A.B.C + A.B.C + A.B.C = A + B + C
de Karnaugh
Donner la forme simplifiée de la fonction suivante :

F ( A, B , C , D ) = ABCD + A BCD + AB C D + ABC D + ABCD

64 65

64 65

6.1. Les termes adjacents Exemple de termes adjacents

•Examinons l’expression suivante : Ces termes sont adjacents

A .B + A .B A.B + A. B = B
A.B.C + A. B. C = A.C
•Les deux termes possèdent les même variables. La A.B.C.D + A.B. C. D = A.B.D
seule différence est l’état de la variable B qui change.
Ces termes ne sont pas adjacents
•Si on applique les règles de simplification on obtient :
A.B + A. B
AB + A B = A ( B + B ) = A A.B.C + A. B. C
A.B.C.D + A. B. C. D
•Ces termes sont dites adjacents.
66 67

66 67
 6.1 Description de la table de karnaugh

•La méthode de Karnaugh se base sur la règle précédente. A AB

• La méthode consiste a mettre en évidence par une B 0 1 C 00 01 11 10
méthode graphique (un tableaux ) tous les termes qui sont 0 0
adjacents (qui ne différent que par l’état d’une seule
variable). 1 1

•La méthode peut s’appliquer aux fonctions logiques de

2,3,4,5 et 6 variables.
•Un tableau de Karnaugh comportent 2n cases ( N est le Tableau à 2 variables Tableaux à 3 variables
nombre de variables ).

68 69

68 69

Tableau à 5 variables
Tableau à 4 variables

AB
CD 00 01 11 10 AB AB
CD 00 01 11 10 CD 00 01 11 10
00
00 00
01
01 01
11
11 11
10
10 10

U=0 U= 1
70 71

70 71
 Dans un tableau de karnaugh , chaque case possède un certain 6.2 Passage de la table de vérité à la table de Karnaugh
nombre de cases adjacentes.

•Pour chaque combinaisons qui représente un min terme lui

AB
correspond une case dans le tableau qui doit être mise à 1 .
AB
C 00 01 11 10 CD 00 01 11 10 •Pour chaque combinaisons qui représente un max terme lui
0 00 correspond une case dans le tableau qui doit être mise à 0 .
1 01 • Lorsque on remplis le tableau , on doit soit prendre les
min terme ou les max terme
11

Les trois cases bleues sont des

10
cases adjacentes à la case rouge

72 73

72 73

Exemple :
6.3 Passage de la forme canonique à la table de
Karnaugh

A B C S • Si la fonction logique est donnée sous la première forme

0 0 0 0 canonique ( disjonctive), alors sa représentation est
AB
directe : pour chaque terme lui correspond une seule
0 0 1 0 C 00 01 11 10 case qui doit être mise à 1.
0 1 0 0 0 1
0 1 1 1 • Si la fonction logique est donnée sous la deuxième
1 1 1 1
1 0 0 0 forme canonique ( conjonctive), alors sa représentation
est directe : pour chaque terme lui correspond une seule
1 0 1 1
case qui doit être mise à 0 .
1 1 0 1
1 1 1 1

74 75

74 75
 Exemple 6.4 Méthode de simplification (Exemple : 3 variables )
AB
C •L’idée de base est d’essayer de regrouper (faire des regroupements ) les
00 01 11 10 cases adjacentes qui comportent des 1 ( rassembler les termes
F1(A, B, C) =  (1,2,5,7) 0 adjacents ).
1
•Essayer de faire des regroupements avec le maximum de cases ( 16,8,4
1 1 1 1 ou 2 )
•Dans notre exemple on peut faire uniquement des regroupements de 2
cases .

AB AB
C 00 01 11 10 C 00 01 11 10
F2(A, B, C) = ∏ (0,2,3,6) 0 0 0 0 0 1 ABC + ABC = AB

1 0 1 1 1 1

76 77

76 77

•Puisque il existent encore des cases qui sont en dehors d’un •On s’arrête lorsque il y a plus de 1 en dehors des regroupements
regroupement on refait la même procédure : former des •La fonction final est égale à la réunion ( somme ) des termes après
regroupements. simplification.
•Une case peut appartenir à plusieurs regroupements
AB
C 00 01 11 10
0 1 ABC + ABC = AB
AB
C 1
00 01 11 10 1 1 1 ABC + A BC = AC
0 1 ABC + ABC = AB
1 1 1 1 ABC + A BC = AC ABC + ABC = BC

F ( A, B, C ) = AB + AC + BC
78 79

78 79
Donc , en résumé pour simplifier une fonction par la table de Exemple 1 : 3 variables
karnaugh il faut suivre les étapes suivantes :

1. Remplir le tableau à partir de la table de vérité ou à partir

de la forme canonique. AB
2. Faire des regroupements : des regroupements de C
16,8,4,2,1 cases ( Les même termes peuvent participer à 00 01 11 10
plusieurs regroupements ) . 0 1
3. Dans un regroupement :
 Qui contient un seule terme on peut pas éliminer de variables. 1
 Qui contient deux termes on peut éliminer une variable ( celle qui
1 1 1 1
change d’état ).
 Qui contient 4 termes on peut éliminer 2 variables.
 Qui contient 8 termes on peut éliminer 3 variables.
 Qui contient 16 termes on peut éliminer 4 variables.
5. L’expression logique finale est la réunion ( la somme ) des
groupements après simplification et élimination des F ( A, B, C ) = C + AB
variables qui changent d’état.
80 81

80 81

Exemple 2 : 4 variables Exemple 3 : 4 variables

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

F ( A , B , C , D ) = C . D + A . B .C + A . B .C . D F ( A, B, C , D) = AB + B D + BC D
82 83

82 83
 Exemple 4 : 5 variables Exercice
AB AB
Trouver la forme simplifiée des fonctions à partir des
CD CD
deux tableaux ?
00 01 11 10 00 01 11 10
00 1 00 1
AB
01 1 1 01 1 1 CD 00 01 11 10
AB
11 1 1 11 1 1 C 00 01 11 10 00 1 1 1
0 1 1 1
10 1 10 1 1 01

1 1 1 1 11
U=0 U= 1
10 1 1 1 1
F(A, B, C, D, U) = A B + A.B.D. U + A .C. D.U + A.B.D.U
84 85

84 85

A B C D S
•Pour les cas impossibles ou interdites
6.5 Cas d’une fonction non totalement définie 0 0 0 0 0
il faut mettre un X dans la T.V . 0 0 0 1 0
•Les cas impossibles sont représentées 0 0 1 0 0
• Examinons l’exemple suivant :
aussi par des X dans la table de karnaugh 0 0 1 1 1
Une serrure de sécurité s’ouvre en fonction de quatre clés A, B, C 0 1 0 0 0
D. Le fonctionnement de la serrure est définie comme suite : 0 1 0 1 1
S(A,B,C,D)= 1 si au moins deux clés sont utilisées 0 1 1 0 1
S(A,B,C,D)= 0 sinon AB
CD 0 1 1 1 1
00 01 11 10
Les clés A et D ne peuvent pas être utilisées en même temps. 1 0 0 0 0
00 1 1 0 0 1 X
1 0 1 0 1
•On remarque que si la clé A et D sont utilisées en même temps 01 1 X X 1 0 1 1 X
l’état du système n’est pas déterminé.
1 1 0 0 1
11 1 1 X X
•Ces cas sont appelés cas impossibles ou interdites  comment 1 1 0 1 X
représenter ces cas dans la table de vérité ?. 10 1 1 1 0 1
86
1 1 1 1 1 1 1 X 87

86 87
 • Il est possible d’utiliser les X dans des regroupements :
– Soit les prendre comme étant des 1
AB
– Ou les prendre comme étant des 0
CD
• Il ne faut pas former des regroupement qui contient uniquement des X 00 01 11 10

AB 00 1
CD
00 01 11 10 01 1 X X
00 1
11 1 1 X X
01 1 X X
10 1 1 1
11 1 1 X X
10 1 1 1
AB + CD
AB 88 89

88 89

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

AB + CD + BD AB + CD + BD + AC
90 91

90 91
 Exercice 1
AB
CD
00 01 11 10 Trouver la fonction logique simplifiée à partir de la table
00 suivante ?
1
01 1 X X AB
CD 00 01 11 10
11 1 1 X X 00 1 X
10 1 1 1 01 1 X 1
11 1 X 1
10 X 1 X
AB + CD + BD + AC + BC
92 93

92 93