5.

Simplification de fonctions
3) Tableau de Karnaugh
a) Termes adjacents
 Examinons l’expression suivante : a.ba.b
Chapitre 4: Simplification de fonctions

Les deux termes possèdent les même variables. La seule différence est l’état de la
variable b qui change.
 Si on applique les règles de simplification on obtient :
a.ba.b a.(bb)a

Les deux termes constituant a.ba.b sont dits adjacents.

 Exemple: Les expressions suivantes sont formées par des termes sont adjacents.
a.(bb)a
abcabcac
abcd abcd abd
Les termes constituant les sommes suivantes ne sont pas adjacents.
a.ba.b
a.b.ca.b.c

Architecture des ordinateurs 35

 5. Simplification de fonctions
 Le tableau de Karnaugh est une représentation de la table de vérité en deux
dimensions. Il comprend 2n cases ( n est le nombre de variables ).
 Le tableau Karnaugh se base sur la règle précédente (les termes adjacents).
 Le tableau consiste a mettre en évidence par une méthode graphique tous les
Chapitre 4: Simplification de fonctions

termes qui sont adjacents (qui ne différent que par l’état d’une seule variable).
 n=2
A
A B F 0 1
B
0 0 0 0 0 1
0 1 1 1 1 1
1 0 1
1 1 1
Table de vérité Table Karnaugh

Architecture des ordinateurs 36

 5. Simplification de fonctions
 Note: Au-delà de deux variables, le tableau devrait être un volume. Pratiquement
on conserve évidemment une représentation à deux dimensions mais il faut alors
respecter une règle qui est l’adjacence de deux lignes ou colonnes.
 n=3
Chapitre 4: Simplification de fonctions

AB
C 00 01 11 10
0
1

 n=4
Adjacence de deux lignes

AB Adjacence de deux colonnes

CD 00 01 11 10
00
01
11
10
Architecture des ordinateurs 37
 5. Simplification de fonctions
 N=5 cde
ab 000 001 011 010 110 111 101 100
00
Chapitre 4: Simplification de fonctions

01
11
10

 Dans un tableau de Karnaugh , chaque case possède un certain nombre de cases

adjacentes.
00 01 11 10 00 01 11 10
0 00 N
A B C
01 M Q O
1 D
11 P
Les cases A, D et C sont adjacentes à B.
Les cases M, N, O et P sont adjacentes à Q. 10
Architecture des ordinateurs 38
 5. Simplification de fonctions
 Deux cases adjacentes sur le tableau de Karnaugh correspondent à des
combinaisons différent d’un seul bit. Ceci est valable à l’intérieur du tableau mais
aussi sur ses bords : en passant du bord droit au bord gauche ou du haut au bas il y
a adjacence. Ceci revient à dire que l’on peut considérer le tableau comme une
Chapitre 4: Simplification de fonctions

sphère.
cde
ab 000 001 011 010 110 111 101 100
00 F G M
01 I J
11 K L
10 N

 Exemple : Les cases F et G sont adjacentes.

Les cases I et J sont adjacentes.
Les cases M et N sont adjacentes.
Les cases K et L sont adjacentes.

Architecture des ordinateurs 39

 Exercices
 Exercice 1: Quelles sont les cases adjacentes de A5, A16 et A20.
cde
ab 000 001 011 010 110 111 101 100
00 A1 A2 A3 A4 A5 A6 A7 A8
Chapitre 4: Simplification de fonctions

01 A9 A10 A11 A12 A13 A14 A15 A16

11 A17 A18 A19 A20 A21 A22 A23 A24
10 A25 A26 A27 A28 A29 A30 A31 A32
 Exercice 2: Á partir de la table de vérité suivant trouver le table de Karnaugh.
A B C F
0 0 0 0
1 0 0 0
0 1 0 1
1 1 0 1
0 0 1 0
1 0 1 1
0 1 1 1
1 1 1 0
Architecture des ordinateurs 40
 5. Simplification de fonctions
 Solution:

A B C F
0 0 0 0
Chapitre 4: Simplification de fonctions

1 0 0 0
0 1 0 1
1 1 0 1
0 0 1 0
1 0 1 1
0 1 1 1
1 1 1 0

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

Architecture des ordinateurs 41

 5. Simplification de fonctions
b) Forme normale disjonctive (FND)
 Les formes normales sont des expressions particulières de fonctions logiques, sous
formes de ET de OU (“produits de sommes”) ou de OU de ET (“sommes de
produits”). Dans chaque terme apparaissent toutes les variables.
Chapitre 4: Simplification de fonctions

 Théorème n°1 de Shannon :Toute fonction logique peut se décomposer en un OU

de deux ET logiques :
f  a,b, c,...  a. f 1,b, c,...  a. f  0,b, c,...
     

 En utilisant successivement ce théorème on arrive à la forme normale

disjonctive (FND) de f:
f (a,b, c)  a.b. f (1,1, c,,)  a.b. f (0,1, c,...)  a.b. f (1,0,c,...)  a.b. f (0,0, c,...)
La fonction s’écrit donc comme un OU de toutes les combinaisons possibles de n
variables pondérées par des 0 et 1 (il y a donc 2n termes). Les termes pondérés par
des 0 disparaissent et il ne reste donc que les termes pondérés par des 1, d’où
l’expression : “développement de la fonction suivant les 1”.

Architecture des ordinateurs 42

 5. Simplification de fonctions
 Exemple 1 : Soit f(a,b,c) définie par le tableau de Karnaugh suivant, déterminer sa
forme normale disjonctive (FND).
ab
c 00 01 11 10
Chapitre 4: Simplification de fonctions

0 0 0 0 1
1 1 1 0 1
 Solution
On a: f (a,b, c)  abc.f (0,0,0,)  abc. f (0,0,1)  abc. f (0,1,0,)  abc. f (0,1,1)
abc. f (1,0,0) abc. f (1,0,1)abc. f (1,1,0)abc. f (1,1,1)

 abc.0  abc.1 abc.0  abc.1 abc.1 abc.1 abc.0  abc.0

Soit f (a,b, c)  abc  abc  abc  abc

 Note: On note que ce résultat est obtenu directement à partir du tableau de
Karnaugh (ou de la table de vérité) en écrivant que f est l’union (+) des
combinaisons de a, b, c pour lesquelles f vaut 1.

Architecture des ordinateurs 43

 5. Simplification de fonctions
 Exemple 2 : Soit f (a,b,c)  abc  abc  abc  abc
Trouver le tableau de Karnaugh (ou la table de vérité) de f.
 Solution:
Sous sa forme normale, f s’écrit:
Chapitre 4: Simplification de fonctions

f (a,b, c)  abc.f (0,0,0,)  abc. f (0,0,1)  abc. f (0,1,0,)  abc. f (0,1,1) 

abc. f (1,0,0) abc. f (1,0,1)abc. f (1,1,0)abc. f (1,1,1)

f (0,0,0,) 1 f (0,0,1) 1 f (0,1,0,)  0 f (0,1,1) 1

Avec f (1,0,0)  0 f (1,0,1) f (1,1,0)  0 f (1,1,1)  0
ab
D’où le tableau de Karnaugh c 00 01 11 10
0 1 0 0 0
1 1 1 0 1

On note que cela revient à mettre des 1 dans les cases définies par les
combinaisons de variables présentes dans l’expression de f.

Architecture des ordinateurs 44

 Exercices
 Exercice 1: Déterminer la forme FND de la fonction logique définie par le tableau
ab
de Karnaugh.
cd 00 01 11 10
00 0 1 0 0
Chapitre 4: Simplification de fonctions

01 0 0 0 0
11 1 0 0 1
10 0 1 1 0
Solution :
f (a,b, c, d )  abcd  abcd abcd abcd abcd 
 Exercice 2: Donner le tableau de Karnaugh correspond à la fonction logique
suivante : f (a,b)  ab ab  ab

Solution : a
b 0 1
0 0 1
1 1 1
Architecture des ordinateurs 45
 5. Simplification de fonctions
c) Forme normale conjonctive (FNC)
 Dualité: Une égalité demeure vraie si l’on permute les OR et AND et les 0 et 1
(d’après les théorèmes De-Morgan).
Exemple:
Chapitre 4: Simplification de fonctions

a 1  1 alors a.0  0
aa1 aa

 Théorème n° 2 de Shannon : Toute fonction logique peut se décomposer en un

ET de deux OU logiques :
f (a, b, c,...)  (a  f (0, b, c,...)).(a  f (1, b, c,...))

 Cette forme est la duale de la FND. Comme précédemment, l’utilisation successive

de ce théorème permet d’arriver à la forme normale conjonctive (FNC).
 Note: Il faut d’abord écrire la fonction sous la forme FND puis on fait le dual
pour trouver la forme FNC.

Architecture des ordinateurs 46

 5. Simplification de fonctions
 Exemple 1: Soit le tableau de Karnaugh. ab
c 00 01 11 10
0 0 0 0 1
1er terme: a  b  c  f  0,0,0 
Chapitre 4: Simplification de fonctions

 
1 1 1 0 1
2 terme: a  b  c  f  0,0,1
ème 

3ème terme: a  b  c  f  0,1,0 

