The First Abstraction
George Boole was a remarkable genius, and like you and me, he was also a self-taught student. He discovered a decision-making system that operates on only two possible values. We call this system Boolean logic.
He also defined all the possible operations and laws for manipulating these values. These operations and laws form a branch of mathematics known as Boolean algebra.
A computer's capabilities come from its ability to perform operations on binary values. Boolean algebra is crucial for the specification, analysis, and optimisation of hardware architectures.
George Boole's work laid down the foundation of computing and the digital world around us.
The three fundamental operations in Boolean algebra are And, Or, and Not. There are more operations but these three can represent any Boolean function.
A logic gate is the implementation of a Boolean operation. They serve as the fundamental building blocks of all computers and digital devices. Any technology that provides switching and conducting is suitable for building these gates. In the digital world, these gates are implemented in silicon.
Boolean logic is the first abstraction for computer scientists. They do not need to worry about the implementation, they need to understand only what they do.
Boolean Expressions and Truth Tables
A Boolean function has two equivalent representations: Boolean expressions and truth tables. A function's truth table is unique, but it can have many Boolean expressions.
Truth tables describe the possible states of a system. Boolean expressions provide a formalism for hardware implementation. Although equivalent, some Boolean expressions are more concise than others. Making concise Boolean expressions is the first step in optimising hardware.
A Universal Logic Gate
The Nand operation can express all the other Boolean operations. This means that we could build any computer architecture only using Nand operations.
This is a remarkable realisation, explained at length in Appendix 1 of the book. This appendix is gold and I will attempt to summarise on another opportunity. For now, the following simplifications describe the universality of the Nand gate:
-
Combining And, Or, and Not operators we can express any Boolean function.
-
And and Not together can represent Or. Thus by combining And and Not, we can express any Boolean function.
-
Nand could represent both And and Not. Thus Nand gates can express any Boolean function.
A functional complete operator is a Boolean operator which behaves as described. A functional complete operator can express all possible Boolean functions. In this regard Nand is not unique since Nor is another functional complete operator. We could build any computer using only Nor gates.
