yeolyi.comSeongyeol's CS

AND, OR, NOT Gates

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 gate

AND means “and.” It is true only when both conditions are true.

A ∧ B
000
010
100
111

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.

Let’s press A and B to make all four rows of the truth table above.

Logging in only when both the username and the password are correct is an example of AND.

OR gate

OR means “or.” It is true if at least one of the two conditions is true.

A ∨ B
000
011
101
111

An OR gate has a curved-in entrance and a pointed tip.

Again, let’s press A and B and check them against the truth table above.

A smartphone that unlocks if either your fingerprint or your passcode matches is an example of OR.

NOT gate

NOT means “not.” It inverts the input bit.

¬A
01
10

A NOT gate has only one input.

Let’s press A. The output is always the opposite.

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.

NAND gate

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
001
011
101
110

Its shape is an AND with the circle we just saw attached to the tip.

Let’s set both A and B to 1. Only then is the output 0.

Building a go-straight circuit

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.

Challenge

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…