© Dunod – Toute reproduction non autorisée est un délit.
11
1.2 Repré sen ta tion ensembliste des algèbres de Boole
n 5 p # q (où p et q sont des nombres pre miers dif fé rents). Pour la figure 1.6, il s’agi
rait du treillis des divi seurs de n 5 p # q # r # s (p, q, r, s pre miers) ; par exemple pour
n 5 210 5 2
1 # 3
1 # 5
1 # 7
1
. Cette isomorphie se tra duit par l’iden tité des deux dia -
grammes de Hasse. Une conséquence du théorème de Stone est que toute algèbre de
Boole comportant m atomes (donc finie) comporte 2
m
éléments.
1.2 repré Sen tA tion enSembliSte deS AlgèbreS de
boole. Appli cA tion à lA logique élé men tAire
1.2.1 Prin cipes de la logique aris to té li cienne
Soit un ensemble fon da men tal R, appelé réfé ren tiel, dont les élé ments sont sus cep -
tibles de pré sen ter cer taines pro prié tés. Étant donnée une pro priété p déter mi née, les
élé ments qui la véri fient forment le sous ensemble A(p) de R, que nous dési gne rons
plus briè ve ment par A. On connaît aussi le sous- ensemble A des élé ments de R qui
véri fient la pro priété nonp (ou, de manière équi va lente, n’ont pas la pro priété P).
C’est le complé men taire du sous- ensemble A. Un dia gramme d’Euler- Venn illustre
ces défi ni tions (figure 1.8). En logique clas sique, le prin cipe de non contradiction
enseigne qu’aucun élé ment ne peut, à la fois, véri fier et ne pas véri fier une pro
priété, c’est- à-dire pré sen ter, en même temps, la pro priété p et la pro priété non-p. Ce
prin cipe se tra duit, en mathéma tique, par le fait que A et A sont dis joints. Un autre
prin cipe de la logique aris to té li cienne, le prin cipe du tiers exclu, indique que l’on ne
trou vera jamais plus de deux classes en tri ant un ensemble d’élé ments par rap port à
une pro priété p : les uns, qui véri fient la pro priété p, consti tuent le sous- ensemble A
du réfé ren tiel; les autres, qui ont la pro priété non-p (ou de manière équi va lente, ne
véri fient pas la pro priété p), forment le complé men taire A de A. Si l’une de ces deux
classes est vide, l’autre se confond avec le réfé ren tiel.
Remarque. Si l’on prend le complé ment de l’ensemble A, soit
A, on retombe évi dem ment sur l’ensemble A.
La complémentation est dite, pour cette rai son, involutive.
1.2.2 Expres sion du prin cipe de non- contradiction
Consi dé rons main te nant une pro priété p, à laquelle cor res pond le
sous- ensemble A du référentiel R, et une pro priété q, à laquelle
cor res pond le sous- ensemble B de R. Si les deux pro prié tés ne
sont pas contra dic toires, il y aura des élé ments véri fiant à la fois
les deux pro prié tés. On aura donc, dans R (fig. 1.9) :
Figure 1.8
Figure 1.9
11
1.2 Repré sen ta tion ensembliste des algèbres de Boole
n 5 p # q (où p et q sont des nombres pre miers dif fé rents). Pour la figure 1.6, il s’agi
rait du treillis des divi seurs de n 5 p # q # r # s (p, q, r, s pre miers) ; par exemple pour
n 5 210 5 2
1 # 3
1 # 5
1 # 7
1
. Cette isomorphie se tra duit par l’iden tité des deux dia -
grammes de Hasse. Une conséquence du théorème de Stone est que toute algèbre de
Boole comportant m atomes (donc finie) comporte 2
m
éléments.
1.2 repré Sen tA tion enSembliSte deS AlgèbreS de
boole. Appli cA tion à lA logique élé men tAire
1.2.1 Prin cipes de la logique aris to té li cienne
Soit un ensemble fon da men tal R, appelé réfé ren tiel, dont les élé ments sont sus cep -
tibles de pré sen ter cer taines pro prié tés. Étant donnée une pro priété p déter mi née, les
élé ments qui la véri fient forment le sous ensemble A(p) de R, que nous dési gne rons
plus briè ve ment par A. On connaît aussi le sous- ensemble A des élé ments de R qui
véri fient la pro priété nonp (ou, de manière équi va lente, n’ont pas la pro priété P).
C’est le complé men taire du sous- ensemble A. Un dia gramme d’Euler- Venn illustre
ces défi ni tions (figure 1.8). En logique clas sique, le prin cipe de non contradiction
enseigne qu’aucun élé ment ne peut, à la fois, véri fier et ne pas véri fier une pro
priété, c’est- à-dire pré sen ter, en même temps, la pro priété p et la pro priété non-p. Ce
prin cipe se tra duit, en mathéma tique, par le fait que A et A sont dis joints. Un autre
prin cipe de la logique aris to té li cienne, le prin cipe du tiers exclu, indique que l’on ne
trou vera jamais plus de deux classes en tri ant un ensemble d’élé ments par rap port à
une pro priété p : les uns, qui véri fient la pro priété p, consti tuent le sous- ensemble A
du réfé ren tiel; les autres, qui ont la pro priété non-p (ou de manière équi va lente, ne
véri fient pas la pro priété p), forment le complé men taire A de A. Si l’une de ces deux
classes est vide, l’autre se confond avec le réfé ren tiel.
Remarque. Si l’on prend le complé ment de l’ensemble A, soit
A, on retombe évi dem ment sur l’ensemble A.
La complémentation est dite, pour cette rai son, involutive.
1.2.2 Expres sion du prin cipe de non- contradiction
Consi dé rons main te nant une pro priété p, à laquelle cor res pond le
sous- ensemble A du référentiel R, et une pro priété q, à laquelle
cor res pond le sous- ensemble B de R. Si les deux pro prié tés ne
sont pas contra dic toires, il y aura des élé ments véri fiant à la fois
les deux pro prié tés. On aura donc, dans R (fig. 1.9) :
Figure 1.8
Figure 1.9