# Thread: Prove Boolean Expressions are equivelant

1. ## Prove Boolean Expressions are equivelant

Using the rules of boolean algebra prove (state which rule is used at each step):-

$
\forall x in X[ p(x) \rightarrow \neg ( q(x) \wedge r(x) ) ] \equiv \neg \exists x in X[ p(x) \wedge q(x) \wedge r(x) ]
$

So far I have,

$
\forall x in X[ \neg p(x) \lor \neg (q(x) \wedge r(x)) ] Rewriting \rightarrow.
$

$
\neg \exists x in X[ p(x) \lor \neg (q(x) \wedge r(x) ) ] Extended De Morgan (ii)
$

This is where I hit the brick wall. I've also tried doing the Extended De Morgan rule first but that doesn't seem right to me.

any help appreciated.

2. $p \to \left( {q \wedge r} \right) \equiv \neg p \vee \left( {q \wedge r} \right) \equiv \neg \left( {p \wedge \neg (q \wedge r)} \right)$

3. This has confused me even more??

4. I'm still struggling with this, not sure what rules you have used to get there.

Help appreciated.

5. I still need help with this if anyone can??

6. I guess this is a trickier subject than I thought judging by the replies. Is there anyone out there who can check my final answer to this. I'm submitting it tomorrow.

Step1
------
Rewriting $\rightarrow$

$
\forall x \in X[ \neg p(x) \lor \neg ( q(x) \wedge r(x) ) ]
$

Step2
------
De Morgan (ii)

$
\forall x \in X[ \neg ( p(x) \wedge q(x) \wedge r(x) ) ]
$

Step3
------
Extended De Morgan (ii)

$
\neg \exists x \in X[ p(x) \wedge q(x) \wedge r(x) ]
$

This is the best I can come up with so it will have to do. Looks correct to me anyway