Skip to content

Logic gates

Logic and puzzles · level 6, lesson 1 of 6

A question to start

Deep inside a phone or a laptop there are billions of tiny switches called transistors. Each one can only be on or off. A switch does not know what a number is. It cannot count, it cannot read, it cannot "add".

And yet the same machine adds \(1{,}234{,}567 + 7{,}654{,}321\) in a tiny fraction of a second, and gets it right every time. How can a heap of on-off switches add?

The answer is one of the great surprises of the last century: adding is logic. The and, or and not you have used since level 3 can be built out of switches, and once you have them, you can build arithmetic. This lesson builds a small machine that adds two binary digits, using nothing but logic.

The idea

True and false become 1 and 0

In a circuit, a wire either carries a voltage or it does not. We write 1 for on (true) and 0 for off (false). A single 1 or 0 is called a bit (short for binary digit). Every truth table from levels 4 and 5 can be rewritten with 1 for T and 0 for F.

A logic gate is a small circuit with one or two input wires and one output wire. The output depends only on the inputs, following a fixed truth table. Each gate has a standard symbol:

ANDORNOT XORNAND

Inputs come in on the left, the output leaves on the right. The small circle on NOT and NAND means "then flip it".

The five gates and their tables

With inputs \(A\) and \(B\):

\(A\) \(B\) AND OR XOR NAND
0 0 0 0 0 1
0 1 0 1 1 1
1 0 0 1 1 1
1 1 1 1 0 0

and NOT has one input: NOT 0 = 1, NOT 1 = 0.

  • AND outputs 1 only when both inputs are 1. It is \(A \land B\).
  • OR outputs 1 when at least one input is 1. It is \(A \lor B\), the "one or both" or.
  • NOT flips its input. It is \(\neg A\).
  • XOR ("exclusive or") outputs 1 when exactly one input is 1: "one or the other, but not both". It is the or of a menu ("soup or salad"), and it also means "the inputs are different".
  • NAND ("not and") is AND followed by NOT: it outputs 0 only when both inputs are 1.

Why switches give AND and OR

Picture a battery, a lamp and two switches \(A\) and \(B\).

ABBA in a row (series): ANDside by side (parallel): OR
  • In a row (in series): the current must pass through \(A\) and then through \(B\). The lamp lights only if both switches are closed. That is AND.
  • Side by side (in parallel): the current can take the top path or the bottom path. The lamp lights if at least one switch is closed. That is OR.

In a chip, the switches are transistors, and a transistor can also be wired to give NOT (on in, off out). So the logic of and, or, not is something you can literally build.

Circuits

Gates can be joined: the output of one becomes an input of another. A diagram of joined gates is a circuit, and every circuit has a truth table. To find it, label every wire, and fill in the table one column per wire, working from the inputs towards the output. That is exactly how you built truth tables for long statements in level 4.

Adding in binary

Computers store numbers in binary (base 2), which uses only the digits 0 and 1 (Numbers level 5). Adding two single binary digits has only four cases:

\[0 + 0 = 0, \qquad 0 + 1 = 1, \qquad 1 + 0 = 1, \qquad 1 + 1 = 10_2.\]

The last one is "two", written \(10\) in binary: a 0 in the ones place and a carry of 1 into the twos place, just as \(5 + 7 = 12\) in base 10 writes 2 and carries 1. So adding two bits gives two output bits: a sum bit \(S\) and a carry bit \(C\).

\(A\) \(B\) \(C\) (carry) \(S\) (sum)
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

Now look at the columns. The carry column is 0, 0, 0, 1: that is exactly AND. The sum column is 0, 1, 1, 0: that is exactly XOR. So:

\[S = A \text{ XOR } B, \qquad C = A \text{ AND } B.\]

The half adder

AB S (sum)C (carry)

This circuit is called a half adder. Each input wire splits (the dots mark the joins; the place where two wires cross without a dot is not a join) and feeds both gates. Feed in \(A = 1\), \(B = 1\): the XOR gives 0 and the AND gives 1, so the output reads \(C S = 10\), which is two. The machine has added, using only logic.

It is called "half" because it cannot accept a carry coming in from the column to its right. A full adder takes three bits (the two digits and the incoming carry) and is built from two half adders and an OR gate. Line up 64 full adders, each passing its carry to the next, and you can add 64-bit numbers. That is, in outline, how a processor adds.

Worked examples

1. Reading the tables. What does each gate output for \(A = 1\), \(B = 0\)? AND: 0. OR: 1. XOR: 1 (they differ). NAND: 1 (since AND gave 0). NOT \(A\): 0.

2. A circuit's truth table. Find the table for \(X = (A \text{ AND } B) \text{ OR } (\text{NOT } C)\).

Label the inner wires \(P = A\) AND \(B\) and \(Q =\) NOT \(C\); then \(X = P\) OR \(Q\).

