A function is its truth table
A Boolean variable holds one bit: 0 or 1. A Boolean function takes some
input bits and produces one output bit. With n inputs there are only 2n possible
input combinations, so you can describe the function completely by listing the output for every one of them.
That list is the truth table.
Our running example is the majority function of three inputs: M is 1 when at least two of A, B, C are 1. (It is also the carry output of a full adder.)
| # | A | B | C | M |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 2 | 0 | 1 | 0 | 0 |
| 3 | 0 | 1 | 1 | 1 |
| 4 | 1 | 0 | 0 | 0 |
| 5 | 1 | 0 | 1 | 1 |
| 6 | 1 | 1 | 0 | 1 |
| 7 | 1 | 1 | 1 | 1 |
Two habits to build now, because every method later depends on them:
- Fix the variable order. A is the most significant bit, C the least.
- Number the rows. Read the inputs as a binary number:
ABC = 101is row 5. The column marked # is that number.
Minterms: the rows where the function is 1
A minterm is an AND of all the variables, each one either plain or complemented, that is 1 for exactly one row. To build the minterm for a row, write each variable plain where its bit is 1 and with an overbar where its bit is 0:
| Row | ABC | Minterm | Name |
|---|---|---|---|
| 3 | 011 | ABC | m3 |
| 5 | 101 | ABC | m5 |
| 6 | 110 | ABC | m6 |
| 7 | 111 | ABC | m7 |
Check one: ABC is 1 only when A = 1, B = 0 and C = 1 — row 5 and no other.
The function is 1 exactly on its minterms, so listing their numbers is a complete description. The shorthand uses Σ (sum, meaning OR):
M(A, B, C) = Σm(3, 5, 6, 7)
This compact list is how you will give functions to every tool on this site.
Maxterms: the rows where the function is 0
You can describe the same function from the other side. A maxterm is an OR of all the variables that is 0 for exactly one row. The rule is the mirror image: write each variable plain where its bit is 0 and complemented where its bit is 1.
| Row | ABC | Maxterm | Name |
|---|---|---|---|
| 0 | 000 | A + B + C | M0 |
| 1 | 001 | A + B + C | M1 |
| 2 | 010 | A + B + C | M2 |
| 4 | 100 | A + B + C | M4 |
The shorthand uses Π (product, meaning AND):
M(A, B, C) = ΠM(0, 1, 2, 4)
The two lists are complements. Every row number from 0 to 2n − 1 is in exactly one of them. If you know Σm, you know ΠM.
Don’t-cares
Sometimes an input combination can never happen, or the output does not matter when it does. Those rows
are don’t-cares, written X in the table and listed separately:
F = Σm(…) + d(…). A minimizer may treat each don’t-care
as 0 or as 1, whichever gives the smaller circuit. You will use them in the
Karnaugh map lesson.
Check yourself
- A function of four variables A B C D is 1 for the input
1010. Which minterm number is that, and what is the minterm?Show answer
Binary 1010 is 10, so it is m10 = ABCD. - For three variables, write the maxterm M6.
Show answer
Row 6 is110. Complement where the bit is 1: A + B + C. It is 0 only when A = 1, B = 1, C = 0. - F(A, B, C) = Σm(0, 2, 4, 6). Write F in ΠM form. Can you see a much simpler description of F?
Show answer
F = ΠM(1, 3, 5, 7). The 1-rows are exactly the even numbers, where C = 0, so F = C. Finding that kind of simplification systematically is what the rest of these lessons are about. - How many rows does the truth table of a 5-variable function have, and what is the largest minterm number?
Show answer
25 = 32 rows, numbered 0 to 31.