# How do I show a statement is a tautology in the Booleans algebra

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 Answer

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.

-
Yes that P and Q are bollean variables! If we then say P is the value of 0 and Q is the value of 1, is it possible to define this in a table as the same prinsiple like the truthtable. – user8322 Mar 16 '11 at 4:12
Yes that P and Q are bollean variables! If we then say P is the value of 0 and Q is the value of 1, is it possible to define this in a table as the same prinsiple like the truthtable. – user8322 Mar 16 '11 at 4:12
@Learningbyasking: I'm sorry, but I do not understand what you are asking in this comment. – Arturo Magidin Mar 16 '11 at 4:16
My mistake, I confused this with something else. If we now should take the statement: (not Q => (R => not (P and Q)) and show it by proof of contradiction. How is this done, my teaching book show a quite difficult example where I understand only the fist part of the Example. Do you have any good books that you also advice me to read? – user8322 Mar 16 '11 at 4:25
Arturo, the implication is commonly used with Boolean algebras as an added operator. Your interpretation is correct. – Asaf Karagila Mar 16 '11 at 4:38