This set covers sets, relations and functions, a scoring area in GATE CS, UGC NET and university Discrete Mathematics papers. It includes counting reflexive, symmetric and equivalence relations, checking relation properties, Hasse diagrams of posets, transitive closure, and counting one-one and onto functions. The questions use the counting formulas and property checks that examiners keep returning to, so the set is good revision before semester exams and placement written tests.
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 18 questions.
Topics covered in this set
- Set operations, power set and Cartesian product
- Reflexive, symmetric, antisymmetric and transitive relations
- Equivalence relations and partitions
- Partial orders and Hasse diagrams
- Counting relations and functions
- Injective, surjective and bijective functions
Discrete Mathematics MCQs with answers and explanations
Q1. How many binary relations can be defined on a set with 3 elements?
a) 64
b) 512
c) 9
d) 256
Q2. How many reflexive relations are there on a set with 4 elements?
a) 65536
b) 256
c) 4096
d) 1024
Q3. How many symmetric relations can be defined on a set with 3 elements?
a) 512
b) 8
c) 216
d) 64
Q4. How many equivalence relations exist on a set with 4 elements?
a) 16
b) 15
c) 24
d) 64
Q5. On A = {1, 2, 3}, consider R = {(1,1), (2,2), (3,3), (1,2), (2,3)}. Which property does R have?
a) Symmetry
b) Transitivity
c) Reflexivity
d) It is an equivalence relation
Q6. Which relation on the positive integers is a partial order but NOT a total order?
a) a R b iff a ≤ b
b) a R b iff a < b
c) a R b iff a ≡ b (mod 3)
d) a R b iff a divides b
Q7. How many functions are there from a set of 4 elements to a set of 3 elements?
a) 81
b) 64
c) 12
d) 24
Q8. How many onto (surjective) functions are there from a 4-element set to a 3-element set?
a) 81
b) 24
c) 36
d) 6
Q9. How many one-one (injective) functions are there from a 3-element set to a 5-element set?
a) 125
b) 10
c) 15
d) 60
Q10. Which function f: R → R is a bijection?
a) f(x) = x^3 + 1
b) f(x) = x^2
c) f(x) = e^x
d) f(x) = |x| - 1
Q11. Let f: A → B and g: B → C. If g ∘ f is injective, which statement must be true?
a) g is injective
b) f is injective
c) f is surjective
d) g is surjective
Q12. In the Hasse diagram of the positive divisors of 12 ordered by divisibility, how many edges are drawn?
a) 6
b) 8
c) 12
d) 7
Q13. Let A = {1, 2, 3, 4} and B = {3, 4, 5}. What is the symmetric difference A Δ B?
a) {1, 2, 5}
b) {3, 4}
c) {1, 2}
d) {1, 2, 3, 4, 5}
Q14. If |A| = 3 and |B| = 2, how many elements does the power set of A × B contain?
a) 6
b) 64
c) 32
d) 36
Q15. Let f: R → R be defined by f(x) = (2x + 3)/5. What is f^(-1)(x)?
a) (5x + 3)/2
b) 5/(2x + 3)
c) (5x - 3)/2
d) (2x - 3)/5
Q16. In a group of 60 students, 35 study Physics, 28 study Chemistry and 12 study both. How many study neither subject?
a) 9
b) 21
c) 12
d) 3
Q17. On {1, 2, 3, 4}, how many ordered pairs are in the transitive closure of R = {(1,2), (2,3), (3,4)}?
a) 3
b) 6
c) 5
d) 10
Q18. Which statement about an equivalence relation on a non-empty set A is correct?
a) Its equivalence classes form a partition of A
b) Two different equivalence classes may share some elements
c) It must be antisymmetric
d) It must contain every pair of A × A
Quick revision notes
- Relations on an n-set: 2^(n^2); reflexive: 2^(n^2 - n); symmetric: 2^(n(n+1)/2).
- Antisymmetric relations on an n-set: 2^n · 3^(n(n-1)/2).
- Equivalence relations on an n-set = Bell number B(n): 1, 2, 5, 15, 52, ...
- Functions from an m-set to an n-set: n^m; one-one (m ≤ n): n!/(n-m)!.
- Onto functions from m to n = Σ (-1)^k C(n,k)(n-k)^m.
- Partial order = reflexive + antisymmetric + transitive.
- If g ∘ f is one-one then f is one-one; if g ∘ f is onto then g is onto.
- |A ∪ B| = |A| + |B| - |A ∩ B|.
Frequently asked questions
How do I count equivalence relations on a finite set?
Every equivalence relation corresponds to exactly one partition of the set, so the count equals the Bell number B(n). For n = 1, 2, 3, 4, 5 these are 1, 2, 5, 15 and 52.
Can a relation be both symmetric and antisymmetric?
Yes. Any relation that is a subset of the diagonal {(a, a)}, including the empty relation, is both symmetric and antisymmetric.
When does a function have an inverse?
A function f: A → B has an inverse function exactly when it is a bijection, both one-one and onto. Then f^(-1): B → A undoes f and is itself a bijection.
Comments
Post a Comment