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.

A Three-Input XOR Against "exactly one"One input row per step, from 000 to 111. The last row is where the two differ.
01234567a b c000001010011100101110111XOR of a, b, cexactly one is 1111: XOR gives 1
Scroll horizontally ↔
  1. Cycle 1

    One input is 1. Both columns give 1.

  2. Cycle 3

    Two inputs are 1. Both columns give 0.

  3. 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.

GateIn codeOutput is 1 whenColumn for ab = 00, 01, 10, 11
ANDa & bboth inputs are 10001
ORa | bat least one input is 10111
NOT~athe input is 01100 (it reads only a)
Bufferathe input is 10011 (it reads only a)

A NOT gate is also called an inverter. A buffer changes no value: it only makes the signal stronger.

Type a Gate and Watch Its Table
aby
00
01
10
11
Type a Gate and Watch Its Tablen0 · ANDn0=0a=0b=0
a=0 b=0
n0 · ANDa=0, b=0 → n0=0
Read the connections
GateKindInputsOutput
n0ANDa, bn0

Outputs: n0. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Type `a | b`, `~a`, `~(a & b)` or `a ^ b` in place of the expression. Click an input pin to walk through the rows.

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.

GateIn codeColumn for ab = 00, 01, 10, 11In words
ANDa & b00011 only when both inputs are 1
ORa | b01111 when at least one input is 1
NAND~(a & b)1110AND, then inverted: 0 only when both are 1
NOR~(a | b)1000OR, then inverted: 1 only when both are 0
XORa ^ b01101 when the inputs differ
XNOR~(a ^ b)10011 when the inputs are equal

Computed and then compared with the six gate primitives of the simulator.

The Bubble Inverts Every Row
aby
00
01
10
11
The Bubble Inverts Every Rown1 · ANDn1=0n0 · NOTn0=1a=0b=0
a=0 b=0
n1 · ANDa=0, b=0 → n1=0
n0 · NOTn1=0 → n0=1
Read the connections
GateKindInputsOutput
n1ANDa, bn1
n0NOTn1n0

Outputs: n0. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

A NAND gate. Remove the `~` and compare the two output columns: each row is the opposite.

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.

The Eight Gate Symbols
The Eight Gate Symbolsg_y_and · ANDy_and=0g_y_or · ORy_or=1g_y_not · NOTy_not=1g_y_buf · BUFy_buf=0g_y_nand · NANDy_nand=1g_y_nor · NORy_nor=0g_y_xor · XORy_xor=1g_y_xnor · XNORy_xnor=0a=0b=1
a=0 b=1
g_y_and · ANDa=0, b=1 → y_and=0
g_y_or · ORa=0, b=1 → y_or=1
g_y_not · NOTa=0 → y_not=1
g_y_buf · BUFa=0 → y_buf=0
g_y_nand · NANDa=0, b=1 → y_nand=1
g_y_nor · NORa=0, b=1 → y_nor=0
g_y_xor · XORa=0, b=1 → y_xor=1
g_y_xnor · XNORa=0, b=1 → y_xnor=0
Read the connections
GateKindInputsOutput
g_y_andANDa, by_and
g_y_orORa, by_or
g_y_notNOTay_not
g_y_bufBUFay_buf
g_y_nandNANDa, by_nand
g_y_norNORa, by_nor
g_y_xorXORa, by_xor
g_y_xnorXNORa, by_xnor

Outputs: y_and, y_or, y_not, y_buf, y_nand, y_nor, y_xor, y_xnor. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Gate delay 1. Settled after 1 gate delays from t = 0.

Output values at each gate delay01y_andx0y_orx1y_notx1y_bufx0y_nandx1y_norx0y_xorx1y_xnorx0
Scroll horizontally ↔
Every computed frame
Timey_andy_ory_noty_bufy_nandy_nory_xory_xnor
0xxxxxxxx
101101010

AND has a flat back and a round front. OR has a curved back and a pointed front. XOR adds a second curve at the back. A bubble at the output inverts: NAND, NOR, XNOR and NOT. Click a or b to change the inputs.

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.

GateOutput is 1 whenColumn for abc = 000 to 111
ANDevery input is 100000001
ORat least one input is 101111111
NANDat least one input is 011111110
NORevery input is 010000000
XORthe number of 1s is odd01101001
XNORthe number of 1s is even10010110

