1
Struc tureS
ordon néeS
Appli cA tionS
deS treilliS
et de l ’ Algèbre
de boole
en recherche
opé rA tion nelle
1.1 notionS Sur leS Struc tureS ordonnéeS
1
1.1.1 Rela tions. Rela tions binaires. Propriétés
On nomme rela tion tout sous-ensemble du « pro duit car té sien » de deux ou plu sieurs
ensembles.
Ainsi, R 5 5(a, b); 1 c, a2 ; 1 c, d 2 6 est par définition un sous- ensemble de :
5(a, a); (a, b); (a, g); (a, d ); (b, a); (b, b); (b, g); (b, d ); (c, a); (c, b); (c, g); (c, d )6,
qui n’est autre que le pro duit car té sien, noté A 3 B de A 5 5a, b, c6
par B 5 5a, b, g, d 6.
En par ti cu lier, une rela tion binaire sur un ensemble de Ε (ainsi que l’on dit par
abus de lan gage) est un sous- ensemble du pro duit E 3 E. Pre nons par exemple
E 5 5x, y, z6. Nous repré sen tons le pro duit car té sien sous forme d’un tableau :
1. Ce sous cha pitre ne consti tue qu’un rapide rap pel. Au cas où le lec teur vou drait appro fon dir
les ques tions concer nant les rela tions et les struc tures ordon nées, il pourra se repor ter à des livres
spé cia li sés.