# Boolean Algebra

## Boolean Algebra: Basic Operations

Boolean algebra is perhaps the oldest method used to minimize logic equations. It provides a formal algebraic system to manipulate logic equations so that the minimum can be found. A basic understanding of this system is indispensable to the study and analysis of logic circuits.

Boolean algebra is a proper algebraic system, with three set elements {‘0’, ‘1’, and ‘A’} (where ‘A’ is any variable that can assume the values ‘0’ or ‘1’), two binary operations (AND or intersection, OR or union), and one unary operation (inversion or complementation). Operations between sets are closed under the three operations. The basic laws governing and, or, and inversion operations are easily derived from the logic truth tables for those operations.

AND Operations OR Operations INV Operations
Truth Table Laws Truth Table Laws Truth Table Laws
$0 \cdot 0 = 0$ $A \cdot 0 = 0$ $0 + 0 = 0$ $A + 0 = A$ $\overline 0 = 1$ $\overline{\overline A} = A$
$0 \cdot 1 = 0$ $A \cdot 1 = A$ $0 + 1 = 1$ $A + 1 = 1$ $\overline 1 = 0$
$1 \cdot 0 = 0$ $A \cdot A = A$ $1 + 0 = 1$ $A + A = A$
$1 \cdot 1 = 1$ $A \cdot \overline A = 0$ $1 + 1 = 1$ $A + \overline A = A$
Table 1. And, OR, and INV Operations

## Associative, Commutative, and Distributive Laws

The associative, commutative, and distributive laws can be directly demonstrated using truth tables. Only the distributive law truth table is shown in the truth table below, with colors used to highlight the columns that show the equivalency of both sides of the distributive law equations. Truth tables to demonstrate the simpler associative and commutative laws are not shown, but they can be easily derived.

The associative law states that when OR’ing more than two variables, the result is the same regardless of the grouping of those variables. Similarly, the communicative law states that the order in which two variables are OR’ed makes no difference to the outcome. The distributive law as shown in the truth table below states that OR’ing two or more variables and then AND’ing the result with a single variable is equivalent to AND’ing the single variable with each of the two or more variables and then OR’ing the products.

Associative Laws Commutative Laws Distributive Laws
$(A\cdot B)\cdot C = A\cdot (B\cdot C) = A\cdot B\cdot C$ $A\cdot B\cdot C = B\cdot A\cdot C = \cdots$ $A\cdot (B+C) = (A\cdot B) + (A\cdot C)$
$(A + B) + C = A + (B + C) = A + B + C$ $A + B + C = B + A + C = \cdots$ $A + (B\cdot C) = (A + B) \cdot (A + C)$
Table 2. Associative, Commutative, and Distributive Laws

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

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

## DeMorgan’s Law

DeMorgan’s Law provides a formal algebraic statement for the property observed in defining the conjugate gate symbols: the same logic circuit can be interpreted as implementing either an AND or an OR function, depending how the input and output voltage levels are interpreted. DeMorgan’s law, which is applicable to logic systems with any number of inputs, states

NAND Form: $\overline{A \cdot B} = \overline A + \overline B$

NOR Form: $\overline{A+B} = \overline A \cdot \overline B$

## Laws for XOR and XNOR

The laws of Boolean algebra generally hold for XOR functions as well, except that DeMorgan’s law takes a different form. Recall from a previous background topic that the XOR function output is asserted whenever an odd number of inputs are asserted, and that the XNOR function output is asserted whenever an even number of inputs are asserted. Thus, inverting a single input to an XOR function, or inverting its output, yields the XNOR function. Likewise, inverting a single input to an XNOR function, or inverting its output, yields the XOR function. Inverting an input together with the output, or inverting two inputs, changes an XOR function to XNOR, and vice-versa. These observations lead to a version of DeMorgan’s Laws that hold for XOR functions of any number of inputs:

$F = \overline{A \oplus B \oplus C} \iff F = \overline A \oplus B \oplus C$ $\iff F= \overline A \oplus \overline B \oplus \overline C$

$F=A \oplus B \oplus C \iff$ $F = \overline{A \oplus \overline B \oplus C} \iff$ $F=\overline A \oplus \overline B \oplus C$

Note that a single input inversion can be moved to any other signal in a multi-input XOR circuit without changing the logical result. Note also that any signal inversion can be replaced with a non-inverted signal and an XNOR function. These properties will be useful in later work.

## Circuit Illustration for Boolean Algebra

The circuits below in Fig. 3 also serve to illustrate the laws of Boolean Algebra.

## Use Boolean Algebra to Find Simpler Logic Equations

The following examples in Fig. 4 illustrate the use of Boolean Algebra to find simpler logic equations.