1

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)$?

Arturo Magidin
  • 398,050

1 Answers1

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.

Arturo Magidin
  • 398,050
  • 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. –  Mar 16 '11 at 04: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. –  Mar 16 '11 at 04:12
  • @Learningbyasking: I'm sorry, but I do not understand what you are asking in this comment. – Arturo Magidin Mar 16 '11 at 04: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?

     –  Mar 16 '11 at 04:25
  • @Learningbyasking: Are you asking how one would prove it is true by contradiction? – Arturo Magidin Mar 16 '11 at 04:27
  • Yes, Since I have allready prooven by truth table that its a tautology. So want to give an example by contradiction. –  Mar 16 '11 at 04:31
  • @Learningbyasking: Done. – Arturo Magidin Mar 16 '11 at 04:33
  • 1
    Arturo, the implication is commonly used with Boolean algebras as an added operator. Your interpretation is correct. – Asaf Karagila Mar 16 '11 at 04:38
  • Thank you, now I am back on track, with the examples shown in my book –  Mar 16 '11 at 04:50