In this question, the professor asks us in parts i through iii to prove using truth tables that:

i. $\neg (p \lor q) \Leftrightarrow (\neg p) \land (\neg q)$

ii. $\neg (p \land q) \Leftrightarrow (\neg p) \lor (\neg q)$

iii. $\neg (\neg p) \Leftrightarrow p$

Then in part iv. he changes the game and asks us to "use (i-iii) to derive (by the use of a succession of $\Leftrightarrow$'s)" that $p \lor q \Leftrightarrow (\neg p) \rightarrow q$. That is, a truth table is now specifically not allowed.

I am just stuck. I get that statements i. through iii. are now "tools" that we can use to prove that $p \lor q \Leftrightarrow (\neg p) \rightarrow q$. I understand that $p \lor q$ means one or both must be true, so if one is false (i.e. $\neg p$), then the other must be true. But I don't see how I am supposed to prove that a statement is equivalent to an implication using i. through iii. if none of these statements i. through iii. involve an implication!

I tried submitting this combination of $\Leftrightarrow$ statements and exposition:

"$p \lor q \Leftrightarrow \neg (\neg (p \land q)) \Leftrightarrow \neg((\neg p) \land (\neg q))$ where this last statement means that $p$ and $q$ cannot be simultaneously false, so if $p$ is false, then $q$ must be true,"

However, the professor said there's an easier way, and I should be able to prove the statement using ONLY $\Leftrightarrow$ statements, and no exposition. I feel like I'm just missing something obvious. Or maybe he is assuming we're going to use outside knowledge and not JUST statements i. through iii.?

EDIT: In case anyone ever comes across this, the answer is that you are to use a combination of the rules i. through iii. as described, and also common, outside facts. So you have $(p \lor q) \equiv \neg(\neg p) \lor q \equiv \neg p \rightarrow q$.

  • 3
    $\begingroup$ How do you define $p\to q$? $\endgroup$ – John Douma Jan 20 at 18:49
  • 2
    $\begingroup$ You are right. With only (i)-(iii) you cannot, because there is nowhere the symbol $\to$ in them... thus, it cannot "pop up" from nowhere. $\endgroup$ – Mauro ALLEGRANZA Jan 20 at 18:50
  • $\begingroup$ What is "exposition" ? $\endgroup$ – Mauro ALLEGRANZA Jan 20 at 18:51
  • $\begingroup$ Good question, "exposition" meaning "explanation in words, instead of just symbols." $\endgroup$ – 1Teaches2Learn Jan 20 at 18:52
  • $\begingroup$ Ok... $p \lor q$ is "either $p$ or $q$ (inclusive or)" that means that at least one of them must be TRUE. If so, if $p$ is FALSE, then $q$ must necessarily be TRUE. And this is : from Left to Right... $\endgroup$ – Mauro ALLEGRANZA Jan 20 at 18:55

You're absolutely right. With no rule involving $\rightarrow$ in (i)-(iii) this is impossible.

But, typically it is given that $p \rightarrow q \Leftrightarrow \neg p \lor q$

With that, I am sure you can do it!

And ask your professor about this ....

  • $\begingroup$ Thank you so much! This was my first time asking a question, and I was not expecting help to come so quickly! I love this site. (Thanks also to Mauro Allegranza.) $\endgroup$ – 1Teaches2Learn Jan 20 at 19:30
  • $\begingroup$ @1Teaches2Learn Ha ha, yes, I remember my first post ... and almost instantaneous reply! :) $\endgroup$ – Bram28 Jan 20 at 19:45
  • $\begingroup$ Thanks again! I did end up getting this question correct. I have submitted an upvote for you, but it apparently will not go through until I get enough "karma" or whatever this site calls it! So I'm off to earn more of it, whatever it's called :P $\endgroup$ – 1Teaches2Learn Jan 27 at 8:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.