Page 44 - DCAP108_DIGITAL_CIRCUITS_AND_LOGIC_DESIGNS

Unit 3: Boolean Algebra

employ. If you are interested in circuit design and optimization, you will need to consult a text Notes
on logic design for better techniques.
3.1 Boolean Algebra

You have seen logic gates and how they can operate on binary numbers. Now, we need a
mathematical framework for describing the relationship between logic gates and binary numbers.
That framework is Boolean algebra. This document of course provides only an introduction to
Boolean algebra, refer to dedicated texts for a detailed discussion of the subject.

The English mathematician George Boole (1815–1864) sought to give symbolic form to Aristotle’s
system of logic. Boole wrote a treatise on the subject in 1854, titled An Investigation of the Laws of
Thought on Which Are Founded the Mathematical Theories of Logic and Probabilities, which codified
several rules of relationship between mathematical quantities limited to one of two possible values:
true or false, 1 or 0. His mathematical system became known as Boolean algebra.
All arithmetic operations performed with Boolean quantities have but one of two possible
outcomes: either 1 or 0. There is no such thing as “2” or “–1” or “1/2” in the Boolean world. It is
a world in which all other possibilities are invalid by fiat. As one might guess, this is not the kind
of math you want to use when balancing a chequebook or calculating current through a resistor.
However, Claude Shannon of MIT fame recognized how Boolean algebra could be applied to
on-and-off circuits, where all signals are characterized as either “high” (1) or “low” (0). His 1938
thesis, titled A Symbolic Analysis of Relay and Switching Circuits, put Boole’s theoretical work to use
in a way Boole never could have imagined, giving us a powerful mathematical tool for designing
and analyzing digital circuits.
In this section, you will find a lot of similarities between Boolean algebra and “normal” algebra,
the kind of algebra involving so-called real numbers. Just bear in mind that the system of numbers
defining Boolean algebra is severely limited in terms of scope, and that there can only be one
of two possible values for any Boolean variable: 1 or 0. Consequently, the “Laws” of Boolean
algebra often differ from the “Laws” of real-number algebra, making possible such statements
as 1 + 1 = 1, which would normally be considered absurd. Once you comprehend the premise of
all quantities in Boolean algebra being limited to the two possibilities of 1 and 0, and the general
philosophical principle of Laws depending on quantitative definitions, the “nonsense” of Boolean
algebra disappears.

3.1.1 Boolean Arithmetic
Let us begin our exploration of Boolean algebra by adding numbers together:

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1

The first three sums make perfect sense to anyone familiar with elementary addition. The last
sum, though, is quite possibly responsible for more confusion than any other single statement in
digital electronics, because it seems to run contrary to the basic principles of mathematics. Well,
it does contradict principles of addition for real numbers, but not for Boolean numbers. There is
no such thing as “2” within the scope of Boolean values. Since the sum “1 + 1” certainly is not 0,
it must be 1 by process of elimination.

It does not matter how many or few terms we add together, either. Consider the following sums:

LOVELY PROFESSIONAL UNIVERSITY 39