Page 96 - Discrete Mathematics and Its Applications

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

Wehavediscussedrulesofinferenceforpropositions.Wewillnowdescribesomeimportantrules
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.