Unit 2 Lattice Lecture Notes PDF

Unit 2 Department of ICT Unit no 2 “Lattice” Discrete Mathematics and Lattice Graph theory Prof. Foram  Topics  Different types of Relations  Partially ordered set  Totally ordered set...

Unit 2 Department of ICT Unit no 2 “Lattice” Discrete Mathematics and Lattice Graph theory Prof. Foram  Topics  Different types of Relations  Partially ordered set  Totally ordered set  Hasse diagram  Lattice as Partially ordered set  Properties of lattices  Lattice as an algebraic system  Different types of Relations Power Set :  Power set of set A is the collection of all subset of A. It is denoted by P( A ).  Example : A = { 1, 2, 3 } Then P(A) = { Φ, {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, A}  Note: If A has n elements then P(A) has 2n elements. Product set:  For any set A, the collection of all possible order pair ( x, y ) where x and y are elements of A is called product set of A. It is denoted by AxA.  i.e. AxA = { (x, y) / x,y є A}  Example : A = { 1, 2 } Then AxA = { (1, 1), (1, 2), (2, 1), (2, 2) }  Different types of Relations Relation : For given set A, subset R of AxA is called relation on A. Example : If A = {a, b, c} then R = { (a, a), (a, b), (b, c) } is a relation on A. Here (a, b) є R it means a is related to b. It is denoted by aRb R1 = { (a, a), (b, b), (b, c) }, R2 = { (a, a), (c, b), (b, c) }, R3 = { (a, -a), (b, b), (b, -c) } here R1 and R2 are relation on A but R3 is not subset of AxA so R3 is not relation on A. Reflexive Relation : A relation R is called reflexive relation on set A if (a, a) є R for all a є A i.e. aRa for all a є A Example : If A = {a, b, c} then R = { (a, a), (b, b), (c, c) } is a reflexive relation on A. R1 = { (a, a), (b, b), (b, c) } is not a reflexive relation on A because (c, c) is not in R1  Different types of Relations Example: Check whether the following relations on Z are reflexive or not. 1) xRy if | x – y | = even number For integer a, | a – a | = 0 = even number Therefore R is reflexive relation on Z. 2) xRy if xy ≥ 0 For integer a, aa = a2 ≥ 0 Therefore R is reflexive relation on Z. 3) xRy if xy < 0 For 2, 2*2 = 4 so 2 is not related to 2 Therefore R is not reflexive relation on Z.  Different types of Relations Symmetric relation: A relation R is called symmetric relation on set A if (a, b) є R for a, b є A then (b, a) є R i.e. if aRb then bRa for all a, b є A Example : If A = {a, b, c} then R = { (a, b), (b, a), (c, c) } is a symmetric relation on A. R1 = { (a, b), (b, a), (b, c) } is not a symmetric relation on A because (c, b) is not in R1 Anti - Symmetric relation: A relation R is called Anti - symmetric relation on set A for a, b є A a≠b if (a, b) є R then (b, a) is not in R i.e. for a, b є A a≠b if aRb then b is not related to a. Example : If A = {a, b, c} then R = { (a, b), (a, c), (b, b) } is Anti - symmetric relation on A. R1 = { (a, b), (b, a), (b, c) } is not anti symmetric relation on A because (a, b), (b, a) є R  Different types of Relations Example: Check whether the following relations on Z Example: Check whether the following relations on Z are symmetric or not. are anti symmetric or not. 1) xRy if | x – y | = even number 1) xRy if | x – y | = even number For integers x, y, if xRy then | x – y | = even For integers x, y, if xRy then | x – y | = even number number ⸫ | y – x | = even number ⸫ | y – x | = even number ⸫ yRx ⸫ yRx Therefore R is not anti symmetric relation on Z. Therefore R is symmetric relation on Z. 2) xRy if x ≥ y 2) xRy if x ≥ y For integers x, y, if xRy then x ≥ y For integers x, y, if xRy then x ≥ y ⸫ y can't be greater than x ⸫ y can't be greater than x ⸫ y is not related to x ⸫ y is not related to x Therefore R is anti symmetric relation on Z. Therefore R is not symmetric relation on Z.  Different types of Relations Example: On the set A = { 1, 2, 3, 4 } define Example: A = Set of all males 1. Relation R which is symmetric but not anti symmetric R = { (x, y) / x is brother of y } relation on A 2. Relation R which is anti symmetric but not symmetric 3. Relation R which is both symmetric and anti If x is brother of y then y is also brother of x symmetric. ⸫ If xRy then yRx 4. Relation R which is neither symmetric nor anti symmetric. ⸫ R is symmetric Example: A = Set of all males Answer : R = { (x, y) / x is father of y } relation on A 1) R = { (1, 2), (2, 1), (3, 3) } If x is father of y then y can’t be father of x 2) R = { (1, 2), (2, 4), (3, 3) } ⸫ If xRy then y is not related to x 3) R = { (1, 1), (2, 2), (3, 3) } ⸫ R is anti symmetric 4) R = { (1, 2), (2, 1), (3, 4) }  Different types of Relations Transitive relation: A relation R is called transitive relation on set A if (a, b), (b, c) є R for a, b, c є A then (a, c) є R i.e. if aRb and bRc then aRc for a, b, c є A Example : If A = {a, b, c} then R = { (a, b), (b, a), (a, a), (a, c), (b, c) } is not a transitive relation on A bcoz (b,b) is not in R. R1 = { (a, b), (b, c), (b, b) } is not a transitive relation on A because (a, c) is not in R1 Example: Check whether the following relations on Z are transitive or not. 1) xRy if | x – y | = even number For integers a, b, c if aRb and bRc then | a – b | = even number and | b – c | = even number ⸫ |a – c| = |a - b| + | b – c | = even number + even number = even number Therefore R is transitive relation on Z.  Different types of Relations 2) xRy if x ≥ y For integers a, b, c If aRb and bRc then a ≥ b and b ≥ c ⸫a≥c ⸫ aRb Therefore R is transitive relation on Z. 3) xRy if xy < 0 (-3)*2 = - 6 < 0 and 2*(-4) = -8 < 0 ⸫ -3R2 and 2R(-4) but (-3)*(-4) = 12 > 0 ⸫ -3 is not related to (-4) Therefore R is not transitive relation on Z.  Different types of Relations Equivalence relation: A relation R is called Equivalence relation on set A if R is Reflexive, Symmetric and Transitive relation on A Example : A = {a, b, c} and R = { (a, b), (b, a), (a, a), (a, c), (b, c), (b, b), (c, c), (c, b), (c, a) } is a relation on A Here R is reflexive R is symmetric R is transitive ⸫ R is an equivalence relation on A.  Different types of Relations Example: Check whether the following relations on Z are Equivalence relation or not. 1) xRy if | x – y | = even number For integer a, | a – a | = 0 = even number Therefore R is reflexive relation on Z. For integers a, b, if aRb then | a – b | = even number ⸫ | b – a | = even number ⸫ bRa Therefore R is symmetric relation on Z. For integers a, b, c if aRb and bRc then | a – b | = even number and | b – c | = even number ⸫ |a – c| = |a - b| + | b – c | = even number + even number = even number Therefore R is transitive relation on Z. Therefore R is equivalence relation on Z.  Different types of Relations 2) xRy if xy ≥ 0 For integer x, x*x = x2 ≥ 0 Therefore R is reflexive relation on Z. For integers x, y, if xRy then x y ≥ 0 ⸫ yx ≥ 0 ⸫ yRx Therefore R is symmetric relation on Z. For integers x, y, z if xRy and yRz then x y ≥ 0 and yz ≥ 0 but, x z ≥ 0 always, for example -2 ≥ 0 , 0 ≥ 3 but -2 ≥ 3 Therefore R is not transitive relation on Z. Therefore R is not Equivalence relation on Z.  Different types of Relations Example: A = Set of all integers, R = { (x, y) / x2 = y2 } relation on A Solution: For integers a, b, c if aRb and bRc then For any integer , we can say that: and Therefore R is reflexive relation on A. ⸫ For integers a, b, if aRb then ⸫ ⸫ Therefore R is transitive relation on A. ⸫ bRa Therefore R is symmetric relation on A. Therefore R is equivalence relation on A.  Different types of Relations Example: A = Set of all males , R = { (x, y) / x is father of y } relation on A Solution: For any in the set of all males, we can say that, is definitely not father of himself i.e, Therefore R is not a reflexive relation on A. Therefore R is not an equivalence relation on A.  Different types of Relations Example: A = {a, b, c}, xRy if x is subset of y for x, y є P(A) Solution: Here, P(A)= For any set , we can say that: Therefore R is reflexive relation on A. Let us consider two sets, and Such that: But, Therefore R is not symmetric relation on A. Therefore R is not an equivalence relation on A.  Different types of Relations (For Practice) Example: Check R is equivalence relation on real numbers, if for real numbers  Partially ordered set Partially ordered set (POSET): If R is a relation on set A and R is reflexive, anti symmetric and transitive relation on A then (A, R) is called Poset. It is also denoted by < A, R > Example : If A = {a, b, c} then R = { (a, b), (b, b), (a, a), (a, c), (b, c), (c, c) } is a relation on A. Here R is reflexive on A R is anti symmetric on A R is transitive on A Therefore (A, R) is a Poset.  Partially ordered set Example: Check whether the (Z, ≤) is Poset or not For integer x, x ≤ x so that xRx ⸫ ≤ is reflexive relation on Z. For integers x ≠ y, if x ≤ y then y can’t be less than x ⸫ ≤ is anti symmetric relation on Z. For integers x, y, z, if x ≤ y and y ≤ z then x ≤ z ⸫ ≤ is transitive relation on Z. ⸫ (Z, ≤) is Poset.. Note: Sn is the set of positive divisor of n Like S12 = {1,2,3,4,6,12} D is a divides relation i.e. if a divides b then aDb Like 2D6, 5D30  Partially ordered set Example: Check whether the ( N, D ) is Poset or not where D is divides relation. For any x є N, x = 1*x , 1 є N ⸫ xDx ⸫ D is reflexive relation on N. For any x, y є N, x ≠ y, if xDy then y = x*z where z є N ⸫ y can’t divide x ⸫ D is anti symmetric relation on N. For x, y, z є N if xDy and yDz then y = m*x and z = n*y where m,n є N ⸫ z = n*y = n*(m*x) = (m*n)*x where m*n є N ⸫ xDz ⸫ D is transitive relation on N. ⸫ ( N, D) is Poset.  Partially ordered set Example: Prove that ( S60, D ) is Poset or not where D is divides relation Here, S60= {1,2,3,4,5,6,10,12,15,20,30,60} For x, y, z є N if xDy and yDz then y = mx and z = ny where For any x є S60, xDx m,n є N ⸫ D is reflexive relation on S60. ⸫ z = ny = n(mx) = nm(x) where nm є N For any x, y є N, x ≠ y, if xDy then y = kx where k є N ⸫ xDz Which implies, x =y where N ⸫ D is transitive relation on S60. ⸫ ⸫ D is anti symmetric relation on S60. ⸫ (S60, D) is Poset.  Partially ordered set HW: Prove that P(A),  is Poset where A = { a, b, c }  Totally ordered set Comparable elements : Let ( A, R) be a Poset. Two elements a, b є A, a ≠ b are called comparable if aRb or bRa Example : ( S18 , D) is a Poset. S18 ={ 1,2,3,6,9,18 } Here 2D6 so 2 and 6 are called comparable elements. But 2 does not divides 3 and 3 does not divides 2 So 2 and 3 are non comparable elements. Totally ordered set (TOSET) or Chain : A Poset ( A, R) is called Toset ( or Chain) if any two elements of A are comparable elements.  Totally ordered set Example : Check whether the ( N, ≤ ) is Toset or not For positive integer x, x ≤ x so that xRx ⸫ ≤ is reflexive relation on N. For positive integers x ≠ y, if x ≤ y then y can’t be less than x ⸫ ≤ is anti symmetric relation on N. For positive integers x, y, z, if x ≤ y and y ≤ z then x ≤ z ⸫ ≤ is transitive relation on N. ⸫ (N, ≤) is Poset. For any two positive integers x ≠ y, either x ≤ y or y ≤ x ⸫ Either xRy or yRx ⸫ x and y are comparable elements. ⸫ ( N, ≤ ) is Toset ( or Chain)  Totally ordered set Example : Check whether the ( S64, D ) is Chain or not Here S64 ={ 1,2,4,8,16,32,64} For any x є S64 , x = 1*x , 1 є N ⸫ xDx ⸫ D is reflexive relation on S 64. For any x, y є S64 , x ≠ y, if xDy then x = y*z where z є N ⸫ y can’t divides x ⸫ D is anti symmetric relation on S64. For x, y, z є S64 if xDy and yDz then y = m*x and z = n*y where m,n є N ⸫ z = n*y = n*(m*x) = (m*n)*x where m*n є N ⸫ xDz ⸫ D is transitive relation on S 64. ⸫ (S64 , D) is Poset. Now 1D2, 2D4, 4D8, 8D16, 16D32 and 32D64 ⸫ For any two elements of S x ≠ y, either xDy or yDx  Totally ordered set Example: Check whether the ( Z, ≤ ) is Toset or not Example: Check if ( S16, D ) is Toset or not where D is divides relation Example: Check whether the P(A), is  Chain or not where A = { a, b, c }  Hasse diagram Cover of an elements : Let ( A, R) be a Poset. For elements a, b є A, a ≠ b, b is called cover of a if aRb and there is no c є A such that aRc and cRb Example : Example : P(A),  is a Poset. A ={ 1,2,3 } ( S18 , D) is a Poset. S18 ={ 1,2,3,6,9,18 } Elements Cover of elements Elements Cover of elements Φ {1}, {2}, {3} 1 2,3 {1} {1,2}, {1,3} 2 6 {2} {1,2}, {2,3} {3} {1,3}, {2,3} 3 6,9 {1,2} A 6 18 {1,3} A {2,3} A 9 18 A -------- 18 ------  Hasse diagram Hasse diagram: Hasse diagram is a graphical representation of Poset elements. Each elements of Poset is represented by a dot and join by lines according to following rules 1) If b is cover of a then dot corresponding a appears below in the diagram than the dot corresponding to b. 2) The two elements a and b are connected by line segment if either a is cover of b or b is cover of a. Example : ( S18 , D) is a Poset. S18 ={ 1,2,3,6,9,18 } Elements Cover of elements 1 2,3 2 6 3 6,9 6 18 9 18 18 ------ ( S18 , D)  Hasse diagram Example : P(A),  is a Poset. A ={ 1,2,3 } Elements Cover of elements Φ {1}, {2}, {3} {1} {1,2}, {1,3} {2} {1,2}, {2,3} {3} {1,3}, {2,3} {1,2} A {1,3} A {2,3} A A --------  Hasse diagram Example : ( S72 , D) is a Poset. S72 ={ 1,2,3,4,6,8,9,12,18,24,36,72 } Elements Cover of elements 1 2,3 2 4,6 3 6,9 4 8,12 6 12,18 8 24 9 18 12 24,36 18 36 24 72 36 72 ( S72 , D) 72 -----  Hasse diagram HW : Draw the Hasse diagram of (1) (S36, D ) (2) ( S64, D ) (3) (S42, D ) (4)  Lattice as Partially ordered set Lower bound : Let (A, R) be a Poset and B is a subset of A then x є A is called lower bound of B if xRy for all y in B. Greatest Lower bound : Let (A, R) be a Poset and B is a subset of A then x є A is called greatest lower bound of B if (1) x is a lower bound of B (2) if a is any other lower bound of B then aRx Example : Let (N, ≤) be a Poset and B = {4,6,8,10} Lower bounds = 1, 2, 3, 4 Greatest lower bound = 4  Lattice as Partially ordered set Upper bound : Let (A, R) be a Poset and B is a subset of A then x є A is called upper bound of B if yRx for all y in B. Least upper bound : Let (A, R) be a Poset and B is a subset of A then x є A is called Least upper bound of B if (1) x is a upper bound of B (2) if a is any other upper bound of B then xRa Example : Let (N, ≤) be a Poset and B = {4,6,8,10} Upper bounds = 10, 11, 12, …… Least upper bound = 10  Lattice as Partially ordered set Lattice as Poset: Poset (A, R) is called lattice as Poset if glb(a, b) and lub(a, b) are in A for all elements a, b of A. i.e. (A, R) is a Poset and for all a, b є A , glb(a, b) є A and lub(a, b) є A Note : Let Poset (A, R) , for elements a, b є A , we denotes glb(a, b) = a  b and lub(a, b) = a  b Some standard relation and their glb(a, b) and lub(a, b) 1) D glb(a, b) = gcd(a, b) lub(a, b) = lcm(a, b) 2) ≤ glb(a, b) = min(a, b) lub(a, b) = max(a, b) 3)  glb a, b  a  b lub a, b  a  b  Lattice as Partially ordered set Example : Prove that ( S30, D ) is a lattice as Poset. Here first we prove that ( S30, D ) is Poset [prove that D is reflexive, anti symmetric and transitive relation on S30 ] Now we prove that for all a, b є S30 , glb(a, b) = gcd(a, b) and lub(a, b) = lcm(a, b) є S30 S30gcd(a, = {1,2,3,5,6,10,15,30} b) 1 2 3 5 6 10 15 30 lcm(a, b) 1 2 3 5 6 10 15 30 1 1 1 1 1 1 1 1 1 1 1 2 3 5 6 10 15 30 2 1 2 1 1 2 2 1 2 2 2 2 6 10 6 10 30 30 3 1 1 3 1 3 1 3 3 3 3 6 3 15 6 30 15 30 5 1 1 1 5 1 5 5 5 5 5 10 15 5 30 10 15 30 6 1 2 3 1 6 2 3 6 6 6 6 6 30 6 30 30 30 10 1 2 1 5 2 10 5 10 10 10 10 30 10 30 10 30 30 15 1 1 3 5 3 5 15 15 15 15 30 15 15 30 30 15 30 30 1 2 3 5 6 10 15 30 30 30 30 30 30 30 30 30 30  Lattice as Partially ordered set In the above two tables all elements are from S30. So that for all a, b є S30 , glb(a, b) = gcd(a, b) and lub(a, b) = lcm(a, b) є S30 ( S30, D ) is a lattice as Poset Example : Prove that ( N, ≤ ) is a lattice as Poset. Here first we prove that ( N, ≤ ) is Poset [prove that ≤ is reflexive, anti symmetric and transitive relation on N. ] Now we prove that for all a, b є N , glb(a, b) = min(a, b) and lub(a, b) = max(a, b) є N For any a, b є N, either a ≤ b or b ≤ a So that either min(a, b) = a, max(a, b) = b or min(a, b) = b, max(a, b) = a So in both case glb(a, b) = min(a, b) and lub(a, b) = max(a, b) є N ⸫ ( N, ≤ ) is a lattice as Poset.  Lattice as Partially ordered set Example : Example : Prove that ( N, D ) is a lattice as Poset. Example : Prove that ( S24, D ) is a lattice as Poset.  Properties of Lattice Properties of Lattice : Let (A, R) be a Lattice. 1) Idempotent law 2) Commutative law a  a a a  b b  a a  a a a  b b  a 3) Associative law 4) Absorption law (a  b)  c a  (b  c) a  (a  b) a (a  b)  c a  (b  c) a  (a  b) a  Lattice as an algebraic system Lattice : Let L be a non empty set and  and are two binary operations define on L. (L, , )Is called Lattice as an algebraic if L satisfied following properties For all a, b, c є L 1) Commutative a  b b  a, a  b b  a 2) Associative (a  b)  c a  (b  c), (a  b)  c a  (b  c) 3) Absorption a  (a  b) a, a  (a  b) a  Lattice as an algebraic system Example :Check whether the ( N, Min, Max ) is a lattice. For any a, b, c є N, a  b min(a, b) and a  b max(a, b) 1) Commutative property a  b min(a, b) min(b, a) b  a a  b max(a, b) m ax(b, a) b  a 2) Associative property (a  b)  c min(a, b)  c min(min(a, b), c) min(a, b, c) a  (b  c) a  min(b, c) min(a, min(b, c)) min(a, b, c)  (a  b)  c a  (b  c)  Lattice as an algebraic system (a  b)  c max(a, b)  c max(max(a, b), c) max(a, b, c) a  (b  c) a  max(b, c) max(a, max(b, c)) max(a, b, c)  (a  b)  c a  (b  c) 3) Absorption property For any a, b є N, either a ≤ b or b ≤ a For a b min(a, b) a, max(a, b) b  a  (a  b) a  max(a, b) a  b min(a, b) a and a  (a  b) a  min(a, b) a  a max(a, a) a For b a min(a, b) b, max(a, b) a  a  (a  b) a  max(a, b) a  a min(a, a) a and a  (a  b) a  min(a, b) a  b max(a, b) a ⸫ ( N, Min, Max ) is a lattice.  Lattice as an algebraic system Example : Prove that ( S30, GCD, LCM ) is a lattice Here S30 = {1,2,3,5,6,10,15,30}, for all a, b, c є S30 a  b gcd(a, b), a  b lcm(a, b) 1) Commutative property a  b gcd(a, b) gcd(b, a) b  a a  b lcm(a, b) lcm(b, a) b  a 2) Associative property (a  b)  c gcd(a, b)  c gcd(gcd(a, b), c) gcd(a, b, c) a  (b  c) a  gcd(b, c) gcd(a, gcd(b, c)) gcd(a, b, c)  (a  b)  c a  (b  c)  Lattice as an algebraic system (a  b)  c lcm(a, b)  c lcm(lcm(a, b), c) lcm(a, b, c) a  (b  c) a  lcm(b, c) lcm(a, lcm(b, c)) lcm(a, b, c)  (a  b)  c a  (b  c) 3) Absorption property For any a, b є S30 , there are four cases 1) a divides b i.e. b = ma a  b gcd(a, b) a and a  b lcm(a, b) b a  (a  b) a  b a a  (a  b) a  a a 2) b divides a i.e. a = mb a  b gcd(a, b) b and a  b lcm(a, b) a a  (a  b) a  a a a  (a  b) a  b a  Lattice as an algebraic system 3) a and b are co prime a  b gcd(a, b) 1 and a  b lcm(a, b) ab a  (a  b) a  ab gcd(a, ab) a a  (a  b) a  1 lcm(a,1) a 4) a and b has common factor m other than 1 a = mx and b = my where m,x,y are positive integers and m ≠ 1 a  b gcd(a, b) m and a  b lcm(a, b) mxy a  (a  b) a  mxy gcd(a, ay) a ( mx a) a  (a  b) a  m lcm(a, m) a ( mx a) ⸫ (S30, Min, Max ) is a lattice.  Lattice as an algebraic system Example : Prove that ( N, gcd, lcm ) is a lattice. Example : Prove that ( R, Min, Max ) is a lattice. Example :  Lattice as an algebraic system Sub Lattice : Let (L, , ) be a Lattice and S is subset of L then (S, , ) is a sub lattice of (L, , ) if glb and lub of elements of S are in S. i.e. for all a, b  S, a  b  S and a  b  S Example : Check whether the following subsets are sub lattice of lattice ( S24, GCD, LCM ) 1) A = {1,2,3,6} To prove that A is Sub lattice we draw tables of lub and glb gcd 1 2 3 6 lcm 1 2 3 6 1 1 1 1 1 1 1 2 3 6 2 1 2 1 2 2 2 2 6 6 3 1 1 3 3 3 3 6 3 6 6 1 2 3 6 6 6 6 6 6 Here all elements of this tables are from A ⸫ A is sub lattice of S24.  Lattice as an algebraic system 2) B = {1,2,3,8} Here 2  3 lcm(2,3) 6  B ⸫ B is not sub lattice of S24. Example : Check whether the following subsets are sub lattice of lattice ( N, GCD, LCM ) (1) A = { 1, 2, 5, 10 } (2) A = { 1, 2, 5, 7, 10, 14, 70 } Example : Check whether the following subsets are sub lattice of lattice (P(A), , ) where A {a, b, c} (1) S = {Φ,{a},{b},{a,b}} (2) T = {Φ,{a},{b},{c},{a,b},{a,c},A}  Lattice as an algebraic system Distributive lattice : A lattice (L, , ) is called distributive lattice if  and  satisfies distributive law i.e. a  (b  c) (a  b)  (a  c) a  (b  c) (a  b)  (a  c) Note : A  (B  C) (A  B)  (A  C) A  (B  C) (A  B)  (A  C) max(a, min(b, c)) min(max(a, b), max(a, c)) min(a, max(b, c)) max(min(a, b), min(a, c)) gcd(a, lcm(b, c)) lcm(gcd(a, b), gcd(a, c)) lcm(a, gcd(b, c)) gcd(lcm(a, b), lcm(a, c))  Lattice as an algebraic system Example : Prove that ( R, Min, Max ) is a distributive lattice. (R, min, max) is a lattice (to be proved) 4) Distributive property a  (b  c) max(a, min(b, c)) min(max(a, b), max(a, c)) (a  b)  (a  c) a  (b  c) min(a, max(b, c)) max(min(a, b), min(a, c)) (a  b)  (a  c) ⸫ ( R, Min, Max ) is a distributive lattice.  Lattice as an algebraic system Example : Prove that ( N, gcd, lcm ) is distributive lattice. Example :  Lattice as an algebraic system Bounded lattice : Lattice (L, , ) is called bounded lattice if glb(L) and lub(L) are exist in L. glb(L) is denoted by 0 element and lub(L) is denoted by I element Bounded lattice is denoted by (L, , , 0, I) Example: ( S24, GCD, LCM ) is lattice S24 = { 1,2,3,4,6,8,12,24} For all x є S24 1Dx and xD24 ⸫ glb(S24 ) = 0 element = 1 and lcm(S24 ) = I element = 24 ⸫ ( S24, GCD, LCM ) is bounded lattice  Lattice as an algebraic system Complement elements : Let (L, , , 0, I) be a bounded lattice then two elements a,b of L are called complement of each other if a  b 0 element and a  b I element Complement of a is denoted by a’ Complemented lattice : A bounded lattice (L, , , 0, I) is called complemented lattice if each element of L has complement in L. Complemented lattice is denoted by (L, , , ', 0, I) Example: Check whether the ( S24, GCD, LCM ) is Complemented lattice or not. S24 = { 1,2,3,4,6,8,12,24}, glb(S24 ) = 0 element = 1 and lcm(S24 ) = I element = 24 2  b 0 element and 2  b I element For 2 there is no element in S24 such that So 2 does not have complement therefore ( S24, GCD, LCM ) is not Complemented lattice  Lattice as an algebraic system Example : Check whether the is P(A), ,  Complemented lattice or not, where A= {a,b,c,d} First prove that P(A), ,  is lattice. Now Φ is subset of all elements of P(A) and all elements of P(A) are subset of A ⸫ 0 element = Φ and I element = A  ' A {d}' {a, b, c} {b, c}' {a, d} {b, c, d}' {a} {a}' {b, c, d} {a, b}' {c, d} {b, d}' {a, c} {a, b, d}' {c} ' ' ' ' {b} {a, c, d} {a, c} {b, d} {c, d} {a, b} {a, c, d} {b} {c}' {a, b, d} {a, d}' {b, c} {a, b, c}' {d} A '  All complements are in P(A) ⸫ P(A), ,  is complemented lattice.  Lattice as an algebraic system Example : Prove that ( S30, GCD, LCM ) is a Complemented lattice. Example : Check whether the ( S90, GCD, LCM ) is Complemented lattice or not Example : Check whether the ( S90, min, max ) is Complemented lattice or not  End of Unit no 2 “Lattice” Unit 2 Discrete Mathematics and Lattice Graph theory