<<

. 2
( 13)



>>

An important method of combining two statements, A and B, in a sentence is
by a conditional, such as “If A, then B,” or equivalently, “A implies B,” which
we shall write as “A ’ B.” How does the truth or falsity of such a conditional
depend on that of A and B? Consider the following sentences:

x > 4, then x 2 > 16.
1. If
x > 4, then x 2 = 2.
2. If
2 = 3, then 0.2 = 0.3.
3. If
2 = 3, then the moon is made of green cheese.
4. If

Clearly, if A is true, then B must also be true for the sentence “A ’ B”
to be true. However, if A is not true, then the sentence “If A, then B” has
no standard meaning in everyday language. Let us take “A ’ B” to mean that
we cannot have A true and B not true. This implies that the truth value of the
18 2 BOOLEAN ALGEBRAS

TABLE 2.5. Truth tables for Conditional and
Biconditional Statements
A’B A⇐B A”B
A B
F F T T T
F T T F F
T F F T F
T T T T T


statement “A ’ B” is the same as that of “not (A and not B).” Let us write
§, ∨, and for “and,” “or,” and “not,” respectively. Then “A ’ B” is equivalent
to (A § B ) = A ∨ B. Thus “A ’ B” is true if A is false or if B is true.
Using this de¬nition, statements 1, 3, and 4 are all true, whereas statement 2
is false.
We can combine two conditional statements to form a biconditional statement
of the form “A if and only if B” or “A ” B.” This has the same truth value as
“(A ’ B) and (B ’ A)” or, equivalently, (A § B) ∨ (A § B ). Another way
of expressing this biconditional is to say that “A is a necessary and suf¬cient
condition for B.” It is seen from Table 2.5 that the statement “A ” B” is true if
either A and B are both true or A and B are both false.

Example 2.14. Apply this propositional calculus to determine whether a certain
politician™s arguments are consistent. In one speech he states that if taxes are
raised, the rate of in¬‚ation will drop if and only if the value of the dollar does
not fall. On television, he says that if the rate of in¬‚ation decreases or the value
of the dollar does not fall, taxes will not be raised. In a speech abroad, he states
that either taxes must be raised or the value of the dollar will fall and the rate of
in¬‚ation will decrease. His conclusion is that taxes will be raised, but the rate of
in¬‚ation will decrease, and the value of the dollar will not fall.

Solution. We write

A to mean “Taxes will be raised,”
B to mean “The rate of in¬‚ation will decrease,”
C to mean “The value of the dollar will not fall.”

The politician™s three statements can be written symbolically as

(i) A ’ (B ” C).
(ii) (B ∨ C) ’ A .
(iii) A ∨ (C § B).

His conclusion is (iv) A § B § C.
The truth values of the ¬rst two statements are equivalent to those of the
following:
SWITCHING CIRCUITS 19

TABLE 2.6. Truth Tables for the Politician™s Arguments
(i) § (ii) § (iii) (i) § (ii) § (iii) ’ (iv)
(i) (ii) (iii) (iv)
A B C
F F F T T F F F T
F F T T T F F F T
F T F T T T T F F
F T T T T F F F T
T F F T T T T F F
T F T F F T F F T
T T F F F T F F T
T T T T F T F T T


(i) A ∨ ((B § C) ∨ (B § C )).
(ii) (B ∨ C) ∨ A .

It follows from Table 2.6 that (i) § (ii) § (iii) ’ (iv) is not a tautology; that
is, it is not always true. Therefore, the politician™s arguments are incorrect. They
break down when A and C are false and B is true, and when B and C are false
and A is true.


SWITCHING CIRCUITS

In this section we use boolean algebra to analyze some simple switching circuits.
A switch is a device with two states; state 1 is the “on” state, and state 0 the “off”
state. An ordinary household light switch is such a device, but the theory holds
equally well for more sophisticated electronic or magnetic two-state devices. We
analyze circuits with two terminals: The circuit is said to be closed if current can
pass between the terminals, and open if current cannot pass.
We denote a switch A by the symbol in Figure 2.8. We assign the value 1 to
A if the switch A is closed and the value 0 if it is open. We denote two switches
by the same letter if they open and close simultaneously. If B is a switch that is
always in the opposite position to A (that is, if B is open when A is closed, and
B is closed when A is open), denote switch B by A .
The two switches A and B in Figure 2.9 are said to be connected in series. If
we connect this circuit to a power source and a light as in Figure 2.10, we see
that the light will be on if and only if A and B are both switched on; we denote
this series circuit by A § B. Its effect is shown in Table 2.7.
The switches A and B in Figure 2.11 are said to be in parallel, and this circuit
is denoted by A ∨ B because the circuit is closed if either A or B is switched on.



A B
A

Figure 2.8. Switch A. Figure 2.9. Switches in series.
20 2 BOOLEAN ALGEBRAS


A B
A


Power source Light B
Figure 2.10. Series circuit. Figure 2.11. Switches in parallel.


TABLE 2.7. Effect of the Series Circuit
Circuit A § B
Switch A Switch B Light
0 (off) 0 (off) 0 (open) off
0 (off) 1 (on) 0 (open) off
1 (on) 0 (off) 0 (open) off
1 (on) 1 (on) 1 (closed) on



A

B′

A′
B
Figure 2.12. Series-parallel circuit.


The reader should be aware that many books on switching theory use the
notation + and · instead of ∨ and §, respectively.
Series and parallel circuits can be combined to form circuits like the one in
Figure 2.12. This circuit would be denoted by (A ∨ (B § A )) § B . Such circuits
are called series-parallel switching circuits.
In actual practice, the wiring diagram may not look at all like Figure 2.12,
because we would want switches A and A together and B and B together.
Figure 2.13 illustrates one particular form that the wiring diagram could take.
Two circuits C1 and C2 involving the switches A, B, . . . are said to be equiv-
alent if the positions of the switches A, B, . . ., which allow current to pass,



Switch A

Switch B


Figure 2.13. Wiring diagram of the circuit.
DIVISORS 21


B A B

A
A C
C
A § (B ∨ C) = (A § B) ∨ (A § C)

Figure 2.14. Distributive law.


