✅ UNIT 4 — POSET, LATTICES & BOOLEAN ALGEBRA (DISCRETE MATHEMATICS)

 

✅ UNIT 4 — POSET, LATTICES & BOOLEAN ALGEBRA

1. Poset

Partially Ordered Set
A pair (A, ≤) where relation is:

• Reflexive

• Anti-symmetric

• Transitive

Toset: Totally ordered set

Every pair comparable.

Woset: Well-ordered set

Totally ordered + every non-empty subset has least element.

---

2. Topological Sorting

Linear ordering of vertices of a DAG respecting dependencies.

---

3. Hasse Diagram

Graphical representation of a poset showing cover relations (without loops or direction).

---

4. Extremal Elements

• Minimum element

• Maximum element

• Minimal elements

• Maximal elements

---

5. Lattices

A poset where every pair has:

• Least Upper Bound (LUB / join ∨)

• Greatest Lower Bound (GLB / meet ∧)

Semi-lattice

Only meet or only join exists.

Properties

• Idempotent

• Commutative

• Associative

• Absorption laws

---

6. Types of Lattices

• Distributive lattice

• Modular lattice

• Boolean lattice (special case)

---

7. Boolean Algebra

Defined with two operations:

• AND (·)

• OR (+)

• NOT (')

Elements usually {0,1}.

Important Laws

• Identity

• Complement

• Idempotent

• Associative

• Distributive

• De Morgan’s laws

  $$(A+B)' = A'B' \quad ;\quad (AB)' = A' + B'$$