3.4 On sets, off sets and the uniting theorem

Why this matters

A truth table says what a circuit must do, and the most direct formula you can write from it is as long as the table. Real designs need something smaller, because every extra term is another gate. This section shows the one algebra step that shrinks a formula, and it shows which pairs of rows it works on. The next two sections turn that step into a drawing you can do quickly by hand.

Learning goals

• Name the on set and the off set of a function from its truth table.
• Write a sum of products from the on set and a product of sums from the off set.
• Identify neighboring input patterns, which differ in exactly one input.
• Merge two neighboring patterns into one smaller term with the uniting theorem.
• Explain why scanning a truth table is a poor way to find neighbors.

Intuition first

Think of a truth table as a guest list. The rows where F is 1 are the names on the list, and a circuit for F is a doorman: it must say yes to every name on the list and no to everyone else. The most direct doorman hires one checker per name. Each checker recognizes exactly one input pattern, and an OR gate at the end says yes when any checker does. That circuit is correct, and it is exactly as big as the list.

Software has the same shape. A test written as a == 0 && b == 0 && c == 1 || a == 0 && b == 1 && c == 1 is really just a == 0 && c == 1, because the test says yes for both values of b, so b does not matter. Hardware gets the same saving, with one difference: all the gates in a circuit work at the same time, so nothing is skipped. What you save is gates and wires.

The question for this section is how to notice, in a table, which checkers can be merged.

On sets and off sets

Definition 3.4.1(on set and off set).

The on set of a function is the set of input patterns for which the function is 1. The off set is the set of input patterns for which it is 0.

A function with no don't-care outputs puts every input pattern in exactly one of the two sets. (Section 3.7 adds a third group for patterns whose output does not matter.)

Example 3.4.1(the two sets of a three-input function).

Figure 3.4.1 shows a function F of three inputs with the rows of its on set highlighted. The on set is the four patterns where A, B and C are 001, 011, 100 and 101. The off set is the other four: 000, 010, 110 and 111.

Truth table with 3 inputs (A, B, C) and output F; 8 rows in ascending binary order, A most significant

A	B	C	F
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0

Description: A truth table of F with inputs A, B and C. Four of the eight rows are highlighted: the rows where A, B and C are 0 0 1, 0 1 1, 1 0 0 and 1 0 1.

Figure 3.4.1. The function F. The highlighted rows are its on set.

A sum of products from the on set

The on set tells you directly how to build the doorman. Each pattern in it gets one checker, which is a product of all the inputs.

Definition 3.4.2(sum of products from the on set).

The sum of products from the on set has one product term for each pattern in the on set. The term is 1 on that pattern and 0 on every other pattern: each input appears plain if it is 1 in the pattern and with a bar if it is 0. The function is the OR of these terms.

For the pattern 001 of F the term is $\overline{A}\,\overline{B}C$: A and B are 0, so they carry bars, and C is 1, so it does not. Doing the same for the other three patterns and adding the results gives

$\overline{A}\,\overline{B}C +$ $\overline{A}BC +$ $A\overline{B}\,\overline{C} +$ $A\overline{B}C$

This is correct, because on every on-set pattern exactly one of the terms is 1, and on every off-set pattern none is. It also has four terms of three variables each, which is as large as the on set.

A product of sums from the off set

The off set gives a second recipe. Instead of listing the patterns where the answer is yes, list the patterns where it is no, and write a check that fails on exactly one of them.

Definition 3.4.3(product of sums from the off set).

The product of sums from the off set has one sum term for each pattern in the off set. The term is 0 on that pattern and 1 on every other pattern: each input appears plain if it is 0 in the pattern and with a bar if it is 1. The function is the AND of these terms.

The bars are the opposite way around from the product recipe, because a sum is 0 only when every one of its pieces is 0. For the off-set pattern 000 the sum is $A + B + C$, which is 0 only when A, B and C are all 0. For 010 it is $A + \overline{B} + C$. Doing this for all four off-set patterns gives

$(A + B + C) \cdot (A + \overline{B} + C) \cdot (\overline{A} + \overline{B} + C) \cdot (\overline{A} + \overline{B} + \overline{C})$

