lattice

Discrete Mathematics

1. A lattice is a poset where every pair of elements has both a supremum and an infimum . Definition Lattice: A poset ( P,v ) is called a lattice, if for all x , y 2 P the subset {x, y} of P has a supremum and an infimum . The supremum of x and y is denoted by x t y and the infimum as x u y. Lattice 12/13/2015 1

2. Supremum : We say that A is  bounded above  if there is  b∈R  such that ∀ x∈A  ( x⩽b ). The number b is called Supremum  for A . Infimum : We say that A is  bounded below  if there is  c∈R  such that ∀ x∈A  ( x⩾c ). The number c is called an  Infimum  for A. Sunday, December 13, 2015 2 Supremum and an Infimum

3. (R,) is a lattice. If x, y 2 R, then sup{x, y} = max{x, y} and inf {x, y} =min{x , y }. If S is a set and P = P(S) the poset of all subsets of S with relation , then P is a lattice with u = \ and t = [. The poset (N, |) of natural numbers with order relation | is a lattice with the least common multiple as t and the greatest common divisor as u. 12/13/2015 3 Some Examples of Lattices

4. 12/13/2015 4 Diagram Example l X Y j t

5. Definition : The dual of a lattice Λ is the set Λˆ of all vectors x ∈ span(Λ) such that hx , yi is an integer for all y ∈ Λ . Ex- 12/13/2015 5 Dual Lattice

6. a  set of elements of a  lattice,  in which each subset  of two   elements has  a least upper bound and a  greatest lower   bound contained  in  the given  set . A lattice ( L ,∨,∧) is  distributive  if the following additional identity holds for all  x ,  y , and  z  in  L : -  x  ∧ ( y  ∨  z ) = ( x  ∧  y ) ∨ ( x  ∧  z ). 12/13/2015 6 Sub Lattice & Distributive Lattice

7. Modular Lattice: A  modular lattice is a   lattice  L=⟨L,∨,∧⟩ that satisfies the modular identity . identity : (( x∧z )∨y)∧z=( x∧z )∨( y∧ z ) Bounded Lattice: A bounded lattice is an algebraic structure , such that  is a lattice, and the constants   satisfy The element 1 is called the upper bound, or top of  and the element 0 is called the lower bound or bottom of . 12/13/2015 7

8. Definition : A  complemented lattice is a bounded  latticee  (with least elementt  0 and greatest elementt  1), in which every element  a  has a  complement , i.e. an element  b  satisfying  a  ∨  b  = 1 and  a  ∧  b  = 0. Complements need not be unique . 12/13/2015 8 Complemented Lattice

9. Partial order and lattice theory now play an important role in many disciplines of computer science and engineering . For example-> they have applications in distributed computing (vector clocks, global predicate detection), concurrency theory ( pomsets , occurrence nets), programming language semantics (fixed-point semantics), and data mining (concept analysis). They are also useful in other disciplines of mathematics such as combinatorics , number theory and group theory. In this book, I introduce important results in partial order theory along with their applications in computer science. The bias of the book is on computational aspects of lattice theory (algorithms) and on applications (esp. distributed systems). 12/13/2015 9 Lattice use in computer science

10. 12/13/2015 10

11. 12/13/2015 11

12. 12/13/2015 12

13. 12/13/2015 13

14. 12/13/2015 14