Section 5.1 Boolean Algebra Operations
There are only two values, \(\binary{0}\) and \(\binary{1}\text{,}\) unlike elementary algebra that deals with an infinity of values, the real numbers. Since there are only two values, a truth table is a very useful tool for working with Boolean algebra. A truth table lists all possible combinations of the variables in the problem. The resulting value of the Boolean operation(s) for each variable combination is shown on the respective row.
Elementary algebra has four operations, addition, subtraction, multiplication, and division, but Boolean algebra has only three operations:
- AND
-
A binary operator; the result is \(\binary{1}\) if and only if both operands are \(\binary{1}\text{,}\) otherwise the result is \(\binary{0}\text{.}\) We will use ‘\(\cdot\)’ to designate the AND operation. It is also common to use the ‘\(\wedge\)’ symbol or simply “AND.” The AND gate operation is shown in Figure 5.1.1 with inputs \(x\) and \(y\text{.}\)
\(x\) \(y\) \(x \cdot y\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{1}\) \(\binary{0}\) \(\binary{1}\) \(\binary{0}\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) Figure 5.1.1. The AND gate acting on two variables, \(x\) and \(y\text{.}\) We can see from the truth table that the AND operator follows similar rules as multiplication in elementary algebra.
- OR
-
A binary operator; the result is \(\binary{1}\) if at least one of the two operands are \(\binary{1}\text{,}\) otherwise the result is \(\binary{0}\text{.}\) We will use ‘\(+\)’ to designate the OR operation. It is also common to use the ‘\(\vee\)’ symbol or simply “OR.” The OR gate operation is shown in Figure 5.1.2 with inputs \(x\) and \(y\text{.}\)
\(x\) \(y\) \(x + y\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) Figure 5.1.2. The OR gate acting on two variables, \(x\) and \(y\text{.}\) From the truth table we can see that the OR operator follows the same rules as addition in elementary algebra except that \(\binary{1} + \binary{1} = \binary{1}\) in Boolean algebra. Unlike elementary algebra, there is no carry from the OR operation. Since addition of integers can produce a carry, you will see in Section 7.1 that implementing addition requires more than a simple OR gate.
- NOT
-
A unary operator; the result is \(\binary{1}\) if the operand is \(\binary{0}\) or \(\binary{0}\) if the operand is \(\binary{1}\text{.}\) Other names for the NOT operation are complement and invert. We will use \(x'\) to designate the NOT operation. It is also common to use \(\neg x\) or \(\overline{x}\text{.}\) The NOT gate operation is shown in Figure 5.1.3 with input \(x\text{.}\)
\(x\) \(x'\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\binary{0}\) Figure 5.1.3. NOT gate acting on one variable, \(x\text{.}\) The NOT operation has no analog in elementary algebra. Be careful to notice that inversion of a value in elementary algebra is a division operation, which does not exist in Boolean algebra.
Two-state variables can be combined into expressions with these three operators in the same way that you would use the C/C++ operators &&, ||, and ! to create logical expressions commonly used to control if and while statements. When used in expressions, the operators are applied according to the precedence rules in Table 5.1.4. As with elementary algebra, expressions in parentheses are evaluated first, following the precedence rules.
| Operation | Symbol | Precedence |
| NOT | \('\) | Highest |
| AND | \(\cdot\) | Middle |
| OR | \(+\) | Lowest |
We now examine some Boolean algebra properties for manipulating Boolean expressions. As you read through this material, keep in mind that the same techniques can be applied to logical expressions in programming languages.
These properties are commonly presented as theorems. They are easily proved from application of truth tables.
There is a duality between the AND and OR operators. In any equality you can interchange AND and OR along with the constants \(0\) and \(1\text{,}\) and the equality still holds. Thus the properties will be presented in pairs that illustrate their duality. We first consider properties that are the same as in elementary algebra.
-
AND and OR are associative:
\begin{equation} x \cdot (y \cdot z) = (x \cdot y) \cdot z\label{and-ass}\tag{5.1.1} \end{equation}\begin{equation} x + (y + z) = (x + y) + z\label{or-ass}\tag{5.1.2} \end{equation}For Equation (5.1.1):
\(x\) \(y\) \(z\) \((y \cdot z)\) \((x \cdot y)\) \(x \cdot (y \cdot z)\) \(=\) \((x \cdot y) \cdot z\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{1}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\) \(\binary{0}\) \(\binary{0}\) \(\binary{1}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\) \(\binary{0}\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{0}\) \(\binary{0}\) \(\) \(\binary{0}\) \(\binary{1}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\) \(\binary{0}\) \(\binary{1}\) \(\binary{0}\) \(\binary{1}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\binary{0}\) \(\binary{0}\) \(\binary{1}\) \(\binary{0}\) \(\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\) \(\binary{1}\) And for Equation (5.1.2):
\(x\) \(y\) \(z\) \((y + z)\) \((x + y)\) \(x + (y + z)\) \(=\) \((x + y) + z\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\binary{0}\) \(\binary{1}\) \(\) \(\binary{1}\) \(\binary{0}\) \(\binary{1}\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\) \(\binary{1}\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\) \(\binary{1}\) \(\binary{1}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\) \(\binary{1}\) \(\binary{1}\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\) \(\binary{1}\) -
AND and OR each have an identity value:
\begin{gather} x \cdot 1 = x\label{eq-identand}\tag{5.1.3}\\ x + 0 = x\label{eq-identor}\tag{5.1.4} \end{gather} -
AND and OR are commutative:
\begin{gather} x \cdot y = y \cdot x\label{eq-comand}\tag{5.1.5}\\ x + y = y + x\label{eq-comor}\tag{5.1.6} \end{gather}This is easily proved by looking at the second and third rows of the respective truth tables (Figure 5.1.1 and Figure 5.1.2. In elementary algebra, only the addition and multiplication operators are commutative.
So far, Boolean AND seems to behave like multiplication and OR like addition in elementary algebra. Let us consider properties where Boolean algebra differs from elementary algebra.
-
AND and OR each have an annulment value:
\begin{gather} x \cdot 0 = 0\label{eq-nuland}\tag{5.1.7}\\ x + 1 = 1\label{eq-nulor}\tag{5.1.8} \end{gather}The annulment value for the AND is the same as multiplication in elementary algebra. But addition in elementary algebra does not have an annulment value, while OR in Boolean algebra does.
-
AND and OR each have a complement value:
\begin{gather} x \cdot x' = 0\label{eq-compand}\tag{5.1.9}\\ x + x' = 1\label{eq-compor}\tag{5.1.10} \end{gather}Complement does not exist in elementary algebra.
-
AND and OR are idempotent:
\begin{gather} x \cdot x = x\label{eq-idemand}\tag{5.1.11}\\ x + x = x\label{eq-idemor}\tag{5.1.12} \end{gather}That is, repeated application of either operator to the same value does not change it. This differs considerably from elementary algebra—repeated application of addition is equivalent to multiplication and repeated application of multiplication is the power operation.
-
AND and OR are distributive:
\begin{gather} x \cdot (y + z) = x \cdot y + x \cdot z\label{eq-distand}\tag{5.1.13}\\ x + y \cdot z = (x + y) \cdot (x + z)\label{eq-distor}\tag{5.1.14} \end{gather}Going from right to left in Equation (5.1.13) is the very familiar factoring from addition and multiplication in elementary algebra. On the other hand, the operation in Equation (5.1.14) has no analog in elementary algebra. It follows from the idempotency property.
-
NOT shows involution:
\begin{gather} (x')' = x\label{eq-inv}\tag{5.1.15} \end{gather}This is easily seen in Figure 5.1.3. Again, there is no complement in elementary algebra.
-
DeMorgan's Law is an important expression of the duality between the AND and OR operations:
\begin{gather} (x \cdot y)' = x' + y'\label{eq-dmi}\tag{5.1.16}\\ (x + y)' = x' \cdot y'\label{eq-dmii}\tag{5.1.17} \end{gather}The validity of DeMorgan's Law can be seen in the following truth tables.
For Equation (5.1.16):
\(x\) \(y\) \((x \cdot y)\) \((x \cdot y)'\) \(x'\) \(y'\) \(x' + y'\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{0}\) \(\binary{1}\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\binary{0}\) \(\binary{0}\) \(\binary{1}\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) And for Equation (5.1.17):
\(x\) \(y\) \((x + y)\) \((x + y)'\) \(x'\) \(y'\) \(x' \cdot y'\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\binary{0}\) \(\binary{1}\) \(\binary{0}\) \(\binary{0}\) \(\binary{1}\) \(\binary{0}\) \(\binary{1}\) \(\binary{0}\) \(\binary{0}\) \(\binary{1}\) \(\binary{0}\) \(\binary{1}\) \(\binary{1}\) \(\binary{1}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\) \(\binary{0}\)