Welcome to our community

Be a part of something great, join today!

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

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,008
Hey!! :eek:

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)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,687
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

Well-known member
MHB Site Helper
Apr 14, 2013
4,008
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)
 
Last edited:

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,687
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

Well-known member
MHB Site Helper
Apr 14, 2013
4,008
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)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,687
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

Well-known member
MHB Site Helper
Apr 14, 2013
4,008
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)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,687
Yes. (Nod)

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

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,008

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,687
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

Well-known member
MHB Site Helper
Apr 14, 2013
4,008
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)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,687
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

Well-known member
MHB Site Helper
Apr 14, 2013
4,008
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)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,687
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)