…
8ème terme: a  b  c  f 1,1,1
 

f (a,b, c)  [(a  b  c)  0][(a  b  c) 1][(a  b  c)  0][(a  b  c) 1]

[(a  b  c) 1][(a  b  c) 1][(a  b  c)  0][(a  b  c)  0]
Les terme contenant 1 disparaissent:
f (a,b, c)  (a  b  c)(a  b  c)(a  b  c)(a  b  c)

 Note: En pratique, on cherche les cases à 0, puis on fait le ET des combinaisons
de variables qui leur “correspondent” en prenant garde que la “correspondance”
n'est pas la même que pour la FND: Développement suivant les “0”.

Architecture des ordinateurs 47

 5. Simplification de fonctions
 Exemple 2: ab
c 00 01 11 10
0 1 0 1 0
1 0 1 0 0
Chapitre 4: Simplification de fonctions

Développement suivant les 0:

f (a,b, c)  (a  b  c)(a  b  c)(a  b  c)(a  b  c)(a  b  c)
 Exemple 3 : Passage de la FNC au tableau de Karnaugh
f (a,b, c)  (a  b  c)(a  b  c)(a  b  c)(a  b  c)
Cette fonction s’ écrit :
f (a,b, c)  [(a  b  c)  f (0,0,0)][(a  b  c)  f (0,0,1)][(a  b  c)  f (0,1,0)][(a  b  c)  f (0,1,1)]
[(a  b  c)  f (1,0,0)][(a  b  c)  f (1,0,1)][(a  b  c)  f (1,1,0)][(a  b  c)  f (1,1,1)]
avec ici : f (0,0,0)  0 f (0,0,1) 1 f (0,1,0)  0 f (0,1,1)  1
f (1,0,0) 1 f (1,0,1)  1 f (1,1,0)  0 f (1,1,1)  0

d’où le tableau de Karnaugh ab

c 00 01 11 10
0 0 0 0 1
1 1 1 0 1
Architecture des ordinateurs 48
 Exercices
 Exercice 1: Déterminer la forme FNC de la fonction logique définie par le tableau
de Karnaugh. cde
ab 000 001 011 010 110 111 101 100
00 0 1 1 1 1 1 1 1
Chapitre 4: Simplification de fonctions

01 1 1 1 1 1 0 1 0
11 1 1 1 0 1 1 1 0
10 0 1 1 1 1 1 1 1
Solution :
f (a,b, c, d ,e)  (a  b  c  d  e).(a  b  c  d  e).(a  b  c  d  e).(a  b  c  d  e).
(a  b  c  d  e).(a  b  c  d  e)
 Exercice 2: Donner le tableau de Karnaugh correspond à la fonction logique
suivante :
f (a,b, c)  (a  b  c)(a  b  c)(a  b  c)
ab 00 01 11 10
Solution : c
0 0 0 1 1
1 1 1 0 1

Architecture des ordinateurs 49

 5. Simplification de fonctions
d) Simplification par le tableau de Karnaugh
 La méthode de Karnaugh permet de visualiser une fonction et d’en tirer
naturellement une écriture simplifiée.
 L’élément de base de cette méthode est la table de Karnaugh qui représente toutes
Chapitre 4: Simplification de fonctions

les combinaisons d’états possibles pour un nombre de variables donné.

 La table de Karnaugh est un outil graphique qui permet de simplifier de manière
méthodique des expressions booléennes.
 La construction des tables de Karnaugh exploite le codage de l’information et la
notion d’adjacence.
 Règle pratique : La règle consiste à “fusionner” les 2n cases adjacentes pour
trouver l’expression simplifiée résultante. On regarde la ou les variables qui
change(nt) entre les cases fusionnées; ces variables sont alors supprimées
dans la nouvelle expression simplifiée.

Architecture des ordinateurs 50

 5. Simplification de fonctions
 Simplification par la forme FND
bc
a 00 01 11 10
0 1 1
Chapitre 4: Simplification de fonctions

1 1

f (a,b,c)abc
. . abc
. . abc
..
 Simplification par la forme FNC
bc
a 00 01 11 10
0 0
1 0 0

f (a,b,c)a  b  c).a  b  c).a  b  c)

Architecture des ordinateurs 51

 5. Simplification de fonctions
 L’idée de base est d’essayer de regrouper (faire des regroupements ) les cases
adjacentes qui comportent des 1 (ou des 0)( rassembler les termes adjacents).
Essayer de faire des regroupements avec le maximum de cases ( 16,8,4 ou 2 )
 Exemple 1: Dans cet exemple on peut faire uniquement des regroupements de 2
Chapitre 4: Simplification de fonctions

