Two-element Boolean algebra: How are the equalities derived?

[mathmari]

Hey!

We have the following equalities:
\begin{align*}\left (\overline{y}\land z\lor x\land \left (\overline{z}\lor y\right )\right )\land \left (\overline{x}\lor \overline{y}\right )& \overset{(1)}{=}\left (\overline{y}\land z\lor x\land \overline{z}\lor x\land y\right )\land \left (\overline{x}\lor \overline{y}\right ) \\ & \overset{(2)}{=}\left (\overline{y}\land z\lor x\land \overline{z}\right )\land \left (\overline{x}\lor \overline{y}\right ) \\ & \overset{(3)}{=}\left (\overline{y}\land \left (z\lor x\land \overline{z}\right )\lor y\land x\land \overline{z}\right )\land \left (\overline{x}\lor \overline{y}\right ) \\ & \overset{(4)}{=}\overline{y}\land \left (x\lor z\right )\land \left (\overline{x}\lor \overline{y}\right )\lor y\land x\land \overline{z}\land \left (\overline{x}\lor \overline{y}\right )\\ & \overset{(5)}{=}\overline{y}\land \left (x\lor z\right ) \lor \overline{\overline{y}\lor \overline{x}}\land \overline{z}\land \left (\overline{x}\lor \overline{y}\right ) \\ & \overset{(6)}{=}\overline{y}\land \left (x\lor z\right )\end{align*}

I want to justify at each step which transformations have been done. First of all, $\left (\overline{y}\land z\lor x\land \left (\overline{z}\lor y\right )\right )\land \left (\overline{x}\lor \overline{y}\right )$ is equivalent to $\left (\overline{y}\land z \lor \left [x\land \left (\overline{z}\lor y\right )\right ]\right )\land \left (\overline{x}\lor \overline{y}\right )$, or not? Then applying the distributive law we get $\left (\overline{y}\land z \lor \left [\left (x\land \overline{z}\right )\lor \left (x\land y\right )\right ]\right )\land \left (\overline{x}\lor \overline{y}\right )$. ow we can eliminat the parentheses and we get $\left (\overline{y}\land z\lor x\land \overline{z}\lor x\land y\right )\land \left (\overline{x}\lor \overline{y}\right ) $ and so the first step is justified.

Is everything correct so far? (Wondering)

How do we continue? How do we get to step $(2)$, i.e. why can we eliminate the term $x\land y$ ? (Wondering)

 

[I like Serena]

Hey mathmari!

Your first step is correct. (Nod)

If you don't mind I'll first write it in a way that looks a bit more intuitive to me. (Blush)

In the first step we have:
$$\big(\bar y z + x(\bar z+y)\big)(\bar x + \bar y)
\overset{(1)}=(\bar y z + x\bar z+xy)(\bar x + \bar y)
$$
We can apply the distributive law again can't we?
That is:
$$(\bar y z + x\bar z+xy)(\bar x + \bar y)
= (\bar y z + x\bar z)(\bar x + \bar y)+xy(\bar x + \bar y)
$$
It puts those $x$ and $y$ more or less together with their negations.

What can we do with $xy(\bar x + \bar y)$? (Wondering)

 

[mathmari]

In the first step we have:
$$\big(\bar y z + x(\bar z+y)\big)(\bar x + \bar y)
\overset{(1)}=(\bar y z + x\bar z+xy)(\bar x + \bar y)
$$
We can apply the distributive law again can't we?
That is:
$$(\bar y z + x\bar z+xy)(\bar x + \bar y)
= (\bar y z + x\bar z)(\bar x + \bar y)+xy(\bar x + \bar y)
$$
It puts those $x$ and $y$ more or less together with their negations.

What can we do with $xy(\bar x + \bar y)$? (Wondering)

We have that $$xy(\bar x + \bar y)=xy\bar x + xy\bar y=x\bar x y + xy\bar y$$ It holds that $x\bar x=y\bar y=0$, or not? Therefore, we get $x\bar x y + xy\bar y=0 y + x0=0+0=0$, or not? (Wondering)

That means that $$(\bar y z + x\bar z+xy)(\bar x + \bar y)
= (\bar y z + x\bar z)(\bar x + \bar y)+xy(\bar x + \bar y)
=(\bar y z + x\bar z)(\bar x + \bar y) $$

Is everything correct so far? (Wondering) Could you give me also a hint for $(3)$ ? How have we extended the term? (Wondering)

 

[I like Serena]

All correct.
We didn't explicitly mention the transformation rules we used though. Shouldn't we? (Wondering)

In step (3) we want to justify that:
$$(\bar y z+x\bar z)(\bar x+\bar y)\overset ?= \big(\bar y(z+x\bar z)+yx\bar z\big)(\bar x+\bar y)$$

Suppose we start from the right side?
That is, what can we do with $\bar y(z+x\bar z)+yx\bar z$ ? (Wondering)

 

[mathmari]

We didn't explicitly mention the transformation rules we used though. Shouldn't we? (Wondering)

Ah yes! We applied twice the distributive law and so we got $$(\bar y z + x\bar z+xy)(\bar x + \bar y)
= (\bar y z + x\bar z)(\bar x + \bar y)+xy(\bar x + \bar y)=(\bar y z + x\bar z)(\bar x + \bar y)+xy\bar x + xy\bar y$$
Then we applied the commutative law and we got $$(\bar y z + x\bar z)(\bar x + \bar y)+x\bar x y + xy\bar y$$ Then we used the fact that $x\bar x=y\bar y=0$, is this a law? Something related to the complement? (Wondering)

In step (3) we want to justify that:
$$(\bar y z+x\bar z)(\bar x+\bar y)\overset ?= \big(\bar y(z+x\bar z)+yx\bar z\big)(\bar x+\bar y)$$

Suppose we start from the right side?
That is, what can we do with $\bar y(z+x\bar z)+yx\bar z$ ? (Wondering)

We have that $$\bar y(z+x\bar z)+yx\bar z=\bar yz+\bar yx\bar z+yx\bar z=\bar yz+x\bar z(\bar y+y)$$ It holds that $\bar y+y=1$, or not? Therefore, we get that the relation is equal to $$\bar yz+x\bar z(\bar y+y)=\bar yz+x\bar z 1=\bar yz+x\bar z$$
Is everything correct? (Wondering)

When we want to describe which transformations we applied can we do that although we looked now the relations from right to left? (Wondering)

 

[I like Serena]

Ah yes! We applied twice the distributive law and so we got $$(\bar y z + x\bar z+xy)(\bar x + \bar y)
= (\bar y z + x\bar z)(\bar x + \bar y)+xy(\bar x + \bar y)=(\bar y z + x\bar z)(\bar x + \bar y)+xy\bar x + xy\bar y$$
Then we applied the commutative law and we got $$(\bar y z + x\bar z)(\bar x + \bar y)+x\bar x y + xy\bar y$$ Then we used the fact that $x\bar x=y\bar y=0$, is this a law? Something related to the complement? (Wondering)

It depends on which set of transformations we want to use. Does your course material list them?
If this is not given in your material, I think we can use these: Laws of a Boolean Algebra.

And yes, in this case we have indeed the Law of Complementation for $x\bar x=0$.

We have that $$\bar y(z+x\bar z)+yx\bar z=\bar yz+\bar yx\bar z+yx\bar z=\bar yz+x\bar z(\bar y+y)$$ It holds that $\bar y+y=1$, or not? Therefore, we get that the relation is equal to $$\bar yz+x\bar z(\bar y+y)=\bar yz+x\bar z 1=\bar yz+x\bar z$$
Is everything correct?
When we want to describe which transformations we applied can we do that although we looked now the relations from right to left?

All correct. (Happy)

For equalities it does not matter if we go from left to right or the other way.
However, to make it easy for other people to follow, we can write it down in the opposite direction, and specify the transformations we used in that direction.
After all, it was only a hint how we can figure out what we need to do. (Nerd)

 

