The term Boolean algebra itself might sound dry and dull, but it is one of the backbones of all the computers we use today. In this article, you will learn what Boolean algebra is and how to use it in Python.
Boolean algebra is named after its inventor George Boole who introduced it in his book The Mathematical Analysis of Logic in 1847. Today Boolean algebra is the foundation of programming languages and digital electronics and is also used in 2D and 3D programs to merge and intersect shapes and bodies.
Basic Boolean Operations
Boolean algebra only knows two values: true and false. Those values are usually abbreviated as t and f or 1 and 0 where 1 represents true and 0 stands for false. As you have seen in Python Course #2 on variables and data types Python has the data type Boolean or bool to represent those two values with True and False. For the introduction to Boolean operations 0 and 1 are used in the remainder of this section.
Conjunction (AND)
The operator for the conjunction operation is AND or this symbol: ∧. The conjunction combines two boolean expressions:
\[x \wedge y\]As \(x\) and \(y\) can only either be 0 or 1 all possible combinations can be written down in a so called truth table:
| \(x\) | \(y\) | \(x \wedge y\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
All combinations of \(x\) and \(y\) are listed in the first two columns of the truth table. In the last column is the result of the operations. You can see that the conjunction or short and is only true if and only if both \(x\) and \(y\) are true in all other cases, it will evaluate to false. The operator for and in Python is and. You can reproduce this truth table in the Python interactive mode with the following statements:
1
2
3
4
False and False
False and True
True and False
True and True
which will only result in True for the last statement, True and True. Instead of using the values True and False, you can also use bool variables.
Disjunction (OR)
The next operation is the disjunction with its operator OR and the symbol: ∨. In the same way as the conjunction the disjunction combines two expressions:
\[x \vee y\]However, the operation evaluates to 1 when atleast one of the variables is 1:
| \(x\) | \(y\) | \(x \wedge y\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
The only way to get the disjunction to result in 0 is when both expressions \(x\) and \(y\) are 0. The OR operator in Python is or. You can also reproduct the truth table in the Python interactive mode with the following statements:
1
2
3
4
False or False
False or True
True or False
True or True
Negation (NOT)
The last operation of the Boolean algebra is the negation and the NOT operator and its symbol: ¬. The negation only takes one operator:
\[\neg x\]When using the NOT operator 0 turns into 1 and 1 turns into 0:
| \(y\) | \(\neg x\) |
|---|---|
| 0 | 1 |
| 1 | 0 |
In Python the negation is represented by the not operator, which you can use like this:
1
2
not True
not False
Combining Operators
You can form any logic expression by only using the three operators AND, OR, and NOT. For example, an often-used operator is the exclusive OR (also called disambiguation). XOR takes two boolean expressions:
\[x \oplus y\]and evaluates to 1 if and only if \(x\) and \(y\) are different. The truth table for XOR looks like this:
| \(x\) | \(y\) | \(x \oplus y\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
And it can be constructed in different ways like this one:
\[x \oplus y = (x \vee y) \wedge \neg(x \wedge y)\]You can check that the equation is correct by evaluating it step-by-step, starting with evaluating the parenthesis using another truth table. The first two columns represent \(x\) and \(y\) the next two represent \(x \vee y\) and \(\neg(x \vee y)\). Lastly, take the results from the last two columns and use the AND operator to combine them and compare the last column to \(x \oplus y\).
| \(x\) | \(y\) | \(x \vee y\) | \(\neg(x \wedge y)\) | \((x \vee y) \wedge \neg(x \vee y)\) | \(x \oplus y\) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 |
As you can see the two last columns are identical and therefore the equation \(x \oplus y = (x \vee y) \wedge \neg(x \vee y)\) is correct. Sadly, Python does not provide an XOR operator. However, you can construct one by using and, or, and not:
1
2
3
4
5
if __name__ == "__main__":
x = True
y = False
z = (x or y) and not (x and y)
print(z)
The parathesis is needed because Python respects the operator evaluation order (or precedence) whereas not is evaluated before and which is evaluated before or. A full list of the Python operator precedence can be found in the official Python docs: 6.17 Operator precedence
Truth tables are an easy way to check a small Boolean algebra expression quickly. However, the more variables you introduce, the more rows you will get. The number of rows you need to cover every possible variable assignment grows exponentially, and after 2020 and 2021, we all know the power of exponential growth. When you got \(n\) variables, you will need \(2^n\) rows to cover all possible variable assignments.
Boolean Algebra Laws
But you don’t have to rely on truth tables to check the equality of two expressions. Boolean algebra has, such as the “normal” algebra, laws that allow you to rearrange Boolean terms. All those laws can be proven with truth tables and then used to rearrange, reduce, and expand boolean expressions.
Annulment Law
An AND operation where one side is 0 will always evaluate to 0:
\[x \wedge 0 = 0\]An OR operation where one side is 1 will always evaluate to 1:
\[x \vee 1 = 1\]Identity Law
An AND operation where one side is 1 will always evaluate to the other side (here \(x\)):
\[x \wedge 1 = x\]An OR operation where one side is 0 will always evaluate to the other side (here \(x\)):
\[x \vee 0 = x\]Idempotent Law
If the same expression is on both sides of an AND or an OR operation, the operation can be reduced to the expression itself:
\[x \wedge x = x\] \[x \vee x = x\]Complement Law
An expressions that is combined with its complement (the expression negated) in an AND operation will always evaluate to 0:
\[x \wedge \neg x = 0\]An expression that is combined with its complement (the expression negated) in an OR operation will always evaluate to 1:
\[x \vee \neg x = 1\]Double Negation
Two negate operations cancel each other out:
\[\neg (\neg x) = x\]Commutative Law
Changing the order of AND and OR does not change the result:
\[x \wedge y = y \wedge x\] \[x \vee y = y \vee x\]Associative Law
Rearranging the parenthesis in an expressions that only include AND or OR does not change the result:
\[(x \wedge y) \wedge z = x \wedge (y \wedge z)\] \[(x \vee y) \vee z = x \vee (y \vee z)\]Absorption Law
Complex expressions can be reduced to simpler ones when the following forms are given:
\[x \wedge (x \vee y) = x\] \[x \vee (x \wedge y) = x\]Distributive Law
Allows for multiplying and factoring out expressions:
\[x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z)\] \[x \vee (y \wedge z) = (x \vee y) \wedge (x \vee z)\]De Morgan’ Law
AND and OR can be exchanged for one another when the negation of it is either applied to the whole parathesis or the single terms:
\[\neg (x \vee y) = \neg x \wedge \neg y\] \[\neg (x \wedge y) = \neg x \vee \neg y\]Using Boolean Algebra Laws
Above XOR is defined as:
\[x \oplus y = (x \vee y ) \wedge \neg ( x \wedge y)\]However, XOR can also be expressed as:
\[x \oplus y = (x \wedge \neg y) \vee (\neg x \wedge y)\]And to show those definitions are equal, you can either write a python program and check all four assignments of \(x\) and \(y\):
1
2
3
4
5
6
7
8
9
if __name__ == "__main__":
x = True
y = False
z0 = (x or y) and not (x and y)
z1 = (x and not y) or (not x and y)
print(x, "xor", y)
print(z0)
print(z1)
Or you can use the Boolena algebra laws to show this equality:
\[\begin{eqnarray} & (x \vee y ) \wedge \neg ( x \wedge y) & \quad\text{distributive law: } a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c) \\ = & (\neg (x \wedge y ) \wedge x) \vee ( \neg (x \wedge y) \wedge y) & \quad\text{De Morgan's law: } \neg (a \wedge b) = \neg a \vee \neg b \\ = & ((\neg x \vee \neg y ) \wedge x) \vee ( \neg x \vee \neg y ) \wedge y) & \quad\text{distributive law} \\ = & ((\neg x \wedge x) \vee (x \wedge y)) \vee ((\neg x \wedge y) \vee (y \wedge \neg y)) & \quad\text{complement law: } a \wedge \neg a = 0\\ = & (0 \vee (x \wedge y)) \vee ((\neg x \wedge y) \vee 0) & \quad\text{identity law: } a \vee 0 = a\\ = & (x \wedge \neg y) \vee (\neg x \wedge y) & \quad\blacksquare \end{eqnarray}\]Trying out all variable assignments is often much easier to show equality. However, the “brute force” method will take much longer than an algebraic approach when you get more variables. And especially exponential growth is hazardous. Throughout this Python course, you will see many examples that show you that thinking about solutions is more important than writing code. A clever solution can save you time and, therefore, money. I encourage you to check the equality of the following expression using Python and the Boolean laws to get used to Boolean algebra:
\[(x \wedge (\neg y \wedge (z \vee (y \wedge \neg z)))) \vee \neg z = (x \wedge \neg y) \vee \neg z\]This concludes this article on Boolean algebra. You have learned about the Boolean Operations AND, OR, NOT, XOR and how to use them in Python. You have also seen how to use truth tables and learned about the laws of Boolean algebra and how to use them to prove the equality of Boolean expressions. If you have any questions about this article, feel free to join our Discord community to ask them over there.