Page 102 - Discrete Mathematics and Its Applications

1.7 Introduction to Proofs 81

theorems. Using these ingredients and rules of inference, the final step of the proof establishes
the truth of the statement being proved.
In our discussion we move from formal proofs of theorems toward more informal proofs.
The arguments we introduced in Section 1.6 to show that statements involving propositions
and quantified statements are true were formal proofs, where all steps were supplied, and the
rules for each step in the argument were given. However, formal proofs of useful theorems can
be extremely long and hard to follow. In practice, the proofs of theorems designed for human
consumption are almost always informal proofs, where more than one rule of inference may
be used in each step, where steps may be skipped, where the axioms being assumed and the
rules of inference used are not explicitly stated. Informal proofs can often explain to humans
why theorems are true, while computers are perfectly happy producing formal proofs using
automated reasoning systems.
The methods of proof discussed in this chapter are important not only because they are used
to prove mathematical theorems, but also for their many applications to computer science. These
applications include verifying that computer programs are correct, establishing that operating
systems are secure, making inferences in artificial intelligence, showing that system specifica-
tions are consistent, and so on. Consequently, understanding the techniques used in proofs is
essential both in mathematics and in computer science.

Some Terminology

Formally, a theorem is a statement that can be shown to be true. In mathematical writing, the
term theorem is usually reserved for a statement that is considered at least somewhat important.
Less important theorems sometimes are called propositions. (Theorems can also be referred to
as facts or results.) A theorem may be the universal quantification of a conditional statement
with one or more premises and a conclusion. However, it may be some other type of logical
statement, as the examples later in this chapter will show. We demonstrate that a theorem is true
with a proof. A proof is a valid argument that establishes the truth of a theorem. The statements
used in a proof can include axioms (or postulates), which are statements we assume to be true
(for example, the axioms for the real numbers, given in Appendix 1, and the axioms of plane
geometry), the premises, if any, of the theorem, and previously proven theorems. Axioms may
be stated using primitive terms that do not require definition, but all other terms used in theorems
and their proofs must be defined. Rules of inference, together with definitions of terms, are used
to draw conclusions from other assertions, tying together the steps of a proof. In practice, the
final step of a proof is usually just the conclusion of the theorem. However, for clarity, we will
often recap the statement of the theorem as the final step of a proof.
A less important theorem that is helpful in the proof of other results is called a lemma
(plural lemmas or lemmata). Complicated proofs are usually easier to understand when they are
proved using a series of lemmas, where each lemma is proved individually. A corollary is a
theorem that can be established directly from a theorem that has been proved. A conjecture is
a statement that is being proposed to be a true statement, usually on the basis of some partial
evidence, a heuristic argument, or the intuition of an expert. When a proof of a conjecture is
found, the conjecture becomes a theorem. Many times conjectures are shown to be false, so they
are not theorems.

Understanding How Theorems Are Stated

Before we introduce methods for proving theorems, we need to understand how many math-
ematical theorems are stated. Many theorems assert that a property holds for all elements in
a domain, such as the integers or the real numbers. Although the precise statement of such