Boolean Algebra

What is Boolean Algebra?

Boolean algebra is the study of what happens when logic operations (AND, OR, NOT) are used on Boolean values (either true or false).

Boolean algebra helps us understand how computers and digital electronics work, and how to simplify logic expressions.

Check out our page about logical operators to see how logic operations AND, OR, and NOT are used in programming.

Different Representations of Boolean Algebra

Boolean algebra can be expressed in different ways, depending on the context.

Below are how the logic operations AND, OR, and NOT can be represented in math, and in programming:

Most of this page is dedicated to Boolean algebra as math, but there are some programming examples in between, and an explanation of logic gates further down.

See our page about logical operators to see more about how these operators are programmed.

AND, OR, and NOT

Before we start looking at Boolean algebra, we need to be sure how the AND, OR, and NOT operations work.

AND takes two Boolean values. The result is only true if both values are true, otherwise it is false.

OR takes two Boolean values, and is true if at least one of the values is true, otherwise it is false.

NOT takes one Boolean value, and makes it the opposite. If the value is false, the NOT operation on that value will return true, and if the value is true, the NOT operation on that value will return false.

Doing the NOT operation "NOT A", we often say "the complement of A", "A bar" (written as \(\overline{A}\)), "A negated", "A prime" (written as \(A'\)), or simply "NOT A".

Writing Boolean Algebra

These are the components used to write Boolean algebra:

• true is written as \(1\)
• false is written as \(0\)
• AND is written using multiplication symbol (\(\cdot\))
• OR is written using addition symbol (\(+\))
• NOT is written using overline (\(\overline{A}\))

AND, OR, and NOT can also be written using symbols \(\wedge\), \(\vee\), and \(\neg\), but we will use the symbols stated in the list above.

Basic Boolean Algebra Examples

Calculating true AND false using Boolean algebra looks like this:

\[1 \cdot 0 = 0 \]

The calculation tells us: "true ANDed with false is false".

Doing the same AND operation using programming looks like this:

print(True and False)

console.log(true && false);

System.out.println(true && false);

cout << (true && false);

The calculation "NOT true", using overline, looks like this:

\[ \overline{1} = 0 \]

The calculation tells us: "NOT true results in false".

Using OR looks like this:

\[ 1 + 0 = 1 \]

The calculation tells us: "true ORed with false is true".

Can you guess this one?

\[ 1 + 1 = \text{ ?} \]

The answer will hopefully not upset you, because remember: we are not doing normal math here. We are doing Boolean algebra.

We get

\[ 1 + 1 = 1 \]

Which just means that "true ORed with true results in true".

The Order of Operations

Like there are rules for what operations we do first in normal math, there is also an order of operations for Boolean algebra.

Before going on to more complex Boolean algebra, we need to know the order of operations.

1. Parentheses
2. NOT
3. AND
4. OR

For example, in this expression:

\[ 1 + 0 \cdot 0 \]

The correct order is to do AND first, so \(0 \cdot 0\), the initial expression is reduced to:

\[ 1 + 0 \]

Which is \(1\) (true).

So solving the expression in the correct order:

\[ \begin{aligned} 1 + 0 \cdot 0 &= 1 + 0 \\[8pt] &= 1 \end{aligned} \]

Solving this expression with the wrong order, doing OR before AND, would result in \(0\) (false) as the answer, so keeping to the correct order of operations is important.

Boolean Algebra with Variables

After establishing the basic concepts of Boolean algebra, we can finally start seeing more useful and interesting results.

Boolean variables are usually written in uppercase, like \(A\), \(B\), \(C\), etc.

We need to think about a Boolean variable as unknown, but it is either true or false.

Below are some basic Boolean algebra results we get, using variables:

\[ \begin{aligned} A + 0 &= A \\[8pt] A + 1 &= 1 \\[8pt] A + A &= A \\[8pt] A + \overline{A} &= 1 \\[8pt] A \cdot 0 &= 0 \\[8pt] A \cdot 1 &= A \\[8pt] A \cdot A &= A \\[8pt] A \cdot \overline{A} &= 0 \\[8pt] \overline{\overline{A}} &= A \\[8pt] \end{aligned} \]

The results above are simple, but important. You should go through them one by one and make sure you understand them. (You can replace variable \(A\) with \(1\), see if it's correct, and then replace \(A\) with \(0\), and see if it's still correct.)

Simplifying Code Using Boolean Algebra

The rules above can be used to simplify code.

Let's look at a code example, where a condition is checked to see if a person can borrow a book from the university library.

if is_student and (age < 18 or age >= 18):
  print("You can borrow a book from the university library")

if (is_student && (age < 18 || age >= 18)) {
  console.log("You can borrow a book from the university library");
}

if (is_student && (age < 18 || age >= 18)) {
  System.out.println("You can borrow a book from the university library");
}

if (is_student && (age < 18 || age >= 18)) {
  cout << "You can borrow a book from the university library";
}

The condition in the if statement above

\[ is\_student \text{ AND } (age \lt 18 \text{ OR } age \geq 18) \]

can be written using Boolean algebra, like this:

\[ is\_student \cdot (under18 + \overline{under18}) \]

Or:

\[ A \cdot (B + \overline{B}) \]

From the list of Boolean algebra results above, we see that

\[B + \overline{B} = 1\]

(We know this rule from the list of Boolean algebra results in the previous section.)

So the condition in the if statement can be simplified:

\[ \begin{aligned} &is\_student \cdot (under18 + \overline{under18}) \\[8pt] &= is\_student \cdot (1) \\[8pt] &= is\_student \end{aligned} \]

The result is that we don't have to check the age at all to see if the person can borrow a book from the university library, we just need to check if they are a student.

The condition is simplified:

if is_student:
  print("You can borrow a book from the university library")

if (is_student) {
  console.log("You can borrow a book from the university library");
}

if (is_student) {
  System.out.println("You can borrow a book from the university library");
}

if (is_student) {
  cout << "You can borrow a book from the university library";
}

So checking the student ID is enough, no need to check their age to see if they are allowed to borrow a book.

You might be able to see how the condition can be simplified without the use of Boolean algebra, but in more complex expressions, Boolean algebra can be very useful.

Boolean Algebra Laws

In addition to the basic Boolean algebra laws listed in the previous section, we also have more complex laws.

The commutative law just shows us that the order of the variables does not matter.

\[ A \cdot B = B \cdot A \]

\[ A + B = B + A \]

The distributive law tells us that we can distribute the AND operation over the OR operation.

\[ A \cdot (B + C) = A \cdot B + A \cdot C \]

\[ A + B \cdot C = (A + B) \cdot (A + C) \]

The first law above is quite straightforward and similar to the distributive law in normal algebra.

But the second law aboveis not that obvious, so let's see how we can arrive at the same result, starting with the right hand side:

\[ \begin{aligned} &(A + B) \cdot (A + C) \\[8pt] &= A \cdot A + A \cdot C + B \cdot A + B \cdot C \\[8pt] &= A + A \cdot C + A \cdot B + B \cdot C \\[8pt] &= A \cdot (1 + C + B) + B \cdot C \\[8pt] &= A \cdot 1 + B \cdot C \\[8pt] &= A + B \cdot C \end{aligned} \]

The associative law tells us that we can group the variables in different ways, without changing the result.

\[ (A \cdot B) \cdot C = A \cdot (B \cdot C) \]

\[ (A + B) + C = A + (B + C) \]

De Morgan's Laws

De Morgan's laws are two widely used and recognized laws in Boolean algebra.

The word complement is used in Boolean algebra meaning the opposite, to negate something, or using the NOT operator. The complement of \(A\) is written as \(\overline{A}\).

Below is an an example of how a condition can be re-written and work exactly the same way, using De Morgan's first law.

Let's say a tank in a production process is safe if both the temperature and pressure in it are below certain limits.

\[ tmp < 100 \text{ AND } press < 20 = \text{Safe} \]

In the oposite case, the tank is not safe, and we should sound the alarm.

\[ \overline{tmp < 100 \text{ AND } press < 20} = \text{Alarm} \]

Using De Morgan's first law, we can rewrite the expression:

\[ \begin{aligned} &\overline{tmp < 100 \text{ AND } press < 20} \\[8pt] &= \overline{tmp < 100} \text{ OR } \overline{press < 20} \\[8pt] &= tmp ≥ 100 \text{ OR } press ≥ 20 \end{aligned} \]

The result we have arrived at here is both easier to understand, and to program, and since we've used De Morgan's first law correctly, we can be sure that the condition will work the same way as the original.

For example, if you say "I do not have dogs or cats"

\[ \overline{haveDogs + haveCats} \]

You might as well say "I do not have dogs and I do not have cats"

\[ \overline{haveDogs} \cdot \overline{haveCats} \]

Those two statements are the same, and they follow De Morgan's second law.

Simplifying a Complex Expression Using Boolean Algebra

Imagine a security system with sensors to detect open windows and doors, and sensors for motion detection.

• open window \(W\)
• open door \(D\)
• motion detected in kitcken \(M_K\)
• motion detected in living room \(M_L\)

These are all the different conditions, or scenarios, that should trigger the alarm:

• Motion detected in living room AND window is open (\(M_L \cdot W\))
• Motion detected in living room AND door is open (\(M_L \cdot D\))
• Motion detected in kitchen AND window is open (\(M_K \cdot W\))
• Motion detected in kitchen AND door is open (\(M_K \cdot D\))

Using Boolean algebra, when this expression is true, the alarm will sound:

Perhaps you see how this could be simplified right away? But even if you do see it, how can you be sure that the simiplified expression works the same way as the original?

Let's use Boolean algebra to simplify the expression:

Using Boolean algebra, we have simplified the expression.

The alarm will sound if motion is detected in the living room or kitchen, if at the same time the window or door is open.

Logic Gates

A logic gate is an electronic device made of transistors that implements a logical operation (Boolean function) AND, OR, or NOT. Other common logic gates are NAND, NOR, XOR, and XNOR.

Try the simulation below to see for yourself how the different logic gates work.

Click on inputs A and B below to toggle them between 0 and 1, and click on the gate to cycle through the different logic gates.

Logic gates are used everywhere in computers and electronic devices: headsets, cars, mobile phones, SSD, RAM, CPU, etc.

Below is an overview of the most common logic gates.

The logic gates for AND, OR, and NOT are the basic logic gates, and works just like described in the previous sections.

The logic gates for NAND and NOR are just the opposite of AND and OR, so they will not be described any further here.

But the logic gates for XOR and XNOR are a bit more special.

The XOR gate checks if the inputs are different \(A \neq B\), and outputs 1 if they are. XOR is like the running A != B in programming.

The XNOR gate checks if the inputs are equal \(A = B\), and outputs 1 if they are. XNOR is like the running A == B in programming.

The truth tables for XOR and XNOR look like this: