DM mcq - Discrete mathematics Multiple choice question and answers PDF

Preview

Summary

Discrete mathematics Multiple choice question and answers...

Description

MA8351 DISCRETE MATHEMATICS

MA8351 DISCRETE MATHEMATICS CSE - SEMESTER 5 UNIT I LOGIC AND PROOFS TOPIC 1.1 PROPOSITIONAL LOGIC 1. Which of the following statement is a proposition? 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 Answer: d 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 Answer: b 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

CSE - Regulations 2017

Answer: a 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? ‘If x equals to one then x=x+2 else x=0’. a) 1 b) 3 c) 0 d) 2 Answer: c 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 Answer: a 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 Answer: c 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 Answer: b Explanation: The first part of the statement is

Downloaded from: https://cse-r17.blogspot.com

1

MA8351 DISCRETE MATHEMATICS

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 Answer: a 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 Answer: b 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 Answer: d Explanation: The third part of the statement is negated, hence negation operator is used, for (‘or’ –V) is used and for(’but’- ∧).

TOPIC 1.2 PROPOSITIONAL EQUIVALENCES

CSE - Regulations 2017

1. The compound propositions p and q are called logically equivalent if ________ is a tautology. a) p ↔ q b) p → q c) ¬ (p ∨ q) d) ¬p ∨ ¬q Answer: a Explanation: Definition of logical equivalence. 2. p → q is logically equivalent to ________ a) ¬p ∨ ¬q b) p ∨ ¬q c) ¬p ∨ q d) ¬p ∧ q Answer: c Explanation: (p → q) ↔ (¬p ∨ q) is tautology. 3. p ∨ q is logically equivalent to ________ a) ¬q → ¬p b) q → p c) ¬p → ¬q d) ¬p → q Answer: d Explanation: (p ∨ q) ↔ (¬p → q) is tautology. 4. ¬ (p ↔ q) is logically equivalent to ________ a) q↔p b) p↔¬q c) ¬p↔¬q d) ¬q↔¬p Answer: b Explanation: ¬(p↔q)↔(p↔¬q) is tautology. 5. p ∧ q is logically equivalent to ________ a) ¬ (p → ¬q) b) (p → ¬q) c) (¬p → ¬q) d) (¬p → q)

Downloaded from: https://cse-r17.blogspot.com

2

MA8351 DISCRETE MATHEMATICS

Answer: a Explanation: (p ∧ q) ↔ (¬(p → ¬q)) is tautology. 6. Which of the following statement is correct? a) p ∨ q ≡ q ∨ p b) ¬(p ∧ q) ≡ ¬p ∨ ¬q c) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) d) All of mentioned

CSE - Regulations 2017

10. ¬ (p ↔ q) is logically equivalent to ________ a) p ↔ ¬q b) ¬p ↔ q c) ¬p ↔ ¬q d) ¬q ↔ ¬p Answer: a Explanation: (¬ (p ↔ q)) ↔ (p ↔ ¬q) is tautology.

Answer: d Explanation: Verify using truth table, all are correct.

TOPIC 1.3 PREDICATES AND QUANTIFIERS

7. p ↔ q is logically equivalent to ________ a) (p → q) → (q → p) b) (p → q) ∨ (q → p) c) (p → q) ∧ (q → p) d) (p ∧ q) → (q ∧ p)

1. Let P (x) denote the statement “x >7.” Which of these have truth value true? a) P (0) b) P (4) c) P (6) d) P (9)

Answer: c Explanation: (p ↔ q) ↔ ((p → q) ∧ (q → p)) is tautology.

Answer: d Explanation: Put x=9, 9>7 which is true.

8. (p → q) ∧ (p → r) is logically equivalent to ________ a) p → (q ∧ r) b) p → (q ∨ r) c) p ∧ (q ∨ r) d) p ∨ (q ∧ r) Answer: a Explanation: ((p → q) ∧ (p → r)) ↔ (p → (q ∧ r)) is tautology. 9. (p → r) ∨ (q → r) is logically equivalent to ________ a) (p ∧ q) ∨ r b) (p ∨ q) → r c) (p ∧ q) → r d) (p → q) → r Answer: c Explanation: ((p → r) ∨ (q → r)) ↔ ((p ∧ q) → r) is tautology.

2. Let Q(x) be the statement “x < 5.” What is the truth value of the quantification ∀xQ(x), having domains as real numbers. a) True b) False Answer: b Explanation: Q(x) is not true for every real number x, because, for instance, Q(6) is false. That is, x = 6 is a counterexample for the statement ∀xQ(x). This is false. 3. Determine the truth value of ∀n(n + 1 > n) if the domain consists of all real numbers. a) True b) False Answer: a Explanation: There are no elements in the domain for which the statement is false. 4. Let P(x) denote the statement “x = x + 7.” What is the truth value of the quantification

Downloaded from: https://cse-r17.blogspot.com

3

MA8351 DISCRETE MATHEMATICS

∃xP(x), where the domain consists of all real numbers? a) True b) False Answer: b Explanation: Because P(x) is false for every real number x, the existential quantification of Q(x), which is ∃xP(x), is false. 5. Let R (x) denote the statement “x > 2.” What is the truth value of the quantification ∃xR(x), having domain as real numbers? a) True b) False Answer: a Explanation: Because “x > 2” is sometimes true—for instance, when x = 3–the existential quantification of R(x), which is ∃xR(x), is true. 6. The statement,” Every comedian is funny” where C(x) is “x is a comedian” and F (x) is “x is funny” and the domain consists of all people. a) ∃x(C(x) ∧ F (x)) b) ∀x(C(x) ∧ F (x)) c) ∃x(C(x) → F (x)) d) ∀x(C(x) → F (x)) Answer: d Explanation: For every person x, if comedian then x is funny. 7. The statement, “At least one of your friends is perfect”. Let P (x) be “x is perfect” and let F (x) be “x is your friend” and let the domain be all people. a) ∀x (F (x) → P (x)) b) ∀x (F (x) ∧ P (x)) c) ∃x (F (x) ∧ P (x)) d) ∃x (F (x) → P (x)) Answer: c Explanation: For some x, x is friend and funny.

CSE - Regulations 2017

8. ”Everyone wants to learn cosmology.” This argument may be true for which domains? a) All students in your cosmology class b) All the cosmology learning students in the world c) Both of the mentioned d) None of the mentioned Answer: c Explanation: Domain may be limited to your class or may be whole world both are good as it satisfies universal quantifier. 9. Let domain of m includes all students, P (m) be the statement “m spends more than 2 hours in playing polo”. Express ∀m ¬P (m) quantification in English. a) A student is there who spends more than 2 hours in playing polo b) There is a student who does not spend more than 2 hours in playing polo c) All students spends more than 2 hours in playing polo d) No student spends more than 2 hours in playing polo Answer: d Explanation: There is no student who spends more than 2 hours in playing polo. 10. Determine the truth value of statement ∃n (4n = 3n) if the domain consists of all integers. a) True b) False Answer: a Explanation: For n=0, 4n=3n hence, it is true.

TOPIC 1.4 NESTED QUANTIFIERS 1. Let Q(x, y) denote “M + A = 0.” What is the truth value of the quantifications ∃A∀M Q(M, A).

Downloaded from: https://cse-r17.blogspot.com

4

MA8351 DISCRETE MATHEMATICS

a) True b) False Answer: b Explanation: 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 Explanation: 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 Explanation: 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 Explanation: There exist no integer for which x+4=x-4.

CSE - Regulations 2017

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 Explanation: 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 Explanation: 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 Explanation: 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

Downloaded from: https://cse-r17.blogspot.com

5

MA8351 DISCRETE MATHEMATICS

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 Explanation: 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 Explanation: 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 Explanation: Putting x=-1, y=17; -17>17 which is wrong. Putting x=-2, y=8; -16>8 which is wrong.

TOPIC 1.5 RULES OF INFERENCE

CSE - Regulations 2017

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 Explanation: (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 Explanation: (¬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 Explanation: 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

Downloaded from: https://cse-r17.blogspot.com

6

MA8351 DISCRETE MATHEMATICS

Answer: b Explanation: (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 Explanation: ((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 Explanation: ∀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 Explanation: ((p ∨ q) ∧ ¬p) → q argument is Disjunctive syllogism.

CSE - Regulations 2017

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 Explanation: 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 Explanation: ((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 Explanation: 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.”

Downloaded from: https://cse-r17.blogspot.com

7

MA8351 DISCRETE MATHEMATICS

TOPIC 1.6 INTRODUCTION TO PROOFS, PROOF METHODS AND STRATEGY. 1. Let the statement be “If n is not an odd integer then square of n is not odd.”, then if P(n) is “n is an not an odd integer” and Q(n) is “(square of n) is not odd.” For direct proof we should prove _________ a) ∀nP ((n) → Q(n)) b) ∃ nP ((n) → Q(n)) c) ∀n~(P ((n)) → Q(n)) d) ∀nP ((n) → ~(Q(n))) Answer: a Explanation: Definition of direct proof. 2. Which of the following can only be used in disproving the statements? a) Direct proof b) Contrapositive proofs c) Counter Example d) Mathematical Induction Answer: c Explanation: Counter examples cannot be used to prove results. 3. Let the statement be “If n is not an odd integer then sum of n with some not odd number will not be odd.”, then if P(n) is “n is an not an odd integer” and Q(n) is “sum of n with some not odd number will not be odd.” A proof by contraposition will be ________ a) ∀nP ((n) → Q(n)) b) ∃ nP ((n) → Q(n)) c) ∀n~(P ((n)) → Q(n)) d) ∀n(~Q ((n)) → ~(P(n))) Answer: d Explanation: Definition of proof by contraposition. 4. When to proof P→Q true, we proof P false, that type of proof is known as ___________ a) Direct proof

CSE - Regulations 2017

b) Contrapositive proofs c) Vacuous proof d) Mathematical Induction Answer: c Explanation: Definition of vacuous proof. 5. In proving √5 as irrational, we begin with assumption √5 is rational in which type of proof? a) Direct proof b) Proof by Contradiction c) Vacuous proof d) Mathematical Induction Answer: b Explanation: Definition of proof by contradiction. 6. A proof covering all the possible cases, such type of proofs are known as ___________ a) Direct proof b) Proof by Contradiction c) Vacuous proof d) Exhaustive proof Answer: d Explanation: Definition of exhaustive proof. 7. Which of the arguments is not valid in proving sum of two odd number is not odd. a) 3 + 3 = 6, hence true for all b) 2n +1 + 2m +1 = 2(n+m+1) hence true for all c) All of the mentioned d) None of the mentioned Answer: a Explanation: Some examples are not valid in proving results. 8. A proof broken into distinct cases, where these cases cover all prospects, such proofs are known as ___________ a) Direct proof b) Contrapositive proofs

Downloaded from: https://cse-r17.blogspot.com

8

MA8351 DISCRETE MATHEMATICS

CSE - Regulations 2017

c) Vacuous proof d) Proof by cases

343 > 27 as a base case and it is true for n = 3.

Answer: c Explanation: Definition of proof by cases.

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

9. A proof that p → q is true based on the fact that q is true, such proofs are known as ___________ a) Direct proof b) Contrapositive proofs c) Trivial proof d) Proof by cases Answer: c Explanation: Definition of trivial proof.

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

10. A theorem used to prove other theorems is known as _______________ a) Lemma b) Corollary c) Conjecture d) None of the mentioned

3. For m = 1, 2, …, 4m+2 is a multiple of ________ a) 3 b) 5 c) 6 d) 2

Answer: a Explanation: Definition of lemma.

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