Principles of Mathematics in Operations Research

8 1 Introduction

Proof. Base: n = 1 = -j-1-

Hypothesis: n = j, ELi * = =L^-

Conciusion: n = j + 1, Efc=i-J + l & I. _ (.7 + D(J+^2 )

Thus, l + 2 + --- + n = £?_,fc=^i. D

1> = (i+1) [1+f] _ (j+l)(j+2) — 2

fc=l'

1.3.3 Contradiction Method

When we examine the operation table for A =*• B in Table 1.2, we immediately

conclude that the only circumstance under which A =4- B is not correct is when

A is true and B is false.

Contradiction

Proof by Contradiction assumes the condition (A is true B is false) and tries

to reach a legitimate condition in which this cannot happen. Thus, the only

way A =$• B being incorrect is ruled out. Therefore, A => B is correct. This

proof method is quite powerful.

Proposition 1.3.

n 6 N, n is even =$• n is even.

Proof. Let us assume that n 6 N, n^2 is even but n is odd. Let n = 2k -1, A; 6

N. Then, n^2 = 4k^2 - 4/c + 1 which is definitely odd. Contradiction. •

Contraposition

In contraposition, we assume A and B and go forward while we assume A

and come backward in order to reach a Contradiction. In that sense, con-

traposition is a special case of Contradiction where all the effort is directed

towards a specific type of Contradiction (^4 vs. A). The main motivation under

contrapositivity is the following:

A=> B = AVB = (A\/ JB) V A = (A/\B)^> A.

One can prove the above fact simply by examining Table 1.2.

Table 1.2. Operation table for some logical operators.

A

T

T

F

F

A

F

F

T

T

B

T

F

T

F

B

F

T

F

T

A^B

T

F

T

T

Av B

T

F

T

T

AAB

F

T

F

F

A/\B^ A

T

F

T

T