Investigation strategies

Deductive reasoning

Much deductive reasoning is based on implications, which are statements of the form If . . . then . . . .

We often write the general statement as If p then q, where p and q are simple statements. For example, in the implication

If it's raining then it's cloudy

p is the statement If it's raining and q is the statement it's cloudy. The statements are called implications because they can be rewritten as p implies q. For example, rain implies cloudiness. (We sometimes need to fudge a little with English to overcome awkwardness in stating implications.)

Negatations

The pieces of implications are often negations of simple statements. The negation of a statement is another statement that is false when the original statement is true, and vice versa. For example, one negation of The person is tall is The person is not tall. Negations are not necessarily opposite; you wouldn't say that The person is tall and The person is short are negations of each other.

Proof by contradiction depends on negations.

To prove that a conjecture is false, you need to prove that its negation is true. If the conjecture is a claim that something is always true, finding one case in which its false is enough to prove that the entire conjecture is false. For example, to prove that the conjecture

If it's a trapezoid then it's a rectangle

is false, you need only to show an example of a trapezoid that isn't a rectangle. Such an example is called a counterexample.

Disguises

Implications are often disguised in forms other than if then and implies. For example, here are some other ways of saying If it's raining then it's cloudy:

It's cloudy if it's raining.
It's raining only if it's cloudy.
Clouds are necessary for rain.
Rain is sufficient to ensure clouds.

Reversing

Implications p implies q and q implies p are called converses of each other. For example, If a person is pregnant then the person is a woman and If a person is a woman then the person is pregnant are converses of each other. Because not all women are pregnant, you can see that converses don't mean the same thing as each other.

On the other hand, implications p implies q and not q implies not p do mean the same thing logically. These are called contrapositives of each other. For example, If a person is pregnant then the person is a woman and If a person is not a woman then the person is not pregnant are contrapositives of each other and have the same logical meaning.

Proofs based on contrapositives are another form of indirect proof.

Direct proof

Underlying every direct proof are three kinds of reasoning:

From the two statements p and p implies q we can conclude statement q. This fact goes by the name modus ponens, Latin for power method.
From the two statements p and not q implies not p we can conclude statement q.
From the two statements p implies q and q implies r we can conclude statement p implies r.

Modus ponens is the basis for proof by induction.