《Discrete Mathematics II教学-华南理工》lattice.pptVIP

Lattice Theorem 11.2: Let S, *, ? is an algebraic system with two binary operations. operations * and ? satisfying the commutative, associative, and absorption laws. Then We can define a partial order ? on S, let S, ? be a lattice, and ?a, b∈S : a∧b = a ? b, a∨b = a?b. Theory of Lattice Proof:(1) First proof * and ? operation satisfy idempotent law in S. For ?a∈S: a * a = a * (a ? (a * a)) = a (absorption law) Similarly: a ? a = a (absorption law) So, * and ? operation are suitable for idempotent law. (2) Define a binary relation R on S, for ?a, b∈R , we can get a, b ∈ R ? a?b = b We can prove R is partial order on S, then let R denoted by ?. (proof omitted) (3) Prove S, ? constitute a Lattice, 【a, b ∈ ? ? a?b = b】 for ?a, b∈S , a ? (a ? b) = (a ? a) ? b = a ? b Similarly, b ? (a ? b) = a ? (b ? b) = a ? b So, a ? a ? b, b ? a ? b, that’s say, a ? b is the upper bound of {a, b}. Then, we prove that a ? b is the least upper bound of {a, b}. Suppose c is is the upper bound of {a, b}, then, a ? c = c and b ? c = c, then we can get (a ? b) ? c = a ? (b ? c) = a ? c = c Namely: a ? b ? c. By the arbitrary of c, we can get a ? b is the least upper bound of {a, b}. Then, we prove that a * b is the greatest lower bound of {a, b}. First proof: (a ? b) = b ? a * b = a a * b = a * (a ? b) = a (absorption law) Therefor, a * b = a ? a ? b，according to the previous proof, similarly, we can prove a * b is the greatest lower bound. Theory of Lattice According to Theorem 11.2, another equivalent definition of lattice can be given. Definition 11.3: Let S, *, ? is an algebraic system. Binary operations * and ? satisfying the commutative, associative, and absorption laws, Then S, *, ? constitutes a lattice. Theory of Lattice Question: Lattice requires meet the four laws, why this definition only point out three? Answer: there is also idempotent law. But idempotent l