Prove or disprove $x∧(¬y↔z)\leftrightarrow ((x→y)∨ ¬z)→(x∧ ¬(y→z))$ using logical equivalence

Question

Here is what I have so far:

L.H.S.

$x \wedge (\neg y \leftrightarrow z) \equiv x \wedge (( \neg y \to z) \wedge (z \to \neg y)) \equiv x \wedge (( \neg (\neg y) \vee z) \wedge (\neg z \vee \neg y)) \equiv (x \wedge(y \vee z)) \wedge (x \wedge ( \neg z \vee \neg y)) \equiv (( x \wedge y) \vee (x \wedge z)) \wedge ((x \wedge \neg z) \vee (x \wedge \neg y))$

R.H.S

$((x \to y) \vee \neg z) \to (x \wedge \neg (y \to z)) \equiv \neg ((\neg x \vee y) \vee \neg z) \vee (x \wedge \neg ( \neg y \vee z)) \equiv (( x \wedge \neg y) \wedge z ) \vee (x \wedge (y \wedge \neg z)) \equiv ((x \wedge z) \wedge (\neg y \wedge z)) \vee (( x \wedge y) \wedge (x \wedge \neg z))$

I see that $(x \wedge y), (x \wedge z), (x \wedge \neg z)$ exist in both of the final statements, however, the only difference is between $(x \wedge \neg y)$ on the L.H.S. and $(\neg \wedge z)$ on the R.H.S. There is also a difference in the unions and intersections.

Could someone please help put me in the right direction or suggest another approach on how to prove/disprove this? Thank you.

Answer 1

From your work, by the distributive property, the L.H.S. is $$( x \wedge y) \land (x \wedge \neg z) \vee ( x \wedge z)\wedge (x \wedge \neg z) \vee ( x \wedge y) \land (x \wedge \neg y) \vee ( x \wedge z)\wedge (x \wedge \neg y)$$ that is (recall that $a\wedge a\equiv a$, and $a\wedge \lnot a\equiv F$), $$( x \wedge y \wedge \neg z)\vee F\vee F\vee (x \wedge \neg y\wedge z)$$ which becomes $$( x \wedge y \wedge \neg z)\vee (x \wedge \neg y\wedge z).$$ Now we compare the above expression with the R. H. S. $$((x \wedge z) \wedge (\neg y \wedge z)) \vee (( x \wedge y) \wedge (x \wedge \neg z))\equiv (x \wedge z \wedge \neg y) \vee ( x \wedge y \wedge \neg z)$$ and we find that they are equivalent.

Answer 2

You did:

L.H.S.

$x \wedge (\neg y \leftrightarrow z) \equiv x \wedge (( \neg y \to z) \wedge (z \to \neg y)) \equiv x \wedge (( \neg (\neg y) \vee z) \wedge (\neg z \vee \neg y)) \equiv (x \wedge(y \vee z)) \wedge (x \wedge ( \neg z \vee \neg y)) \equiv (( x \wedge y) \vee (x \wedge z)) \wedge ((x \wedge \neg z) \vee (x \wedge \neg y))$

R.H.S

$((x \to y) \vee \neg z) \to (x \wedge \neg (y \to z)) \equiv \neg ((\neg x \vee y) \vee \neg z) \vee (x \wedge \neg ( \neg y \vee z)) \equiv (( x \wedge \neg y) \wedge z ) \vee (x \wedge (y \wedge \neg z)) \equiv ((x \wedge z) \wedge (\neg y \wedge z)) \vee (( x \wedge y) \wedge (x \wedge \neg z))$

But instead of taking the last two steps for the L.H.S, you could have continued with a Distribution on the right conjunct:

$x \wedge (( \neg (\neg y) \vee z) \wedge (\neg z \vee \neg y)) \equiv x \wedge (( y \vee z) \wedge (\neg z \vee \neg y)) \equiv x \land ((y \land \neg z) \lor (z \land \neg z) \lor (y \land \neg y) \lor (z \land \neg y)) \equiv x \land ((y \land \neg z) \lor \bot \lor \bot \lor (z \land \neg y)) \equiv x \land ((y \land \neg z) \lor (z \land \neg y)) \equiv (x \land y \land \neg z) \lor (x \land z \land \neg y))$

And for the R.H.S, starting with the second to last result:

$(( x \wedge \neg y) \wedge z ) \vee (x \wedge (y \wedge \neg z)) \equiv ( x \wedge \neg y \wedge z ) \vee (x \wedge y \wedge \neg z)) $

And now you see that they are the same, modulo some trivial Commutations

The moral is: sometimes you can save some work by not Distributing all the way through.

I also want to note that by rewriting the biconditional as two conditionals, you effectively end up with:

$p \leftrightarrow q \equiv (\neg p \lor q) \land (\neg q \lor p)$

However, another useful equivalence principle with the biconditional is:

$p \leftrightarrow q \equiv (p \land q) \lor (\neg p \land \neg q)$

Of course, you can go between these two equivalence using Distribution, but again, to save some work, you can strategically pick one over the other. And, noticing the $x \land \neg (z \to y)$ term in the R.H.S ... which we quickly realize is equivalent to $x \land z \land \neg y$, I would definitely have picked the other biconditional equivalence. Indeed, that equivalence would have made short work of this problem:

L.H.S

$x \wedge (\neg y \leftrightarrow z) \equiv x \land ((\neg y \land z) \lor (y \land \neg z)) \equiv (x \land \neg y \land z) \lor (x \land y \land \neg z))$

R.H.S

$((x \to y) \vee \neg z) \to (x \wedge \neg (y \to z)) \equiv (\neg x \lor y \lor \neg z) \to (x \wedge y \land \neg z)) \equiv \neg (x \land \neg y \land z) \to (x \wedge y \land \neg z)) \equiv (x \land \neg y \land z) \lor (x \wedge y \land \neg z))$

Cool!