Chapitre 1 • Structures ordonnées Applications des treillis
22
1 2 3 4 5 6 7
8
9
10
11
12 13
14
15 16
a b c a b c a # b a # b 1
# c a # b 1
# c a # b 1 ab 1
# c 2 # a # b b # c a 1
# c b # c # 1 a 1
# c 2  a # b # c
0 0 0 1 1 1 0
0
1
0
0
0
1
0
0 m 0
0 0 1 1 1 0 0
1
0
0
0
0
1
0
0 m 1
0 1 0 1 0 1 0
0
1
0
0
1
1
1
1 m 2
0 1 1 1 0 0 0
1
0
0
0
0
1
0
0 m 3
1 0 0 0 1 1 0
0
1
1
1
0
0
0
1 m 4
1 0 1 0 1 0 0
1
0
1
0
0
1
0
0 m 5
1 1 0 0 0 1 1
1
0
0
0
1
0
0
0 m 6
1 1 1 0 0 0 1
1
0
0
0
0
1
0
0 m 7
1.3.3 Minimi sa tion d’une fonc tion boo léenne
Consi dé rons deux fonc tions des variables binaires 1 x 1 , x 2 , c , x n 2 . On dit que la fonc -
tion f implique la fonc tion g et l’on écrit : f 1 g , si f 5 1 entraîne g 5 1, c’està-dire si f est une par tie de g : les mintermes de f figurent aussi dans ceux de g.
Soit alors la fonc tion :
F 5 x 1 # x 2 1
# x 2 # x 1 1
# x 1 # x 3 .
Si l’on choi sit des valeurs telles que l’un des pro duits x 1 # x 2 ou bien x 2 # x 1 ou bien
x 1 # x 3 , soit égal à 1, on a évi dem ment F 5 1. La fonc tion F est impli quée par l’un
quel conque de ces pro duits.
Consi dé rons alors la fonc tion 1 x 1 , x 2 2 5 x 1 # x 2 ; si l’on y fait x 1 5 1 ou bien
x 2 5 1, on obtient :
1 1, x 2 2 5 x 2 ; 1 x 1 , 12 5 x 1 ;
la fonc tion  n’est impli quée ni par x 1 , ni par x 2 ; en effet :
1 x 1 5 1 1  5 1 ; 1 x 2 5 12 1  5 1.
Comme  implique F et  n’est impli qué ni par x 1 , ni par x 2, on dit que  est un
consti tuant pre mier (ou encore monôme pre mier) de F.
Au contraire, si l’on fait x 3 5 1 dans F, on obtient :
F1 x 3 5 12 5 x 1 # x 2 1
# x 2 1
# x 1
et, si l’on construit le tableau des valeurs (voir tableau ci­ dessous),