An AND is 0 as soon as one factor is 0, so this is 0 on every off-set pattern. On any other pattern every factor is 1, so the whole product is 1. The two forms describe the same function: the sum of products is 1 on exactly the on-set rows, and the product of sums is 0 on exactly the off-set rows. The sum of products reads the ones of the table and the product of sums reads the zeros. Both are two-level forms: a layer of ANDs feeding one OR, or a layer of ORs feeding one AND.

Neighbors and the uniting theorem

Definition 3.4.4(neighboring patterns).

Two input patterns are neighbors if they differ in exactly one input.

A pattern of $n$ inputs has exactly $n$ neighbors, one for each input you could flip. The pattern 001 has three: 101 (flip A), 011 (flip B) and 000 (flip C).

Neighbors are interesting because of what happens to their terms. In F, the patterns 001 and 011 are both in the on set, and they differ only in B. Their two products are the same except for the bar on B, so B can be pulled out of the picture:

Step-by-step simplification; each line names the law used to get from the line above

Expression	Law used
$\overline{A}\,\overline{B}C + \overline{A}BC$
$= \overline{A} \cdot C \cdot (\overline{B} + B)$	Distributive
$= \overline{A} \cdot C \cdot 1$	Complement
$= \overline{A}C$	Identity

Nothing special happened to B in that argument. Any two products that match in every variable except one, where one has the variable and the other has its complement, merge this way. That is the uniting theorem.

Definition 3.4.5(uniting theorem).

The uniting theorem says that if E is any expression that does not use B, then $EB + E\overline{B} = E$. Its dual for sums is $(E + B) \cdot (E + \overline{B}) = E$. In words: two terms that differ only in whether B or its complement appears collapse into the part they share.

Example 3.4.2(merging the neighbors of F).

F has three neighbor pairs in its on set, and two of them are enough to cover it. The patterns 001 and 011 differ only in B and merge into $\overline{A}C$, as the derivation above showed. The patterns 100 and 101 differ only in C. Both have A equal to 1 and B equal to 0, so they merge into $A\overline{B}$. All four on-set patterns are now covered, and the sum of the two merged terms is the function: $\overline{A}\,\overline{B}C +$ $\overline{A}BC +$ $A\overline{B}\,\overline{C} +$ $A\overline{B}C$ $= \overline{A}C +$ $A\overline{B}$. Four terms of three variables became two terms of two.

There is a third neighbor pair, which also lies inside the on set: 001 and 101 differ only in A, and they merge into $\overline{B}C$. A pattern can have several neighbors in the on set, and it can be merged with any of them. Here that extra term is not needed, because the first two merges already cover every on-set pattern: $\overline{A}C +$ $A\overline{B} +$ $\overline{B}C$ $= \overline{A}C +$ $A\overline{B}$. Section 3.6 returns to this, because deciding which merges to keep is the whole skill of grouping.

The product of sums has its own version of the same move. In F, the off-set patterns 000 and 010 are neighbors that differ only in B.

Example 3.4.3(the same move on the off set).

The sums for 000 and 010 are $A + B + C$ and $A + \overline{B} + C$. Pulling out the shared part works the same way, with the dual form of the theorem:

Step-by-step simplification; each line names the law used to get from the line above

Expression	Law used
$(A + B + C) \cdot (A + \overline{B} + C)$
$= (A + C + B) \cdot (A + C + \overline{B})$	Commutative
$= A + C + B\overline{B}$	Distributive
$= A + C + 0$	Complement
$= A + C$	Identity

The other two off-set patterns, 110 and 111, differ only in C and merge into $\overline{A} + \overline{B}$. Together the two merged sums cover the whole off set, and the result is the same function again: $(A + C) \cdot (\overline{A} + \overline{B})$ $= \overline{A}C +$ $A\overline{B}$. This product of sums has two sums of two variables each, and the sum of products above has two products of two variables each, so neither form is smaller here. In general the two recipes can give forms of different sizes.

Why we need a better way to find neighbors

Both examples relied on spotting neighbors in a table, and the table makes that hard. The patterns 001 and 101 are neighbors but sit four lines apart. The patterns 011 and 100 sit on consecutive lines, and they differ in all three inputs. With four inputs a pattern has four neighbors scattered through sixteen rows, and the counting-order layout of the table is no help in finding them.

What we want is a layout of the same truth table in which neighbors are physically next to each other, so that your eye finds the pairs. That layout is the Karnaugh map (Definition 3.5.2), and building one is the next section.

Course conventions

How CSE 369 writes this

In CSE 369 we write NOT as an overbar and name the two recipes by their shape: a sum of products from the on set, a product of sums from the off set. Truth table rows are in ascending binary order with the first-listed input as the high bit, which is why 011 comes just before 100. The merging rule is called the uniting theorem.

Pitfalls

Common pitfall

• Taking neighbors in the table to be neighbors in the function. Patterns that sit on consecutive lines may differ in several inputs, and patterns that are far apart may differ in one.
• Building a product from an off-set pattern, or a sum from an on-set pattern. The sum of products reads the ones of the table and the product of sums reads the zeros.
• Putting the bars the wrong way around in a sum. A sum for an off-set pattern shows an input plain where the pattern has 0 and barred where it has 1, the opposite of a product.
• Dropping the wrong variable when merging. Keep every variable that is the same in both patterns and drop only the one that differs.
• Trying to merge two patterns that differ in two or more inputs. Two such patterns cannot be written as a single product, because a product with a variable left out always covers two patterns that differ in that variable.

Check your understanding

Take the quiz (5 questions)

Which expression is the sum of products built from the on set of F, the function in Figure 3.4.1?

$\overline{A}\,\overline{B}C + \overline{A}BC + A\overline{B}\,\overline{C} + A\overline{B}C$$\overline{A}\,\overline{B}\,\overline{C} + \overline{A}B\overline{C} + AB\overline{C} + ABC$$AB\overline{C} + A\overline{B}\,\overline{C} + \overline{A}BC + \overline{A}B\overline{C}$

The on-set patterns 001 and 101 of F differ only in A. Which term do they merge into?

$\overline{B}C$$\overline{A}C$$C$

Which product of sums is built from the off set of F?

$(A + B + C) \cdot (A + \overline{B} + C) \cdot (\overline{A} + \overline{B} + C) \cdot (\overline{A} + \overline{B} + \overline{C})$$(\overline{A} + \overline{B} + \overline{C}) \cdot (\overline{A} + B + \overline{C}) \cdot (A + B + \overline{C}) \cdot (A + B + C)$$(A + B + \overline{C}) \cdot (A + \overline{B} + \overline{C}) \cdot (\overline{A} + B + C) \cdot (\overline{A} + B + \overline{C})$

The function that is 1 when an odd number of A, B and C are 1 has four patterns in its on set, and none of them is a neighbor of another. How many terms does a minimal sum of products for it have?

423

Let G be 1 exactly when A and B are equal, whatever C is. On how many of the eight input patterns is G equal to 1?

426

Exercises

Exercise 3.4.1

A function F of three inputs A, B and C is 1 exactly when A and B have the same value, whatever C is. List its on set and its off set, and write the sum of products from the on set.

Hint

List the combinations of A and B that agree, and let C take both values for each.

Solution

A and B agree when both are 0 or both are 1. With C free, the on set is 000, 001, 110 and 111, and the off set is the other four patterns, 010, 011, 100 and 101.

Truth table with 3 inputs (A, B, C) and output F; 8 rows in ascending binary order, A most significant

A	B	C	F
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Description: A truth table of F with the rows 0 0 0, 0 0 1, 1 1 0 and 1 1 1 highlighted.

Figure 3.4.2. The function with its on set highlighted.

One product for each pattern of the on set, with a bar on every input that is 0 in that pattern, gives $\overline{A}\,\overline{B}\,\overline{C} +$ $\overline{A}\,\overline{B}C +$ $AB\overline{C} +$ $ABC$. The first two products differ only in C, and the last two differ only in C as well, so each pair merges. The merged form is $\overline{A}\,\overline{B}\,\overline{C} +$ $\overline{A}\,\overline{B}C +$ $AB\overline{C} +$ $ABC$ $= \overline{A}\,\overline{B} +$ $AB$.

Tags: Warm-upBoolean algebra

Exercise 3.4.2

Use the uniting theorem to simplify $A\overline{B}C + ABC$. Say which variable disappears and why.

Hint

The two products differ in exactly one variable.

Solution

The products match in A and C and differ in B, so B disappears. Factor out what they share, A and C, and the rest is B or its complement, which is always 1.

Step-by-step simplification; each line names the law used to get from the line above

Expression	Law used
$A\overline{B}C + ABC$
$= A \cdot C \cdot (\overline{B} + B)$	Distributive
$= A \cdot C \cdot 1$	Complement
$= AC$	Identity

