Computers Are Made of 'Do You Like Mom or Dad?'

In the previous post, we expressed the judgment “if the traffic light is green and there is no obstacle ahead, go straight” using Boolean algebra and a truth table. And thanks to Shannon’s insight, we confirmed that such logic can be implemented as actual electrical circuits.

But a truth table is just a blueprint on paper. How do we build an actual working circuit from this blueprint? We need logic gates.

While Boolean algebra has many operations, AND, OR, and NOT are special. They directly correspond to the way we think in everyday life using “and,” “or,” and “not,” making them intuitive. More importantly, these three alone can express any complex Boolean function. Let’s verify this after examining each gate.

The AND Gate: Both Must Be True

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

The AND gate is primarily used to check whether all specific conditions are met. For example, think of a smartphone that unlocks only when both the password and fingerprint match.

The OR Gate: At Least One Must Be True

OR means “or.” The result is true when at least one of the two conditions is true.

It is used to determine situations where satisfying just one of several possible conditions is enough. For example, think of a house where ventilation works as long as either the front door or the back door is open.

The NOT Gate: Flipping the Value

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

It is used to flip a state or to check when a certain condition is not met. For example, think of a smartphone where touch only works when it is NOT locked.

Building the Go-Straight Circuit

Now that we’ve learned all three gates, let’s build the go-straight decision from the previous post as an actual circuit. We had Go straight = Green light ∧ ¬Obstacle. Expressing this with gates means inverting the obstacle signal with a NOT gate, then feeding the result along with the green light signal into an AND gate.

Here it is as a circuit. Click the inputs to change their values.

It works exactly like the go-straight truth table we made in the previous post. By combining AND, OR, and NOT gates, we can implement truth tables as actual circuits.

This example was intuitive enough to combine gates directly. But not all Boolean functions decompose this easily. Is there a systematic way to convert any truth table into AND, OR, and NOT?

Building Any Boolean Function with AND, OR, and NOT

Yes. Let’s look at one such method. This is the most abstract part of the early series, but it’s not difficult if you follow the example.

The key idea is simple. Find all input combinations where the output is true (1), create an AND gate for each such combination, and finally combine all these AND results with an OR gate.

It might sound a bit complicated in words, so let’s walk through an example. Let’s build a gate whose output is 1 when the two inputs are equal using only AND, OR, and NOT. First, the truth table looks like this:

Now we just follow three simple steps.

First, find all rows where the output is 1. In the truth table above, the rows with output 1 are the first row (A=0, B=0) and the fourth row (A=1, B=1).

Next, create an AND condition representing each row. The first row (A=0, B=0) means “when input A is 0 and input B is 0, the output is 1,” which can be expressed as (input A is 0) AND (input B is 0), i.e., (NOT A) AND (NOT B). The fourth row (A=1, B=1) means “when input A is 1 and input B is 1, the output is 1,” which is simply A AND B.

Finally, connect all these AND conditions with an OR gate. The output becomes 1 when “the first row’s condition is satisfied” or “the fourth row’s condition is satisfied.” So we connect the two expressions with OR.

The final logic expression is ((NOT A) AND (NOT B)) OR (A AND B).

We’ve completed a circuit that works exactly like the original truth table.

In this way, a truth table serves as a “blueprint” that defines the desired logical behavior, and the method we just introduced shows the process of building that blueprint into an actual circuit using AND, OR, and NOT as “basic components.”

Physical Implementation of Logic Gates

Since this is about physical implementation, let’s keep it brief. The key to implementing logic gates is creating switches that control the flow of electrical signals. The component that serves as this switch is the transistor. A transistor opens a pathway for electricity to flow when certain conditions are met, and blocks it otherwise. AND, OR, and NOT gates are built by connecting these transistors in specific ways.

Wrap-up

AND, OR, and NOT are intuitive for humans, but from a hardware engineer’s perspective, what matters more is how efficiently and simply they can be physically implemented.

Not just AND, OR, and NOT, but any complex logic gate can be built using only NAND gates. This is called NAND’s completeness or universality. It’s like having a single universal block among LEGO pieces that can assemble any other shape. NAND and NOR gates are exactly such universal blocks.

Next time, we’ll dive deeper into how NAND gates alone can construct any logic circuit.