Properties and laws of Boolean logic

Boolean operations are essential for mathematics because they're used for proving of different theorems. These operations are also widely applied in Computer Science, since many logical expressions and constructions are used in boolean conditions. Here you'll learn properties of these operations which will help you to simplify logical expressions.

Operation with constant 0 and 1

At first, let's focus on the identity law.

It states that any variable remains unchanged in the operation OR with $0$ or AND with $1$.

$X + 0 = X \\ X\cdot1 = X$

Let's build truth tables of these operations:

So, now it's obvious that the results of these two operations depend only on the value of $X$ and are equal to it.

Here's an example of the identity law. Imagine that while you were solving a coding problem, you wrote a condition for an integer $a$ like the following one:

if a > 0 and (a == a) then
...

Is this condition efficient? Of course not! For any integer number $a = a$ and the second statement is always true. It means that this logical statement can be simplified using the second statement of the identity law: $(a > 0 ) \cdot1 = (a>0)$.

Let's move on to the annulment law.

The result of the AND operation between a variable and $0$ is $0$, while the result of the OR operation with $1$ is $1$.

$X \cdot 0 = 0 \\ X + 1 = 1$

Here are truth tables of these operations:

As you can see, the results don't depend on the value of $X$ and only depend on the value of the second variable: 0 in the first case and 1 in the second.

Here's an example of application of the annulment law. Imagine that you're coding, and you have a condition for an integer variable $a$ like:

if (a/a == 1) or a > 3 then
...

For any integer number $a/a = 1$, so the first statement is always true. So, the whole logical statement is $1 + (a >3)$. The result is always equal to $1$ according to the annulment law. Many programming languages were built using this law, so the value of the second logical statement won't be calculated because its value doesn't affect the result.

Double negation

Now we can focus on the double negation law. This law states that the double negation of an expression is equal to this expression.

$\neg(\neg X) = X$

This law may seem confusing, but if you build the truth table of this operation, everything will become clear.

As you see from the table, the result of this operation is equal to the value of $X$.

Here's also a visual illustration of this law.

Complement and idempotent laws

First, we should define the universal set. It is the set of all elements under consideration. For instance, if you have two sets $A = \{1, 2 ,3\}$ and $B = \{-3, -2, -1 \}$ the universal set $U$ will include all the elements of these two sets: $U =\{-3,-2, -1, 1, 2, 3\}$.

Now we can move on to the complement and idempotent laws. The complement law states that

$X \cdot (\neg X) = 0 \\ X + (\neg X) = 1$

Let's use Venn diagrams to visualize these laws.

You see that there are no elements which belong to the set $X$ and $\neg X$ at the same time and that all elements of these sets together make the universal set.

The idempotent law states that

$X \cdot X = X \\ X + X = X$

Let's once again build the truth table of these operations:

As you see from the table, the result is equal to the value of $X$.

Here's how this law can be applied. Imagine that you have a set $A = \{a, b, c\}$. If you try to find an intersection of $A$ and $A$ you'll get a set with elements which belong to $A$ and $A$ at the same time and this set will be $\{a, b, c\}$, so it is equal to the set $A$. And the same thing will happen if you try to find the union of the set $A$ and $A$.

Commutative law

Let's move on to the commutative law. This law states that changing the sequence of the variables does not have any effect on the result.

$X + Y = Y + X\\X\cdot Y = Y \cdot X$

Here's an example of application of this law.

Any alphabet can be represented as a set. Let $E$ be the English alphabet and $G$ be the German alphabet.

$E = \{ a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z\}\\ G = \{a, ä, b, c, d, e, f,g,h,i,j,k,l,m,n,o, ö,p,q,r,s,ß,t,u, ü,v, w, x, y, z\}$

Let's find the intersection of these sets.

