1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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*}

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.