Category: Discrete Mathematics Objective Questions

Discrete Mathematics Multiple Choice Questions on “Types of Relations”.

1. The binary relation {(1,1), (2,1), (2,2), (2,3), (2,4), (3,1), (3,2)} on the set {1, 2, 3} is __________
a) reflective, symmetric and transitive
b) irreflexive, symmetric and transitive
c) neither reflective, nor irreflexive but transitive
d) irreflexive and antisymmetric

Answer: c
Clarification: Not reflexive -> (3,3) not present; not irreflexive -> (1, 1) is present; not symmetric -> (2, 1) is present but not (1, 2); not antisymmetric – (2, 3) and (3, 2) are present; not asymmetric -> asymmetry requires both antisymmetry and irreflexivity. So, it is transitive closure of relation.

2. Consider the relation: R’ (x, y) if and only if x, y>0 over the set of non-zero rational numbers,then R’ is _________
a) not equivalence relation
b) an equivalence relation
c) transitive and asymmetry relation
d) reflexive and antisymmetric relation

Answer: b
Clarification: Reflexive: a, a>0
Symmetric: if a, b>0 then both must be +ve or -ve, which means b, a > 0 also exists
Transitive: if a, b>0 and b, c>0 then to have b as same number, both pairs must be +ve or -ve which implies a, c>0. Hence, R’ is an equivalence relation.

3. Let S be a set of n>0 elements. Let be the number B_r of binary relations on S and let B_f be the number of functions from S to S. The expression for B_r and B_f, in terms of n should be ____________
a) n² and 2(n+1)²
b) n³ and n⁽ⁿ⁺¹⁾
c) n and n⁽ⁿ⁺⁶⁾
d) 2^(n*n) and nⁿ

Answer: d
Clarification: For a set with n elements the number of binary relations should be 2^(n*n) and the number of functions should be nⁿ. Hence B_r = 2^(n*n) and B_f = nⁿ.

4. Let A be a set of k (k>0) elements. Which is larger between the number of binary relations (say, N_r) on A and the number of functions (say, N_f) from A to A?
a) number of relations
b) number of functions
c) the element set
d) number of subsets of the relation

Answer: a
Clarification: For a set with k elements the number of binary relations should be 2^(n*n) and the number of functions should be nⁿ. Now, 2^(n*n) => n²log (2) [taking log] and nⁿ => nlog (n) [taking log]. It is known that n²log (2) > nlog (n). Hence, the number of binary relations > the number of functions i.e, N_r > N_f.

5. Consider the binary relation, A = {(a,b) | b = a – 1 and a, b belong to {1, 2, 3}}. The reflexive transitive closure of A is?
a) {(a,b) | a >= b and a, b belong to {1, 2, 3}}
b) {(a,b) | a > b and a, b belong to {1, 2, 3}}
c) {(a,b) | a <= b and a, b belong to {1, 2, 3}}
d) {(a,b) | a = b and a, b belong to {1, 2, 3}}

Answer: a
Clarification: By definition of Transitive closure we have that a is related to all smaller b (as every a is related to b – 1) and from the reflexive property a is related to a.

6. Let R₁ be a relation from A = {1, 3, 5, 7} to B = {2, 4, 6, 8} and R2 be another relation from B to C = {1, 2, 3, 4} as defined below:
i. An element a in A is related to an element b in B (under R₁) if a * b is divisible by 3.
ii. An element a in B is related to an element b in C (under R₂) if a * b is even but not divisible by 3. Which is the composite relation R₁R₂ from A to C?
a) R₁R₂ = {(1, 2), (1, 4), (3, 3), (5, 4), (5,6), (7, 3)}
b) Φ
c) R₁R₂ = {(1, 2), (1,6), (3, 2), (3, 4), (5, 4), (7, 2)}
d) R₁R₂ = {(2,2), (3, 2), (3, 4), (5, 1), (5, 3), (7, 1)}

