Day 03Part 13-Example based on lattice in discrete mathematics with all the basic concept.

Day 03Part 13-Example based on lattice in discrete mathematics with all the basic concept.

 Examples Based on Lattice in Discrete Mathematics

 Recap: What is a Lattice?

A lattice is a partially ordered set (poset) (L, ≤) where every pair of elements has:
1️⃣ Least Upper Bound (LUB) → Join ( ∨ )
2️⃣ Greatest Lower Bound (GLB) → Meet ( ∧ )

Graphically, lattices are represented using Hasse diagrams.

 Example 1: Check if a Poset Forms a Lattice

Given Set: L={1,2,3,6}L = \{ 1, 2, 3, 6 \} under divisibility relation (|).

 We check LUB (Join) and GLB (Meet) for each pair.

Elements (a, b) Join (a ∨ b) = LCM Meet (a ∧ b) = GCD
(1,2) LCM(1,2) = 2 GCD(1,2) = 1
(2,3) LCM(2,3) = 6 GCD(2,3) = 1
(2,6) LCM(2,6) = 6 GCD(2,6) = 2
(3,6) LCM(3,6) = 6 GCD(3,6) = 3

✔ Since every pair has a Join ( ∨ ) and Meet ( ∧ ), this forms a lattice.

Hasse Diagram Representation:

markdown
6
/ \
2 3
\ /
1

 Example 2: Complemented Lattice Check

A lattice (L, ∨, ∧) is complemented if:

  • It is bounded (Has Top (1) and Bottom (0)).
  • Every element a has a complement a’ such that:
    • a ∨ a’ = 1
    • a ∧ a’ = 0

Boolean Algebra Example:
Elements {0,1} form a complemented lattice since:

  • 0’ = 1, 1’ = 0
  • 0 ∨ 1 = 1, 0 ∧ 1 = 0

Hasse Diagram Representation:

mathematica
1 (Top)
|
0 (Bottom)

 Example 3: Distributive Lattice Check

A lattice is distributive if it satisfies:

  • a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
  • a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)

Power Set Example: P(S)={∅,{a},{b},{a,b}}P(S) = \{ \emptyset, \{a\}, \{b\}, \{a, b\} \}

  • Operations:
    • Join ( ∨ ) = Union ( ∪ )
    • Meet ( ∧ ) = Intersection ( ∩ )

 Since power sets satisfy distributive laws, they form a distributive lattice.

Hasse Diagram Representation:

css
{a, b}
/ \
{a} {b}
\ /
∅ (empty set)

 Conclusion

Lattice: Poset where each pair has Join ( ∨ ) & Meet ( ∧ ).
Complemented Lattice: Has Top, Bottom & Complements.
Distributive Lattice: Satisfies Distributive Laws.

Would you like more solved problems or real-life applications of lattices?

Day 03Part 13-Example based on lattice in discrete mathematics with all the basic concept.

Discrete Mathematics for Computer Science

Notes on Lattice Theory

Leave a Reply

Your email address will not be published. Required fields are marked *

error: