Boolean algebra, named after mathematician George Boole, is the bedrock of all digital circuitry. It deals with variables that can only have two states: True (1) or False (0). When we consider two input variables, A and B, there are only four possible combinations of inputs: (0, 0), (0, 1), (1, 0), and (1, 1).
Since each of these four input combinations can result in either a 0 or a 1 as an output, the total number of unique Boolean functions possible is `2^4 = 16`.
This article explores these 16 fundamental logical operations, categorized by their complexity and importance in digital design.
To understand the functions, we must first define the input possibilities.
| A | B |
|---|---|
| 0 | 0 |
| 0 | 1 |
| 1 | 0 |
| 1 | 1 |
The 16 functions can be grouped into several categories based on their output patterns, from the simplest constants to the most complex exclusive gates. Let `F` represent the function’s output.
These functions ignore the inputs entirely and always produce the same output.
| Function Name | Expression | A=0, B=0 | A=0, B=1 | A=1, B=0 | A=1, B=1 | Description |
|---|---|---|---|---|---|---|
| Zero (FALSE) | `F\_0 \= 0` | 0 | 0 | 0 | 0 | Always outputs 0. |
| One (TRUE) | `F\_{15} \= 1` | 1 | 1 | 1 | 1 | Always outputs 1. |
These functions depend on only one of the inputs, either directly or inverted.
| Function Name | Expression | A=0, B=0 | A=0, B=1 | A=1, B=0 | A=1, B=1 | Description |
|---|---|---|---|---|---|---|
| Transfer A | `F\_{3} \= A` | 0 | 0 | 1 | 1 | Output is simply A. |
| Transfer B | `F\_{5} \= B` | 0 | 1 | 0 | 1 | Output is simply B. |
| NOT A | `F\_{12} \= \bar{A}` | 1 | 1 | 0 | 0 | Output is the inverse of A. |
| NOT B | `F\_{10} \= \bar{B}` | 1 | 0 | 1 | 0 | Output is the inverse of B. |
These are the primary logic gates used universally in digital systems.
| Function Name | Expression | A=0, B=0 | A=0, B=1 | A=1, B=0 | A=1, B=1 | Common Gate |
|---|---|---|---|---|---|---|
| AND | `F\_{8} \= A \cdot B` | 0 | 0 | 0 | 1 | A 1 only if A AND B are 1. |
| OR | `F\_{14} \= A \+ B` | 0 | 1 | 1 | 1 | A 1 if A OR B (or both) is 1. |
| NAND | `F\_{7} \= \overline{A \cdot B}` | 1 | 1 | 1 | 0 | The NOT-AND of A and B. (Universal Gate) |
| NOR | `F\_{1} \= \overline{A \+ B}` | 1 | 0 | 0 | 0 | The NOT-OR of A and B. (Universal Gate) |
These functions are critical for arithmetic circuits (like adders) and comparing inputs.
| Function Name | Expression | A=0, B=0 | A=0, B=1 | A=1, B=0 | A=1, B=1 | Description |
|---|---|---|---|---|---|---|
| XOR (Exclusive-OR) | `F\_{6} \= A \oplus B` | 0 | 1 | 1 | 0 | A 1 if A and B are different. |
| XNOR (Equivalence) | `F\_{9} \= \overline{A \oplus B}` | 1 | 0 | 0 | 1 | A 1 if A and B are the same. |
These functions are less common in general digital logic but play a role in advanced logic design and certain formal systems.
| Function Name | Expression | A=0, B=0 | A=0, B=1 | A=1, B=0 | A=1, B=1 | Description |
|---|---|---|---|---|---|---|
| A Implies B (Material Implication) | `F\_{13} \= \bar{A} \+ B` | 1 | 1 | 0 | 1 | False only if A is 1 and B is 0. |
| B Implies A | `F\_{11} \= A \+ \bar{B}` | 1 | 0 | 1 | 1 | False only if B is 1 and A is 0. |
| A NOT-Implies B | `F\_{4} \= A \cdot \bar{B}` | 0 | 0 | 1 | 0 | True only if A is 1 and B is 0. |
| B NOT-Implies A | `F\_{2} \= \bar{A} \cdot B` | 0 | 1 | 0 | 0 | True only if A is 0 and B is 1. |
The most fascinating aspect of these 16 functions is that two are individually capable to construct all the others: the NAND gate and the NOR gate.
Because of this property, NAND and NOR gates are known as Universal Gates. A computer can be built entirely using only one type of gate, significantly simplifying the manufacturing process of integrated circuits.
This table consolidates all 16 functions based on the output for the four input combinations.
| F# | (0,0) | (0,1) | (1,0) | (1,1) | Function Name | Expression | Common Gate |
|---|---|---|---|---|---|---|---|
| `F\_0` | 0 | 0 | 0 | 0 | Zero | `0` | (Constant) |
| `F\_1` | 1 | 0 | 0 | 0 | NOR | `\overline{A+B}` | NOR |
| `F\_2` | 0 | 1 | 0 | 0 | B NOT-Implies A | `\bar{A} \cdot B` | |
| `F\_3` | 0 | 0 | 1 | 1 | Transfer A | `A` | |
| `F\_4` | 0 | 0 | 1 | 0 | A NOT-Implies B | `A \cdot \bar{B}` | |
| `F\_5` | 0 | 1 | 0 | 1 | Transfer B | `B` | |
| `F\_6` | 0 | 1 | 1 | 0 | XOR | `A \oplus B` | XOR |
| `F\_7` | 1 | 1 | 1 | 0 | NAND | `\overline{A \cdot B}` | NAND |
| `F\_8` | 0 | 0 | 0 | 1 | AND | `A \cdot B` | AND |
| `F\_9` | 1 | 0 | 0 | 1 | XNOR | `\overline{A \oplus B}` | XNOR |
| `F\_{10}` | 1 | 0 | 1 | 0 | NOT B | `\bar{B}` | NOT |
| `F\_{11}` | 1 | 0 | 1 | 1 | B Implies A | `A \+ \bar{B}` | |
| `F\_{12}` | 1 | 1 | 0 | 0 | NOT A | `\bar{A}` | NOT |
| `F\_{13}` | 1 | 1 | 0 | 1 | A Implies B | `\bar{A} \+ B` | |
| `F\_{14}` | 0 | 1 | 1 | 1 | OR | `A \+ B` | OR |
| `F\_{15}` | 1 | 1 | 1 | 1 | One | `1` | (Constant) |
These 16 logical functions, derived from two simple binary inputs, form the complete vocabulary for all computational processes, demonstrating the incredible complexity that can be built from the simplest of foundations.