yeolyi.comSeongyeol's CS

Boolean Algebra

In the last post, we saw why computers represent the world with simple bits, 0 and 1. But if all it did was store bits, a computer would be nothing more than a storage device. Its real power lies in processing bits meaningfully to produce the results we want.

Take a bank vault, for example. It opens when two employees each turn their own key, but the branch manager can open it alone by tapping a card.

Locked
  1. Turn only Key 1. The door stays locked.
  2. Turn Key 2 as well. With both turned, it opens.
  3. Turn both keys back and tap only the card. It opens on its own.

Can we express logic like this with bits? First, let’s look at how to write this logic as an expression.

Boolean algebra

The 19th-century English mathematician George Boole created a system that expresses human logical reasoning like mathematics, using just two values, true and false, and a few operations. This is called Boolean algebra. Its main operations are:

The vault opens “when Key 1 and (∧) Key 2 are both turned, or (∨) the card is tapped,” so in Boolean algebra we write:

Open = (Key1 ∧ Key2) ∨ Card

Truth tables

To check whether the expression is right, we can go through every combination of keys and card. Let’s set true to 1 and false to 0. Then the vault’s logic can be written in bits.

Something that takes true/false values as input and gives back true/false according to a fixed rule is called a Boolean function, and a table that lists the rule for every combination of inputs is called a truth table. Spelled out as a truth table, the vault looks like this:

Open
0000
0011
0100
0111
1000
1011
1101
1111

Logic and electricity

But how can this expression be turned into a machine? The person who connected abstract logic to electrical circuits was the American mathematician Claude Shannon.

In his 1937 MIT master’s thesis, A Symbolic Analysis of Relay and Switching Circuits, Shannon showed that circuits made of switches can be written and calculated as Boolean algebra expressions.

A page from Shannon's 1937 master's thesis that reduces a circuit to an expression
A page from Shannon's 1937 master's thesis that reduces a circuit to an expression

Thanks to this, circuits that used to be designed by intuition could be designed with expressions, and simpler circuits could be found by simplifying the expressions.

A vault built from switches

Let’s build the vault as a circuit, Shannon’s way. Suppose that turning a key or tapping the card closes a switch and connects it, and that the door’s lock releases when current flows. We treat current flowing as true and no current as false.

Key 1Key 2CardLock

Both wires are broken, so the lock stays locked.

  1. Press the Key 1 and Key 2 switches. Both must be closed for the top wire to connect.
  2. Turn the key switches back and press only the card switch. The bottom wire alone releases the lock.

The expression became a circuit as is. Today’s computers do the same thing not with switches flipped by hand, but with transistors, tiny semiconductor switches turned on and off by electrical signals. How transistors work belongs to physics, so this series stops here.

In the next post, let’s look at the basic parts that build these Boolean functions into real circuits: the AND, OR, and NOT logic gates.

Challenge

Open = (Key1 ∧ Key2) ∨ Card. Which of the following always gives the same value as Open, whatever the values of Key1, Key2, and Card?