Lesson 15 — Advanced

Top 50 Discrete Mathematics Questions

Ye hai wo 50 questions jo discrete maths mein sabse zyada poochhe jaate hain — GATE, CUET, B.Sc aur placements ke liye. Har answer ek line mein. Inhe padh lo — poore course ka rapid revision ek saath ho jaayega.

⏱ 20 min• Advanced• All lessons

Sets & Logic (Q1–Q12)

WHAT

Ye 50 questions poore syllabus ka map hain — sets, logic, counting, graphs aur algebra. Har ek previous lessons mein detail mein padha hai — yahan sirf rapid revision hai.

WHEN

Exam se ek raat pehle, interview se 10 minute pehle, ya weekly revision mein — bas padte jao, answer bol ke check karo.

WHERE

GATE, CUET, B.Sc exams, TCS NQT aur har CS interview — in 50 mein se questions ghoom ke aate hi rehte hain.

Pehla set — sets aur logic. Har answer ek line mein, agar atka toh us lesson par wapas jao:

Q1. Set ka size kaise likhte hain?   → |A| (cardinality)
Q2. |A ∪ B| = ?                     → |A| + |B| − |A ∩ B|
Q3. n-element set ke subsets?        → 2^n (power set)
Q4. Empty set ka size?               → 0
Q5. De Morgan: (A ∪ B)′ = ?          → A′ ∩ B′
Q6. p → q kab FALSE?                 → p TRUE, q FALSE
Q7. Tautology kya hai?               → har row TRUE (p ∨ ¬p)
Q8. p → q ka contrapositive?         → ¬q → ¬p
Q9. ¬∀x P(x) ≡ ?                    → ∃x ¬P(x)
Q10. 3 variables ki truth table rows → 8
Q11. Equivalence relation = ?        → reflexive + symmetric
                                        + transitive
Q12. 50 students, 12 months → min   → ⌈50/12⌉ = 5 ek mahine

Tip: Ye 12 questions sets-logic ka foundation hain. Har ek ka 1-line answer muh zubaan par hona chahiye — confidence badhta hai aur time bachta hai.

Counting & Recurrence (Q13–Q24)

Q13. 0! = ?                          → 1
Q14. P(n, r) = ?                     → n! / (n − r)!
Q15. C(n, r) = ?                     → n! / (r! (n − r)!)
Q16. C(5, 2) = ?                     → 10
Q17. 5 books arrange (shelf)         → 5! = 120
Q18. 6 log round table               → 5! = 120 ((n−1)!)
Q19. MISSISSIPPI arrangements        → 11!/(4!4!2!) = 34650
Q20. Kitne log → birthday collision  → 367 (366 din + 1)
Q21. A se B functions (|A|=m,|B|=n)  → n^m = |B|^|A|
Q22. Hanoi: T(n)=2T(n−1)+1, T(1)=1   → 2^n − 1
Q23. Fibonacci F(6) (F1=1,F2=1)      → 8
Q24. a_n=3a_(n−1)−2a_(n−2) ki        → r² − 3r + 2 = 0
   characteristic equation              (roots 1 aur 2)

Relations, Functions & Graphs (Q25–Q38)

Q25. |A × B| = ?                     → |A| × |B|
Q26. A→B relations kitne (m,n)?      → 2^(mn)
Q27. Reflexive ka matlab?            → har (a,a) ∈ R
Q28. Antisymmetric?                   → (a,b)&(b,a) → a=b
Q29. Injective ke liye condition?    → |A| ≤ |B|
Q30. Surjective?                      → codomain sab covered
Q31. Inverse function kab banta?     → bijection par
Q32. Graph G = ?                     → (V, E) — vertices+edges
Q33. Handshaking lemma                → Σ deg(v) = 2|E|
Q34. K5 mein edges?                   → 5×4/2 = 10
Q35. Euler circuit condition?         → connected + all even
Q36. Tree edges (n vertices)?         → n − 1
Q37. K4 ke spanning trees (Cayley)?   → 4^2 = 16
Q38. K(m,n) mein edges?               → m × n

GATE ka pattern: relation type wale questions mein 4-mark ka block aata hai — reflexive, symmetric, transitive teeno check karo.
Counting ka pattern: "total minus galat" — complement set socho, calculation chhoti ho jaati hai.
Graph ka pattern: degree-based questions mein handshaking se shuru karo — 10 second mein answer.

Boolean Algebra & Algebraic Structures (Q39–Q50)

Q39. ¬(A ∧ B) = ?                    → ¬A ∨ ¬B
Q40. Idempotent law: A ∨ A = ?        → A
Q41. 3-var K-map cells?               → 8
Q42. K-map group sizes?               → 1, 2, 4, 8 (2 ki power)
Q43. Group ke kitne axioms?           → 4
Q44. (Z, +) group?                    → HAAN (identity 0)
Q45. (Z, ×) group?                    → NAHI (2 ka inverse nahi)
Q46. Ring ki conditions?              → (R,+) abelian group,
                                          (R,×) semigroup,
                                          distributive
Q47. Field ka matlab?                 → commutative ring with
                                          unity + nonzero inverses
Q48. Z_5 field hai?                   → HAAN (5 prime hai)
Q49. Z_6 field hai?                   → NAHI (2 × 3 = 0)
Q50. Absorption law?                  → A ∨ (A ∧ B) = A

Final tip: In 50 mein se 30+ har CS exam mein ghoom ke aate hain. Roz 10 questions revise karo — 5 din mein sab yaad. Aur jo atke, us lesson mein jaake worked example dobara solve karo.

Exercise

Question: Handshaking lemma: Σ deg(v) = ? (2|E| / |E| / |V|)

Question: n elements wale set ke subsets kitne hote hain? (2^n / n^2 / n!)

Question: Group ke kitne axioms hote hain? Sirf number daalo.

Common mistakes

Sirf ratta, concept nahi: Ye answers concepts se aate hain. Agar base clear hai toh ratne ki zarurat nahi — khud bol paoge. Jo atka, us lesson par wapas jao.
Formula ka n aur r ulta: P(n, r) mein n hamesha total bada set hai, r chhota selection. C(15,11) = C(15,4) wali identity se calculation chhoti karo.
Last week mein naya topic shuru karna: Naya topic revision ke time nahi — sirf wahi jo aata hai, uski speed badhao. Naye mein time gaya toh purana bhi bhool jaayega.

Desi example: Exam se pehle 10-minute plan

Written test se pehle bus mein bas ye 5 formulas revise karo — is course ki poori power isi mein hai:

1. |A ∪ B| = |A| + |B| − |A ∩ B|,  subsets = 2^n
2. P(n,r) = n!/(n−r)!,   C(n,r) = n!/(r!(n−r)!)
3. p → q false sirf (T, F),   ¬∀ = ∃¬
4. Σ deg = 2|E|,   tree edges = n − 1
5. ¬(A∧B) = ¬A∨¬B,   group = 4 axioms
Bas — discrete maths exam ready!

Exam mapping (GATE / CUET / TCS)

GATE: poora syllabus — ye 50 se major questions cover ho jaate hain.
TCS NQT/aptitude: counting + sets se 4-6Q.
CUET/B.Sc: definitions aur proofs (induction, equivalence relation).
Trap: definitions exam mein exact wording poochhti hain — key terms (reflexive, bijection, tautology) exact rakho.

Lesson complete?

Course complete! Tumne discrete mathematics master kar liya — sets se groups tak. Ab DSA (graphs, trees, recursion) ya programming path pe jao — foundation strong hai.