8 LATTICES
There are two ways to de?ne a lattice L. One way is to de?ne L in terms of a partially ordered set. Speci?cally, a lattice L may be de?ned as a partially ordered set in which inf (a, b) and sup(a, b) exist for any pair of elements
a, b ? L. Another way is to de?ne a lattice L axiomatically. This we do below.
Axioms De?ning a Lattice
Let L be a nonempty set closed under two binary operations called meet and join, denoted respectively by
? and ?. Then L is called lattice if the following axioms hold where a, b, c are elements in L:
[L1 ] Commutative law:
(1a) a ? b = b ? a (1b) a ? b = b ? a
[L2 ] Associative law:
(2a) (a ? b) ? c = a ? (b ? c) (2b) (a ? b) ? c = a ? (b ? c)
[L3 ] Absorption law:
(3a) a ? (a ? b) = a (3b) a ? (a ? b) = a
We will sometimes denote the lattice by (L, ?, ?) when we want to show which operations are involved.
Duality and the Idempotent Law
The dual of any statement in a lattice (L, ?, ?) is de?ned to be the statement that is obtained by interchanging
? and ?. For example, the dual of
a ? (b ? a) = a ? a is a ? (b ? a) = a ? a
Notice that the dual of each axiom of a lattice is also an axiom. Accordingly, the principle of duality holds;
that is:
Theorem 2 (Principle of Duality): The dual of any theorem in a lattice is also a theorem.
This follows from the fact that the dual theorem can be proven by using the dual of each step of the proof of the original theorem.
An important property of lattices follows directly from the absorption laws.
Theorem 3 (Idempotent Law): (i) a ? a = a; (ii) a ? a = a.
The proof of (i) requires only two lines:
a ? a = a ? (a ? (a ? b)) (using (3b))
= a (using (3a))
The proof of (ii) follows from the above principle of duality (or can be proved in a similar manner).
Lattices and Order
Given a lattice L, we can de?ne a partial order on L as follows:
a b if a ? b = a
Analogously, we could de?ne
We state these results in a theorem.
Theorem 4: Let L be a lattice. Then:
a b if a ? b = b
(i) a ? b = a if and only if a ? b = b.
(ii) The relation a b (de?ned by a ? b = a or a ? b = b) is a partial order on L.
Now that we have a partial order on any lattice L, we can picture L by a diagram as was done for partially ordered sets in general.
EXAMPLE 10 Let C be a collection of sets closed under intersection and union.
Then (C, ?, ?) is a lattice. In this lattice, the partial order relation is the same as the set inclusion relation. Figure 6 shows the diagram
of the lattice L of all subsets of {a, b, c}.
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .