Definitia 1. Fie L o multime nevida. O relatie binara ,,?’’ pe L este relatie de ordine daca urmatoarele conditii sunt verificate pentru orice a, b, c ? L: i) a ? a (reflexivitatea); ii) a ? b si b ? c ? a ? c (tranzitivitatea); iii) a ? b si b ? a ? a = b (antisimetria). Definitia 2. O multime L pe care s-a definit o relatie de ordine ,,?’’se numeste multime ordonata si se noteaza (L, ?)
Definitia 3. O multime ordonata (L, ?) se numeste latice daca pentru orice x, y ? L exista: sup {x, y} = x ? y si inf {x, y} = x ? y. Propozitia 4. Fie multimea (L, ?) o latice. Operatiile ? si ? au urmatoarele proprietati: 1) idempotenta: a ? a = a 1’) a ? a = a 2) comutativitatea: a ? b = b ? a 2’) a ? b = b ? a 3) asociativitatea: a ? (b ? c) = (a ? b) ? c 3’) a ? (b ? c) = (a ? b) ? c 4) absortia: a ? (a ? b) = a 4’) a ? (a ? b) = a
Demonstratie.
3) (a? b) ? c = sup{sup{a, b}, c}
a ? (b ? c) = sup{a, sup{b, c}}
sup{sup{a, b}, c} ? sup{a, b} ? b
sup{sup{a, b}, c} ? c ? sup{sup{a, b}, c} ? sup{b, c}. Cum
sup{sup{a, b}, c} ? a, atunci sup{sup{a, b}, c} ? sup{a, sup{b, c}}.
Analog si cealalta inegalitate.
4) Avem ca sup{a, inf{a, b}} = a, dar sup{a, inf{a, b}} ? a.
Reciproc, a ? a si a ? inf{a, b} ? a ? sup{a, inf{a, b}}. Relatiile 1’), 2’), 3’), 4’) se
demonstreaza in mod analog. Demonstrarea lor ramane ca tema la seminar.
Observatia 5.
Cele opt conditii demonstrate nu sunt independente, deoarece idempotenta este o
consecinta a absorbtiei. De exemplu, sa presupunem ca
a ? (a ? b) = a si a ? (a ? b) = a, atunci a ? a = a ? [a ? (a ? b)] din 4’).
Notand a ? b = c, avem a ? a = a ? (a ? c) = a din 4).
Fie o latice (L, ?, ?). Putem defini o relatie de ordine partiala ? pe L astfel:
2
x ? y daca x = x ? y ? x, y ? L,
sau, echivalent:
x ? y daca y = x ? y, ? x, y ? L.
Legile definite pentru absortie ne asigura ca definitiile sunt echivalente si putem verifica
faptul ca relatia ? introdusa astfel, defineste legea de ordine partiala in care marginea
inferioara si cea superioara sunt date de operatiile ? si ?.
Laticele finite se pot reprezenta cu ajutorul unei diagrame. Daca x si y sunt
comparabile si intre ele nu mai exista alte elemente ale laticei, atunci nodurile x, y se
unesc printr-o linie neorizontala, astfel incat daca x < y, x sa fie situat sub y.
Multimea ordonata a carei diagrama este data in figura 1 este o latice.
De exemplu: sup{a3, a4} = a5 si inf{a3,a4} = a1.
Fig.1
Exemple.
