Page 93 - Discrete Mathematics and Its Applications

72 1 / The Foundations: Logic and Proofs

TABLE 1 Rules of Inference.
Rule of Inference Tautology Name
p (p ∧ (p → q)) → q Modus ponens
p → q
∴ q
¬q (¬q ∧ (p → q)) →¬p Modus tollens
p → q
∴ ¬p

p → q ((p → q) ∧ (q → r)) → (p → r) Hypothetical syllogism
q → r
∴ p → r

p ∨ q ((p ∨ q) ∧¬p) → q Disjunctive syllogism
¬p
∴ q
p p → (p ∨ q) Addition
∴ p ∨ q
p ∧ q (p ∧ q) → p Simplification
∴ p
p ((p) ∧ (q)) → (p ∧ q) Conjunction
q
∴ p ∧ q
p ∨ q ((p ∨ q) ∧ (¬p ∨ r)) → (q ∨ r) Resolution
¬p ∨ r
∴ q ∨ r

EXAMPLE 3 State which rule of inference is the basis of the following argument: “It is below freezing now.
Therefore, it is either below freezing or raining now.”

Solution: Let p be the proposition “It is below freezing now” and q the proposition “It is raining
now.” Then this argument is of the form

p
∴ p ∨ q

This is an argument that uses the addition rule. ▲

EXAMPLE 4 State which rule of inference is the basis of the following argument: “It is below freezing and
raining now. Therefore, it is below freezing now.”

Solution: Let p be the proposition “It is below freezing now,” and let q be the proposition “It is
raining now.” This argument is of the form

p ∧ q
∴ p

This argument uses the simplification rule. ▲