1.3 Three equivalent forms: circuit, expression, truth table

Why this matters

Designers describe the same circuit in three ways and move between them all day: a drawing of gates, an algebra-style expression, and a table of every case. Each is best at something. A drawing shows how the parts are connected, an expression is quick to write and to manipulate, and a table is the unambiguous statement of what the circuit must do. Being able to translate between them is how you check a design, because you can work out the same function two ways and compare.

Learning goals

• Turn a sentence describing a rule into an expression, a circuit and a truth table.
• Read the expression of a circuit by following signals through its gates.
• Draw the circuit of an expression using AND, OR and NOT gates.
• Build the truth table of a circuit or an expression by evaluating it for every input row.
• Explain why a truth table does not directly give a small circuit.

Intuition first

A rule for a door chime can be told as a sentence ("sound the chime when the key is in and the door is open"), as a wiring diagram, or as a list of every combination of key and door with the chime's answer next to it. All three say the same thing. If you have written code, you know the same situation: one function can be a formula, a chain of operations, or a lookup table with one entry for each possible argument. They compute the same result and differ in how they are built and how much they cost.

The analogy breaks in one place. In software, "cost" means instructions and memory. For a circuit it means gates, wires and the time signals take to pass through them, and those are the costs the next two chapters teach you to reduce.

Definition 1.3.1(Boolean expression).

A Boolean expression combines signal names with NOT, AND and OR (and sometimes XOR) into a single value, 0 or 1. Given a value for every signal, the expression can be evaluated.

Definition 1.3.2(equivalent descriptions).

Two descriptions of a circuit, whatever their form, are equivalent when they give the same output for every setting of the inputs.

Moving between the forms

Each translation has a method. Some are easy, and one of them is not.

From	To	Method
Sentence	Expression	Decide which words mean AND, OR and NOT, and write the structure down.
Circuit	Expression	Write the output of each gate as an expression of its inputs, working from the inputs toward the output.
Expression	Circuit	Draw one gate for each operator, starting with the operator that is applied last.
Circuit or expression	Table	Evaluate it for every row of inputs.
Table	Expression	Write a product for each row where the output is 1, and add the products (a sum of products). A product of sums, built from the rows where the output is 0, also works; Section 2.2 shows both.
Table	Circuit	Possible through an expression, but getting a small circuit takes more thought.

The last two rows are previews. Section 2.2 treats reading an expression off a table properly, and the idea of making a circuit small is the subject of the next chapters.

Three indicators on a dashboard

A car's dashboard lights are driven by small circuits that read sensors. Here are the signals we will use. Each has a long name and a short one, and the short ones are used in expressions and drawings.

Short name	Long name	Meaning
DDO	DriverDoorOpen	the driver's door is open
PDO	PassengerDoorOpen	the passenger's door is open
DA	DoorAjar	the door warning light is on
LO	LightsOn	the headlights are on
HBO	HighBeamOn	the high beam is selected
HBI	HighBeamIndicator	the high-beam indicator is on
DBI	DriverBeltIn	the driver's belt is fastened
PBI	PassengerBeltIn	the passenger's belt is fastened
P	Passenger	a passenger is in the seat
SBL	SeatBeltLight	the seat belt warning light is on

Example 1.3.1(the door warning light).

The warning light is on when either door is open. "Either" means at least one, so the connecting word is OR. The expression is $\mathrm{DDO} + \mathrm{PDO}$, and the table lists the four settings of the two doors.

Truth table with 2 inputs (DDO, PDO) and output DA; 4 rows in ascending binary order, DDO most significant

$\mathrm{DDO}$	$\mathrm{PDO}$	$\mathrm{DA}$
0	0	0
0	1	1
1	0	1
1	1	1

The circuit has one gate, since the expression has one operator.

A logic schematic with inputs DDO and PDO and output DA.

OR gate g1: inputs DDO and PDO; output DA.

It agrees with the function logic:ch01/door-ajar#DA.

Description: An OR gate with inputs DDO and PDO and output DA.

Figure 1.3.1. The door warning light: an OR gate on the two door signals.

Example 1.3.2(the high-beam indicator).

The indicator is on when the lights are on and the high beam is selected. Both must hold, so the word is AND. The expression is $\mathrm{LO} \cdot \mathrm{HBO}$. A dot separates the two names because they are longer than one letter.

Truth table with 2 inputs (LO, HBO) and output HBI; 4 rows in ascending binary order, LO most significant

$\mathrm{LO}$	$\mathrm{HBO}$	$\mathrm{HBI}$
0	0	0
0	1	0
1	0	0
1	1	1