Tags: Warm-upBoolean algebra

Exercise 3.4.3

List the three neighbors of the input pattern 101 for F, the function in Figure 3.4.1. Which of them are in the on set of F, and what terms do the pairs they form with 101 merge into?

Hint

Flip one input at a time. The function's on set is 001, 011, 100 and 101.

Solution

Flipping A gives 001, flipping B gives 111, and flipping C gives 100. The patterns 001 and 100 are in the on set, and 111 is not, because F is 0 there. The pair 101 and 001 differs only in A, so A drops out and the term is $\overline{B}C$. The pair 101 and 100 differs only in C, so C drops out and the term is $A\overline{B}$. The pattern 111 is a neighbor of 101, but it is in the off set, so it cannot be merged with an on-set pattern. Merging them would produce a term that is 1 on a pattern where F is 0.

Tags: StandardBoolean algebra

Exercise 3.4.4

The function in the table below is 0 on the patterns 010, 011 and 110 only. Write a product of sums from its off set, and then merge neighboring off-set patterns to make it smaller.

Truth table with 3 inputs (A, B, C) and output F; 8 rows in ascending binary order, A most significant

A	B	C	F
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

Description: A truth table of F with inputs A, B and C. F is 0 on three rows and 1 on five rows.

Figure 3.4.3. A function whose off set has three patterns.

Hint

A sum for an off-set pattern shows each input plain where the pattern has 0. Then look for two off-set patterns that differ in one input.

Solution

The three sums are $A + \overline{B} + C$ for 010, $A + \overline{B} + \overline{C}$ for 011 and $\overline{A} + \overline{B} + C$ for 110, so the function is $(A + \overline{B} + C) \cdot (A + \overline{B} + \overline{C}) \cdot (\overline{A} + \overline{B} + C)$.

The patterns 010 and 011 differ only in C, so their sums merge into $A + \overline{B}$. The patterns 010 and 110 differ only in A, so their sums merge into $\overline{B} + C$. Together these two sums cover all three off-set patterns, so the function is $(A + \overline{B}) \cdot (\overline{B} + C)$. As a check, the merged form and the original agree: $(A + \overline{B} + C) \cdot (A + \overline{B} + \overline{C}) \cdot (\overline{A} + \overline{B} + C)$ $= (A + \overline{B}) \cdot (\overline{B} + C)$.

Tags: StandardBoolean algebra

Exercise 3.4.5

Starting from the four products that are 1 on the four patterns with A equal to 1, use the uniting theorem twice to show that they add up to $A$.

Hint

Merge them in pairs first, and then merge the two results.

Solution

The products are $A\overline{B}\,\overline{C}$, $A\overline{B}C$, $AB\overline{C}$ and $ABC$. The first two differ only in C and the last two differ only in C, so the first round merges them in pairs. The two results differ only in B, so the second round merges them into A.

Step-by-step simplification; each line names the law used to get from the line above

Expression	Law used
$A\overline{B}\,\overline{C} + A\overline{B}C + AB\overline{C} + ABC$
$= A\overline{B} + AB$	Uniting
$= A$	Uniting

Every variable except A was dropped one round at a time, which is why a group of four neighbors on a map has two fewer variables than a single pattern.

Tags: StandardBoolean algebra

Exercise 3.4.6

Let F be 1 when an odd number of A, B and C are 1, so its on set is 001, 010, 100 and 111. Show that no two on-set patterns are neighbors. What does that tell you about the smallest sum of products for F?

Hint

Flipping one input changes how many of the inputs are 1 by exactly one.

Solution

Flipping one input changes the number of 1s by exactly one, so it turns an odd count into an even count. Every pattern in the on set has an odd count, so each of its three neighbors has an even count and lies in the off set. No two on-set patterns are neighbors.

A product that leaves out a variable is 1 on two patterns that differ only in that variable. If both were on-set patterns they would be neighbors, so no product of F's smallest form can leave a variable out. Every product keeps all three variables and covers one pattern, and the smallest sum of products has four terms: $\overline{A}\,\overline{B}C +$ $\overline{A}B\overline{C} +$ $A\overline{B}\,\overline{C} +$ $ABC$. The quiz above confirms the count of four with the same function.

Tags: ChallengeBoolean algebra