Java Reference
In-Depth Information
succinctly. The argument phase involves good technical writing skills — the ability
to make a clear, logical argument.
Being conversant with standard proof techniques can help you in this process.
Knowing how to write a good proof helps in many ways. First, it clarifies your
thought process, which in turn clarifies your explanations. Second, if you use one of
the standard proof structures such as proof by contradiction or an induction proof,
then both you and your reader are working from a shared understanding of that
structure. That makes for less complexity to your reader to understand your proof,
because the reader need not decode the structure of your argument from scratch.
This section briefly introduces three commonly used proof techniques: (i) de-
duction, or direct proof; (ii) proof by contradiction, and (iii) proof by mathematical
induction.
2.6.1 Direct Proof
In general, a direct proof is just a “logical explanation.” A direct proof is some-
times referred to as an argument by deduction. This is simply an argument in terms
of logic. Often written in English with words such as “if ... then,” it could also
be written with logic notation such as “P ) Q.” Even if we don't wish to use
symbolic logic notation, we can still take advantage of fundamental theorems of
logic to structure our arguments. For example, if we want to prove that P and Q
are equivalent, we can first prove P ) Q and then prove Q ) P.
In some domains, proofs are essentially a series of state changes from a start
state to an end state. Formal predicate logic can be viewed in this way, with the vari-
ous “rules of logic” being used to make the changes from one formula or combining
a couple of formulas to make a new formula on the route to the destination. Sym-
bolic manipulations to solve integration problems in introductory calculus classes
are similar in spirit, as are high school geometry proofs.
2.6.2 Proof by Contradiction
The simplest way to disprove a theorem or statement is to find a counterexample
to the theorem. Unfortunately, no number of examples supporting a theorem is
sufficient to prove that the theorem is correct. However, there is an approach that
is vaguely similar to disproving by counterexample, called Proof by Contradiction.
To prove a theorem by contradiction, we first assume that the theorem is false. We
then find a logical contradiction stemming from this assumption. If the logic used
to find the contradiction is correct, then the only way to resolve the contradiction is
to recognize that the assumption that the theorem is false must be incorrect. That
is, we conclude that the theorem must be true.
Example2.10 Here is a simple proof by contradiction.
Search WWH ::




Custom Search