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


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.


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}


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.