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)$?
How do I show a statement is a tautology in the Booleans algebra
1 Answers
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.
-
0Yes 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. – 2011-03-16
-
0Yes 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. – 2011-03-16
-
0@Learningbyasking: I'm sorry, but I do not understand what you are asking in this comment. – 2011-03-16
-
0My 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? – 2011-03-16
-
0@Learningbyasking: Are you asking how one would prove it is true by contradiction? – 2011-03-16
-
0Yes, Since I have allready prooven by truth table that its a tautology. So want to give an example by contradiction. – 2011-03-16
-
0@Learningbyasking: Done. – 2011-03-16
-
1Arturo, the implication is commonly used with Boolean algebras as an added operator. Your interpretation is correct. – 2011-03-16
-
0Thank you, now I am back on track, with the examples shown in my book – 2011-03-16