✅ 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'$$

✅ UNIT 3 — SET THEORY, RELATIONS & FUNCTIONS (DISCRETE MATHEMATICS)

 

✅ UNIT 3 — SET THEORY, RELATIONS & FUNCTIONS

A. Relations

Definition

A relation R from A to B is a subset of A×B.

Representation

• List of ordered pairs

• Matrix representation

• Directed graph

Operations

• Union

• Intersection

• Composition (R ∘ S)

• Inverse relation (R⁻¹)

Types of Relations

1. Reflexive: (a,a) ∈ R for all a

2. Symmetric: (a,b) ⇒ (b,a)

3. Transitive: (a,b) & (b,c) ⇒ (a,c)

4. Anti-symmetric

---

Counting Relations

If A has n elements:

Total possible relations =

$$2^{n^2}$$

---

Closure of Relations

• Reflexive closure = R ∪ {(a,a)}

• Symmetric closure = R ∪ R⁻¹

• Transitive closure = Add pairs until transitivity satisfied (Warshall)

---

Equivalence Relation

When R is:

• Reflexive

• Symmetric

• Transitive

Then A is partitioned into equivalence classes.

---

Partial Order Relation

R is:

• Reflexive

• Anti-symmetric

• Transitive

Forms a poset.

---

Power of a Relation

Rⁿ = R composed with itself n times.

---

Functions

Definition

A function f: A → B assigns each element in A to exactly one element in B.

Terms

• Domain

• Co-domain

• Range

Types

• One-one (Injective)

• Onto (Surjective)

• Bijective

• Constant

• Identity function

---

Counting Functions

From set A (m elements) to B (n elements):

$$n^m \text{ functions}$$

---

Inverse Function

Exists only for bijective functions.

---

Composition

If f: A→B and g: B→C
Then g∘f: A→C.

---

Group Theory (Basics)

A set G with binary operation * is a group if:

1. Closure

2. Associativity

3. Identity element

4. Inverse exists for all elements

If operation is commutative → Abelian group.

✅ UNIT 2 — COMBINATORICS (DISCRETE MATHEMATICS)

 

✅ UNIT 2 — COMBINATORICS

1. Permutations & Combinations

Permutation

Arrangement of objects where order matters.

• Formula:

  $$^nP_r = \frac{n!}{(n-r)!}$$

Example:
Number of ways to arrange 3 letters from ABCD
= $^4P_3 = 24$

Combination

Selection of objects where order does NOT matter.

• Formula:

  $$^nC_r = \frac{n!}{r!(n-r)!}$$

Example:
Choose 2 students from 5
= $^5C_2 = 10$

---

2. Summation

Properties of Σ:

• Linearity:
  $\sum (a_i + b_i) = \sum a_i + \sum b_i$

• Constant factor:
  $\sum c\cdot a_i = c\sum a_i$

---

3. Binomial Function

Binomial Theorem:

$$(a + b)^n = \sum_{k=0}^{n} {^nC_k a^{n-k} b^k}$$

Properties:

• Number of terms = n+1

• Middle term depends on n (odd/even)

• Coefficients symmetric:

  $$^nC_k = ^nC_{n-k}$$

---

4. Generating Functions

Used in recurrence and combinatorics.

Basic idea:

If we have sequence {a₀, a₁, a₂, …}
Generating function is:

$$G(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots$$

Example: For sequence 1,1,1,1,…

$$G(x) = \frac{1}{1 - x}$$

---

5. Recurrence Relation

Example: Fibonacci

$$f(n) = f(n-1) + f(n-2)$$

Solving Linear Recurrences

General form:

$$a_n = c_1 a_{n-1} + c_2 a_{n-2}$$

Steps:

1. Form characteristic equation

   $$r^2 - c_1 r - c_2 = 0$$

2. Find roots r₁, r₂

3. General solution:

   $$a_n = A r_1^n + B r_2^n$$