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

mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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)
 
Physics news on Phys.org
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)
 
Klaas van Aarsen said:
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 by a moderator:
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)
 
Klaas van Aarsen said:
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)
Klaas van Aarsen said:
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)
 
mathmari said:
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$.
mathmari said:
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)
 
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)
 
Yes. (Nod)

Have you considered applying distributivity of $+$ over $\cdot$? (Wondering)
 
Klaas van Aarsen said:
Have you considered applying distributivity of $+$ over $\cdot$? (Wondering)
What do you mean? I got stuck right now. (Wondering)
 
  • #10
mathmari said:
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)
 
  • #11
Klaas van Aarsen said:
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)
 
  • #12
mathmari said:
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)

mathmari said:
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)
 
  • #13
Klaas van Aarsen said:
And the law of identity. And we also used the laws of associativity, didn't we? (Nerd)

Ahh yes! (Nerd)

Klaas van Aarsen said:
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)
 
  • #14
mathmari said:
Using that we don't need the parentheses!

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

mathmari said:
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)
 

Similar threads

Replies
2
Views
2K
Replies
6
Views
2K
Replies
22
Views
3K
Replies
1
Views
1K
Replies
5
Views
2K
Replies
1
Views
1K
Back
Top