1
$\begingroup$

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$.

$\endgroup$
6
  • 3
    $\begingroup$ How do you define $p\to q$? $\endgroup$
    – John Douma
    Commented Jan 20, 2019 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
    Commented Jan 20, 2019 at 18:50
  • $\begingroup$ What is "exposition" ? $\endgroup$
    – Mauro ALLEGRANZA
    Commented Jan 20, 2019 at 18:51
  • $\begingroup$ Good question, "exposition" meaning "explanation in words, instead of just symbols." $\endgroup$
    – 1Teaches2Learn
    Commented Jan 20, 2019 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
    Commented Jan 20, 2019 at 18:55

1 Answer 1

Reset to default
0
$\begingroup$

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 ....

$\endgroup$
3
  • $\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
    Commented Jan 20, 2019 at 19:30
  • $\begingroup$ @1Teaches2Learn Ha ha, yes, I remember my first post ... and almost instantaneous reply! :) $\endgroup$
    – Bram28
    Commented Jan 20, 2019 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
    Commented Jan 27, 2019 at 8:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .