Logic Gates and Truth Tables
Read the symbol and the truth table of every basic gate, and write the truth table of a small circuit.
You Will Be Able To
- Name the eight basic gates from a symbol or a truth table.
- Write the truth table of a gate with three or more inputs.
- List the 16 functions of two inputs.
- Find the output of a small circuit for every input row.
- Lesson
- G2.2
- Time
- 22 min
- Runs on
- Your browser
- Check
- 5 questions
A stair light has three switches. The designer wanted the lamp on when exactly one switch is up, and used one three-input XOR gate. With all three switches up, the lamp went on.
- Cycle 1
One input is 1. Both columns give 1.
- Cycle 3
Two inputs are 1. Both columns give 0.
- Cycle 7
All three inputs are 1. "Exactly one" gives 0, but the XOR gate gives 1. Three is an odd number.
Measured on the simulator with the xor gate primitive. XOR means an odd number of 1s.
The Three Basic Gates
A logic gate is a small circuit with one output. The output depends only on the inputs at this moment.
A truth table lists the output for every input row. Two inputs give four rows, in counting order: 00, 01, 10, 11.
| Gate | In code | Output is 1 when | Column for ab = 00, 01, 10, 11 |
|---|---|---|---|
| AND | a & b | both inputs are 1 | 0001 |
| OR | a | b | at least one input is 1 | 0111 |
| NOT | ~a | the input is 0 | 1100 (it reads only a) |
| Buffer | a | the input is 1 | 0011 (it reads only a) |
A NOT gate is also called an inverter. A buffer changes no value: it only makes the signal stronger.
NAND, NOR, XOR and XNOR
A small circle on a symbol is a bubble. It means NOT. An AND symbol with a bubble on its output is a NAND gate.
| Gate | In code | Column for ab = 00, 01, 10, 11 | In words |
|---|---|---|---|
| AND | a & b | 0001 | 1 only when both inputs are 1 |
| OR | a | b | 0111 | 1 when at least one input is 1 |
| NAND | ~(a & b) | 1110 | AND, then inverted: 0 only when both are 1 |
| NOR | ~(a | b) | 1000 | OR, then inverted: 1 only when both are 0 |
| XOR | a ^ b | 0110 | 1 when the inputs differ |
| XNOR | ~(a ^ b) | 1001 | 1 when the inputs are equal |
Computed and then compared with the six gate primitives of the simulator.
XOR is short for exclusive OR. It is 1 when the two inputs differ. XNOR is its opposite: it is 1 when the inputs are equal.
NAND and NOR matter most in real chips. Lesson G9.2 shows why they need fewer transistors than AND and OR.
Gates with More Inputs
Most gates also come with three or more inputs. The rule in words stays the same. N inputs give 2^N rows.
| Gate | Output is 1 when | Column for abc = 000 to 111 |
|---|---|---|
| AND | every input is 1 | 00000001 |
| OR | at least one input is 1 | 01111111 |
| NAND | at least one input is 0 | 11111110 |
| NOR | every input is 0 | 10000000 |
| XOR | the number of 1s is odd | 01101001 |
| XNOR | the number of 1s is even | 10010110 |
Computed and then compared with three-input gate primitives on the simulator.
| Inputs | 1 | 2 | 3 | 4 | 5 | 8 |
|---|---|---|---|---|---|---|
| Rows in the truth table | 2 | 4 | 8 | 16 | 32 | 256 |
Each extra input doubles the table.
The Sixteen Functions of Two Inputs
A truth table with two inputs has four output cells. Each cell is 0 or 1, so there are 2^4 = 16 possible columns. Each column is one function.
| Column for ab = 00, 01, 10, 11 | Name | Textbook name | In code |
|---|---|---|---|
0000 | constant 0 | null | 0 |
0001 | AND | AND | a & b |
0010 | a and not b | inhibition (a but not b) | a & ~b |
0011 | a itself | transfer of a | a |
0100 | b and not a | inhibition (b but not a) | ~a & b |
0101 | b itself | transfer of b | b |
0110 | XOR | exclusive-OR | a ^ b |
0111 | OR | OR | a | b |
1000 | NOR | NOR | ~(a | b) |
1001 | XNOR | equivalence | ~(a ^ b) |
1010 | NOT b | complement of b | ~b |
1011 | a or not b | implication (b implies a) | a | ~b |
1100 | NOT a | complement of a | ~a |
1101 | b or not a | implication (a implies b) | ~a | b |
1110 | NAND | NAND | ~(a & b) |
1111 | constant 1 | identity | 1 |
All 16 columns, computed. Six are the gates above. Two are constants, four copy or invert one input, and four mix an input with an inverted input.
So the six named gates are not a full list of what two inputs can do. They are the six columns that got a symbol of their own.
A Circuit Is a Function
Gates connect output to input to make a circuit. A circuit with no loop has a truth table too. Find it one row at a time.
- I/O
- Datapath
- Data
- The first AND gate
It reads a = 1 and b = 1, so
abis 1.Follow the calls, values and waits
- data 1: AND → OR
- The two other AND gates
Each of them reads c = 0, so
acandbcare both 0.Follow the calls, values and waits
- data 0: AND → OR
- data 0: AND → OR
- The OR gate
One of its inputs is 1. That is enough: y is 1 for the row 110.
Follow the calls, values and waits
- data 1: OR → y
Read the diagram as text
- a = 1: input
- b = 1: input
- c = 0: input
- AND: ab = a & b
- AND: ac = a & c
- AND: bc = b & c
- OR: y = ab | ac | bc
- y: output
- a = 1 → AND
- b = 1 → AND
- a = 1 → AND
- c = 0 → AND
- b = 1 → AND
- c = 0 → AND
- AND → OR: ab
- AND → OR: ac
- AND → OR: bc
- OR → y: y
Two of the three inputs are 1, and the output is 1. Repeat this for all eight rows to get the truth table.
| a b c | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
|---|---|---|---|---|---|---|---|---|
| number of 1s | 0 | 1 | 1 | 2 | 1 | 2 | 2 | 3 |
| y | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
The majority function: y is 1 when two or three inputs are 1. The lab below prints the same column.
Asked in interviews
What does a three-input XOR gate compute?
It gives 1 when an odd number of its inputs are 1. So 111 gives 1. It is a parity function, and it is different from "exactly one input is 1".
How many different functions of two inputs exist?
Sixteen. The truth table has four rows, and each output cell is 0 or 1, so there are 2^4 columns. For N inputs the count is 2 to the power 2^N.
What is the difference between NAND and "invert, then AND"?
NAND inverts the output of an AND gate:
~(a & b), column 1110. Inverting the inputs first gives~a & ~b, column 1000, which is NOR.
Try It
Press Run and read the output as a truth table. Practice G2.2.1 shows you the one line a gate needs; lesson G2.3 teaches the rest.
Each line starting with and or or places one gate. The first name in the brackets is its output. Read down the y column: 00010111.
Try one change. Replace or in gate g4 by nor and run again. Every y flips, and the column becomes 11101000.
Now replace it by xor. The column is 00010111 again. In every row, zero, one or all three of the pair wires are 1.
a=0 b=0 c=0 y=0 a=0 b=0 c=1 y=0 a=0 b=1 c=0 y=0 a=0 b=1 c=1 y=1 a=1 b=0 c=0 y=0 a=1 b=0 c=1 y=1 a=1 b=1 c=0 y=1 a=1 b=1 c=1 y=1Check Yourself
Common Mistakes
Wrong Read a three-input XOR as "exactly one input is 1".
XOR gives 1 for an odd number of 1s. With all three inputs at 1 the output is 1.
Fix Count the 1s on the inputs. An odd count gives 1, an even count gives 0.
Wrong Miss the bubble and read a NAND gate as an AND gate.
The bubble inverts. Every output of the truth table is the opposite.
Fix Look at the output of the symbol first. A small circle there means NOT.
Wrong Read NAND as "NOT the inputs, then AND".
That circuit is ~a & ~b, which is NOR. NAND inverts the result, not the inputs.
Fix NAND is AND first, then NOT: ~(a & b).
y = ~a & ~b; // 1000: this is NORy = ~(a & b); // 1110: this is NANDWrong Assume an input with no driver is 0.
A floating wire has the value z. The simulator then gives the AND gate the output x, unknown.
Fix Drive every input. Tie an unused input to a fixed 0 or 1.
Remember
- AND needs every input at 1; OR needs at least one. A bubble inverts.
- NAND is
~(a & b): AND first, then NOT. NOR is~(a | b). - XOR gives 1 for an odd number of 1s, with any number of inputs.
- N inputs give 2^N rows. Two inputs allow 16 different functions.
- A circuit without loops has one truth table. Majority of three is 00010111.