A logic schematic with inputs LO and HBO and output HBI.

AND gate g1: inputs LO and HBO; output HBI.

It agrees with the function logic:ch01/high-beam#HBI.

Description: An AND gate with inputs LO and HBO and output HBI.

Figure 1.3.2. The high-beam indicator: an AND gate on the two signals.

Example 1.3.3(the seat belt light).

The light is on when the driver's belt is not fastened, or when a passenger is present and the passenger's belt is not fastened. Break the sentence at its connecting words. The two conditions are joined by OR. The second condition is itself an AND of two things: a passenger is present, and the passenger's belt is not in. "Not fastened" is a NOT on the signal that says a belt is fastened. In symbols the light is $\overline{\mathrm{DBI}} + P \cdot \overline{\mathrm{PBI}}$.

To get the table, try every setting of the three inputs, with DBI as the leftmost column. In the first four rows DBI is 0, so the first term is 1 and the light is on whatever the other inputs are. In the last four rows DBI is 1, and the light is on only when P is 1 and PBI is 0. That is the single row 101.

Truth table with 3 inputs (DBI, PBI, P) and output SBL; 8 rows in ascending binary order, DBI most significant

$\mathrm{DBI}$	$\mathrm{PBI}$	P	$\mathrm{SBL}$
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

The highlighted rows are the five rows where the light is on. The circuit has one gate per operator in the expression: two NOT gates, one AND and one OR.

A logic schematic with inputs DBI, PBI and P and output SBL.

NOT gate n1: input DBI; output n1.

NOT gate n2: input PBI; output n2.

AND gate a1: inputs n2 and P; output n3.

OR gate o1: inputs n1 and n3; output SBL.

It agrees with the function logic:ch01/seat-belt#SBL.

Description: Input DBI goes through a NOT gate to the top input of an OR gate. Inputs PBI and P go to an AND gate, with PBI inverted by a NOT gate first. The AND gate output goes to the other input of the OR gate. The OR output is SBL.

Figure 1.3.3. The seat belt light. The two NOT gates are labeled with the signals they produce.

You can also go the other way, from the circuit back to its expression. Follow the signals through the gates in Figure 1.3.3. The top NOT gate outputs $\overline{\mathrm{DBI}}$. The lower NOT gate outputs $\overline{\mathrm{PBI}}$. The AND gate takes P and that signal, so its output is $P \cdot \overline{\mathrm{PBI}}$. The OR gate adds its two inputs, $\overline{\mathrm{DBI}}$ and $P \cdot \overline{\mathrm{PBI}}$, which gives the expression we started with. When a circuit and an expression describe the same function, one trip through the gates is all it takes to see it.

Drawing a circuit from an expression

Example 1.3.4(from an expression to gates and a table).

Draw the circuit for $AB + \overline{C}$. The operator applied last is the sum, so the output gate is an OR. Its two operands are the product $AB$, which needs an AND gate, and the signal $\overline{C}$, which needs a NOT gate. Each operand becomes a gate that feeds the OR.

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

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

NOT gate g2: input C; output n2.

OR gate g3: inputs n1 and n2; output F.

It agrees with the function logic:ch01/s03-ex-f#F.

Description: Inputs A and B go to an AND gate. Input C goes to a NOT gate. The outputs of the AND gate and the NOT gate go to an OR gate whose output is F.

Figure 1.3.4. The circuit for the expression: an AND gate and a NOT gate feed an OR gate.

For the table, evaluate the expression in every row. The second term is 1 whenever C is 0, which makes F equal to 1 in the four rows with C equal to 0. When C is 1, the first term decides, and it is 1 only in the row where A and B are both 1.

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	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

Why a table is not yet a circuit

Reading an expression off a table works, and it always works. Write one product for each row where the output is 1, with a variable written plain where it is 1 in that row and barred where it is 0, and add the products. For the seat belt table, the five rows give five products:

$\overline{\mathrm{DBI}} \cdot \overline{\mathrm{PBI}} \cdot \overline{P} +$ $\overline{\mathrm{DBI}} \cdot \overline{\mathrm{PBI}} \cdot P +$ $\overline{\mathrm{DBI}} \cdot \mathrm{PBI} \cdot \overline{P} +$ $\overline{\mathrm{DBI}} \cdot \mathrm{PBI} \cdot P +$ $\mathrm{DBI} \cdot \overline{\mathrm{PBI}} \cdot P$

This expression is correct, and it is equivalent to the short one:

$\overline{\mathrm{DBI}} \cdot \overline{\mathrm{PBI}} \cdot \overline{P} +$ $\overline{\mathrm{DBI}} \cdot \overline{\mathrm{PBI}} \cdot P +$ $\overline{\mathrm{DBI}} \cdot \mathrm{PBI} \cdot \overline{P} +$ $\overline{\mathrm{DBI}} \cdot \mathrm{PBI} \cdot P +$ $\mathrm{DBI} \cdot \overline{\mathrm{PBI}} \cdot P$ $= \overline{\mathrm{DBI}} +$ $P \cdot \overline{\mathrm{PBI}}$

But it uses fifteen signal names, and the form we wrote from the sentence uses three. A circuit built row by row would be much larger than the circuit in Figure 1.3.3, and nothing in the table tells you which smaller circuit to build. That is why the arrow from table to circuit is the hard direction, and why the next chapters spend their time on making expressions smaller.

Course conventions

How CSE 369 writes this

This book writes the product of single-letter signals by placing the letters side by side, and the product of longer names with a dot, as in $\mathrm{LO} \cdot \mathrm{HBO}$. The lecture slides often put the dot between single letters too (A·B); both mean AND. A bar over a multi-letter name covers the whole name. Logic courses call a sum of products a disjunctive normal form and a product of sums a conjunctive normal form. This book says sum of products (SoP) and product of sums (PoS), as the course does.

Pitfalls

Common pitfall

• Dropping a NOT or a bubble when turning a circuit into an expression, or putting the bar on the wrong signal. Write the output of each gate as its own expression, in order.
• Turning "or" into AND, or "and" into OR, when translating a sentence. Ask whether both conditions must hold, or either one is enough.
• Trusting an expression after trying a few rows. Evaluate it for every row.
• Treating a circuit read straight from a table as finished. It is correct but usually larger than it needs to be.
• Writing a variable plain in a row's product where it is 0 in that row. Plain means 1 and barred means 0.

Check your understanding

Take the quiz (5 questions)

Which expression is the door warning light, DoorAjar?

$\mathrm{DDO} + \mathrm{PDO}$$\mathrm{DDO} \cdot \mathrm{PDO}$$\overline{\mathrm{DDO}} + \overline{\mathrm{PDO}}$

Which expression is the seat belt light?

$\overline{\mathrm{DBI}} + P \cdot \overline{\mathrm{PBI}}$$\overline{\mathrm{DBI}} + P \cdot \mathrm{PBI}$$\overline{\mathrm{DBI}} \cdot P + \overline{\mathrm{PBI}}$

In how many of the eight rows of the seat belt table is the light on?

543

What is the most reliable way to get the truth table of a circuit? Evaluate the circuit for every row of inputs. Evaluate it for the rows that seem most likely to matter. Count the gates and divide by the number of inputs.

You write one product per row where the output is 1, and add them. What is true of the circuit you get? It is correct, and usually larger than needed. It is correct, and always the smallest possible. It is wrong for the rows where the output is 0.

Exercises

Exercise 1.3.1

Say in words when $\overline{\mathrm{DBI}} \cdot P$ is 1. Is the seat belt light on when it is 1?

Hint

A bar means the signal is 0. A signal written plain is 1. Two signals side by side must both be right.

Solution

The product is 1 when DBI is 0 and P is 1: the driver's belt is not fastened and a passenger is present. The belt signal of the passenger is not mentioned, so it can be either value. The light is on in those rows, because the first term of the seat belt expression, $\overline{\mathrm{DBI}}$, is already 1 whenever the driver's belt is out.

Tags: Warm-upBoolean algebraTruth tables

Exercise 1.3.2

A chime sounds when the key is in the ignition and the door is open, or when the headlights are on and the key has been removed. The inputs are KeyIn, DoorOpen and LightsOn, with KeyIn as the leftmost input. Write the expression, the truth table and the circuit.

Hint

The sentence has two conditions joined by "or". The second one says the key is out, which is a NOT on KeyIn.

Solution

The first condition is KeyIn AND DoorOpen. The second is LightsOn AND the key out, which is LightsOn AND NOT KeyIn. The two are joined by OR:

$\mathrm{KeyIn} \cdot \mathrm{DoorOpen} +$ $\overline{\mathrm{KeyIn}} \cdot \mathrm{LightsOn}$

For the table, the first term is 1 in the two rows with KeyIn and DoorOpen equal to 1. The second term is 1 in the two rows with KeyIn equal to 0 and LightsOn equal to 1. Those are the only rows where the chime sounds, and there are exactly four of them, because no row satisfies both terms.

