Ch 6. Boolean Algebra and Combinatorial Circuits
6.3 Boolean Functions and Synthesis of Circuits
In this section, we explore how Boolean functions are defined, simplified, and implemented using logic gates. We also introduce techniques for circuit synthesis, which is the process of converting a Boolean function into a physical or simulated circuit.
A Boolean function of [latex]n[/latex] variables is a mapping: [latex]f: \{ 0, 1 \} \times \{ 0, 1 \} \times \cdots \times \{ 0, 1 \} \rightarrow \{ 0, 1 \}[/latex]. It assigns a binary output to each possible combination of [latex]n[/latex] binary inputs.
Example 6.10
Let [latex]f(A, B) = A \cdot B + \bar{A} \cdot \bar{B}[/latex]. This function outputs [latex]1[/latex] when both inputs are equal (either both [latex]0[/latex] or both [latex]1[/latex]). It is the XNOR function.
A truth table can represent a Boolean function, listing all input combinations and corresponding outputs. From the truth table, we can derive:
- Sum of Products (SOP): A disjunction (OR) of minterms (ANDs of literals).
- Product of Sums (POS): A conjunction (AND) of maxterms (ORs of literals).
SOP and POS are useful because they allow mechanical construction from any truth table, and they map directly to 2-level digital circuits.
Example 6.11
Consider the following truth table:
| [latex]A[/latex] | [latex]B[/latex] | [latex]F(A, B)[/latex] |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
The SOP form can be directly constructed from it by noting which rows have a [latex]1[/latex] in [latex]F(A, B)[/latex]. The first row corresponds to [latex]\bar{A} \cdot \bar{B}[/latex] and the last row corresponds to [latex]A \cdot B[/latex]. Taking the logical sum of these two expressions together produces the SOP form [latex]F(A, B) = \bar{A} \cdot \bar{B} + A \cdot B[/latex]. This is the XNOR function from Example 6.10.
The POS form can be constructed from the truth table by noting which rows have a [latex]0[/latex] in [latex]F(A, B)[/latex]. The second row corresponds to [latex]\bar{A} + B[/latex] and the third row corresponds to [latex]A + \bar{B}[/latex]. Taking the logical product of these two expressions together produces the POS form [latex]F(A, B) = (\bar{A} + B) \cdot (A + \bar{B})[/latex].
You can verify that the SOP and POS forms are equivalent using Boolean algebra:
[latex]F(A, B) = (\bar{A} + B) \cdot (A + \bar{B})[/latex]
[latex]= \bar{A} \cdot (A + \bar{B}) + B \cdot (A + \bar{B})[/latex]
[latex]= (\bar{A} \cdot A + \bar{A} \cdot \bar{B}) + (B \cdot A + B \cdot \bar{B})[/latex]
[latex]= (0 + \bar{A} \cdot \bar{B}) + (B \cdot A + 0)[/latex]
[latex]= \bar{A} \cdot \bar{B} + B \cdot A[/latex]
[latex]= \bar{A} \cdot \bar{B} + A \cdot B[/latex]
The following theorem shows that any Boolean function can be written in SOP form. It helps connect truth tables, Boolean algebra, and circuit design cleanly. Its proof is a generalization of the technique used in Example 6.11.
Theorem 6.6
Any Boolean function that is not identically zero can be represented in SOP form.
Proof
Let [latex]F(A_{1}, A_{2}, \dots, A_{n})[/latex] be a Boolean function of [latex]n[/latex] variables. Suppose [latex]F[/latex] is not identically zero, meaning that there exists at least one input combination [latex](a_{1}, a_{2}, \dots, a_{n})[/latex] such that [latex]F(a_{1}, a_{2}, \dots, a_{n}) = 1[/latex].
Construct the truth table for [latex]F[/latex]. For each row where [latex]F = 1[/latex], identify the corresponding input combination [latex](a_{1}, a_{2}, \dots, a_{n})[/latex]. For each such input combination [latex](a_{1}, a_{2}, \dots, a_{n})[/latex] where [latex]F(a_{1}, a_{2}, \dots, a_{n}) = 1[/latex], construct a minterm as follows:
If [latex]a_{i} = 1[/latex], include [latex]A_{i}[/latex] in the minterm.
If [latex]a_{i} = 0[/latex], include [latex]\bar{A_{i}}[/latex] in the minterm.
Take the logical sum of all such minterms. This gives the SOP form that evaluates to 1 exactly when [latex]F(A_{1}, A_{2}, \dots, A_{n}) = 1[/latex], and [latex]0[/latex] otherwise. Hence, it is logically equivalent to [latex]F[/latex].
[latex]\square[/latex]
Recall that Theorem 6.5 states that if a Boolean identity is a theorem, then its dual is also a theorem. The dual transformation of Theorem 6.6 gives the following dual theorem.
Theorem 6.7
Any Boolean function that is not identically one can be represented in POS form.
Boolean expressions can often be simplified using identities and laws (see Section 6.2). Simplification reduces the number of gates and inputs required in a circuit, improving efficiency.
Example 6.12
Consider the Boolean function [latex]F(A, B, C) = A \cdot B \cdot C + A \cdot B \cdot \bar{C} + A \cdot \bar{B} \cdot C[/latex]. It has 2 NOT gates, 6 AND gates, and 2 OR gates, so it would require 10 gates to construct the equivalent circuit.
Let’s simplify the function. First group terms with common factors as follows:
[latex]F(A, B, C) = A \cdot B \cdot (C + \bar{C}) + A \cdot \bar{B} \cdot C[/latex]
Apply Axiom 6.1 f) i. and 6.1 e) ii. to obtain
[latex]F(A, B, C) = A \cdot B \cdot 1 + A \cdot \bar{B} \cdot C = A \cdot B + A \cdot \bar{B} \cdot C[/latex]
Now factor out [latex]A[/latex] using the reverse of Axiom d) i. to get the form
[latex]F(A, B, C) = A \cdot (B + \bar{B} \cdot C)[/latex]
This can be simplified further using Axiom 6.1 d) ii., Axiom 6.1 f) i., and Axiom 6.1 e) ii. to obtain
[latex]F(A, B, C) = A \cdot (B + C)[/latex]
It cannot be reduced further using basic Boolean identities. This simplified function has 0 NOT gates, 1 AND gate, and 1 OR gate, so it requires 2 gates, fewer than the original Boolean function.
Circuit synthesis is the process of converting a Boolean function into a logic circuit using gates. The steps are as follows:
- Define the Boolean function (from truth table or specification).
- Simplify the function using Boolean algebra.
- Draw the logic diagram using AND, OR, NOT, etc.
- Implement the circuit in hardware or software.
Example 6.13
Let’s extend the majority function (see Example 6.1) from three to four inputs: [latex]A[/latex], [latex]B[/latex], [latex]C[/latex], and [latex]D[/latex]. The output should be [latex]1[/latex] if at least three of its four inputs are [latex]1[/latex].
First, we identify the minterms. We want the output to be [latex]1[/latex] for combinations where three or more inputs are [latex]1[/latex]. These combinations are [latex]A \cdot B \cdot C[/latex], [latex]A \cdot B \cdot D[/latex], [latex]A \cdot C \cdot D[/latex], [latex]B \cdot C \cdot D[/latex], and [latex]A \cdot B \cdot C \cdot D[/latex].
Next, we write the Boolean function:
[latex]F(A, B, C, D) = A \cdot B \cdot C + A \cdot B \cdot D + A \cdot C \cdot D + B \cdot C \cdot D + A \cdot B \cdot C \cdot D[/latex]
Then we simplify the expression; however, it is already minimal in terms of SOP for the majority logic. Each term represents a unique combination of three or more inputs being [latex]1[/latex].
Finally, we implement the circuit. Four 3-input AND gates, one 4-input AND gate and one 5-input OR gate can achieve this. The same circuit could also be created using 2-input AND and OR gates.
Real-World Example 6.3: Smart Home Security System
Suppose you are designing a smart home security system that uses sensors to determine whether to trigger an alarm. The system has the three binary inputs ([latex]1[/latex] = yes, [latex]0[/latex] = no) [latex]A[/latex], [latex]B[/latex], and [latex]C[/latex] to detect motion, an open door, and an open window, respectively. The alarm should activate if motion is detected ([latex]A[/latex]) AND either the door ([latex]B[/latex]) or window ([latex]C[/latex]) is open; OR if both the door ([latex]B[/latex]) AND window ([latex]C[/latex]) are open, even without motion.
Let the alarm output be [latex]F(A, B, C)[/latex]. Then
[latex]F(A, B, C) = A \cdot (B + C) + B \cdot C[/latex]
The term [latex]A \cdot (B + C)[/latex] means motion is detected and either the door or window is open. The term [latex]B \cdot C[/latex] means both the door and window are open, regardless of motion.
To implement this function, use one OR gate to compute [latex]B + C[/latex], one AND gate to compute [latex]A \cdot (B + C)[/latex], another AND gate to compute [latex]B \cdot C[/latex], and one OR gate to combine the two outputs for final [latex]F[/latex]. The circuit is shown in the figure below:
