1.3 Additional Forms of Proof

In this section, we take up several additional topics concerning how to construct proofs:

1. Proofs about sets.

2. Proofs by contradiction.

3. Proofs by counterexample.

2. [ж], the ceiling of real number x, is the least integer equal to or greater than X.

Theorem 1.7: Let л; be a real number. Then [x\ = [x] if and only if x is an integer,

PROOF: (Only-if part) In this part, we assume [x\ - fx] and try to prove x is an integer. Using the definitions of the floor and ceiling, we notice that [xj < x, and fx] > X. However, we are given that [x\ - fx]. Thus, we may substitute the floor for the ceiling in the first inequality to conclude fx] < x. Since both fx] < X and fx] > x hold, we may conclude by properties of arithmetic inequalities that fx] = a;. Since fx] is always an integer, x must also be an integer in this case.

(If part) Now, we assume x is an integer and try to prove [xj = fx]. This part is easy. By the definitions of floor and ceiling, when x is an integer, both [xJ and fx] are equal to x, and therefore equal to each other, □

1.2.4 Theorems That Appear Not to Be If-Then Statements

Sometimes, we encounter a theorem that appears not to have a hypothesis. An example is the well-known fact from trigonometry:

Theorem 1.8: sm + cos в = 1. □

Actually, this statement does have a hypothesis, and the hypothesis consists of all the statements you need to know to interpret the statement. In particular, the hidden hypothesis is that в is an angle, and therefore the functions sine and cosine have their usual meaning for angles. From the definitions of these terms, and the Pythagorean Theorem (in a right triangle, the square of the hypotenuse equals the sum of the squares of the other two sides), you could prove the theorem. In essence, the if-then form of the theorem is really: if в is an angle, then sin в + cos в = 1.

14 CHAPTER L AUTOMATA: THE METHODS AND THE MADNESS 1.3.1 Proving Equivalences About Sets

In automata theory, we are frequently asked to prove a theorem which says that the sets constructed in two different ways are tlie same sets. Often, these sets are sets of character strings, and the sets are called languages, but in this section the nature of the sets is miimportant. If E and F are two expressions representing sets, the statement E = F means that the two sets represented are the same. More precisely, every element in the set represented by E is in the set represented by F, and every element in the set represented by F is in the set represented by E.

Example 1.9: The commutative law of union says that we can take the union of two sets R and S in either order. That is, RV S - S U R. hi this case, E is the expression R\J S and F is the expression S U R. The commutative law of union says that E - F. □

We can write a set-equality E = F as an if-and-only-if statement: an element j; is in £ if and only if x is in F. As a consequence, we see the outline of a proof of any statement that asserts the equality of two sets E = F\\t follows tlie form of any if-and-only-if proof:

1. Proof that if X is in E, then x is in F,

2. ProC that if x is in F, then x is in E.

ks an example of this proof process, let us prove the distributive law of union over intersection:

Theorem 1.10: R\J {S Г\Т) = {RU S) f] {R\J T).

PROOF: The two set-expressions involved are £ = Л U (5 П Г) and

F(RUS)n{RL)T)

We shall prove the two parts of the theorem in turn. In the if part we assume element x is in E and show it is in F. This part, summarized in Fig. 1,5, uses the definitions of union and intersection, with which we assume you are familiar.

Then, wo nmst prove the only-if part of the theorem. Here, we assume x is in F and show it is in E. The steps are summarized in Fig. 1.6. Since we have now proved both parts of the if-and-only-if statement, the distributive law of union over int(!rsection is proved. □

1.3.2 The Contrapositive

Every if-then statement has an equivalent form that in some circumstances is easier to prove. The contrapositive of the statement if Я then C is if not С then not H. A statement and its contrapositive are either both true or both false, so we can prove either to prove the other.

To see why if Я then C and if not С then not Я are logically equivalent, first observe that there are four cases to consider:

Figure 1.6: Steps in the only-lf part of Theorem 1,10

1, H and С both true.

2, H true and С false.

3. С true and H false,

4. Я and С both false.

There is only one way to make an if-then statement false; the hypothesis must be true and the conclusion false, as in case (2). For the other three cases, including case (4) where the conclusion is false, the if-then statement itself is true.

Now, consider for which cases the contrapositive if not С then not H is false. In order for this statement to be false, its hypothesis (which is not C ) must be true, and its conclusion (which is not Я ) must be false. But not C7 is true exactly when С is false, and not Я is false exactly when H is true. These two conditions are again case (2), which shows that in eacli of the four cases, the original statement and its contrapositive are either both true or both false; i.e., they are logically equivalent.