The Art and Craft of Problem Solving

2.3 METHODS OF ARGUMENT 41

the ":=" is the new definition (usually a simple variable) and the thing on the

right is an expression using already defined variables. See Example 2.3.3 for

an example of this notation.

6. A strictly formal argument may deal with many logically similar cases. Some­
   times it is just as clear to single out one illustrative case or example. When this
   happens, we always alert the audience with WLOG ("without loss of general­
   ity"). Just make sure that you really can argue the specific and truly prove the
   general. For example, suppose you intend to prove that 1 + 2 + 3 + ... + n =
   n(n + 1) /2 for all positive integers n. It would be wrong to argue, "WLOG, let
   n = 5. Then 1 + 2 + 3 + 4 + 5 = 15 = 5 ·6/2. QED." This argument is certainly
   not general!

Deduction and Symbolic Logic

"Deduction" here has nothing to do with Sherlock Holmes. Also known as "direct
proof," it is merely the simplest form of argument in terms of logic. A deductive

argument takes the form "If P, then Q" or "P===:::;.Q" or "P implies Q." Sometimes the

overall structure of an argument is deductive, but the smaller parts use other styles.
If you have isolated the penultimate step, then you have reduced the problem to the
simple deductive statement

The truth of the penultimate step ===:::;. The conclusion.

Of course, establishing the penultimate step may involve other forms of argument.

Sometimes both p===:::;.Q and Q===:::;.p are true. In this case we say that P and Q are

logically equivalent, or P {=::} Q. To prove equivalence, we first prove one direction

(say, P=== Q) and then its converse Q=== P.

Keep track of the direction of the your implications. Recall that p===:::;.Q is not

logically equivalent to its converse Q===* P. For example, consider the true statement

"Dogs are mammals." This is equivalent to "If you are a dog, then you are a mammal."
Certainly, the converse "If you are a mammal, then you are a dog" is not true!

However, the contrapositive of P===*Q is the statement (not Q) ===:::;. (not P), and

these two are logically equivalent. The contrapositive of the clearly true statement
"Dogs are mammals" is the true statement "Non-mammals are not dogs".
Viewed globally, most arguments have a simple deductive structure. But locally,
the individual pieces of an argument can take many forms. We tum now to the most
common of these alternate forms, argument by contradiction.

Argument by Contradiction

Instead of trying to prove something directly, we start by assuming that it is false, and
show that this assumption leads us to an absurd conclusion. A contradiction argument
is usually helpful for proving directly that something cannot happen. Here is a simple
number theory example.

Example 2.3.1 Show that

(4)