1

BOOLEAN ALGEBRAS

• IMPORTANT CLASS OF ALGEBRAS EXTENSIVELY USED

FOR MANY PURPOSES
• BASIS OF THE SWITCHING ALGEBRA (SA) USED FOR
FORMAL TREATMENT OF SWITCHING CIRCUITS:
– TRANSFORMATION OF SWITCHING EXPRESSIONS
– IDENTITIES FROM BA ENABLE GRAPHICAL AND TAB-
ULAR TECHNIQUES FOR MINIMIZATION OF SWITCH-
ING EXPRESSIONS LEADING TO SIMPLER/FASTER CIR-
CUITS

Introduction to Digital Systems Appendix A – Boolean Algebras

 2
DEFINITION OF BOOLEAN ALGEBRA

A BOOLEAN ALGEBRA IS A TUPLE {B, , ·}:

• B IS A SET OF ELEMENTS;

• AND · ARE BINARY OPERATIONS APPLIED OVER THE

ELEMENTS OF B,
SATISFYING THE FOLLOWING POSTULATES:
P1: If a, b ∈ B, then
(i) a b = b a
(ii) a · b = b · a
That is, and · are COMMUTATIVE.
P2: If a, b, c ∈ B, then
(i) a (b · c) = (a b) · (a c)
(ii) a · (b c) = (a · b) (a · c)
Introduction to Digital Systems Appendix A – Boolean Algebras
 3

P3: THE SET B HAS TWO DISTINCT IDENTITY ELEMENTS,

DENOTED AS 0 AND 1, SUCH THAT FOR EVERY ELEMENT
IN B
(i) 0 a = a 0 = a
(ii) 1 · a = a · 1 = a
THE ELEMENTS 0 AND 1 ARE CALLED THE ADDITIVE
IDENTITY ELEMENT AND THE MULTIPLICATIVE IDEN-
TITY ELEMENT, respectively.
P4: FOR EVERY ELEMENT a ∈ B THERE EXISTS AN EL-
EMENT a′, CALLED THE COMPLEMENT OF a, SUCH
THAT
(i) a a′ = 1
(ii) a · a′ = 0

Introduction to Digital Systems Appendix A – Boolean Algebras

 4
COMMENTS

• SYMBOLS AND · ARE NOT THE ARITHMETIC

ADDITION AND MULTIPLICATION SYMBOLS
For convenience and · called “plus” and “times”
Expressions a b and a · b called “sum” and “product,”
and · also called “or” and “and”
• THE ELEMENTS OF THE SET B ARE CALLED CONSTANTS:
0 AND 1 ARE CONSTANTS
• SYMBOLS REPRESENTING ARBITRARY ELEMENTS OF B
ARE VARIABLES: a, b and c in the postulates are variables.

Introduction to Digital Systems Appendix A – Boolean Algebras

 5

• PRECEDENCE ORDERING DEFINED ON THE OPERA-

TORS: · HAS PRECEDENCE OVER .
a (b · c) can be written as a bc
• SYMBOLS a, b, c, . . . IN THEOREMS AND POSTULATES ARE
GENERIC VARIABLES: THEY CAN BE SUBSTITUTED
BY
– COMPLEMENTED VARIABLES
– EXPRESSIONS (FORMULAS)

Introduction to Digital Systems Appendix A – Boolean Algebras

 6
SWITCHING ALGEBRA

• SERVES THE SAME ROLE FOR SWITCHING FUNCTIONS AS

THE ORDINARY ALGEBRA DOES FOR ARITHMETIC FUNC-
TIONS
• SA: SET OF TWO ELEMENTS B = {0, 1}, AND TWO OP-
ERATIONS and AND or:
and 0 1 or 0 1
0 00 0 01
1 01 1 11
• THESE OPERATIONS ARE USED TO EVALUATE SWITCH-
ING EXPRESSIONS

Introduction to Digital Systems Appendix A – Boolean Algebras

 7
Theorem 1 THE SWITCHING ALGEBRA IS
A BOOLEAN ALGEBRA.

Introduction to Digital Systems Appendix A – Boolean Algebras

 8
PROOF ...

SHOW THAT SA SATISFIES POSTULATES OF BA: FOR EX-

AMPLE

[P2:] DISTRIBUTIVITY of ( ) and (·) shown by perfect induc-

tion:
abc a bc (a b)(a c)
000 0 0
001 0 0
010 0 0
011 1 1
100 1 1
101 1 1
110 1 1
111 1 1
Since a bc = (a b)(a c) for all cases, P2(i) is satisfied. Show
Introduction to Digital Systems Appendix A – Boolean Algebras
 9
that P2(ii) is also satisfied.

Introduction to Digital Systems Appendix A – Boolean Algebras

 10
IMPORTANT THEOREMS IN BOOLEAN ALGEBRA

Theorem 2 PRINCIPLE OF DUALITY.

EVERY ALGEBRAIC IDENTITY DEDUCIBLE FROM THE POS-
TULATES OF A BOOLEAN ALGEBRA REMAINS VALID IF
• the operations and · are interchanged throughout; and

• the identity elements 0 and 1 are also interchanged throughout.

• This theorem is useful because it reduces the number of dif-
ferent theorems that must be proven: every theorem has its dual.

Introduction to Digital Systems Appendix A – Boolean Algebras

 11
Theorem 3 EVERY ELEMENT IN B HAS A UNIQUE
COMPLEMENT.
Proof: Let a ∈ B; let us assume that a′1 and a′2 are both comple-
ments of a. Then, using the postulates we can perform the following
transformations:
a′1 = a′1 · 1 by P3(ii) (identity)
= a′1 · (a a′2) by hypothesis (a′2 is the complement of a)
= a′1 · a a′1 · a′2 by P2(ii) (distributivity)
= a · a′1 a′1 · a′2 by P1(ii) (commutativity)
= 0 a′1 · a′2 by hypothesis (a′1 is complement of a)
= a′1 · a′2 by P3(i) (identity)
Changing the index 1 for 2 and vice versa, and repeating all steps
for a′2 we get
a′2 = a′2 · a′1
= a′1 · a′2 by P1(ii)
and therefore a′2 = a′1.
Introduction to Digital Systems Appendix A – Boolean Algebras
 12
The uniqueness of the complement of an element allows consid-
ering ′ as a unary operation called complementation.

Introduction to Digital Systems Appendix A – Boolean Algebras

 13
Theorem 4 For any a ∈ B:
(1) a 1 = 1
(2) a · 0 = 0

Introduction to Digital Systems Appendix A – Boolean Algebras

 14
Proof: Using the postulates, we can perform the following trans-
formations:
Case (1): by
a 1 = 1 · (a 1) P3 (ii)
= (a a′) · (a 1) P4 (i)
= a (a′ · 1) P2 (i)
= a a′ P3 (ii)
=1 P4 (i)

Case (2): by
a · 0 = 0 (a · 0) P3 (i)
= (a · a′) (a · 0) P4 (ii)
= a · (a′ 0) P2 (ii)
= a · a′ P3 (i)
=0 P4 (ii)
(2) can also be proven by means of (1) and the principle of duality.

Introduction to Digital Systems Appendix A – Boolean Algebras

 15
Theorem 5 THE COMPLEMENT OF THE ELEMENT 1 IS 0,
AND VICE VERSA. That is,
(1) 0′ = 1
(2) 1′ = 0
Proof: By Theorem 4,
0 1= 1 and
0·1 = 0
Since, by Theorem 3, the complement of an element is unique,
Theorem 5 follows.

Introduction to Digital Systems Appendix A – Boolean Algebras

 16
Theorem 6 IDEMPOTENT LAW.
For every a ∈ B
(1) a a = a
(2) a · a = a
Proof:
by
(1): a a = (a a) · 1 P3 (ii)
= (a a) · (a a′) P4 (i)
= (a (a · a′)) P2 (i)
=a 0 P4 (ii)
=a P3 (i)

(2): duality

Introduction to Digital Systems Appendix A – Boolean Algebras

 17
Theorem 7 INVOLUTION LAW.
For every a ∈ B,
(a′)′ = a
Proof: From the definition of complement (a′)′ and a are both
complements of a′. But, by Theorem 3, the complement of an
element is unique, which proves the theorem.

Introduction to Digital Systems Appendix A – Boolean Algebras

 18
Theorem 8 ABSORPTION LAW. For every pair of elements a, b ∈
B,
(1) a a · b = a
(2) a · (a b) = a
Proof:
by
(1): a ab = a · 1 ab P3 (ii)
= a(1 b) P2 (ii)
= a(b 1) P1 (i)
=a·1 Theorem 4 (1)
=a P3 (ii)

(2) duality

Introduction to Digital Systems Appendix A – Boolean Algebras

 19
Theorem 9 FOR EVERY PAIR OF ELEMENTS a, b ∈ B,
(1) a a′b = a b
(2) a(a′ b) = ab

Proof:
by
(1): a a′b = (a a′)(a b) P2 (i)
= 1 · (a b) P4 (i)
=a b P3 (ii)

(2): duality

Introduction to Digital Systems Appendix A – Boolean Algebras

 20
ASSOCIATIVITY OF OR and AND

Theorem 10 In a Boolean algebra, each of the binary operations

( ) and (·) is associative. That is, for every a, b, c ∈ B,
(1) a (b c) = (a b) c
(2) a(bc) = (ab)c
Corollary 1
1. The order in applying the operator among n elements does
not matter. For example
a (b (c (d e))) = (((a b) c) d) e
= a ((b c) d)) e
=a b c d e
2. The order in applying the · operator among n elements does not
matter.

Introduction to Digital Systems Appendix A – Boolean Algebras

 21
DeMorgan’s Law

Theorem 11 For every pair of elements a, b ∈ B:

(1) (a b)′ = a′b′
(2) (ab)′ = a′ b′

By duality,
(a · b)′ = a′ b′

Introduction to Digital Systems Appendix A – Boolean Algebras

 22
Theorem 12 GENERALIZED DeMorgan’s LAW.
Let {a, b, . . . , c, d} be a set of elements in a Boolean algebra.
Then, the following identities hold:
(1) (a b . . . c d)′ = a′b′ . . . c′d′
(2) (ab . . . cd)′ = a′ b′ . . . c′ d′

Introduction to Digital Systems Appendix A – Boolean Algebras

 23

DeMorgan’s theorems useful in manipulating switching expres-

sions:

Example: find the complement of a switching expression

[(a b′)(c′ d′) (f ′ g)′]′ = [(a b′)(c′ d′)]′[(f ′ g)′]′

= [(a b′)′ (c′ d′)′](f ′ g)
= (a′b cd)(f ′ g)

Introduction to Digital Systems Appendix A – Boolean Algebras

 24
OTHER EXAMPLES OF BOOLEAN ALGEBRAS

ALGEBRA OF SETS. The elements of B: set of all subsets

of a set S
(P (S)). The operations: set-union (∪) and set-intersection
(∩).

M = (P (S), ∪, ∩)
ALGEBRA OF LOGIC (PROPOSITIONAL CALCULUS).
The elements B: T and F (true and false). The operations:
logical and and logical or.
This algebra is isomorphic with the switching algebra.

Introduction to Digital Systems Appendix A – Boolean Algebras