Bridge to Abstract Mathematics: Mathematical Proof and Structures

78 LOGIC, PART I: THE PROPOSITIONAL CALCULUS Chapter 2
I

in symbolic form, looks like

Therefore p -, s

Proceeding by either constructing a truth table or using the method de-

scribed in Examples 3 and 4, we conclude that this argument is not logi-

cally valid. 0

The tautologies [p A (p -+ q)] -+ q (modus ponens), [(p -+ q) A (q -+ r)] -,
(p -+ r) (transitivity of implication), and [p -+ (q -+ r)] - [(p A q) -, r],
provide a method of concluding validity of an argument (or suspecting non-
validity) that allows us to avoid writing cumbersome truth tables repeatedly.
Modus ponens indicates that we can conclude q whenever we have p and
p -, q. Transitivity of implication says that we can replace two hypotheses
of the form (p -, q) and (q -, r) by the single hypothesis (p -, r), if this is
to our advantage. The third implication says that if our conclusion has the
form q -, r, we may add q to the list of partial premises and deduce r, rather
that q -, r, from this expanded list. Finally, recall the significance of logical
equivalence: A statement form may be replaced by any equivalent statement
form. We illustrate the method in Example 3.

EXAMPLE 3 Analyze the argument from Example 1 without using a truth

table.

Solution The question is whether we can validly deduce r from the assumed

truth of each of the three partial premises p, p -+ q, and -q v r. We re-

call first the equivalence (-q v r) - (q -, r) [Theorem l(o), Article 2.31.

Thus our premise becomes p A (p + q) A (q -+ r). From p A (p -+ q), we

may conclude q, by modus ponens. From q and q -, r, we may conclude

r, again by modus ponens, as desired. We conclude from this analysis

that r does follow logically from the premise, so that the argument is

indeed valid.

An argument of the form [(p -, q) A (q -, r) A (r -+ s)] -, (p -, s) can be

analyzed as follows. The question is whether we can derive s from p, given

the three hypotheses. Add p to the list of partial premises and ask instead

whether we can derive s from this expanded list. From p A (p -+ q), we get

q. From q and q -+ r, we get r. From r A (r -, s), we get s, as desired.

EXAMPLE 4 Analyze the argument in Example 2, without constructing a

complete truth table.

Solution The question is whether we can derive s from p, given hypotheses

p + q, q -, r, and s -+ r. First, add p to the list of hypotheses. The