Skip to main content
\(\newcommand{\doubler}[1]{2#1} \newcommand{\binary}{\texttt} \newcommand{\hex}{\texttt} \newcommand{\octal}{\texttt} \newcommand{\prog}{\texttt} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section5.1Boolean 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 hardware symbol for the AND gate is shown in Figure 5.1.1. The inputs are \(x\) and \(y\text{.}\) The resulting output, \(x \cdot y\text{,}\) is shown in the truth table in this figure.

<<SVG image is unavailable, or your browser cannot render it>>

\(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}\)
Figure5.1.1The 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 hardware symbol for the OR gate is shown in Figure 5.1.2. The inputs are \(x\) and \(y\text{.}\) The resulting output, \(x \vee y\text{,}\) is shown in the truth table in this figure.

<<SVG image is unavailable, or your browser cannot render it>>

\(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}\)
Figure5.1.2The 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}\text{,}\) or it is \(\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 hardware symbol for the NOT gate is shown in Figure 5.1.3. The input is \(x\text{.}\) The resulting output, \(x'\text{,}\) is shown in the truth table in this figure.

<<SVG image is unavailable, or your browser cannot render it>>

\(x\) \(x'\)
\(\binary{0}\) \(\binary{1}\)
\(\binary{1}\) \(\binary{0}\)
Figure5.1.3The 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
Table5.1.4Precedence rules of Boolean algebra operators.

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, 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{gather} x \cdot (y \cdot z) = (x \cdot y) \cdot z\label{and-ass}\tag{5.1.1}\\ x + (y + z) = (x + y) + z\label{or-ass}\tag{5.1.2} \end{gather}

    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 commutattive:

    \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}\)

Subsection5.1.1Exercises

2

Prove the commutative property expressed by Equation (5.1.5) and Equation (5.1.6).

Solution
6

Prove the distributive property expressed by Equation (5.1.13) and Equation (5.1.14).

Solution