Discrete Math : Logic (40 MC Problems)

1. Identify the rule of inference used in the following:
If it rains today, the flood gates will open. The flood gates did not open
today. Therefore, it did not rain.
a. modus tollens
b. hypothetical syllogism
c. modus ponens
d. disjunctive syllogism
2. Identify the rule of inference used in the following:
If I work all night on this homework, then I can answer all the
exercises. If I answer all the exercises, I will understand the material.
Therefore, if I work all night on this homework, then I will understand
the material.
a. modus tollens
b. hypothetical syllogism
c. modus ponens
d. disjunctive syllogism
3. The following argument is valid:
q
p
p q
∴¬
¬
→
a. True
b. False
4. Analyze the following argument:
If n is a real number such that n > 1, then n2 > 1. Suppose that n2 > 1,
then n > 1.
a. It is valid.
b. It is not valid because it begs the question.
c. It is not valid because it affirms the hypothesis.
d. It is not valid because it affirms the conclusion.
5. Analyze the following argument:
If n is a real number such that n > 2, then n2 > 4. Suppose that n ≤ 2,
then n2 ≤ 4.
a. It is valid.
b. It is not valid because it begs the question.
c. It is not valid because it denies the hypothesis.
d. It is not valid because it affirms the conclusion.
6. The following argument is valid:
Lynn works part time or full time
If Lynn does not play on the team, then she does not work part time
If Lynn plays on the team, she is busy
Lynn does not work full time
Therefore Lynn is busy
a. True
b. False
7. The statement "I visited New Orleans last month" logically implies
"Someone visited New Orleans last month."
a. True
b. False
8. You wish to prove theorem of the form "if p then q". To use the method
of direct proof, what do you assume and what do you prove?
a. assume p, prove q .
b. assume ¬q, prove p .
c. assume ¬q, prove ¬p .
d. assume p ∧ ¬q, prove otherwise .
9. You wish to prove theorem of the form "if p then q". To use the method
of indirect proof, what do you assume and what do you prove?
a. assume p, prove q .
b. assume ¬q, prove p .
c. assume ¬q, prove ¬p .
d. assume p ∧ ¬q, prove otherwise.
10. You wish to prove theorem of the form "if p then q". To use the method
of contradiction, what do you assume and what do you prove?
a. assume p, prove q .
b. assume ¬q, prove p .
c. assume ¬q, prove ¬p .
d. assume p ∧ ¬q, prove otherwise .
11. The method of mathematical induction is used to prove propositions of
the form: ∃ n P(n) .
a. True
b. False
12. The step that proves P(1) is called the basis step.
a. True
b. False
13. Why is mathematical induction valid?
a. It formalizes symbolic logic.
b. It follows from the well-ordering property.
c. It uses concrete examples as a means of proof by cases.
d. It is widely accepted as valid.
14. 2 | (n2 + 3n) for all n ≥ 1. (Hint: Use mathematical induction.)
a. True
b. False
15. 2n + 3 ≤ 2n for all n ≥ 4. (Hint: Use mathematical induction.)
a. True
b. False
16. A recursive definition specifies the value of the function at zero and
then gives a rule for finding it value at a given integer from its values
at smaller integers.
a. True
b. False
17. What is a reasonable name for the following procedure?
procedure mystery (x, y : integers)
if x = 0 then y := 1
else y := x*mystery(x-1)
a. Fibonacci
b. Factorial
c. Max
d. Product
18. Recursive functions are well-defined as a consequence of mathematical
induction.
a. True
b. False
19. What is a reasonable name for the following procedure?
procedure mystery (x, y : non-negative integers)
if x = 0 then answer := y
else answer := mystery(y mod x, x)
return(answer)
a. Binary Search
b. Power
c. Search
d. GCD
20. One of the common uses of recursive definitions is to define wellformed
formulae in various systems.
a. True
b. False
21. Σ* is:
a. the power set of Σ.
b. the set of strings over the alphabet Σ.
c. limited to the letters of the English alphabet.
d. limited to the non-negative integers.
22. Assume you have constructed a proof that P(k) is true for
3 ≤ k ≤ n. The proof of P(3) is called the:
a. basis step.
b. inductive step.
c. recursive step.
d. None of the above.
23. Continuing the above example, the ______________ step shows that
P(3) �� P(4).
a. basis step.
b. inductive step.
c. recursive step.
d. None of the above.
24. n2 > 2n whenever n is an integer greater than 4.
a. True
b. False
25. A procedure that starts with the value of the function at 1 and then
successively applies the definition to find the value of the function at
successively larger integers is said to be:
a. recursive.
b. iterative.
c. factorial.
d. None of the above.
26. The proof of the correctness of a program is called:
a. verification.
b. induction.
c. inference.
d. validation.
27. If you split a program into a series of subprograms and show that each
subprogram is correct, then you have established the program is
correct by means of:
a. verification.
b. induction.
c. inference.
d. validation.
28. A program is said to be ______________ if it produces the correct output
for every possible input.
a. correct
b. complete
c. partially correct
d. None of the above.
29. If the correct answer is obtained when a program terminates, it is said
to be:
a. correct.
b. complete.
c. partially correct.
d. None of the above.
30. To show that a conditional statement S in a program is correct, it is
necessary to show that:
a. when the condition is true, S executes.
b. when the condition is false, S does not execute.
c. both A and B.
d. None of the above.
31. Analyze the following rule of inference:
This inference rule is best described as:
a. if...then
b. while
c. compositional
d. loop invariant
32. The notation p{S}q is called a Hoare triple.
a. True
b. False
33. The notation p{S}q indicates the program or subprogram S is partially
correct with respect to the initial assertion p and the final assertion q.
a. True
b. False
p condition S q
p condition S q
( ){ }
( ){ }
2
1
∧ ¬
∧
34. Analyze the following rule of inference:
This inference rule is best described as:
a. if...then
b. while
c. compositional
d. loop invariant
35. Given the initial assertion is true and the following rule of inference,
what is the truth value of final assertion y = 2?
if x < 0 then
y := -2|x|/x
else if x > 0 then
y := 2|x|/x
else if x=0 then
y := 2
a. True
b. False
36. A sequence is a discrete structure used to define a set.
a. True
b. False
37. What is the lower limit of the index of summation for &#931;=
100
1
1
j j
?
a. 0
b. 1
c. 100
d. None of the above.
38. What is the value of &#931; =
5
2
2
i i ?
a. 32
b. 54
c. 55
d. 65
q S r
p S q
{ }
{ }
2
1
39. A sequence of the form a, ar, ar2, ar3, ar4,...,ark is called a harmonic
progression.
a. True
b. False
40. To compute a double summation,
a. expand the outer summation, then compute the inner summation.
b. expand the inner summation, then compute the outer summation.
c. expand the summation indices, then compute the function.
d. None of the above.