Discrete Structures

# Proof Strategies

 Last Update: 24 February 2009 Note: or material is highlighted

#### Meta-strategies (i.e., strategies for using the strategies):

1. Determine the logical form of the theorem to be proved.
Then use an appropriate strategy.

2. If more than one strategy is applicable,
then try each of them until you find one that works.

#### Specific Strategies:

If the logical form is: Then a strategy is:
p Indirect Proof:
Assume/suppose/make believe that ¬p
& then try to derive a contradiction;
i.e., try to find r such that (r ∧ ¬r)
PRED(c), where PRED(c) =def DEF(c) Try to prove DEF(c)

In general, wherever possible in a proof,
try to replace predicates by their definitions

¬P(x),
where P(x) is a compound proposition
Try to prove Q(x), where Q(x) ≡ ¬P(x),
but the "¬" has been moved to the right by DeMorgan
(p → q), where p is a contradiction "Vacuous" proof:
(p → q) must be true!
(p → q), where q is a tautology "Trivial" proof:
(p → q) must be true!
(p → q) Direct Proof:
Assume p
& then try to show q

Hint:
If p =def DEF(x)
then suppose DEF(x) & try to show q

(p → q) Indirect Proofs:

Proof by Contraposition:
Try to show (¬q → ¬p)
(by using one of the other strategies for "→")

Assume p
Assume ¬q
& then try to find a contradiction;
i.e., try to find a proposition r such that (r ∧ ¬r)

(p1 ∨ p2) → q

To make this simpler to understand,
I just show the case for 2 propositions;
see text for more details.

Proof by Cases:
Try to show each of the following:
(p1 → q)
and
(p2 → q)
(by using any of the above strategies for "→")
(p ↔ q) Try to show
both (p → q)
and (q → p)
(by using any of the above strategies for "→")
(p1 ↔ p2 ↔ p3)

To make this simpler to understand,
I just show the case for 3 propositions;
see text for more details.

Try to show all of the following:
(p1 → p2)
and
(p2 → p3)
and
(p3 → p1)
(by using any of the above strategies for "→")
∀x[P(x) → Q(x)] Try to show
[P(c) → Q(c)], for arbitrary c
(by using one of the strategies for "→";
then apply UG)
∃xP(x) Constructive Proof:
Find c such that P(c)