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

• MHB
• mathmari
In summary: Yes, you can still describe the transformations used in step (3) even if you worked from right to left. You can mention that you applied the distributive law twice and used the fact that $\bar y + y = 1$. In this case, it doesn't matter in which direction you write the transformations as long as you correctly describe the steps taken. (Smile) In summary, we have a series of equalities that show the simplification of the given expression. We first applied the distributive law to eliminate parentheses and then used the commutative law to rearrange terms. We also used the fact that $x\bar x = y\bar y = 0$. Finally, we applied the distributive law
mathmari
Gold Member
MHB
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)

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)

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)

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)

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)

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)

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)

1. What is Two-element Boolean algebra?

Two-element Boolean algebra is a mathematical system that consists of two elements, typically represented as 0 and 1, and follows a set of rules for logical operations such as AND, OR, and NOT. It is the simplest form of Boolean algebra and is often used in computer science and digital electronics.

2. How are the equalities derived in Two-element Boolean algebra?

The equalities in Two-element Boolean algebra are derived using the associative, commutative, and distributive properties, as well as the identities and complement laws. These laws allow for manipulation of logical expressions to simplify and prove equalities.

3. What are the basic operations in Two-element Boolean algebra?

The basic operations in Two-element Boolean algebra are AND, OR, and NOT. These operations follow specific rules and truth tables to determine the resulting value of a logical expression.

4. How is Two-element Boolean algebra used in real-world applications?

Two-element Boolean algebra is used in various real-world applications, such as digital circuit design, computer programming, and database systems. It allows for the representation and manipulation of logical statements, which is essential in these fields.

5. What are the benefits of using Two-element Boolean algebra?

Two-element Boolean algebra provides a simple and efficient way to represent and manipulate logical statements. It allows for the simplification of complex expressions and the determination of logical equivalences, which are crucial in various fields such as computer science and engineering.

• Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
• Introductory Physics Homework Help
Replies
7
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
26
Views
3K
• Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
10
Views
3K