《Discrete Mathematics II教学-华南理工》Lection 15 Lattice boolean algebra.pptVIP

Let R be a partial order on a set A, and let R-1 be the inverse relation of R. Then R-1 is also a partial order. The poset (A, R-1) is galled the dual of the poset (A, R). whenever (A, ≤) is a poset, we use “≥” for the partial order ≤-1 Dual of a lattice: Let (L, ≤) be a lattice, then the (L, ?) is called dual lattice of (L, ≤). Note: Dual of dual lattice is original lattice. Note: In (L, ≤), if a ? b = c; a ? b = d, then in dual lattice (L, ?), a ? b = d; a ? b = c Principle of duality: If P is a valid statement in a lattice, then the statement obtained by interchanging meet and join everywhere and replacing ≤ by ? is also a valid statement. * Dual of a Lattice Example Fig. a shows the Hasse diagram of a poset (A, ≤), where A={a, b, c, d, e, f} Fig. b shows the Hasse diagram of the dual poset (A, ≥) * f d e b a c b a c d e f Some properties of dual of poset: The upper bounds in (A, ≤ ) correspond to lower bounds in (A, ≥) (for the same set of elements) The lower bounds in (A, ≤ ) correspond to upper bounds in (A, ≥) (for the same set of elements) Similar statements hold for greatest lower bounds and least upper bounds. Note: An element a of (A, ≤ ) is a greatest (or least) element if and only if it is a least (or greatest) element of (A, ≥ ) * Dual poset Bounded A lattice L is said to be bounded if it has a greatest element 1 and a least element 0 For instance: Example: The lattice P(S) of all subsets of a set S, with the relation containment is bounded. The greatest element is S and the least element is empty set. Example : The lattice Z+ under the partial order of divisibility is not bounded, since it has a least element 1, but no greatest element. Bounded Lattices * If L is a bounded lattice, then for all a in A 0 ≤ a ≤ 1 a ∨ 0 = a, a ∨ 1 = 1 a ∧ 0 = 0 , a ∧ 1 = a Note: 1(0) and a are comparable, for all a i