Truth Tables
A truth table is a clean way to explain the behavior of a logic gate or circuit. We can use truth tables to understand what a particular circuit does as well as to identify circuits that can be simplified to save money and power.
Video Lecture
Inputs and Outputs
Each logic gate or circuit built from logic gates takes one or more inputs and produces one or more outputs. An input is a logical signal (on or off) that flows into the gate or circuit. By convention, we label inputs starting from the letter A and moving up a letter for each input.
In contrast, an output is the logical signal (on or off) that a gate or circuit produces. For our purposes, we can use the convention of labeling a single output with the letter Q. If we have a circuit that produces multiple outputs, we can use subscripts like Q0, Q1, etc.
Truth Tables
When we’re describing the behavior of a gate, or of a logical circuit composed of multiple gates, a clean way to explain what the circuit will do for a given set of inputs is to create a truth table for the circuit. Each possible combination of inputs to a circuit is enumerated by the rows of the truth table, which will also show the circuit’s output for that combination of inputs.
You may have seen truth tables used before in mathematics. Math folks like to write truth tables like the one shown in Table 1.
| A | B | A·B |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Mathematicians like to put the true conditions (T) before the false conditions (F) on the inputs. With this ordering, the row where all the inputs are true appears as the first row of the table, and the row where all inputs are false appears last. In addition, the logical expression is often written in the header out of the output column.
In computing, and particularly in the field of computer engineering, it is more useful to write the truth table in the opposite order. As shown in Table 2, the row with all false values (represented by 0) comes first, while the row with all true values (represented by 1) comes last.
| A | B | Q |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
We write the truth table in the second format to make it easier to design and reference circuits based on the input combinations. As we’ll see later, the input combinations (00, 01, 10, 11) correspond to the binary numbers for 0, 1, 2, and 3. When truth tables become long and complex, it is easy and unambiguous to refer to a single row in the truth table by number. For example, if we’re told to look at row 2 in the truth table in Table 2, we convert 2 to binary (10), then look at the row where the input A is 1 and the input B is 0. The output Q on that row is 0.
Another reason that we put truth tables in a different order in computing is that truth tables in math (and philosophy, where they are also used) are usually limited to a small number of inputs – frequently only two. In computing, we routinely deal with logical circuits that can have more than 10 inputs. Not the counting the header that shows us which column is which, a truth table has 2N data rows, where N is the number of inputs. It takes that many rows to be able to represent every possible combination of inputs.
If we have one input, 21=2, so our truth table will have 2 data rows. At two inputs, we have 22=4 data rows. Three inputs is still reasonably manageable, with 23=8 data rows. However, this doubling pattern continues with each extra input. At 10 inputs, we will have 210=1,024 data rows. A truth table of this size, which is not uncommon in computing, will not fit on one sheet of paper or a marker board. For these reasons, we organize our truth tables differently in computing.
Tautologies
Consider the truth table for the logical expression A + A (A OR NOT A), shown in Table 3.
| A | A | Q |
|---|---|---|
| 0 | 1 | 1 |
| 1 | 0 | 1 |
Regardless of the input value for A, the output value of A + A is always 1. This circuit is called a tautology, meaning that it is always true.
We care about tautologies because we can save money building circuits that produce them. In this example, we can remove the input A, the NOT gate, and the OR gate. All we need to do is to run a wire directly from positive voltage (1) to the output, since that output will always be a 1.
To compare the cost difference, consider two commercially available chips that provide the logic gates. The TI SN74321 provides 4 OR gates on a single chip, while the SN74042 model contains 6 inverters (NOT gates). As of September 20, 2021, the cost to purchase a single SN7404N chip from a major electronics component supplier was $2.353. The SN7432N cost $2.45 from the same supplier4, and flat-rate shipping was about $7. The cost to implement this circuit would be about $12, not including the wire to join the chips together or the breadboard on which to place the components.
Assuming we already had the wire, we could save this entire cost by simply replacing this circuit with a wire to VCC. Now, the actual cost savings in practice would be a different calculation, since we wouldn’t actually order just 1 of each chip at a time, and there are price breaks with increasing quantities. However, if we were manufacturing a large number of devices, there would be a cost per device to consider, and using unnecessary gates would eat into our profits. Once built, a circuit with unneeded gates would also cost more to run, since each gate consumes a small amount of electricity. At scale, the extra gates would have an environmental impact.
Fallacies
The other extreme from a tautology is a fallacy, or a logical circuit that always produces a 0 (false). If we change our previous example to A·A (A AND NOT A), we get the truth table shown in Table 4.
| A | A | Q |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 0 | 0 |
We can replace this entire circuit with a wire running directly to the negative side of our power supply (GND), again saving a little bit of money and power. The TI SN74S085 quadruple AND gate chip was a bit less expensive (September 20, 2021) at $1.68.6
