<< стр. 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
в€Ё в€Є Parallel Or lcm
в€’ a = n/a
Opposite Not
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  or Lidl and Pilz .
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 .

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

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
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
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

ai bi

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.
2.2.
A в€’ (B в€Є C) = (A в€’ B) в€Є (A в€’ C).
2.3.
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)СОДЕРЖАНИЕ >>