Mathematics Multiple Choice Questions & Answers (MCQs Logics – Propositions.
a) Get me a glass of milkshake
b) God bless you!
c) What is the time now?
d) The only odd prime number is 2
Explanation: Only this statement has got the truth value which is false.
2. The truth value of ‘4+3=7 or 5 is not prime’.
a) False
b) True
Explanation: Compound statement with ‘or’ is true when either of the statement is true. Here the first part of the statement is true, hence the whole is true.
3. Which of the following option is true?
a) If the Sun is a planet, elephants will fly
b) 3 +2 = 8 if 5-2 = 7
c) 1 > 3 and 3 is a positive integer
d) -2 > 3 or 3 is a negative integer
Explanation: Hypothesis is false, thus the whole statement is true.
4. What is the value of x after this statement, assuming the initial value of x is 5?
a) 1
b) 3
c) 0
d) 2
Explanation: If condition is false so value decided according to else condition.
5. Let P: I am in Bangalore.; Q: I love cricket.; then q -> p(q implies p) is?
a) If I love cricket then I am in Bangalore
b) If I am in Bangalore then I love cricket
c) I am not in Bangalore
d) I love cricket
Explanation: Q is hypothesis and P is conclusion. So the compound statement will be if hypothesis then conclusion.
6. Let P: If Sahil bowls, Saurabh hits a century.; Q: If Raju bowls,
Sahil gets out on first ball. Now if P is true and Q is false then
which of the following can be true?
a) Raju bowled and Sahil got out on first ball
b) Raju did not bowled
c) Sahil bowled and Saurabh hits a century
d) Sahil bowled and Saurabh got out
Explanation: Either hypothesis should be false or both (hypothesis and conclusion) should be true.
7. The truth value ‘9 is prime then 3 is even’.
a) False
b) True
Explanation: The first part of the statement is false, hence whole is true.
8. Let P: I am in Delhi.; Q: Delhi is clean.; then q ^ p(q and p) is?
a) Delhi is clean and I am in Delhi
b) Delhi is not clean or I am in Delhi
c) I am in Delhi and Delhi is not clean
d) Delhi is clean but I am in Mumbai
Explanation: Connector should be ‘and’, that is q and p.
9. Let P: This is a great website, Q: You should not come back here.
Then ‘This is a great website and you should come back here.’ is best
represented by?
a) ~P V ~Q
b) P ∧ ~Q
c) P V Q
d) P ∧ Q
Explanation: The second part of the statement is negated, hence negation operator is used.
10. Let P: We should be honest., Q: We should be dedicated., R: We
should be overconfident. Then ‘We should be honest or dedicated but not
overconfident.’ is best represented by?
a) ~P V ~Q V R
b) P ∧ ~Q ∧ R
c) P V Q ∧ R
d) P V Q ∧ ~R
Explanation: The third part of the statement is negated, hence negation operator is used, for (‘or’ –V) is used and for(’but’- ∧).
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Logics – Types of Statements”.
1. The contrapositive of p → q is the proposition of ____________
a) ¬p → ¬q
b) ¬q → ¬p
c) q → p
d) ¬q → p
Explanation: Definition of contrapositive.
2. The inverse of p → q is the proposition of ____________
a) ¬p → ¬q
b) ¬q → ¬p
c) q → p
d) ¬q → p
Explanation: Definition of inverse.
3. The converse of p → q is the proposition of _______________
a) ¬p → ¬q
b) ¬q → ¬p
c) q → p
d) ¬q → p
Explanation: Definition of converse.
4. What is the contrapositive of the conditional statement? “The home team misses whenever it is drizzling?”
a) If it is drizzling, then home team misses
b) If the home team misses, then it is drizzling
c) If it is not drizzling, then the home team does not misses
d) If the home team wins, then it is not drizzling
Explanation: q whenever p contrapositive is ¬q → ¬p.
5. What is the converse of the conditional statement “If it ices today, I will play ice hockey tomorrow.”
a) “I will play ice hockey tomorrow only if it ices today.”
b) “If I do not play ice hockey tomorrow, then it will not have iced today.”
c) “If it does not ice today, then I will not play ice hockey tomorrow.”
d) “I will not play ice hockey tomorrow only if it ices today.”
Explanation: If p, then q has converse q → p.
6. What are the contrapositive of the conditional statement “I come to class whenever there is going to be a test.”
a) “If I come to class, then there will be a test.”
b) “If I do not come to class, then there will not be a test.”
c) “If there is not going to be a test, then I don’t come to class.”
d) “If there is going to be a test, then I don’t come to class.”
Explanation: q whenever p, has contrapositive ¬q → ¬p.
7. What are the inverse of the conditional statement “ A positive
integer is a composite only if it has divisors other than 1 and
itself.”
a) “A positive integer is a composite if it has divisors other than 1 and itself.”
b) “If a positive integer has no divisors other than 1 and itself, then it is not composite.”
c) “If a positive integer is not composite, then it has no divisors other than 1 and itself.”
d) None of the mentioned
Explanation: p only if q has inverse ¬p → ¬q.
8. What are the converse of the conditional statement “When Raj stay up late, it is necessary that Raj sleep until noon.”
a) “If Raj stay up late, then Raj sleep until noon.”
b) “If Raj does not stay up late, then Raj does not sleep until noon.”
c) “If Raj does not sleep until noon, then Raj does not stay up late.”
d) “If Raj sleep until noon, then Raj stay up late.”
Explanation: Necessary condition for p is q has converse q → p.
9. What are the contrapositive of the conditional statement “Medha will find a decent job when she labour hard.”?
a) “If Medha labour hard, then she will find a decent job.”
b) “If Medha will not find a decent job, then she not labour hard.”
c) “If Medha will find a decent job, then she labour hard.”
d) “If Medha not labour hard, then she will not find a decent job.”
Explanation: The statement q when p has its contrapositive as ¬q → ¬p.
10. What are the inverse of the conditional statement “If you make your notes, it will be a convenient in exams.”
a) “If you make notes, then it will be a convenient in exams.”
b) “If you do not make notes, then it will not be a convenient in exams.”
c) “If it will not be a convenient in exams, then you did not make your notes.”
d) “If it will be a convenient in exams, then you make your notes
Explanation: If p then q has inverse ¬p → ¬q.
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Types of Set”.
1. {x: x is an integer neither positive nor negative} is ________
a) Empty set
b) Non-empty set
c) Finite set
d) Non- empty and Finite set
Explanation: Set = {0} non-empty and finite set.
2. {x: x is a real number between 1 and 2} is an ________
a) Infinite set
b) Finite set
c) Empty set
d) None of the mentioned
Explanation: It is an infinite set as there are infinitely many real number between any two different real numbers.
3. Write set {1, 5, 15, 25,…} in set-builder form.
a) {x: either x=1 or x=5n, where n is a real number}
b) {x: either x=1 or x=5n, where n is a integer}
c) {x: either x=1 or x=5n, where n is an odd natural number}
d) {x: x=5n, where n is a natural number}
Explanation: Set should include 1 or an odd multiple of 5.
4. Express {x: x= n/ (n+1), n is a natural number less than 7} in roster form.
a) {1⁄2, 2⁄3, 4⁄5, 6⁄7}
b) {1⁄2, 2⁄3, 3⁄4, 4⁄5, 5⁄6, 6⁄7, 7⁄8}
c) {1⁄2, 2⁄3, 3⁄4, 4⁄5, 5⁄6, 6⁄7}
d) Infinite set
Explanation: n/(n+1) = 1/(1+1) = 1⁄2 and n>7.
5. Number of power set of {a, b}, where a and b are distinct elements.
a) 3
b) 4
c) 2
d) 5
Explanation: Power set of {a, b} = {∅, {a, b}, {a}, {b}}.
6. Which of the following is subset of set {1, 2, 3, 4}?
a) {1, 2}
b) {1, 2, 3}
c) {1}
d) All of the mentioned
Explanation: There are total 16 subsets.
7. A = {∅,{∅},2,{2,∅},3}, which of the following is true?
a) {{∅,{∅}} ∈ A
b) {2} ∈ A
c) ∅ ⊂ A
d) 3 ⊂ A
Explanation: Empty set is a subset of every set.
8. Subset of the set A= { } is?
a) A
b) {}
c) ∅
d) All of the mentioned
Explanation: Every set is subset of itself and Empty set is subset of each set.
9. {x: x ∈ N and x is prime} then it is ________
a) Infinite set
b) Finite set
c) Empty set
d) Not a set
Explanation: There is no extreme prime, number of primes is infinite.
10. Convert set {x: x is a positive prime number which divides 72} in roster form.
a) {2, 3, 5}
b) {2, 3, 6}
c) {2, 3}
d) {∅}
Explanation: 2 and 3 are the divisors of 72 which are prime.
This set of Discrete Mathematics Questions and Answers for Entrance exams focuses on “Inverse of a Function”.
1. For an inverse to exist it is necessary that a function should be __________
a) injection
b) bijection
c) surjection
d) none of the mentioned
Explanation: Inverse exist only for those functions which are one one and onto.
2. If f(x) = y then f-1(y) is equal to __________
a) y
b) x
c) x2
d) none of the mentioned
Explanation: On giving inverse, image the function returns preimage thus f-1 (y) = x.
3. A function f(x) is defined from A to B then f -1 is defined __________
a) from A to B
b) from B to A
c) depends on the inverse of function
d) none of the mentioned
Explanation: Inverse associate each element in B with corresponding element in A.
4. If f is a function defined from R to R, is given by f(x) = 3x – 5 then f –1(x) is given by __________
a) 1/(3x-5)
b) (x+5)/3
c) does not exist since it is not a bijection
d) none of the mentioned
Explanation: y = 3x-5, x = (y+5)/3, f -1(x) = (x+5)/3.
5. For some bijective function inverse of that function is not bijective.
a) True
b) False
Explanation: If f(x) is a bijection than f -1(x) is also a bijection.
6. f(x) is a bijection than f -1(x) is a mirror image of f(x) around y = x.
a) True
b) False
Explanation: Inverse of a function is the mirror image of function in line y = x.
7. If f is a function defined from R to R, is given by f(x) = x2 then f -1(x) is given by?
a) 1/(3x-5)
b) (x+5)/3
c) does not exist since it is not a bijection
d) none of the mentioned
Explanation: It is not a one one function hence Inverse does not exist.
8. For any function fof -1(x) is equal to?
a) x
b) 1
c) x2
d) none of the mentioned
Explanation:Compostion of a function with its inverse gives x.
9. The solution to f(x) = f -1(x) are __________
a) no solutions in any case
b) same as solution to f(x) = x
c) infinite number of solution for every case
d) none of the mentioned
Explanation: Inverse of a function is the mirror image of function in line y = x.
10. Let f(x) = x then number of solution to f(x) = f -1(x) is zero.
a) True
b) False
Explanation: Since inverse of a function is the mirror image of function in line y = x, therefore in this case infinte solution will exist.
This set of Discrete Mathematics Multiple Choice s & Answers (MCQs) focuses on “Algorithms”.
1. An algorithm is a _________ set of precise instructions for performing computation.
a) Infinite
b) Finite
c) Constant
d) None of the mentioned
Explanation: By the definition of an algorithm.
2. Out of the following which property algorithms does not share?
a) Input
b) Finiteness
c) Generality
d) Constancy
Explanation: All the others are the properties of algorithms.
3. In ________ search each element is compared with x till not found.
a) Binary
b) Sequential
c) Merge
d) None of the mentioned
Explanation: In linear or sequential search entire list is searched sequentially for x.
4. If the entire list is searched sequentially without locating x in linear search, the solution is __________
a) 0
b) -1
c) 1
d) 2
Explanation: If the element is not found in the entire list, then the solution is 0.
5. To sort a list with n elements, the insertion sort begins with the __________ element.
a) First
b) Second
c) Third
d) Fourth
Explanation: The insertion sort compares the second element with the first element to start sorting.
6. __________ comparisons required to sort the list 1, 2, 3…….n using insertion sort.
a) (n2 + n + 2) / 2
b) (n3 + n – 2) / 2
c) (n2 + n – 2) / 2
d) (n2 – n – 2) / 2
Explanation: 2+3+4+….6n = (n2 + n – 2) / 2.
7. The Worst case occurs in linear search algorithm when ____________
a) Item is somewhere in the middle of the array
b) Item is not in the array at all
c) Item is the last element in the array
d) Item is the last element in the array or is not there at all
Explanation: The Worst case occur in linear search algorithm when Item is the last element in the array or is not there at all.
8. List obtained in third pass of selection sort for list 3, 5, 4, 1, 2 is ___________
a) 1, 2, 4, 3, 5
b) 1, 2, 3, 4, 5
c) 1, 5, 4, 3, 2
d) 3, 5, 4, 1, 2
Explanation: The selection sort begins with finding the least element in the list. This element is moved to front and then the least element among the remaining elements. Is found and put into the second position and so on.
9. The operation of processing each element in the list is known as _________
a) Sorting
b) Merging
c) Inserting
d) Traversal
Explanation: The operation of processing each element in the list is known as Traversal.
10. The complexity of Bubble sort algorithm is _________
a) O(n)
b) O(log n)
c) O(n2)
d) O(n log n)
Explanation: The complexity of Bubble sort algorithm is O(n2).
This set of Discrete Mathematics Questions and Answers for Freshers focuses on “Algorithms – Complexity-2”.
1. Which is used to measure the Time complexity of an algorithm Big O notation?
a) describes limiting behaviour of the function
b) characterises a function based on growth of function
c) upper bound on growth rate of the function
d) all of the mentioned
Explanation: Big O notation describes limiting behaviour, and also gives upper bound on growth rate of a function.
2. If for an algorithm time complexity is given by O(1) then the complexity of it is ____________
a) constant
b) polynomial
c) exponential
d) none of the mentioned
Explanation: The growth rate of that function will be constant.
3. If for an algorithm time complexity is given by O(log2n) then complexity will be ___________
a) constant
b) polynomial
c) exponential
d) none of the mentioned
Explanation: The growth rate of that function will be logarithmic therefore complexity will be logarithmic.
4. If for an algorithm time complexity is given by O(n) then the complexity of it is ___________
a) constant
b) linear
c) exponential
d) none of the mentioned
Explanation: The growth rate of that function will be linear.
5. If for an algorithm time complexity is given by O(n2) then complexity will ___________
a) constant
b) quadratic
c) exponential
d) none of the mentioned
Explanation: The growth rate of that function will be quadratic therefore complexity will be quadratic.
6. If for an algorithm time complexity is given by O((3⁄2)n) then complexity will be ___________
a) constant
b) quardratic
c) exponential
d) none of the mentioned
Explanation: The growth rate of that function will be exponential therefore complexity will be exponential.
7. The time complexity of binary search is given by ___________
a) constant
b) quardratic
c) exponential
d) none of the mentioned
Explanation: It is O(log2n), therefore complexity will be logarithmic.
8. The time complexity of the linear search is given by ___________
a) O(log2n)
b) O(1)
c) exponential
d) none of the mentioned
Explanation: It is O(n), therefore complexity will be linear.
9. Which algorithm is better for sorting between bubble sort and quicksort?
a) bubble sort
b) quick sort
c) both are equally good
d) none of the mentioned
Explanation: Running time of quicksort is logarithmic whereas for bubble sort it is quadratic.
10. Time complexity of the binary search algorithm is constant.
a) True
b) False
Explanation: It is O(log2n), therefore complexity will be logarithmic.
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Number Theory – Prime Numbers”.
1. The number of factors of prime numbers are ___________
a) 2
b) 3
c) Depends on the prime number
d) None of the mentioned
Explanation: A prime number is only divisible by 1 and itself.
2. What is the number ‘ 1’?
a) Prime number
b) Composite number
c) Neither Prime nor Composite
d) None of the mentioned
Explanation: 1 is neither prime number nor composite.
3. All prime numbers are odd.
a) True
b) False
Explanation: 2 is even as well as prime.
4. 3 is the smallest prime number possible.
a) True
b) False
Explanation: 2 is also a prime number.
5. How many prime numbers are there between 1 to 20?
a) 5
b) 6
c) 7
d) None of the mentioned
Explanation: The prime numbers between 1 to 20 are 2, 3, 5, 7, 11, 13, 17, 19.
6. There are finite number of prime numbers.
a) True
b) False
Explanation: There are infinite numbers of primes.
7. Sum of two different prime number is a ____________
a) Prime number
b) Composite number
c) Either Prime or Composite
d) None of the mentioned
Explanation: Eg:- 2 + 3 = 5 a prime, 3 + 7 = 10 a composite.
8. Difference of two distinct prime numbers is?
a) Odd and prime
b) Even and composite
c) None of the mentioned
d) All of the mentioned
Explanation: 3 – 2 = 1 is neither prime nor composite.
9. If a, b, c, d are distinct prime numbers with an as smallest prime then a * b * c * d is a ___________
a) Odd number
b) Even number
c) Prime number
d) None of the mentioned
Explanation: Since a is 2, 2 * b * c * d = Even number.
10. If a, b are two distinct prime number than a highest common factor of a, b is ___________
a) 2
b) 0
c) 1
d) ab
Explanation: HCF of two prime numbers is 1.
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses 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
Explanation: By using the Euclidean algorithm.
2. The inverse of 3 modulo 7 is?
a) -1
b) -2
c) -3
d) -4
Explanation: 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
Explanation: By using the Fermat’s theorem, it follows that b560 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
Explanation: By using the Euclidean algorithm.
5. The inverse of 7 modulo 26 is?
a) 12
b) 14
c) 15
d) 20
Explanation: By using the Euclidean algorithm.
6. The inverse of 19 modulo 141 is?
a) 50
b) 51
c) 54
d) 52
Explanation: By using the Euclidean algorithm.
7. The integer 2821 is a Carmichael number.
a) True
b) False
Explanation: By using the Fermat’s theorem, it follows that b2820 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)
Explanation: 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
Explanation: By using the Euclidean theorem, it follows that 1 = (-1)*10 + 1*11.
10. The value of 52003 mod 7 is?
a) 3
b) 4
c) 8
d) 9
Explanation: By using the Fermat’s theorem.
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Principle of Mathematical Induction”.
1. What is the base case for the inequality 7n > n3, where n = 3?
a) 652 > 189
b) 42 < 132
c) 343 > 27
d) 42 <= 431
Explanation: By the principle of mathematical induction, we have 73 > 33 ⇒ 343 > 27 as a base case and it is true for n = 3.
2. In the principle of mathematical induction, which of the following steps is mandatory?
a) induction hypothesis
b) inductive reference
c) induction set assumption
d) minimal set representation
Explanation: The hypothesis of Step is a must for mathematical induction that is the statement is true for n = k, where n and k are any natural numbers, which is also called induction assumption or induction hypothesis.
3. For m = 1, 2, …, 4m+2 is a multiple of ________
a) 3
b) 5
c) 6
d) 2
Explanation: For n = 1, 4 * 1 + 2 = 6, which is a multiple of 2. Assume that 4m+2 is true for m=k and so 4k+2 is true based on the assumption. Now, to prove that 4k+2 is also a multiple of 2 ⇒ 4(k+1)+2 ⇒ 2 * 4k – 4k + 6 ⇒ 2*4k+4 – 4k+2 ⇒ 2(4k+2) – 2(2k+1). Here, the first term 2(4k+2) is true as per assumption and the second term 2(4k+2) is must to be a multiple of 2. Hence, 4(k+1)+2 is a multiple of 2. So, by induction hypothesis, (4m+2) is a multiple of 2, for m = 1,2,3,…
4. For any integer m>=3, the series 2+4+6+…+(4m) can be equivalent to ________
a) m2+3
b) m+1
c) mm
d) 3m2+4
Explanation: The required answer is m2+3. Now, by induction assumption, we have to prove 2+4+6+…+4(k+1) = (k+1)2+3 also can be true, 2+4+6+…+4(k+1) = 2+4+6+⋯+(4k+4) and by the subsequent steps, we can prove that (m+1)2+3 also holds for m=k. So, it is proved.
5. For every natural number k, which of the following is true?
a) (mn)k = mknk
b) m*k = n + 1
c) (m+n)k = k + 1
d) mkn = mnk
Explanation: In the first step, for k = 1, (mn)1 = m1n1 = mn, hence it is true. Let us assume the statement is true for k = l, Now by induction assumption, (mn)1 = m1n1 is true. So, to prove, (mn)l+1 = ml + 1nl+1, we have (mn)l = mlnl and multiplying both sides by (mn) ⇒ (mn)1(mn)=(m1n1)(mn)
⇒ (mn)l+1 = (mm1)(nn1) ⇒ (mn)l+1 = (ml+1nl+1). Hence, it is proved. So, (mn)k = mknk is true for every natural number k.
6. By induction hypothesis, the series 12 + 22 + 32 + … + p2 can be proved equivalent to ____________
a) \(\frac{p^2+2}{7}\)
b) \(\frac{p*(p + 1)*(2p + 1)}{6}\)
c) \(\frac{p*(p+1)}{4}\)
d) p+p2
Explanation: By principle of mathematical induction, we now assume that p (b) is true 12 + 22 + 32 + … + b2 = \(\frac{b (b + 1) (2b + 1)}{6}\)
so to prove P(b+1): 12 + 22 + 32 + … + b2 + (b + 1)2 = \(\frac{b (b + 1) (2b + 1)}{6}\) + (b + 1)2
By induction assumption it is shown that 12 + 22 + 32 + … + b2 + (b + 1)2 = \(\frac{(b + 1) [(b + 2) (2b + 3)]}{6}\). Hence it is proved that 12 + 22 + 32 + … + p2 = \(\frac{p*(p + 1)*(2p + 1)}{6}\).
7. For any positive integer m ______ is divisible by 4.
a) 5m2 + 2
b) 3m + 1
c) m2 + 3
d) m3 + 3m
Explanation: The required answer is, m3 + 3m. Now, by induction hypothesis, we have to prove for m=k, k3+3k is divisible by 4. So, (k + 1)3 + 3 (k + 1) = k3 + 3 k2 + 6 k + 4
= [k3 + 3 k] + [3 k2 + 3 k + 4] = 4M + (12k2 + 12k) – (8k2 + 8k – 4), both the terms are divisible by 4. Hence (k + 1)3 + 3 (k + 1) is also divisible by 4 and hence it is proved for any integer m.
8. According to principle of mathematical induction, if P(k+1) = m(k+1) + 5 is true then _____ must be true.
a) P(k) = 3m(k)
b) P(k) = m(k) + 5
c) P(k) = m(k+2) + 5
d) P(k) = m(k)
Explanation: By the principle of mathematical induction, if a statement is true for any number m = k, then for its successor m = k + 1, the statement also satisfies, provided the statement is true for m = 1. So, the required answer is p(k) = mk + 5.
9. Which of the following is the base case for 4n+1 > (n+1)2 where n = 2?
a) 64 > 9
b) 16 > 2
c) 27 < 91
d) 54 > 8
Explanation: Statement By principle of mathematical induction, for n=2 the base case of the inequation 4n+1 > (n+1)2 should be 64 > 9 and it is true.
10. What is the induction hypothesis assumption for the inequality m ! > 2m where m>=4?
a) for m=k, k+1!>2k holds
b) for m=k, k!>2k holds
c) for m=k, k!>3k holds
d) for m=k, k!>2k+1 holds
Explanation: By the induction hypothesis, assume that p (k) = k! > 2k is true, for m=k and we need to prove this by the principle of mathematical induction.
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Recursion”.
1. Which of the following is contained in a recursive grammar?
a) semantic rules
b) production rules
c) recursive language
d) recursive function
Explanation: In natural language semantics, recursive grammar plays a vital role as well as in syntax. A recursive grammar in a context free language is a formal grammar which consists of recursive production rules.
2. ________ is the consequence of dynamic programming.
a) Bellman equation
b) Frobenius equation
c) Linear equation
d) Boolean expression
Explanation: Dynamic programming can lead to recursive optimization that can restate a multistep optimization problem in its recursive form. The Bellman equation that writes the value of the optimization problem at an earlier time in terms of its value at a later time is the result of dynamic programming.
3. How many types of self-referential recursive data are there in computer programs?
a) 6
b) 2
c) 10
d) 4
Explanation: There are two types of self-referential definitions and these are inductive and coinductive definitions. An inductively defined recursive data definition must have to specify how to construct instances of the data. For example, linked lists are defined as an inductively recursive data definition.
4. _______ recursion consists of multiple self-references.
a) binary recursion
b) single recursion
c) multiple recursion
d) coinductive recursion
Explanation: A recursion which consists of multiple self-references and requires exponential time and space is called multiple recursion. Multiple recursions include tree traversal of a graph, such as in a depth-first search. However, single recursion is more efficient than multiple recursion.
5. The argument of each recursive call is the content of a field of
the original output. This definite characteristic belongs to which of
the following function?
a) Structurally recursive function
b) Generativity recursive function
c) General function
d) Indirect recursive function
Explanation: A structurally recursive function has a characteristic that the argument to each recursive call is the content of a field of the original input. This recursion function includes mostly all tree traversals which includes binary tree creation and search, XML processing etc.
6. The mutual recursion is also termed as ______
a) indirect recursion
b) constructive recursion
c) generative recursion
d) definitive recursion
Explanation: When a function is not called by itself but by another function which it has called either directly or indirectly is termed as Indirect recursion. Mutual recursion is a more symmetric term of Indirect recursion.
7. In which of the following problems recurrence relation holds?
a) Optimal substructure
b) Tower of Hanoi
c) Hallmark substitution
d) Longest common subsequence
Explanation: We can have recurrence relation for tower of hanoi and that is hn = 2 hn-1 + 1h1 = 1, for n number of disks in one peg.
8. Which of the following functions generates new data at each step of a method?
a) corecursive function
b) structural recursive function
c) unirecursive function
d) indirect function
Explanation: The generatively recursive functions or corecursive functions is defined as generation of the new data at each step that is successive approximation in Regula Falsi method. In terms of loop variants, there is no such loop variant, and termination depends on error of approximation.
9. Every recursive algorithm must have the problem of ________
a) overhead of repeated function calls
b) collision of different function calls
c) searching for all duplicate elements
d) make only two recursive calls
Explanation: Due to the overhead of repeated function calls and returns, recursive algorithms may be inefficient for small data. Any recursion can be replaced by iteration with an explicit call stack whereas iteration can be replaced with tail recursion.
10. If the height of a binary tree is 54, how many null pointers are there as children?
a) 1267
b) 358
c) 56
d) 255
Explanation: Depth-first search (DFS) algorithm of a binary tree, is a trivial example of short-circuiting. We can have a standard recursive algorithm in case of DFS. Now, a perfect binary tree of height h has 2h+1 Null pointers as children.
h = 54
254+1
255.
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Fundamental Principle of Counting”.
1. How many even 4 digit whole numbers are there?
a) 1358
b) 7250
c) 4500
d) 3600
Explanation: The thousands digit cannot be zero, so there are 9 choices. There are 10 possibilities for the hundreds digit and 10 possibilities for the tens digit. The units digit can be 0, 2, 4, 6 or 8, so there are 5 choices. By the basic counting principle, the number of even five digit whole numbers is 9 × 10 × 10 × 5 = 45,00.
2. In a multiple-choice question paper of 15 questions, the answers
can be A, B, C or D. The number of different ways of answering the
question paper are ________
a) 65536 x 47
b) 194536 x 45
c) 23650 x 49
d) 11287435
Explanation: There are 415 = 65536 x 47 different ways of answering the exam paper of 15 MCQs.
3. How many words with seven letters are there that start with a
vowel and end with an A? Note that they don’t have to be real words and
letters can be repeated.
a) 45087902
b) 64387659
c) 12765800
d) 59406880
Explanation: The first letter must be a vowel, so there are 5 choices. The second letter can be any one of 26, the third letter can be any one of 26, the fourth letter can be any one of 26 and fifth and sixth letters can be any of 26 choices. The last letter must be an A, so there is only 1 choice. By the basic counting principle, the number of ‘words’ is 5 × 26 × 26 × 26 × 26 × 26 × 1 = 59406880.
4. Neela has twelve different skirts, ten different tops, eight
different pairs of shoes, three different necklaces and five different
bracelets. In how many ways can Neela dress up?
a) 50057
b) 14400
c) 34870
d) 56732
Explanation: By the basic counting principle, the number of different ways = 12 × 10 × 8 × 3 × 5 = 14400. Note that shoes come in pairs. So she must choose one pair of shoes from ten pairs, not one shoe from twenty.
5. How many five-digit numbers can be made from the digits 1 to 7 if repetition is allowed?
a) 16807
b) 54629
c) 23467
d) 32354
Explanation: 75 = 16807 ways of making the numbers consisting of five digits if repetition is allowed.
6. For her English literature course, Ruchika has to choose one novel
to study from a list of ten, one poem from a list of fifteen and one
short story from a list of seven. How many different choices does Rachel
have?
a) 34900
b) 26500
c) 12000
d) 10500
Explanation: By the Basic Counting Principle, the number of different choices is 10 × 15 × 7 = 10500.
7. There are two different Geography books, five different Natural
Sciences books, three different History books and four different
Mathematics books on a shelf. In how many different ways can they be
arranged if all the books of the same subjects stand together?
a) 353450
b) 638364
c) 829440
d) 768700
Explanation: There are four groups of books which can be arranged in 4! different ways. Among those books, two are Geography books, five are Natural Sciences books, three are History books and four are Mathematics books. Therefore, there are 4! × 2! × 5! × 3! × 4! = 829440 ways to arrange the books.
8. The code for a safe is of the form PPPQQQQ where P is any number
from 0 to 9 and Q represents the letters of the alphabet. How many codes
are possible for each of the following cases? Note that the digits and
letters of the alphabet can be repeated.
a) 874261140
b) 537856330
c) 549872700
d) 456976000
Explanation: 103 × 264 = 456976000 possible codes are formed for the safe with the alphanumeric digits.
9. Amit must choose a seven-digit PIN number and each digit can be
chosen from 0 to 9. How many different possible PIN numbers can Amit
choose?
a) 10000000
b) 9900000
c) 67285000
d) 39654900
Explanation: By the basic counting principle, the total number of PIN numbers Amit can choose is 10 × 10 × 10 × 10 × 10 × 10 × 10 = 10,000000.
10. A head boy, two deputy head boys, a head girl and 3 deputy head
girls must be chosen out of a student council consisting of 14 girls and
16 boys. In how many ways can they are chosen?
a) 98072
b) 27384
c) 36428
d) 44389
Explanation: There are 16 × 15 × 14 + 14 × 13 × 12 × 11 = 27384 ways to choose from a student council.
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Counting – Division of Objects”.
1. For a gaming competition, 8 girls are planning on splitting up
into 3 (non-empty) groups. How many ways can they split up into these
groups?
a) 465
b) 1056
c) 966
d) 3215
Explanation: Using the inclusion-exclusion principle, the total number of ways of splitting the girls into 3 groups is 38 + 3.(28) + 3.(18). However, since the three groups are identical we need to divide by 3!. Hence, the answer is 966.
2. In a picnic with 20 persons where 6 chocolates will be given to
the top 8 children(the chocolates are distinct: first, second). How many
ways can this be done?
a) 18C6
b) 20P6
c) 25C4 * 6!
d) 19P5
Explanation: This is a permutation problem since the chocolates are distinct. The answer is P(20, 6) -> the number of ways to arrange 20 things taken 6 at a time -> which is \(\frac{20!}{(20-6)!}\) = 20*19*18*17*16*15.
3. How many ways can one choose 20 cookies from 45 different types (assuming there are at least 20 of each type)?
a) 64C21 * 15
b) 64C20
c) 44C20 * 2!
d) 65C22
Explanation: Imagine the 20 cookies one is choosing are indistinguishable dots. The 45 different types of cookies are like 45 distinguishable boxes and so the answer is C(45 + 20-1, 20) = 64C20.
4. Assume that it is an afternoon. What is the time on the 24 hour clock after 146 hours?
a) 12:10 pm
b) 8:30 am
c) 3 am
d) 2 pm
Explanation: Divide 146 with 24. The remainder is the time on the 24 hour clock. So, 146 = 6*24 + 2 and the result is 2pm.
5. There are 28 identical oranges that are to be distributed among 8
distinct girls. How many ways are there to distribute the oranges?
a) 22P7
b) 34C6
c) 35C7
d) 28C8
Explanation: By the definition of star and bar problem, there are n+r-1Cr-1 possible distributions of n identical objects among r distinct bins. Now, there are n = 28 identical objects and r = 8 distinct bins. Using the formula above, there are 35C7 ways to distribute the oranges.
6. There are 5 distinct fruits. How many ways can they be planted into identical fruit plants?
a) 87
b) 52
c) 76
d) 128
Explanation: These fruits can be placed into 1, 2, 3, 4 or 5 fruit plants. The number of distributions of fruits into fruit plants will thus be the sum of Stirling numbers of the second kind: S(5,1) + S(5,2) + S(5,3) + S(5,4) + S(5,5) = 1 + 15 + 25 + 10 + 1 = 52.
7. A woman has 14 identical pens to distribute among a group of 10
distinct students. How many ways are there to distribute the 14 pens
such that each student gets at least one pencil?
a) 15C10
b) 10C5 * 11
c) 15C8 * 4!
d) 13C9
Explanation: For this type of problem, n>=r must be true and so according to stars and bars model, the number of possible arrangements of stars and bars is n-1Cr-1 or equivalently, there are n-1Cr-1 distributions of n identical objects into r distinct non-empty bins. In this example, there are n = 14 identical objects to be distributed among r=10 distinct bins. Using the above formula, the number of possible distributions is 13C9.
8. Suppose that M is the product of k distinct primes. Find the
number of ways to write N as the product of positive integers(>1),
where the order of terms does not matter.
a) MCN-k
b) NCM
c) N * Bk
d) Bk
Explanation: To solve the problem first find the prime factorization of each term of the product, and place the factors of each term into a box. Then, since N is the product of distinct prime factors, each prime factor appears in a unique box. Since the product of all of these terms is N, each prime factor must be in a box. Conversely, for any arrangement of these n distinct primes into r identical boxes, multiply the primes in a box to create a term and the product of these terms results in N. This establishes the bijection and the number of ways is Bk which is Bell number.
9. How many ways are there to place 7 differently colored toys into 5
identical urns if the urns can be empty? Note that all balls have to be
used.
a) 320
b) 438
c) 1287
d) 855
Explanation: The problem can be described as distinct objects into any number of identical bins and this number can be found with B7 = ∑S(7,k), where S(7,k) is the number of distributions of 5 distinct objects into k identical non-empty bins, so that S(7,1) = 1, S(7,2) = 63, S(7,3) = 301, S(7,4) = 350 and S(7,5) = 140. These values can be found using the recurrence relation identity for Stirling numbers of the second kind. Thus, B7 = 1 + 63 + 301 + 350 + 140 = 855.
10. Suppose, there are 7 of your friends who want to eat pizza (8
distinct people in total). You order a 16-cut pizza (16 identical
slices). How many distributions of pizza slices are there if each person
gets at least one slice of pizza?
a) 346
b) 6435
c) 3214
d) 765
Explanation: This problem can be viewed as identical objects distributed into distinct non-empty bins. Using the formula for these kind of distributions n-1Cr-1 = 15C7 = 6435. Thus, there are distributions of the pizza slices.
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Addition Theorem on Probability”.
1. Neha has 4 yellow t-shirts, 6 black t-shirts, and 2 blue t-shirts
to choose from for her outfit today. She chooses a t-shirt randomly with
each t-shirt equally likely to be chosen. Find the probability that a
black or blue t-shirt is chosen for the outfit.
a) \(\frac{8}{13}\)
b) \(\frac{5}{6}\)
c) \(\frac{1}{2}\)
d) \(\frac{7}{12}\)
Explanation: Define the events A and B as follows: A=Neha chooses a black t-shirt. B= Neha chooses a blue skirt. Neha cannot choose both a black t-shirt and a blue t-shirt, so the addition theorem of probability applies:
P(A U B) = P(A) + P(B) = \((\frac{6}{12}) + (\frac{2}{12}) = \frac{3}{6} = \frac{1}{2}\).
2. If a fair 15-sided dice is rolled, then is the probability that the roll is an odd number or prime number or both?
a) \(\frac{3}{20}\)
b) \(\frac{4}{19}\)
c) \(\frac{9}{20}\)
d) \(\frac{17}{20}\)
Explanation: There are 7 even numbers on the 20-sided dice: 1, 3, 5, 7, 9, 13, 15. There are 6 prime numbers on the 20-sided dice: 2, 3, 5, 7, 11, 13. There are 4 numbers that are both odd and prime: 3, 5, 7, 13. By the rule of sum, the probability that an odd or prime number is rolled is \((\frac{7}{20}) + (\frac{6}{20}) – (\frac{4}{20}) = \frac{9}{20}\).
3. There are a total of 50 distinct books on a shelf such as 20 math
books, 16 physics books, and 14 chemistry books. Find is the probability
of getting a book that is not a chemistry book or not a physics book.
a) \(\frac{4}{17}\)
b) \(\frac{43}{50}\)
c) \(\frac{12}{31}\)
d) 1
Explanation: The probability of not getting chemistry book = 1 – (probability of chemistry book)
= 1 – \(\frac{14}{30} = \frac{16}{30}\) and the probability of not getting chemistry book = 1 – (probability of physics book) = 1 – \(\frac{16}{30} = \frac{14}{30}\). So, the required probability is = \(\frac{16}{30} + \frac{14}{30}\) = 1.
4. A number is selected from the first 20 natural numbers. Find the probability that it would be divisible by 3 or 7?
a) \(\frac{19}{46}\)
b) \(\frac{24}{67}\)
c) \(\frac{12}{37}\)
d) \(\frac{7}{20}\)
Explanation: Let X be the event that the number selected would be divisible by 3 and Y be the event that the selected number would be divisible by 7. Then A u B denotes the event that the number would be divisible by 3 or 7. Now, X = {3, 9, 12, 15, 18} and Y = {7, 14} whereas S = {1, 2, 3, …,20}. Since A n B = Null set, so that the two events A and B are mutually exclusive and as such we have,
P(A u B) = P(A) + P(B) ⇒ P(A u B) = \(\frac{5}{20} + \frac{2}{20}\)
Therefore, P(A u B) = \(\frac{7}{20}\).
5. There are 24 red marbles in a bag 68 marbles, and 8 of those
marbles are both red and white striped. 27 marbles are white striped and
of those marbles, the same 8 marbles would be both red and white
striped). Find the probability of drawing out a marble from the bag that
is either red or white striped.
a) \(\frac{12}{35}\)
b) \(\frac{43}{68}\)
c) \(\frac{26}{68}\)
d) \(\frac{32}{55}\)
Explanation: The “or” indicates finding the probability of a union of events. Let R be the event that a red marble is drawn and W be the event that a striped marble is drawn. R U W is the event that a marble that is either a red and a white striped is drawn. By the rule of sum of probability,
P(R U W) = P(R) + P(W) – p(R ⋂ W) = \(\frac{24}{68} + \frac{27}{68} – \frac{8}{68} = \frac{43}{68}\).
Hence, the probability of drawing a red or white striped marble is \(\frac{43}{68}\).
6. If spinner has 3 equal sectors colored yellow, blue and red, then
the probability of landing on red or yellow after spinning this spinner
is _______
a) \(\frac{2}{3}\)
b) \(\frac{4}{7}\)
c) \(\frac{6}{17}\)
d) \(\frac{23}{47}\)
Explanation: We can have, P(red) = \(\frac{1}{3}\), P(yellow) = \(\frac{1}{3}\), P(red or yellow) = P(red) + P(yellow) = \(\frac{1}{3} + \frac{1}{3} = \frac{2}{3}\).
7. In a secondary examination, 75% of the students have passed in
History and 65% in Mathematics, while 50% passed in both History and
Mathematics. If 35 candidates failed in both the subjects, what is the
total number of candidates sit for that exam?
a) 658
b) 398
c) 764
d) 350
Explanation: 50% passed in both the subjects, (75-50)% or 25% passed only in History and (65-50)% or 15% passed only in Mathematics, (50 + 25 + 15)% or 90% passed in both the subjects and 10% failed in both subjects. From the question, 10% of total candidates = 35. So, total candidates = 350.
8. In a Press Conference, there are 450 foreign journalists. 275
people can speak German, 250 people can speak English, 200 people can
speak Chinese and 260 people can speak Japanese. Find the maximum number
of foreigners who cannot speak at least one language.
a) 401
b) 129
c) 324
d) 415
Explanation: The total number of journalists = 350.People who speak German = 275 -> people who do not speak German = 75, people who speak English = 250-> people who do not speak English = 100,people who speak Chinese = 200 -> people who do not speak Chinese = 150, people who speak Japanese = 260 -> people who do not speak Japanese = 90. The total number of people who do not know at least one language will be maximum when the sets of people not knowing a particular language are mutually exclusive. Hence, the maximum number of people who do not know at least one language = 75 + 100 + 150 + 90 = 415.
9. There is a class of 40 students out of which 16 are girls. There
are 27 students who are right-handed. How many minimum numbers of girls
who are left-handed in this class?
a) 17
b) 56
c) 23
d) 3
Explanation: Number of girls in the class is 16. Number of left-handed pupils + Number of right-handed pupils = 40. So, Number of left-handed pupils + 27 = 40, Number of left-handed pupils = 13. Therefore, the minimum number of right-handed girls is 16 – 13 = 3.
10. How many positive integers less than or equal to 100 are divisible by 2, 4 or 5?
a) 12.3
b) 87.2
c) 45.3
d) 78.2
Explanation: To count the number of integers = \(\frac{100}{2} + \frac{100}{4} + \frac{100}{5} – \frac{100}{8} – \frac{100}{20} + \frac{100}{100}\)
= 50 + 25 + 20 – 12.8 – 5 + 1 = 78.2.
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Discrete Probability – Bayes Theorem”.
1. A single card is drawn from a standard deck of playing cards. What
is the probability that the card is a face card provided that a queen
is drawn from the deck of cards?
a) \(\frac{3}{13}\)
b) \(\frac{1}{3}\)
c) \(\frac{4}{13}\)
d) \(\frac{1}{52}\)
Explanation: The probability that the card drawn is a queen = \(\frac{4}{52}\), since there are 4 queens in a standard deck of 52 cards. If the event is “this card is a queen” the prior probability P(queen) = \(\frac{4}{52} = \frac{1}{13}\). The posterior probability P(queen|face) can be calculated using Bayes theorem: P(king|face) = P(face|king)/P(face)*P(king). Since every queen is also a face card, P(face|queen) = 1. The probability of a face card is P(face) = (\(\frac{3}{13}\)). [since there are 3 face cards in each suit (Jack, Queen, King)]. Using Bayes theorem gives P(queen|face) = \(\frac{13}{3}*\frac{1}{13} = \frac{1}{3}\).
2. Naina receives emails that consists of 18% spam of those emails.
The spam filter is 93% reliable i.e., 93% of the mails it marks as spam
are actually a spam and 93% of spam mails are correctly labelled as
spam. If a mail marked spam by her spam filter, determine the
probability that it is really spam.
a) 50%
b) 84%
c) 39%
d) 63%
Explanation: 18% email are spam and 82% email are not spam. Now, 18% of mail marked as spam is spam and 82% mail marked as spam are not spam. By Bayes theorem the probability that a mail marked spam is really a spam = (Probability of being spam and being detected as spam)/(Probability of being detected as spam) = (0.18 * 0.82)/(0.18 * 0.82) + (0.18 * 0.82) = 0.5 or 50%.
3. A meeting has 12 employees. Given that 8 of the employees is a woman, find the probability that all the employees are women?
a) \(\frac{11}{23}\)
b) \(\frac{12}{35}\)
c) \(\frac{2}{9}\)
d) \(\frac{1}{8}\)
Explanation: Assume that the probability of an employee being a man or woman is (\(\frac{1}{2}\)). By using Bayes’ theorem: let B be the event that the meeting has 3 employees who is a woman and let A be the event that all employees are women. We want to find P(A|B) = \(\frac{P(B|A)*P(A)}{P(B)}\). P(B|A) = 1, P(A) = \(\frac{1}{12}\) and P(B) = \(\frac{8}{12}\). So, P(A|B) = \(\frac{1*\frac{1}{12}}{\frac{8}{12}} = \frac{1}{8}\).
4. A cupboard A has 4 red carpets and 4 blue carpets and a cupboard B
has 3 red carpets and 5 blue carpets. A carpet is selected from a
cupboard and the carpet is chosen from the selected cupboard such that
each carpet in the cupboard is equally likely to be chosen. Cupboards A
and B can be selected in \(\frac{1}{5}\) and \(\frac{3}{5}\) ways
respectively. Given that a carpet selected in the above process is a
blue carpet, find the probability that it came from the cupboard B.
a) \(\frac{2}{5}\)
b) \(\frac{15}{19}\)
c) \(\frac{31}{73}\)
d) \(\frac{4}{9}\)
Explanation: The probability of selecting a blue carpet = \(\frac{1}{5} * \frac{4}{8} + \frac{3}{5} * \frac{5}{8} = \frac{4}{40} + \frac{15}{40} = \frac{19}{40}\). Probability of selecting a blue carpet from cupboard, P(B) = \(\frac{3}{5} * \frac{5}{8} = \frac{15}{40}\). Given that a carpet selected in the above process is a blue carpet, the probability that it came from the cupboard A is = \(\frac{\frac{15}{40}}{\frac{19}{40}} = \frac{15}{19}\).
5. Mangoes numbered 1 through 18 are placed in a bag for delivery.
Two mangoes are drawn out of the bag without replacement. Find the
probability such that all the mangoes have even numbers on them?
a) 43.7%
b) 34%
c) 6.8%
d) 9.3%
Explanation: The events are not independent. There will be a \(\frac{10}{18} = \frac{5}{9}\) chance that any of the mangoes in the bag is even. The probability that the first one is even is \(\frac{1}{2}\), for the second mango, given that the first one was even, there are only 9 even numbered balls that could be drawn from a total of 17 balls, so the probability is \(\frac{9}{17}\). For the third mango, since the first two are both odd, there are 8 even numbered mangoes that could be drawn from a total of 16 remaining balls and so the probability is \(\frac{8}{16}\) and for fourth mango, the probability is = \(\frac{7}{15}\). So the probability that all 4 mangoes are even numbered is \(\frac{10}{18}*\frac{9}{17}*\frac{8}{16}*\frac{7}{16}\) = 0.068 or 6.8%.
6. A family has two children. Given that one of the children is a
girl and that she was born on a Monday, what is the probability that
both children are girls?
a) \(\frac{13}{27}\)
b) \(\frac{23}{54}\)
c) \(\frac{12}{19}\)
d) \(\frac{43}{58}\)
Explanation: We let Y be the event that the family has one child who is a girl born on Tuesday and X be the event that both children are boys, and apply Bayes’ Theorem. Given that there are 7 days of the week and there are 49 possible combinations for the days of the week the two girls were born on and 13 of these have a girl who was born on a Monday, so P(Y|X) = \(\frac{13}{49}\). P(X) remains unchanged at \(\frac{1}{4}\). To calculate P(Y), there are 142 = 196 possible ways to select the gender and the day of the week the child was born on. There are 132 = 169 ways which do not have a girl born on Monday and which 196 – 169 = 27 which do, so P(Y) = \(\frac{27}{196}\). This gives is that P(X|Y) = \(\frac{\frac{13}{19}*\frac{1}{4}}{\frac{27}{196}} = \frac{13}{27}\).
7. Suppose a fair eight-sided die is rolled once. If the value on the
die is 1, 3, 5 or 7 the die is rolled a second time. Determine the
probability that the sum of values that turn up is at least 8?
a) \(\frac{32}{87}\)
b) \(\frac{12}{43}\)
c) \(\frac{6}{13}\)
d) \(\frac{23}{64}\)
Explanation: Sample space consists of 8*8=64 events. While (8) has \(\frac{1}{8}\) probability of occurrence, (1,7) has only \(\frac{1}{64}\) probability. So, the required probability = \(\frac{1}{6} + (9 * \frac{1}{64}) = \frac{69}{192} = \frac{23}{64}\).
8. A jar containing 8 marbles of which 4 red and 4 blue marbles are
there. Find the probability of getting a red given the first one was red
too.
a) \(\frac{4}{13}\)
b) \(\frac{2}{11}\)
c) \(\frac{3}{7}\)
d) \(\frac{8}{15}\)
Explanation: Suppose, P (A) = getting a red marble in the first turn, P (B) = getting a black marble in the second turn. P (A) = \(\frac{4}{8}\) and P (B) = \(\frac{3}{7}\) and P (A and B) = \(\frac{4}{8}*\frac{3}{7} = \frac{3}{14}\) P(B/A) = \(\frac{P(A \,and \,B)}{P(A)} = \frac{\frac{3}{14}}{\frac{1}{2}} = \frac{3}{7}\).
9. A bin contains 4 red and 6 blue balls and three balls are drawn at
random. Find the probability such that both are of the same color.
a) \(\frac{10}{28}\)
b) \(\frac{1}{5}\)
c) \(\frac{1}{10}\)
d) \(\frac{4}{7}\)
Explanation: Total no of balls = 10. Number of ways drawing 3 balls at random out of 10 = 10C3 = 120. Probability of drawing 3 balls of same colour = 4C3 + 6C3 = 24. Hence, the required probability is \(\frac{24}{120} = \frac{1}{5}\).
10. A bucket contains 6 blue, 8 red and 9 black pens. If six pens are
drawn one by one without replacement, find the probability of getting
all black pens?
a) \(\frac{8}{213}\)
b) \(\frac{8}{4807}\)
c) \(\frac{5}{1204}\)
d) \(\frac{7}{4328}\)
Explanation: Total number of pens = 23, number of pens we have chosen = 6, total number of black pens = 9. According to the combination probability formula it states that nCr = \(\frac{n!}{r! (n-r)!}\),
where n = total number of outcomes, r = random selection, P = \(\frac{^9C_6}{^{23}C_6} = \frac{8}{4807}\).
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Number of Relations”.
1. How many binary relations are there on a set S with 9 distinct elements?
a) 290
b) 2100
c) 281
d) 260
Explanation: S is the set with 9 elements. A relation on S is defined as S x S. There are 92 number of ordered pairs in relation. So, the number of binary relations is 2(9*9) = 281.
2. _________ number of reflexive relations are there on a set of 11 distinct elements.
a) 2110
b) 3121
c) 290
d) 2132
Explanation: Let A be a set consists of n distinct elements. There are 2(n*n)-n number of reflexive relations that can be formed. So, here the answer is 2(11*11)-11 = 2110.
3. The number of reflexive as well as symmetric relations on a set with 14 distinct elements is __________
a) 4120
b) 270
c) 3201
d) 291
Explanation: Let A be a set consists of n distinct elements. There are 2(n*(n-1))/2 number of reflexive and symmetric relations that can be formed. So, here the answer is 214*(14-1)/2 = 291.
4. The number of symmetric relations on a set with 15 distinct elements is ______
a) 2196
b) 250
c) 2320
d) 278
Explanation: Let S be a set consists of n distinct elements. There are 2(n-1)*(n-1) number of reflexive and symmetric relations that can be formed. So, here the answer is 2(15-1)*(15-1) = 2196.
5. Suppose S is a finite set with 7 elements. How many elements are there in the largest equivalence relation on S?
a) 56
b) 78
c) 49
d) 100
Explanation: Let R is an equivalence relation on the set S and so it satisfies the reflexive, symmetric and transitive property. The largest equivalence relation means it should contain the largest number of ordered pairs. Since we can have n2 ordered pairs in R x R where n belongs to S and all these ordered pairs are present in this relation; its the largest equivalence relation.So there are n2 elements i.e 72 = 49 elements in the largest equivalence relation.
6. ________ is the rank of the largest equivalence relation on a set of 20 elements.
a) 320
b) 2400
c) 20
d) 1
Explanation: The rank of an equivalence relation is the number of an equivalence classes. If we have a1, a2, a3, …, an elements then a1 and a2 will be in the same equivalence class because everything is related and so on. In this case, there is only one equivalence class.
7. How many elements are there in the smallest equivalence relation on a set with 8 elements?
a) 102
b) 8
c) 48
d) 32
Explanation: Let R is an equivalence relation on the set S with n elements and so it satisfies reflexive, symmetric and transitive properties. The smallest equivalence relation means it should contain minimum number of ordered pairs i.e along with symmetric and transitive properties it must always satisfy reflexive property. So, the smallest equivalence relation will have n ordered pairs and so the answer is 8.
8. The rank of smallest equivalence relation on a set with 12 distinct elements is _______
a) 12
b) 144
c) 136
d) 79
Explanation: In the case of smallest equivalence relation, each element is in one equivalence class like {a1}, {a2}, … are equivalence classes. So, the rank or number of equivalence classes is n for a set with n elements and so the answer is 12.
9. If a set A has 8 elements and a set B has 10 elements, how many relations are there from A to B?
a) 290
b) 380
c) 164
d) 280
Explanation: Let, a relation R from A to B is a subset of A×B. As the maximum number of subsets (Elements in the powerset) is 2mn, there are 2mn number of relations from A to B and so the answer is 280.
10. Synonym for binary relation is _______
a) equivalence relation
b) dyadic relation
c) orthogonal relation
d) one to many relations
Explanation: A binary relation on a set S is a set of ordered pairs of elements of S. It is a subset of the cartesian product S2 = S x S. The terms correspondence, dyadic relation and 2-place relation are synonyms for the binary relation.
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Relations – Partial Orderings”.
1. Let a set S = {2, 4, 8, 16, 32} and <= be the partial order
defined by S <= R if a divides b. Number of edges in the Hasse
diagram of is ______
a) 6
b) 5
c) 9
d) 4
Explanation: Hasse Diagram is:
32
/
16
/
8
/ \
2 4
So, the number of edges should be: 4.
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Graphs – Diagraph”.
1. A directed graph or digraph can have directed cycle in which ______
a) starting node and ending node are different
b) starting node and ending node are same
c) minimum four vertices can be there
d) ending node does not exist
Explanation: If the start node and end node are same in the path of a graph then it is termed as directed cycle i.e, c0 = cn. For instance, a c b a is a simple cycle in which start and end nodes are same(a). But, a c b b a is not a simple cycle as there is a loop <b,b>.
2. Let, D = <A, R> be a directed graph or digraph,then D’ = <A’, R’> is a subgraph if ___________
a) A’ ⊂ A and R’ = R ∩ (A’ x A’)
b) A’ ⊂ A and R ⊂ R’ ∩ (A’ x A’)
c) R’ = R ∩ (A’ x A’)
d) A’ ⊆ A and R ⊆ R’ ∩ (A’ x A’)
Explanation: A directed graph or digraph is an ordered pair D<A, R> where A(is a set of nodes of D) is a set and R(the elements of R are the arcs of D) is a binary relation on A. The relation R is called the incidence relation on D. Now, a digraph is a subgraph of D if i)A’ ⊂ A and ii)R’ = R ∩ (A’ x A’). If D’ D, D’ is a proper subgraph of D.
3. The graph representing universal relation is called _______
a) complete digraph
b) partial digraph
c) empty graph
d) partial subgraph
Explanation: Consider, A is a graph with vertices {a, b, c, d} and the universal relation is A x A. The graph representing universal relation is called a complete graph and all ordered pairs are present there.
4. What is a complete digraph?
a) connection of nodes without containing any cycle
b) connecting nodes to make at least three complete cycles
c) start node and end node in a graph are same having a cycle
d) connection of every node with every other node including itself in a digraph
Explanation: Every node should be connected to every other node including itself in a digraph is the complete digraph. Now, graphs are connected, strongly connected and disconnected
5. Disconnected components can be created in case of ___________
a) undirected graphs
b) partial subgraphs
c) disconnected graphs
d) complete graphs
Explanation: By the deletion of one edge from either connected or strongly connected graphs the graph obtained is termed as a disconnected graph. It can have connected components separated by the deletion of the edges. The edge that has to be deleted called cut edge.
6. A simple graph can have _______
a) multiple edges
b) self loops
c) parallel edges
d) no multiple edges, self-loops and parallel edges
Explanation: If a graph say G = <V, E> has no parallel or multiple edges and no self loops contained in it is called a simple graph. An undirected graph may have multiple edges and self-loops.
7. Degree of a graph with 12 vertices is _______
a) 25
b) 56
c) 24
d) 212
Explanation: Number of edges incident on a graph is known as degree of a vertex. Sum of degrees of each vertex is called total degree of the graph. Total degree = 2 * number of vertices. So, if there are 24 vertices then total degree is 24.
8. In a finite graph the number of vertices of odd degree is always ______
a) even
b) odd
c) even or odd
d) infinite
Explanation: In any finite graph, sum of degree of all the vertices = 2 * number of edges.
Sum of degree of all the vertices with even degree + sum of degree of all the vertices with odd degree = 2 * number of edges. Now, even number + sum of degree of all the vertices with odd degree = even number. It is possible if and only if number of odd degree vertices are even.
9. An undirected graph has 8 vertices labelled 1, 2, …,8 and 31
edges. Vertices 1, 3, 5, 7 have degree 8 and vertices 2, 4, 6, 8 have
degree 7. What is the degree of vertex 8?
a) 15
b) 8
c) 5
d) 23
Explanation: Vertices 1, 3, 5, 7 have degree 8 and vertices 2, 4, 6, 8 have degree 7. By definition, sum of degree= 2 * No of edges
Let x = degree of vertex 8
8 + 7 + 8 + 7 + 8 + 7 + 8 + x = 2 * 31
53 + x = 61
x = 8
Hence, degree of vertex 8 is 8.
10. G is an undirected graph with n vertices and 26 edges such that
each vertex of G has a degree at least 4. Then the maximum possible
value of n is ___________
a) 7
b) 43
c) 13
d) 10
Explanation: Let m be min degree and M be a max degree of a graph, then m ≤ 2E/V ≤ M. Here, m=4, E=26, v=?
So, 4 ≤ (2*26)/V
V ≤ (52/4)
V ≤ 13 ⇒ V = 13.
This set of Tricky Discrete Mathematics Questions and Answers focuses on “Complete and Connected Graphs”.
1. A bridge can not be a part of _______
a) a simple cycle
b) a tree
c) a clique with size ≥ 3 whose every edge is a bridge
d) a graph which contains cycles
Explanation: In a connected graph, a bridge is an edge whose removal disconnects the graph. In a cycle if we remove an edge, it will still be connected. So, bridge cannot be part of a cycle. A clique is any complete subgraph of a graph.
2. Any subset of edges that connects all the vertices and has minimum
total weight, if all the edge weights of an undirected graph are
positive is called _______
a) subgraph
b) tree
c) hamiltonian cycle
d) grid
Explanation: If all the edge weights of an undirected graph are positive, any subset of edges that connects all the vertices and has minimum total weight is termed as a tree. In this case, we need to have a minimum spanning tree need to be exact.
3. G is a simple undirected graph and some vertices of G are of odd
degree. Add a node n to G and make it adjacent to each odd degree vertex
of G. The resultant graph is ______
a) Complete bipartite graph
b) Hamiltonian cycle
c) Regular graph
d) Euler graph
Explanation: In any simple undirected graph, total degree of all vertices is even (since each edge contributes 2 degrees). So number of vertices having odd degrees must be even, otherwise, their sum would have been odd, making total degree also odd. Now single vertex n is connected to all these even number of vertices (which have odd degrees). So, degree of n is also even. Moreover, now degree of all vertices which are connected to v is increased by 1, hence earlier vertices which had odd degree now have even degree. So now, all vertices in the graph have even degree, which is necessary and sufficient condition for euler graph.
4. Let G be a directed graph whose vertex set is the set of numbers
from 1 to 50. There is an edge from a vertex i to a vertex j if and only
if either j = i + 1 or j = 3i. Calculate the minimum number of edges in
a path in G from vertex 1 to vertex 50.
a) 98
b) 13
c) 6
d) 34
Explanation: Edge set consists of edges from i to j using either 1) j = i+1 OR 2) j=3i. The trick to solving this question is to think in a reverse way. Instead of finding a path from 1 to 50, try to find a path from 100 to 1. The edge sequence with the minimum number of edges is 1 – 3 – 9 – 10 – 11 – 33 which consists of 6 edges.
5. What is the number of vertices in an undirected connected graph
with 39 edges, 7 vertices of degree 2, 2 vertices of degree 5 and
remaining of degree 6?
a) 11
b) 14
c) 18
d) 19
Explanation: We know that, sum of degree of all the vertices = 2 * number of edges
2*7 + 5*2 + 6*x = 39*2
x=9
Number of vertices = 7 + 2 + 9 = 18.
6. ______ is the maximum number of edges in an acyclic undirected graph with k vertices.
a) k-1
b) k2
c) 2k+3
d) k3+4
Explanation: This is possible with spanning trees since, a spanning tree with k nodes has k – 1 edges.
7. The minimum number of edges in a connected cyclic graph on n vertices is _____________
a) n – 1
b) n
c) 2n+3
d) n+1
Explanation: For making a cyclic graph, the minimum number of edges have to be equal to the number of vertices. SO, the answer should be n minimum edges.
8. The maximum number of edges in a 8-node undirected graph without self loops is ____________
a) 45
b) 61
c) 28
d) 17
Explanation: In a graph of n vertices we can draw an edge from a vertex to n-1 vertex we will do it for n vertices and so total number of edges is n*(n-1). Now each edge is counted twice so the required maximum number of edges is n*(n-1)/2. Hence, 8*(8-1)/2 = 28 edges.
9. Let G be an arbitrary graph with v nodes and k components. If a
vertex is removed from G, the number of components in the resultant
graph must necessarily lie down between _____ and _____
a) n-1 and n+1
b) v and k
c) k+1 and v-k
d) k-1 and v-1
Explanation: If a vertex is removed from the graph, lower bound: number of components decreased by one = k-1 (remove an isolated vertex which was a component) and upper bound: number of components = v-1 (consider a vertex connected to all other vertices in a component as in a star and all other vertices outside this component being isolated. Now, removing the considered vertex makes all other (v-1) vertices isolated making (v-1) components.
10. The 2n vertices of a graph G corresponds to all
subsets of a set of size n, for n>=4. Two vertices of G are adjacent
if and only if the corresponding sets intersect in exactly two elements.
The number of connected components in G can be ___________
a) n+2
b) 3n/2
c) n2
d) 2n
Explanation: n+1(subsets of size < 2 are all disconnected) (subsets of size >= 2 are all connected)+1(subset of size >= 2 are all connected)=n+2 is the number of connected components in G.
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Properties of Tree”.
1. An undirected graph G which is connected and acyclic is called ____________
a) bipartite graph
b) cyclic graph
c) tree
d) forest
Explanation: An undirected graph G which is connected and acyclic is termed as a tree. G contains no cycles and if any edge is added to G a simple cycle is formed.
2. An n-vertex graph has ______ edges.
a) n2
b) n-1
c) n*n
d) n*(n+1)/2
Explanation: Suppose G is a connected graph which has no cycles. Every subgraph of G includes at least one vertex with zero or one incident edges. It has n vertices and n-1 edges. Generally, the order-zero graph is not considered to be a tree.
3. What is a star tree?
a) A tree having a single internal vertex and n-1 leaves
b) A tree having n vertices arranged in a line
c) A tree which has 0 or more connected subtrees
d) A tree which contains n vertices and n-1 cycles
Explanation: A star tree of order n is a tree with as many leaves as possible or in other words a star tree is a tree that consists of a single internal vertex and n-1 leaves. However, an internal vertex is a vertex of degree at least 2.
4. A polytree is called _______________
a) directed acyclic graph
b) directed cyclic graph
c) bipartite graph
d) connected graph
Explanation: A directed acyclic graph is known as a polytree whose underlying undirected graph is a tree. In other words, a directed tree is a directed graph which would be tree if the directions on the edges were ignored.
5. The tree elements are called __________
a) vertices
b) nodes
c) points
d) edges
Explanation: Every tree element is called a node and the lines connecting the elements are called branches. A finite tree structure has a member that has no superior and is called the “root” Or root node. Nodes that have no child are called leaf nodes.
6. In an n-ary tree, each vertex has at most ______ children.
a) n
b) n4
c) n*n
d) n-1
Explanation: An n-ary tree is a rooted tree in which each vertex has at most n children. 2-ary trees are termed as binary trees, 3-ary trees are sometimes called ternary trees.
7. A linear graph consists of vertices arranged in a line.
a) false
b) true
c) either true or false
d) cannot determined
Explanation: A linear graph also known as a path graph is a graph which consists of k vertices arranged in a line, so that vertices from i and i+1 are connected by an edge for i=0,…, k-1.
8. Two labeled trees are isomorphic if ____________
a) graphs of the two trees are isomorphic
b) the two trees have same label
c) graphs of the two trees are isomorphic and the two trees have the same label
d) graphs of the two trees are cyclic
Explanation: The number of labeled trees of k number of vertices is kn-2. Two labeled trees are isomorphic if their graphs are isomorphic and the corresponding points of the two trees have the same labels.
9. A graph which consists of disjoint union of trees is called ______
a) bipartite graph
b) forest
c) caterpillar tree
d) labeled tree
Explanation: A forest is an undirected acyclic graph in which all the connected components are individual trees. This graph contains a disjoint union of trees.
10. What is a bipartite graph?
a) a graph which contains only one cycle
b) a graph which consists of more than 3 number of vertices
c) a graph which has odd number of vertices and even number of edges
d) a graph which contains no cycles of odd length
Explanation: A graph is called a bipartite graph if and only if it contains no cycle of odd length. Every tree is a bipartite graph and a median graph.
This set of Discrete Mathematics Question Paper focuses 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
Explanation: 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
Explanation: 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
Explanation: 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
Explanation: 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
Explanation: 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
Explanation: 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 +
Explanation: 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
Explanation: 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
Explanation: 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.
Explanation: 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.
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Boolean Algebra”.
1. Algebra of logic is termed as ______________
a) Numerical logic
b) Boolean algebra
c) Arithmetic logic
d) Boolean number
Explanation: The variables that can have two discrete values False(0) and True(1) and the operations of logical significance are dealt with Boolean algebra.
2. Boolean algebra can be used ____________
a) For designing of the digital computers
b) In building logic symbols
c) Circuit theory
d) Building algebraic functions
Explanation: For designing digital computers and building different electronic circuits boolean algebra is accepted widely.
3. What is the definition of Boolean functions?
a) An arithmetic function with k degrees such that f:Y–>Yk
b) A special mathematical function with n degrees such that f:Yn–>Y
c) An algebraic function with n degrees such that f:Xn–>X
d) A polynomial function with k degrees such that f:X2–>Xn
Explanation: A Boolean function is a special mathematical function with n degrees and where Y = {0,1} is the Boolean domain with being a non-negative integer. It helps in describing the way in which the Boolean output is derived from Boolean inputs.
4. F(X,Y,Z,M) = X`Y`Z`M`. The degree of the function is ________
a) 2
b) 5
c) 4
d) 1
Explanation: This is a function of degree 4 from the set of ordered pairs of Boolean variables to the set {0,1}.
5. A ________ value is represented by a Boolean expression.
a) Positive
b) Recursive
c) Negative
d) Boolean
Explanation: A Boolean value is given by a Boolean expression which is formed by combining Boolean variables and logical connectives.
6. Which of the following is a Simplification law?
a) M.(~M+N) = M.N
b) M+(N.O) = (M+N)(M+O)
c) ~(M+N) = ~M.~N
d) M.(N.O) = (M.N).O
Explanation: By Simplification Law we can have X.(~X+Y) = X.Y and X+(~X.Y) = X+Y. By, De’ Morgan’s law ~(X+Y) = ~X.~Y. By commutative law we can say that A.(B.C) = (A.B).C.
7. What are the canonical forms of Boolean Expressions?
a) OR and XOR
b) NOR and XNOR
c) MAX and MIN
d) SOM and POM
Explanation: There are two kinds of canonical forms for a Boolean expression-> 1)sum of minterms(SOM) form and
2)product of maxterms(SOM) form.
8. Which of the following is/are the universal logic gates?
a) OR and NOR
b) AND
c) NAND and NOR
d) NOT
Explanation: NAND and NOR gates are known as the universal logic gates. A universal gate is a gate which can implement any Boolean function without the help of 3 basic gate types.
9. The logic gate that provides high output for same inputs ____________
a) NOT
b) X-NOR
c) AND
d) XOR
Explanation: The logic gate which gives high output for the same inputs, otherwise low output is known as X-NOR or Exclusive NOR gate.
10. The ___________ of all the variables in direct or complemented from is a maxterm.
a) addition
b) product
c) moduler
d) subtraction
Explanation: The Boolean function is expressed as a sum of the 1-minterms and the inverse of function is represented as 0-minterms.
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Boolean Algebra – Interconversion of Gates”.
1. In order to make a luggage security alarm, a single _____ is used.
a) NOR gate
b) NAND gate
c) X-NOR gate
d) XOR gate
Explanation: The NAND gate consists of two inputs and if both of them are high the output is low. A luggage security alarm circuit is a system which is based on the NAND gate. It is used to generate an alarm when any authorized person tries to steal the luggage.
2. In Boolean algebra, the data is a bit-representation of information consists of _________
a) 0 and 1
b) 2 and 5
c) 1 and 15
d) 4 and 8
Explanation: The data, in boolean algebra must be in a bit-representation form which can be in between two values 0 and 1.
3. Using which component a shift register is implemented?
a) register
b) transistor
c) latch
d) flip-flop
Explanation: A shift register, in digital circuitry, is a combination of two or more flip-flops to share the bits of information by using the same clock. A shift register can have both parallel and serial inputs and outputs.
4. How many NAND gates are required to make an XOR gate?
a) 7
b) 12
c) 4
d) 8
Explanation: An XOR gate is created by using four NAND gates. This construction gives a propagation delay three times to that of a single NAND gate.
5. In Multiplexer gate, for selecting the inputs, two bits named _____ and _____ are required generally.
a) selector bit, data bit
b) parity bit. Generator bit
c) input bit, inverted bit
d) raising bit, sinking bit
Explanation: In multiplexer gate for selecting the inputs say, for 3 input bits, one bit is required as selector bit and two other bits are required as data bits.
6. A NOR gate can be derived from ______
a) NAND gate
b) XOR gate
c) AND gate
d) OR gate
Explanation: NAND and NOR gates are called universal gates. As we can generate any of the basic gates as well as other gates from these two gates. So, a NOR gate can be made by a NAND gate.
7. In which logic gate the output state is usually the complement of the input state?
a) NOT gate
b) NOR gate
c) X-NOR gate
d) OR gate
Explanation: NOT gate is the simplest digital logic circuit which is also called an inverter because it takes the input in 0 or 1 form and gives the output as the complement of the input.
8. In OR gate for 13 numbers of inputs what are the stages possible for it?
a) 1239
b) 213
c) 13
d) 1387
Explanation: OR gate works in a way such that if any of the input is binary low(or 0), the output of the gate is binary 1(or high). Here, the number of stage possible = 2n = 213.
9. Which of the following is built exclusively from NOR gate?
a) Plant guard machine
b) Apollo Guidance Computer
c) Street market app
d) Dish washer
Explanation: The first embedded system is the Apollo Guidance Computer which was built exclusively from NOR gates. A logically inverted OR gate is a NOR gate and it can have two or more inputs.
10. Which of the following gates is used to implement a logical conditional?
a) OR gate
b) Magnetic logic gate
c) XOR gate
d) IMPLY gate
Explanation: The IMPLY gate is a digital logic gate that is used to implements logical conditional. Two symbols are used to represent the IMPLY gates → the traditional symbol and the IEEE symbol. IMPLY gate can be made by two memristors.
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Group Theory”.
1. A non empty set A is termed as an algebraic structure ________
a) with respect to binary operation *
b) with respect to ternary operation ?
c) with respect to binary operation +
d) with respect to unary operation –
Explanation: A non empty set A is called an algebraic structure w.r.t binary operation “*” if (a*b) belongs to S for all (a*b) belongs to S. Therefore “*” is closure operation on ‘A’.
2. An algebraic structure _________ is called a semigroup.
a) (P, *)
b) (Q, +, *)
c) (P, +)
d) (+, *)
Explanation: An algebraic structure (P,*) is called a semigroup if a*(b*c) = (a*b)*c for all a,b,c belongs to S or the elements follow associative property under “*”. (Matrix,*) and (Set of integers,+) are examples of semigroup.
3. Condition for monoid is __________
a) (a+e)=a
b) (a*e)=(a+e)
c) a=(a*(a+e)
d) (a*e)=(e*a)=a
Explanation: A Semigroup (S,*) is defined as a monoid if there exists an element e in S such that (a*e) = (e*a) = a for all a in S. This element is called identity element of S w.r.t *.
4. A monoid is called a group if _______
a) (a*a)=a=(a+c)
b) (a*c)=(a+c)
c) (a+c)=a
d) (a*c)=(c*a)=e
Explanation: A monoid(B,*) is called Group if to each element there exists an element c such that (a*c)=(c*a)=e. Here e is called an identity element and c is defined as the inverse of the corresponding element.
5. A group (M,*) is said to be abelian if ___________
a) (x+y)=(y+x)
b) (x*y)=(y*x)
c) (x+y)=x
d) (y*x)=(x+y)
Explanation: A group (M,*) is said to be abelian if (x*y) = (x*y) for all x, y belongs to M. Thus Commutative property should hold in a group.
6. Matrix multiplication is a/an _________ property.
a) Commutative
b) Associative
c) Additive
d) Disjunctive
Explanation: The set of two M*M non-singular matrices form a group under matrix multiplication operation. Since matrix multiplication is itself associative, it holds associative property.
7. A cyclic group can be generated by a/an ________ element.
a) singular
b) non-singular
c) inverse
d) multiplicative
Explanation: A singular element can generate a cyclic group. Every element of a cyclic group is a power of some specific element which is known as a generator ‘g’.
8. How many properties can be held by a group?
a) 2
b) 3
c) 5
d) 4
Explanation: A group holds five properties simultaneously –
i) Closure
ii) associative
iii) Commutative
iv) Identity element
v) Inverse element.
9. A cyclic group is always _________
a) abelian group
b) monoid
c) semigroup
d) subgroup
Explanation: A cyclic group is always an abelian group but every abelian group is not a cyclic group. For instance, the rational numbers under addition is an abelian group but is not a cyclic one.
10. {1, i, -i, -1} is __________
a) semigroup
b) subgroup
c) cyclic group
d) abelian group
Explanation: The set of complex numbers {1, i, -i, -1} under multiplication operation is a cyclic group. Two generators i and -i will covers all the elements of this group. Hence, it is a cyclic group.
This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on “Groups – Cosets”.
1. a * H is a set of _____ coset.
a) right
b) left
c) sub
d) semi
Explanation: Let (H, *) be the semigroup of the group (G, *). Let a belongs to G. (a * H) is the set of a left coset of H in G and (H * a) be the set of a right coset of H in G.
2. a * H = H * a relation holds if __________
a) H is semigroup of an abelian group
b) H is monoid of a group
c) H is a cyclic group
d) H is subgroup of an abelian group
Explanation: If h is the subgroup of an abelian group G, then the set of left cosets of H in G is to be set of right cosets i.e, a * H = H * a. Hence, subgroup is called the normal subgroup.
3. Lagrange’s theorem specifies __________
a) the order of semigroup is finite
b) the order of the subgroup divides the order of the finite group
c) the order of an abelian group is infinite
d) the order of the semigroup is added to the order of the group
Explanation: Lagrange’s theorem satisfies that the order of the subgroup divides the order of the finite group.
4. A function is defined by f(x)=2x and f(x + y) = f(x) + f(y) is called _____________
a) isomorphic
b) homomorphic
c) cyclic group
d) heteromorphic
Explanation: Let (G,*) and (G’,+) are two groups. The mapping f:G->G’ is said to be isomorphism if two conditions are satisfied 1) f is one-to-one function and onto function and 2) f satisfies homomorphism.
5. An isomorphism of a group onto itself is called ____________
a) homomorphism
b) heteromorphism
c) epimorphism
d) automorphism
Explanation: An automorphism is defined as an isomorphism of a group onto itself. Similarly, the homomorphism of a group onto itself is defined as the endomorphism of the group.
6. The elements of a vector space form a/an ____________ under vector addition.
a) abelian group
b) commutative group
c) associative group
d) semigroup
Explanation: An example of a coset is associated with the theory of vector spaces. The elements (vectors) form an abelian group under the vector addition in a vector space. Subspaces of a vector space are subgroups of this group.
7. A set of representatives of all the cosets is called _________
a) transitive
b) reversal
c) equivalent
d) transversal
Explanation: A coset representative is a representative in the equivalence class. In all cosets, a set of the representative is always transversal.
8. Which of the following statement is true?
a) The set of all rational negative numbers forms a group under multiplication
b) The set of all matrices forms a group under multiplication
c) The set of all non-singular matrices forms a group under multiplication
d) The set of matrices forms a subgroup under multiplication
Explanation: Since multiplication of two negative rational numbers gives a positive number. Hence, closure property is not satisfied. Singular matrices do not form a group under multiplication. Matrices have to be non-singular (determinant !=0) for the inverse to exist. Hence the set of all non-singular matrices forms a group under multiplication is a true option.
9. How many different non-isomorphic Abelian groups of order 8 are there?
a) 5
b) 4
c) 2
d) 3
Explanation: The number of Abelian groups of order Pm (let, P is prime) is the number of partitions of m. Here order is 8 i.e. 23 and so partition of 3 are {1, 1} and {3, 0}. So number of different abelian groups are 2.
10. Consider the set B* of all strings over the alphabet set B = {0, 1} with the concatenation operator for strings ________
a) does not form a group
b) does not have the right identity element
c) forms a non-commutative group
d) forms a group if the empty string is removed from
Explanation: Identity element for concatenation is an empty string. Now, we cannot concatenate any string with a given string to get empty string there is no inverse for string concatenation. Only other 3 group properties such as closure, associative and existence of identity are satisfied.