are the same for both circuits. We write C1 = C2 to mean that the circuits are
equivalent. It can be veri¬ed that all the axioms for a boolean algebra are valid
when interpreted as series-parallel switching circuits. For example, Figure 2.14
illustrates a distributive law. The zero corresponds to a circuit that is always
open, and the unit corresponds to a circuit that is always closed. The com-
plement C of a circuit C is open whenever C is closed and closed when C
is open.


DIVISORS

As a last example, we are going to construct boolean algebras based on the
divisibility relation on the set P of positive integers. Given two integers d and
a in P, we write d|a (and call d a divisor of a) if a = qd for some q ∈ P. If
p 2 in P, and the only divisors of p are 1 and p, then p is called a prime.
Thus, the ¬rst few primes are 2, 3, 5, 7, 11, . . .. A fundamental fact about P is
the prime factorization theorem: Every number a ∈ P is uniquely a product
of primes.—
For example, the prime factorizations of 110 and 12 are 110 = 2 · 5 · 11 and
12 = 22 · 3. If a = p1 1 p2 2 · · · pr r is the prime factorization of a ∈ P where the
aa a

pi are distinct primes, the divisors d of a can be described as follows:
dd
d = p1 1 p2 2 · · · pr r
d
if and only if where 0 ai for each i.
d|a di

Hence the divisors of 12 = 22 31 in P are 1 = 20 30 , 2 = 21 30 , 4 = 22 30 , 3 =
20 31 , 6 = 21 31 , and 12 = 22 31 .
Given a and b in P, let p1 , p2 , . . . , pr denote the distinct primes that are divisors
aa bb
of either a or b. Hence we can write a = p1 1 p2 2 · · · pr r and b = p1 1 p2 2 · · · pr r ,
a b

where ai 0 and bi 0 for each i. Then the greatest common divisor d =
gcd(a, b) and the least common multiple m = lcm(a, b) of a and b are de¬ned by
min(a,b) min(a,b) max(a,b) max(a,b)
d = p1 · · · pr and m = p1 · · · pr
min(a,b) max(a,b)
p2 p2 .

See Appendix 2 for a proof of the prime factorization theorem.
22 2 BOOLEAN ALGEBRAS


It follows that d is the unique integer in P that is a divisor of both a and b, and
is a multiple of every such common divisor (hence the name). Similarly, m is
the unique integer in P that is a multiple of both a and b, and is a divisor of
every such common multiple. For example, gcd(2, 3) = 1 and gcd(12, 28) = 4,
while lcm(2, 3) = 6 and lcm(12, 28) = 84.
With this background, we can describe some new examples of boolean alge-
bras. Given n ∈ P, let
Dn = {d ∈ P|d divides n}.

It is clear that gcd and lcm are commutative binary operations on Dn , and it is
easy to verify that the zero is 1 and the unit is n. To prove the distributive laws,
let a, b, and c be elements of Dn , and write

a = p1 1 p2 2 · · · pr r , b = p1 1 p2 2 · · · pr r , and c = p11 p22 · · · pr r ,
aa bb cc
a b c


where p1 , p2 , . . . , pr are the distinct primes dividing at least one of a, b, and c,
and where ai 0, bi 0, and ci 0 for each i. Then the ¬rst distributive law
states that
gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c)).

If we write out the prime factorization of each side in terms of the primes pi , this
holds if and only if for each i, the powers of pi are equal on both sides, that is,

min(ai , max(bi , ci )) = max(min(ai , bi ), min(ai , ci )).

To verify this, observe ¬rst that we may assume that bi ci (bi and ci can be
interchanged without changing either side), and then check the three cases ai
bi , bi ai ci , and ci ai separately. Hence the ¬rst distributive law holds; the
other distributive law and the associative laws are veri¬ed similarly. Thus (Dn ,
gcd, lcm) satis¬es all the axioms for a boolean algebra except for the existence
of a complement.
But complements need not exist in general: For example, 6 has no comple-
ment in D18 = {1, 2, 3, 6, 9, 18}. Indeed, if 6 has a complement 6 in D18 , then
gcd(6, 6 ) = 1, so we must have 6 = 1. But then lcm(6, 6 ) = 6 and this is not
the unit of D18 . Hence 6 has no complement, so D18 is not a boolean alge-
bra. However, all is not lost. The problem in D18 is that the prime factorization
18 = 2 · 32 has a repeated prime factor. An integer n ∈ P is called square-free
if it is a product of distinct primes with none repeated (for example, every prime
is square-free, as are 6 = 2 · 3, 10 = 2 · 5, 30 = 2 · 3 · 5, etc.) If n is square-free,
it is routine to verify that the complement of d ∈ Dn is d = n/d, and we have

Example 2.15. If n ∈ P is square-free, then (Dn , gcd, lcm, ) is a boolean alge-
bra where d = n/d for each d ∈ Dn .

The interpretations of the various boolean algebra terms are given in Table 2.8.
POSETS AND LATTICES 23

TABLE 2.8. Dictionary of Boolean Algebra Terms
Boolean Switching Propositional
P(X) Dn
Algebra Circuits Logic
§ © Series And gcd
∨ ∪ Parallel Or lcm
’ a = n/a
Opposite Not
0 ˜ Open Contradiction 1
1 Closed Tautology
X n
= = =
Equivalent circuit Logically equivalent



POSETS AND LATTICES

Boolean algebras were derived from the algebra of sets, and there is one important
relation between sets that we have neglected to generalize to boolean algebras,
namely, the inclusion relation. This relation can be de¬ned in terms of the union
operation by
A ⊆ B if and only if A © B = A.

on any boolean algebra (K, §, ∨, )
We can de¬ne a corresponding relation
using the meet operation:

A § B = A.
if and only if
A B

If the boolean algebra is the algebra of subsets of X, this relation is the usual
inclusion relation.

Proposition 2.16. A § B = A if and only if A ∨ B = B. Hence either of the
these conditions will de¬ne the relation .

Proof. If A § B = A, then it follows from the absorption law that A ∨ B =
(A § B) ∨ B = B. Similarly, if A ∨ B = B, it follows that A § B = A.

Proposition 2.17. If A, B, and C are elements of a boolean algebra, K, the
following properties of the relation hold.

