Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 55 ยท Logic and Programs

Boolean Logic and Logic Gates

Learn Boolean logic and logic gates: AND, OR, NOT, XOR and NAND, truth tables, and how gates combine into half and full adders that let a computer do arithmetic.

Inside a processor there are no numbers and no letters, only wires that carry one of two voltage levels. Yet the same machine adds, compares and decides. The bridge between a wire and a decision is Boolean logic, named after the mathematician George Boole. In it, every value is either true (1) or false (0), and a few simple operations combine values into new ones.

Circuits that perform these operations are called logic gates. Billions of them, wired together, make a CPU. This lesson shows the basic gates, how to describe them with truth tables, and how to build a circuit that adds numbers using nothing but gates. It follows Motherboard, Buses, GPU and Power and builds on the 0s and 1s of Bits and Bytes.

The basic gates

A truth table lists every possible input combination and the output for each. With two inputs there are only four rows, so truth tables are short.

NOT inverts its single input.

A NOT A
0 1
1 0

AND outputs 1 only when both inputs are 1. Think of two switches in a row: current flows only if both are closed.

OR outputs 1 when at least one input is 1. Two switches side by side: closing either lets current through.

XOR (exclusive or) outputs 1 when the inputs differ.

A B AND OR XOR
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 1 0

Two more are just inversions: NAND is NOT-AND (0 only when both inputs are 1) and NOR is NOT-OR. They look like minor variations, but NAND has a special status, as you will see below.

Programming languages expose the same operations. In many languages & is AND, | is OR, ^ is XOR and ~ or ! is NOT. The words "and", "or", "not" in an if statement are the same idea applied to true/false conditions.

JS A gate simulator and truth tables

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Gates in circuits

Engineers draw gates as small symbols and connect them with lines. The diagram below shows the same logic as a flow: two inputs go through an AND and an OR, and a final gate combines them. Read it left to right.

flowchart LR
  A["Input A"] --> AND["AND"]
  B["Input B"] --> AND
  A --> OR["OR"]
  B --> OR
  AND --> NOT["NOT"]
  NOT --> OUT["AND (final)"]
  OR --> OUT
  OUT --> Q["Output = (A OR B) AND NOT (A AND B)"]

Three kinds of gate combined: this circuit behaves exactly like XOR.

That diagram is a real result: XOR can be built from AND, OR and NOT. Combining small gates to get new behaviour is the entire method of digital design.

NAND is universal

Any other gate can be built from NAND alone. NOT is a NAND with both inputs tied together (NAND(a, a)). AND is a NAND followed by that NOT. OR is built from NOT on each input and then a NAND. Chip makers like this because one gate type, repeated, is simple to manufacture. The next stand-in proves it by building everything from a single function.

JS Everything from NAND

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Why gates can do arithmetic

Add two single bits by hand: 0+0 = 0, 0+1 = 1, 1+0 = 1, and 1+1 = 10 in binary (that is, sum digit 0 and a carry of 1). Look at the table again:

A B Sum digit Carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

The sum digit column is exactly XOR, and the carry column is exactly AND. A circuit with one XOR and one AND is a half adder: it adds two bits and produces a sum and a carry.

A half adder cannot accept a carry coming in from a lower digit, so it is only enough for the lowest bit. A full adder takes three inputs (A, B and a carry-in) and is built from two half adders plus an OR to merge their carries. Chain full adders side by side, passing each carry-out to the next carry-in, and you get a ripple-carry adder for numbers of any width. Real processors use faster carry designs, but the idea is the same.

JS Half adder, full adder and a 4-bit adder

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The last line shows an important consequence: a 4-bit adder cannot represent 16, so 15 + 1 produces 0 with the carry-out set. That is overflow, and you will meet it again in Binary, Octal and Hexadecimal. The stand-in uses ordinary JavaScript operators to model the gates; in hardware each one is a few transistors.

From gates to the machine

Gates cannot remember anything on their own, since their output depends only on current inputs. Feeding a gate's output back into itself in a clever loop creates a latch or flip-flop, which holds one bit. Rows of those make registers and the memory you saw in Memory: RAM, Cache and the Memory Hierarchy. Adders, comparers and multiplexers (circuits that select one of several inputs) form the ALU, the arithmetic heart of the CPU described in The CPU. Everything the computer does is layers of these same gates.

A modern processor holds billions of transistors. A gate takes from two to a handful of transistors, so even one chip contains a vast number of gates. They switch billions of times per second, which is why simple rules produce such complex behaviour.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. For which inputs does an AND gate output 1?

    AND is true only when all of its inputs are true.
  2. 2. Which gate matches the sum digit of a half adder?

    Adding two bits gives 1 when exactly one of them is 1, which is XOR. The carry is AND.
  3. 3. Why is NAND called a universal gate?

    NOT, AND, OR and XOR can all be made from combinations of NAND, so one gate type is enough.
  4. 4. What does a full adder take as inputs?

    A full adder adds A, B and the carry from the previous digit, which lets adders be chained for wide numbers.
  5. 5. What happens when a 4-bit adder adds 15 and 1?

    The result needs 5 bits. The lower 4 bits are 0000 and the extra bit appears as carry-out (overflow).

Summary

  • Boolean logic has two values, true/1 and false/0, and a few operations: NOT, AND, OR, XOR, NAND, NOR.
  • A truth table lists the output for every input combination.
  • Gates combine into larger circuits; XOR can be made from AND, OR and NOT, and NAND alone can build every gate.
  • A half adder is an XOR (sum) plus an AND (carry); two half adders and an OR make a full adder.
  • Chained full adders add numbers of any width, and too-large results show up as overflow.
  • Feedback loops of gates give memory; adders and selectors make up the ALU.

Now see how a list of such operations becomes a program: Machine Code and Assembly.