5
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ Try to use $\LaTeX$ for better readability. $\endgroup$
    – NasuSama
    Feb 6, 2014 at 2:06

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .