# Is this a valid Boolean expression?

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.

• I am not sure what you are trying to prove. – Math1000 Nov 16 '19 at 3:24
• This is an issue I'm having. I read the question as prove that X OR (Y≡Z) is equivalent to X OR Y which is equivalent to X OR Z. I'm not sure X OR (Y≡Z) is even valid Boolean, but even if so X OR Y !≡ X OR Z . So the question as written to my best knowledge is either unreadable as Boolean algebra, or is false, which makes it unprovable. I am leaning towards their being a typo at this point but wanted to share here to see if I am just interpreting the expression incorrectly. The question on paper is as I described here, I'd like to link a picture but my reputation is not high enough yet. – Detrimental Nov 16 '19 at 4:24
• If you read it as $(X or (Y\equiv Z))\equiv((X or Y) \equiv (X or Z))$, it's a tautology – Manx Nov 16 '19 at 4:39

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.

• Thanks you for taking the time to answer, I knew I must have been interpreting the expression wrong. I just had a quick question about the use of the identity law in line 15. I would of thought that $( \top \land (X \lor Y) \lor Z)$ would simplify to $(X \lor Y \lor Z)$ but instead it simplifies to $(X \lor Y' \lor Z)$ . How does the $Y$become a $Y'$? Thanks again for your time. – Detrimental Nov 16 '19 at 11:38
• @Detrimental Manx simply forgot to copy the $\neg$ in the two previous lines. I fixed it. – Bram28 Nov 16 '19 at 16:50

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.

• Thank you very much for the explanation. The proof is very concise as well, cheers! – Detrimental Nov 16 '19 at 11:42

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 easyGreat!

REMARK:   The above OP's expression means distributivity.