How do I prove that $\lnot(q \rightarrow (p \rightarrow q)) \not\equiv p$ using logical equivalences?

Question

I was able to prove that $\lnot(q \rightarrow (p \rightarrow q)) \not\equiv p$ using truth tables, but when it comes to propositional equivalences, I'm a little stuck. Do I need to show that the left hand side contradicts the right hand side? Any help is appreciated!

Answer 1

We use that $$\lnot ( a \rightarrow b ) = a \land \lnot b$$

Using this we get:
$$\lnot(q \rightarrow (p \rightarrow q)) = q \land \lnot (p \rightarrow q) = q \land ( p \land \lnot q) = $$

$$q \land p \land \lnot q = q \land \lnot q \land p = false \land p = false$$

So the proposition $(q \rightarrow (p \rightarrow q))$ is a tautology i.e. something which is always $true$

And the given proposition $\lnot (q \rightarrow (p \rightarrow q))$ is always $false$
i.e. it is a contradiction (because it is the negation of a tautology).

Answer 2

Two propositions are logically equivalent if they are both true or both false.

Let $$R : q \rightarrow (p \rightarrow q)$$

If $ q $ is false, then $ R $ will be true no matter what $ p $ is. So, if $ p $ and $ q $ are true, $ \lnot R$ is false. we conclude that $ p $ and $ \lnot R $ are not equivalent.

Answer 3

We say that $A ≡ B$ iff $A,B$ have the same truth-value for every truth-assignment (i.e. no matter what truth-values the propositional atoms have). So $A ≢ B$ iff $A,B$ have different truth-value for some truth-assignment. Such statements cannot be proven using propositional equivalences! For example, $p ≢ p∧q$, but we can prove neither $p ⇔ p∧q$ nor $¬( p ⇔ p∧q )$, because they are each neither a tautology nor a contradiction.

The only way to prove this kind of statement is therefore by finding some truth-assignment that differentiates the truth-values of the two expressions. As you noted, a truth-table is one way to do that. You can first simplify each expression via equivalences such as peter.petrov showed, but you eventually still need to find a truth-assignment to finish.

Hence the implicit assumption in your question that you can prove the desired claim using merely propositional equivalences is incorrect, because propositional equivalences only allow you to prove equivalences (i.e. "≡") and nothing else. To prove anything else, you have to step beyond boolean algebra.