Category: Discrete Mathematics Objective Questions

Discrete Mathematics Multiple Choice Questions 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

Answer: b
Clarification: 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

Answer: a
Clarification: 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

Answer: d
Clarification: 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

Answer: c
Clarification: 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

Answer: a
Clarification: 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

Answer: a
Clarification: 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

Answer: a
Clarification: 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

Answer: b
Clarification: 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 = 2ⁿ = 2¹³.

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

Answer: b
Clarification: 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

Answer: d
Clarification: 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.

Discrete Mathematics Multiple Choice Questions on “Logics – Inference”.

1. Which rule of inference is used in each of these arguments, “If it is Wednesday, then the Smartmart will be crowded. It is Wednesday. Thus, the Smartmart is crowded.”
a) Modus tollens
b) Modus ponens
c) Disjunctive syllogism
d) Simplification

Answer: b
Clarification: (M ∧ (M → N)) → N is Modus ponens.

2. Which rule of inference is used in each of these arguments, “If it hailstoday, the local office will be closed. The local office is not closed today. Thus, it did not hailed today.”
a) Modus tollens
b) Conjunction
c) Hypothetical syllogism
d) Simplification

Answer: a
Clarification: (¬N ∧ (M → N)) → ¬M is Modus tollens.

3. Which rule of inference is used, ”Bhavika will work in an enterprise this summer. Therefore, this summer Bhavika will work in an enterprise or he will go to beach.”
a) Simplification
b) Conjunction
c) Addition
d) Disjunctive syllogism

Answer: c
Clarification: p → (p ∨ q) argument is ‘Addition’.

4. What rule of inference is used here?
“It is cloudy and drizzling now. Therefore, it is cloudy now.”
a) Addition
b) Simplification
c) Resolution
d) Conjunction

Answer: b
Clarification: (p ∧ q) → p argument is Simplification.

5. What rule of inference is used in this argument?
“If I go for a balanced diet, then I will be fit. If I will be fit, then I will remain healthy. Therefore, if I go for a balanced diet, then I will remain healthy.”
a) Modus tollens
b) Modus ponens
c) Disjunctive syllogism
d) Hypothetical syllogism

Answer: d
Clarification: ((p → q) ∧ (q → r)) → (p → r) argument is ‘Hypothetical syllogism’.

6. What rules of inference are used in this argument?
“All students in this science class has taken a course in physics” and “Marry is a student in this class” imply the conclusion “Marry has taken a course in physics.”
a) Universal instantiation
b) Universal generalization
c) Existential instantiation
d) Existential generalization

Answer: a
Clarification: ∀xP (x), ∴ P (c) Universal instantiation.

7. What rules of inference are used in this argument?
“It is either colder than Himalaya today or the pollution is harmful. It is hotter than Himalaya today. Therefore, the pollution is harmful.”
a) Conjunction
b) Modus ponens
c) Disjunctive syllogism
d) Hypothetical syllogism

Answer: c
Clarification: ((p ∨ q) ∧ ¬p) → q argument is Disjunctive syllogism.

8. The premises (p ∧ q) ∨ r and r → s imply which of the conclusion?
a) p ∨ r
b) p ∨ s
c) p ∨ q
d) q ∨ r

Answer: b
Clarification: The premises (p ∧ q) ∨ r has two clauses: p ∨ r, and q ∨ r. We can also replace r → s with the equivalent clause r ∨ s. Using the two clauses p ∨ r and r ∨ s, we can conclude p ∨ s.

9. What rules of inference are used in this argument?
“Jay is an awesome student. Jay is also a good dancer. Therefore, Jay is an awesome student and a good dancer.”
a) Conjunction
b) Modus ponens
c) Disjunctive syllogism
d) Simplification

Answer: a
Clarification: ((p) ∧ (q)) → (p ∧ q) argument is conjunction.

10. “Parul is out for a trip or it is not snowing” and “It is snowing or Raju is playing chess” imply that __________
a) Parul is out for trip
b) Raju is playing chess
c) Parul is out for a trip and Raju is playing chess
d) Parul is out for a trip or Raju is playing chess

Answer: d
Clarification: Let p be “It is snowing,” q be “Parul is out for a trip,” and r the proposition “Raju is playing chess.” The hypotheses as ¬p ∨ q and p ∨ r, respectively. Using resolution, the proposition q ∨ r is, “Parul is out for a trip or Raju is playing chess.”

