Flow Chart for Proof/Disproof

NOTE: To prove a statement means to show that the statement is true.

To disprove a statement means to show that the statement is false.

Assumption: D is an infinite set or a very large finite set.

Problem: Determine whether a statement is true or false.

True or False? For all x in D, if ,<hypothesis about x> then <conclusion about x>

true

Disproof Direct Proof Proof by Contradiction

Find a counterexample. Suppose x is any element Suppose x is any element of D

That is: of D for which for which <hypothesis about x>

Find an element x in D <hypothesis about x> is true is true and <conclusion about x> is false.

such that<hypothesis about x> Show that <conclusion about x> is true. Show that this supposition leads to a contradiction.

is true and <conclusion about x>

is false.