Category: Discrete Mathematics Objective Questions

Discrete Mathematics Multiple Choice Questions on “Boolean Algebra – Karnaugh Maps”.

1. K-map is used for _______
a) logic minimization
b) expression maximization
c) summing of parity bits
d) logic gate creation

Answer: a
Clarification: K-map(Maurice Karnaugh of Bell labs in 1953) is defined as a diagrammatic method for logic minimization and it is a pictorial view of truth table which shows the relationship between inputs and output. It is more efficient than Boolean algebra. K-map is a diagram made up of squares in which each square represents a minterm or maxterm of the logic function.

2. To display time in railway stations which digital circuit is used?
a) seven segment decoder
b) eight segment encoder
c) 8:3 multiplexer
d) 9 bit segment driver

Answer: a
Clarification: A seven segment decoder is a digital circuit which is used to construct a common type of digital display device i.e., a set of LED (or LCD) segments that display numbers from 0 through 9 at the command of a four-bit code. Moreover, the behavior of the display driver IC is represented by a truth table with seven outputs.

3. Simplify the expression using K-maps: F(A,B,C,D)=Σ (1,3,5,6,7,11,13,14).
a) AB+BC’D+A’B’C
b) BCD’+A’C’D+BD’
c) A’D+BCD+A’BC+AB’C’
d) AC’D’+BC+A’BD+C’D’

Answer: c
Clarification: By solving the given expression we have minterms such as A’D+BCD+A’BC+AB’C’. So, we can get the required expression A’D+BCD+A’BC+AB’C’.

4. When designing a circuit to emulate a truth table, both Product-of-Sums (POS) expressions and Sum-of-Products (SOP) expressions can be derived from?
a) k-map
b) NAND gate
c) NOR gate
d) X-NOR gate

Answer: a
Clarification: A Karnaugh map can be used to build the appropriate POS expression for designing a circuit to form the truth table. Karnaugh maps are not limited to SOP expressions only for minimizing boolean functions.

5. Simplify the expression using K-maps: F(A,B,C) = Σ (1,3,5,6,7).
a) AC’+B’
b) AB+C
c) AB’+B’C’
d) A’BC+B’C+AC

Answer: b
Clarification: By solving the given expression, the minterms are: C and AB. Hence, we can get the required expression C+AB.

6. Simplify the expression using K-maps: F(A,B,C) = π(0,2,4,5,7).
a) (x+y)(y+z)(x+z)(x’+z’)
b) (x+z’)(y+z)(x+y)
c) (x+y’+z)(x+z’)
d) (y’+z’)(x’+y)(z+y’)

Answer: a
Clarification: By solving the given expression, the maxterms are: (x+y), (x’+y), (x+z) and (x’+z’). Hence, we can get required expression (x+y)(x’+y)(x+z)(x’+z’).

7. Addition of two or more bits produces how many bits to construct a logic gate?
a) 108
b) 2
c) 32
d) 64

Answer: b
Clarification: Addition of bits requires carry-in and carry-out bits. Addition of two terms (bits) a and b, and a carry-in bit Cin is required to compute a sum bit S and a carry-out bit Cout. Hence, two bits are produced in general.

8. Use Karnaugh map to find the simplified expression of the function: F = x’yz + xy + xy’z’.
a) xz’+y’z’
b) xy’z+xy
c) y’z+x’y+z
d) yz+xy+xy’z

Answer: d
Clarification: F = x’yz + xyz + xy z’ + xy’z’ is the canonical form for the function. Now, using k-map the minimal form must be: yz+xy+xy’z.

9. Who has invented K-map?
a) Maurice Karnaugh
b) Edward Veitch
c) George Boole
d) Adam Smith

Answer: a
Clarification: The Karnaugh map (KM or K-map) is invented by Maurice Karnaugh in 1953 that is a method of simplifying Boolean expressions.

10. In Gray coding, the adjacent code values differ by _______
a) single bit
b) 3 bits
c) 10 bits
d) 0 bit

Answer: a
Clarification: In Gray coding, the adjacent code values differ only by a single bit. If the given code-word is 01, then the previous and the next code-words are to be 11 or 00 but cannot be 10 in any case. Each cell within a K-map has a definite place-value which is obtained by using this encoding technique. The rows and the columns of the table use Gray code-labeling which in turn represents the values of the corresponding input variables and each K-map cell can be addressed using a unique Gray Code-Word.

Discrete Mathematics Multiple Choice Questions on “Logics – Nested Quantifiers”.

1. Let Q(x, y) denote “M + A = 0.” What is the truth value of the quantifications ∃A∀M Q(M, A).
a) True
b) False

Answer: b
Clarification: For each A there exist only one M, because there is no real number A such that M + A = 0 for all real numbers M.

2. Translate ∀x∃y(x < y) in English, considering domain as a real number for both the variable.
a) For all real number x there exists a real number y such that x is less than y
b) For every real number y there exists a real number x such that x is less than y
c) For some real number x there exists a real number y such that x is less than y
d) For each and every real number x and y such that x is less than y

Answer: a
Clarification: Statement is x is less than y. Quantifier used are for each x, there exists a y.

3. “The product of two negative real numbers is not negative.” Is given by?
a) ∃x ∀y ((x < 0) ∧ (y < 0) → (xy > 0))
b) ∃x ∃y ((x < 0) ∧ (y < 0) ∧ (xy > 0))
c) ∀x ∃y ((x < 0) ∧ (y < 0) ∧ (xy > 0))
d) ∀x ∀y ((x < 0) ∧ (y < 0) → (xy > 0))

Answer: d
Clarification: For every negative real number x and y, the product of these integer is positive.

4. Let Q(x, y) be the statement “x + y = x − y.” If the domain for both variables consists of all integers, what is the truth value of ∃xQ(x, 4).
a) True
b) False

Answer: b
Clarification: There exist no integer for which x+4=x-4.

5. Let L(x, y) be the statement “x loves y,” where the domain for both x and y consists of all people in the world. Use quantifiers to express, “Joy is loved by everyone.”
a) ∀x L(x, Joy)
b) ∀y L(Joy,y)
c) ∃y∀x L(x, y)
d) ∃x ¬L(Joy, x)

Answer: a
Clarification: Joy is loved by all the people in the world.

6. Let T (x, y) mean that student x likes dish y, where the domain for x consists of all students at your school and the domain for y consists of all dishes. Express ¬T (Amit, South Indian) by a simple English sentence.
a) All students does not like South Indian dishes.
b) Amit does not like South Indian people.
c) Amit does not like South Indian dishes.
d) Amit does not like some dishes.

Answer: d
Clarification: Negation of the statement Amit like South Indian dishes.

7. Express, “The difference of a real number and itself is zero” using required operators.
a) ∀x(x − x! = 0)
b) ∀x(x − x = 0)
c) ∀x∀y(x − y = 0)
d) ∃x(x − x = 0)

Answer: b
Clarification: For every real number x, difference with itself is always zero.

8. Use quantifiers and predicates with more than one variable to express, “There is a pupil in this lecture who has taken at least one course in Discrete Maths.”
a) ∃x∃yP (x, y), where P (x, y) is “x has taken y,” the domain for x consists of all pupil in this class, and the domain for y consists of all Discrete Maths lectures
b) ∃x∃yP (x, y), where P (x, y) is “x has taken y,” the domain for x consists of all Discrete Maths lectures, and the domain for y consists of all pupil in this class
c) ∀x∀yP(x, y), where P (x, y) is “x has taken y,” the domain for x consists of all pupil in this class, and the domain for y consists of all Discrete Maths lectures
d) ∃x∀yP(x, y), where P (x, y) is “x has taken y,” the domain for x consists of all pupil in this class, and the domain for y consists of all Discrete Maths lectures

Answer: a
Clarification: For some x pupil, there exists a course in Discrete Maths such that x has taken y.

9. Determine the truth value of ∃n∃m(n + m = 5 ∧ n − m = 2) if the domain for all variables consists of all integers.
a) True
b) False

Answer: b
Clarification: The equation does not satisfy any value of m and n in the domain consist of integers.

10. Find a counterexample of ∀x∀y(xy > y), where the domain for all variables consists of all integers.
a) x = -1, y = 17
b) x = -2 y = 8
c) Both x = -1, y = 17 and x = -2 y = 8
d) Does not have any counter example

Answer: c
Clarification: Putting x=-1, y=17; -17>17 which is wrong. Putting x=-2, y=8; -16>8 which is wrong.

Discrete Mathematics Multiple Choice Questions on “Arithmetic Sequences”.

1. Let the sequence be 1, 3, 5, 7, 9……… then this sequence is ____________
a) An arithmetic sequence
b) A geometric progression
c) A harmonic sequence
d) None of the mentioned

Answer: a
Clarification: The difference in any term with the previous term is same.

2. In the given AP series find the number of terms?

5, 8, 11, 14, 17, 20.........50.

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

