2.1 Boolean algebra

Why this matters

A circuit that is built from a messy expression costs more gates, more wiring and more delay than one built from a tidy expression for the same function. Boolean algebra is the toolbox for going from the messy form to the tidy one without changing what the circuit does. Every later technique in this chapter, from minimizing to NAND-only designs, is a few of these laws applied in a useful order.

Learning goals

• State each basic law of Boolean algebra, including the distributive law that has no counterpart in ordinary arithmetic.
• Check a proposed law or a proposed simplification by trying every input row.
• Read the expression that a circuit computes, gate by gate.
• Simplify an expression one step at a time, naming the law that justifies each step.
• Spot a step that changes the function.

Intuition first

In ordinary algebra a variable stands for any number, and you rewrite expressions using facts such as $a(b+c)=ab+ac$. Boolean algebra is the same game with two differences. A variable can only be 0 or 1, and the operations are OR (written $+$), AND (written as a product) and NOT (an overbar).

Because there are only two values, a claim about an expression with $n$ variables can be settled by brute force: try all $2^n$ combinations. A law is a claim that has survived that test for every choice of its variables. Here is the test for the law that surprises most people, in which OR distributes over AND. The two columns are the two sides:

Truth table with 3 inputs (X, Y, Z) and outputs L, R; 8 rows in ascending binary order, X most significant

X	Y	Z	L	R
0	0	0	0	0
0	0	1	0	0
0	1	0	0	0
0	1	1	1	1
1	0	0	1	1
1	0	1	1	1
1	1	0	1	1
1	1	1	1	1

Description: A truth table with inputs X, Y and Z and two outputs, L and R. The eight rows give the same value in L and R on every row.

Figure 2.1.1. Both sides of X + YZ = (X + Y)(X + Z), row by row. The columns L and R are identical.

Every row agrees, so the law holds. Ordinary arithmetic has no such law: with numbers, $2+3\cdot 4$ is 14 but $(2+3)(2+4)$ is 30. The brute-force test is also why you can trust the laws below even without a proof: each one is a small table.

What makes the laws useful is that rewriting never changes the function, only its shape. If two expressions agree on every row, you can build whichever one is cheaper.

Definition 2.1.1(equivalent expressions).

Two Boolean expressions are equivalent when they give the same output for every combination of input values. Rewriting an expression into an equivalent one is always allowed. A step that produces a non-equivalent expression is an error, however plausible it looks.

Definition 2.1.2(literal).

A literal is a variable or its complement: $A$ and $\overline{A}$ are two different literals of the variable $A$. The number of literals is one measure of how big an expression is. Section 2.3 uses the related count of gate inputs when it compares circuits.

The laws

Each law below is a pair of expressions that a program has checked equal on every input row. They come in pairs: swap every $+$ with a product, and every 0 with a 1, and a law turns into its partner. The Section 1 review calls the null law "domination" and the complement law "negation", and lists the six absorption identities together under the one heading "absorption".^{F (fact ch02/law-names)} This book says null and complement, with the other name in parentheses in the tables below, and uses "absorption" as the one name for all six. The derivations print the same names: Null, Complement, Double negation for the law that removes two bars, and Absorption for all six absorption identities.

Constants and repetition. These say what happens when one operand is a constant or when a variable meets itself.

Law	The OR form	The AND form
Identity	$X + 0 = X$	$X \cdot 1 = X$
Null (domination)	$X + 1 = 1$	$X \cdot 0 = 0$
Idempotent	$X + X = X$	$XX = X$
Complement (negation)	$\overline{X} + X = 1$	$\overline{X}X = 0$

A variable and its own complement always disagree, so exactly one of them is 1. That is why $\overline{X}+X$ is 1 and $\overline{X}X$ is 0. The last basic law has no pair: $\overline{\overline{X}} = X$ is the double negation law.

Order and grouping. These are the ones from ordinary algebra.

Law	The OR form	The AND form
Commutative	$X + Y = Y + X$	$XY = YX$
Associative	$X + Y + Z = X + Y + Z$	$XYZ = XYZ$

Because grouping never matters, a long run of ANDs or of ORs is written without parentheses, and a derivation on this page treats it as one product or one sum.

Distribution. AND distributes over OR, as in ordinary algebra, and OR also distributes over AND, which is the new one:

Law	Form
Distributive, AND over OR	$X \cdot (Y + Z) = XY + XZ$
Distributive, OR over AND	$X + YZ = (X + Y) \cdot (X + Z)$