cases . ab
c 00 01 11 10
0 abc abc abc
1 abc
ab . .ca.b
. .cab
1 abc abc 1 abc
1 abc
1
Puisque il existent encore des cases qui sont en dehors d’un regroupement on
refait la même procédure : former des regroupements.
ab
c 00 01 11 10
0 1 abc . . ab
. . abc .
1 1 1 1 abc . . a.c
. . abc
Note: Une case peut appartenir à plusieurs regroupements (rappel A+A=A).

Architecture des ordinateurs 52

 5. Simplification de fonctions
On s’arrête lorsque il y a plus de 1 en dehors des regroupements.
La fonction final est égale à la réunion (somme) des termes après simplification.
ab
c
Chapitre 4: Simplification de fonctions

00 01 11 10
0 1 abc  abc  ab

1 1 1 1 abc  abc  ac

abc  abc  bc

f ( a , b , c )  ab  ac  bc

Note : Nous pouvons faire la même démarche mais en développement seulement

suivant les 0 (utilisation du FNC).
Architecture des ordinateurs 53
 5. Simplification de fonctions
 En résumé pour simplifier une fonction par la table de Karnaugh il faut suivre les
étapes suivantes :
1) Remplir le tableau à partir de la table de vérité ou à partir de la forme canonique
(FND ou FNC).
Chapitre 4: Simplification de fonctions

2) Faire des regroupements : des regroupements de 1, 2, 4, 8, 16 cases (Les même

termes peuvent participer à plusieurs regroupements ).
3) Dans un regroupement :
Qui contient un seul terme on peut pas éliminer de variables.
Qui contient deux termes on peut éliminer une variable (celle qui 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.
4) L’expression logique finale est la réunion (la somme) des groupements après
simplification et élimination des variables qui changent d’état.
 Note : Attention on utilise que de regroupements de 1, 2, 4, 8, 16 (20, 21, 22, 23, 24)
cases.

Architecture des ordinateurs 54

 5. Simplification de fonctions
 Exemple 2: 3 variables ab
c 00 01 11 10
0 1
1 1 1 1 1
Chapitre 4: Simplification de fonctions

f ( a , b , c )  cab
bc
a 00 01 11 10
0 1 1
1 1 1 1
bc
a 00 01 11 10
0 0 0
f (a,b,c)ab
. c
1 0

f (a, b, c ) a  c).(b  c)

Architecture des ordinateurs 55
 5. Simplification de fonctions
 Exemple 3: 4 variables ab
cd 00 01 11 10
00 1
01 1 1 1 1
Chapitre 4: Simplification de fonctions

11
10 1

f (a, b, c)cd  abcabcd

ab
cd 00 01 11 10


a change
00 1 1
b ne change pas (0)
01 bd
c change
11 d ne change pas (0)
10 1 1
f (a, b, c)abcd abcd abcd abcd bd

Architecture des ordinateurs 56

 5. Simplification de fonctions
 Exemple 4:
ab
cd 00 01 11 10
Chapitre 4: Simplification de fonctions

00 1 1

01 1 1 1

11 1

10 1 1

f (a, b, c, d )abbd bcd

 Exercice: Refaire cet exemple en cherchant la FCN simplifiée.

Architecture des ordinateurs 57
 5. Simplification de fonctions
 Exemple 5: 5 variables

cde
ab 000 001 011 010 110 111 101 100
Chapitre 4: Simplification de fonctions

00 1 1 1
01 1 1 1 1 1
11 1 1 1
10 1 1 1 1

f (a, b, c) ade bd ccd e abe

Architecture des ordinateurs 58

 Exercices
 Exercice 1: Trouver la forme simplifiée des fonctions à partir des tableaux
a (b)
ab (c)
suivants. b 0 1
a (a ) c 00 01 11 10
0 1 0 0 1 0 0 1 1 1
Chapitre 4: Simplification de fonctions

1 0 1 1 1 1 1 1 1 1
abc (d )
d 000 001 011 010 110 111 101 100
0 0 0 0 0 1 1 0 0
1 0 1 1 0 1 1 1 0
ab (e)
00 01 11 10 abc 000 001 011 010( f ) 110 111 101 100
cd de
00 0 0 1 0 00 0 1 1 0 0 1 1 0
01 0 0 1 0 01 1 1 1 0 1 0 0 0
11 1 1 1 1 11 1 0 1 1 0 0 0 1
10 0 0 1 0 10 0 1 1 1 0 1 1 0
(a) f  a(b) f  a  b(c) f  a b c(d ) f  abcd
 Correction : (e) f  abcd ( f ) f  (ce abd  bcdeabcde) acd abde
Architecture des ordinateurs 59