(i) A A. (re¬‚exivity)
A, then A = B.
(ii) If A B and B (antisymmetry)
(iii) If A B and B C, then A C. (transitivity)
Proof

(i) A § A = A is an idempotent law.
(ii) If A § B = A and B § A = B, then A = A § B = B § A = B.
(iii) If A § B = A and B § C = B, then A § C = (A § B) § C
= A § (B § C) = A § B = A.
24 2 BOOLEAN ALGEBRAS

TABLE 2.9. Partial Order Relation in Various Boolean Algebras

Series-Parallel Divisors of a
Boolean Algebra of Switching Propositional Square-Free
Algebra Subsets Circuits Logic Integer

A§B =A A©B =A A§B =A (A and B) = A gcd(a, b) = a
A⊆B A’B A’B
AB a|b
A is less than A is a subset If A is closed, A implies B a divides b
or equal to B of B then B is
closed



A relation satisfying the three properties in Proposition 2.17 is called a partial
order relation, and a set with a partial order on it is called a partially ordered
set or poset for short. The interpretation of the partial order in various boolean
algebras is given in Table 2.9.
A partial order on a ¬nite set K can be displayed conveniently in a poset
diagram in which the elements of K are represented by small circles. Lines are
drawn connecting these elements so that there is a path from A to B that is always
directed upward if and only if A B. Figure 2.15 illustrates the poset diagram
of the boolean algebra of subsets (P ({a, b}, )©, ∪, ’ ). Figure 2.16 illustrates
the boolean algebra D110 = {1, 2, 5, 11, 10, 22, 55, 110} of positive divisors of
110 = 2 · 5 · 11. The partial order relation is divisibility, so that there is an upward
path from a to b if and only if a divides b.
The following proposition shows that has properties similar to those of the
inclusion relation in sets.

Proposition 2.18. If A, B, C are elements of a boolean algebra (K, §, ∨, ),
then the following relations hold:

(i) A § B A.
(ii) A A ∨ B.
C implies that A ∨ B
(iii) A C and B C.



110


10 22 55
{a, b}
5
2 11
{a} {b}
f 1

Poset diagram of D110 .
Figure 2.15. Poset diagram of P ({a, b}). Figure 2.16.
POSETS AND LATTICES 25


B if and only if A § B = 0.
(iv) A
(v) 0 A and A 1 for all A.

Proof

(A § B) § A = (A § A) § B = A § B so A § B A.
(i)
A § (A ∨ B) = A, so A A ∨ B.
(ii)
(A ∨ B) § C = (A § C) ∨ (B § C) = A ∨ B.
(iii)
If A B, then A § B = A and A § B = A § B § B = A § 0 = 0. On
(iv)
the other hand, if A § B = 0, then A B because

A = A § 1 = A § (B ∨ B ) = (A § B) ∨ (A § B )
= (A § B) ∨ 0 = A § B.

(v) 0 § A = 0 and A § 1 = A.

Not all posets are derived from boolean algebras. A boolean algebra is an
extremely special kind of poset. We now determine conditions which ensure that
a poset is indeed a boolean algebra. Given a partial order on a set K, we have
to ¬nd two binary operations that correspond to the meet and join.
An element d is said to be the greatest lower bound of the elements a and
b in a partially ordered set if d a, d b, and x is another element, for which
x a, x b, then x d. We denote the greatest lower bound of a and b by
a § b. Similarly, we can de¬ne the least upper bound and denote it by ∨. It
follows from the antisymmetry of the partial order relation that each pair of
elements a and b can have at most one greatest lower bound and at most one
least upper bound.
A lattice is a partially ordered set in which every two elements have a greatest
lower bound and a least upper bound. Thus Dn is a lattice for every integer n ∈ P,
so by the discussion preceding Example 2.15, D18 is a lattice that is not a boolean
algebra (see Figure 2.17).
We can now give an alternative de¬nition of a boolean algebra in terms of a
lattice: A boolean algebra is a lattice that has universal bounds (that is, elements
0 and 1 such that 0 a and a 1 for all elements a) and is distributive and
complemented (that is, the distributive laws for § and ∨ hold, and complements
exist). It can be veri¬ed that this de¬nition is equivalent to our original one.
In Figure 2.18, the elements c and d have a least upper bound b but no greatest
lower bound.
We note in passing that the discussion preceding Example 2.15 shows that for
each n ∈ P, the poset Dn is a lattice in which the distributive laws hold, but it is
not a boolean algebra unless n is square-free. For further reading on lattices in
applied algebra, consult, Davey and Priestley [16] or Lidl and Pilz [10].
26 2 BOOLEAN ALGEBRAS


18


6 9


2 3


1

Figure 2.17. Lattice that is not a boolean algebra.



b
a



c d

e

Figure 2.18. Poset that is not a lattice.



NORMAL FORMS AND SIMPLIFICATION OF CIRCUITS

If we have a complicated switching circuit represented by a boolean expression,
such as
(A § (B ∨ C ) ) ∨ ((B § C ) ∨ A ),

we would like to know if we can build a simpler circuit that would perform the
same function. In other words, we would like to reduce this boolean expression
to a simpler form. In actual practice, it is usually desirable to reduce the circuit to
the one that is cheapest to build, and the form this takes will depend on the state
of the technology at the time; however, for our purposes we take the simplest
form to mean the one with the fewest switches. It is dif¬cult to ¬nd the simplest
form for circuits with many switches, and there is no one method that will lead to
that form. However, we do have methods for determining whether two boolean
expressions are equivalent. We can reduce the expressions to a certain normal
form, and the expressions will be the same if and only if their normal forms are
the same. We shall look at one such form, called the disjunctive normal form.
In the boolean algebra of subsets of a set, every subset can be expressed as
a union of singleton sets, and this union is unique to within the ordering of the
terms. We shall obtain a corresponding result for arbitrary ¬nite boolean algebras.
The elements that play the role of singleton sets are called atoms. Here an atom
in a boolean algebra (K, §, ∨, ) is a nonzero element B for which

B §Y =B B § Y = 0 for each Y ∈ K.
or
NORMAL FORMS AND SIMPLIFICATION OF CIRCUITS 27


Thus B is an atom if Y B implies that Y = 0 or Y = B. This implies that the
atoms are the elements immediately above the zero element in the poset diagram.
In the case of the algebra of divisors of a square-free integer, the atoms are the
primes, because the de¬nition of b being prime is that y|b implies that y = 1 or
y = b.
We now give a more precise description of the algebra of switching circuits.
The atoms of the algebra and the disjunctive normal form of an expression will
become clear from this description.
An n-variable switching circuit can be viewed as a black box containing
n independent switches A1 , A2 , . . . , An , as shown in Figure 2.19, where each
switch can be either on or off. The effect of such a circuit can be tested by trying
all the 2n different combinations of the n switches and observing when the box
allows current to pass. In this way, each circuit de¬nes a function of n variables
A1 , A2 , . . . , An :
f : {0, 1}n ’ {0, 1},

which we call the switching function of the circuit. Two circuits give rise to
the same switching function if and only if they are equivalent.
For example, the circuit in Figure 2.20, corresponding to the expression
(A ∨ B ) § (C ∨ A ), gives rise to the switching function f : {0, 1}3 ’ {0, 1}
given in Table 2.10.


A1 A2 An
• • •



Figure 2.19. n-Variable switching circuit.


A C




B′ A′
Circuit (A ∨ B ) § (C ∨ A ).
Figure 2.20.


TABLE 2.10. Switching Function
f = (A ∨ B ) § (C ∨ A )
A B C
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
28 2 BOOLEAN ALGEBRAS


Denote the set of all n-variable switching functions from {0, 1}n to {0, 1} by
Fn . Each of the 2n elements in the domain of such a function can be mapped to
either of the two elements in the codomain. Therefore, the number of different
n-variable switching functions, and hence the number of different circuits with
n
n switches, is 22 .
Let f and g be the switching functions of two circuits of the n-variables
A1 , A2 , . . . , An . When these circuits are connected in series or in parallel, they
give rise to the switching functions f § g or f ∨ g, respectively, where

(f § g)(A1 , . . . , An ) = f (A1 , . . . , An ) § g(A1 , . . . , An )

and
(f ∨ g)(A1 , . . . , An ) = f (A1 , . . . , An ) ∨ g(A1 , . . . , An ).

The switching function of the opposite circuit to that de¬ning f is f , where

f (A1 , . . . , An ) = (f (A1 , . . . , An )) .

Theorem 2.19. The set of n-variable switching functions forms a boolean alge-
n
bra (Fn , §, ∨, ) that contains 22 elements.

Proof. It can be veri¬ed that (Fn , §, ∨, ) satis¬es all the axioms of a boolean
algebra. The zero element is the function whose image is always 0, and the unit
element is the function whose image is always 1.

The boolean algebra of switching functions of two variables contains 16 ele-
ments, which are displayed in Table 2.11. For example, f6 (A, B) = 0 if A = B,
and 1 if A = B. This function is the exclusive OR function or a modulo 2 adder.
It is also the symmetric difference function, where the symmetric difference of
A and B in a boolean algebra is de¬ned by

A B = (A § B ) ∨ (A § B).

The operations NAND and NOR stand for “not and” and “not or,” respectively;
these are discussed further in the section “Transistor Gates.”
As an example of the operations in the boolean algebra F2 , we calculate the
meet and join of f10 and f7 , and the complement of f10 in Table 2.12. We
see that f10 § f7 = f2 , f10 ∨ f7 = f15 and f10 = f5 . These correspond to the
relations B § (A ∨ B) = A § B , B ∨ (A ∨ B) = 1, and (B ) = B.
In the boolean algebra Fn , f g if and only if f § g = f , which happens if
g(A1 , . . . , An ) = 1 whenever f (A1 , . . . , An ) = 1. The atoms of Fn are therefore
the functions whose image contains precisely one nonzero element. Fn contains
2n atoms, and the expressions that realize these atoms are of the form
A±1 § A±2 § · · · § A±n , where each A±i = Ai or Ai .
n
1 2 i
NORMAL FORMS AND SIMPLIFICATION OF CIRCUITS 29

TABLE 2.11. Two-Variable Switching Functions
0 0 1 1 Expressions in A and B
A
0 1 0 1 Representing the Function
B
0 0 0 0 0
f0
A§B
0 0 0 1
f1
A § B or A ’ B
0 0 1 0
f2
0 0 1 1
f3 A
A § B or A ⇐ B
0 1 0 0
f4
0 1 0 1
f5 B
0 1 1 0 A B or Exclusive OR(A, B)
f6
A∨B
0 1 1 1
f7
A § B or NOR(A, B)
1 0 0 0
f8
A B or A ” B
1 0 0 1
f9
1 0 1 0
f10 B
A ∨ B or A ⇐ B
1 0 1 1
f11
1 1 0 0
f12 A
A ∨ B or A ’ B
1 1 0 1
f13
A ∨ B or NAND(A, B)
1 1 1 0
f14
1 1 1 1 1
f15


TABLE 2.12. Some Operations in F 2
f10 § f7 f10 ∨ f7
A B f10 f7 f10
0 0 1 0 0 1 0
0 1 0 1 0 1 1
1 0 1 1 1 1 0
1 1 0 1 0 1 1


The 16 elements of F2 are illustrated in Figure 2.21, and the four atoms are
f1 , f2 , f4 , and f8 , which are de¬ned in Table 2.11.
To show that every element of a ¬nite boolean algebra can be written as a
join of atoms, we need three preliminary lemmas.

Lemma 2.20. If A, B1 , . . . , Br are atoms in a boolean algebra, then
A (B1 ∨ · · · ∨ Br ) if and only if A = Bi , for some i with 1 i r.

Proof. If A (B1 ∨ · · · ∨ Br ), then A § (B1 ∨ · · · ∨ Br ) = A; thus (A § B1 ) ∨
· · · ∨ (A § Br ) = A. Since each Bi is an atom, A § Bi = Bi or 0. Not all the
elements A § Bi can be 0, for this would imply that A = 0. Hence there is some i,
with 1 i r, for which A § Bi = Bi . But A is also an atom, so A = A § Bi =
Bi .
The implication the other way is straightforward

Lemma 2.21. If Z is a nonzero element of a ¬nite boolean algebra, there exists
an atom B with B Z.
30 2 BOOLEAN ALGEBRAS


f15



f7 f11 f13 f14


f3 f5 f9 f6 f10 f12



f1 f2 f4 f8


f0

Figure 2.21. Poset diagram of the boolean algebra of two-variable switching functions.


Proof. If Z is an atom, take B = Z. If not, then it follows from the de¬nition
of atoms that there exists a nonzero element Z1 , different from Z, with Z1 Z.
If Z1 is not an atom, we continue in this way to obtain a sequence of distinct
nonzero elements · · · Z3 Z2 Z1 Z, which, because the algebra is ¬nite,
must terminate in an atom B.

Lemma 2.22. If B1 , . . . , Bn are all the atoms of a ¬nite boolean algebra, then
Y = 0 if and only if Y § Bi = 0 for all i such that 1 i n.

Proof. Suppose that Y § Bi = 0 for each i. If Y is nonzero, it follows from the
previous lemma that there is an atom Bj with Bj Y . Hence Bj = Y § Bj = 0,
which is a contradiction, so Y = 0. The converse implication is trivial.

Theorem 2.23. Disjunctive Normal Form. Each element X of a ¬nite boolean
algebra can be written as a join of atoms

X = B± ∨ Bβ ∨ · · · ∨ Bω .

Moreover, this expression is unique up to the order of the atoms.

Proof. Let B± , Bβ , . . . , Bω be all the atoms less than or equal to X in the
partial order. It follows from Proposition 2.18(iii) that the join Y = B± ∨ Bβ ∨
· · · ∨ Bω X.
We will show that X § Y = 0, which, by Proposition 2.18(iv), is equivalent
to X Y . We have
X § Y = X § B± § · · · § Bω .

If B is an atom in the join Y , say B = B± , it follows that X § Y § B = 0,
since B± § B± = 0. If B is an atom that is not in Y , then X § Y § B = 0 also,
NORMAL FORMS AND SIMPLIFICATION OF CIRCUITS 31


because X § B = 0. Therefore, by Lemma 2.22, X § Y = 0, which is equivalent
to X Y . The antisymmetry of the partial order relation implies that X = Y .
To show uniqueness, suppose that X can be written as the join of two sets
of atoms
X = B± ∨ · · · ∨ Bω = Ba ∨ · · · ∨ Bz .

Now B± X; thus, by Lemma 2.20, B± is equal to one of the atoms on the
right-hand side, Ba , . . . , Bz . Repeating this argument, we see that the two sets of
atoms are the same, except possibly for their order.

In the boolean algebra of n-variable switching functions, the atoms are realized
by expressions of the form A±1 § A±2 § · · · § An ±n , where the ±i ™s are 0 or 1 and
1 2
Ai ±i = Ai , if ±i = 1, whereas Ai ±i = Ai , if ±i = 0. The expression A±1 § A±2 §
1 2
· · · § An ±n is included in the disjunctive normal form of the function f if and
only if f (±1 , ±2 , . . . , ±n ) = 1. Hence there is one atom in the disjunctive normal
form for each time the element 1 occurs in the image of the switching function.

Example 2.24. Find the disjunctive normal form for the expression
(B ∨ (A § C)) § ((A ∨ C) § B) , and check the result by using the axioms to
reduce the expression to that form.

Solution. We see from the values of the switching function in Table 2.13 that
the disjunctive normal form is (A § B § C ) ∨ (A § B § C).
From the axioms, we have
(B ∨ (A § C)) § ((A ∨ C) § B) = (B ∨ (A § C)) § ((A § C ) ∨ B )
= ((B ∨ (A § C)) § (A § C ))∨
((B ∨ (A § C)) § B )
= (B § A § C ) ∨ (A § C § A § C )∨
(B § B ) ∨ (A § C § B )
= (A § B § C ) ∨ 0 ∨ 0 ∨ (A § B § C)
= (A § B § C ) ∨ (A § B § C).

TABLE 2.13. Switching Function
(B ∨ (A § C)) § ((A ∨ C) § B)
A B C
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 0
32 2 BOOLEAN ALGEBRAS

TABLE 2.14. Switching Function
(A ∨ B) § B (A ∨ B) § (A § B) (A § B) § (A § B )
A B
0 0 0 0 0
0 1 0 1 0
1 0 1 1 1
1 1 0 0 0


Example 2.25. Determine whether any of the three expressions
(A ∨ B) § B , (A ∨ B) § (A § B) , and (A § B) § (A § B ) equivalent.

Solution. We see from Table 2.14 that (A ∨ B) § B = (A § B) § (A § B )
and that these are both equal to A § B .

The atoms in the boolean algebra F2 are realized by the expressions
A § B , A § B, A § B , and A § B. These atoms partition the Venn diagram
in Figure 2.22 into four disjoint regions. The disjunctive normal form for any
boolean expression involving the variables A and B can be calculated by shading
the region of the Venn diagram corresponding to the expression and then taking
the join of the atoms in the shaded region. Figure 2.23 illustrates the eight regions
of the corresponding Venn diagram for three variables.

A B


A § B′ A § B A′ § B



A′ § B′

Figure 2.22. Venn diagram for F2 .




A B
A § B § C′
A § B′ § C ′ A′ § B § C ′

A§B§C


A′ § B § C
A § B′ § C


A′ § B′ § C
C


A′ § B′ § C ′

Figure 2.23. Venn diagram for F3 .
NORMAL FORMS AND SIMPLIFICATION OF CIRCUITS 33


By looking at the shaded region of a Venn diagram corresponding to a boolean
expression, it is often possible to see how to simplify the expression. Furthermore,
the disjunctive normal form provides a method of proving hypotheses derived
from these Venn diagrams.
However, Venn diagrams become too complicated and impractical for func-
tions of more than four variables. For other general methods of simplifying
circuits, consult a book on boolean algebras such as Mendelson [21].

Example 2.26. Find the disjunctive normal form and simplify the circuit in
Figure 2.24.

Solution. This circuit is represented by the boolean expression

f = A ∨ ((B ∨ C) § (A ∨ B ∨ C)).

The boolean function f : {0, 1}3 ’ {0, 1} that this expression de¬nes is given in
Table 2.15. It follows that the disjunctive normal form is

(A § B § C) ∨ (A § B § C) ∨ (A § B § C ) ∨ (A § B § C)
∨ (A § B § C ) ∨ (A § B § C),

which is certainly not simpler than the original. However, by looking at the Venn
diagram in Figure 2.25, we see that this expression is equivalent to just A ∨ C;
thus a simpler equivalent circuit is given in Figure 2.25.

A

A
B′
B

C
C
Figure 2.24. Series-parallel circuit.


TABLE 2.15. Switching
Function
A B C f
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
34 2 BOOLEAN ALGEBRAS


A B
A


C
C
Figure 2.25. Venn diagram and simpli¬ed circuit.


In building a computer, one of the most important pieces of equipment needed
is a circuit that will add two numbers in binary form. Consider the problem of
adding the numbers 15 and 5. Their binary forms are 1111 and 101, respectively.
The binary and decimal additions are shown below. In general, if we add the
number . . . a2 a1 a0 to . . . b2 b1 b0 , we have to carry the digits . . . c2 c1 to obtain the
sum . . . s2 s1 s0 .

1111 15 . . . a2 a1 a0
101 5 . . . b2 b1 b0
1111 ← carry digits ’ 1 . . . c2 c1
10100 20 . . . s2 s1 s0
binary addition decimal addition

Let us ¬rst design a circuit to add a0 and b0 to obtain s0 and the carry digit
c1 . This is called a half adder. The digits s0 and c1 are functions of a0 and b0
which are given by Table 2.16. For example, in binary arithmetic, 1 + 1 = 10,
which means that if a0 = 1 and b0 = 1, s0 = 0, and we have to carry c1 = 1.
We see from Table 2.16 that c1 = a0 § b0 and s0 = (a0 § b0 ) ∨ (a0 § b0 ).
These circuits are shown in Figure 2.26.

TABLE 2.16. Switching
Functions for the Half
Adder
a0 b0 c1 s0
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0



a′ b0
0
s0
a0 b′
0


a0 b0 c1

Figure 2.26. Circuits for the half adder.
NORMAL FORMS AND SIMPLIFICATION OF CIRCUITS 35

TABLE 2.17. Switching Functions
for a Full Adder
ai bi ci ci+1 si
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1



ai bi

ci + 1 shaded

ci

ai bi

si shaded

ci

Figure 2.27. Venn diagrams for a full adder.



b′ ci
i
a′
i
c′
bi i
si
b′ c′
i i
ai
bi ci

bi
ai
ci ci +1
bi ci

Figure 2.28. Circuits for a full adder.



A circuit that adds ai , bi , and the carry digit, ci , to obtain si , with ci+1 to
carry, is called a full adder. The functions ci+1 and si are de¬ned by Table 2.17,
and their Venn diagrams are given in Figure 2.27. Notice that si = ai bi ci .
Suitable expressions for a full adder are as follows. The corresponding circuits
are shown in Figure 2.28.
36 2 BOOLEAN ALGEBRAS


si = (ai § bi § ci ) ∨ (ai § bi § ci ) ∨ (ai § bi § ci ) ∨ (ai § bi § ci )
= (ai § ((bi § ci ) ∨ (bi § ci ))) ∨ (ai § ((bi § ci ) ∨ (bi § ci ))).
ci+1 = (ai § bi ) ∨ (ai § ci ) ∨ (bi § ci )
= (ai § (bi ∨ ci )) ∨ (bi § ci ).

Using one half adder and (n ’ 1) full adders, we can design a circuit that will
add two numbers that in binary form have n or fewer digits (that is, numbers
less than 2n ).


TRANSISTOR GATES

The switches we have been dealing with so far have been simple two-state
devices. Transistor technology, however, allows us to construct basic switches
with multiple inputs. These are called transistor gates. Transistor gates can be
used to implement the logical operations AND, OR, NOT, and modulo 2 addi-
tion (that is, exclusive OR). Gates for the composite operations NOT-AND and
NOT-OR are also easily built from transistors; these are called NAND and NOR
gates, respectively. Figure 2.29 illustrates the symbols and outputs for these gates
when there are two inputs. However, any number of inputs is possible. Note that
the inversion operation is indicated by a small circle.
Transistor gates can be combined in series and in parallel to form more com-
plex circuits. Any circuit with n inputs and one output de¬nes an n-variable
switching function. The set of all such n-variable functions again forms the
boolean algebra (Fn , §, ∨, ).
It follows from the disjunctive normal form that any boolean function can
be constructed from AND, OR, and NOT gates. What is not so obvious is that
any boolean function can be constructed solely from NOR gates (or solely from
NAND gates). This is of interest because with certain types of transistors, it is
easier to build NOR gates (and NAND gates) than it is to build the basic opera-
tions. Figure 2.30 illustrates how two-input NOR gates can be used to construct
two-input AND and OR gates as well as a NOT gate.


a a
(a § b)′ = a′ ∨ b′
a§b
AND NAND
b b

a a
(a ∨ b)′ = a′ § b′
a∨b
OR NOR
b b

Exclusive OR(a, b) =
a
(a § b′) ∨ (a′ § b)
a a′
NOT b

Figure 2.29. Transistor gates.
TRANSISTOR GATES 37


a
a∨b
NOR NOR
a a′
NOR b
a′ § b′

a′
a NOR
(a′ ∨ b′)′ = a § b
NOR
b′
b NOR

Figure 2.30. Basic operations constructed from NOR gates.



ci
NOR
NOR
ai si
NOR NOR
NOR NOR
bi
NOR NOR


cj +1
NOR

Figure 2.31. Full adder using NOR gates.



Example 2.27. Verify that the circuit in Figure 2.31 is indeed a full adder.

Solution. We analyze this circuit by breaking it up into component parts as
illustrated in Figure 2.32. Consider the subcircuit consisting of four NOR gates
in Figure 2.32 with inputs a and b and outputs l and m. If u and v are the
intermediate functions as shown in the ¬gure, then

m = NOR(a, b) = a § b
u = NOR(a, a § b ) = a § (a § b ) = a § (a ∨ b)
= (a § a) ∨ (a § b) = 0 ∨ (a § b) = a § b,



TRANSISTOR GATES

u ci
NOR si
a l
NOR NOR
b ai
NOR v li
m
NOR
bi ci +1
mi

Figure 2.32. Component parts of the full adder.
38 2 BOOLEAN ALGEBRAS


and v = a § b , similarly. Therefore,

l = NOR(u, v) = (a § b) § (a § b ) = (a ∨ b ) § (a ∨ b)
= (a § a ) ∨ (a § b) ∨ (b § a ) ∨ (b § b) = 0 ∨ (a § b) ∨ (b § a ) ∨ 0
= (a § b) ∨ (a § b ) = a b .

The entire circuit can now be constructed from two of these identical sub-
circuits together with one NOR gate, as shown in Figure 2.32. The switching
functions for the subcircuit and the full adder are calculated in Table 2.18.
We have ci+1 = NOR(mi , NOR(ci , li )), while si = ci li . We see from
Table 2.18 that the circuits do perform the addition of ai , bi , and ci correctly.


TABLE 2.18. Switching Functions for the NOR
Circuit
ai bi ci li mi NOR(ci , li ) ci+1 si
ab l m
0 0 1 1 0 0 0 1 1 0 0 0
0 1 0 0 0 0 1 1 1 0 0 1
1 0 0 0 0 1 0 0 0 1 0 1
1 1 1 0 0 1 1 0 0 0 1 0
1 0 0 0 0 1 0 1
1 0 1 0 0 0 1 0
1 1 0 1 0 0 1 0
1 1 1 1 0 0 1 1




Figure 2.33. Photomicrograph of the IBM POWER4 chip containing 174 million transistors. (Cour-
tesy of the IBM Journal of Research and Development.)
REPRESENTATION THEOREM 39


Instead of using many individual transistors, circuits are now made on a single
semiconductor “chip,” such as the one in Figure 2.33. This chip may contain
millions of gates and several layers of semiconductor. Simpli¬cation of a circuit
may not mean the reduction of the circuit to the smallest number of gates. It
could mean simpli¬cation to standard modules, or the reduction of the numbers
of layers in the chip. In the design of high-speed computers, it is important to
reduce the time a circuit will take to perform a given set of operations.


REPRESENTATION THEOREM

A boolean algebra is a generalization of the notion of the algebra of sets. How-
ever, we now show that every ¬nite boolean algebra is in fact essentially the
same as the algebra of subsets of some ¬nite set. To be more precise about
what we mean by algebras being essentially the same, we introduce the notion
of morphism and isomorphism of boolean algebras. A morphism between two
boolean algebras is a function between their elements that preserves the two
binary operations and the unary operation.
More precisely, if (K, §, ∨, ) and (L, ©, ∪, ’ ) are two boolean algebras,
the function f : K ’ L is called a boolean algebra morphism if the following
conditions hold for all A, B ∈ K:

(i) f (A § B) = f (A) © f (B).
(ii) f (A ∨ B) = f (A) ∪ f (B).
(iii) f (A ) = f (A).

A boolean algebra isomorphism is a bijective boolean algebra morphism.
Isomorphic boolean algebras have identical properties. For example, their poset
diagrams are the same, except for the labeling of the elements. Furthermore, the
atoms of one algebra must correspond to the atoms in the isomorphic algebra.
If we wish to ¬nd an isomorphism between any boolean algebra, K, and an
algebra of sets, the atoms of K must correspond to the singleton elements of the
algebra of sets. This suggests that we try to de¬ne an isomorphism from K to
the algebra P (A) of subsets of the set A of atoms of K. The following theorem
shows that if K is ¬nite, we can set up such an isomorphism.

Theorem 2.28. Representation Theorem for Finite Boolean Algebras. Let A
be the set of atoms of the ¬nite boolean algebra (K, §, ∨, ). Then there is a
boolean algebra isomorphism between (K, §, ∨, ) and the algebra of subsets
(P (A), ©, ∪, ’ ).

Proof. We already have a natural correspondence between the atoms of K
and the atoms of P (A). We use the disjunctive normal form (Theorem 2.23) to
extend this correspondence to all the elements of K.
40 2 BOOLEAN ALGEBRAS


By the disjunctive normal form, any element of K can be written as a join of
atoms of K, say B± ∨ · · · ∨ Bω . De¬ne the function f : K ’ P (A) by

f (B± ∨ · · · ∨ Bω ) = {B± } ∪ · · · ∪ {Bω }.

The uniqueness of the normal form implies that each element of K has a unique
image in P (A) and that f is a bijection.
We still have to show that f is a morphism of boolean algebras. If X and
Y are two elements of K, the atoms in the normal forms of X ∨ Y and X § Y
are, respectively, the atoms in the forms of X or Y and the atoms common to
the forms of X and Y . Therefore, f (X ∨ Y ) = f (X) ∪ f (Y ), and f (X § Y ) =
f (X) © f (Y ). An atom B is in the normal form for X if and only if B X ,
which, by Proposition 2.18(iv), happens if and only if B § X = 0. Therefore, the
atoms in X are all the atoms that are not in X and f (X ) = f (X). This proves
that f is a boolean algebra isomorphism.

COROLLARY 2.29. If (K, §, ∨, ) is a ¬nite boolean algebra, then K has 2n
elements, where n is the number of atoms in K.

Proof. This follows from Theorem 2.5.

Consider the representation theorem (Theorem 2.28) applied to the boolean
algebra D110 , which consists of the divisors of 110. The atoms of this algebra
are the prime divisors 2, 5, and 11. Theorem 2.28 de¬nes a boolean algebra
isomorphism to the algebra of subsets of {2, 5, 11}. This isomorphism, f , maps
a number onto the subset consisting of its prime divisors; for example, f (11) =
{11} and f (10) = {2, 5}.

Example 2.30. Do the divisors of 12 form a boolean algebra under gcd and lcm?

Solution. The set of divisors of 12 is {1, 2, 3, 4, 6, 12}. Since the number of
elements is not a power of 2, it cannot form a boolean algebra.

Example 2.31. Do the divisors of 24 form a boolean algebra under gcd and lcm?

Solution. There are 8 = 23 divisors of 24, namely 1, 2, 3, 4, 6, 8, 12, and
24. However, the poset diagram in Figure 2.34 shows that 2 and 3 are the only
atoms. Hence, by Corollary 2.29, it cannot be a boolean algebra because it does
not have 22 = 4 elements.

An in¬nite boolean algebra is not necessarily isomorphic to the algebra of all
subsets of a set, but is isomorphic to the algebra of some subsets of a set. This
result is known as Stone™s representation theorem, and a proof can be found in
Mendelson [21, Sec. 5.7].
EXERCISES 41


24

12
8

6
4

3
2

1

Figure 2.34. Poset diagram of the divisors of 24.



EXERCISES

If A, B, and C are subsets of a set X, under what conditions do the equalities in
Exercises 2.1 to 2.6 hold?
A ∪ B = A B (A © B).
2.1.
A © (B ∪ C) = (A © B) ∪ C.
2.2.
A ’ (B ∪ C) = (A ’ B) ∪ (A ’ C).
2.3.
A (B © C) = (A B) © (A C).
2.4.
A (B ∪ C) = (A B) ∪ (A C).
2.5.
A ∪ (B © A) = A.
2.6.
2.7. Prove the remaining parts of Proposition 2.1.
2.8. Prove the remaining parts of Proposition 2.3.
2.9. Prove Theorem 2.5 by induction on n. That is, if X is a ¬nite set with n
elements, prove that P (X) contains 2n elements.
2.10. Prove or give a counterexample to the following statements.
(a) P (X) © P (Y ) = P (X © Y ).
(b) P (X) ∪ P (Y ) = P (X ∪ Y ).
2.11. (Cantor™s theorem) Prove that there is no surjective (onto) function from
X to P (X) for any ¬nite or in¬nite set X. This shows that P (X) always
contains more elements than X.
[Hint: If f : X ’ P (X), consider {x ∈ X|x ∈ f (x)}.]
/
Write down the table for (P (X), ’), under the difference operation, when
2.12.
X = {a, b}.
If A, B, C, and D are ¬nite sets, ¬nd an expression for |A ∪ B ∪ C ∪ D|
2.13.
in terms of the number of elements in their intersections.
2.14. Of the Chelsea pensioners who returned from a war, at least 70% had lost
an eye, 75% an ear, 80% an arm, and 85% a leg. What percentage, at least
must have lost all four? (From Lewis Carroll, A Tangled Tale.)
2.15. One hundred students were questioned about their study habits. Seventy
said they sometimes studied during the day, 55 said they sometimes studied
during the night, and 45 said they sometimes studied during the weekend.
42 2 BOOLEAN ALGEBRAS


Also, 36 studied during the day and night, 24 during the day and at week-
ends, 17 during the night and at weekends, and 3 during the day, night,
and weekends. How many did not study at all?
2.16. Prove that the associative laws in de¬ned in the section “Boolean Algebras”
follow from the other axioms of a boolean algebra.
2.17. If the zero element is the same as the unit element in a boolean algebra,
prove that the algebra has only one element. Is this algebra isomorphic to
the algebra of subsets of some set?
2.18. Draw the poset diagram for F1 , the boolean algebra of switching functions
of one variable.
If A, B, and C are elements of a boolean algebra (K, §, ∨, ) and is the related
partial order, prove the assertions in Exercises 2.19 to 2.24 from the axioms and
Propositions 2.13, 2.17, and 2.18.
0 = 1.
2.19.
A § (A ∨ B) = A § B.
2.20.
(A § B) ∨ (B § C) ∨ (C § A) = (A ∨ B) § (B ∨ C) § (C ∨ A).
2.21.
A B § C implies that A B and A C.
2.22.
(A § B ) ∨ C = (B § C) ∨ (B § (A ∨ C)).
2.23.
2.24. A B if and only if B A.
2.25. Write down the truth tables for the following propositions. Which of these
propositions are equivalent?
(a) A ’ B. (b) B ’ A .
(c) (A § B) ” B. (d) (A ∨ B) ” A.
2.26. Is the proposition [(A ’ B) § (B ” C) ] equivalent to [B ∨ (A § C)] or
[(C ’ B) ∨ (B ’ (A § C))]?
2.27. Which of the following are tautologies, and which are contradictions?
(a) (A § B) ” (A ’ B ). (b) A ’ (B ’ A).
(c) (A § B ) ” (A ’ B) . (d) (A ’ B) ’
((B ’ C) ’ (A ’ C)).
2.28. Harry broke the window if and only if he ran away and John was lying.
John said that either Harry broke the window or Harry did not run away.
If Harry ran away, then he did not break the window. What conclusions
can you come to?
Draw circuits to realize the expressions in Exercises 2.29 and 2.30.
2.29. (A § (B ∨ C ∨ D)) ∨ B .
2.30. (A § B § C ) ∨ (A § B § C) ∨ (A § B § C).
2.31. Simplify the following expression and then draw a circuit for it.

((A § B) ∨ C ) § (B ∨ (C § A )) ∨ (A § B § C ).
EXERCISES 43


Give a boolean expression for each of the circuits in Exercises 2.32 to 2.36, ¬nd
their disjunctive normal forms, and then try to simplify the circuits.
2.32. 2.33.
A
A
A
A′ A′
B
2.34.
A B B′ C


A′ C′
C A′
2.35.
A A′ B′

B B A′
2.36.
A B A′
C B′
B C
C′ A′
2.37. By looking at all the possible paths through the bridge circuit in Figure 2.35,
show that it corresponds to the boolean expression

(A § D) ∨ (B § E) ∨ (A § C § E) ∨ (B § C § D).


A D
C
B E

Figure 2.35


2.38. Find a series-parallel circuit that is equivalent to the bridge circuit in
Figure 2.36 and simplify your circuit.


A B
C
B A′
C

Figure 2.36


2.39. A hall light is controlled by two switches, one upstairs and one downstairs.
Design a circuit so that the light can be switched on or off from the upstairs
or the downstairs.
44 2 BOOLEAN ALGEBRAS

<<

. 2
( 13)



>>