I am studying discrete maths at uni, and i am trying to do some practice tests from the workbook.
One of the questions is:
For each of the following statements, use a truth table to determine whether it is a contradiction,
a tautology or neither. If it is a contradiction or a tautology, verify your answer
using logical equivalences
I have proven using truth tables that it is indeed a tautology, but i am having dificulty proving using logical equiverlences that it is indeed a tautology.
I was just wondering if someone might be able to give me some hints as to what steps i should take?
thanks
Tim
Best Answer
A proposition and its contrapositive are logically equivalent. The contrapositive of $(p \to q)$ is $(\lnot q \to \lnot p)$ and similarly, the contrapositive of $(q \to r)$ is $(\lnot r \to \lnot q)$. Therefore your main proposition can be rewritten as $((\lnot q \to \lnot p) \land (\lnot r \to \lnot q) \land (\lnot r)) \to (\lnot p)$. From there we can see that the left side simplifies to $(\lnot p)$ using the rule of Modus Ponens (refer to the comments below). Now, $(\lnot p) \to (\lnot p)$ is clearly a tautology and so we are done.