[mathmari]

I got it so far! (Nerd)

Let's see equation $(4)$.

After the equation $(3)$ we have $$(\bar y(z+x\bar z)+yx\bar z)(\bar x+\bar y)$$ At equation $(4)$ we get $$\bar y(x+z)(\bar x+\bar y)+yx\bar z(\bar x+\bar y)=\left (\bar y(x+z)+yx\bar z\right )(\bar x+\bar y)$$ right? (Wondering)

Therefore to explain the equation $(4)$ we have to explain why $z+x\bar z=x+z$, or not? (Wondering)

 

[I like Serena]

Yes. (Nod)

Have you considered applying distributivity of $+$ over $\cdot$? (Wondering)

 

[mathmari]

Have you considered applying distributivity of $+$ over $\cdot$? (Wondering)

What do you mean? I got stuck right now. (Wondering)

 

[I like Serena]

What do you mean? I got stuck right now.

Normally we consider distributivity to mean $a(b+c)=ab+ac$.
But in boolean algebras we also have $a+bc=(a+b)(a+c)$. (Thinking)

 

[mathmari]

Normally we consider distributivity to mean $a(b+c)=ab+ac$.
But in boolean algebras we also have $a+bc=(a+b)(a+c)$. (Thinking)

Ahh ok! Using that we get the following:
\begin{align*}\left (\overline{y} \left (z+ x \overline{z}\right )+ y x \overline{z}\right ) \left (\overline{x}+ \overline{y}\right ) &= \left (\overline{y} \left [\left (z+ x\right ) \left (z+ \bar z\right )\right ]+ y x \overline{z}\right ) \left (\overline{x}+ \overline{y}\right )\\ & =\left (\overline{y} \left [\left (z+ x\right ) 1\right ]+ y x \overline{z}\right ) \left (\overline{x}+ \overline{y}\right )\\ & =\left (\overline{y} \left (z+ x\right )+ y x \overline{z}\right ) \left (\overline{x}+ \overline{y}\right ) \\ & =\left [\overline{y} \left (z+ x\right ) \left (\overline{x}+ \overline{y}\right )\right ]+ \left [y x \overline{z} \left (\overline{x}+ \overline{y}\right )\right ] \\ & =\overline{y} \left (z+ x\right ) \left (\overline{x}+ \overline{y}\right )+ y x \overline{z} \left (\overline{x}+\overline{y}\right ) \end{align*}

Therefore we used the distributive law and the law of complementation, didn't we?As for the equality $(5)$ :

Do we apply the De Morgan's Law and get $y x=\overline{\overline{y}+ \overline{x}}$ and so we get the following? $$\overline{y} \left (x+ z\right )\left (\overline{x}+ \overline{y}\right )+ y x \overline{z} \left (\overline{x}+ \overline{y}\right ) =\overline{y}\left (x+ z\right ) \left (\overline{x}+ \overline{y}\right )+ \overline{\overline{y}+ \overline{x}} \overline{z} \left (\overline{x}+ \overline{y}\right ) $$

Then applying the distributive law we get $$\left (\overline{y} \left (x+ z\right )+ \overline{\overline{y}+\overline{x}} \overline{z} \right )\left (\overline{x}+ \overline{y}\right )$$

Is everything correct? But shouldn't we get the expression without the parentheses? (Wondering)

 

[I like Serena]

Ahh ok! Using that we get the following:
\begin{align*}\left (\overline{y} \left (z+ x \overline{z}\right )+ y x \overline{z}\right ) \left (\overline{x}+ \overline{y}\right ) &= \left (\overline{y} \left [\left (z+ x\right ) \left (z+ \bar z\right )\right ]+ y x \overline{z}\right ) \left (\overline{x}+ \overline{y}\right )\\ & =\left (\overline{y} \left [\left (z+ x\right ) 1\right ]+ y x \overline{z}\right ) \left (\overline{x}+ \overline{y}\right )\\ & =\left (\overline{y} \left (z+ x\right )+ y x \overline{z}\right ) \left (\overline{x}+ \overline{y}\right ) \\ & =\left [\overline{y} \left (z+ x\right ) \left (\overline{x}+ \overline{y}\right )\right ]+ \left [y x \overline{z} \left (\overline{x}+ \overline{y}\right )\right ] \\ & =\overline{y} \left (z+ x\right ) \left (\overline{x}+ \overline{y}\right )+ y x \overline{z} \left (\overline{x}+\overline{y}\right ) \end{align*}

