properties of semantic equivalence proof

Question

I would like to prove using semantic equivalences that

(p ⇒ q) ∧ (¬q ⇒  r) ≡ (r ⇒ p) ⇒ q

but I keep getting stuck at the same point. Can someone please tell me where I go wrong?

(implication)

(¬p v q) ∧ (¬q ⇒  r)

(implication)

(¬p v q) ∧ (¬¬q v r)

(double negation)

(¬p v q) ∧ (q v r)

(commutativity)

(q v ¬p) ∧ (q v r) 

(distributivity)

q v (¬p ∧ r)

(commutivity)

q v (r ∧ ¬p)

(commutativity)

(r ∧ ¬p) v q

(implication)

(r ∧ ¬p) ⇒ q

and then CompilerSaysNo pulls hair out?

Please help.

Thank you in advance.

Answer 1

After your last invocation of commutatitivity, you have

$$(r \land ¬p) \lor q$$

Then you invoked implication, but forgot to negate the $(r \land \lnot p)$. So everything up to and including the second-to-last line is fine!

Using the definition of implication:

$$(r\land \lnot p) \lor q \equiv \lnot(r \land \lnot p)\rightarrow q$$

Using DeMorgan's

$$\equiv (\lnot r \lor \lnot \lnot p) \rightarrow q$$

By double negation, that gives us:

$$\equiv (\lnot r \lor p) \rightarrow q$$

Using the definition of implication, that gives us

$$\equiv (r\rightarrow p) \rightarrow q$$ as desired.

Answer 2

You're almost there! You have

\begin{equation*}\begin{aligned}(r\wedge \neg p)\vee q &\equiv (\neg\neg r\wedge\neg p)\vee q\\ &\equiv \neg(\neg r\vee p)\vee q\\ &\equiv (\neg r\vee p)\to q\\ &\equiv (r\to p)\to q\end{aligned}\end{equation*}