Category: Discrete Mathematics Objective Questions

Discrete Mathematics Multiple Choice Questions on “Applications of Number Theory”.

1. The linear combination of gcd(252, 198) = 18 is?
a) 252*4 – 198*5
b) 252*5 – 198*4
c) 252*5 – 198*2
d) 252*4 – 198*4

Answer: a
Clarification: By using the Euclidean algorithm.

2. The inverse of 3 modulo 7 is?
a) -1
b) -2
c) -3
d) -4

Answer: b
Clarification: By using the Euclidean algorithm, 7 = 2*3 + 1. From this we see that -2*3 + 1*7 = 1. This show that -2 is an inverse.

3. The integer 561 is a Carmichael number.
a) True
b) False

Answer: a
Clarification: By using the Fermat’s theorem, it follows that b⁵⁶⁰ is congruent to 1 (mod 561).

4. The linear combination of gcd(117, 213) = 3 can be written as _________
a) 11*213 + (-20)*117
b) 10*213 + (-20)*117
c) 11*117 + (-20)*213
d) 20*213 + (-25)*117

Answer: a
Clarification: By using the Euclidean algorithm.

5. The inverse of 7 modulo 26 is?
a) 12
b) 14
c) 15
d) 20

Answer: c
Clarification: By using the Euclidean algorithm.

6. The inverse of 19 modulo 141 is?
a) 50
b) 51
c) 54
d) 52

Answer: d
Clarification: By using the Euclidean algorithm.

7. The integer 2821 is a Carmichael number.
a) True
b) False

Answer: a
Clarification: By using the Fermat’s theorem, it follows that b²⁸²⁰ is congruent to 1 (mod 2821).

8. The solution of the linear congruence 4x = 5(mod 9) is?
a) 6(mod 9)
b) 8(mod 9)
c) 9(mod 9)
d) 10(mod 9)

Answer: b
Clarification: The inverse of 5 modulo 9 is -2. Multiply by (-2) on both sides in equation 4x = 5(mod 9), it follows that x is congruent to 8(mod 9).

9. The linear combination of gcd(10, 11) = 1 can be written as _________
a) (-1)*10 + 1*11
b) (-2)*10 + 2*11
c) 1*10 + (-1)*11
d) (-1)*10 + 2*11

Answer: a
Clarification: By using the Euclidean theorem, it follows that 1 = (-1)*10 + 1*11.

10. The value of 5²⁰⁰³ mod 7 is?
a) 3
b) 4
c) 8
d) 9

Answer: a
Clarification: By using the Fermat’s theorem.

Discrete Mathematics Questions & Answers for Exams on “Counting – Number of Equations Solution”.

1. The linear system Cx = d is known as _________ if d! = 0.
a) homogeneous
b) heterogeneous
c) nonhomogeneous
d) augmented system

Answer: c
Clarification: A linear system Cx = d is known as a homogeneous system if d! = 0. The homogeneous linear system Ax = 0 is called its corresponding homogeneous linear system.

2. Every linear equation determines a _______ in n-dimensional space for n variables.
a) shipshape
b) hyperplane
c) cone
d) pyramid

Answer: b
Clarification: In an m-dimensional space, every linear equation produces a hyperplane for n variables. The solution set is the intersection of these hyperplanes and is planar which may have any dimension smaller than m.

3. Determine all possibilities for the number of solutions of the system of 7 equations in 5 unknowns and it has x₁ = 0, x₂ = −6, and x₃ = 4 as a solution.
a) unique or infinitely many
b) unique
c) finitely many
d) zero

Answer: a
Clarification: Let i be the number of equations and j be the number of unknowns in the given system. Since i> j, the system has at least one solution x₁ = 0, x₂ = −6, and x₃ = 4 and so it is consistent. Thus, it results in either a unique solution or infinitely many solutions.

4. Determine all possibilities for the solution set of the homogeneous system that has y₁ = 6, y₂ = −4, y₃ = 0 as a solution.
a) zero
b) infinitely many
c) finitely many
d) only one

