DIZNR INTERNATIONAL

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

Ali Seron Jason
 Ali Seron Jason

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

https://www.gyanodhan.com/video/7B4.%20GATE%20CSEIT/Discrete%20Mathematics%201/491.%20Day%2003Part%2013-Example%20based%20on%20lattice%20in%20discrete%20mathematics%20with%20all%20the%20basic%20concept.mp4

 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:

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

Hasse Diagram Representation:

mathematica
1 (Top)
|
0 (Bottom)

 Example 3: Distributive Lattice Check

A lattice is distributive if it satisfies:

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

 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

Here’s a detailed explanation for:

Day 03 – Part 13: Example-Based Learning on Lattices (Discrete Mathematics)

Topic: Example-Based Concepts of Lattices in Discrete Mathematics

Basic Concept Recap: What is a Lattice?

A lattice is a special kind of partially ordered set (poset) where:

For any two elements a and b, both:

must exist and be unique.

This means: A lattice allows for combining and comparing any two elements using ∨ and ∧ operations.

Example 1: Set of Divisors of 12

Let S = {1, 2, 3, 4, 6, 12}

Relation: a ≤ b if a divides b
This forms a partial order

Let’s Test Lattice Conditions:

Pick any two elements:

All such pairs satisfy meet and join → So S is a lattice.

Meet = GCD
Join = LCM

Hasse Diagram:

markdown
12
/ \
4 6
/ \ / \
2 3 |
\ | /
1

Example 2: Power Set of {a, b}

Let P = P({a, b}) = {∅, {a}, {b}, {a,b}}

Operations:

A B A ∪ B A ∩ B
∅ {a} {a} ∅
{a} {b} {a,b} ∅
{a} {a,b} {a,b} {a}

Every pair has union and intersection
So this is a lattice

Distributive and Complemented?

Hence, this is a Boolean lattice

Quick Properties Summary

Type Condition Example
Lattice ∀ a,b: a ∧ b and a ∨ b exist Divisors of 12
Bounded Lattice Has 0 and 1 (min and max) Power set of {a,b}
Complemented Each element has complement (a ∧ a′ = 0, a ∨ a′ = 1) Power set or Boolean algebra
Distributive ∧ and ∨ distribute over each other Power set, numeric min/max
Boolean Lattice Distributive + Complemented Power set of any set

Practice Questions

  1. Is the set {1, 2, 3, 5, 15} under divisibility a lattice?

  2. Draw Hasse diagram of power set P({x, y, z}) and show if it’s a Boolean lattice.

  3. Show with example whether lattice {0, 1, 2} with min/max forms distributive lattice.

Need More Help?

I can send:

Would you like me to prepare a diagram worksheet or animated explanation as well?

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