2.2: A Universal Set of Boolean Operations

Last updated
Save as PDF

Page ID: 26947

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

When thinking about Boolean algebra, it is important to realize that Boolean values are binary, so any Boolean variable is limited to two values. Often these values will be True or False, but in reality any binary values can be used. In this textbook, the value 0 will be used for False, and 1 for True. The reason for using 0 and 1 is that it is a more natural and useful way to represent these values in an engineering context, which will hopefully become apparent to the reader as they continue their study of computer organization.

To be useful some minimum set of operations which can be used to manipulate those Boolean variables. For Boolean algebra this minimum set of operations will include just 3 operations, they are AND, OR, and NOT. The AND and OR operations are binary operations (operations that take two operands), and the NOT is a unary operation (operation that takes one operand). These operations will be defined formally using truth tables in the next section. For now they will be defined informally as follows:

the AND operator is f(A,B), where f(A,B) is 1 (true) where A, B are both 1 (true) otherwise it is 0 (false).
the OR operator is f(A,B), where f(A,B) is 1 (true) is A or B or both A and B are 1(true), otherwise it is 0 (false).
the NOT operator is f(A), where f(A) is 1 (true) if A is 0 (false), and f(A) is 0 (false) if a is 1 (true).

This leads to a question as to why these three, and only these three, operations are chosen. The answer is that these three operations are universal Boolean operations. In this context, universal means that any Boolean function can be reduced to combinations of these three operations. Therefore, there is never a need to define any other Boolean operations to calculate a Boolean function. Other useful Boolean operations will be introduced in this textbook, but realize that these operations can be reduced to simply AND, OR, and NOT operations². The proof of this will be left to the exercises at the end of this chapter.

In this textbook, the AND operation will be written using the multiplication sign, "*", and the result call a product; the OR operation will be written using the "+" sign, and will be called a sum; the NOT operation will be shown by following the variable with a single "'" mark, e.g. A' is NOT-A. Note also that the "*" symbol can be dropped as in standard algebra, so "A*B" can also be written simply as "AB".

² This result, and AND, OR, and NOT are Universal over Boolean functions is even more amazing when it is realized that any effectively computable function is computable using only Boolean functions. This result, that any effectively computable function is computable with just the operations AND, OR, and NOT, was personally mind blowing when I first understood it.