1.

6 Rules of Inference 75

EXAMPLE 9 Show that the premises (p ∧ q) ∨ r and r → s imply the conclusion p ∨ s.

Solution: We can rewrite the premises (p ∧ q) ∨ r as two clauses, p ∨ r and q ∨ r. We can also
replace r → s by the equivalent clause ¬r ∨ s. Using the two clauses p ∨ r and ¬r ∨ s, we can
use resolution to conclude p ∨ s.

▲
Fallacies
Several common fallacies arise in incorrect arguments. These fallacies resemble rules of infer-
ence, but are based on contingencies rather than tautologies. These are discussed here to show
the distinction between correct and incorrect reasoning.
The proposition ((p → q) ∧ q) → p is not a tautology, because it is false when p is false
and q is true. However, there are many incorrect arguments that treat this as a tautology. In
other words, they treat the argument with premises p → q and q and conclusion p as a valid
argument form, which it is not. This type of incorrect reasoning is called the fallacy of affirming
the conclusion.

EXAMPLE 10 Is the following argument valid?

If you do every problem in this book, then you will learn discrete mathematics. You learned
discrete mathematics.
Therefore, you did every problem in this book.

Solution: Let p be the proposition “You did every problem in this book.” Let q be the proposition
“You learned discrete mathematics.” Then this argument is of the form: if p → q and q, then
p. This is an example of an incorrect argument using the fallacy of affirming the conclusion.
Indeed, it is possible for you to learn discrete mathematics in some way other than by doing every
problem in this book. (You may learn discrete mathematics by reading, listening to lectures,

▲
doing some, but not all, the problems in this book, and so on.)

The proposition ((p → q) ∧ ¬p) → ¬q is not a tautology, because it is false when p is

false and q is true. Many incorrect arguments use this incorrectly as a rule of inference. This
type of incorrect reasoning is called the fallacy of denying the hypothesis.

EXAMPLE 11 Let p and q be as in Example 10. If the conditional statement p → q is true, and ¬p is true,
is it correct to conclude that ¬q is true? In other words, is it correct to assume that you did not
learn discrete mathematics if you did not do every problem in the book, assuming that if you do
every problem in this book, then you will learn discrete mathematics?

Solution: It is possible that you learned discrete mathematics even if you did not do every
problem in this book. This incorrect argument is of the form p → q and ¬p imply ¬q, which ▲
is an example of the fallacy of denying the hypothesis.

Rules of Inference for Quantified Statements

We have discussed rules of inference for propositions. We will now describe some important rules
of inference for statements involving quantifiers. These rules of inference are used extensively
in mathematical arguments, often without being explicitly mentioned.
Universal instantiation is the rule of inference used to conclude that P (c) is true, where c
is a particular member of the domain, given the premise ∀xP (x). Universal instantiation is used
when we conclude from the statement “All women are wise” that “Lisa is wise,” where Lisa is
a member of the domain of all women.
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
76 1 / The Foundations: Logic and Proofs

TABLE 2 Rules of Inference for Quantified Statements.

Rule of Inference Name

∀xP (x)
Universal instantiation
∴ P (c)

P (c) for an arbitrary c

Universal generalization
∴ ∀xP (x)

∃xP (x)
Existential instantiation
∴ P (c) for some element c

P (c) for some element c

Existential generalization
∴ ∃xP (x)

Universal generalization is the rule of inference that states that ∀xP (x) is true, given the
premise that P (c) is true for all elements c in the domain. Universal generalization is used when
we show that ∀xP (x) is true by taking an arbitrary element c from the domain and showing that
P (c) is true. The element c that we select must be an arbitrary, and not a specific, element of
the domain. That is, when we assert from ∀xP (x) the existence of an element c in the domain,
we have no control over c and cannot make any other assumptions about c other than it comes
from the domain. Universal generalization is used implicitly in many proofs in mathematics and
is seldom mentioned explicitly. However, the error of adding unwarranted assumptions about
the arbitrary element c when universal generalization is used is all too common in incorrect
reasoning.
Existential instantiation is the rule that allows us to conclude that there is an element c in
the domain for which P (c) is true if we know that ∃xP (x) is true. We cannot select an arbitrary
value of c here, but rather it must be a c for which P (c) is true. Usually we have no knowledge
of what c is, only that it exists. Because it exists, we may give it a name (c) and continue our
argument.
Existential generalization is the rule of inference that is used to conclude that ∃xP (x) is
true when a particular element c with P (c) true is known. That is, if we know one element c in
the domain for which P (c) is true, then we know that ∃xP (x) is true.
We summarize these rules of inference in Table 2. We will illustrate how some of these rules
of inference for quantified statements are used in Examples 12 and 13.

