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.

  • $\begingroup$ I am not sure what you are trying to prove. $\endgroup$ – Math1000 Nov 16 '19 at 3:24
  • $\begingroup$ 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. $\endgroup$ – Detrimental Nov 16 '19 at 4:24
  • $\begingroup$ If you read it as $(X or (Y\equiv Z))\equiv((X or Y) \equiv (X or Z))$, it's a tautology $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Detrimental Nov 16 '19 at 11:38
  • 1
    $\begingroup$ @Detrimental Manx simply forgot to copy the $\neg$ in the two previous lines. I fixed it. $\endgroup$ – 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*}


| cite | improve this answer | |
  • $\begingroup$ Thank you very much for the explanation. The proof is very concise as well, cheers! $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.