Answer: b
Clarification: By definition, i) R₁ = {(1,6), (3,2), (3,4), (3,6), (3,8), (5,6), (7,6)} and ii) R₂ = {(1,2), (1,4), (1,8), (5,2), (5,4), (5,8), (7,2), (7,4), (7,8)}. So, R₁R₂ = Φ.

7. The time complexity of computing the transitive closure of a binary relation on a set of n elements should be ________
a) O(n)
b) O(logn)
c) O(n^(n+(3/2)))
d) O(n³)

Answer: d
Clarification: Calculation of transitive closure results into matrix multiplication. We can do matrix multiplication in O(n³) time. There are better algorithms that do less than cubic time.

8. Let A and B be two non-empty relations on a set S. Which of the following statements is false?
a) A and B are transitive ⇒ A∩B is transitive
b) A and B are symmetric ⇒ A∪B is symmetric
c) A and B are transitive ⇒ A∪B is not transitive
d) A and B are reflexive ⇒ A∩B is reflexive

Answer: c
Clarification: In terms of set theory, the binary relation R defined on the set X is a transitive relation if, for all a, b, c ∈ X, if aRb and bRc, then aRc. If there are two relations on a set satisfying transitive property then there union must satisfy transitive property.

9. Determine the characteristics of the relation aRb if a² = b².
a) Transitive and symmetric
b) Reflexive and asymmetry
c) Trichotomy, antisymmetry, and irreflexive
d) Symmetric, Reflexive, and transitive

Answer: d
Clarification: Since, x² = y² is just a special case of equality, so all properties that apply to x = y also apply to this case. Hence, the relation satisfies symmetric, reflexive and transitive closure.

10. Let R be a relation between A and B. R is asymmetric if and only if ________
a) Intersection of D(A) and R is empty, where D(A) represents diagonal of set
b) R^-1 is a subset of R, where R^-1 represents inverse of R
c) Intersection of R and R^-1 is D(A)
d) D(A) is a subset of R, where D(A) represents diagonal of set

Answer: a
Clarification: A relation is asymmetric if and only if it is both antisymmetric and irreflexive. As a consequence, a relation is transitive and asymmetric if and only if it is a strict partial order. If D(A) is a diagonal of A set and intersection of D(A) and R is empty, then R is asymmetric.

Discrete Mathematics Question Paper on “Trees – Interconversion for Prefix Postfix Infix Notations”.