Answer: b
Clarification: Since m<n, the system is either inconsistent or has infinitely many solutions. Since y₁ = 6, y₂ = −4, y₃ = 0 is a solution of the system, the system is not inconsistent. Thus the only possibility is infinitely many solutions.

5. Determine all possibilities for the solution set of the homogeneous system of 5 equations in 3 unknowns and the rank of the system is 3.
a) more than two
b) only one
c) zero
d) infinite

Answer: c
Clarification: Since the rank of this homogeneous system(which is always consistent) and the number of unknowns are equal, the only possible solution is zero and it is a unique solution.

6. Determine all possibilities for the solution set of a homogeneous system that has y₁ = 5, y₂ = −3, y₃ = 2 as a solution.
a) one
b) finitely many
c) infinitely many
d) either one or infinitely many

Answer: c
Clarification: The possibilities for the solution set for any homogeneous system is either a unique solution or infinitely many solutions. Since the homogeneous system has the zero solution and y₁ = 5, y₂ = −3, y₃ = 2 is another solution, it has at least two distinct solution. Thus the only possibility is infinitely many solutions.

7. Determine all possibilities for the solution set of the system of 2 equations in 3 unknowns that has x₁ = 4, x₂ = −7, x₃ = 0 as a solution.
a) one or finitely many
b) infinite
c) finite
d) zero

Answer: b
Clarification: Since m1 = 4, x₂ = −7, x₃ = 0 is a solution of the system, the system is not inconsistent. Thus the only possibility is infinitely many solutions.

8. Determine all possibilities for the solution set of a homogeneous system of 4 equations in 4 unknowns.
a) only one
b) finitely many or zero
c) zero
d) one or infinitely many

Answer: b
Clarification: Here the number of equations and the number of unknowns are equal and the system is homogeneous, so it may have the zero solution or infinitely many solutions.

9. Determine all possibilities for the solution set of a homogeneous system of 6 equations in 5 unknowns.
a) only one
b) zero
c) one or infinitely many
d) finitely many

Answer: c
Clarification: Since the system is homogeneous and there are more equations than the number of unknowns, so the possibilities are either a unique solution or infinitely many solutions. However, if the rank r of the system is 5, then it can be a unique solution as well as if r<5, then there are infinitely many solutions.

10. Determine all possibilities for the solution set of a homogeneous system of 5 equations in 4 unknowns and the rank of the system is 3.
a) finite
b) zero or finitely many
c) only one
d) infinite

Answer: d
Clarification: A homogeneous system is consistent. The rank is r = 3 and the number of variables is n = 4. Hence there is n – r = 1 free variable. Thus there are infinitely many solutions.

Discrete Mathematics Multiple Choice Questions on “Closure on Relations”.

1. R is a binary relation on a set S and R is reflexive if and only if _______
a) r(R) = R
b) s(R) = R
c) t(R) = R
d) f(R) = R

Answer: a
Clarification: Let reflexive closure of R:r(R) = R. If R is reflexive, it satisfies all the condition in the definition of reflexive closure. So, a reflexive closure of a relation is the smallest number of reflexive relation contain in R. Hence, R = r(R).

2. If R₁ and R₂ are binary relations from set A to set B, then the equality ______ holds.
a) (R^c)^c = R^c
b) (A x B)^c = Φ
c) (R₁ U R₂)^c = R₁^c ∪ R₂^c
d) (R₁ U R₂)^c = R₁^c ∩ R₂^c

Answer: c
Clarification: To proof (R₁ U R₂)^c = R₁^c ∪ R₂^c,
if <x,y> belongs to (R₁ U R₂)^c
⇔ <y,x> ∈ (R₁ U R₂)
⇔ <y,x> ∈ R₁ or <y,x> ∈ R₂
⇔ <x,y> ∈ R₁^c or <x,y> ∈ R₂^c
⇔ <x,y> ∈ R₁^c ∪ R₂^c.

3. The condition for a binary relation to be symmetric is _______
a) s(R) = R
b) R ∪ R = R
c) R = R^c
d) f(R) = R

Answer: c
Clarification: If <a,b> ∈ R then <b,a> ∈ R, where a and b belong to two different sets and so its symmetric.
R^c also contains <b,a>
R^c = R.

