4.1 for teaching

LATTICE
UB,
LBHasse Diagram:
For
 Upper Bound element (if it exists) Let B be a

subset of a set A, an element 𝒙 ∈ 𝑨 is in the upper
bound of B if 𝒚, 𝒙 ∈ 𝑷𝒐𝒔𝒆𝒕 ∀𝒚 ∈ 𝑩.
subset of a set A, an element 𝒙 ∈ 𝑨 is in the

 Lower Bound element (if it exists) Let B be a
lower bound of B if 𝒙, 𝒚 ∈ 𝑷𝒐𝒔𝒆𝒕 ∀𝒚

∈ 𝑩.
LUB,
GLB
For Hasse Diagram:
∨, Disjunction: Minimum element in UB

 Least Upper Bound (LUB), Supremum, Join,
 Greatest Lower Bound(GLB), Infimum,
𝖠, Conjunction: Maximum element in LB

Meet,
LB, GLB, UB,
LUB
g
100
d f
50 20
e
10 4
25
c
b 2
5
a
1
1
2
In Fig 1: B= {d, g},
In Fig 2: B= {5, 10},
• LB(d, g)= {e, a, b, d}
• LB(5, 10)= {1, 5}
• GLB (d, g)= {d}
• GLB (5,10)= {5}
• UB (d, g) ={g}
• UB (5, 10) ={10, 50, 20, 100}
• LUB (d, g)= {g}
• LUB (5, 10)= {10}
In Fig 1: B= {e, f},
• LB(e,f) = {a, e}
• GLB (e,f)= {e}
• UB (e,f) ={g,f }
• LUB (e, f )= {f }
Lattice
 Meet Semi Lattice: In a poset if Meet (GLB)
exists for every pair of elements, then the
poset is called as meet semi lattice.
 Join Semi Lattice: In a poset if Join (LUB)

exists for every pair of elements, then the
poset is called as join semi lattice.
 Lattice: If a poset is both Meet semi lattice

and Join semi lattice then it is lattice.
Lattice or
Not? c f c d
f
e d e g
c
b
a
b
a
1 a
2 3
No Meet (GLB){a,b} Meet (GLB)
No Join (LUB) {c,d} No Join (LUB){c,d}
Meet
Not Lattice Not Lattice
Join
Lattice
LATTICE
PROPERTIES
Idempotent
𝒂 ∨ 𝒂 = 𝒂
Law Join, OR, Disjunction,
𝒂𝖠𝒂=𝒂
(LUB, Union)
Meet, AND, Conjunction,
(GLB, d
Intersection) c
 {b}𝒃 ∨ 𝒃 = 𝒃
 Let’s check with element {b,b}
{b} 𝒃 𝖠 𝒃 = 𝒃
 LUB
 GLB
 Yes, Lattice follows Idempotent property
Associative
𝒂∨𝒃
 Law ∨𝒄=𝒂∨
(𝒃 ∨ 𝒄)
c
b d
f
e
𝐛 ∨ 𝐞 = 𝐛 ∨ (𝐝
a
𝐛 = 𝐜; ∨ 𝐝 ∨ 𝐞)
 Let’s check with elements
∨𝐝 𝐜 =𝐜
 LHS:
Lattice𝐝follows
= 𝐜;Associative
∨ 𝒆 property
=𝐜
then
∨𝒆 𝐛∨
 RHS:
Yes,
then
Commutative
 𝒂 = (𝒃
∨ 𝒃 ∨ 𝒂)
Law
c
f
b d
𝐛 = (𝐝
a
𝐛 ∨ 𝐝 = 𝐜; ∨𝐝 ∨ 𝐛)
 Let’s check with elements
𝐝∨𝒃
 LHS:
= 𝐜;Lattice follows Commutative property

 RHS:
Yes,
Distributive
𝒂∨ 𝒃 𝖠 𝒄 = (𝒂 ∨
𝒃) 𝖠 (𝒂 ∨ 𝒄)
Law
e
a b f
c
 Let’s check with elements 𝐚 ∨ (𝐛 𝖠 𝐜) = (𝐚 ∨ 𝐛) 𝖠

(𝐚 ∨ 𝐜)
𝐛 𝖠 𝒄 =d; then 𝒂 ∨ 𝒅 = 𝒂
𝐚∨𝒃 = 𝐞; 𝐚 ∨ 𝒄 = 𝒆;
 LHS:
𝐞𝖠𝒆 =𝒆
 RHS:
then
Others
Similarly, for the following
Laws
• De-Morgan’s Law
• Identity Law
• Complement Law
• Involution Law
Lattice May or May Not follow the property!

TYPES OF
LATTICES
Lattice
Bounded Lattice Distributive Lattice

Complement Lattice
Bounded
 Upper Bound of Lattice(Maximum): In a
Lattice
lattice L, if there exist an element 𝑰, such that
∀𝒂 ∈ 𝑳, 𝒂 is related to 𝑰 (𝒂𝑹𝑰),
𝑰 is
then
called upper bound of the lattice.
 Lower Bound of Lattice (Minimum): In a

lattice L, if there exist an element 𝑶, such that
∀𝒂 ∈ 𝑳, 𝒂 is related to 𝑶 (𝒂𝑹𝑶), then𝑶
is called lower bound of the lattice.
 Bounded (Finite) Lattice : If a lattice L has both

