Chapitre 1 • Structures ordonnées Applications des treillis
16
La rela tion d’inclu sion, que nous avons dési gnée par le sym bole ( , est une rela -
tion d’ordre (large) :
1) elle est réflexive, car, quel que soit p, on a : p 1 p, d’où :
A ( A ;
2) elle est tran si tive, car :
1 p 1 p et q 1 r 2 1 1 p 1 r 2 ,
d’où :
1 A ( B et B ( C 2 1 1 A ( C 2 ;
3) elle est anti sy mé trique, car si l’on a, à la fois : p 1 q et q 1 p, c’est que
A(p) 5 B(q),
d’où:
A ( B
et
B ( A
s 1 A 5 B.
Sur le dia gramme d’Euler Venn (figure 1.13), on remarque que, si A ( B :
A c B 5 B et A d B 5 A.
On ver rait faci le ment aussi que, si A ( B :
A c B 5 1 et A d B 5 0.
Ce sont là quatre expres sions équi va lentes de l’inclu sion :
1 A ( B2 3 A d B 5 A 3 A c B 5 B 3 A c B 5 1 3 A d B 5 0.
L’expression de p 1 q par A c B 5 1 est fréquemment employée en logique.
Remarque. Le fait d’écrire : p 1 p, c’est- à-dire que toute pro po si tion s’implique elle même, revient à for mu ler le prin cipe d’iden tité.
1.2.8 Formes cano niques
Au lieu de par ler de sous- ensembles A 1 , A 2 , c d’un réfé ren tiel, nous pour rons,
grâce au para graphe 1.2.6, par ler main te nant de variables A 1 , A 2 , c .
Soient n variables boo léennes (n, nombre fini) : A 1 , A 2 , A 3 , c , A i , c , A n .
Dési gnons par X i la variable A i sous l’un de ses deux aspects : A i (affir ma tif) ou A i
(néga tif). On appelle minterme de l’algèbre de Boole à n variables toute expres sion :
X 1 d X 2 d X 3 d c d X i d c d X n ,
où chaque variable figure sous un et un seul de ses aspects.
Dualement, on appelle maxterme toute expres sion de la forme :
X 1 c X 2 c X 3 c c c X i c c c X n ,
Figure 1.13
16
La rela tion d’inclu sion, que nous avons dési gnée par le sym bole ( , est une rela -
tion d’ordre (large) :
1) elle est réflexive, car, quel que soit p, on a : p 1 p, d’où :
A ( A ;
2) elle est tran si tive, car :
1 p 1 p et q 1 r 2 1 1 p 1 r 2 ,
d’où :
1 A ( B et B ( C 2 1 1 A ( C 2 ;
3) elle est anti sy mé trique, car si l’on a, à la fois : p 1 q et q 1 p, c’est que
A(p) 5 B(q),
d’où:
A ( B
et
B ( A
s 1 A 5 B.
Sur le dia gramme d’Euler Venn (figure 1.13), on remarque que, si A ( B :
A c B 5 B et A d B 5 A.
On ver rait faci le ment aussi que, si A ( B :
A c B 5 1 et A d B 5 0.
Ce sont là quatre expres sions équi va lentes de l’inclu sion :
1 A ( B2 3 A d B 5 A 3 A c B 5 B 3 A c B 5 1 3 A d B 5 0.
L’expression de p 1 q par A c B 5 1 est fréquemment employée en logique.
Remarque. Le fait d’écrire : p 1 p, c’est- à-dire que toute pro po si tion s’implique elle même, revient à for mu ler le prin cipe d’iden tité.
1.2.8 Formes cano niques
Au lieu de par ler de sous- ensembles A 1 , A 2 , c d’un réfé ren tiel, nous pour rons,
grâce au para graphe 1.2.6, par ler main te nant de variables A 1 , A 2 , c .
Soient n variables boo léennes (n, nombre fini) : A 1 , A 2 , A 3 , c , A i , c , A n .
Dési gnons par X i la variable A i sous l’un de ses deux aspects : A i (affir ma tif) ou A i
(néga tif). On appelle minterme de l’algèbre de Boole à n variables toute expres sion :
X 1 d X 2 d X 3 d c d X i d c d X n ,
où chaque variable figure sous un et un seul de ses aspects.
Dualement, on appelle maxterme toute expres sion de la forme :
X 1 c X 2 c X 3 c c c X i c c c X n ,
Figure 1.13