1.2 Logic gates and truth tables

Why this matters

Every digital circuit, from a door alarm to a processor, is built from a few kinds of gates. A truth table is the most complete way to say what a circuit does, because it lists the output for every possible input. Gates and tables are the vocabulary of the rest of the book, so the symbols, the notation and the row order on this page are used on every page after it.

Learning goals

• Recognize the seven gates by their symbols and state the output of each from its inputs.
• Write the expression for a gate in the book's notation, with the overbar for NOT.
• Lay out a truth table with the right number of rows, in the row order this book uses.
• Fill in a table with several outputs, such as the one-bit adder.
• Count the rows of a table, and the number of different functions, for any number of inputs.

Intuition first

Suppose you have to test a function that takes two booleans. There are only four pairs of arguments, so you can write all four down, with the result you expect for each. That list is a truth table. In everyday software you almost never test a function this way, because two 32-bit integers have far too many combinations to list. A gate has one bit per input, so the list is short enough to write out, and for a circuit it is more than a test: it is a complete description, because nothing except the inputs decides the outputs.

A software function that reads a global variable or the clock can return different results on two calls with the same arguments, and that is exactly what a gate cannot do. This is why a table can say everything about a gate: there is no hidden state for it to leave out.

Definition 1.2.1(truth table).

A truth table lists, for every combination of input values, the output values of a circuit. Each combination is one row. The inputs are written to the left of a vertical rule, and the outputs to the right of it.

The gates

A gate is drawn with a distinctive shape. Its inputs come in on the left and its output leaves on the right. A small circle, called a bubble, on a symbol means NOT: the signal is inverted at that point. Below, each gate is drawn above its table. Each drawing is checked against its table, so the picture and the numbers cannot disagree.

A logic schematic with input A and output Out.

NOT gate g1: input A; output Out.

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

Truth table with 1 inputs (A) and output Out; 2 rows in ascending binary order, A most significant

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

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

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

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

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

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

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

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

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

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

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

Description: Three gate symbols, each above its table. NOT is a triangle with a bubble on its output, with one input A. AND and OR each have inputs A and B and one output Out. The tables list Out for every row.

Figure 1.2.1. NOT, AND and OR, each drawn above its truth table.

• NOT has one input, and its output is the opposite of it.
• AND is 1 only when every input is 1.
• OR is 1 when at least one input is 1.

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

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

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

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

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

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

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

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

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

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

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

XOR gate g1: inputs A and B; output Out.

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

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

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

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

XNOR gate g1: inputs A and B; output Out.

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

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

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

Description: Four gate symbols, each above its table, each with inputs A and B and one output Out. NAND and NOR look like AND and OR with a bubble on the output. XOR looks like OR with a second curved line at the back. XNOR is XOR with a bubble on the output.

Figure 1.2.2. NAND, NOR, XOR and XNOR, each drawn above its truth table.

• NAND is an AND followed by a NOT, so it is 0 only when every input is 1.
• NOR is an OR followed by a NOT, so it is 1 only when every input is 0.
• XOR, the exclusive OR, is 1 when its two inputs differ. It differs from OR in one row only, the row where both inputs are 1.
• XNOR is a NOT after an XOR, so it is 1 when its two inputs are equal.

The bubble is the whole difference between AND and NAND, OR and NOR, and XOR and XNOR. A bubble can also sit on an input, which inverts the signal as it enters the gate. Chapter 2 uses input bubbles.

AND, OR, NAND and NOR can have more than two inputs, and the descriptions above hold for any number of them. The case of XOR needs a warning. Writing the XOR operation between three signals gives 1 when an odd number of them are 1. That is not the same as "exactly one", and the two answers differ in the row where all three are 1.

Writing a gate as an expression

Boolean notation writes each gate as an expression of its inputs. The rules are short.

• NOT is a bar over the signal: $\overline{A}$.
• AND is the product: $AB$. Letters written side by side mean AND, and a dot separates longer names.
• OR is the sum: $A + B$.
• XOR is a circled plus: $A \oplus B$.
• NAND, NOR and XNOR are a bar over the whole expression of the gate they negate: $\overline{AB}$, $\overline{A + B}$ and $\overline{A \oplus B}$.

The last rule hides a trap, because a bar over a product and a bar over each letter are different things.

Example 1.2.1(two bars, two functions).

Compare a bar over the whole product, $\overline{AB}$, with a bar over each letter, $\overline{A}\,\overline{B}$. The table shows both for every setting of A and B.

Truth table with 2 inputs (A, B) and outputs OneBar, TwoBars; 4 rows in ascending binary order, A most significant