4. ______ number of reflexive closure exists in a relation R = {(0,1), (1,1), (1,3), (2,1), (2,2), (3,0)} where {0, 1, 2, 3} ∈ A.
a) 2⁶
b) 6
c) 8
d) 36

Answer: b
Clarification: The reflexive closure of R is the relation, R ∪ Δ = { (a,b) | (a,b) R (a,a) | a A }. Hence, R ∪ Δ = {(0,1), (1,1), (1,3), (2,1), (2,2), (3,0)} and the answer is 6.

5. The transitive closure of the relation {(0,1), (1,2), (2,2), (3,4), (5,3), (5,4)} on the set {1, 2, 3, 4, 5} is _______
a) {(0,1), (1,2), (2,2), (3,4)}
b) {(0,0), (1,1), (2,2), (3,3), (4,4), (5,5)}
c) {(0,1), (1,1), (2,2), (5,3), (5,4)}
d) {(0,1), (0,2), (1,2), (2,2), (3,4), (5,3), (5,4)}

Answer: d
Clarification: Let R be a relation on a set A. The connectivity relation on R* consists of pairs (a,b) such that there is a path of length at least one from a to b in R. Mathematically, R* = R¹ ∪ R² ∪ R³ ∪ … ∪ Rⁿ. Hence the answer is {(0,1), (0,2), (1,2), (2,2), (3,4), (5,3), (5,4)}.

6. Amongst the properties {reflexivity, symmetry, antisymmetry, transitivity} the relation R={(a,b) ∈ N² | a!= b} satisfies _______ property.
a) symmetry
b) transitivity
c) antisymmetry
d) reflexivity

Answer: a
Clarification: It is not reflexive as aRa is not possible. It is symmetric as if aRb then bRa. It is not antisymmetric as aRb and bRa are possible and we can have a!=b. It is not transitive as if aRb and bRc then aRc need not be true. This is violated when c=a. So the answer is symmetry property.

7. The number of equivalence relations of the set {3, 6, 9, 12, 18} is ______
a) 4
b) 2⁵
c) 22
d) 90

Answer: a
Clarification: Number of equivalence Relations are given by BELL number. The nth of these numbers i.e, B_n counts the number of different ways to partition a set that has exactly n elements, or equivalently, the number of equivalence relations on it. Let’s say, 1 -> Equivalence relation with 1 element; 1 2 -> Equivalence relation with 2 element; 2 3 5 -> Equivalence relation with 3 element; 5 7 10 15 -> Equivalence relation with 4 element. Hence, the answer is 4.

8. Let R₁ and R₂ be two equivalence relations on a set. Is R₁ ∪ R₂ an equivalence relation?
a) an equivalence relation
b) reflexive closure of relation
c) not an equivalence relation
d) partial equivalence relation

Answer: a
Clarification: R₁ union R₂ is not equivalence relation because transitivity property of closure need not hold. For instance, (x, y) can be in R₁ and (y, z) be in R₂ and (x, z) not in either R₁ or R₂. However, R₁ intersection R₂ is an equivalence relation.

9. A relation R is defined on the set of integers as aRb if and only if a+b is even and R is termed as ______
a) an equivalence relation with one equivalence class
b) an equivalence relation with two equivalence classes
c) an equivalence relation
d) an equivalence relation with three equivalence classes

Answer: b
Clarification: R is reflexive as (a+b) is even for any integer; R is symmetric as if (a+b) is even (b+a) is also even; R is transitive as if ((a+b)+c) is even, then (a+(b+c)) is also even.
So, R is an equivalence relation. For set of natural numbers, sum of even numbers always give even, sum of odd numbers always give even and sum of any even and any odd number always give odd. So, must have two equivalence classes -> one for even and one for odd.
{…, -4, -2, 0, 2, … } and {…, -3, -1, 1, 3, … }.

10. The binary relation U = Φ (empty set) on a set A = {11, 23, 35} is _____
a) Neither reflexive nor symmetric
b) Symmetric and reflexive
c) Transitive and reflexive
d) Transitive and symmetric

