Ch 6. Boolean Algebra and Combinatorial Circuits
6.1 Combinatorial Circuits
There are many types of digital logic circuits, and this section focuses on combinatorial circuits, whose output is determined solely by the current values of their inputs. Unlike sequential circuits (beyond the scope of this textbook), which depend on past inputs and include memory elements, combinatorial circuits are stateless and compute outputs using Boolean logic.
Combinatorial circuits are constructed from logic gates, the basic building blocks of digital systems. Each gate performs a specific Boolean operation.
The basic logic gates are AND, OR, and NOT. The AND gate outputs 1 only if both inputs are 1. Its symbol is [latex]x \cdot y[/latex] or [latex]x \land y[/latex]. Its truth table is the following:
| [latex]x[/latex] | [latex]y[/latex] | [latex]x \cdot y[/latex] |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Note the difference between this table and the table for conjunctions in Chapter 3:
| p | q | [latex]p \land q[/latex] |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
The truth values of T and F correspond to the binary values of 1 and 0, respectively. The values between the two tables are “flipped” because digital circuit design matches binary signals to hardware, while mathematical logic emphasizes truth values.
The AND gate is drawn as follows:
The OR gate outputs 1 if at least one of its inputs is 1. Its symbol is [latex]x + y[/latex] or [latex]x \lor y[/latex]. Its truth table is the following:
| [latex]x[/latex] | [latex]y[/latex] | [latex]x + y[/latex] |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
The OR gate is drawn as follows:
The NOT gate outputs the inverse of the input. Its symbol is [latex]\bar{x}[/latex] or [latex]\neg x[/latex]. Its truth table is the following:
| [latex]x[/latex] | [latex]\neg x[/latex] |
|---|---|
| 0 | 1 |
| 1 | 0 |
The NOT gate is drawn as follows:
Example 6.1
A majority circuit outputs 1 if at least two of its three inputs are 1. Let inputs be [latex]A[/latex], [latex]B[/latex], and [latex]C[/latex]. The Boolean expression is
[latex]F = A \cdot B + A \cdot C + B \cdot C[/latex]
This circuit uses three AND gates and two OR gates to compute the result. The three AND gates compute [latex]A \cdot B[/latex], [latex]A \cdot C[/latex], and [latex]B \cdot C[/latex]. The two OR gates are needed to combine the outputs:
First OR gate: [latex]A \cdot B + A \cdot C[/latex]
Second OR gate: [latex](A \cdot B + A \cdot C) + B \cdot C[/latex]
The combinatorial circuit is shown in the figure below.
Note that the AND and OR gates we’ve been using so far are 2-input gates; however, they can be expanded to gates with 3 or more inputs. A multi-input AND gate outputs 1 only if all inputs are 1, while a multi-input OR gate outputs 1 if at least one input is 1. Multi-input gates are useful for simplifying complex circuits, such as replacing two 2-input AND gates to check three conditions with a single 3-input AND gate (try simplifying the circuit in Example 6.1).
A Boolean expression is a formula composed of variables (called literals) and logical operators (AND, OR, NOT). Each literal represents a binary input (0 or 1).
Example 6.2
Let [latex]x[/latex] and [latex]y[/latex] be literals. The expression
[latex]F = x \cdot \bar{y} + \bar{x} \cdot y[/latex]
represents the exclusive OR (XOR) function, which outputs 1 when [latex]x[/latex] and [latex]y[/latex] are different. The combinatorial circuit is shown below.
In Chapter 4, you learned about the fundamental laws of set theory (Theorem 4.2), and similar rules govern how logic gates and Boolean expressions behave. The following theorem outlines properties that make combinatorial circuit design more efficient, reliable, and easier to verify. In addition, these laws allow proofs of equivalence between different circuit designs.
Theorem 6.1: Properties of Combinatorial Circuits
Let [latex]x[/latex], [latex]y[/latex], and [latex]z[/latex] be Boolean variables. The following properties hold for combinatorial circuits:
- Associate Laws
- [latex](x + y) + z = x + (y + z)[/latex]
- [latex](x \cdot y) \cdot z = x \cdot (y \cdot z)[/latex]
- Commutative Laws
- [latex]x + y = y + x[/latex]
- [latex]x \cdot y = y \cdot x[/latex]
- Distributive Laws
- [latex]x \cdot (y + z) = x \cdot y + x \cdot z[/latex]
- [latex]x + (y \cdot z) = (x + y) \cdot (x + z)[/latex]
- Identity Laws
- [latex]x + 0 = x[/latex]
- [latex]x \cdot 1 = x[/latex]
- Complement Laws
- [latex]x + \bar{x} = 1[/latex]
- [latex]x \cdot \bar{x} = 0[/latex]
Proof
All these laws can be proved using truth tables.
[latex]\square[/latex]
Example 6.3
Simplify [latex]F = x \cdot y + x \cdot \bar{y}[/latex].
Using Theorem 6.1 c) i., 6.1 e) i., and 6.1 d) ii. gives
[latex]F = x \cdot (y + \bar{y}) = x \cdot 1 = x[/latex]
The simplified circuit is equivalent to a single wire carrying [latex]x[/latex], as shown below.
Two Boolean expressions are equal if they produce the same output for every possible combination of inputs.
Example 6.4
Let [latex]F_{1} = x \cdot y + x \cdot \bar{y}[/latex] and [latex]F_{2} = x[/latex]. As shown in Example 6.3, [latex]F_{1} = F_{2}[/latex] for all values of [latex]x[/latex] and [latex]y[/latex], so they are equal.
Two combinatorial circuits are equivalent if they compute the same Boolean function.
Example 6.5
Circuit A implements [latex]F = x \cdot y + x \cdot \bar{y}[/latex] and Circuit B implements [latex]F = x[/latex]. Though Circuit A uses more gates, both circuits output the same result for all inputs. Therefore, they are equivalent.
At this point, it appears as if combinatorial circuits and Boolean expressions are the same, and the following theorem confirms this. This equivalence allows engineers to move between algebraic reasoning and hardware implementation easily.
Theorem 6.2: Equivalence Between Combinatorial Circuits and Boolean Expressions
Every combinatorial circuit corresponds to a Boolean expression, and every Boolean expression can be implemented as a combinatorial circuit.
Proof
A combinatorial circuit is constructed using logic gates such as AND, OR, and NOT. Each gate performs a well-defined Boolean operation: AND [latex]\rightarrow[/latex] multiplication ([latex]\cdot[/latex]), OR [latex]\rightarrow[/latex] addition ([latex]+[/latex]), NOT [latex]\rightarrow[/latex] negation ([latex]\neg[/latex]). When gates are connected, their operations can be represented symbolically. Since every gate has a corresponding Boolean operator, and the connections define the structure of the expression, every combinatorial circuit corresponds to a Boolean expression.
Conversely, a Boolean expression is composed of literals and operators such as AND, OR, and NOT. Each operator has a logic gate: [latex]x \cdot y \rightarrow[/latex] AND gate, [latex]x + y \rightarrow[/latex] OR gate, [latex]\bar{x} \rightarrow[/latex] NOT gate. By analyzing the expression and placing gates accordingly (such as in Example 6.1), we can construct a circuit that computes the same output. Thus, every Boolean expression can be implemented as a combinatorial circuit.
[latex]\square[/latex]
Real-World Example 6.1: Digital Access Control System
Suppose you work in a secure office building, where a digital keypad and a card scanner control access to a restricted area. The system grants access only if:
- The correct keypad code is entered ([latex]P = 1[/latex])
- The card is valid ([latex]C = 1[/latex])
- The time of access is within authorized hours ([latex]T = 1[/latex])
This logic can be implemented using a combinatorial circuit with three inputs: [latex]P[/latex], [latex]C[/latex], and [latex]T[/latex]. The output [latex]A[/latex] (Access Granted) is defined by the Boolean expression [latex]A = P \cdot C \cdot T[/latex].
If any input is [latex]0[/latex] (an incorrect code, an invalid card, or the wrong time), access is denied. Only when all three conditions are met does the output become [latex]1[/latex], triggering the door to unlock.
The circuit could be designed with two AND gates, each with two inputs (or with one AND gate with three inputs). The gate's output is connected to the door control mechanism.