1. Evaluation of expression a/b+c*d-e in postfix notation.
a) ab+cd/*-e
b) ab/cd*+e-
c) abc/+d*-e
d) abcd/+*-e

Answer: b
Clarification: The expression=a/b+c*d-e
={(ab/)+(cd*)}-e
={(ab/)(cd*)+}-e
={(ab/)(cd*)+}e-
So the output is: ab/cd*+e-

2. Evaluation of 4*5+3/2-9 in prefix notation.
a) *45-/32+9
b) *+453/-29
c) -+*45/329
d) *+/45932

Answer: c
Clarification: The expression=4*5+3/2-9
={(4*5)+(3/2)-9}
={(*45)+(/32)-9}
={+(*45)(/32)}-9
=-{+(*45)(/32)9
So the output is; -+*45/329.

3. What is the output of the following if funct1(7)?

Void main()
{
    int n;
    long int func;
    scanf(“%d”,&n);
    func=func1 (n)
    printf(“%ld!=%ld”,n,func);
}
long int func1(int n)
{
    if(n==0)
    {
        Return 1;
    }
    else
    {
        return(n*func1(n-1));
    }
}

a) 128
b) 4320
c) 720
d) 5040

Answer: d
Clarification: This is a factorial function of an integer using recursive approach. By running the function on integer 7 we get 5040.

4. Infix to prefix conversion can be done using __________
a) two queues
b) two stacks
c) one stack and two queues
d) one stack

Answer: b
Clarification: In the infix expression, the operator appears between the operands and in infix notation if the operator appears before the operands in the expression. For the conversion between them two stacks are used efficiently. The idea is to use one stack for operators and other to store operands.

5. Conversion from prefix to postfix expression can be done _______________
a) using bubble sort
b) using radix sort
c) using two queues
d) in a direct manner

Answer: d
Clarification: In a postfix expression, the operators appear after the operands. Conversion from prefix to postfix is done directly which is better than converting the prefix expression in infix and then infix to postfix expression. It gives better efficiency.

6. What is the postfix expression of 9+3*5/(10-4)?
a) 9 3 + * 5 / 10 4 –
b) 9 3 5 + * / 10 4 –
c) 9 3 + 5 * / 10 4 –
d) 9 3 5 * / + 10 – 4

Answer: c
Clarification: The expression, 9+3*5/(10-4)
= 9+3*5/(10 4-)
= 9+35/*(10 4-)
= 935/*+(10 4-)
So the output is:9 3 5 / * + 10 4 -.

7. What is the postfix expression of (A+B)-C*(D/E))+F?
a) A B + C D E / * – F +
b) A B C D E + / * F – +
c) A B C + * D E / F + –
d) A B + C – * D E / F +

Answer: a
Clarification: The expression is (A+B)-C*(D/E))+F
= (A+B)-C*(DE/)+F
= (A+B)-C*(DE/)F+
= (A+B)-C(DE/)*F+
= (A+B)C(DE/)*-F+
= (AB+)C(DE/)*-F+
So the output is: AB+CDE/*-F+.

8. Convert the following expression into prefix notation.

(g-(f^e/d+c)-ba)

a) ^-/gfed+c-ab
b) -ab/+-ec^dgf
c) -ab-+c/d^efg
d) ab/+-^cde-fg

Answer: c
Clarification: Convert it first in postfix notation, we can have
(g-(f^e/d+c)-ba)
= (g-(f^e/dc+)-ba)
= (g-(f^ed/c+)-ba)
= (g-(fe^d/c+)-ba)
= (g-(fe^d/c+)ba-)
= (gfe^d/c+-ba-)
By reversing this expression gives the prefix expression, i.e
-ab-+c/d^efg.

9. What is the postfix expression of the given expression, (2*4-(5+7/3^4)-8)10?
a) 2 4 5 * 7 3 4 ^ / + 8 – – 10
b) 2 4 * ^ 5 7 3 4 / + 8 10 – –
c) 2 4 * 5 7 ^ 3 4 / + – 8 10 –
d) 2 4 * 5 7 3 4 ^ / + – 8 – 10

Answer: d
Clarification: By solving we can have,
(2*4-(5+7/3^4)-8)10
= (2*4-(5+7/34^)-8)10
= (2*4-(5+734^/)-8)10
= (2*4-(5734^/+)-8)10
= (2*45734^/+–8)10
= 2*45734^/+-8-10
= 24*5734^/+-8-10
So the output is: 2 4 * 5 7 3 4 ^ / + – 8 – 10.

10. Prefix expression can be evaluated _________
a) from right to left
b) from left to right
c) from the exact middle
d) from second right element

Answer: b
Clarification: Expressions are usually evaluated from left to right manner. Prefix expressions follow the normal rule i.e from left to right. Postfix expressions can be evaluated from right to left.

Discrete Mathematics Multiple Choice Questions on “Permutation Groups”.

1. Consider an integer 23 such that 23 >= 3p for a 2p-cycle in a permutation group, then p is ___________
a) odd prime
b) even prime
c) rational number
d) negative prime

Answer: a
Clarification: Let n an integer such that n>=3p and m is a 2p-cycle in the permutation group, then p is an odd prime.

2. Suppose K_m={P∈S_m|, |P| is odd prime}. Determine the set for which m≥3 Km a subgroup of S_m.
a) {3, 5, 7, 11, 13, …}
b) {-14, -8, -3, 0, 3, 8, 14}
c) {2, 4, 6, 8, 10, 12}
d) {12, 25, 56, 78, 134,…}

Answer: a
Clarification: Since K_m is a subset of S_m, then the set will be {3, 5, 7, 11, 13, …}.

3. The dihedral group having order 6 can have degree _____________
a) 3
b) 26
c) 326
d) 208

Answer: a
Clarification: A symmetric group on a set of three elements is said to be the group of all permutations of a three-element set. It is a dihedral group of order six having degree three.

4. Let (z, *) is a group with x*y=x+y-2 then inverse of x is ___________
a) -(x+4)
b) (x²+6)
c) (x+y)/5
d) (3y+4x²)

Answer: a
Clarification: Let, Identity element I, x*I = I*x = x ⇒ x = x + I – 2 ⇒ I = 2. Inverse of x is x^-1
Now, x*x^-1 = I
⇒ x + x^-1 – 2 = 2
⇒ x^-1 = -(x+4).

5. Let X be a n-square matrix such that Y = X + 8I. Which of the following property will exist?
a) idempotent
b) Y transpose is nilpotent
c) X nilpotent
d) Y inverse

Answer: b
Clarification: Suppose, we have a matrix
(a=begin{bmatrix}
1 & 0\
2 & 1\
end{bmatrix} )
then Y² will not resulting in Y, hence it is not idempotent, Y² is not 0 and so it is not nilpotent. But, as Y is a square matrix, by the property inverse will exist in this case.

6. Suppose, M is a lower triangular matrix with all diagonal entries zero. The resultant matrix of M+I will be ___________
a) idempotent
b) singular
c) nilpotent
d) inverse

Answer: b
Clarification: Since, M is a lower triangular matrix with diagonal elements zero, then we add I and it will result in a lower triangular matrix with all diagonal entries 1. Thus, all eigenvalues M+I are non zero (eigenvalues of triangular matrix is the diagonal elements). So, determinant will never be zero. Hence, the matrix can have inverse property.

7. If Y⁹⁸ (a raised to the power of 5) = 0 and Y is a 97-square matrix. Determine the value of Y⁹⁷.
a) I+Y
b) -Y+3
c) 0
d) Y²

Answer: c
Clarification: Question does not provide any notion of existing an inverse property or related to rank matrix. Hence, by considering zero matrix as Y and that satisfy all the constraints.

8. If 54^th row of a 67^th row matrix is linearly independent with each other then find the rank of the matrix.
a) 61
b) 54
c) 187
d) 32

Answer: b
Clarification: If k^th row of a matrix with n^th row is linearly independent then the rank of that matrix is k. If we take the transpose of a matrix the rank does not change. Hence, the answer is 54 in this case.

9. Let M be an 4×4 matrix with real entries such that M^k=0, for some k≥1. Find the determinant value of (I+M), where, I be the 4 x 4 identity matrix.
a) 72
b) 1
c) 4
d) 36

Answer: b
Clarification: By cayley hamilton theorem, M⁴ = 0. So, characteristic equation should be λ*4=0 and after solving we get 0 for every eigen value. Eigen values of (I+M) = Individual Eigen value of 1+m. So all the eigen values of (I+M) are 1 and Det(I+A) = 1.

10. Suppose (2, 5, 8, 4) and (3, 6) are the two permutation groups that form cycles. What type of permutation is this?
a) odd
b) even
c) acyclic
d) prime

Answer: b
Clarification: There are four permutations (2, 5), (2, 8), (2, 4) and (3, 6) and so it is an even permutation.

Discrete Mathematics Multiple Choice Questions on “Logics and Proofs – De-Morgan’s Laws”.

1. Which of the following statements is the negation of the statements “4 is odd or -9 is positive”?
a) 4 is even or -9 is not negative
b) 4 is odd or -9 is not negative
c) 4 is even and -9 is negative
d) 4 is odd and -9 is not negative

Answer: c
Clarification: Using De Morgan’s Law ~(A V B) ↔ ~A ∧ ~B.

2. Which of the following represents: ~A (negation of A) if A stands for “I like badminton but hate maths”?
a) I hate badminton and maths
b) I do not like badminton or maths
c) I dislike badminton but love maths
d) I hate badminton or like maths

Answer: d
Clarification: De Morgan’s Law ~ (A ∧ B) ↔ ~A V ~B.

3. The compound statement A v ~(A ∧ B).
a) True
b) False

Answer: a
Clarification: Applying De-Morgan’s law we get A v ~ A Ξ Tautology.

4. Which of the following is De-Morgan’s law?
a) P ∧ (Q v R) Ξ (P ∧ Q) v (P ∧ R)
b) ~(P ∧ R) Ξ ~P v ~R, ~(P v R) Ξ ~P ∧ ~R
c) P v ~P Ξ True, P ∧ ~P Ξ False
d) None of the mentioned

Answer: b
Clarification: Definition of De–Morgan’s Law.

5. What is the dual of (A ∧ B) v (C ∧ D)?
a) (A V B) v (C v D)
b) (A V B) ^ (C v D)
c) (A V B) v (C ∧ D)
d) (A ∧ B) v (C v D)

Answer: b
Clarification: In dual ∧ is replaced by v and vice – versa.

6. ~ A v ~ B is logically equivalent to?
a) ~ A → ~ B
b) ~ A ∧ ~ B
c) A → ~B
d) B V A

Answer: c
Clarification: By identity A → B Ξ ~A V B.

7. Negation of statement (A ∧ B) → (B ∧ C) is _____________
a) (A ∧ B) →(~B ∧ ~C)
b) ~(A ∧ B) v ( B v C)
c) ~(A →B) →(~B ∧ C)
d) None of the mentioned

Answer: a
Clarification: ~(A →B) Ξ A ∧ ~B using this we can easily fetch the answer.

8. Which of the following satisfies commutative law?
a) ∧
b) v
c) ↔
d) All of the mentioned

Answer: d
Clarification: All of them satisfies commutative law.

9. If the truth value of A v B is true, then truth value of ~A ∧ B can be ___________
a) True if A is false
b) False if A is false
c) False if B is true and A is false
d) None of the mentioned

Answer: a
Clarification: If A is false then both the condition are obeyed.

10. If P is always against the testimony of Q, then the compound statement P→(P v ~Q) is a __________
a) Tautology
b) Contradiction
c) Contingency
d) None of the mentioned

Answer: a
Clarification: Since either hypothesis is false or both (hypothesis as well as conclusion) are true.

Discrete Mathematics Multiple Choice s on “Growth of Functions”.

1. If f(x) = (x³ – 1) / (3x + 1) then f(x) is?
a) O(x²)
b) O(x)
c) O(x² / 3)
d) O(1)

Answer: a
Clarification: 0 < (x³ – 1) / (3x + 1) 2.

2. If f(x) = 3x² + x³logx, then f(x) is?
a) O(x²)
b) O(x³)
c) O(x)
d) O(1)

Answer: b
Clarification: 0 < 3x² < x³, it follows that 0 < 3x² + x³logx < x³. Consequently, f(x) = O(x³).

3. The big-O notation for f(n) = (nlogn + n²)(n³ + 2) is?
a) O(n²)
b) O(3ⁿ)
c) O(n⁴)
d) O(n⁵)

Answer: d
Clarification: 0 < n³ + 2 < n³, it follows that (nlogn + n²)(n³ + 2) is less than equal to n⁵.

4. The big-theta notation for function f(n) = 2n³ + n – 1 is?
a) n
b) n²
c) n³
d) n⁴

Answer: c
Clarification: 2n³ + n – 1 is less than equal to n³.

5. The big-theta notation for f(n) = nlog(n² + 1) + n²logn is?
a) n²logn
b) n²
c) logn
d) nlog(n²)

Answer: a
Clarification: n²logn < n³, it follows that nlog(n² + 1) + n²logn is less than n³ and greater than n²logn.

5. The big-omega notation for f(x, y) = x⁵y³ + x⁴y⁴ + x³y⁵ is?
a) x⁵y³
b) x⁵y⁵
c) x³y³
d) x⁴y⁴

Answer: c
Clarification: x⁵y³, x⁴y⁴ and x³y⁵ is greater than or equal to x³y³.

6. If f₁(x) is O(g(x)) and f₂(x) is o(g(x)), then f₁(x) + f₂(x) is?
a) O(g(x))
b) o(g(x))
c) O(g(x)) + o(g(x))
d) None of the mentioned

Answer: a
Clarification: f₂(x) is less than O(g(x)). So, f₁(x) + f₂(x) upper bound is O(g(x)).

7. The little-o notation for f(x) = xlogx is?
a) x
b) x³
c) x²
d) xlogx

Answer: c
Clarification: Find the limit for xlogx / x² as x tends to infinity.

8. The big-O notation for f(n) = 2log(n!) + (n² + 1)logn is?
a) n
b) n²
c) nlogn
d) n²logn

Answer: d
Clarification: log(n!) < n²logn, it follows that 2log(n!) + (n² + 1)logn is less than or equal n²logn.

9. The big-O notation for f(x) = 5logx is?
a) 1
b) x
c) x²
d) x³

Answer: b
Clarification: logx < x, it follows that 5logx < x.

10. The big-Omega notation for f(x) = 2x⁴ + x² – 4 is?
a) x²
b) x³
c) x
d) x⁴

Answer: d
Clarification: 2x⁴ + x² – 4 is greater than or equal to x⁴.

Discrete Mathematics Multiple Choice Questions on “Sequences and Summations”.

1. For the sequence 1, 7, 25, 79, 241, 727 … simple formula for {a_n} is ____________
a) 3ⁿ⁺¹ – 2
b) 3ⁿ – 2
c) (-3)ⁿ + 4
d) n² – 2

Answer: b
Clarification: The ratio of consecutive numbers is close to 3. Comparing these terms with the sequence of {3ⁿ} which is 3, 9, 27 …. Comparing these terms with the corresponding terms of sequence {3ⁿ} and the nth term is 2 less than the corresponding power of 3.

2. For the sequence 0, 1, 2, 3 an is ____________
a) ⌈n/2⌉+⌊n/2⌋
b) ⌈n/2⌉+⌈n/2⌉
c) ⌊n/2⌋+⌊n/2⌋
d) ⌊n/2⌋

Answer: a
Clarification: Expand the sequence ⌈n/2⌉+⌊n/2⌋ where a1 is ⌊0.5⌋+⌈0.5⌉ = 1+0 = 1, a2 is ⌊1⌋+⌈1⌉ = 1 + 1 = 2 and so on.

3. The value of∑(k=50)¹⁰⁰ k² is __________
a) 338, 350
b) 297, 900
c) 297, 925
d) 290, 025

Answer: c
Clarification: Using the formula. ∑(k=1)ⁿ k² = (n(n + 1)(2n + 1)) / 6.

4. The sets A and B have same cardinality if and only if there is ___________ from A to B.
a) One-to-one
b) One-to-many
c) Many-to-many
d) Many-to-one

Answer: a
Clarification: If there is one-to-one correspondence then they have same cardinality.

5. For the sequence a_n = ⌊√2n+ 1/2⌋, a₇is ____________
a) 1
b) 7
c) 5
d) 4

Answer: d
Clarification: a₇ = ⌊√14+1/2⌋ which is ⌊4.24⌋ = 4.

6. The value of ∑(i=1)³ ∑(h=0)² i is _________
a) 10
b) 17
c) 15
d) 18

Answer: d
Clarification: The value of ∑(i=1)³ ∑(h=0)² i = 1+1+1+2+2+2+3+3+3 = 18.

7. For the sequence a_n = 6. (1/3)ⁿ, a₄ is _________
a) 2/25
b) 2/27
c) 2/19
d) 2/13

Answer: b
Clarification: Put n = 4 in the sequence.

8. The value of ∑(i=0)⁴i! is __________
a) 32
b) 30
c) 34
d) 35

Answer: c
Clarification: First five term of the sequence n! is given by 1, 1, 2, 6, 24.

9. Set of all integers is counter.
a) True
b) False

Answer: a
Clarification: There is one-to-one correspondence between set of positive integers and set of all integers.

10. The value of ∏(k=1)¹⁰⁰(-1) ^k is _________
a) 0
b) 1
c) -1
d) 2

Answer: b
Clarification: The product of a₁, a₂, a₃ …… a_n is represented by ∏(i=1)ⁿ a_i.