Discrete Mathematics Solved PYQs & Complete Notes

Unit 1: Set Theory

Sets and Basic Operations

A Set is a well-defined collection of distinct objects. Sets are fundamental to all of mathematics and computer science.

Notation: Sets are written with capital letters: A, B, C. Elements inside curly braces: A = 5

Types of Sets:

• Empty Set (∅ or ) — set with no elements
• Singleton Set — exactly one element: 5
• Finite Set — countable elements: 3
• Infinite Set — uncountable: set of all natural numbers
• Universal Set (U) — contains all elements under discussion
• Power Set P(A) — set of all subsets of A; |P(A)| = 2^n

Set Operations:

| Operation | Symbol | Definition | Example (A=3, B=4) | |---|---|---|---| | Union | A ∪ B | All elements in A or B | 4 | | Intersection | A ∩ B | Elements in both A and B | 3 | | Difference | A − B | Elements in A but not B | 1 | | Complement | A' | Elements not in A (in U) | U − A | | Symmetric Diff | A ⊕ B | Elements in A or B but not both | 4 |

De Morgan's Laws (Very Important for Exams!):

• (A ∪ B)' = A' ∩ B'
• (A ∩ B)' = A' ∪ B'

Cardinality Formula:

|A ∪ B| = |A| + |B| − |A ∩ B|
|A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |B∩C| − |A∩C| + |A∩B∩C|

---

Unit 2: Relations

A Relation from set A to set B is a subset of the Cartesian product A × B.

Cartesian Product: A × B = {(a, b) | a ∈ A, b ∈ B}

If A = {1,2} and B = {a,b}, then A × B = {(1,a), (1,b), (2,a), (2,b)}

Properties of Relations on Set A:

| Property | Definition | Example | |---|---|---| | Reflexive | (a,a) ∈ R for all a ∈ A | "is equal to" | | Irreflexive | (a,a) ∉ R for all a ∈ A | "is less than" | | Symmetric | (a,b) ∈ R → (b,a) ∈ R | "is sibling of" | | Antisymmetric | (a,b) ∈ R and (b,a) ∈ R → a=b | "is ≤" | | Transitive | (a,b) ∈ R and (b,c) ∈ R → (a,c) ∈ R | "is ancestor of" |

Equivalence Relation: Reflexive + Symmetric + Transitive

Partial Order Relation (POSET): Reflexive + Antisymmetric + Transitive

Equivalence Classes: When an equivalence relation partitions a set into disjoint subsets, each subset is an equivalence class.

---

Unit 3: Functions

A Function f: A → B assigns exactly one element of B to each element of A.

• A is the Domain, B is the Codomain
• The actual set of output values is the Range (Range ⊆ Codomain)

Types of Functions:

| Type | Property | Example | |---|---|---| | Injective (One-to-One) | Different inputs → different outputs | f(x) = 2x | | Surjective (Onto) | Every element in codomain has a preimage | f(x) = x mod 2 on 1 | | Bijective | Both injective and surjective | f(x) = x+1 |

Composition: (f ∘ g)(x) = f(g(x)) — apply g first, then f.

Inverse Function f⁻¹: Exists only if f is bijective.

Pigeonhole Principle: If n+1 objects are placed in n holes, at least one hole has at least 2 objects. Used in proofs and algorithm analysis.

---

Unit 4: Mathematical Logic

Propositional Logic deals with statements that are either True (1) or False (0).

Logical Connectives:

| Symbol | Name | Meaning | |---|---|---| | ¬ | NOT | negation | | ∧ | AND | conjunction | | ∨ | OR | disjunction | | → | IMPLIES | conditional | | ↔ | IFF | biconditional |

Truth Table for Key Connectives:

| P | Q | P∧Q | P∨Q | P→Q | P↔Q | |---|---|---|---|---|---| | T | T | T | T | T | T | | T | F | F | T | F | F | | F | T | F | T | T | F | | F | F | F | F | T | T |

Note: P→Q is False ONLY when P is True and Q is False!

Tautology: Formula always True (e.g., P ∨ ¬P) Contradiction: Formula always False (e.g., P ∧ ¬P) Contingency: Sometimes True, sometimes False

Logical Equivalences (Important!):

De Morgan's: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q
             ¬(P ∨ Q) ≡ ¬P ∧ ¬Q
Implication: P → Q ≡ ¬P ∨ Q
Contrapositive: P → Q ≡ ¬Q → ¬P
Double Negation: ¬¬P ≡ P

---

Unit 5: Graph Theory

A Graph G = (V, E) consists of vertices V and edges E connecting them.

