UNIT III - LATTICES
Ordered Pair
Let A and B be any two sets, consider a pair (a, b) in which the first element a is from
A and the second element b is from B. Then (a, b) is called an ordered pair.
Relation
Consider the particular ordered pair of ( x, y) R where R is a relation which can be
defined as X RY which may be read as x related to y.
Equivalence Relation
A relation R defined on a set X is said to be equivalence relation if it satisfies the
following condition
i. Reflexive
ii. Symmetric
iii. Transitive
i) Reflexive
A binary relation R in a set X is said to be reflexive x x, then
(x, x) R that is, x R x
ii) Symmetric
A binary relation R in a set X is said to be symmetric x, y x, whenever
(x, y) R then <y, x> R that is, x R y then y R x.
iii) Transitive
A binary relation R in a set X is said to be transitive if x, y ,z x, whenever
(x, y) R and (y, z) R then (x, z) R that is, x R y and y R z then x R z.
iv) Anti Symmetric
A relation R in a set X is said to be anti symmetric if x, y x whenever x R y and
y R x then x = y.
Partial Ordered Relation (or) Partial Ordering
A relation R in a set X is said to be partial ordered relation or partial ordering if it
satisfies the following conditions
.
i. Irreflexive
ii. Anti Symmetric
iii. Transitive
Irreflexive
A relation R in a set X is said to be irreflexive if x x, <x, x> R.
Partial ordered set (or) Po set:
A set L on which a partial ordering is defined as less than or equal to is called partial
ordered set (or) Poset. It is denoted by .
Lower Bound
Let be a Po set and a,b L if there exist an element c L such that
then c is said to be lower bound for a and b.
Greatest lower Bound (GLB)
Let be a Poset and A L , any element x L is said to be greatest lower
bound for A, if x is the lower bound for A and where y is any lower bound for A.
Example
X = {-1, 0, 1, 2, 3, 4}
A= {0, 1}
LB= {0, -1}
GLB= {0}
Upper Bound
Let be a Po set and a,b L if there exist an element C L such that
then c is said to be upper bound for a and b.
Least Upper Bound (LUB)
Let be a Po set and A is containing A L , any element x L is said to be
greatest lower bound for A, if x is the lower bound for A and where y is any
lower bound for A.
Example
X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
A= {6, 7, 8}
UB= {8, 9, 10}
LUB= {8}
NOTE
Let A and B be any two elements in a po set if least upper bound and greatest upper
bound of A and B exist and it is denoted by
glb {a, b}= ( - meet or product)
lub {a, b}= ( - join or sum)
Lattice
A lattice is a poset in which every pair of element have least upper bound and greatest
lower bound.
Properties of Lattices
1) Idempotent law
i)
ii)
2) Commutative law
i)
ii)
3) Associative law
i)
ii)
4) Absorption law
i)
ii)
Theorem 1
Let be a lattice in which denote the operation of the meet and join
respectively for any element .
Prove that (or)
Let be a lattice for any element then the following are equivalent:
i)
ii)
iii)
Proof
Given : be a lattice and .
To Prove
i)
ii)
iii)
Proof of (i)
a b a b a
Assume that
To Prove
By definition,
from 1 and 2
a b a
Proof of (ii)
a b a a b b
Assume a b a
Consider,
a b a a b b
Proof of (iii)
a b b a b
Assume a b b
lub{a, b}=b
ub{a, b}=b
a b b a b
Theorem 2[ Isotonicity property]
In any lattice the operation and if then prove that
i.
ii.
Proof.
we know that
and
If and
as and 1
Proof of (i):
To prove
Consider
=
Proof of (ii):
To prove
consider
Theorem 3 (Inequality distributive law):
Let (L, ) be a lattice and for any a,b,c belongs to L(a,b,c L)
Prove that the following inequalities
i)a (b c)
Given
is a lattice and a,b,c L
To prove
i)a (b c)
Proof of (i)
To prove a (b c)
As and
As and b
As
From 2 and 3 4
From 1 and 4
is the upper bound of a and
is the upper bound of
Proof of (ii)
As
As
is the upper bound of a and b c
Theorem 4
In a lattice (L,≤) show that
i)
ii)
Given
Let (L,≤) be a lattice
To prove
i)
ii)
Proof of i)
As
As
From1 and 2
is the upper bound of and
Proof of (ii)
As
As
4
As
From 3,4&5
Similarly
Theorem 5
Let (L,≤) be a lattice a,b,c L then show that the following inequalities
i)
ii)
Given
(L,≤) be a lattice a,b,c L
To Prove
i)
ii)
Proof of( i):
To prove
WKT,
Given that
Consider
(By inequality distributive law)
Proof of (ii)
Given that
Consider, (By Theorem 3)
Theorem6.
Show that in a lattice a ≤ b and c ≤ d then a c≤b d
Given
Let (L,≤) be a lattice .
Given that a ≤ b and c ≤ d
To prove
a c≤b d
Proof
WKT a ≤ b and a b=b
As c ≤ d c d=c and c d=d
Consider, a c = (a b) (c d)
= a (b c) d (assosiative)
= a (c b) d (commutative)
a c = (a c) (b d) (assosiative)
Theorem 7
In a lattice if a≤b≤c then show that
i) a b=b*c
ii) (a b) (b c)=(a b) (a c)
Given
Let (L,≤) be a lattice and a≤b≤c.
To prove
i) a b=b c
ii) (a b) (b c)= (a b) (a c)
Proof
Wkt ,a≤b a b=a and a b=b
and b≤c b∗c=b and b c=c
and a≤c a∗c=a and a c=c
Proof (i)
To prove a b=b c
Consider, a b=b ;
Proof (ii)
(a b) (b c)= (a b) (a c)
LHS =(a b) (b c)
=a b (by 1)
=b
RHS=(a b)∗(a c)
=b∗c
=b
LHS=RHS
SOME SPECIAL LATTICES
CHAIN
A lattice (L,≤) is called a chain if ∀ a,b∈ L either a ≤ b or b ≤ a.
DISTRIBUTED LATTICE
A lattice (L,∗, ) is called a distributive lattice the operation ∗ and distribute over
each other
THEOREM 8
Every chain is a lattice
To prove: Every chain is a lattice
Let (L,≤) be a chain. ∀ a,b∈ L either a ≤ b or b ≤ a.
It is enough to prove every ordered pair have glb and lub .
Case (i):
Assume that a ≤ b
As a ≤ a and a ≤ b
a=lb
y definition,
B
As
= ub
b
y definition,
B
Case (ii) assume b ≤ a
As b ≤ a and b ≤ b
b=lb
By definition
As
= ub
a
y definition,
B
Therefore in both cases (a,b) have lub and glb.
Theorem 9
Every chain lattice is a distributive lattice ∀ a, b, c ϵ L
Given
Let (L, ≤) be a chain lattice.
Let a, b, c ϵ L
To prove
Let (L,≤) be a distributive lattice
Proof
Since (L,≤) be a chain lattice a ≤ b ≤ c or a ≥ b ≥ c
Case (i): let a ≤ b ≤ c
Wkt a ≤ b a b=a and a b=b
and b ≤ c b∗c=b and b c=c
and a ≤ c a∗c=a and a c=c
Proof of (i)
LHS=RHS
Proof of (ii)
LHS=RHS
Case(ii)
≥b≥a
Let c
Proof of (i)
Proof of (ii)
Theorem 10
Let (L,∗,⨁) be a distributive lattice and ∀ a,b,c ϵ L prove that
Given
Let (L,∗,⨁) be a distributive lattice and ∀ a,b,c ϵ L
(a∗b)=(a∗c) and (a⨁b)=(a⨁c)
To prove : b=c
Proof
Consider,
(associative)
(given)
(distributive)
(commutative)
(given)
(distributive)
(given)
Complemented lattice
A lattice is called complemented lattice, if every element of L has at least
one complement in L.
(i.e)
Note:
i) Demorgans’s law
i)
ii)
ii) Identity law
i)
ii)
iii) Null law
i)
ii)
iv) Involution law
Theorem 11
Show that the Demorgan’s law
i)
ii)
holds in a complemented, distributive lattice (Boolean algebra).
Given
Let be a complemented, distributive lattice
To prove
i)
ii)
Proof of (i)
It is enough to prove
a)
b)
Proof of (a)
Consider LHS =
Proof of (b)
L.H.S=
Proof of (ii)
It is enough to prove
a)
b)
Proof of (a)
L.H.S =
Proof of (b)
Theorem 12
Show that in a complemented , distributive lattice the following are equivalent.
Given
Let L be a complemented, distributed lattice
To prove
It is enough to prove
(i)
(ii)
(iii)
(iv)
Proof of (i)
wkt
Consider
Post multiply by on both sides
Proof of(ii):
Assume
Taking complement on both sides
Proof of (iii):
consider,
post multiply by on both sides
Proof of (iv):
Assume
(i.e)
Take complement on both sides
Theorem 13:
Simplify the Boolean expression
Given
Let L be a complemented and distributive lattice
To prove
Theorem 14
In a distributive lattice,
Given
Let L be a distributive lattice where a,b,c L.
To prove
Proof
Theorem 15:
In a complemented distributive lattice, if a b then show that
1.
2.
Given
Let L be a distributive lattice where a,b,c L
To prove
1.
2.
Proof
Proof of 1
Proof of 2
Modular lattice
A lattice (L, ) is said to be modular, if
Theorem 16
In a distributive lattice, show that if
Or show that a distributive lattice is modular.
Given
Let L be a distributive lattice where a,b,c L.
To prove
L is modular.
(i.e.),
Proof
Lattice has algebraic system:
Algebraic system
A lattice is an algebraic system (L, ) with two binary operations on L then the following
laws are satisfied
(i)Associative (ii) Commutative (iii) Absorption.
Sub lattice:
Let (L, ) be a lattice and let S is contained in L(S<=L) be a subset of L, the algebra (S,
) is a sub lattice of (L, ) if and only if S is closed under both the operations ( ).
Direct product of lattices:
Let (L, ) and (S, ) be a two lattices, the algebraic system (L S,.,+) which the binary
operations . and + on L S such that for any ordered pair (a1,b1) and (a2,b2) L S.
1.
2.
Is called the direct product of lattice (L, ), (S, , )
Theorem 17
Show that the direct product of any two distributive lattices is a distributive lattice.
Proof.
Let (L, ) and (S, , ) be two distributive lattice
Let (L S, .,+) be the direct product of L and S.
Let x,y,z L S.
Let
To prove L S is a distributive lattice
1.
2.
Proofof1.
Proof of 2.
L S is distributive lattice.
Hasse Diagram or Lattice Diagram
Every finite lattice can be pictured in a poset diagram is called Hasse diagram or lattice
diagram or partially ordered set diagram.
Example:
Let N be a positive integer and Sn be the set of all devices of n. Let denote the
divisibility relation , then the ordered pair (Sn, ) is a lattice.
1. Let N=6
S6={ 1,2,3,6}
(S6 , )
2.Let N=12, (S12 , )
S12 ={1,2,3,4,6,12 }
1.Draw the lattice diagram P (S,<=) where S = {a,b,c}
SOLUTION :
Let S = {a,b,c} be set of three elements
The partition of S be
P (S) = { {a} , {b} , {c} , {a,b} , {a,c} , {b,c} , {a,b,c} , { } }
Properties of lattice:
1. Absorption law
1.1.
1.2.
Proof of 1.1
Proof of 1.2
2. Commutative law:
2.1.
2.2.
Proof of 2.1
Proof of 2.2
3. Idempotent law:
3.1.
3.2.
Proof of 3.1 & 3.2
4. Identity law:
4.1.
4.2.
Proof of 4.1
Proof of 4.2
5. Null law:
5.1.
5.2.
Proof of 5.1
Proof of 5.2
