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.
Best Answer
\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.
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}