Day 03Part 16-Discrete mathematics – Concept of lattices and Complemented and Distributive lattices.

Day 03Part 16-Discrete mathematics – Concept of lattices and Complemented and Distributive lattices.

https://www.gyanodhan.com/video/7B4.%20GATE%20CSEIT/Discrete%20Mathematics%201/488.%20Day%2003Part%2016-Discrete%20mathematics%20-%20Concept%20of%20lattices%20and%20Complemented%20and%20Distributive%20lattices.mp4

 Discrete Mathematics – Lattices, Complemented & Distributive Lattices

 What is a Lattice?

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

Example:

• Set L = {1, 2, 3, 6} under divisibility relation.
• Join ( ∨ ) → Least Common Multiple (LCM).
• Meet ( ∧ ) → Greatest Common Divisor (GCD).

Graphically, lattices are represented using Hasse diagrams.

Types of Lattices:

1⃣ Bounded Lattice

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

• It has a Greatest Element (1 or Top).
• It has a Least Element (0 or Bottom).

2⃣ Complemented Lattice

A lattice is complemented if:

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

Example: Boolean Algebra Lattice

• Elements {0,1}
• Complement: 0’ = 1, 1’ = 0

3⃣ Distributive Lattice

A lattice (L, ∨, ∧) is distributive if it satisfies:

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

Example:

• The power set of a set (P(S), ⊆) forms a distributive lattice under union ( ∪ ) and intersection ( ∩ ).

 Summary

Lattice = A poset where each pair has LUB (∨) & GLB (∧).
Complemented Lattice = Bounded Lattice where each element has a complement.
Distributive Lattice = Lattice follows Distributive Laws.

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

Day 03Part 16-Discrete mathematics – Concept of lattices and Complemented and Distributive lattices.

Discrete Mathematics for Computer Science

DISTRIBUTIVE LATTICES FACT 1

Notes on Lattice Theory

LATTICES Download

Here is a concise explanation and study guide for:

---

Day 03 | Part 16 – Discrete Mathematics

Topic: Lattices, Complemented & Distributive Lattices

---

1. What is a Lattice?

A lattice is a partially ordered set (poset) in which every pair of elements has:

• A least upper bound (LUB) also called join (∨)

• A greatest lower bound (GLB) also called meet (∧)

Formal Definition:

A poset (L, ≤) is a lattice if ∀ a, b ∈ L:

• a ∨ b (join) exists

• a ∧ b (meet) exists

---

2. Types of Lattices

Bounded Lattice

• Has a least element (0) and greatest element (1)
  i.e., ∀ a ∈ L: 0 ≤ a ≤ 1

Complemented Lattice

• A bounded lattice where each element a has a complement a' such that:

  • a ∨ a’ = 1 (top element)

  • a ∧ a’ = 0 (bottom element)

Distributive Lattice

• A lattice is distributive if the operations ∨ and ∧ distribute over each other:

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

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

Boolean Lattice / Boolean Algebra

• A complemented distributive lattice

• Follows all properties of Boolean algebra
  Example: Power set of a set with union (∨), intersection (∧), and complement

---

3. Hasse Diagram and Examples

You can represent a lattice using a Hasse Diagram – where:

• Nodes = elements of the set

• Edges show the partial order

• Useful to visually test for lattice properties

Example: L = {1, 2, 3, 6} with divisibility

• 1 divides 2, 3, and 6

• 2 and 3 divide 6
  This forms a lattice with:

• Meet: GCD

• Join: LCM

---

4. Quick Properties to Remember

---

Tips to Crack GATE/UGC-NET MCQs

• Check if join and meet exist → Lattice

• Check for uniqueness of complement

• Use truth tables for Boolean lattice questions

• Draw Hasse diagrams for small sets

---

Want More?

I can provide:

• PDF Notes with examples & Hasse diagrams

• Practice MCQs on lattices (with solutions)

• Video explanation in Hindi or English

Let me know your preference!