1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proofs involving negations and conditionals

  1. Jan 9, 2015 #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. The problem statement, all variables and given/known data


    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) ##.
    2. Relevant 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.

    3. 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.
     
  2. jcsd
  3. Jan 9, 2015 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  4. Jan 10, 2015 #3
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted