A decision like “go straight if the light is green and there’s no obstacle
ahead” can be written in Boolean algebra as
Go = Green ∧ ¬Obstacle. And thanks to Shannon’s insight, logic like this can
be built into real electrical circuits.
To build circuits that actually work, we need several kinds of logic gates. Gates can be made from transistors, but looking inside them is closer to electrical engineering than computer science. In this series, let’s assume the gates work properly and use them as parts. In this post, let’s look at what gates there are.
AND, OR, and NOT gates are intuitive because they match the everyday words
“and,” “or,” and “not.” As in Boolean algebra, A AND B is written
A ∧ B, A OR B is A ∨ B, and NOT A is ¬A. Let’s start with the idea behind
each of the three.
AND means “and.” It is true only when both conditions are true.
| A ∧ B | ||
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
In circuits, an AND gate is drawn in the shape below. Inputs go in on the left, and the result comes out on the right.
Logging in only when both the username and the password are correct is an example of AND.
OR means “or.” It is true if at least one of the two conditions is true.
| A ∨ B | ||
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
An OR gate has a curved-in entrance and a pointed tip.
A smartphone that unlocks if either your fingerprint or your passcode matches is an example of OR.
NOT means “not.” It inverts the input bit.
| ¬A | |
|---|---|
| 0 | 1 |
| 1 | 0 |
A NOT gate has only one input.
A fridge that beeps when its door is not closed is an example of NOT.
The small circle at the tip of the triangle is the mark for inverting.
The gate that inverts the output of AND is NAND. It is false only when both inputs are true, and true otherwise.
| A NAND B | ||
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Its shape is an AND with the circle we just saw attached to the tip.
Now let’s turn the go-straight decision from the beginning,
Go = Green ∧ ¬Obstacle, into a circuit. We invert the obstacle signal with
NOT, then feed the result into AND together with the green light.
Let’s click the inputs to change their values.
This example could be put together by intuition, but not every Boolean function breaks down this easily. Even so, AND, OR, and NOT are enough to build any truth table as a circuit. Let’s see whether that’s really true, and the systematic way to do it, in the next post.
Building a circuit that passes (1) when at least two of three people A, B, and C vote yes (1) as (A ∧ B) ∨ (A ∧ C) ∨ (B ∧ C) takes 5 gates. Which of the following expressions does the same job with 4 gates? Try editing the circuit below to find out.
Loading the circuit…