upper bound 𝑰 and lower bound (𝑶), then that
lattice is known as bounded lattice.
Bounded
4 Lattice d
3
b c
2
a
1
(ii)
(i)
COMPLEMENTED
LATTICE DISTRIBUTIVE
LATTICE
Complemented and Distributive
Lattice
 Complemented Lattice (𝑪𝑳) A lattice L is said to
be complemented if ∀𝒂 ∈ 𝑳 must have atleast one
 Distributive Lattice (𝑫𝑳) A lattice L is said to be

complement (min one).
distributive if ∀𝒂 ∈ 𝑳 must have atmost one

complement (zero or max one).
How to find Complement in
Lattice?
Universal Set (𝕌) Upper Bound (𝑰)
Set Theory Lattice
Empty Set (∅) Lower Bound (𝑶)

𝐴 𝖴 𝕌= 𝕌 𝐴 ∨ 𝑰 =𝑰
𝐴∩𝕌=A 𝐴𝖠𝑰=A
𝐴𝖴∅=A 𝐴∨𝑂=A
𝐴∩∅= ∅ 𝐴𝖠𝑂=𝑂
𝑨 𝖴 𝑨= 𝕌 𝑨 ∨ 𝑨= 𝑰 [Join]
𝑨∩𝑨=∅ 𝑨 𝖠 𝑨 = 𝑶 ,𝑴𝒆𝒆𝒕-
𝕌= ∅ 𝑰=𝑶
∅ =𝕌 𝑶=𝑰
How to find Complement in
Lattice?
𝑨 𝖴 𝑨= 𝕌 𝑨 ∨ 𝑨= 𝑰 [Join]
Set Theory Lattice
𝑨∩𝑨=∅ 𝑨𝖠𝑨=
𝑶 ,𝑴𝒆𝒆𝒕-
𝕌= ∅ 𝑰=𝑶
∅ =𝕌 𝑶=𝑰
• if we take JOIN (∨), the answer is I and

If we find an element with which
•if we take MEET (𝖠), the answer is O,

Then, that element is the compliment
To Find Complement in
Lattice
 Complement Lattice: In a bounded lattice L, for
any element 𝒂 ∈ 𝑳, if there exist an element 𝒃
∈ 𝑳, such that 𝒂 ∨ 𝒃 = 𝑰 and 𝒂 𝖠 𝒃 = 𝑶 , then
that element 𝒃 is called complement of element 𝒂.
We can say that 𝒂 and 𝒃 are complement of each other.

OR
Find Complement in
= 𝑼 𝑳𝑩 = 𝑶 =
𝑰
Lattice
d
𝒂
b c
𝑶=
∅ 𝑼𝑩 = 𝑰 =
a
(i)
Check for Upper

𝒅 (Universal) and Lower
(empty)
𝒂∨𝒅=𝒅
𝒂𝖠𝒅=𝒂
[Join, LUB]
[Meet, GLB]
Hence, 𝒂 and 𝒅 are complement of each other.

Find Complement in
= 𝑼 𝑳𝑩 = 𝑶 =
𝑰
Lattice
d
𝒂
b c
𝑶=
∅ 𝑼𝑩 = 𝑰 =
a
(i)
Find complement
𝒅 for element 𝒃
𝒃 ∨ 𝒄 = 𝒅 [Join, LUB]
𝒃 𝖠 𝒄 = 𝒂 [Meet, GLB]
Hence, 𝐛 and 𝒄 are complement of
each other.
𝑫 or
𝑳 𝑪 ?
𝑳
d
b c
a
1
𝑫
𝑳
𝑪
𝑳
1.
a’=d
d’=a
b’=c
c’=d
THANK YOU
!

4.1 for teaching

Uploaded by

Copyright:

Available Formats

4.1 for teaching

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

4.1 for teaching

Uploaded by

Copyright:

Available Formats

LATTICE

 Upper Bound element (if it exists) Let B be a

subset of a set A, an element 𝒙 ∈ 𝑨 is in the

lower bound of B if 𝒙, 𝒚 ∈ 𝑷𝒐𝒔𝒆𝒕 ∀𝒚

∨, Disjunction: Minimum element in UB

 Greatest Lower Bound(GLB), Infimum,

𝖠, Conjunction: Maximum element in LB

 Join Semi Lattice: In a poset if Join (LUB)

 Lattice: If a poset is both Meet semi lattice

= 𝐜;Lattice follows Commutative property

 Let’s check with elements 𝐚 ∨ (𝐛 𝖠 𝐜) = (𝐚 ∨ 𝐛) 𝖠

Lattice May or May Not follow the property!

Bounded Lattice Distributive Lattice

 Lower Bound of Lattice (Minimum): In a

 Bounded (Finite) Lattice : If a lattice L has both

 Distributive Lattice (𝑫𝑳) A lattice L is said to be

distributive if ∀𝒂 ∈ 𝑳 must have atmost one

Empty Set (∅) Lower Bound (𝑶)

• if we take JOIN (∨), the answer is I and

•if we take MEET (𝖠), the answer is O,

We can say that 𝒂 and 𝒃 are complement of each other.

Check for Upper

Hence, 𝒂 and 𝒅 are complement of each other.

You might also like