Using Logical Equivalences to prove $(((\neg r) \lor q) \lor ((q \lor (\neg p)) \land ((\neg p) \lor q)))$ is equivalent to $(\neg(r \land p) \lor q)$

Question

I have been trying to solve the following proof:

$$(((\neg r) \lor q) \lor ((q \lor (\neg p)) \land ((\neg p) \lor q)))\text{ is equivalent to } (\neg(r \land p) \lor q)$$

I am new to proofs and logical equivalences but so far I have tried:

1: the commutative law.

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

2: the Idempotent law

$$((\neg r) \lor q) \lor (r \lor (\neg q))$$

I don't know where to go from here, any suggestions?

Answer 1

I suggest we begin by showing that $$(q \vee \neg p) \wedge (\neg p \vee q) = q \vee \neg p$$ which requires only the commutativity of $\vee$ and the idempotence of $\wedge$.

After that, it follows that $$\big(\neg r \vee q\big) \vee \big((q \vee \neg p) \wedge (\neg p \vee q)\big) = (\neg r \vee q) \vee (q \vee \neg p)$$ which simplifies to $$\neg r \vee q \vee \neg p$$ which is equivalent to the desired $$\neg (r \wedge p) \vee q$$ using commutativity of $\wedge$ and de Morgan's Law.

Answer 2

Firstly, by pushing in the negation on the right hand side:

~(r ^ p) v q = ~r v ~p v q

Then by A^A = A and commutativity of disjunction:

(~r v q) v (q v ~p)
~r v q v q v ~p

Now by A v A = A

 ~r v q v ~p

Done.