Answer: d
Clarification: U = Φ (empty set) on a set A = {11, 23, 35} need to be hold Irreflexive, symmetric, anti-symmetric, asymmetric and transitive closure property, but it is not Reflexive as it does not contain any self loop in itself.

Discrete Mathematics Multiple Choice Questions on “Tree Traversal”.

1. In preorder traversal of a binary tree the second step is ____________
a) traverse the right subtree
b) traverse the left subtree
c) traverse right subtree and visit the root
d) visit the root

Answer: b
Clarification: In a preorder traversal of a binary tree first is to visit the root, second traverse the left subtree of the tree and third traverse the right subtree of the tree.

2. An important application of binary tree is ______
a) Huffman coding
b) stack implementation
c) queue implementation
d) traverse a cyclic graph

Answer: a
Clarification: A binary tree is used to sort a list of elements; the inorder traversal will do this automatically. Better tree sorting algorithm will involve balancing the trees. The binary coding, in particular for the Huffman coding is an immediate application of binary trees.

3. From the following code identify the which traversal of a binary tree is this __________

//if node has left child
  order(node.left)
//if node has right child
  order(node.right)
  visit(node)

a) Inorder traversal
b) preorder traversal
c) postorder traversal
d) Euler tour traversal

Answer: c
Clarification: In a postorder traversal of a binary tree first is to traverse the left subtree, second traverse the right subtree of the tree and third is to visit the node.

4. What is the minimum height for a binary search tree with 60 nodes?
a) 1
b) 3
c) 4
d) 2

Answer: d
Clarification: If there are k nodes in a binary tree, maximum height of that tree should be k-1, and minimum height should be floor(log2k). By using the formula, minimum height must be 2 when there are 60 nodes in a tree.

5. From the following code identify the which traversal of a binary tree is this __________

function traversal(node)
{
    //Input:root node of the tree
    //Output:None
    visitLeft(node)
    //if node has left child
    traversal(node.left)
    visit_Below(node)
    //if node has right child
    traversal(node.right)
    visitRight(node)
}

a) Inorder traversal
b) Euler Tour traversal
c) Post-order traversal
d) Pre-order Traversal

Answer: b
Clarification: The code signifies Euler Tour traversal which is a generic traversal of a binary tree. In this tree traversal we have to walk around the tree and visit each node three times:
1. On the left (pre-order), 2. From below (in-order), 3. On the right (post-order) and Create subtrees for all the nodes.

6. For the expression (7-(4*5))+(9/3) which of the following is the post order tree traversal?
a) *745-93/+
b) 93/+745*-
c) 745*-93/+
d) 74*+593/-

Answer: c
Clarification: First build a binary tree for the expression then find out the postorder traversal of that tree and after that the answer will be 745*-93/+.

7. The time complexity of calculating the sum of all leaf nodes in an n-order binary tree is __________
a) O(n²)
b) O(n+1)
c) O(1)
d) O(n)

Answer: d
Clarification: The approach is to traverse the binary tree in any fashion and check if the node is the leaf node(child node)or not. After that, add node data to the sum variable. So, after summing up all leaf nodes, the time complexity of the operation should be O(n).

8. An immediate application of a Depth First Search traversal is __________
a) count the number of leaf nodes
b) perform Inorder traversal in easy way
c) count number of nodes
d) implement preorder traversal

Answer: a
Clarification: Given an n-ary binary tree, by performing DFS traversal on that tree number of leaf nodes can be calculated and for that we need to maintain an array for the leaf count.

9. Breadth First Search traversal of a binary tree finds its application in __________
a) Cloud computing
b) Peer to peer networks
c) Weighted graph
d) Euler path

Answer: b
Clarification: Breadth First Search traversal has diverse applications such as in the peer to peer networks like BitTorrent, BFS traversal is used to find all the neighbour nodes of the network.

10. Worst case complexity of Breadth First Search traversal __________
a) O(n*n)
b) O(nlogn)
c) O(n² logn)
d) O(n³)

Answer: b
Clarification: In an n-ary binary tree, we must have to visit all nodes from an adjacent node and repeat the same for next unvisited nodes. Hence, in worst case the time complexity should be O(nlogn).