EXAMPLE 12 Show that the premises “Everyone in this discrete mathematics class has taken a course in
computer science” and “Marla is a student in this class” imply the conclusion “Marla has taken
a course in computer science.”

Solution: Let D(x) denote “x is in this discrete mathematics class,” and let C(x) denote “x has
taken a course in computer science.” Then the premises are ∀x(D(x) → C(x)) and D(Marla).
The conclusion is C(Marla).
The following steps can be used to establish the conclusion from the premises.

Step Reason
1. ∀x(D(x) → C(x)) Premise
2. D(Marla) → C(Marla) Universal instantiation from (1)
3. D(Marla) Premise
4. C(Marla)
▲

Modus ponens from (2) and (3)

Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
 1.6 Rules of Inference 77

EXAMPLE 13 Show that the premises “A student in this class has not read the book,” and “Everyone in this
class passed the first exam” imply the conclusion “Someone who passed the first exam has not
read the book.”

Solution: Let C(x) be “x is in this class,” B(x) be “x has read the book,” and P (x) be “x passed
the first exam.” The premises are ∃x(C(x) ∧ ¬B(x)) and ∀x(C(x) → P (x)). The conclusion
is ∃x(P (x) ∧ ¬B(x)). These steps can be used to establish the conclusion from the premises.
Step Reason
1. ∃x(C(x) ∧ ¬B(x)) Premise
2. C(a) ∧ ¬B(a) Existential instantiation from (1)
3. C(a) Simplification from (2)
4. ∀x(C(x) → P (x)) Premise
5. C(a) → P (a) Universal instantiation from (4)
6. P (a) Modus ponens from (3) and (5)
7. ¬B(a) Simplification from (2)
8. P (a) ∧ ¬B(a) Conjunction from (6) and (7)
9. ∃x(P (x) ∧ ¬B(x)) Existential generalization from (8)

▲
Combining Rules of Inference for Propositions
and Quantified Statements
We have developed rules of inference both for propositions and for quantified statements. Note
that in our arguments in Examples 12 and 13 we used both universal instantiation, a rule of
inference for quantified statements, and modus ponens, a rule of inference for propositional logic.
We will often need to use this combination of rules of inference. Because universal instantiation
and modus ponens are used so often together, this combination of rules is sometimes called
universal modus ponens. This rule tells us that if ∀x(P (x) → Q(x)) is true, and if P (a) is
true for a particular element a in the domain of the universal quantifier, then Q(a) must also
be true. To see this, note that by universal instantiation, P (a) → Q(a) is true. Then, by modus
ponens, Q(a) must also be true. We can describe universal modus ponens as follows:

∀x(P (x) → Q(x))

P (a), where a is a particular element in the domain
∴ Q(a)

Universal modus ponens is commonly used in mathematical arguments. This is illustrated

in Example 14.

EXAMPLE 14 Assume that “For all positive integers n, if n is greater than 4, then n2 is less than 2n ” is true.
Use universal modus ponens to show that 1002 < 2100 .

Solution: Let P (n) denote “n > 4” and Q(n) denote “n2 < 2n .” The statement “For all positive
integers n, if n is greater than 4, then n2 is less than 2n ” can be represented by ∀n(P (n) → Q(n)),
where the domain consists of all positive integers. We are assuming that ∀n(P (n) → Q(n)) is
true. Note that P (100) is true because 100 > 4. It follows by universal modus ponens that
Q(100) is true, namely that 1002 < 2100 .
▲

Another useful combination of a rule of inference from propositional logic and a rule
of inference for quantified statements is universal modus tollens. Universal modus tollens
78 1 / The Foundations: Logic and Proofs

combines universal instantiation and modus tollens and can be expressed in the following way:

∀x(P (x) → Q(x))

¬Q(a), where a is a particular element in the domain
∴ ¬P (a)

The verification of universal modus tollens is left as Exercise 25. Exercises 26–29 develop
additional combinations of rules of inference in propositional logic and quantified statements.

Exercises

1. Find the argument form for the following argument and e) If I work all night on this homework, then I can an-
determine whether it is valid. Can we conclude that the swer all the exercises. If I answer all the exercises, I
conclusion is true if the premises are true? will understand the material. Therefore, if I work all
night on this homework, then I will understand the
If Socrates is human, then Socrates is mortal. material.
Socrates is human. 5. Use rules of inference to show that the hypotheses “Randy
∴ Socrates is mortal. works hard,” “If Randy works hard, then he is a dull boy,”
and “If Randy is a dull boy, then he will not get the job”
imply the conclusion “Randy will not get the job.”
2. Find the argument form for the following argument and
determine whether it is valid. Can we conclude that the 6. Use rules of inference to show that the hypotheses “If it
conclusion is true if the premises are true? does not rain or if it is not foggy, then the sailing race will
be held and the lifesaving demonstration will go on,” “If
If George does not have eight legs, then he is not a the sailing race is held, then the trophy will be awarded,”
spider. and “The trophy was not awarded” imply the conclusion
George is a spider. “It rained.”
7. What rules of inference are used in this famous argu-
∴ George has eight legs.
ment? “All men are mortal. Socrates is a man. Therefore,
Socrates is mortal.”
3. What rule of inference is used in each of these argu-
ments? 8. What rules of inference are used in this argument? “No
a) Alice is a mathematics major. Therefore, Alice is ei- man is an island. Manhattan is an island. Therefore, Man-
ther a mathematics major or a computer science major. hattan is not a man.”
b) Jerry is a mathematics major and a computer science 9. For each of these collections of premises, what relevant
major. Therefore, Jerry is a mathematics major. conclusion or conclusions can be drawn? Explain the
c) If it is rainy, then the pool will be closed. It is rainy. rules of inference used to obtain each conclusion from
Therefore, the pool is closed. the premises.
d) If it snows today, the university will close. The uni- a) “If I take the day off, it either rains or snows.” “I took
versity is not closed today. Therefore, it did not snow Tuesday off or I took Thursday off.” “It was sunny on
today. Tuesday.” “It did not snow on Thursday.”
e) If I go swimming, then I will stay in the sun too long. b) “If I eat spicy foods, then I have strange dreams.” “I
If I stay in the sun too long, then I will sunburn. There- have strange dreams if there is thunder while I sleep.”
fore, if I go swimming, then I will sunburn. “I did not have strange dreams.”
4. What rule of inference is used in each of these arguments? c) “I am either clever or lucky.” “I am not lucky.” “If I
a) Kangaroos live inAustralia and are marsupials. There- am lucky, then I will win the lottery.”
fore, kangaroos are marsupials. d) “Every computer science major has a personal com-
b) It is either hotter than 100 degrees today or the pollu- puter.” “Ralph does not have a personal computer.”
tion is dangerous. It is less than 100 degrees outside “Ann has a personal computer.”
today. Therefore, the pollution is dangerous. e) “What is good for corporations is good for the United
c) Linda is an excellent swimmer. If Linda is an excellent States.” “What is good for the United States is good
swimmer, then she can work as a lifeguard. Therefore, for you.” “What is good for corporations is for you to
Linda can work as a lifeguard. buy lots of stuff.”
d) Steve will work at a computer company this summer. f ) “All rodents gnaw their food.” “Mice are rodents.”
Therefore, this summer Steve will work at a computer “Rabbits do not gnaw their food.” “Bats are not ro-
company or he will be a beach bum. dents.”
 1.6 Rules of Inference 79