Computed and then compared with three-input gate primitives on the simulator.

Inputs123458
Rows in the truth table2481632256

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, 11NameTextbook nameIn code
0000constant 0null0
0001ANDANDa & b
0010a and not binhibition (a but not b)a & ~b
0011a itselftransfer of aa
0100b and not ainhibition (b but not a)~a & b
0101b itselftransfer of bb
0110XORexclusive-ORa ^ b
0111ORORa | b
1000NORNOR~(a | b)
1001XNORequivalence~(a ^ b)
1010NOT bcomplement of b~b
1011a or not bimplication (b implies a)a | ~b
1100NOT acomplement of a~a
1101b or not aimplication (a implies b)~a | b
1110NANDNAND~(a & b)
1111constant 1identity1

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.

The Majority Circuit, Row Abc = 110Arrows show signals. Three AND gates each test one pair of inputs. The OR gate collects them.
  • I/O
  • Datapath
  • Data
CallValueReturnWaiting
The majority circuit, row abc = 110Arrows show signals. Three AND gates each test one pair of inputs. The OR gate collects them. io a = 1 input io b = 1 input io c = 0 input datapath AND ab = a & b datapath AND ac = a & c datapath AND bc = b & c datapath OR y = ab | ac | bc io y output abacbcy
  1. io a = 1input
    • AND
    • AND
  2. io b = 1input
    • AND
    • AND
  3. datapath ANDab = a & b
    • ab → OR
  4. io c = 0input
    • AND
    • AND
  5. datapath ANDac = a & c
    • ac → OR
  6. datapath ANDbc = b & c
    • bc → OR
  7. datapath ORy = ab | ac | bc
    • y → y
  8. io youtput
  1. The first AND gate

    It reads a = 1 and b = 1, so ab is 1.

    Follow the calls, values and waits
    1. data 1: AND → OR
  2. The two other AND gates

    Each of them reads c = 0, so ac and bc are both 0.

    Follow the calls, values and waits
    1. data 0: AND → OR
    2. data 0: AND → OR
  3. 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
    1. 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.

Majority: Click the Pins
abcy
0000
0010
0100
0111
1000
1011
1101
1111
Majority: Click the Pinsn2 · ANDn2=0n3 · ANDn3=0n1 · ORn1=0n4 · ANDn4=0n0 · ORn0=0a=0b=0c=0
a=0 b=0 c=0
n2 · ANDa=0, b=0 → n2=0
n3 · ANDa=0, c=0 → n3=0
n1 · ORn2=0, n3=0 → n1=0
n4 · ANDb=0, c=0 → n4=0
n0 · ORn1=0, n4=0 → n0=0
Read the connections
GateKindInputsOutput
n2ANDa, bn2
n3ANDa, cn3
n1ORn2, n3n1
n4ANDb, cn4
n0ORn1, n4n0

Outputs: n0. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Click an input pin. Wires at 1 light, and the matching row of the table is ringed. The output column is 00010111.

a b c000001010011100101110111
number of 1s01121223
y00010111

The majority function: y is 1 when two or three inputs are 1. The lab below prints the same column.

Asked in interviews
  1. 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".

  2. 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.

  3. 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.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: 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=1

Check Yourself

Predict the outputA three-input XOR gate gets 1 on all three inputs. Predict the exact line this program prints.
module tb;
  logic a, b, c;
  wire  y;
  xor g (y, a, b, c);       // one XOR gate with three inputs
  initial begin
    {a, b, c} = 3'b111;
    #1 $display("%b", y);
  end
endmodule
ConceptWhich gate gives 0 only when all of its inputs are 1?
ConceptA symbol has a flat back, a round front and a bubble at the output. Which gate is it?
ConceptIn the majority circuit, the inputs are a = 0, b = 1 and c = 1. Which internal wires are 1?
ConceptThe output column of a two-input gate is 1001 for the inputs 00, 01, 10 and 11. Which gate is it?

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).

Before
y = ~a & ~b;    // 1000: this is NOR
After
y = ~(a & b);   // 1110: this is NAND

Wrong 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.

Practice

Report a problem with this page