Discrete Mathematics Multiple Choice Questions on “Cyclic Groups”.

1. An infinite cyclic group does not have a ______ series.
a) AP
b) GP
c) Composite
d) Finite

Answer: c
Clarification: Suppose that any finite group of order less than n has a composition series. Let G be a finite group of order n. If G is simple, then G⊳{e}, where e is the identity element of G and hence, it is a composition series. However, any infinite cyclic group does not have a composite series.

2. Every cyclic group is a/an ______
a) infinite subgroup
b) abelian group
c) monoid
d) commutative semigroup

Answer: b
Clarification: Let C be a cyclic group with a generator g∈C. Namely, we have G={g.Let x and y be arbitrary elements in C. Then, there exists n, m∈Z such that x=gn and y=gm. It follows that x*y = gn*gm = gn+m = gm*gn = yx. Hence, we find that xy=yx for any x,y belongs to G.Thus, G is an abelian group.

3. What is an irreducible module?
a) A cyclic module in a ring with any non-zero element as its generator
b) A cyclic module in a ring with any positive integer as its generator
c) An acyclic module in a ring with rational elements as its generator
d) A linearly independent module in a semigroup with a set of real numbers

Answer: a
Clarification: A nonzero R-module M is irreducible if and only if M is a cyclic module with any nonzero element as its generator. Suppose that M is an irreducible module. Let a∈M be any nonzero element and consider the submodule (a) generated by the element a. Since a is a nonzero element, the submodule (a) is non-zero. Since M is irreducible, this implies that M=(a). Hence M is a cyclic module generated by a. Since a is any nonzero element, the module M is a cyclic module with any nonzero element as its generator.

4. A finite group G of order 219 is __________
a) a semigroup
b) a subgroup
c) a commutative inverse
d) a cyclic group

Answer: d
Clarification: The prime factorization 219=3⋅73. By the definition of Sylow’s theorem, determine the number np of Sylow p-group for p=3,73. np≡1(mod p) and np divides n/p. Thus, n3 could be 1, 4, 7, 10, 13,… and n3 needs to divide 219/3=73. Hence the only possible value for n3 is n3=1. So there is a unique Sylow 3-subgroup P3 of G. By Sylow’s theorem, the unique Sylow 3-subgroup must be a normal subgroup of G. Similarly, n73=1, 74,… and n73 must divide 219/73=3 and hence we must have n73=1. Thus, G has a unique normal Sylow 73-subgroup P73.

5. The number of generators of cyclic group of order 219 is __________
a) 144
b) 124
c) 56
d) 218

Answer: a
Clarification: The number of generators of a cyclic group of order n is equal to the number of integers between 1 and n that are relatively prime to n.Namely, the number of generators is equal to ϕ(n), where ϕ is the Euler totient function. We know that G is a cyclic group of order 219. Hence, the number of generators of G is ϕ(219) = ϕ(3)ϕ(73) = 3⋅73 = 144.

6. The order of a simple abelian group is __________
a) infinite
b) real number
c) finite
d) prime

Answer: a
Clarification: Let p be the order of g (hence the order of G). As a contradiction, assume that p=ab is a composite number with integers a > 1, b > 1. Then (ga) is a proper normal subgroup of G. This is a contradiction since G is simple. Thus, p must be a prime number.
Therefore, the order of G is a prime number.

7. The Number of Elements Satisfying g7=e in a finite Group F is ______
a) even
b) not a number
c) odd
d) rational

Answer: c
Clarification: Let g≠e be an element in group F such that g7=e. As 7 is a prime number, this yields that the order of g is 7. Consider, the subgroup (g) is generated by g. As the order of g is 7, the order of the subgroup (g) is 7. Hence, the order must be odd.

8. All the rings of order p2 is ____________
a) associative
b) cyclic
c) inverse
d) commutative

Answer: d
Clarification: Let R be a ring with unit 1. Suppose that the order of R is |R|=p2 for some prime number p. Then it has been proven that R is a commutative ring.