Answer: d
Clarification: n^th term = first_term + (number_of_terms – 1)common_differnce., 50 = 5 + (n-1)3, n=16.

3. In the given AP series the term at position 11 would be?

5, 8, 11, 14, 17, 20.........50.

a) 35
b) 45
c) 25
d) None of the mentioned

Answer: a
Clarification: n^th term = a + (n – 1)d, n^th term = 5+(11-1)3 = 35.

4. For the given Arithmetic progression find the position of first negative term?

50, 47, 44, 41,............

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

Answer: c
Clarification: Let n^th term=0, the next term would be first negative term.
0 = 50 + (n-1) – 3, n = 17.66.. therfore at n = 18 the first negative term would occur.

5. For the given Arithmetic progression find the first negative term?

50, 47, 44, 41,............

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

Answer: a
Clarification: Let n^th term = 0, the next term would be first negative term.
0 = 50 +(n-1)- 3, n = 17.66.. therfore at n=18 the first negative term would occur. N^th term = 50 + (18-1) – 3 = -1.

6. A series can either be AP only or GP only or HP only but not all at the same time.
a) True
b) False

Answer: b
Clarification: 1, 1, 1, 1, 1…….. is AP, GP and HP series.

7. In the given Arithmetic progression, ’25’ would be a term in it.

5, 8, 11, 14, 17, 20.........50.

a) True
b) False

Answer: b
Clarification: n^th term = a + (n-1)d, 25 = 5 + (n-1)3, n = 23/3, n = 7.666 not an integer. Thus 25 is not a term in this series.

8. Which of the following sequeces in AP will have common difference 3, where n is an Integer?
a) a_n = 2n² + 3n
b) a_n = 2n² + 3
c) a_n = 3n² + 3n
d) a_n = 5 + 3n

Answer: d
Clarification: a_n = 5 + 3n it is a linear expression with coefficient of as 3. So it is AP with common difference 3.

9. If a, b, c are in AP then relation between a, b, c can be _________
a) 2b = 2a + 3c
b) 2a = b + c
c) 2b = a + c
d) 2c = a + c

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

10. Let the sum of the 3 consecutive terms in AP be 180 then midlle of those 3 terms would be ________
a) 60
b) 80
c) 90
d) 179

Answer: a
Clarification: Let a₁, b₁, c₁ be three terms, then a₁ + b₁ + c₁ = 180, a₁ + c₁ = 2b₁(A M property), 3b₁ = 180, b₁=60.

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

1. The binary notation of 231 is ___________
a) (11010111)₂
b) (10111011)₂
c) (11100011)₂
d) (11100111)₂

Answer: d
Clarification: By binary Expansion of 11100111 is 1*2⁰ + 1*2¹ + 1*2² + 1*2⁵ + 1*2⁶ + 1*2⁷ is equal to 231.

2. The decimal notation of 101010101 is ___________
a) 340₁₀
b) 341₁₀
c) 342₁₀
d) 315₁₀

Answer: b
Clarification: (101010101)₂ = 1*2⁰ + 1*2² + 1*2⁴ + 1*2⁶ + 1*2⁸ = 341.

3. The binary notation of ABBA is ___________
a) 1010 1011 1011 1010
b) 1010 1001 1011 1011
c) 1011 1000 1010 1001
d) 1001 1000 1000 1111

Answer: a
Clarification: By the base conversion algorithm.

4. The hexadecimal notation of (1011 0111 1011)₂ is ___________
a) (B2B)₁₆
b) (B5B)₁₆
c) (B7B)₁₆
d) (A7B)₁₆

Answer: c
Clarification: (1011)₂ = 11 and (0111)₂ = 7, 11 in hexadecimal notation represents B. So it is (B7B)₁₆.

5. The octal expansion of (10 1011 1011)₂ is ___________
a) (1245)₈
b) (1276)₈
c) (1275)₈
d) (1273)₈

Answer: d
Clarification: (10 1011 1011)₂ = (699)₁₀. Using base conversion algorithm, (699)₁₀ = (1273)₈.

6. The hexadecimal expansion of (177130)₁₀ is ___________
a) (2B3EB)₁₆
b) (2B3EA)₁₆
c) (2C3AA)₁₆
d) (2B2AA)₁₆

Answer: b
Clarification: Successively divide 177130 by 16 to obtain remainder they are (2B3EA)₁₆.

7. The greatest common divisor of 414 and 662 is?
a) 4
b) 5
c) 2
d) 6

Answer: c
Clarification: By using Euclid Lemma.

8. The greatest common divisor of 12 and 18 is?
a) 2
b) 3
c) 4
d) 6

