Prove that (p ⇒ q) ⇔ (¬q ⇒ ¬p)

• Feb 12th 2011, 05:02 PM
s3a
Prove that (p ⇒ q) ⇔ (¬q ⇒ ¬p)
How do I show this?

Any input would be greatly appreciated!
• Feb 12th 2011, 05:17 PM
topspin1617
Quote:

Originally Posted by s3a
How do I show this?

Any input would be greatly appreciated!

First, I would be slightly careful with the notation...

In logic, the symbol for "implies" is generally $\rightarrow$. We use $\Rightarrow$ on the "metamathematical" level; i.e., when we want to talk ABOUT formulas such as these. A subtle distinction, but nonetheless important...

Anyway, to prove that $(p\rightarrow q)$ and $(\neg p\rightarrow \neg q)$ are really the "same thing", I would simply construct a truth table. Make all possible combinations of T and F for each of the two "statements" $p,q$ and, for each, use the rules for the if...then connective $\rightarrow$ to find the truth values of the two statements. If you can prove that the two have the same exact truth table, then you are done.
• Feb 12th 2011, 05:55 PM
Ackbeet
Please see this sticky and do what it says.
• Feb 12th 2011, 07:41 PM
s3a
topspin1617: Thanks! I feel dumb now. Is there a way to do this with algebra and not using tables though? If there is, could you tell me how to do it that way too please? (My notation is correct since my teacher uses it and it's all I've ever seen - maybe you're using a different system as I write below?)

Ackbeet: I have no idea, what system I am using. How do I figure it out for future reference?
• Feb 12th 2011, 07:51 PM
topspin1617
Quote:

Originally Posted by s3a
topspin1617: Thanks! I feel dumb now. Is there a way to do this with algebra and not using tables though? If there is, could you tell me how to do it that way too please? (My notation is correct since my teacher uses it and it's all I've ever seen - maybe you're using a different system as I write below?)

Ackbeet: I have no idea, what system I am using. How do I figure it out for future reference?

You're welcome. I'm not saying your notation is wrong, really... it's just a very subtle thing. Basically... notice how if you JUST write what you're trying to prove, (p ⇒ q) ⇔ (¬q ⇒ ¬p), it just looks like one long formula? That's all I'm saying.

And if you don't know which type of logic you're using, then chances are you're just using basic, first order propositional logic. Which... well basically just means the few symbols you've learned, and the rules that go with them. Nothing fancy.
• Feb 14th 2011, 06:25 AM
emakarov
Quote:

Originally Posted by s3a
Is there a way to do this with algebra and not using tables though?

p ⇒ q = ¬p \/ q. Also, ¬q ⇒ ¬p = ¬¬q \/ ¬p = ¬p \/ q.
• Feb 14th 2011, 09:04 AM
s3a
I'm confused at the first step, could you tell me how to get there? Like could you please state every theorem or identity or whatever? Sorry if it's obvious.
• Feb 14th 2011, 10:35 AM
emakarov
The equality p ⇒ q = ¬p \/ q can be verified using a truth table. Alternatively, if you approach this problem from a purely syntactic standpoint (i.e., no talking about truth values, only rewriting some expressions by others), then it can serve as the definition of ⇒, or it has to be an axiom or follow from other axioms. So, in the syntactic approach, one has to specify the basic equivalences one starts with.

This is similar to justifying 2 * n = n + n. If you are looking at this from the high-school algebra standpoint, then you can take any number n and verify that the equation is true. If you are in a more abstract setting, such as when this equation can later be applied to vectors, functions and other objects that may not even be in the picture at this moment, then this equation must be an axiom or follow from other axioms. In this case, the set of axioms must be specified.