An Introduction to Optimization, 4th Edition

CHAPTER 1

METHODS OF PROOF AND SOME NOTATION

1.1 Methods of Proof

Consider two statements, “A” and “B,” which could be either true or false. For example, let “A” be the statement “John is an engineering student,” and let “B” be the statement “John is taking a course on optimization.” We can combine these statements to form other statements, such as “A and B” or “A or B.” In our example, “A and B” means “John is an engineering student, and he is taking a course on optimization.” We can also form statements such as “not A,” “not B,” “not (A and B),” and so on. For example, “not A” means “John is not an engineering student.” The truth or falsity of the combined statements depend on the truth or falsity of the original statements, “A” and “B.” This relationship is expressed by means of truth tables; see Tables 1.1 and 1.2.

Table 1.1 Truth Table for “A and B” and “A or B”

Table 1.2 Truth Table for “not A”

A	not A
F	T
T	F

From the tables, it is easy to see that the statement “not (A and B)” is equivalent to “(not A) or (not B)” (see Exercise 1.3). This is called DeMorgan’s law.

In proving statements, it is convenient to express a combined statement by a conditional, such as “A implies B,” which we denote “A⇒B.” The conditional “A⇒B” is simply the combined statement “(not A) or B” and is often also read “A only if B,” or “if A then B,” or “A is sufficient for B,” or “B is necessary ...