离散数学英文DMAv7-9.1-6.ppt

Special Types of Lattices A lattice L is said to be bounded（有界的） if it has a greatest element I and a least element 0 Example 15 The lattice P(S) of all subsets of a set S, as defined in Example 1, is bounded. Its greatest element is S and its least element is ? If L is a bounded lattice, then for all a ? A, 0 ≤a≤I a∨0 = a a∧0 = 0 a∨I = I a∧I = a Theorem 5 Let L = {a1, a2, …, an} be a finite lattice. Then L is bounded. Proof The greatest element of L is a1∨a2∨…∨an, and its least element is a1∧a2∧…∧an Distributive lattice（分配格） A lattice is called distributive if for any elements a, b, and c in L we have the following distributive properties. a∧(b∨c) = (a∧b)∨(a∧c) a∨(b∧c) = (a∨b)∧(a∨c) If L is not distributive, we say that L is nondistributive nondistributive lattices The lattice shown in Figure 6.44 are nondistributive. a∧(b∨c) =a (a∧b)∨(a∧c)=b a∧(b∨c) =a (a∧b)∨(a∧c)=0 Theorem 6 A lattic L is nondistributive if and only if it contains a sublattice that is isomorphic to one of the above two lattices. Proof: omitted Complement（补元） Let L be a bounded lattice with greatest element I and least element 0, and let a ? L. An element a’ L is called a complement of a if a∨a’ = I and a∧a’ = 0 Note that 0’ = I and I’ = 0. An element a in a lattice need not have a complement, and it may have more than one complement. Example 20 The lattices in Figure 6.44 each have the property that every element has a complement. The element c in both cases has two complements, a and b. Theorem 7 Let L be a bounded distributive lattice. If a complement exists, it is unique. (11 ,12) (01 ,02) (11 ,a) (01 ,a) (11 ,b) (01 ,b) (01 ,12) (11 ,02) Proof Let a’ and a’’ be complements of the element a?L. Then a∨a’ = I, a∨a’’ = I, a∧a’ = 0, a∧a’’ = 0. Using the distributive laws, we obtain a’ = a’∨0 = a’∨(a∧a’’) = (a’∨a) ∧(a’∨a’’) = I∧(a’ ∨a’’) = a’∨a’’ Also a’’ = a’’∨0 = a’’∨(a∧a’)= (a’’∨a)∧(a’’∨a’) = I∧(a’’∨a’) = a’∨a’’ Hence a’ = a’’. Complemented（有补格） A lattic