How do I show this?

Any input would be greatly appreciated!

Thanks in advance!

Printable View

- Feb 12th 2011, 05:02 PMs3aProve that (p ⇒ q) ⇔ (段 ⇒ 殆)
How do I show this?

Any input would be greatly appreciated!

Thanks in advance! - Feb 12th 2011, 05:17 PMtopspin1617
First, I would be slightly careful with the notation...

In logic, the symbol for "implies" is generally $\displaystyle \rightarrow$. We use $\displaystyle \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 $\displaystyle (p\rightarrow q)$ and $\displaystyle (\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" $\displaystyle p,q$ and, for each, use the rules for the if...then connective $\displaystyle \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 PMAckbeet
Please see this sticky and do what it says.

- Feb 12th 2011, 07:41 PMs3a
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 PMtopspin1617
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) ⇔ (段 ⇒ 殆), 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 AMemakarov
- Feb 14th 2011, 09:04 AMs3a
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 AMemakarov
The equality p ⇒ q = 殆 \/ 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.