I'm currently working on some tautology questions as a brush up for a discrete mathematics course and I'm having a bit of trouble remembering tautology. Precisely, how do I prove certain statements are tautologies, without using truth tables? I've had luck with a couple but right now I'm stumped on the following :
Without doing a truth table, determine whether there are truth values of p, q, r
for which the logical statement
[p ∧ (p → q) ∧ r] → [(p ∨ q) → r]
is false.
Not using truth tables for a question such as this one seems almost impossible to me at the moment. Any help is appreciated in finding out how to navigate my way through this question.
Best Answer
To falsify the logical statement, you need the "if" part to be true, and the "then" part to be false.
"If part is true" means that:
1. $p$ is true, and
2. $p\to q$ is true, and
3. $r$ is true
"then" part is false means that:
4. $p\vee q$ is true, and
5. $r$ is false.
But conditions $3$ and $5$ can't both hold, since $r$ can only be one or the other.
Hence, the logical statement can not be falsified, so it must be true, for all values of $p,q,r$.