Concept Notes
1. Sets
- Definition: A set is a well-defined collection of distinct objects.
- Representation: {1, 2, 3}, {a, b, c}
- Types of Sets:
- Empty Set (∅)
- Finite & Infinite Sets
- Subset, Proper Subset, Power Set
- Universal Set
- Set Operations:
- Union (A ∪ B): All elements in A or B
- Intersection (A ∩ B): Common elements
- Difference (A − B): Elements in A but not in B
- Complement (A′): Elements not in A
2. Relations
- A relation R from set A to set B is a subset of A × B.
- Types of Relations:
- Reflexive: (a,a) ∈ R ∀ a ∈ A
- Symmetric: (a,b) ∈ R ⇒ (b,a) ∈ R
- Transitive: (a,b),(b,c) ∈ R ⇒ (a,c) ∈ R
- Equivalence Relation: Reflexive + Symmetric + Transitive
- Partial Order: Reflexive + Antisymmetric + Transitive
3. Functions
- A function f: A → B is a relation where each element of A maps to exactly one element of B.
- Types:
- One-One (Injective): Different elements map to different elements
- Onto (Surjective): Every element in codomain is mapped
- Bijective: Both injective & surjective
- Composition of Functions: If f: A → B, g: B → C, then g∘f: A → C
⚙️ Formulas (QuickLaTeX format)
🔟 10 Most Expected MCQs – GATE 2026 Discrete Maths
Q1. If A = {1,2,3}, then |P(A)| = ?
A) 6
B) 7
C) 8
D) 9
Q2. n(A) = 10, n(B) = 15, n(A ∩ B) = 5. Then n(A ∪ B) = ?
A) 15
B) 20
C) 25
D) 30
Q3. Which of the following is an equivalence relation?
A) R = {(a,b) | a = b}
B) R = {(a,b) | a < b}
C) R = {(a,b) | a > b}
D) R = {(a,b) | a+b = 5}
Q4. Number of relations on a set A with |A| = 3 is:
A) 9
B) 27
C) 512
D) 64
Q5. Number of functions from A = {1,2} to B = {a,b,c} is:
A) 3
B) 6
C) 9
D) 8
Q6. A function f: A→B is bijective only if:
A) One-One only
B) Onto only
C) Both One-One and Onto
D) Neither
Q7. If f: A→B and g: B→C are bijections, then g∘f is:
A) Injection
B) Surjection
C) Bijection
D) None
Q8. The number of bijective functions from A to A, where |A| = 4, is:
A) 16
B) 24
C) 8
D) 32
Q9. Relation R = {(a,b) | a divides b} on set of natural numbers is:
A) Reflexive and Transitive only
B) Symmetric only
C) Antisymmetric only
D) None of these
Q10. If A and B are disjoint sets with n(A)=5 and n(B)=7, then n(A ∪ B) = ?
A) 12
B) 35
C) 2^12
D) 5×7
✅ Answer Key
| Q.No | Answer |
|---|---|
| 1 | C |
| 2 | B |
| 3 | A |
| 4 | C |
| 5 | C |
| 6 | C |
| 7 | C |
| 8 | B |
| 9 | A |
| 10 | A |
🧠 Explanations
- Power set cardinality = 2^3 = 8 → C
- n(A∪B) = 10+15-5 = 20 → B
- a=b relation is reflexive, symmetric, transitive → equivalence → A
- Number of relations = 2^(3^2) = 2^9 = 512 → C
- |B|^|A| = 3^2 = 9 → C
- Bijective ⇔ One-One + Onto → C
- Composition of bijections = bijection → C
- Bijective functions = n! = 4! = 24 → B
- “Divides” relation is reflexive (a|a), transitive, antisymmetric → but not symmetric. Answer = A
- If disjoint, n(A∪B) = 5+7 = 12 → A
🎯 Why This Practice Matters
- Sets, Relations, Functions are fundamental for Discrete Mathematics.
- Every year, GATE has 2–4 marks directly from these topics.
- Concepts of bijection, equivalence, and relations are building blocks for Automata, Graph Theory, and Probability.
- Strong understanding here helps in higher algorithms & TOC.
📲 CTA
👉 Join our GATE 2026 CSE Community for daily practice & mock tests:
@LearnNewThingsHub
