4
$\begingroup$

Without using truth tables prove that $$\neg(P\land Q)\to(\neg P\lor(\neg P\lor Q))\iff(\neg P\lor Q)$$

This is a question I've encountered during my examination.

So basically what I did was, I took the RHS of the equation which is $\neg(P\land Q)\to(\neg P\lor(\neg P\lor Q))$ and hoped I could equate it to $(\neg P\lor Q)$ even though I was sure it was not enough to prove this bi - conditional statement.

Following on my assumption, this is what I've reached

\begin{array}{rl} & & \neg(P\land Q)\to(\neg P\lor(\neg P\lor Q)) \iff\\ & \iff & (P\land Q)\lor(\neg P\lor Q) \iff\\ & \iff & (\neg P\lor Q\lor P) \land(\neg P\lor Q\lor Q) \iff\\ & \iff & Q \land(\neg P\lor Q) & \end{array}

I'm kinda stuck on what to do after this, I'm not even sure whether this approach is even right. So some help is appreciated on how to prove this bi - conditional statement.

$\endgroup$
5
  • $\begingroup$ Note that $(\neg P \lor Q \lor P)$ is a tautology. $\endgroup$ – player3236 Sep 6 '20 at 13:37
  • 1
    $\begingroup$ This also depends on what rules you are allowed to use. $\endgroup$ – player3236 Sep 6 '20 at 13:37
  • $\begingroup$ Well, yes indeed it's a tautology and I'd get the LHS, but how can I prove that it's a bi-conditional statement? $\endgroup$ – Nimrod Sep 6 '20 at 13:42
  • $\begingroup$ The rules you employed, e.g. material implication, distribution etc. goes both ways. $\endgroup$ – player3236 Sep 6 '20 at 13:45
  • $\begingroup$ So this is what I just have to do? $\endgroup$ – Nimrod Sep 6 '20 at 13:45
4
$\begingroup$

\begin{array}{rl} & & \neg(P\land Q)\to(\neg P\lor(\neg P\lor Q)) \iff\\ & \iff & (P\land Q)\lor(\neg P\lor Q) \iff & \quad & \text{Material Implication}\\ & \iff & (\neg P\lor Q\lor P) \land(\neg P\lor Q\lor Q) & \quad & \text{Distributive Law}\\ \end{array}

As you can verify, $\neg P \vee Q \vee P$ is a tautology.

$$\neg P \vee Q \vee P \iff \neg P \vee P \vee Q \iff \top \vee Q \iff \top$$

Hence, we have the following.

\begin{array}{rl} & & \top \wedge (\neg P \vee Q \vee Q) \iff\\ & \iff & \neg P \vee Q \vee Q \iff\\ & \iff & \neg P \vee Q & \square\\ \end{array}

$\endgroup$
3
  • 1
    $\begingroup$ Thanks, but what about this bi-conditionality? $\endgroup$ – Nimrod Sep 6 '20 at 13:45
  • $\begingroup$ @Nimrod you are very welcome! I didn’t get the question. What bi-conditionality? $\endgroup$ – Air Mike Sep 6 '20 at 13:47
  • $\begingroup$ Note that these are all logical equivalences $\endgroup$ – Air Mike Sep 6 '20 at 13:47

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.