Truth table with 3 inputs (KeyIn, DoorOpen, LightsOn) and output Chime; 8 rows in ascending binary order, KeyIn most significant

$\mathrm{KeyIn}$	$\mathrm{DoorOpen}$	$\mathrm{LightsOn}$	$\mathrm{Chime}$
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

The expression has two ANDs, one OR and one NOT, so the circuit has two AND gates, one OR gate and one NOT gate on KeyIn. The input KeyIn is used twice, and a dot marks the place where its wire splits.

A logic schematic with inputs DoorOpen, KeyIn and LightsOn and output Chime.

AND gate a1: inputs DoorOpen and KeyIn; output n1.

NOT gate n1: input KeyIn; output n2.

AND gate a2: inputs n2 and LightsOn; output n3.

OR gate o1: inputs n1 and n3; output Chime.

It agrees with the function logic:ch01/s03-chime#Chime.

Description: DoorOpen and KeyIn go to the first AND gate. KeyIn also goes through a NOT gate to the second AND gate, whose other input is LightsOn. The outputs of the two AND gates go to an OR gate whose output is Chime.

Figure 1.3.5. The chime circuit. A dot on the KeyIn wire marks where it splits to feed both the first AND gate and the NOT gate.

Tags: StandardBoolean algebraTruth tablesGates and schematics

Exercise 1.3.3

Find the expression and the truth table of this circuit.

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

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

NOT gate g2: input C; output n2.

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

It agrees with the function logic:ch01/s03-ex-circuit#Out.

Description: Inputs A and B go to an OR gate. Input C goes to a NOT gate. The OR gate and the NOT gate outputs go to an AND gate whose output is Out.

Figure 1.3.6. A circuit with three inputs.

Hint

Name the output of the OR gate and of the NOT gate first. Then write the output of the AND gate in terms of those two.

Solution

The OR gate outputs $A + B$. The NOT gate outputs $\overline{C}$. The AND gate combines them, so the output is $(A + B) \cdot \overline{C}$. The sum needs parentheses, because without them the product would bind only to the nearer signal.

The output is 1 when C is 0 and at least one of A and B is 1.

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

A	B	C	$\mathrm{Out}$
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	0

Rows with C equal to 1 give 0 because the NOT gate output is 0. Among the four rows with C equal to 0, only the first, where A and B are both 0, gives 0.

Tags: StandardGates and schematicsTruth tables

Exercise 1.3.4

Draw the circuit for $\overline{A}B + A\overline{B}$ using NOT, AND and OR gates, and say which single gate of section 1.2 it equals.

Hint

The operator applied last is the sum. Each product needs an AND gate, and each barred letter needs a NOT gate.

Solution

The expression is a sum of two products, so the last gate is an OR. The first product is a NOT on A and an AND with B. The second product is a NOT on B and an AND with A. That takes four gates in front of the OR: two NOT gates and two AND gates.

The two products are 1 in the rows 01 and 10, which are the rows where the inputs differ. That is the table of the XOR gate, so the five-gate circuit computes what one XOR gate does. The whole circuit is drawn below. Dots mark where an input wire splits, and the one place where two wires cross without a dot is not a connection.

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

NOT gate nb: input B; output n1.

NOT gate na: input A; output n2.

AND gate a1: inputs A and n1; output n3.

AND gate a2: inputs n2 and B; output n4.

OR gate o1: inputs n3 and n4; output Out.

It agrees with the function logic:ch01/gate-xor#Out.

Description: Input A goes to the first AND gate, and through a NOT gate to the second AND gate. Input B goes to the second AND gate, and through a NOT gate to the first AND gate. The outputs of the AND gates go to an OR gate whose output is Out.

Figure 1.3.7. An XOR function built from two NOT gates, two AND gates and an OR gate. The vertical wire from A and the horizontal wire from B cross without a dot, so they are not connected.

Tags: StandardGates and schematicsBoolean algebra

Exercise 1.3.5

This table has three rows where Out is 1. Write an expression for it with one product for each of those rows, and check it against the table.

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

A	B	C	$\mathrm{Out}$
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

Hint

For each row where Out is 1, write the product of all three inputs: plain where the input is 1 in that row, barred where it is 0.

Solution

Out is 1 in the rows 010, 100 and 111. In row 010, A is 0, B is 1 and C is 0, so its product is $\overline{A}B\overline{C}$. Row 100 gives $A\overline{B}\,\overline{C}$, and row 111 gives $ABC$. The sum is

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

Each product is 1 in exactly one row, and the sum is 1 exactly in those three rows.

Tags: StandardTruth tablesBoolean algebra