Notes on Boolean Algebra

July 13, 2018

While it's described in the sources section, most of the content of this is verbatim taken from The Elements of Computing Systems, a great book to understand (and build) computers.

This are some of my notes on the first chapter about boolean logic, and when I say notes, I must admit that I'm referring to the literal meaning of it, they may not have any sense nor a defined path, but I'm publishing this in case anyone wants to expend 3 minutes reading some boolean algebra and for myself, I'm pretty sure that my future self will want to take a brief recap at some time.


Boolean algebra deals with Boolean values that are typically labeled with true/false, 1/0, on/off and so forth.

A boolean function is a function that operates with binary input and returns binary output.

The simplest way to specify a boolean function is by specifying all the possible values of the function variables along with all the possible ooutputs.

[thuth table example]

A boolean function can also be specified using boolean expressions, which are expressed via boolean operators over its input variables. The basic boolean operators typically used are:

It can be proved that any boolean function can be expressed usint at least one boolean expression, and this has a profound implication because it means that any truth table can be expressed on terms of the boolean operators mentioned above (And, Or, Not).

Using the base boolean operators, we can construct and name common boolean functions, for example Nand is defined as Not-And, which means: given two values x, y; take the And of x and y and negate the result. This function has an interesting property with far-reaching practical implications: each one of the basic operations can be constructed from Nand, therefore, any boolean function can be written in terms of Nand only.