250+ TOP MCQs on Cyclic Groups and Answers

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) an = 0, for some positive integer n
c) an = 1, for some integer n
d) a2 = 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.

250+ TOP MCQs on Logics – Implication and Double Implications

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.

250+ TOP MCQs on Functions and Answers

Discrete Mathematics Multiple Choice Questions on “Functions”.

1. A function is said to be ______________ if and only if f(a) = f(b) implies that a = b for all a and b in the domain of f.
a) One-to-many
b) One-to-one
c) Many-to-many
d) Many-to-one

Answer: b
Clarification: A function is one-to-one if and only if f(a)≠f(b) whenever a≠b.

2. The function f(x)=x+1 from the set of integers to itself is onto. Is it True or False?
a) True
b) False

Answer: a
Clarification: For every integer “y” there is an integer “x ” such that f(x) = y.

3. The value of ⌊1/2.⌊5/2⌋ ⌋ is ______________
a) 1
b) 2
c) 3
d) 0.5

Answer: a
Clarification: The value of ⌊5/2⌋ is 2 so, the value of ⌊1/2.2⌋ is 1.

4. Which of the following function f: Z X Z → Z is not onto?
a) f(a, b) = a + b
b) f(a, b) = a
c) f(a, b) = |b|
d) f(a, b) = a – b

Answer: c
Clarification: The function is not onto as f(a)≠b.

5. The domain of the function that assign to each pair of integers the maximum of these two integers is ___________
a) N
b) Z
c) Z +
d) Z+ X Z+

Answer: d
Clarification: The domain of the integers is Z+ X Z+.

6. Let f and g be the function from the set of integers to itself, defined by f(x) = 2x + 1 and g(x) = 3x + 4. Then the composition of f and g is ____________
a) 6x + 9
b) 6x + 7
c) 6x + 6
d) 6x + 8

Answer: a
Clarification: The composition of f and g is given by f(g(x)) which is equal to 2(3x + 4) + 1.

7. __________ bytes are required to encode 2000 bits of data.
a) 1
b) 2
c) 3
d) 8

Answer: b
Clarification: Two bytes are required to encode 2000 (actually with 2 bytes you can encode up to and including 65,535.

8. The inverse of function f(x) = x3 + 2 is ____________
a) f -1 (y) = (y – 2) 1/2
b) f -1 (y) = (y – 2) 1/3
c) f -1 (y) = (y) 1/3
d) f -1 (y) = (y – 2)

Answer: b
Clarification: To find the inverse of the function equate f(x) then find the value of x in terms of y such that f -1 (y) = x.

9. The function f(x) = x3 is bijection from R to R. Is it True or False?
a) True
b) False

Answer: a
Clarification: The function f(x) = x3 is one to one as no two values in domain are assigned the same value of the function and it is onto as all R of the co domain is images of elements in the domain.

10. The g -1({0}) for the function g(x)= ⌊x⌋ is ___________
a) {x | 0 ≤ x < 1}
b) {x | 0 < x ≤ 1}
c) {x | 0 < x < 1}
d) {x | 0 ≤ x ≤ 1}

Answer: d
Clarification: g({0}) for the function g(x) is {x | 0 ≤ x ≤ 1}. Put g(x) = y and find the value of x in terms of y such that ⌊x⌋ = y.

250+ TOP MCQs on Inverse of Matrices and Answers

Discrete Mathematics Multiple Choice Questions on “Inverse of Matrices”.

1. For a matrix A, B and identity matrix I, if a matrix AB=I=BA then?
a) B is inverse of A
b) A is inverse of B
c) A-1 = B, B-1 = A
d) All of the mentioned

Answer: d
Clarification: Since AB = I, A = B-1 Similarly A is the inverse of B.

2. For matrix A,(A3) = I, A-1 is equals to _________
a) A2
b) A-2
c) Can’t say
d) None of the mentioned

Answer: a
Clarification: A(A2) = I this implies A-1 = A2.

3. Let A = [0 1 0 0 ], A-1 is equal to _________
a) Null matrix
b) Identity matrix
c) Does not exist
d) None of the mentioned

Answer: c
Clarification: Since A is singular matrix, inverse does not exists.

4. If A is an invertible square matrix then _________
a) (AT)-1 = (A-1)T
b) (AT)T = (A-1)T
c) (AT)-1 = (A-1)-1
d) None of the mentioned

Answer: a
Clarification: For invertible matrix A, AT is also inveritble.

