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, 2020 at 13:37
  • 1
    $\begingroup$ This also depends on what rules you are allowed to use. $\endgroup$
    – player3236
    Sep 6, 2020 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, 2020 at 13:42
  • $\begingroup$ The rules you employed, e.g. material implication, distribution etc. goes both ways. $\endgroup$
    – player3236
    Sep 6, 2020 at 13:45
  • $\begingroup$ So this is what I just have to do? $\endgroup$
    – Nimrod
    Sep 6, 2020 at 13:45

1 Answer 1

Reset to default
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, 2020 at 13:45
  • $\begingroup$ @Nimrod you are very welcome! I didn’t get the question. What bi-conditionality? $\endgroup$
    – Air Mike
    Sep 6, 2020 at 13:47
  • $\begingroup$ Note that these are all logical equivalences $\endgroup$
    – Air Mike
    Sep 6, 2020 at 13:47

You must log in to answer this question.

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