Read the second one in the direction that shrinks an expression: whenever two sums share a variable, you can pull it out.

Absorption. These six let a term or a variable disappear because the rest of the expression already covers it.

Law	The OR form	The AND form
Absorb a product	$X + XY = X$	$X \cdot (X + Y) = X$
Merge two terms	$XY + X\overline{Y} = X$	$(X + Y) \cdot (X + \overline{Y}) = X$
Drop a complement	$X + \overline{X}Y = X + Y$	$X \cdot (\overline{X} + Y) = XY$

The middle row is the pair that Chapter 3 calls the uniting theorem. Try the OR form of the third row on the numbers 0 and 1 if it looks wrong: when $X$ is 1 both sides are 1, and when $X$ is 0 both sides become $Y$. The derivations below label all six as Absorption.

Reading a circuit

Before simplifying an expression you usually have to get it from somewhere. A circuit gives it to you: write the output of each gate in terms of its inputs, working from the inputs to the output.

Example 2.1.1(a five-gate circuit that is too big).

Look at Figure 2.1.2. B and C each feed several gates, and the dots mark where a wire splits. The AND gate at the top takes A and B, so its output is $AB$. The OR gate below it takes B and C and gives $B + C$. The AND gate at the bottom takes C and B and gives $BC$. The AND gate on the right takes those two and gives $B \cdot C \cdot (B + C)$. The OR gate at the end combines the top product with that, so the output is $AB + B \cdot C \cdot (B + C)$.

A logic schematic with inputs A, B and C and output Q.

AND gate g1: inputs A and B; output n1.

OR gate g2: inputs B and C; output n2.

AND gate g3: inputs C and B; output n3.

AND gate g4: inputs n2 and n3; output n4.

OR gate g5: inputs n1 and n4; output Q.

It computes Q = A and B or B and C and (B or C).

Description: A circuit with inputs A, B and C and output Q: an AND gate on A and B, an OR gate on B and C, an AND gate on C and B, an AND gate whose inputs are the outputs of the OR gate and the lower AND gate, and a final OR gate that combines the top AND gate with that last AND gate.

Figure 2.1.2. Five two-input gates. The output Q is the OR of the top AND gate and the AND of the other two outputs.

The next step is to see whether all five gates are needed. Each line below follows from the one above it by the law named beside it.

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

Expression	Law used
$AB + B \cdot C \cdot (B + C)$
$= AB + BCB + BCC$	Distributive
$= AB + BBC + BCC$	Commutative
$= AB + BC + BCC$	Idempotent
$= AB + BC + BC$	Idempotent
$= AB + BC$	Idempotent
$= BA + BC$	Commutative
$= B \cdot (A + C)$	Distributive

The first step multiplies out the factor $(B+C)$. The second reorders the first long product so that the two copies of B sit together, and the next two steps use $XX = X$ on $BB$ and then on $CC$. The fifth step uses $X + X = X$ on the two equal terms. The last two steps swap $AB$ to $BA$ and pull the common B out.

The result needs only an OR gate and an AND gate, as in Figure 2.1.3, so two gates replace five. The program that drew both figures checked each against the expression above, so the two circuits are known to compute the same function.

A logic schematic with inputs A, C and B and output Q.

OR gate g1: inputs A and C; output n1.

AND gate g2: inputs n1 and B; output Q.

It computes Q = B and (A or C).

Description: A circuit with inputs A, B and C and output Q: an OR gate on A and C feeds an AND gate whose other input is B.

Figure 2.1.3. The same function from two gates.

Example 2.1.2(simplifying with a bar over a sum).

Now a circuit with inverted signals. In Figure 2.1.4 a NOR gate takes A and B, an AND gate takes A and an inverted B, a second AND gate takes an inverted C and an inverted D, and a three-input OR gate combines the three outputs.

A logic schematic with inputs A, B, C and D and output X.

NOT gate n1: input B; output n2.

NOT gate n2: input C; output n4.

NOT gate n3: input D; output n5.

NOR gate g1: inputs A and B; output n1.

AND gate g2: inputs A and n2; output n3.

AND gate g3: inputs n4 and n5; output n6.

OR gate g4: inputs n1, n3 and n6; output X.

It computes X = not (A or B) or A and not B or not C and not D.

Description: A circuit with inputs A, B, C and D and output X. A NOR gate takes A and B. An AND gate takes A and the output of an inverter on B. A second AND gate takes the outputs of an inverter on C and an inverter on D. A three-input OR gate combines the three gate outputs.