9. An element of a commutative ring R(1≠0) is nilpotent if __________
a) a+1=0
b) aⁿ = 0, for some positive integer n
c) aⁿ = 1, for some integer n
d) a² = 0

Answer: b
Clarification: Since a is nilpotent in a commutative ring R, we have an=0 for some positive integer n. since R is commutative, for any m∈R, we have (am)n=anmn=0. Then we have the following equality: (1−am)(1+(am)+(am)2+⋯+(am)n−1)=1. Hence, 1−am is a unit in R.

10. A group G of order 20 is __________
a) solvable
b) unsolvable
c) 1
d) not determined

Answer: a
Clarification: The prime factorization of 20 is 20=2⋅5. Let n5 be the number of 5-Sylow subgroups of G. By Sylow’s theorem, we have, n5≡1(mod 5)and n5|4. Thus, we have n5=1. Let P be the unique 5-Sylow subgroup of G. The subgroup P is normal in G as it is the unique 5-Sylow subgroup. Then consider the subnormal series G▹P▹{e}, where e is the identity element of G. Then the factor groups G/P, P/{e} have order 4 and 5 respectively. Hence these are cyclic groups(in particular abelian). Hence, the group G of order 20 has a subnormal series whose factor groups are abelian groups, and thus G is a solvable group.

Discrete Mathematics Interview Questions and Answers for freshers on “Logics – Implication and Double Implications”.

1. Let P and Q be statements, then P<->Q is logically equivalent to __________
a) P<->~Q
b) ~P<->Q
c) ~P<->~Q
d) None of the mentioned

Answer: c
Clarification: Both of them have same truth table, Hence they are equal.

2. What is the negation of the statement A->(B v(or) C)?
a) A ∧ ~B ∧ ~C
b) A->B->C
c) ~A ∧ B v C
d) None of the mentioned

Answer: a
Clarification: A->P is logically equivalent to ~A v P.

3. The compound statement A-> (A->B) is false, then the truth values of A, B are respectively _________
a) T, T
b) F, T
c) T, F
d) F, F

Answer: c
Clarification: For implications to be false hypothesis should be true and conclusion should be false.

4. The statement which is logically equivalent to A∧ (and) B is?
a) A->B
b) ~A ∧ ~ B
c) A ∧ ~B
d) ~(A->~B)

Answer: d
Clarification: The truth table of both statements are same.

5. Let P: We give a nice overall squad performance, Q: We will win the match.
Then the symbolic form of “We will win the match if and only if we give a nice overall squad performance.“ is?
a) P v Q
b) Q ∧ P
c) Q<->P
d) ~P v Q

Answer: c
Clarification: If and only if statements are bi-conditionals.

6. Let P, Q, R be true, false true, respectively, which of the following is true?
a) P∧Q∧R
b) P∧~Q∧~R
c) Q->(P∧R)
d) P->(Q∧R)

Answer: c
Clarification: Hypothesis is false, hence statement is true.

7. “Match will be played only if it is not a humid day.” The negation of this statement is?
a) Match will be played but it is a humid day
b) Match will be played or it is a humid day
c) All of the mentioned statement are correct
d) None of the mentioned

Answer: a
Clarification: Negation of P->Q is P∧~Q.

8. Consider the following statements.
A: Raju should exercise.
B: Raju is not a decent table tennis player.
C: Raju wants to play good table tennis.
The symbolic form of “Raju is not a decent table tennis player and if he wants to play good table tennis then he should exercise.” is?
a) A->B->C
b) B∧(C->A)
c) C->B∧A
d) B<->A∧C

Answer: b
Clarification: For conditionals statement (if then), implications are used.

9. The statement (~P<->Q)∧~Q is true when?
a) P: True Q: False
b) P: True Q: True
c) P: False Q: True
d) P: False Q: False

Answer: a
Clarification: For a bi-conditional to be true both inputs should be same.

10. Let P, Q, R be true, false, false, respectively, which of the following is true?
a) P∧(Q∧~R)
b) (P->Q)∧~R
c) Q<->(P∧R)
d) P<->(QvR)

Answer: c
Clarification: For a bi-conditional to be true both inputs should be the same.