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.
Contents
- 0.1 Examples Based on Lattice in Discrete Mathematics
- 0.2 Recap: What is a Lattice?
- 0.3 Example 1: Check if a Poset Forms a Lattice
- 0.4 Given Set: L={1,2,3,6}L = \{ 1, 2, 3, 6 \}L={1,2,3,6} under divisibility relation (|).
- 0.5 Example 2: Complemented Lattice Check
- 0.6 Example 3: Distributive Lattice Check
- 1 Conclusion
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:
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:
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:
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?