Answer: d
Clarification: By using Euclid Lemma, 6 divides 12 and 18.

9. The decimal expansion of (2AE0B)₁₆ is?
a) (175627)₁₀
b) (175624)₁₀
c) (178566)₁₀
d) (175622)₁₀

Answer: a
Clarification: (2AE0B)₁₆ = 2*16₄ + 10*16₃ + 14*16₂ + 0*16+11 = (175627)₁₀.

10. The greatest common divisor of 7 and 5 is?
a) 1
b) 2
c) 5
d) 7

Answer: a
Clarification: Two numbers 7 and 5 are relatively prime, so gcd(7, 5) = 1.

Discrete Mathematics Multiple Choice Questions on “Strong Induction and Well-Ordering”.

1. A polygon with 7 sides can be triangulated into ________
a) 7
b) 14
c) 5
d) 10

Answer: c
Clarification: A simple polygon with n sides can be triangulated into n-2 triangles, where n > 2.

2. Every simple polynomial has an interior diagonal.
a) True
b) False

Answer: a
Clarification: By using Strong Induction.

3. A polygon with 12 sides can be triangulated into _______
a) 7
b) 10
c) 5
d) 12

Answer: b
Clarification: A simple polygon with n sides can be triangulated into n-2 triangles, where n > 2.

4. Let P(n) be the statement that postage of n cents can be formed using just 3-cents stamps and 5-cents stamps. Is the statements P(8) and P(10) are Correct?
a) True
b) False

Answer: a
Clarification: We can form 8 cent of postage with one 3-cent stamp and one 5-cent stamp. P(10) is true because we can form it using two 5-cent stamps.

5. Which amount of postage can be formed using just 4-cent and 11-cent stamps?
a) 2
b) 5
c) 30
d) 10

Answer: d
Clarification: We can form 30 cent of postage with two 4-cent stamp and two 11-cent stamp.

6. 22-cent of postage can be produced with two 4-cent stamp and one 11-cent stamp.
a) True
b) False

Answer: b
Clarification: By using two 4-cent stamp and one 11-cent stamp, 27-cent postage is produced.

7. Which amount of postage can be formed using just 3-cent stamp and 10-cent stamps?
a) 27
b) 20
c) 11
d) 5

Answer:a
Clarification: We can form 27 cent of postage with nine 3-cent stamp and 20-cent postage can be formed by using two 10-cent stamps.

8. Suppose that P(n) is a propositional function. Determine for which positive integers n the statement P(n) must be true if: P(1) is true; for all positive integers n, if P(n) is true then P(n+2) is true.
a) P(3)
b) P(2)
c) P(4)
d) P(6)

Answer: a
Clarification: By induction we can prove that P(3) is true but we can’t conclude about P(2), p(6) and P(4).

9. Suppose that P(n) is a propositional function. Determine for which positive integers n the statement P(n) must be true if: P(1) and P(2) is true; for all positive integers n, if P(n) and P(n+1) is true then P(n+2) is true.
a) P(1)
b) P(2)
c) P(4)
d) P(n)

Answer: d
Clarification: By induction, we can prove that P(n) is true.

10. A polygon with 25 sides can be triangulated into _______
a) 23
b) 20
c) 22
d) 21

Answer: a
Clarification: A simple polygon with n sides can be triangulated into n-2 triangles, where n > 2.

Discrete Mathematics Multiple Choice Questions on “Geometric Probability”.

1. Suppose, R is a random real number between 5 and 9. What is the probability R is closer to 5 than it is to 6?
a) 12.5%
b) 18%
c) 73%
d) 39.8%

Answer: a
Clarification: Since there are infinitely many possible outcomes for the value of X we will take the equally likely outcomes as random points along the number line from 5 to 9. R will be closer to 5 than it is to 6 if R<5.5. We can easily see it by drawing a probability line. Here, P(R is closer to 5 than to 6) = (length of segment where 5<R<5.5)/(length of segment where (5<R<9) = 0.5/4 = 0.125 = 12.5%.

2. A ball is thrown at a circular bin such that it will land randomly over the area of the bin. Find the probability that it lands closer to the center than to the edge?
a) 51%
b) 25%
c) 72%
d) 34%

Answer: b
Clarification: The set of outcomes are all of the points on the bin, which make up an area of where is the radius of the circle. The points which are closer to the center than to the edge are those that lie within the circle of radius around the center. Hence, the area of the success outcomes is π(r/2)² = πr²/4. Thus, P(closer to center than edge)=(area of the desired outcome)/(area of the total outcome) = πr²/4 /πr² = 1/4 = 0.25 = 25%.

3. A programmer has a 95% chance of finding a bug every time she compiles his code, and it takes her three hours to rewrite the code every time she discovers a bug. Find the probability that she will finish her program by the end of her workday. (Assume that a workday is 9 hours)
a) 76%
b) 44%
c) 37%
d) 28%

Answer: d
Clarification: In this instance, a success is a bug-free compilation, and a failure is the discovery of a bug. The programmer needs to have 0, 1 or 2 failures, so her probability of finishing the program is: P(X=0) + P(X=1) + P(X=2) = (0.95)⁰(0.1) + (0.95)¹(0.1) + (0.95)²(0.1) = 0.28% = 28%.

4. A football player has a 45% chance of getting a hit on any given pitch. What is the probability that the player earns a hit ignoring the balls before he strikes out (that requires four strikes)?
a) 0.36
b) 0.95
c) 0.67
d) 0.59

Answer: b
Clarification: IA success is a hit and a failure is a strike. The player requires either 0, 1, 2 or 3 failures in order to get a hit before striking out, so the probability of a hit is:
P(X=0) + P(X=1) + P(X=2) + P(X=3) = (0.45)⁰(0.55) + (0.45)¹(0.55) + (0.45)²(0.55) + (0.45)³(0.55) = 0.95.

5. What is variance of a geometric distribution having parameter p=0.72?
a) 54%
b) 76%
c) 13%
d) 69%

Answer: a
Clarification: The variance of a geometric distribution with parameter p is (frac{1-p}{p^2} = frac{(1-0.72)}{0.722}) = 0.54 or 54%. However, the variance of the geometric distribution and the variance of the shifted geometric distribution are identical.

6. The probability that it rains tomorrow is 0.72. Find the probability that it does not rain tomorrow?
a) 65%
b) 43%
c) 28%
d) 32%

Answer: c
Clarification: we know that the sum of the probability that it rains and the probability that it does not rain must be 1. To determine the probability that it does not rain, calculate 1 – 0.72 = 0.28.

7. Suppose a rectangle edges equals i = 4.7 and j = 8.3. Now, a straight line drawn through randomly selected two points K and L in adjacent rectangle edges. Find the condition for the probability such that the drawn triangle area is smaller than c = 9.38.
a) K-L≤18.76
b) K+L≤18.76
c) KL≤18.76
d) K/L≤18.76

Answer: c
Clarification: The random sides of the triangle are K and L. These are the uniform random variables with uniform distributions on [0,8.3] and [0,4.7] respectively. They are independent and their joint distribution is uniform on the rectangle R = [0,8.3]∗[0,4.7]. The condition is KL/2≤9.38 ⇒ KL≤18.76. The probability that one needs is the ratio between the area under the hyperbola inside R and the area of R.

8. Find the expectation for how many bacteria there are per field if there are 2350 bacteria are randomly distributed over 340 fields (all having the same size) next to each other.
a) 4.98
b) 3.875
c) 6.91
d) 7.37

Answer: c
Clarification: The probability to land in a field for a bacterium is p = 1/340 and since we have n = 2350 bacteria. So, the expectation is m = np = 2350/340 = 6.91.

9. What is the possibility such that the inequality x² + b > ax is true, when a=32.4 and b=76.5 and x∈[0,30].
a) 1.91
b) 4.3
c) 2.94
d) 6.1

Answer: a
Clarification: x2+76.5>32.4x is equivalent to x²−32.4x+76.5 > 0. By completing the square, x² − 32.4x + 266.44 – 266.44 + 76.5 = (x−16.2)² − 189.94>0, which is the same as (x−16.2)² > 189.94, which implies that either x−16.2 > 13.78 ⇒ x > 29.98, or x−16.2 < −2.42 ⇒ x < 13.78. Assume that it is a uniform distribution. So, the probability that x > 29.98 is 30 − 29.98 = 0.02 and the probability that x < 189.94 is 1.89. The desired probability is 0.02 + 1.89 = 1.91.

10. In a bucket there are 5 purple, 15 grey and 25 green balls. If the ball is picked up randomly, find the probability that it is neither grey nor purple?
a) (frac{5}{9})
b) (frac{12}{13})
c) (frac{51}{43})
d) (frac{2}{7})

Answer: a
Clarification: If the ball is neither grey nor purple then it must be blue. There are 45 balls in total of which 25 are green and so the probability of picking a purple ball is (frac{25}{45} = frac{5}{9}).