Therefore we used the distributive law and the law of complementation, didn't we?

And the law of identity. And we also used the laws of associativity, didn't we? (Nerd)

As for the equality $(5)$ :

Do we apply the De Morgan's Law and get $y x=\overline{\overline{y}+ \overline{x}}$ and so we get the following? $$\overline{y} \left (x+ z\right )\left (\overline{x}+ \overline{y}\right )+ y x \overline{z} \left (\overline{x}+ \overline{y}\right ) =\overline{y}\left (x+ z\right ) \left (\overline{x}+ \overline{y}\right )+ \overline{\overline{y}+ \overline{x}} \overline{z} \left (\overline{x}+ \overline{y}\right ) $$

Then applying the distributive law we get $$\left (\overline{y} \left (x+ z\right )+ \overline{\overline{y}+\overline{x}} \overline{z} \right )\left (\overline{x}+ \overline{y}\right )$$

Is everything correct? But shouldn't we get the expression without the parentheses? (Wondering)

It's correct all right.

Perhaps we need to prove that
$$\bar y(x+z)(\bar x + \bar y) \overset?= \bar y(x+z)$$
(Wondering)

 

[mathmari]

And the law of identity. And we also used the laws of associativity, didn't we? (Nerd)

Ahh yes! (Nerd)

It's correct all right.

Perhaps we need to prove that
$$\bar y(x+z)(\bar x + \bar y) \overset?= \bar y(x+z)$$
(Wondering)

Using that we don't need the parentheses! Let's look now the equation $(6)$ :

Using the commutative law we get
\begin{align*}\overline{y}\left (x+ z\right )+ \overline{\overline{y}+ \overline{x}} \overline{z} \left (\overline{x}+\overline{y}\right ) &=\overline{y} \left (x+ z\right ) + \overline{z} \overline{\overline{x}+ \overline{y}} \left (\overline{x}+\overline{y}\right ) \\ & = \overline{y} \left (x+ z\right ) + \overline{z} \left [\overline{\overline{x}+\overline{y}} \left (\overline{x}+ \overline{y}\right )\right ]\end{align*}

Using then the complementary law, the annihilator and the identity for $\land$ we get
\begin{equation*}\overline{y}\left (x+z\right ) + \overline{z} 0=\overline{y} \left (x+z\right ) +0=\overline{y} \left (x+ z\right ) \end{equation*}

And so we have justified also the equation $(6)$, right? (Wondering)

 

[I like Serena]

Using that we don't need the parentheses!

Indeed! (Happy)
If we can prove it though.

Let's look now the equation $(6)$ :

Using the commutative law we get
\begin{align*}\overline{y}\left (x+ z\right )+ \overline{\overline{y}+ \overline{x}} \overline{z} \left (\overline{x}+\overline{y}\right ) &=\overline{y} \left (x+ z\right ) + \overline{z} \overline{\overline{x}+ \overline{y}} \left (\overline{x}+\overline{y}\right ) \\ & = \overline{y} \left (x+ z\right ) + \overline{z} \left [\overline{\overline{x}+\overline{y}} \left (\overline{x}+ \overline{y}\right )\right ]\end{align*}

Using then the complementary law, the annihilator and the identity for $\land$ we get
\begin{equation*}\overline{y}\left (x+z\right ) + \overline{z} 0=\overline{y} \left (x+z\right ) +0=\overline{y} \left (x+ z\right ) \end{equation*}

And so we have justified also the equation $(6)$, right?

Yes.
It's the identity for $\lor$ though, isn't it? (Wondering)