14.2 Truth tables and logic expressions

Truth Tables and Logic Expressions

Truth tables and logic expressions are the two main ways to describe what a digital circuit does. A truth table lists every possible input combination and the output for each one. A logic expression captures that same information as a compact Boolean algebra formula. Together, they let you move from a written description of a circuit's behavior to an actual design you can build and optimize.

Truth Tables and Logic Expressions

Representing Logic Functions

A truth table is a chart that shows the output of a logic function for every possible combination of inputs. Each row is one combination, and the rightmost column gives the output value (0 or 1) for that row.

For example, a 2-input AND gate has this truth table:

With $n$ inputs, the table has $2^n$ rows. So a 3-input function has 8 rows, a 4-input function has 16, and so on.

A logic expression describes the same function using Boolean variables (typically letters like A, B, C) and operators:

• AND (written as $A \cdot B$ or just $AB$): output is 1 only when both inputs are 1
• OR (written as $A + B$): output is 1 when at least one input is 1
• NOT (written as $A'$ or $\overline{A}$): flips the value, so 1 becomes 0 and vice versa

Minterms and Maxterms

These are the building blocks for writing logic expressions directly from a truth table.

Minterms are AND (product) terms where every variable appears exactly once, either in true or complemented form. Each minterm corresponds to exactly one row of the truth table where the output is 1.

• Notation: $m_i$, where $i$ is the decimal value of the binary input combination.
• Example with three variables A, B, C: the input combination A=0, B=1, C=1 is binary 011 = decimal 3, so $m_3 = A'BC$.

Maxterms are OR (sum) terms where every variable appears exactly once. Each maxterm corresponds to a row where the output is 0. The variable is complemented when the input bit is 1 (the opposite convention from minterms).

• Notation: $M_i$, using the same decimal index.
• Example: for the same row (A=0, B=1, C=1), $M_3 = A + B' + C'$.

Canonical Forms

Sum of Products (SOP) and Product of Sums (POS)

Canonical forms give you a standard recipe for writing a logic expression straight from a truth table.

Sum of Products (SOP): OR together all the minterms where the output is 1.

1. Look at the truth table and find every row with output = 1.
2. Write the minterm for each of those rows.
3. OR them all together.

For example, if a 3-variable function outputs 1 for rows 1, 3, and 5:

$F = m_1 + m_3 + m_5 = A'B'C + A'BC + AB'C$

Product of Sums (POS): AND together all the maxterms where the output is 0.

1. Find every row with output = 0.
2. Write the maxterm for each of those rows.
3. AND them all together.

$F = M_0 \cdot M_2 \cdot M_4 \cdot M_6 \cdot M_7$

Both forms describe the exact same function. Any logic function can be written in either SOP or POS form, and you can convert between them. SOP tends to be more common in practice because most people find it more intuitive to list the conditions that make the output 1.

Simplifying Logic Expressions

Canonical SOP and POS expressions are complete but often longer than necessary. Simplification reduces the number of terms and literals, which translates directly to fewer gates and connections in hardware.

Boolean algebra laws you'll use most often:

• Commutative: $A + B = B + A$, $AB = BA$
• Associative: $(A + B) + C = A + (B + C)$
• Distributive: $A(B + C) = AB + AC$
• Absorption: $A + AB = A$
• De Morgan's Theorem: $(AB)' = A' + B'$ and $(A + B)' = A'B'$

Karnaugh maps (K-maps) offer a visual shortcut that avoids algebraic manipulation:

1. Draw a grid where each cell represents one minterm. The rows and columns are labeled using Gray code so that adjacent cells differ by only one variable.
2. Place a 1 in each cell where the function output is 1.
3. Group adjacent 1s into rectangles whose size is a power of 2 (1, 2, 4, 8...). Make groups as large as possible.
4. Each group becomes one product term in the simplified expression. Variables that stay the same across the group remain; variables that change are eliminated.
5. OR the resulting product terms together for the simplified SOP.

Larger groups mean simpler terms. A group of 2 eliminates one variable, a group of 4 eliminates two, and so on.

Don't Care Conditions and Simplification

Sometimes certain input combinations can never actually occur in your system, or you genuinely don't care what the output is for those cases. These are called don't care conditions, marked with an X in the truth table.

Don't cares are powerful for simplification because you can treat each X as either 0 or 1, whichever helps you form larger groups on the K-map.

How to use them:

1. Place Xs in the appropriate K-map cells alongside your 1s and 0s.
2. When forming groups, include X cells if doing so lets you make a group larger.
3. You don't have to include every X. Only include the ones that actually help simplify.
4. Never form a group that contains only Xs with no actual 1s (for SOP simplification).

A classic example of don't cares: a BCD (Binary-Coded Decimal) system uses 4 bits but only represents values 0 through 9. Input combinations 10 through 15 (binary 1010 through 1111) never occur, so those six rows are don't cares. Taking advantage of them often leads to significantly simpler circuits.