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