Boolean algebra

Section 7.2 Boolean algebra

The analysis of digital circuits and their behaviors can be conducted in two ways: 1) the method of exhaustion, and 2) Boolean algebra. The method of exhaustion is a brute-force method in which each gate in a circuit is evaluated in turn based on the inputs values it receives. We used this method in the previous section as we were evaluating circuits constructed solely with NAND gates. Boolean algebra is a mathematical formalism used for two-state variables and the operations that act on these variables. This formalism allows us to analyze circuits containing multiple gates through equation manipulation.

🔗

Boolean algebra, like standard algebra, is governed by rules that determine how mathematical operations interact. The following Boolean identities provide these rules by which we must adhere.

List 7.2.1. Boolean identities

🔗

\(\displaystyle A+B = B+A\)

🔗
\(\displaystyle A \cdot B = B \cdot A\)

🔗
\(\displaystyle A+(B+C) = (A+B) + C\)

🔗
\(\displaystyle A\cdot(B\cdot C) = (A\cdot B)\cdot C \)

🔗
\(\displaystyle A\cdot(B+C) = A\cdot B + A\cdot C \)

🔗
\(\displaystyle (A+B)\cdot(C+D) = A\cdot C + A\cdot D + B\cdot C + B\cdot D \)

🔗
\(\displaystyle \overline{1}=0 \)

🔗
\(\displaystyle \overline{0}=1 \)

🔗
\(\displaystyle A\cdot 0 = 0 \)

🔗
\(\displaystyle A\cdot 1 = A \)

🔗
\(\displaystyle A + 0 = A \)

🔗
\(\displaystyle A + 1 = 1 \)

🔗
\(\displaystyle A + A = A \)

🔗
\(\displaystyle A \cdot A = A \)

🔗
\(\displaystyle \overline{\overline{A}} = A \)

🔗
\(\displaystyle A + \overline{A} = 1 \)

🔗
\(\displaystyle A \cdot \overline{A} = 0 \)

🔗
\(\displaystyle \overline{A + B} = \overline{A} \cdot \overline{B} \)

🔗
\(\displaystyle \overline{A\cdot B} = \overline{A} + \overline{B} \)

🔗
\(\displaystyle A + \overline{A}\cdot B = A+B \)

🔗
\(\displaystyle \overline{A}+A\cdot B = \overline{A} + B \)

🔗
\(\displaystyle A \oplus B = \overline{A}\cdot B + A\cdot\overline{B} = (A+B)\cdot(\overline{A\cdot B}) \)

🔗
\(\displaystyle \overline{A\oplus B} = A\cdot B + \overline{A}\cdot\overline{B} \)

🔗

🔗

Let’s look at a few examples demonstrating the use of Boolean algebra.

🔗

Example 7.2.2. Boolean algebra: NOT gate from NAND gates.

Use Boolean algebra to build a NOT gate from one NAND gate.

🔗

Answer.

We want the result \(\overline{A}\) for input \(A\) using only NAND gates. Starting with our desired result, we find that

\begin{equation*} \overline{A} = \overline{A\cdot A}\qquad \text{(Identity 14)}\text{.} \end{equation*}

So, NOT-gate functionality can be produced using the circuit in Figure 7.1.4.

🔗

Example 7.2.3. Boolean algebra: AND gate from NAND gates.

Use Boolean algebra to make an AND gate from two NAND gates.

🔗

Answer.

We want the result \(A\cdot B\text{.}\) Starting with our desired result, we find that

\begin{align*} A\cdot B \amp = \overline{\overline{A\cdot B}} \amp \text{(identity 15)\ } \\ \amp = \overline{\left(\overline{A\cdot B}\right)\cdot \left(\overline{A\cdot B}\right)} \amp \text{(identity 14)} \text{.} \end{align*}

So, AND-gate functionality can be produced using the circuit in Figure 7.1.6.

🔗

Example 7.2.4. Boolean algebra: OR gate from NAND gates.

Use Boolean algebra to make an OR gate from three NAND gates.

🔗

Answer.

We want the result \(A+B\) and want expressions containing AND-like functions instead of OR-like functions. DeMorgan’s theorems (identities 18 and 19) are thus going to be instrumental to our effort. Starting with our desired result, we find that

\begin{align*} A+B \amp = \overline{\overline{A+B}} \amp \text{(identity 15)} \\ \amp = \overline{\overline{A}\cdot\overline{B}} \amp \text{(identity 18)} \\ \amp = \overline{\left(\overline{A\cdot A}\right)\cdot \left(\overline{B\cdot B}\right)} \amp \text{(identity 14)} \end{align*}

which describes the circuit in Figure 7.2.5.

Figure 7.2.5. NAND circuit providing AND functionality.
🔗

🔗

Example 7.2.6. Boolean algebra: Circuit simplification.

Content not yet available.

🔗

Prev Top Next