# Notes on Boolean Algebra

July 14, 2018While 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.

## Notes

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:

`And`

(`&&`

,`·`

):`x && y`

is true if both are true.`Or`

(`||`

,`+`

):`x || y`

is true if one of both is true.`Not`

(`!`

,`‾`

):`!x`

is true when`x`

is false.

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.