Figure 2.1.4. A NOR gate, an AND gate with an inverted B, and an AND gate with two inverted inputs, feeding one OR gate.

The output is $\overline{A + B} + A\overline{B} + \overline{C}\,\overline{D}$. Notice the first term: the bar sits over the whole sum $A+B$, because the NOR gate inverts the OR of its inputs. We will simplify it. The first step needs DeMorgan's law, which turns a bar over a sum into a product of bars. Section 2.4 gives that law its own treatment; here we only use it in this direction.

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

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

The first step replaces the bar over $A+B$ by $\overline{A}\,\overline{B}$. The second factors $\overline{B}$ out of the first two terms, and the third uses $\overline{A} + A = 1$. The fourth drops the 1. The fifth reads $\overline{C}\,\overline{D}$ backwards as a bar over $C+D$, and the last step does the same trick on $\overline{B}+\overline{(C+D)}$, which is a bar over the product $B(C+D)$. The two circuits are Figure 2.1.4 and Figure 2.1.5: seven gates and inverters became two gates.

A logic schematic with inputs B, C and D and output X.

OR gate g1: inputs C and D; output n1.

NAND gate g2: inputs B and n1; output X.

It computes X = not (B and (C or D)).

Description: A circuit with inputs B, C and D and output X: an OR gate on C and D feeds a NAND gate whose other input is B.

Figure 2.1.5. The simplified function: an OR gate feeding a NAND gate.

The final form has a single bar over a product, the whole of $B(C+D)$. Writing a bar over each letter instead would give a different function. Section 2.4 explains why.

A step that looks harmless

Every law above is an equality, so a step is only as good as the law behind it. The most common way to go wrong is to use a real law on the wrong thing.

You want to split the term $ABC$ in two. Which of these rewrites keeps the function the same?

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

Example 2.1.3(five products that collapse to two).

This function of three variables is a sum of five products. Each step is one law, and the program checks that each line equals the one above it. A step that, like the first choice above, swapped $ABC$ for $AB(C+\overline{C})$ would be rejected.

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

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

The first step applies $X + XY = X$ twice, once with C in the role of Y and once with $\overline{C}$ in that role, because $A\overline{B}$ already covers both of those products. The answer is $A\overline{B} + BC$.

Course conventions

How CSE 369 writes this

NOT is an overbar, never a prime or a tilde: $\overline{A}$. AND is written by putting letters next to each other ($AB$) or with a centered dot, and OR is $+$. The complement of a product is one bar over the whole product, so $\overline{AB}$ and $\overline{A}\,\overline{B}$ are different expressions. In this book every expression is drawn from a parsed expression, so each bar covers exactly the letters it should.

Pitfalls

Common pitfall

• Putting a bar on each letter when the bar belongs over a whole product or sum. $\overline{AB}$ and $\overline{A}\,\overline{B}$ differ, and so do $\overline{A+B}$ and $\overline{A}+\overline{B}$. Try one input row on each form when you are unsure.
• Dropping a complement that is not covered. $A+\overline{A}B$ is $A+B$, not $A$. The bar goes away only because the term is absorbed into the plain sum.
• Splitting a term by multiplying only part of it by $X+\overline{X}$. The factor must multiply the whole term, or the function changes.
• Applying the arithmetic distributive law to OR, so that $X + YZ$ becomes $XY + XZ$. Those are different functions. The correct law is $X + YZ = (X + Y) \cdot (X + Z)$.
• Naming a law that does not match the step. Check the named law against the actual change: a step that merely reorders letters is Commutative, a step that removes a repeated letter is Idempotent.

Check your understanding

Take the quiz (5 questions)

Which of these is equal to $A+\overline{A}B$?

$A + B$$A$$AB$

Which of these is equal to $(A+B)(A+\overline{B})$?

$A$$A + B$$AB$

How many gates does the five-gate circuit of the first example use?

546

Which of these is a simplified form of the output Q of that circuit?

$B \cdot (A + C)$$A + BC$$AB + C$

Which of these is equal to the output X of the second example circuit?

$\overline{B \cdot (C + D)}$$\overline{B} + \overline{C} + \overline{D}$$\overline{B}\,\overline{C}\,\overline{D}$

Exercises

Exercise 2.1.1

Show with a truth table that $X+YZ$ and $(X+Y)(X+Z)$ are equal. Then say, in a sentence, why the rows where X is 1 are easy.

Hint

Build the table with the eight rows of X, Y and Z, and add one column for each side. Ask what each side is when X is 1.

Solution

The table of both sides is the one in the intuition section, and the L and R columns agree on every row. When X is 1 the left side is $1 + YZ$, which is 1 by the null law. The right side is $(1 + Y) \cdot (1 + Z)$, and each factor is 1 by the null law, so the product is 1 as well. When X is 0 the left side is $0 + YZ$ and the right side is $(0 + Y) \cdot (0 + Z)$. Both reduce to $YZ$ by the identity law.

Truth table with 3 inputs (X, Y, Z) and outputs L, R; 8 rows in ascending binary order, X most significant

X	Y	Z	L	R
0	0	0	0	0
0	0	1	0	0
0	1	0	0	0
0	1	1	1	1
1	0	0	1	1
1	0	1	1	1
1	1	0	1	1
1	1	1	1	1

Description: A truth table with inputs X, Y and Z and outputs L and R, with the row where X is 1 and Y and Z are 0 highlighted. L and R agree on every row.

Figure 2.1.6. The truth table of both sides again, with row 100 marked.

Tags: Warm-upBoolean algebraTruth tables

Exercise 2.1.2

Write the output Z of Figure 2.1.7 as an expression, then simplify it step by step, naming the law for each step.

A logic schematic with inputs A and B and output Z.

NAND gate g1: inputs A and B; output n1.

OR gate g2: inputs A and B; output n2.

AND gate g3: inputs n1 and n2; output Z.

It agrees with the function logic:ch02/s01-ex-circuit#Z.

Description: A circuit with inputs A and B and output Z: a NAND gate on A and B and an OR gate on A and B both feed an AND gate.

Figure 2.1.7. A NAND gate and an OR gate on the same two inputs feed an AND gate.

Hint

The NAND gate's output has a bar over the whole product. Replace it with sums first, then multiply out.

Solution

The NAND gate gives $\overline{AB}$ and the OR gate gives $A+B$, so Z is their product. First turn the bar into sums, then distribute twice, then use the complement law on the two terms that contain a variable and its complement.

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

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

The result is $\overline{B}A + \overline{A}B$, which is the exclusive-or of A and B. The NAND-and-OR circuit is another way to build it.

Tags: StandardBoolean algebraGates and schematics

Exercise 2.1.3

Simplify $(A + B) \cdot (A + \overline{B}) \cdot C$ and name the law.

Hint

Look at the first two factors only. They differ in one variable.

Solution

The first two factors have the shape $(X+Y)(X+\overline{Y})$ with $X=A$ and $Y=B$, which is X by absorption.

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

Expression	Law used
$(A + B) \cdot (A + \overline{B}) \cdot C$
$= AC$	Absorption

The result is $AC$. The circuit for the original expression needs three gates plus an inverter, and the result needs one gate.

Tags: StandardBoolean algebra

Exercise 2.1.4

A classmate simplifies $A+\overline{A}B$ to $A$ and says "the $\overline{A}B$ is covered by $A$". Find one input row where the two expressions differ, and give the correct simplification.

Hint

The classmate's reasoning needs A to be 1. What if A is 0?

Solution

Take A = 0 and B = 1. The expression $A + \overline{A}B$ is 1 there, because the product $\overline{A}B$ is 1, but A alone is 0. The term $\overline{A}B$ is not covered by $A$: it is exactly the case that $A$ does not cover. The correct law is $X + \overline{X}Y = X + Y$, so the answer is $A + B$.

Tags: StandardBoolean algebra

Exercise 2.1.5

Simplify $AB\overline{C} +$ $A\overline{B}\,\overline{C} +$ $\overline{A}B\overline{C}$ to a product of a sum and a single literal, naming the law for each step.

Hint

All three terms contain the same literal. Factor it out first, then look at what is left.

Solution

All three terms contain $\overline{C}$. Factoring it out leaves the sum $AB+A\overline{B}+\overline{A}B$. The first two terms merge into $A$, and then $A+\overline{A}B$ becomes $A+B$.

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

Expression	Law used
$AB\overline{C} +$ $A\overline{B}\,\overline{C} +$ $\overline{A}B\overline{C}$
$= (AB + A\overline{B} + \overline{A}B) \cdot \overline{C}$	Distributive
$= (A + \overline{A}B) \cdot \overline{C}$	Absorption
$= (A + B) \cdot \overline{C}$	Absorption

The result is $(A + B) \cdot \overline{C}$: the function is 1 exactly when C is 0 and at least one of A and B is 1.

Tags: ChallengeBoolean algebra