Chapitre 1 • Structures ordonnées Applications des treillis
26
le lec teur pourra véri fier faci le ment, par la méthode indi quée plus haut, la liste
complète des consti tuants pre miers de cette fonc tion :
F 5 a # b 1
# a # c 1
# b # c ;
or, cette liste n’est pas la forme mini male de F. En effet, si nous déve lop pons F sous la
forme cano nique dis jonc tive (somme de mintermes), nous trou vons :
F 5 a # b # c 1
# a # b # c 1
# a # b # c 1
# a # b # c .
Si main te nant nous déve lop pons : Fr 5 a # b 1
# a # c, sous forme canonique disjonctive
nous aurons éga le ment :
Fr 5 a # b # c 1
# a # b # c 1
# a # b # c 1
# a # b # c ; ainsi Fr 5 F.
c’est donc que les deux consti tuants pre miers a # b et a # c suf fisent à repré sen ter la
fonc tion F.
Pour mieux nous en rendre compte, dres sons un tableau à double entrée dans
lequel nous men tion ne rons, en colonnes, les mintermes de la forme cano nique et, en
lignes, les consti tuants pre miers.
Mar quons d’une croix, sur
chaque ligne, les mintermes que
l’on obtien drait en déve lop pant
cha cun des consti tuants pre miers.
On constate que les mintermes
a # b # c et a # b # c ne sont conte nus,
res pec ti ve ment, que dans a # b et
a # c ; au contraire, les mintermes a # b # c et a # b # c peuvent être obte nus res pec ti ve ment,
soit par déve lop pe ment de a # b et a # c, soit encore par déve lop pe ment de b # c.
Les consti tuants pre miers a # b et a # c sont des consti tuants (premiers) essen tiels ;
l’absence de l’un d’entre eux dans la forme mini male n’est pas possible, puis qu’ils
engendrent des mintermes qui ne sont conte nus dans aucun autre consti tuant pre mier.
Il se trouve que les consti tuants essen tiels suf fisent ici à repré sen ter la fonc tion
et que b # c est un consti tuant pre mier redon dant, donc qu’il ne faut pas faire figu rer
dans la forme mini male. Mais il arrive souvent que, pour obte nir une forme mini
male, on doive employer, outre les consti tuants essen tiels, un cer tain nombre de
consti tuants non essen tiels ; le pro blème qui consiste à trou ver un ensemble mini mal
de ces consti tuants n’est guère plus dif fi cile, mais sor ti rait de notre sujet (il s’agit
du pro blème de « recou vre ment », bien connu en recherche opé ra tion nelle). Notons
qu’une même fonction peut admettre plusieurs formes minimales (cf ci-dessous).
Remarque. La mani pu la tion des for mules de l’algèbre de Boole exige par fois des
cal culs très longs. En effet, les problèmes rencontrés sont le plus sou vent NP-complets (le lec teur se repor tera au cha pitre 2). Nous ver rons, plus loin dans cet ouvrage,
dans la par tie défi nis sant ces pro blèmes, qu’ils ne peuvent pas être réso lus sans
avoir recours à des méthodes énu mé ra tives très lourdes en temps de cal cul.
a • b
a • b • c a • b • c a • b • c a • b • c
a • c
b • c
26
le lec teur pourra véri fier faci le ment, par la méthode indi quée plus haut, la liste
complète des consti tuants pre miers de cette fonc tion :
F 5 a # b 1
# a # c 1
# b # c ;
or, cette liste n’est pas la forme mini male de F. En effet, si nous déve lop pons F sous la
forme cano nique dis jonc tive (somme de mintermes), nous trou vons :
F 5 a # b # c 1
# a # b # c 1
# a # b # c 1
# a # b # c .
Si main te nant nous déve lop pons : Fr 5 a # b 1
# a # c, sous forme canonique disjonctive
nous aurons éga le ment :
Fr 5 a # b # c 1
# a # b # c 1
# a # b # c 1
# a # b # c ; ainsi Fr 5 F.
c’est donc que les deux consti tuants pre miers a # b et a # c suf fisent à repré sen ter la
fonc tion F.
Pour mieux nous en rendre compte, dres sons un tableau à double entrée dans
lequel nous men tion ne rons, en colonnes, les mintermes de la forme cano nique et, en
lignes, les consti tuants pre miers.
Mar quons d’une croix, sur
chaque ligne, les mintermes que
l’on obtien drait en déve lop pant
cha cun des consti tuants pre miers.
On constate que les mintermes
a # b # c et a # b # c ne sont conte nus,
res pec ti ve ment, que dans a # b et
a # c ; au contraire, les mintermes a # b # c et a # b # c peuvent être obte nus res pec ti ve ment,
soit par déve lop pe ment de a # b et a # c, soit encore par déve lop pe ment de b # c.
Les consti tuants pre miers a # b et a # c sont des consti tuants (premiers) essen tiels ;
l’absence de l’un d’entre eux dans la forme mini male n’est pas possible, puis qu’ils
engendrent des mintermes qui ne sont conte nus dans aucun autre consti tuant pre mier.
Il se trouve que les consti tuants essen tiels suf fisent ici à repré sen ter la fonc tion
et que b # c est un consti tuant pre mier redon dant, donc qu’il ne faut pas faire figu rer
dans la forme mini male. Mais il arrive souvent que, pour obte nir une forme mini
male, on doive employer, outre les consti tuants essen tiels, un cer tain nombre de
consti tuants non essen tiels ; le pro blème qui consiste à trou ver un ensemble mini mal
de ces consti tuants n’est guère plus dif fi cile, mais sor ti rait de notre sujet (il s’agit
du pro blème de « recou vre ment », bien connu en recherche opé ra tion nelle). Notons
qu’une même fonction peut admettre plusieurs formes minimales (cf ci-dessous).
Remarque. La mani pu la tion des for mules de l’algèbre de Boole exige par fois des
cal culs très longs. En effet, les problèmes rencontrés sont le plus sou vent NP-complets (le lec teur se repor tera au cha pitre 2). Nous ver rons, plus loin dans cet ouvrage,
dans la par tie défi nis sant ces pro blèmes, qu’ils ne peuvent pas être réso lus sans
avoir recours à des méthodes énu mé ra tives très lourdes en temps de cal cul.
a • b
a • b • c a • b • c a • b • c a • b • c
a • c
b • c