\(A\) \(B\) \(C\) \(P\) \(Q\) \(X\)
0 0 0 0 1 1
0 0 1 0 0 0
0 1 0 0 1 1
0 1 1 0 0 0
1 0 0 0 1 1
1 0 1 0 0 0
1 1 0 1 1 1
1 1 1 1 0 1

In words: the output is 1 when \(C\) is off, or when \(A\) and \(B\) are both on.

3. Building XOR from the basic three. XOR means "at least one, but not both". "At least one" is \(A\) OR \(B\); "not both" is NOT (\(A\) AND \(B\)). Join them with AND:

\[A \text{ XOR } B = (A \text{ OR } B) \text{ AND } \text{NOT}(A \text{ AND } B).\]

Check row by row: for 1, 1 the OR gives 1 but NOT(AND) gives 0, so the result is 0. ✓ For 0, 0 the OR gives 0, result 0. ✓ For 0, 1 and 1, 0 the OR gives 1 and NOT(AND) gives 1, result 1. ✓

4. A door alarm. An alarm should ring (\(R = 1\)) if the system is armed (\(M = 1\)) and either the door (\(D\)) or the window (\(W\)) is open. The circuit is \(R = M\) AND (\(D\) OR \(W\)). With \(M = 1\), \(D = 0\), \(W = 1\): \(D\) OR \(W\) = 1, then \(M\) AND 1 = 1. The alarm rings. With \(M = 0\) it never rings, whatever is open.

5. Adding two-bit numbers. Add \(11_2 + 01_2\) (that is \(3 + 1\)) column by column, like a circuit.

  • Ones column: \(1 + 1\). Half adder: sum 0, carry 1.
  • Twos column: \(1 + 0\) plus the carry 1. That is three bits, \(1 + 0 + 1 = 10_2\): sum 0, carry 1.
  • The final carry becomes the fours digit.

Answer: \(100_2 = 4\). ✓ The second column needed a full adder, because it had a carry coming in.

Try it

  1. Give the output of AND, OR, XOR and NAND when both inputs are 0.
  2. Which gate has the output column 1, 1, 1, 0 (inputs in the order 00, 01, 10, 11)? Which has 1, 0, 0, 1?
  3. Make the truth table for NOT (\(A\) OR \(B\)). This gate is called NOR. Compare it with (NOT \(A\)) AND (NOT \(B\)). What law from level 5 is this?
  4. Find the truth table of \((A \text{ OR } B) \text{ AND } (\text{NOT } C)\).
  5. A car beeps if the engine is on and a seat belt is not fastened. Write the circuit using \(E\) (engine on) and \(F\) (belt fastened).
  6. What does a half adder output for \(A = 0\), \(B = 1\)? Explain why this is right.
  7. Add \(101_2 + 011_2\) in binary, column by column, writing the sum bit and carry of each column. Check in base 10.
  8. Explain why two switches in parallel act as OR. What would three switches in a row act as?
Answers
  1. AND 0, OR 0, XOR 0, NAND 1.
  2. 1, 1, 1, 0 is NAND. 1, 0, 0, 1 is "the inputs are equal": NOT XOR (often called XNOR), the gate version of "if and only if".
  3. NOR: 00 gives 1, 01 gives 0, 10 gives 0, 11 gives 0. (NOT \(A\)) AND (NOT \(B\)) is 1 only when both inputs are 0: the same column 1, 0, 0, 0. This is De Morgan's law, \(\neg(A \lor B) \equiv \neg A \land \neg B\) (level 5).
  4. The output is 1 exactly when \(C = 0\) and at least one of \(A\), \(B\) is 1. Going through \(ABC\) = 000, 001, 010, 011, 100, 101, 110, 111 the outputs are 0, 0, 1, 0, 1, 0, 1, 0.
  5. Beep \(= E\) AND (NOT \(F\)).
  6. \(S\) = 0 XOR 1 = 1, \(C\) = 0 AND 1 = 0. Output \(CS = 01\), which is one. Right, since \(0 + 1 = 1\).
  7. Ones: \(1 + 1 = 10_2\), sum 0 carry 1. Twos: \(0 + 1 + 1 = 10_2\), sum 0 carry 1. Fours: \(1 + 0 + 1 = 10_2\), sum 0 carry 1. The last carry is the eights digit: \(1000_2 = 8\). Check: \(101_2 = 5\), \(011_2 = 3\), and \(5 + 3 = 8\). ✓
  8. Current reaches the lamp along either path, so one closed switch is enough: at least one closed means on, which is OR. Three in a row need all three closed: a three-input AND.

Common mistake

Using OR when you mean XOR. The gate OR, like the logical or, includes "both". If the output must be 1 for "exactly one", you need XOR. The sum bit of an adder is XOR, not OR: with OR, \(1 + 1\) would give sum 1, which is wrong.

Reading a circuit in the wrong order. Work from the inputs to the output, one gate at a time, writing every middle wire as its own column. Skipping straight to the output is where errors creep in.

Where it leads