Discrete Mathematics carries steady marks in GATE CSE and most questions reduce to a known formula or a careful logical step. This GATE-style set covers logic, relations and functions, counting, graph theory and basic group theory.
How to practise: read each question and tap the option you think is correct. You will see right away whether you got it, along with a short explanation, and your score is tracked at the bottom of the screen. This set has 15 questions.
Topics covered in this set
- Propositional and predicate logic
- Counting relations and functions
- Permutations, combinations and derangements
- Inclusion-exclusion and pigeonhole
- Planar graphs, trees and colouring
- Groups, subgroups and Lagrange's theorem
GATE CSE Discrete Mathematics MCQs with answers and explanations
Q1. Which formula is logically equivalent to ¬(p → q)?
a) p ∧ ¬q
b) ¬p ∨ q
c) ¬p ∧ q
d) p ∨ ¬q
Q2. Over any domain, which implication between the statements is always valid?
a) Neither direction is valid
b) Both directions are valid
c) ∃y ∀x P(x, y) → ∀x ∃y P(x, y)
d) ∀x ∃y P(x, y) → ∃y ∀x P(x, y)
Q3. How many binary relations are there on a set with 3 elements?
a) 256
b) 9
c) 64
d) 512
Q4. How many reflexive relations are there on a set with 3 elements?
a) 128
b) 64
c) 8
d) 512
Q5. How many equivalence relations are there on a set with 3 elements?
a) 5
b) 8
c) 6
d) 3
Q6. How many one-to-one functions are there from a 3-element set to a 4-element set?
a) 12
b) 24
c) 64
d) 81
Q7. How many onto functions are there from a 4-element set to a 3-element set?
a) 24
b) 54
c) 81
d) 36
Q8. How many derangements of 4 objects are there (permutations with no object in its original position)?
a) 8
b) 6
c) 12
d) 9
Q9. How many non-negative integer solutions does x₁ + x₂ + x₃ = 10 have?
a) 66
b) 45
c) 36
d) 120
Q10. How many integers from 1 to 100 are divisible by 2, 3 or 5?
a) 76
b) 74
c) 70
d) 80
Q11. What is the maximum number of edges in a simple connected planar graph with 10 vertices?
a) 27
b) 24
c) 30
d) 20
Q12. How many distinct labelled trees are there on 5 vertices?
a) 120
b) 60
c) 25
d) 125
Q13. What is the chromatic number of the cycle graph C₅?
a) 2
b) 4
c) 3
d) 5
Q14. A group has order 12. Which of these CANNOT be the order of one of its subgroups?
a) 6
b) 2
c) 5
d) 4
Q15. How many generators does the cyclic group (ℤ₁₂, +) have?
a) 6
b) 2
c) 12
d) 4
Quick revision notes
- ¬(p → q) ≡ p ∧ ¬q; ∃y∀x implies ∀x∃y, not the reverse.
- Relations on n elements: 2^(n²); reflexive: 2^(n² − n); equivalence relations = Bell number.
- Onto functions m → n by inclusion-exclusion; D₄ = 9.
- Planar simple graph: E ≤ 3V − 6; labelled trees: nⁿ⁻².
- Lagrange: subgroup order divides group order; ℤₙ has φ(n) generators.
Frequently asked questions
Are these GATE previous year questions?
No, they are original GATE-style practice questions written to the syllabus.
Which counting formulas should I memorise for GATE?
Number of relations and their special types, functions and onto functions, derangements, stars and bars, and inclusion-exclusion for two or three sets.
How do I check if a graph is planar in an exam?
First test E ≤ 3V − 6 (or E ≤ 2V − 4 if there are no triangles). If the bound fails, it is not planar; if it holds, look for a K₅ or K₃,₃ subdivision.
Comments
Post a Comment