Prove a tautology with contradiction theory and boolean algebra

Question

I am working with tautology in discrete mathematics and I am trying to learn how to prove a tautology using different methods. My book gave me the following task to try, and I would really appreciate some help from more experienced people who could describe this to me?

Based on the statement (not Q) ⇒ (R ⇒ not (P and Q)) How can you show/prove this is a tautology by

1. Contradiction theory

2. How can you use Boolean algebra to show that the statement is equivalent with the tautology (Q or (not Q))

Answer 1

For the second task, you need logical equivalence rules, like e.g. De Morgan's laws and the equivalence between $(p \to q)$ and $(\lnot p \lor q)$ (called: Material implication rule).

---

For the first task, you can show that the formula:

$(\lnot Q) \to (R \to \lnot (P \land Q))$

is a tautology, arguing by contradiction.

I.e. assume not: this means that there is a valuation $v$ such that:

$v(\lnot Q)=$ TRUE and $v((R \to \lnot (P \land Q)))=$ FALSE.

Answer 2

I am not sure what you mean by 'contradiction theory' ... but I am guessing the idea is to show the statement is a tautology by showing that the assumption that it is not leads to a contradiction. So, below I'll show you a semi-formal technique to do something like this; it's known as a 'short truth-table'.

So, let's assume the statement is not a tautology. This means that it should be possible for it to be false. Let's indicate that by putting a False (F) under its main connective:

\begin{array}{ccccccccc} \neg & Q & \rightarrow & (R & \rightarrow & \neg & (P & \land & Q))\\ &&F \end{array}

Now, the only way for a conditional to be false is if the antecedent is true and the consequent is false, so:

\begin{array}{ccccccccc} \neg & Q & \rightarrow & (R & \rightarrow & \neg & (P & \land & Q))\\ T&&F&&F \end{array}

And the same holds for the second conditional:

\begin{array}{ccccccccc} \neg & Q & \rightarrow & (R & \rightarrow & \neg & (P & \land & Q))\\ T&&F&T&F&F \end{array}

For negations we of course flip the truth-value, so this forces:

\begin{array}{ccccccccc} \neg & Q & \rightarrow & (R & \rightarrow & \neg & (P & \land & Q))\\ T&F&F&T&F&F&&T \end{array}

And finally, a true conjunction means both conjuncts are true:

\begin{array}{ccccccccc} \neg & Q & \rightarrow & (R & \rightarrow & \neg & (P & \land & Q))\\ T&F&F&T&F&F&T&T&T \end{array}

But now we see that $Q$ is forced to be both False and True ... which is a contradiction. Hence, out assumptions that the statement is not a tautology is incorrect: it is a tautology.

Now that we're done maybe you can understand why this technique is called a 'short truth-table': the line of truth-values we created looks like one of the lines you may find in a full truth-table ... except of course that this actual line of values would never appear on a truth-table since $Q$ is both true and False. However, if we would have been able to make the statement false without running into such a contradiction, then we would have shown that the statement is not a tautology, and the line we would heave created really would have been one of the lines in a full truth-table. But, we would have found this line much more quickly than if we had done a full truth-table.

Finally, now that you have seen how the method works, you can show the order in which you assign truth-values simply by indexing those truth-values:

\begin{array}{ccccccccc} \neg & Q & \rightarrow & (R & \rightarrow & \neg & (P & \land & Q))\\ T_2&F_6&F_1&T_4&F_3&F_5&T_8&T_7&T_9 \end{array}