10. For each of these sets of premises, what relevant conclu- b) “Each of five roommates, Melissa, Aaron, Ralph, Ve-
sion or conclusions can be drawn? Explain the rules of in- neesha, and Keeshawn, has taken a course in discrete
ference used to obtain each conclusion from the premises. mathematics. Every student who has taken a course in
a) “If I play hockey, then I am sore the next day.” “I discrete mathematics can take a course in algorithms.
use the whirlpool if I am sore.” “I did not use the Therefore, all five roommates can take a course in
whirlpool.” algorithms next year.”
c) “All movies produced by John Sayles are wonder-
b) “If I work, it is either sunny or partly sunny.” “I worked
ful. John Sayles produced a movie about coal miners.
last Monday or I worked last Friday.” “It was not sunny
Therefore, there is a wonderful movie about coal min-
on Tuesday.” “It was not partly sunny on Friday.”
ers.”
c) “All insects have six legs.” “Dragonflies are insects.” d) “There is someone in this class who has been to
“Spiders do not have six legs.” “Spiders eat dragon- France. Everyone who goes to France visits the
flies.” Louvre. Therefore, someone in this class has visited
d) “Every student has an Internet account.” “Homer does the Louvre.”
not have an Internet account.” “Maggie has an Internet 15. For each of these arguments determine whether the argu-
account.” ment is correct or incorrect and explain why.
e) “All foods that are healthy to eat do not taste good.” a) All students in this class understand logic. Xavier is
“Tofu is healthy to eat.” “You only eat what tastes a student in this class. Therefore, Xavier understands
good.” “You do not eat tofu.” “Cheeseburgers are not logic.
healthy to eat.” b) Every computer science major takes discrete math-
f ) “I am either dreaming or hallucinating.” “I am not ematics. Natasha is taking discrete mathematics.
dreaming.” “If I am hallucinating, I see elephants run- Therefore, Natasha is a computer science major.
ning down the road.” c) All parrots like fruit. My pet bird is not a parrot. There-
11. Show that the argument form with premises fore, my pet bird does not like fruit.
p1 , p2 , . . . , pn and conclusion q → r is valid if the d) Everyone who eats granola every day is healthy. Linda
argument form with premises p1 , p2 , . . . , pn , q, and is not healthy. Therefore, Linda does not eat granola
conclusion r is valid. every day.
16. For each of these arguments determine whether the argu-
12. Show that the argument form with premises (p ∧ t) →
ment is correct or incorrect and explain why.
(r ∨ s), q → (u ∧ t), u → p, and ¬s and conclusion
q → r is valid by first using Exercise 11 and then us- a) Everyone enrolled in the university has lived in a dor-
ing rules of inference from Table 1. mitory. Mia has never lived in a dormitory. Therefore,
Mia is not enrolled in the university.
13. For each of these arguments, explain which rules of in- b) A convertible car is fun to drive. Isaac’s car is not a
ference are used for each step. convertible. Therefore, Isaac’s car is not fun to drive.
a) “Doug, a student in this class, knows how to write c) Quincy likes all action movies. Quincy likes the movie
programs in JAVA. Everyone who knows how to write Eight Men Out. Therefore, Eight Men Out is an action
programs in JAVA can get a high-paying job. There- movie.
fore, someone in this class can get a high-paying job.” d) All lobstermen set at least a dozen traps. Hamilton is a
b) “Somebody in this class enjoys whale watching. Ev- lobsterman. Therefore, Hamilton sets at least a dozen
ery person who enjoys whale watching cares about traps.
ocean pollution. Therefore, there is a person in this 17. What is wrong with this argument? Let H (x) be “x is
class who cares about ocean pollution.” happy.” Given the premise ∃xH (x), we conclude that
c) “Each of the 93 students in this class owns a personal H (Lola). Therefore, Lola is happy.
computer. Everyone who owns a personal computer 18. What is wrong with this argument? Let S(x, y) be “x is
can use a word processing program. Therefore, Zeke, shorter than y.” Given the premise ∃sS(s, Max), it follows
a student in this class, can use a word processing pro- that S(Max, Max). Then by existential generalization it
gram.” follows that ∃xS(x, x), so that someone is shorter than
d) “Everyone in New Jersey lives within 50 miles of the himself.
ocean. Someone in New Jersey has never seen the 19. Determine whether each of these arguments is valid. If an
ocean. Therefore, someone who lives within 50 miles argument is correct, what rule of inference is being used?
of the ocean has never seen the ocean.” If it is not, what logical error occurs?
14. For each of these arguments, explain which rules of in- a) If n is a real number such that n > 1, then n2 > 1.
ference are used for each step. Suppose that n2 > 1. Then n > 1.
a) “Linda, a student in this class, owns a red convertible. b) If n is a real number with n > 3, then n2 > 9.
Everyone who owns a red convertible has gotten at Suppose that n2 ≤ 9. Then n ≤ 3.
least one speeding ticket. Therefore, someone in this c) If n is a real number with n > 2, then n2 > 4.
class has gotten a speeding ticket.” Suppose that n ≤ 2. Then n2 ≤ 4.
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)),
a) If x is a positive real number, then x 2 is a positive real ∀x(¬Q(x) ∨ S(x)), ∀x(R(x) → ¬S(x)), and ∃x¬P (x)
number. Therefore, if a 2 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
b) If x 2 = 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
a be a real number with a 2 = 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).
26. Justify the rule of universal transitivity, which states that e) That if not many students like logic, then either math-
if ∀x(P (x) → Q(x)) and ∀x(Q(x) → R(x)) are true, ematics is not easy or logic is not difficult.
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