0

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.

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

3 Answers3

2

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.

trancelocation
  • 32,243
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.

Bram28
  • 100,612
  • 6
  • 70
  • 118
Ethan
  • 5,291
  • 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
  • 1
    @Detrimental Manx simply forgot to copy the $\neg$ in the two previous lines. I fixed it. – Bram28 Nov 16 '19 at 16:50
0

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.

Wlod AA
  • 2,124