- #1

- 20

- 1

**0. Background**

First and foremost, this is a proof-reading request. I'm going through Velleman's "How To Prove It" because I found that writing and understanding proofs is a prerequisite to serious study of mathematics that I did not meet. Unfortunately, the book is very light on answers to its exercises and there is no solution manual available for purchase. Also, I understand that the best (and only?) way of learning to write proofs is by getting feedback from actual human beings. For what it's worth, I have an engineering degree's curriculum worth of math.

1. Homework Statement

1. Homework Statement

Exercise 3.2.2. This problem could be solved by using truth tables, but don't do it that way. Instead, use the methods for writing proofs discussed discussed so far in this chapter. (See Example 3.2.4.)

- Suppose ## P \rightarrow Q ## and ## R \rightarrow \neg Q ## are both true. Prove that ## P \rightarrow \neg R ## is true.
- Suppose that ## P ## is true. Prove that ## Q \rightarrow \neg (Q \rightarrow \neg P) ##.

## Homework Equations

At this point Velleman has introduced sentential and quantificational logic. He has talked about a few techniques that can be used to tackle proofs involving conditionals and negations, including proof by contradiction and contrapositive, how one can use the

*givens*of a problem to infer other givens via inference rules such as

*modus ponens*and

*modus tollens*, etc. For example, he says that to prove a statement of the form ##P \rightarrow Q##, one can assume that P is true and then prove Q.

## The Attempt at a Solution

The first one is rather simple:

- Suppose ##P## is true. Then, since ##P \rightarrow Q##, it follows that ##Q## is true. By the contrapositive of ## R \rightarrow \neg Q ##, we know that ## Q \rightarrow \neg R ##. Therefore, ## P \rightarrow \neg R ##.

*(By assuming the antecedent is true and proving the consequent. Contrapositive.)*Suppose ##Q## is true. Then ## \neg (Q \rightarrow \neg P) ## is also true since it is equivalent to ## Q \wedge P ## and we know ##P## is true. Therefore, if ## Q ##, then ## \neg (Q \rightarrow \neg P)##.

*(By contrapositive.)*We will prove ##Q \rightarrow \neg (Q \rightarrow \neg P)## by its contrapositive ##(Q \rightarrow \neg P) \rightarrow \neg Q##. Suppose ##Q \rightarrow \neg P## is true. Since we know ##P## is true, it cannot be that ##Q## is true (again by contrapositive). Therefore, ##(Q \rightarrow \neg P) \rightarrow \neg Q##.

*(By contradiction.)*Assume ##\neg (Q \rightarrow \neg (Q \rightarrow \neg P))## is true. This is equivalent to saying that ## Q \wedge (Q \rightarrow \neg P) ## is true. Thus, both ## Q ## and ## Q \rightarrow \neg P ## must be true. But since ## Q \rightarrow \neg P ##, we have ## \neg P ##, which is a contradiction. Therefore, it cannot be the case that ##Q \rightarrow \neg (Q \rightarrow \neg P)## is false.