If we begin with the set $E$, we'll try to find every element of this set in the set $G$. Here we won't face any problems and get a new set $E_G = \{ a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z\}$ which represents the intersection of $E$ and $G$. If we begin with the set $G$, we'll try to find every element of this set in the set $E$. We won't be able to find $ä, ö,ß,ü$, so we won't include them into the set which represents the intersection of $G$ and $E$ and we'll get $G_E = \{ a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z\}$. As you can see, $E_G = G_E$. So, the result doesn't change if we change the sequence of the sets.

Complex laws

Now we're ready to focus on more complex laws.

The first law is the distributive law.

This law states that

$X + Y\cdot Z = (X+Y)\cdot(X+Z) \\ X\cdot(Y+Z) =X\cdot Y + X\cdot Z$

Here are Venn diagrams of this law. The first statement looks like this:

And the second statement looks as below:

Let's move on to the associative law.

This law states that

$X+(Y+Z) = (X+Y)+Z\\ X\cdot(Y\cdot Z) = (X\cdot Y) \cdot Z$

Here are some illustrations of this law. The first statement:

And the second one:

And now we can move to the absorptive law.

This law states that

$X\cdot(X+Y) = X \\ X+X\cdot Y = X$

Here are Venn diagrams of this law:

And last but not least, let's focus on de Morgan's laws.

These laws state that

$\neg(X\cdot Y)=(\neg X)+(\neg Y)\\ \neg(X+Y)=(\neg X) \cdot(\neg Y)$

We won't prove these laws. Here's an illustration to help you to understand these laws:

Application of boolean algebra laws

Remember how we discussed the usefulness of boolean laws for simplifying expressions? Let's simplify the following complex expression that your friend ended up with while solving a coding problem.

Given

$(\neg C) + (A\cdot C) +( \neg(C + (\neg B))$

Let's begin with applying the second de Morgan's law and the double negation law to the last term:

$\neg(C + (\neg B)) =( \neg C)\cdot(\neg(\neg B))=(\neg C) \cdot B$

Now we get the following expression:

$(\neg C) + (A\cdot C) + (\neg C)\cdot B$

We can change the sequence of the variables according to the commutative law:

$(\neg C) + (A\cdot C) + (\neg C)\cdot B = (\neg C) + (\neg C)\cdot B+(A\cdot C)$

Now let's apply the second statement of the absorptive law to the first two terms:

$(\neg C) + (\neg C)\cdot B = (\neg C)$

Now we get:

$(\neg C) + (A\cdot C)$

Let's apply the first statement of the distributive law:

$(\neg C) + (A\cdot C) =((\neg C) +A)\cdot((\neg C) +C)$

Now let's apply the second statement of the complement law:

$(\neg C) +C = 1$

So, finally we get according to the second statement of the identity law that:

$((\neg C) +A)\cdot1 = (\neg C) +A$

You see that we've just simplified a big and a little bit terrifying logical expression and got a small and easy to understand logical expression!

Conclusion

Let's sum up all the laws which you've just learned.

The identity law: $X + 0 = X$ and $X\cdot1 = X$

The annulment law: $X \cdot 0 = 0$ and $X + 1 = 1$

The double negation law: $\neg(\neg X) = X$

The complement law: $X \cdot (\neg X) = 0$ and $X + (\neg X) = 1$

The idempotent law: $X \cdot X = X$ and $X + X = X$

The commutative law: $X\cdot Y = Y \cdot X$ and $X + Y = Y + X$

The distributive law:

$X + Y\cdot Z = (X+Y)\cdot(X+Z) \\ X\cdot(Y+Z) =X\cdot Y + X\cdot Z$

The associative law:

$X+(Y+Z) = (X+Y)+Z\\ X\cdot(Y\cdot Z) = (X\cdot Y) \cdot Z$

The absorptive law:

$X\cdot(X+Y) = X \\ X+X\cdot Y = X$

De Morgan's laws:

$\neg(X\cdot Y)=(\neg X)+(\neg Y)\\ \neg(X+Y)=(\neg X) \cdot(\neg Y)$

Now that you know all these rules, it's time to put them into practice!