Types of Graphs:

| Type | Description | |---|---| | Simple Graph | No self-loops, no multiple edges | | Multigraph | Multiple edges between same vertices | | Directed (Digraph) | Edges have direction | | Weighted Graph | Edges have weights/costs | | Complete Graph Kₙ | Every vertex connected to every other | | Bipartite Graph | Vertices in two sets; edges only between sets |

Graph Terminology:

• Degree of vertex — number of edges incident to it
• Degree sum theorem: Sum of all degrees = 2|E| (every edge contributes 2 degrees)
• Path — sequence of vertices connected by edges
• Cycle — path that starts and ends at same vertex
• Connected Graph — path exists between every pair of vertices
• Tree — connected graph with no cycles; |E| = |V| − 1

Graph Representations:

1. Adjacency Matrix — 2D array; A[i][j] = 1 if edge exists

   • Space: O(V²)
   • Good for dense graphs

2. Adjacency List — array of lists

   • Space: O(V + E)
   • Good for sparse graphs

Eulerian and Hamiltonian Graphs:

| Concept | Condition | Traversal | |---|---|---| | Eulerian Circuit | All vertices have even degree | Visits every EDGE exactly once | | Eulerian Path | Exactly 2 vertices have odd degree | Visits every edge, different start/end | | Hamiltonian Circuit | No simple polynomial condition | Visits every VERTEX exactly once |

Planar Graph: Can be drawn in a plane without crossing edges. Euler's Formula for planar graphs: V − E + F = 2 (V=vertices, E=edges, F=faces)

Graph Coloring: Minimum colors needed to color vertices so no two adjacent vertices have same color = Chromatic Number χ(G).

• Trees: χ = 2 (bipartite)
• Odd cycles: χ = 3
• Complete graph Kₙ: χ = n

---

Unit 6: Combinatorics

Fundamental Counting Principle:

• Multiplication Rule: If event A can happen in m ways and event B in n ways, both can happen in m × n ways.
• Addition Rule: If events are mutually exclusive, total ways = m + n.

Permutations (Order matters!):

P(n, r) = nPr = n! / (n-r)!

Example: Arrange 3 books from 5: P(5,3) = 5!/2! = 60

Combinations (Order doesn't matter!):

C(n, r) = nCr = n! / [r!(n-r)!]

Example: Choose 3 students from 10: C(10,3) = 10!/(3!×7!) = 120

Binomial Theorem:

(x + y)ⁿ = Σ C(n,k) × xⁿ⁻ᵏ × yᵏ  (k from 0 to n)

Pascal's Triangle: C(n,r) = C(n-1,r-1) + C(n-1,r)

Inclusion-Exclusion Principle:

|A ∪ B| = |A| + |B| − |A ∩ B|

---

Solved PYQ Sample Questions

Q1 (2022): Prove that |A ∪ B| = |A| + |B| − |A ∩ B|

Proof: Every element counted in |A ∪ B| is in A, or B, or both. Elements in both sets get counted twice in |A| + |B|. So subtract |A ∩ B| once. ∎

Q2 (2022): If A = 3 and B = 4, find A⊕B

A⊕B = (A−B) ∪ (B−A) = 1 ∪ 4 = 4

Q3 (2023): In how many ways can 5 boys and 3 girls be arranged so no two girls are adjacent?

Step 1: Arrange 5 boys: 5! = 120 ways Step 2: Choose 3 gaps from 6 available gaps between/outside boys: P(6,3) = 6×5×4 = 120 Total = 120 × 120 = 14,400 ways

Q4 (2023): Check if the relation R = 1 on 3 is an equivalence relation.

• Reflexive: (1,1),(2,2),(3,3) ∈ R ✓
• Symmetric: (1,2) ∈ R and (2,1) ∈ R ✓
• Transitive: (1,2) and (2,1) → (1,1) ∈ R ✓ Yes, R is an equivalence relation.

Q5 (2024): A connected graph has 8 vertices and 15 edges. How many faces does it have?

Using Euler's formula: V − E + F = 2 8 − 15 + F = 2 F = 9 faces

---

Quick Revision Checklist

• Set operations and De Morgan's laws
• Cardinality of union formula
• 5 properties of relations (reflexive, irreflexive, symmetric, antisymmetric, transitive)
• Equivalence relation = Reflexive + Symmetric + Transitive
• Types of functions: injective, surjective, bijective
• Truth table for → (False only when T→F)
• De Morgan's logical laws
• Graph: degree sum theorem, Eulerian conditions
• Permutation vs Combination formulas
• Euler's formula V−E+F=2