A	B	$\overline{AB}$	$\overline{A}\,\overline{B}$
0	0	1	1
0	1	1	0
1	0	1	0
1	1	0	0

The first column is 0 only in the row where A and B are both 1, which is the NAND table. The second column is 1 only in the row where A and B are both 0, which is the NOR table. A bar covers exactly what is under it, so check how far it reaches.

Many inputs, many outputs

A table can have as many input columns as a circuit has inputs. Each input doubles the number of combinations, so a table with $n$ inputs has $2^n$ rows. A second fact follows. In every row the output is either 0 or 1, and the rows are filled in independently, so there are $2^{2^n}$ ways to fill in a table with $n$ inputs, and each way is a different function.

Inputs $n$	Rows $2^n$	Different functions $2^{2^n}$
1	2	4
2	4	16
3	8	256
4	16	65,536
5	32	4,294,967,296

With one input there are two rows and four functions, and you can write them all down. Only one of them, Flip, is one of the seven gates on this page.

Truth table with 1 inputs (A) and outputs Zero, Same, Flip, One; 2 rows in ascending binary order, A most significant

A	$\mathrm{Zero}$	$\mathrm{Same}$	$\mathrm{Flip}$	$\mathrm{One}$
0	0	0	1	1
1	0	1	0	1

The column Zero ignores its input and gives 0, and One ignores it and gives 1. The column Same copies the input, which is just a wire. The column Flip is the NOT gate. With two inputs there are sixteen functions, and the gates above, AND, OR, NAND, NOR, XOR and XNOR, are six of them.

Example 1.2.2(a three-input vote).

Three people vote on a motion, and it passes when at least two vote yes. Call the votes A, B and C, with 1 for yes, and let Out be 1 when the motion passes. Three inputs give eight rows. In each row, count the 1s on the left and write 1 on the right when there are at least two.

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

The highlighted rows are the ones with at least two 1s: 011, 101, 110 and 111. The remaining four rows have at most one 1 and give 0. Rows 000, 001, 010 and 100 are all 0 because a single yes is not enough.

A circuit can also have several outputs. Each output column is a separate function of the same inputs, and a table with two outputs is two tables that share their input columns.

Example 1.2.3(adding two one-bit numbers).

Adding two bits gives 0, 1 or 2, which is written in two bits: a carry bit on the left and a sum bit on the right. The outputs are Carry and Sum.

Truth table with 2 inputs (A, B) and outputs Carry, Sum; 4 rows in ascending binary order, A most significant

A	B	$\mathrm{Carry}$	$\mathrm{Sum}$
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

Carry is 1 only in the last row, so it is an AND of the inputs: $AB$. Sum is 1 when exactly one input is 1, so it is an XOR: $A \oplus B$. This is the half adder from section 1.1, with the outputs written as Carry and Sum, carry first, in the order the two bits of the result are written.

In SystemVerilog

The operators of the language correspond to the gates one to one. This module has one output for each gate, so each line can be compared with a symbol above.

gate_operators.sv

// The seven gates as operators. A NOT gate has one input, so y_not looks only at A.
module gate_operators(
  input logic A, B,
  output logic y_not, y_and, y_or, y_nand, y_nor, y_xor, y_xnor
);
  assign y_not = ~A;
  assign y_and = A & B;
  assign y_or = A | B;
  assign y_nand = ~(A & B);
  assign y_nor = ~(A | B);
  assign y_xor = A ^ B;
  assign y_xnor = ~(A ^ B);
endmodule

The symbol ~ is NOT, & is AND, | is OR and ^ is XOR. Here NAND, NOR and XNOR are each written as a NOT around the operator they negate. The book's tools ran this module on every setting of A and B and compared all seven outputs with a table of the seven functions. Section 1.4 shows another way to write gates, as named gate primitives.

Course conventions

How CSE 369 writes this

In CSE 369 we list the rows of a table in ascending binary order, with the first-listed input as the leftmost bit. For inputs A, B and C the rows are 000, 001, 010, 011, 100, 101, 110 and 111, and the row after 011 is 100. Outputs that may be either value, which come up later, are written X. NOT is an overbar, never a prime or a hook symbol, and a bar over several letters covers all of them. AND is written by placing letters side by side or with a dot, OR with a plus, and XOR with a circled plus. The lectures draw NOT, AND, OR, NAND, NOR and XOR with the distinctive shapes shown here. The lectures name XNOR in words and in code, as ~(a ^ b), but never draw its symbol or write it in Boolean notation. This book writes it as a bar over an XOR and draws it as an XOR with a bubble.

Pitfalls

Common pitfall

• Putting a bar over each letter of a product when it belongs over the whole product, or the reverse. The two functions differ.
• Reading XOR as OR and writing 1 in the row where both inputs are 1. XOR gives 0 there.
• Taking an XOR of three inputs to mean "exactly one is 1". The XOR of three signals is 1 when an odd number of them are 1, so it is also 1 when all three are.
• Giving a table for $n$ inputs $2n$ or $n^2$ rows. It has $2^n$.
• Listing the rows in some other order, or reading the first-listed input as the least significant bit.

Check your understanding

Take the quiz (5 questions)

Which expression gives the output of a NAND gate with inputs A and B?

$\overline{AB}$$\overline{A}\,\overline{B}$$AB$

Which expression gives the output of an XNOR gate?

$\overline{A \oplus B}$$\overline{\overline{A} \oplus B}$$A \oplus B$

In the table for the three-input majority function, how many rows have Out equal to 1?

435

For how many rows is the XOR of three inputs, $A \oplus B \oplus C$, equal to 1?

431

In a table with inputs A, B and C, which row comes right after 011? 100 111 010

Exercises

Exercise 1.2.1

A gate with three inputs has this table. Which gate is it? Draw it.

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

Hint

Look at the one row that is different from all the others, and ask which gate has a single odd row.

Solution

The output is 0 only when A, B and C are all 1, and 1 in the other seven rows. An AND gate would be 1 only in that row, so this is its opposite: a NAND gate with three inputs.

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

NAND gate g1: inputs A, B and C; output Out.

It agrees with the function logic:ch01/s02-mystery#Out.

Description: A NAND gate with three inputs A, B and C and one output Out.

Figure 1.2.3. A three-input NAND gate.

Tags: Warm-upGates and schematicsTruth tables

Exercise 1.2.2

How many rows does a truth table with six inputs have? How many rows have the first input equal to 1? Then say how many different functions of two inputs there are.

Hint

Each extra input doubles the number of rows. For the second part, half of all rows have the first input equal to 1.

Solution

Six inputs give $2^6 = 64$ rows. Any one input is 1 in exactly half of them: every row with it equal to 0 has a partner, the same in every other column, with it equal to 1. So 32 rows have the first input equal to 1. Two inputs give four rows, and each row's output can be 0 or 1, so there are $2^4 = 16$ functions.

Tags: Warm-upTruth tables

Exercise 1.2.3

Write the truth table of $A \oplus B \oplus C$, the XOR of three inputs. Then say why it is not the same as "exactly one of A, B, C is 1".

Hint

Work out $A \oplus B$ first for each row of A and B, and then XOR the result with C.

Solution

Take $A \oplus B$ first: it is 1 when A and B differ. Then XOR it with C, which is 1 when the two values differ.

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

The result is 1 in the rows with an odd number of 1s: the three rows with a single 1, and the row 111. In row 111 $A \oplus B$ is 0, and 0 XOR 1 is 1. "Exactly one" would give 0 there, and so the two rules differ in that one row.

Tags: StandardTruth tablesGates and schematics

Exercise 1.2.4

Compare two one-bit numbers A and B. The output Gt is 1 when A is larger than B, Eq is 1 when they are equal, and Lt is 1 when A is smaller. Write the table, and write each output as an expression.

Hint

With one bit each, A is larger than B in only one row. Check which row, and which input is 1 in it.

Solution

A one-bit number is larger than another only when it is 1 and the other is 0, so Gt is 1 in the row where A is 1 and B is 0. By the same reasoning Lt is 1 in the row where A is 0 and B is 1. Eq is 1 in the two rows where A and B are equal.

Truth table with 2 inputs (A, B) and outputs Gt, Eq, Lt; 4 rows in ascending binary order, A most significant

A	B	$\mathrm{Gt}$	$\mathrm{Eq}$	$\mathrm{Lt}$
0	0	0	1	0
0	1	0	0	1
1	0	1	0	0
1	1	0	1	0

Gt is 1 when A is 1 and B is not: $A\overline{B}$. Lt is 1 when B is 1 and A is not: $\overline{A}B$. Eq is 1 when the inputs are equal, which is the XNOR: $\overline{A \oplus B}$. In every row exactly one of the three is 1.

Tags: StandardTruth tablesGates and schematics

Exercise 1.2.5

Four inputs A, B, C and D each say whether a sensor is on. An output Out is 1 when at least three of the four sensors are on. How many rows does the table have, and in how many is Out equal to 1? Write the table.

Hint

Sixteen rows is a lot to write blindly. List the rows with exactly three 1s, then the row with four.

Solution

Four inputs give 16 rows. A row has exactly three 1s when one input is 0, and there are four ways to choose which one, so four rows. One more row, 1111, has four 1s. That makes five rows with Out equal to 1.

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

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

Tags: StandardTruth tables