Chapitre 1 • Structures ordonnées Applications des treillis
18
Exemple. Soit la fonction booléenne , à trois variables A, B et C :
5 5 3 1 A d B2 c C 4 d 1 A d B2 6 c 3 1 B d C 2 d 1 A c C 2 4
Appli quons d’abord la for mule géné ra li sée de de Morgan :
5 5 3 1 A c B2 d C 4 d 1 A d B2 6 c 3 1 B d C 2 d 1 A c C 2 4
Déve lop pons ensuite en uti li sant la distributivité de l’opé ra tion d par rap port à l’opé -
ra tion c :
5 5 3 1 A d C 2 c 1 B d C 2 4 d 1 A d B2 6 c 5 3 1 B d C 2 d A4 c 3 1 B d C 2 d C 46
5 3 1 A d C 2 d 1 A d B2 4 c 3 1 B d C 2 d 1 A d B2 4 c 3 1 A d B d C 2 c 1 B d C d C 4
5 (A d A d B d C) c (A d B d B d C) c (A d B d C) c (B d C d C)
Éli mi nons ensuite les termes tels que X d X 5 0 et rem pla çons X d X par X :
5 0 c 1 A d B d C 2 c 1 A d B d C 2 c 0
5 1 A d B d C 2 c 1 A d B d C 2 .
Le minterme A d B d C se code 100 ; A d B d C se code 010 .
On a donc :
5 m 4 c m 2 .
On peut obte nir de deux façons :
– ou bien, sous la forme d’une réunion de mintermes, en ne pre nant que ceux qui
n’appar tiennent pas à :
5 m 7 c m 6 c m 5 c m 3 c m 1 c m 0
– ou bien, sous la forme d’une inter sec tion de maxtermes, en pre nant le complé
men taire de l’expres sion de sous la forme d’une réunion de mintermes :
5 m 4 c m 2 5 m 4 d m 2 5 M 3 d M 5 5 1 A c B c C 2 d 1 A c B c C 2
(on observe, en effet, qu’en pre nant le complé men taire d’un minterme d’indice i on
obtient le maxterme d’indice 2
n 2 1 2 i).
Dans ces condi tions, on peut obte nir sous la forme d’une inter sec tion de maxtermes de deux façons, en effet, on a d’abord :
5 5 m 7 c m 6 c m 5 c m 3 c m 1 c m 0 5 M 0 d M 1 d M 2 d M 4 d M 6 d M 7 ,
puis, aussi bien :
5 , inter sec tion de tous les maxtermes, à l’excep tion de ceux qui figurent dans :
5 5 M 0 d M 1 d M 2 d M 4 d M 6 d M 7 .
18
Exemple. Soit la fonction booléenne , à trois variables A, B et C :
5 5 3 1 A d B2 c C 4 d 1 A d B2 6 c 3 1 B d C 2 d 1 A c C 2 4
Appli quons d’abord la for mule géné ra li sée de de Morgan :
5 5 3 1 A c B2 d C 4 d 1 A d B2 6 c 3 1 B d C 2 d 1 A c C 2 4
Déve lop pons ensuite en uti li sant la distributivité de l’opé ra tion d par rap port à l’opé -
ra tion c :
5 5 3 1 A d C 2 c 1 B d C 2 4 d 1 A d B2 6 c 5 3 1 B d C 2 d A4 c 3 1 B d C 2 d C 46
5 3 1 A d C 2 d 1 A d B2 4 c 3 1 B d C 2 d 1 A d B2 4 c 3 1 A d B d C 2 c 1 B d C d C 4
5 (A d A d B d C) c (A d B d B d C) c (A d B d C) c (B d C d C)
Éli mi nons ensuite les termes tels que X d X 5 0 et rem pla çons X d X par X :
5 0 c 1 A d B d C 2 c 1 A d B d C 2 c 0
5 1 A d B d C 2 c 1 A d B d C 2 .
Le minterme A d B d C se code 100 ; A d B d C se code 010 .
On a donc :
5 m 4 c m 2 .
On peut obte nir de deux façons :
– ou bien, sous la forme d’une réunion de mintermes, en ne pre nant que ceux qui
n’appar tiennent pas à :
5 m 7 c m 6 c m 5 c m 3 c m 1 c m 0
– ou bien, sous la forme d’une inter sec tion de maxtermes, en pre nant le complé
men taire de l’expres sion de sous la forme d’une réunion de mintermes :
5 m 4 c m 2 5 m 4 d m 2 5 M 3 d M 5 5 1 A c B c C 2 d 1 A c B c C 2
(on observe, en effet, qu’en pre nant le complé men taire d’un minterme d’indice i on
obtient le maxterme d’indice 2
n 2 1 2 i).
Dans ces condi tions, on peut obte nir sous la forme d’une inter sec tion de maxtermes de deux façons, en effet, on a d’abord :
5 5 m 7 c m 6 c m 5 c m 3 c m 1 c m 0 5 M 0 d M 1 d M 2 d M 4 d M 6 d M 7 ,
puis, aussi bien :
5 , inter sec tion de tous les maxtermes, à l’excep tion de ceux qui figurent dans :
5 5 M 0 d M 1 d M 2 d M 4 d M 6 d M 7 .