5. If matrix A, B and C are invertible matrix of same order then (ABC)-1 = _________
a) CBA
b) C-1 B-1 A-1
c) CT B-1 AT
d) None of the mentioned

Answer: b
Clarification: Reversal rule holds for inverse multiplication of the matrices.

6. If A is non singular matrix then AB = AC implies B = C.
a) True
b) False

Answer: a
Clarification: Pre-multipliying by A-1 we get B = C.

7. For a matrix A of order n, the det(adj(A)) = (det(A))n, where adj() is adjoint of matrix.
a) True
b) False

Answer: b
Clarification: For a matrix A of order n, the det(adj(A)) = (det(A))n-1.

8. For a non-singular matrix A, A-1 is equal to _________
a) (adj(A))/det(A)
b) det(A)*(adj(A))
c) det(A)*A
d) none of the mentioned

Answer: a
Clarification: A(adj(A)) = det(A)I, I = A(adj(A))/det(A) which implies A-1 = (adj(A))/det(A).

9. Let I3 be the Identity matrix of order 3 then (I3)-1 is equal to _________
a) 0
b) 3I3
c) I3
d) None of the mentioned

Answer: c
Clarification: Idenity matrices are self invertible that is I3 x I3 = I3.

10. If for a square matrix A(non-singular) and B, null matrix O, AB = O then?
a) B is a null matrix
b) B is a non singular matrix
c) B is a identity matrix
d) All of the mentioned

Answer: a
Clarification: Given det(A) is not equal to zero. A-1 exists, A-1(AB) = O, B = O.

250+ TOP MCQs on Number Theory – Primes and Greatest Common Divisors

Discrete Mathematics Multiple Choice Questions on “Number Theory – Primes and Greatest Common Divisors”.

1. The prime factorization of 7007 is __________
a) 73.11.13
b) 72.11.13
c) 7.11.13
d) 7.113.13

Answer: b
Clarification: Perform successive division beginning with 2.

2. Out of following which one is Mersenne Primes?
a) 3
b) 7
c) 2047
d) 31

Answer: c
Clarification: 2047 = 23.89 also not in form of 2b-1 form.

3. Out of the following which of these integers is not prime?
a) 21
b) 35
c) 71
d) 101

Answer: b
Clarification: 35 = 5.7 which is the product of two prime numbers.

4. The prime factorization of 1001 is __________
a) 73.11.13
b) 72.11.13
c) 7.11.13
d) 7.113.13

Answer: c
Clarification: Perform successive division beginning with 2.

5. Which positive integer less than 21 are relatively prime to 21?
a) 18
b) 19
c) 21
d) 24

Answer: b
Clarification: gcd(19,21) = 1. According to the definition of relatively prime gcd of two numbers is 1.

6. Is 7, 8, 9, 11 are pairwise relatively prime.
a) True
b) False

Answer: a
Clarification: gcd(7, 9) = gcd(8, 9) = gcd(9, 11) = gcd(11, 7) = 1. The numbers 7 and 11 are prime and numbers 8 and 9 are relatively prime.

7. The greatest common divisor of 313.517 and 212.35 is __________
a) 30
b) 31
c) 33
d) 35

Answer: d
Clarification: gcd(a, b) = 3min(13, 5).5min(17, 0).2min(12, 0).

8. The greatest common divisor of 0 and 5 is ___________
a) 0
b) 1
c) 2
d) 5

Answer: b
Clarification: gcd(0, 5) = 0min(1, 0).5min(0, 1).

9. The lcm of 3 and 21 is ________ if gcd(3,21)=3.
a) 3
b) 12
c) 21
d) 42

Answer: c
Clarification: 3 * lcm(3, 21) = 63 hence, lcm(3, 21) = 63 / 3 = 21.

10. The least common multiple of 41.42 and 42.41 is ____________
a) 42
b) 41
c) 84
d) 41.42

Answer: d
Clarification: lcm(41 * 42, 42 * 42) = 41.42.42.41 / 41.42 = 41.42.

250+ TOP MCQs on Counting – Derangements and Answers

Discrete Mathematics Multiple Choice Questions on “Counting – Derangements”.

1. Determine the number of derangements of (2, 4, 6, 1, 3, 5) that end with integer 2, 4 and 6 in some order?
a) 128
b) 29
c) 54
d) 36

