## Chapter - 3, Proofs

### Section - 3.2 - Proofs Involving Negations and Conditionals

### Summary

- There can be following ways to prove a
*goal*of the form :- Convert or re-express the
*goal*to some other form and then use one of the proof strategies for this other goal form. This is generally possible when the original goal is complex goal(containing many components). - Proof by contradiction: by assuming the
*goal*is true and try to reach a contradiction. On a contradiction, it can be concluded that P must be false.

- Convert or re-express the
*Proof by contradiction*is vague as it requires to produce a contradiction by proving something that is known to be false. One approach can be:- To use a
*given*of the form : Try making as*goal*. Now, If can be proved, then the proof will be complete, because contradicts the given .

- To use a
- If
*not*using the strategy to prove by contradiction, One approach can be:- To re-express/convert a
*given*of the form of , to some other form.

- To re-express/convert a
- In previous section, strategy to prove
*goal*of the form of was described. - Apart from all the above strategies, One more strategy can be:
- To use a
*given*of the form of . Many strategies for using givens suggests ways for drawing inferences from the givens. These strategies are called*rules of inference*. There can be following two*Rules of inference*for using given of the form of :- Rule
*modus ponens*: If both and are true, then must also be true. - Rule
*modus tollens*: If is true and is false, then must also be false.

- Rule

- To use a
- Till now following strategies are covered:
- To prove a
*goal*of the form . - To use a
*given*of the form of . - To prove a
*goal*of the form of . - To use a
*given*of the form of .

- To prove a

**Soln1**

**(a)**

Suppose . Since , it follows . Similarly, since , it follows . Thus if then , or .

**(b)** Suppose . For , using contra-positive for proof. Suppose , it follows . Since , it follows . Thus , or . It follows that .

**Soln2**

**(a)**

Suppose . Since , it follows . Since , using contrapositive , it follows . Thus, .

**(b)**

Simplifying , gives . Since P, it follows , which is always true.

**Soln3**

Suppose . Since , it follows that . Now since , it follows that . Thus .

**Soln4**

Suppose . Since , it follows that . And is equivalent to . Since , it follows that . Thus .

**Soln5**

Suppose , which means and . Since , it follows that . Since and , it follows that . This contradicts the *given*: . Thus .

**Soln6**

Since and , it follows that . Suppose , then it follows that . But it contradicts with the given . Thus .

**Soln7**

Suppose . Since , it follows that . But this contradicts the *given* that . Thus .

**Soln8**

Suppose . Since , it follows that . Similarly, . Thus there are four possible cases:

- Case 1: and .
- Case 2: and .
- Case 3: and . This is not possible because and . But in this case .
- Case 4: and . This is also not possible because and . But in this case .

Thus only Case 1 and Case 2 are possible. It follows that .

**Soln9**

Suppose . We will prove , using contra-positive. Suppose , it follows that . Thus we have .

**Soln10**

Simplifying , gives . Suppose . Suppose , it follows that , or . Thus we have .

**Soln11**

**(a)** Reverse of , is . Thus reverse of the conclusion used in proof is wrong.

**(b)** Using , and , gives . Thus conclusion is not correct for the given , and .

**Soln12**

**(a)** Statement:

Since and , then .

is not *correct*.

**(b)** Lets say , and . Now if , the theorem is not correct.

Leaving Problems 13 to 16, as all involve truth tables and such problems were already solved in earlier chapters.

**Soln17**

Suppose . Suppose , it follows that , or or . Thus for and , there is no contradiction. Thus theorem is not correct.