Discrete Mathematics Multiple Choice Questions on “Geometric Sequences”.

1. Let the sequence be 2, 8, 32, 128,……… then this sequence is _______________
a) An arithmetic sequence
b) A geometic progression
c) A harmonic sequence
d) None of the mentioned

Answer: b
Clarification: The ratio of any term with previous term is same.

2. In the given Geometric progression find the number of terms.

32, 256, 2048, 16384,.........,250.

a) 11
b) 13
c) 15
d) None of the mentioned

Answer: d
Clarification: n^th term = first term(ratio^{n – 1})., 2⁵⁰ = 2⁵(2^3(n-1)), n=15. This implies 16^th term.

3. In the given Geometric progression the term at position 11 would be ___________

32, 256, 2048, 16384,.........,250.

a) 2³⁵
b) 2⁴⁵
c) 35
d) None of the mentioned

Answer: a
Clarification: n^th term = first term(ratio^{n – 1})., g_n = 2⁵(2^3(n-1)), n=11. This implies 2³⁵.

4. For the given Geometric progression find the position of first fractional term?

250, 247, 244,.........

a) 17
b) 20
c) 18
d) None of the mentioned

Answer: c
Clarification: Let n^th term=1, the next term would be first fractional term.
G_n = 1 = 2⁵⁰(2^3(-n+1)), n=17.66.. therfore at n = 18 the first fractional term would occur.

5. For the given geometric progression find the first fractional term?

250, 247, 244,.........

a) 2^-1
b) 2^-2
c) 2^-3
d) None of the mentioned

Answer: a
Clarification: Let n^th term=1, the next term would be first fractional term.
G_n = 1 = 2⁵⁰( 2 ^3(-n+1)), n=17.66. Therefore at n=18 the first fractional term would occur. G_n = 2⁵⁰( 2 ^3(-n+1)), G₁₈ = 2^-1.

6. State whether the given statement is true or false.

1, 1, 1, 1, 1........ is a GP series.

a) True
b) False

Answer: a
Clarification: The ratio of any term with previous term is same.

7. In the given Geometric progression, ‘2²⁵‘ would be a term in it.

32, 256, 2048, 16384,.........,250.

a) True
b) False

Answer: b
Clarification: n^th term = first term(ratio^{n – 1})., g_n = 2²⁵ = 2⁵ (2 ^3(n-1)), n=23/3, n=7.666 not an integer. Thus 2²⁵ is not a term in this series.

8. Which of the following sequeces in GP will have common ratio 3, where n is an Integer?
a) g_n = 2n² + 3n
b) g_n = 2n² + 3
c) g_n = 3n² + 3n
d) g_n = 6(3^n-1)

Answer: d
Clarification: g_n = 6( 3^n-1) it is a geometric expression with coefficient of constant as 3^n-1.So it is GP with common ratio 3.

9. If a, b, c are in GP then relation between a, b, c can be ___________
a) 2b = 2a + 3c
b) 2a = b+c
c) b =(ac)^1/2
d) 2c = a + c

Answer: c
Clarification: The term b should be the geometric mean of of term a and c.

10. Let the multiplication of the 3 consecutive terms in GP be 8 then midlle of those 3 terms would be _______
a) 2
b) 3
c) 4
d) 179

Answer: a
Clarification: Let a, b, c be three terms, then a/r * a * ar = 8, b = (ac)^1/2 (G M property), b³ = 8, b = 2.

Discrete Mathematics Multiple Choice Questions on “Algorithms – Integers and Division”.

1. The quotient when 19 is divided by 6 is?
a) 1
b) 2
c) 3
d) 0

Answer: c
Clarification: According to the Division Algorithm 19 = 6(3) + 1. Hence, quotient when 19 divided by 6 is 3 = 19 div 6.

2. The remainder when 111 is divided by 12 is?
a) 0
b) 1
c) 2
d) 3

Answer: d
Clarification: According to the Division Algorithm 111 = 12(9) + 3. Hence, remainder when 111 divided by 12 is 3 = 111 mod 12.

3. The quotient and remainder when -1 is divided by 3 is?
a) -1 and -1
b) -1 and 2
c) 1 and 2
d) -1 and -2

Answer: b
Clarification: According to the Division Algorithm -1 = 3(-1) + 2. Hence, quotient when -1 divided by 3 is -1 = -1 div 3 and remainder when -1 divided by 3 is 2 = -1 mod 3.

4. The value of 12 mod 3 is?
a) 0
b) 1
c) 2
d) 3

Answer: a
Clarification: By the Division algorithm 12 = 3(4) + 0. Where remainder is 12 mod 3.

5. The value of 155 mod 9 is?
a) 0
b) 1
c) 2
d) 3

Answer: c
Clarification: By the Division algorithm 155 = 9(17) + 2. Where remainder is 155 mod 9.

6. Is 17 congruent to 4 modulo 6.
a) True
b) False

Answer: b
Clarification: 6 does not divide 17 – 4 = 13.

7. If a|b and a|c, then?
a) a|bc
b) c|a
c) a|(b+c)
d) b|a

Answer: c
Clarification: If a|b and a|c then b = am and c = an for some integer m and n. Hence, b + c = a(m + n). Therefore, a|(b+c).

8. Is 102 congruent to 6 modulo 16.
a) True
b) False

Answer: a
Clarification: 16 divide 102 – 6 = 96.

9. The quotient and remainder when 18 is divided by 5 is?
a) 2 and 3
b) 1 and 2
c) 3 and 2
d) 3 and 3

Answer: d
Clarification: According to the Division Algorithm 18 = 5(3) + 3. Hence, quotient when 18 divided by 5 is 3 = 18 div 5 and remainder when 18 divided by 5 is 3 = 18 mod 5.

10. The value of 15 mod 11 is?
a) 1
b) 2
c) 3
d) 4

Answer: d
Clarification: By the Division algorithm 15 = 11(1) + 4. Where the remainder is 15 mod 11.

Discrete Mathematics Multiple Choice Questions 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

Answer: b
Clarification: 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

Answer: a
Clarification: 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

Answer: b
Clarification: 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

Answer: c
Clarification: 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

Answer: a
Clarification: 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

Answer: a
Clarification: 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

Answer: b
Clarification: We can have recurrence relation for tower of hanoi and that is h_n = 2 h_n-1 + 1h₁ = 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

Answer: a
Clarification: 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

Answer: a
Clarification: 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) 3⁵⁸
c) 56
d) 2⁵⁵

Answer: d
Clarification: 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 2^h+1 Null pointers as children.
h = 54
2⁵⁴⁺¹
2⁵⁵.

Discrete Mathematics Multiple Choice Questions on “Probability Distribution”.

1. Two fair coins are flipped. As a result of this, tails and heads runs occurred where a tail run is a consecutive occurrence of at least one head. Determine the probability function of number of tail runs.
a) (frac{1}{2})
b) (frac{5}{6})
c) (frac{32}{19})
d) (frac{6}{73})

Answer: a
Clarification: The sample space of the experiment is S = {HH, HT, TH, TT}. Let X is the number of tails and It takes up the values 0, 1 and 2. Now, P(no tail) = p(0) = (frac{1}{4}), P(one tail) = p(1) = (frac{2}{4}) and P(two tails) = p(2) = (frac{1}{4}). So, X is the number of tail runs and it takes up the values 0 and 1. P(X = 0) = p(0) = (frac{2}{4} = frac{1}{4}).

2. The length of alike metals produced by a hardware store is approximated by a normal distribution model having a mean of 7 cm and a standard deviation of 0.35 cm. Find the probability that the length of a randomly chosen metal is between 5.36 and 6.14 cm?
a) 0.562
b) 0.2029
c) 3.765
d) 1.576

Answer: b
Clarification: Let L be the random variable that represents the length of the component. It has a mean of 7 cm and a standard deviation of 0.35 cm. To find P( 5.36 < x < 6.14). For x = 5.36, z = (frac{5.36 – 6}{0.35}) = -1.82. For x = 6.14, z = (frac{6.14 – 6}{0.35}) = 0.4 ⇒ P(5.36 < x < 6.14) = P( -1.82 < z < 0.4) = 0.2029.

3. A personal computer has the length of time between charges of the battery is normally distributed with a mean of 66 hours and a standard deviation of 20 hours. What is the probability when the length of time will be between 58 and 75 hours?
a) 0.595
b) 3.44
c) 0.0443
d) 1.98

