1
$\begingroup$

I want to show through Boolean algebra that the statement $\neg Q\Rightarrow (R\Rightarrow \neg (P\land Q))$ is equivalent to the tautology $Q\lor(\neg Q)$?

1 Answers 1

5

Don't know exactly what you mean by "Boolean algebra", given that implications are not usually part of the language of Boolean algebras. If I translate $A\Rightarrow B$ to the logically equivalent $\neg A \lor B$, then it is straightforward:

\begin{align*} \neg Q\Rightarrow (R\Rightarrow (\neg (P\land Q)) &\equiv \neg(\neg Q)\lor (R\Rightarrow (\neg (P\land Q)))\\ &\equiv Q \lor (\neg R \lor (\neg(P\land Q)))\\ &\equiv Q\lor (\neg R \lor (\neg P \lor \neg Q))\\ &\equiv Q \lor \neg R \lor \neg P \lor \neg Q\\ &\equiv (Q\lor \neg Q) \lor (R\lor \neg P)\\ &\equiv Q\lor \neg Q. \end{align*}

Added. In the comments you ask how to prove it by contradiction: here we use the fact that $\neg(A\Rightarrow B) \equiv A\land \neg B$.

\begin{align*} \neg\Bigl(\neg Q\Rightarrow (R\Rightarrow (\neg (P\land Q))\Bigr) &\equiv \neg Q \land \neg\Bigl(R\Rightarrow (\neg (P\land Q))\Bigr)\\ &\equiv \neg Q \land \Bigl( R \land \neg(\neg(P\land Q))\Bigr)\\ &\equiv \neg Q \land (R \land (P\land Q))\\ &\equiv \neg Q \land R \land P \land Q\\ &\equiv (\neg Q\land Q) \land R \land P\\ &\equiv (\neg Q\land Q). \end{align*} Since the negation of the proposition is equivalent to a contradiction, the original proposition is a tautology, i.e., true.

  • 0
    Thank you, now I am back on track, with the examples shown in my book2011-03-16