Is this a valid Boolean expression?

Question

a friend of mine asked me to look over some questions he was working on for practice, and I came across the question.

Prove the following Boolean expression:

$(X\lor(Y\leftrightarrow Z))\leftrightarrow((X \lor Y) \leftrightarrow (X \lor Z))$

I can't make head nor tail of it unfortunately, there were some minor typos earlier in the paper so I suspected this was the case, but replacing ($Y\leftrightarrow Z$) in the expression solves nothing, as writing the truth table for $X \lor Y$ and $X \lor Z$ show they are not equivalent regardless. At a loss so any help would be appreciated.

Apologies for not using MathJax, for some reason the logical operators were not converting properly.

Answer 1

It's a tautology, and we can prove it with Logical equivalence:

$$\begin{align} &(X \lor Y) \leftrightarrow (X \lor Z)\\ &\equiv(\neg X \to Y) \leftrightarrow (\neg X \to Z)\tag*{Biconditional equ}\\ &\equiv(\neg X \to Y) \to (\neg X \to Z)\tag*{Apply def.}\\ &\land((\neg X \to Z)\to(\neg X \to Y))\\ &\equiv\neg(X \lor Y) \lor (X \lor Z)\tag*{Conditional equ}\\ &\land(\neg(X \lor Z)\lor(X \lor Y))\\ &\equiv(\neg X \land \neg Y) \lor (X \lor Z)\tag*{De Morgan's law}\\ &\land((\neg X \land \neg Z)\lor(X \lor Y))\\ &\equiv((\neg X \land \neg Y) \lor X) \lor Z)\tag*{Associative law}\\ &\land(((\neg X \land \neg Z)\lor X) \lor Y)\\ &\equiv((\neg X\lor X) \land (\neg Y \lor X)\lor Z)\tag*{Distributive law}\\ &\land(((\neg X\lor X) \land (\neg Z\lor X)) \lor Y)\\ &\equiv(\top \land (\neg Y \lor X)\lor Z)\tag*{Negation law}\\ &\land((\top \land (\neg Z\lor X)) \lor Y)\\ &\equiv(X\lor Z\lor \neg Y)\land(X\lor \neg Z\lor Y)\tag*{Identity law}\\ &\equiv X\lor((Z\lor \neg Y)\land(\neg Z\lor Y))\tag*{Distributive law}\\ &\equiv X\lor((\neg Y\lor Z)\land (\neg Z\lor Y))\tag*{Commutative law}\\ &\equiv X\lor((Y\to Z)\land (Z\to Y))\tag*{Conditional equ}\\ &\equiv X\lor(Y\leftrightarrow Z)\tag*{Apply def.} \end{align}$$

Now let's consider our statement: $$\begin{align} &(X\lor(Y\leftrightarrow Z))\leftrightarrow((X \lor Y) \leftrightarrow (X \lor Z))\\ &\equiv(X\lor(Y\leftrightarrow Z))\leftrightarrow(X\lor(Y\leftrightarrow Z))\tag*{Substitution}\\ &\equiv ((X\lor(Y\leftrightarrow Z))\land (X\lor(Y\leftrightarrow Z)))\tag*{Apply def.}\\ &\lor(\neg(X\lor(Y\leftrightarrow Z))\land\neg(X\lor(Y\leftrightarrow Z)))\\ &\equiv (X\lor(Y\leftrightarrow Z))\lor\neg(X\lor(Y\leftrightarrow Z))\tag*{Identity law}\\ &\equiv\top\tag*{Negation law}\\ \end{align}$$

Hence we proved it's a tautology.

Answer 2

Two-element algebra $\,(\Bbb B\,\,\leftrightarrow\,\,\vee),\, $ where $\,\Bbb B:=(T\,F),\,$ is a commutative ring, where

• $\,T\,$ is the neutral element with respect to $\,\leftrightarrow\, $ (think about $\,T\,$ as zero),
• $\,F\,$ is the neutral element with respect to $\,\vee\,$ (think about $\,F\,$ as one),
• we have the distributive property of $\,\vee\,$ over $\,\leftrightarrow.\, $

This $\,(\Bbb B\,\,\leftrightarrow\,\,\vee)\, $ algebra is isomorphic to $\,(\Bbb Z_2\,+\,\cdot).\,$ Now, it is easy.  Great!

REMARK:   The above OP's expression means distributivity.

Answer 3

Using $(a \leftrightarrow b) = ab + a'b'$, you only need to show

• $\color{blue}{X+ YZ + Y'Z'} = \color{green}{(X+Y)(X+Z) + (X+Y)'(X+Z)'}$

Now, just some Boolean algebra gives

\begin{eqnarray*} \color{green}{(X+Y)(X+Z) + (X+Y)'(X+Z)'} & = & XX + XZ + XY + YZ + (X'Y')(X'Z') \\ & \stackrel{aa = a, a+ab=a}{=} & X + YZ + X'Y'Z' \\ & \stackrel{a+ab=a}{=} & X + XY'Z' + YZ + X'Y'Z' \\ & \stackrel{(a+a')b=b}{=} & \color{blue}{X +YZ + Y'Z'}\\ \end{eqnarray*}

Done.