© Dunod – Toute reproduction non autorisée est un délit.
15
1.2 Repré sen ta tion ensembliste des algèbres de Boole
A c B 5 B c A
(Commu ta ti vité)
A d B 5 B d A
A c 1 B c C 2 5 1 A c B 2 c C
(Associativité)
A d 1 B d C 2 5 1 A d B 2 d C
A c A 5 A
(Idempotence)
A d A 5 A
A c 0 5 A
(Élé ments neutres)
A d 1 5 A
A c A 5 1
(Défi ni tion du complé ment)
A d A 5 0
A c 1 B d C 2 5 1 A c B 2 d 1 A c C 2
(Distributivité mutuelle)
A d 1 B c C 2 5 1 A d B 2 c 1 A d C 2
A d (A c B) 5 A 5 A c (A d B)
(Absorption)
consti tue une algèbre de Boole compre nant au moins deux élé ments, 0 et 1.
Dans cette algèbre on a, notam ment, les pro prié tés :
A 5 A (Involution de la complémentation)
A d B 5 A c B et A c B 5 A d B
(For mules de de Morgan)
On remarque que le deuxième axiome de cha cune des six paires d’axiomes
ci- dessus peut être obtenu à par tir du pre mier axiome de la paire, en chan geant tout
signe c en d, tout signe d en c et tout 0 en 1.
Les cor res pon dances :
c 4 d ; d 4 c ; 0 4 1
per mettent donc de pas ser d’un axiome quel conque à l’axiome qui lui cor res pond
dans la même paire. En appli quant les règles de la logique (en par ti cu lier deux des
axiomes de la liste : contra dic tion et tiers exclu), cette pro priété sera conser vée.
Ainsi, à toute pro priété géné rale, éta blie pour une algèbre de Boole, cor res pond une
pro priété duale, obte nue en effec tuant les échanges de sym boles indi qués ci- dessus.
1.2.7 Impli ca tion. Inclu sion
On remarque que l’opé ra tion d’inter sec tion cor res pond à la conjonc tion logique
« et », l’opé ra tion de réunion à la conjonc tion logique « ou » (inclusif) et la
complémentation à la néga tion.
On uti lise aussi en logique l’impli ca tion : la pro priété p implique la pro priété q,
et l’on écrit : p 1 q, si et seule ment si tous les élé ments qui véri fient la pro priété p
véri fient aussi la pro priété q. Dans ces condi tions, le sous- ensemble A(p) est inclus
dans le sous- ensemble B(q) et l’on écrit :
A ( B.
f
f
f
f
f
f
15
1.2 Repré sen ta tion ensembliste des algèbres de Boole
A c B 5 B c A
(Commu ta ti vité)
A d B 5 B d A
A c 1 B c C 2 5 1 A c B 2 c C
(Associativité)
A d 1 B d C 2 5 1 A d B 2 d C
A c A 5 A
(Idempotence)
A d A 5 A
A c 0 5 A
(Élé ments neutres)
A d 1 5 A
A c A 5 1
(Défi ni tion du complé ment)
A d A 5 0
A c 1 B d C 2 5 1 A c B 2 d 1 A c C 2
(Distributivité mutuelle)
A d 1 B c C 2 5 1 A d B 2 c 1 A d C 2
A d (A c B) 5 A 5 A c (A d B)
(Absorption)
consti tue une algèbre de Boole compre nant au moins deux élé ments, 0 et 1.
Dans cette algèbre on a, notam ment, les pro prié tés :
A 5 A (Involution de la complémentation)
A d B 5 A c B et A c B 5 A d B
(For mules de de Morgan)
On remarque que le deuxième axiome de cha cune des six paires d’axiomes
ci- dessus peut être obtenu à par tir du pre mier axiome de la paire, en chan geant tout
signe c en d, tout signe d en c et tout 0 en 1.
Les cor res pon dances :
c 4 d ; d 4 c ; 0 4 1
per mettent donc de pas ser d’un axiome quel conque à l’axiome qui lui cor res pond
dans la même paire. En appli quant les règles de la logique (en par ti cu lier deux des
axiomes de la liste : contra dic tion et tiers exclu), cette pro priété sera conser vée.
Ainsi, à toute pro priété géné rale, éta blie pour une algèbre de Boole, cor res pond une
pro priété duale, obte nue en effec tuant les échanges de sym boles indi qués ci- dessus.
1.2.7 Impli ca tion. Inclu sion
On remarque que l’opé ra tion d’inter sec tion cor res pond à la conjonc tion logique
« et », l’opé ra tion de réunion à la conjonc tion logique « ou » (inclusif) et la
complémentation à la néga tion.
On uti lise aussi en logique l’impli ca tion : la pro priété p implique la pro priété q,
et l’on écrit : p 1 q, si et seule ment si tous les élé ments qui véri fient la pro priété p
véri fient aussi la pro priété q. Dans ces condi tions, le sous- ensemble A(p) est inclus
dans le sous- ensemble B(q) et l’on écrit :
A ( B.
f
f
f
f
f
f