# How do I prove $\neg(P\land Q)\to(\neg P\lor(\neg P\lor Q))\iff(\neg P\lor Q)$ without using a truth table?

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.

• Note that $(\neg P \lor Q \lor P)$ is a tautology. – player3236 Sep 6 '20 at 13:37
• This also depends on what rules you are allowed to use. – player3236 Sep 6 '20 at 13:37
• 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? – Nimrod Sep 6 '20 at 13:42
• The rules you employed, e.g. material implication, distribution etc. goes both ways. – player3236 Sep 6 '20 at 13:45
• So this is what I just have to do? – Nimrod Sep 6 '20 at 13:45

$$\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}$$

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