Page 101 - Discrete Mathematics and Its Applications

80 1 / The Foundations: Logic and Proofs

20. Determine whether these are valid arguments. 29. Use rules of inference to show that if ∀x(P (x) ∨ Q(x)),
2
a) If x is a positive real number, then x is a positive real ∀x(¬Q(x) ∨ S(x)), ∀x(R(x) →¬S(x)), and ∃x¬P(x)
2
number. Therefore, if a is positive, where a is a real are true, then ∃x¬R(x) is true.
number, then a is a positive real number. 30. Use resolution to show the hypotheses “Allen is a bad
2
b) If x = 0, where x is a real number, then x = 0. Let boy or Hillary is a good girl” and “Allen is a good boy or
2
a be a real number with a = 0; then a = 0.
David is happy” imply the conclusion “Hillary is a good
21. Which rules of inference are used to establish the girl or David is happy.”
conclusion of Lewis Carroll’s argument described in 31. Use resolution to show that the hypotheses “It is not rain-
Example 26 of Section 1.4? ing or Yvette has her umbrella,” “Yvette does not have
22. Which rules of inference are used to establish the her umbrella or she does not get wet,” and “It is raining
conclusion of Lewis Carroll’s argument described in or Yvette does not get wet” imply that “Yvette does not
Example 27 of Section 1.4? get wet.”
23. Identify the error or errors in this argument that sup-
posedly shows that if ∃xP(x) ∧∃xQ(x) is true then 32. Show that the equivalence p ∧¬p ≡ F can be derived
∃x(P(x) ∧ Q(x)) is true. using resolution together with the fact that a condi-
tional statement with a false hypothesis is true. [Hint: Let
1. ∃xP(x) ∨∃xQ(x) Premise q = r = F in resolution.]
2. ∃xP(x) Simplification from (1)
3. P(c) Existential instantiation from (2) 33. Use resolution to show that the compound propo-
4. ∃xQ(x) Simplification from (1) sition (p ∨ q) ∧ (¬p ∨ q) ∧ (p ∨¬q) ∧ (¬p ∨¬q) is
5. Q(c) Existential instantiation from (4) not satisfiable.
6. P(c) ∧ Q(c) Conjunction from (3) and (5) ∗ 34. The Logic Problem, taken from WFF’N PROOF, The
7. ∃x(P(x) ∧ Q(x)) Existential generalization Game of Logic, has these two assumptions:
24. Identify the error or errors in this argument that sup- 1. “Logic is difficult or not many students like logic.”
posedly shows that if ∀x(P (x) ∨ Q(x)) is true then 2. “If mathematics is easy, then logic is not difficult.”
∀xP(x) ∨∀xQ(x) is true. By translating these assumptions into statements involv-
1. ∀x(P(x) ∨ Q(x)) Premise ing propositional variables and logical connectives, deter-
2. P(c) ∨ Q(c) Universal instantiation from (1) mine whether each of the following are valid conclusions
3. P(c) Simplification from (2) of these assumptions:
4. ∀xP(x) Universal generalization from (3) a) That mathematics is not easy, if many students like
5. Q(c) Simplification from (2) logic.
6. ∀xQ(x) Universal generalization from (5) b) That not many students like logic, if mathematics is
7. ∀x(P(x) ∨∀xQ(x)) Conjunction from (4) and (6) not easy.
25. Justify the rule of universal modus tollens by showing
c) That mathematics is not easy or logic is difficult.
that the premises ∀x(P(x) → Q(x)) and ¬Q(a) for a
d) That logic is not difficult or mathematics is not easy.
particular element a in the domain, imply ¬P(a).
e) That if not many students like logic, then either math-
26. Justifytheruleofuniversaltransitivity,whichstatesthat
ematics is not easy or logic is not difficult.
if ∀x(P(x) → Q(x)) and ∀x(Q(x) → R(x)) are true,
then ∀x(P(x) → R(x)) is true, where the domains of all ∗ 35. Determine whether this argument, taken from Kalish and
quantifiers are the same. Montague [KaMo64], is valid.
27. Use rules of inference to show that if ∀x(P(x) → If Superman were able and willing to prevent evil,
(Q(x) ∧ S(x))) and ∀x(P (x) ∧ R(x)) are true, then he would do so. If Superman were unable to prevent
∀x(R(x) ∧ S(x)) is true. evil, he would be impotent; if he were unwilling
28. Use rules of inference to show that if ∀x(P(x) ∨ to prevent evil, he would be malevolent. Superman
Q(x)) and ∀x((¬P(x) ∧ Q(x)) → R(x)) are true, then does not prevent evil. If Superman exists, he is nei-
∀x(¬R(x) → P(x)) is also true, where the domains of ther impotent nor malevolent. Therefore, Superman
all quantifiers are the same. does not exist.

1.7 Introduction to Proofs

Introduction

In this section we introduce the notion of a proof and describe methods for constructing proofs.
A proof is a valid argument that establishes the truth of a mathematical statement. A proof can
use the hypotheses of the theorem, if any, axioms assumed to be true, and previously proven