Answer: d
Clarification: The place of 2, 4, 6 is specified i.e. each of them will get their place out of the last 3 places only. So 1, 3, 5 will automatically get one of the places in the first 3 places. This must ensure that 2, 4 and 6 occupies one of the last 3 places each and 1, 3 and 5 one of 1st 3 places each. Hence, 1, 3 and 5 can be arranged in 3! ways and 2, 4 and 6 also in 3! Ways. So, no of such derangements = 3! * 3! = 6 * 6 = 36.

2. A nursery teacher has 5 pencil boxes to give out to her five students. Determine the probability that at least one student gets their name tag?
a) (frac{19}{30})
b) (frac{26}{47})
c) (frac{123}{537})
d) (frac{12}{79})

Answer: a
Clarification: There are 5!= 120 ways to give out the pencil boxes. By using complementary probability, the number of ways where nobody gets their pencil boxes is
5!((frac{1}{0!} – frac{1}{1!} + … – frac{1}{5!}))
= 44. Hence, the required probability is (frac{120 – 44}{120} = frac{19}{30}).

3. Farhan has received 9 gifts from 9 different people. In how many ways can Farhan receives the gifts such that no one gives him real gifts?
a) 133496
b) 326654
c) 218744
d) 745331

Answer: a
Clarification: By the derangements formula, the number of possible derangements should be 9!((frac{1}{0!} – frac{1}{1!} + … – frac{1}{9!})) = 133496. Hence, there are a total of ways to give the gifts to him such that no one distributes the real gifts.

4. There are 7 groups in a picnic who has brought their own lunch box, and then the 7 lunch box are exchanged within those groups. Determine the number of ways that they can exchange the lunch box such that none of them can get their own.
a) 655
b) 328
c) 1854
d) 3765

Answer: c
Clarification: This can be solved by the derangement formula:
!n = n!(1 – (frac{1}{1!} + frac{1}{2!} – frac{1}{3!} + … + frac{(-1)^n1}{n!})) ⇒ 7! = 1854.

5. Computational complexity of derangements is of __________
a) NP-complete
b) NP-hard
c) NP
d) P

Answer: a
Clarification: Computational complexity of derangements is NP-complete in order to determine whether a given permutation group consists of any derangements or not.

6. There are 5 different-colored boxes in a room each with a distinct cover. Find out the number of ways so that these covers can be put on the boxes such that none of the boxes can have right covers on it? (Assume that all the covers must be on the boxes).
a) 208
b) 137
c) 239
d) 24

Answer: d
Clarification: Let the box covers be A, B, C, D and E. The possible ways for the covers to not be in the exact order of A, B, C, D, E are: 4! = 24 ways. (Since correct order i.e., A, B, C, D and E must be eliminated from such arrangements).

7. A postman can put 12 letters into their respective envelopes such that exactly 5 will go into the right envelope. Find the number of ways of doing this work.
a) 2984300
b) 1610496
c) 5322167
d) 3768650

Answer: b
Clarification: The number of ways in which the 5 correct envelopes can be selected = 12C5 = 864
Derangement of the remaining 7 envelopes & letters = 1864 (derangement value for 7 is 1864)
Total No of ways of arrangement = 1864 * 864 = 1610496.

8. Determine the number of ways In a single competition a singing couple from 5 boys and 5 girls can be formed so that no girl can sing a song with their respective boy?
a) 123
b) 44
c) 320
d) 21

Answer: b
Clarification: This is a case of derangement of 5 boys and 5 girls. The required number of ways can be described as D = 5! (1 – (frac{1}{1!} + frac{1}{2!} – frac{1}{3!} + frac{1}{4!} – frac{1}{5!}) = 120(frac{11}{30})) = 44 ways.

9. What is the sum of all 6 digit numbers which can be formed using the digits 2, 3, 5, 6 and 9 exactly once?
a) 986546600
b) 25611866
c) 433338798
d) 319999680

Answer: d
Clarification: Note that sum of all possible numbers = (n-1)!(sum of the digits involved)(1111…n times), where n is the number of digits. Here n = 6, we have (6-1)!(2+3+5+6+9)(111111) = 5!*(24)*(111111) = 319999680.

10. Determine the average of all four digit numbers that can be made using all the digits 2, 3, 5, 7 and 11 exactly once?
a) 3993
b) 1555
c) 5486
d) 1347

Answer: b
Clarification: First we need to find the sum of all possible numbers and then divide it by the total such numbers possible to gain an average of all the numbers. So, we have (n-1)!(sum of digits)(1111…n times)/n!. Here n = 4. Therefore, (5-1)!(2+3+5+7+11)(1111)/5! = 1555.