Chapitre 1 • Structures ordonnées Applications des treillis
20
f A 1 x2 5 1   f B 1 x2 5 0
f A 1 x2 5 1   f B 1 x2 5 1
f A c B 1 x2 5 1
f A c B 1 x2 5 1
Figure 1.16
Cette fois, on remarque que l’on a :
f AcB 1 x2 5 f A 1 x2 1
# f B 1 x2
avec une règle spé ciale qui veut que : 1 1
#
1 5 1 (propriété d’idempotence).
Nous appel le rons cette opé ra tion la somme logique ; elle cor res pond à l’opé ra tion
ou, envi sa gée pré cé dem ment.
En résumé, sur l’ensemble {0, 1}, nous avons une opé ra tion unaire et deux opé ­
ra tions binaires, dont les tables sont données ci- dessous :
Négation logique
Produit logique
0
1
1
0
0
0
0
1
0
1
0
1
0
1
1
1
0
1
0
1
Somme logique




Nous uti li se rons en par ti cu lier ces opé ra tions en théo rie des graphes, lors de la
déter mi na tion de la « fer me ture tran si tive » d’un graphe.
Remarque.
L’élé ment 0 appa raît comme l’élé ment neutre de l’opé ra tion 1
# et le 1,
comme l’élé ment neutre de l’opé ra tion ? : 0 1
# a 5 a 1
#
0 et 1 # a 5 a # 1,
pour tout a P50, 16
Mais, faute de symé trique pour chaque élé ment, tant pour la somme logique
où 1 n’a pas de symé trique ( q xP50,16 tel que 1 1
# x 5 0) que pour le pro duit
logique où 0 n’a pas de symé trique ( q xP50,16 tel que 0 # x 5 1), les opé ra -
tions consi dé rées ne confèrent pas une struc ture de groupe à l’ensemble {0,1}.
C’est pour quoi l’on intro duit sou vent une nou velle opé ra tion appe lée somme
dis­ ­ jonc­ ­ tive ou encore somme modulo 2, telle que ;a, bP {0, 1} :
a ! b 5 a # b 1
# a # b.