Answer: c
Clarification: Suppose x be the random variable that represents the length of time. It has a mean of 66 and a standard deviation of 20. Find the probability that x is between 70 and 90 or P(70 < x < 90). For x = 70, z = (frac{58 – 66}{20}) = -4. For x = 75, z = (frac{75 – 66}{20}) = 0.45. P(70 < x < 90) = P(-4 < z < 0.75) = [area to the left of z = 0.75] – [area to the left of z = -4] = 0.0443. The required probability when the length of time between 58 and 75 hours is 0.0443.

4. The length of life of an instrument produced by a machine has a normal distribution with a mean of 9.4 months and a standard deviation of 3.2 months. What is the probability that an instrument produced by this machine will last between 6 and 11.6 months?
a) 0.642
b) 0.4098
c) 0.16
d) 0.326

Answer: d
Clarification: We have to find P(6 < x < 11.6). Now, for x = 6, z becomes -1.062 and for z = 11.6, z = 0.687. So, P(6 < x < 11.6) = P(-1.062 < z < 0.687) = 0.326.

5. The speeds of a number of bicycles have a normal distribution model with a mean of 83 km/hr and a standard deviation of 9.4 km/hr. Find the probability that a bicycle picked at random is travelling at more than 95 km/hr?
a) 0.1587
b) 0.38
c) 0.49
d) 0/278

Answer: b
Clarification: Let x be the random variable that represents the speed of bicycle. x has μ = 90 and σ = 9.5. We have to find the probability that x is higher than 95 or P(x > 95). For x = 95, z = (frac{95 – 83}{9.4}) = 1.27, P(x > 95) = P(z > 1.27) = [total area] – [area to the left of z = 1] = 1 – 0.620 = 0.38. The probability that a car selected at a random has a speed greater than 100 km/hr is equal to 0.38.

6. Let us say that X is a normally distributed variable with mean(μ) of 43 and standard deviation (σ) of 6.4. Determine the probability of X<32.
a) 0.341
b) 0.962
c) 6.231
d) 0.44

Answer: a
Clarification: The area is defined as the area under the standard normal curve.Now, for x = 32, z becomes (frac{32 – 43}{6.4}) = -1.71. Hence, the required probability is P(x < 32) = P(z < -1.71) = 0.341.

7. The time taken to assemble a machine in a certain plant is a random variable having a normal distribution of 32 hours and a standard deviation of 3.6 hours. What is the probability that a machine can be assembled at this plant in less than 25.4 hours?
a) 0.61
b) 0.674
c) 0.298
d) 1.823

Answer: c
Clarification: We have to find P(x < 25.4). Now, for x = 25.4, z becomes (frac{25.4 – 32}{3.6}) = -1.83. Hence, P(z < -1.83) = 0.298.

8. The scores on an admission test are normally distributed with a mean of 640 and a standard deviation of 105.7. A student wants to be admitted to this university. He takes the test and scores 755. What is the probability of him to be admitted to this university?
a) 65.9%
b) 84.6%
c) 40.9%
d) 54%.

Answer: b
Clarification: Let k be the random variable that represents the scores. k is normally distributed with a mean of 640 and a standard deviation of 124.7. The total area under the normal curve represents the total number of students who take the test. If we multiply the values of the areas under the curve by 124.7, we obtain percentages. Now, for k = 755, z = (frac{755 – 640}{105.7}) = 1.087. The proportion of the students who scored below 755 is given by, P = [area to the left of z = 1.087] = 0.846. Hence, the required probability is 84.6 %.

9. The annual salaries of workers in a large manufacturing factory are normally distributed with a mean of Rs. 48,000 and a standard deviation of Rs. 1500. Find the probability of workers who earn between Rs. 35,000 and Rs. 52,000.
a) 64%
b) 76.2%
c) 42.1%
d) 20%

Answer: c
Clarification: For x = 45000, z = -2 and for x = 52000, z = 0.375. Now, area between z = -2 and z = 0.375 is equal to 0.421 or 42.1% earn between Rs. 45,000 and Rs. 52,000.

10. Discrete probability distribution depends on the properties of ___________
a) data
b) machine
c) discrete variables
d) probability function

Answer: a
Clarification: We know that discrete probability function largely depends on the properties and types of data such as Binomial distribution can lead to model binary data such as flipping of coins.