Logic Minimization
Boolean Algebra
Logic Minimization
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} = 1$ | ||
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)$ |
| Truth Table to Verify Distributive Laws | ||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $A$ | $B$ | $C$ | $A+B$ | $B+C$ | $A+C$ | $A\cdot B$ | $B\cdot C$ | $A\cdot C$ | $A\cdot (B+C)$ | $(A\cdot B)+(A\cdot C)$ | $A + (B\cdot C)$ | $(A + B)\cdot (A + C)$ | ||||||||||||||||||||||||||
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||||||||||||||||||||||||||
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||||||||||||||||||||||||||
| 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||||||||||||||||||||||||||
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | ||||||||||||||||||||||||||
| 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | ||||||||||||||||||||||||||
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | ||||||||||||||||||||||||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | ||||||||||||||||||||||||||
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ||||||||||||||||||||||||||
In logic functions, AND'ing operations take precedence over OR'ing operations. Parentheses can be used to eliminate any possible confusion. Thus, the following two sets of equations show equivalent logic equations: \[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 $\overline{A\cdot B} = \overline{A} + \overline{B}$ (NAND form) and $\overline{A+B} = \overline{A}\cdot \overline{B}$ (NOR form).
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: \[\begin{align} 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} \end{align}\]
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. 2 also serve to illustrate the laws of Boolean Algebra.
Use Boolean Algebra to Find Simpler Logic Equations
The following examples in Fig. 3 illustrate the use of Boolean Algebra to find simpler logic equations.
The last two examples on the left (with the blue boxes) shows relationships that are sometimes called the “absorptive” laws, and the example on the right (with the green box) is often called the “consensus” law. The so-called absorptive laws are easily demonstrated with other laws, so it is not necessary or even convenient to use these relationships as laws—particularly because different forms of equations can make it difficult to identify when the law might apply. The consensus law is also easily derived, if the “trick” of AND'ing a '1' into the equation, and then expanding that AND into an OR relationship is used.
Important Ideas
- 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).
- The associative law states that when OR'ing more than two variables, the result is the same regardless of the grouping of those variables.
- Communicative law states that the order in which two variables are OR'ed makes no difference to the outcome.
- The distributive law 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.
- Other product and company names mentioned herein are trademarks or trade names of their respective companies. © 2014 Digilent Inc. All rights reserved.