Proofs involving negations and conditionals

  • #1
20
0
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


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.)
  1. Suppose ## P \rightarrow Q ## and ## R \rightarrow \neg Q ## are both true. Prove that ## P \rightarrow \neg R ## is true.
  2. 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 ##.
The second one I found at least 3 ways of proving, so I'm most interested in input on this one. Which one would be better? Are there other, better ways of proving it?
  • (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.
Thanks.
 

Answers and Replies

  • #2
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,470
246
All of your proofs look fine to me. For the second statement, I don't see any reason to prefer one of your three proofs over another. It's a matter of taste. I like the middle proof (contrapositive) slightly better because it doesn't require me to remember how to negate ##A \to B##. But they're all valid and easy to understand. Nice job finding several proofs of the same statement - doing so can often provide additional insight into the problem.
 
  • Like
Likes jfierro
  • #3
20
0
Thanks a lot. I realize the proofs are very basic so there wasn't much room for me to screw up. I just exercise 3.2.8 which was a bit more challenging and I'll post that in a new thread soon.
 

Related Threads on Proofs involving negations and conditionals

Replies
2
Views
1K
Replies
10
Views
1K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
18
Views
1K
Replies
1
Views
953
  • Last Post
Replies
2
Views
712
  • Last Post
Replies
5
Views
821
  • Last Post
Replies
3
Views
647
  • Last Post
Replies
13
Views
1K
  • Last Post
Replies
1
Views
474
Top