3

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.

Johnathan Scott
  • 333

2 Answers2

4

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$.

vadim123
  • 82,796
1

$(p\wedge (p\rightarrow q) \wedge r)=(p\wedge q\wedge r)$, because $((p\wedge (p\rightarrow q))\rightarrow q$.

$p\wedge q\wedge r$ of course implies $(q\lor p)\rightarrow r$. Thus there are no $p, q, r$ for which the statement is false.

Dasherman
  • 4,206