CS101 part 1: Boolean Algebra

Several people have suggested that I write a series of “CS101” posts explaining computer science and software engineering fundamentals, unrelated to anything in the news cycle. This idea appealed to my inner didact, so I’ll try a few posts along those lines and see what responses I get. Feel free to comment and/or suggest topics.

Hopefully, reading these posts will provide non-engineers in the tech industry with a better sense of what goes on under the hood, of what their engineering colleagues do, and of why software engineering is such a fascinating, intricate discipline. To any engineers reading this: you’ll have to forgive my simplification of many concepts, in the interest of clarity and brevity.

I’ll kick off, appropriately, by discussing the lowest level concept in Computer Science…

Boolean Algebra

Boolean algebra, first developed by 19th century mathematician George Boole, is a mathematical formalization of intuitive logic. It provides a formal framework for reasoning about relationships between mathematical quantities that are limited to two possible values: true and false, often denoted as 1 and 0, respectively.  In particular, Boolean algebra allows us to reason about operations on truth values.

The three basic operations on truth values are:

  • NOT: NOT(true) is false, and NOT(false) is true.
  • OR: OR(X, Y) is true if either X or Y are true, and false otherwise.
  • AND: AND(X, Y) is true if both X and Y are true, and false otherwise.
Note how intuitive these definitions are. For example, we all understand intuitively that the statement “X is a programming language and Y is programming language” is only true if the statements “X is a programming language” and “Y is a programming language” are each independenly true. So for X=Java and Y=Ruby, the statement is true, but for X=Java and Y=Spanish the statement is false

The basic Boolean operations can be combined, e.g., we can formalize the intuitive statement “either X is false and Y is true, or Z is false” as OR(AND(NOT(X), Y), NOT(Z)). Boolean algebra provides rules for manipulating these expressions, much as regular high-school algebra does for expressions involving numbers. Such expressions are known as Boolean functions: They take one or more truth values as input, and output a single truth value. Crucially:

Any Boolean function can be written as some combination of the basic Boolean operations.

So far so good, but why is Boolean algebra so central to computer science? Because it provides the bridge between the abstract world of mathematics and the physical implementation of computer hardware. 

Boolean Hardware

Electronic circuits consist of components connected by wires. We can assign a truth value to a wire in an electronic circuit: true if there is electrical current on that wire and false if there isn’t. 

Now it turns out to be possible to construct circuits that implement each of the three basic Boolean operations. For example, it’s possible to build a little circuit that has two wires going in and one coming out, and in which current comes out only if both incoming wires have current. This little contraption is a real life AND circuit: a physical thing that implements the abstract mathematical concept of Boolean AND. Similar circuits can be built to implement OR and NOT. 

Such circuits can be combined, by connecting the output wire of one to an input wire of another so that current can flow from one to the other. As we saw above, any Boolean function is some combination of the 3 basic operations, and therefore:

Any Boolean function can be implemented as an electronic circuit.

This is a remarkable engineering fact. Given any Boolean function, we can build hardware that can actually compute it! If we want to find out what the function’s output is for a given set of inputs, we simply apply current to the wires representing the inputs that are true, apply no current to the wires representing the inputs that are false, and measure the current on the output wire.

Now Repeat Billions of Times

The advent of transistors and, later, integrated circuits have made it cheap and easy to mass-produce phenomenally complicated circuits, consisting of many millions of AND, OR and NOT operations, modeling similarly large and complicated Boolean functions. These circuits form the basis of real-life computers. 

In the next post in the series we’ll examine how these circuits are used to provide elementary computing capabilities.