rl#
ií i
iíit
coNTENTs
35.1 Notation 789
SS.Z Equality, union, and intersection 790
35.3 Venn diagrams 792
Problems 799
e are often interested in grouping together objects that have common characteristics
or features. 7e might be interested in the integers I,2,3,4,, or in all the
integers. Such a group is called a set. The set of all points in a plane would consist
of Pairs of numbers of the form (x, y), where x and y aíe coordinates which can
take any real values. These examples all involve numbers, but the elements of sets
can be other objects such as functions, or matrices, or Fourier series, or Laplace
transforms, etc.
A set is a collection of objects or elements. The elements in the set can be defined
bY a rule or in any descriptive manner. Sets are usually denoted by capital letters
such as S, Á, B., X, etc., and their elements by lowercase letters such as s, a, b, x,
etc. The elements in a set are listed between braces { ... }. If the set Á consists of
just two numbers 0 and 1, then we write
A= {0,1}, or A_ {1,0}, (35.1)
tbe order being a matter of indifference. 7e say that 0 and 1 are the elements or
members of the set A, or belong to A. 7e write
0eÁ, IeA,
read as '0 belongs to the set Á', etc. The number 2 does not belon gto A, and we
write
zeA,
that is '2 does not belong to the set Á'.
The set defined by (35.1) is the binary set, which could represent the on and" off
states of a system. This could be the state of a light switch, for example.
Sets iií
liii 35
Sets can be either finite, having a finite number of elements, or infinite, in which
case the set contains an infinite number of elements. Thus the set given by (35.1)
defines a finite set Á, while
B = {1, 2,3, ... } ,
the list of all positive integers, defines an infinite set.
Some of the more common sets have their own special symbols:
llqwhereq*Oand
/eÁ D\
Often the elements are defined by a rule rather than by a list or formula.
'
7e
write the set as
S - {x Ix satisfies specified rules},
which can be translated as 'S is the set of values of x which satisfy the stated rules'.
The rules occur after the vertical |. Thus
S-{xIxeN*andZ<r <8}
is an alternative way of writing S = {2, 3,4, 5,6,7 ,8}. As another example,
S-{xIxeRandO<x<1}
is the closed interval |0, 1], that is, all real numbers between 0 and 1 including 0
and 1.
a
r(
s(
í(
F
d
s(
\\
;
T
1
a1
c(
T
aí
A
u1
A,
th
E,
T
is
SeIf-test 35.1
List in full the elements in the following sets:
(a) S, = {r|xe N* and-2š x { B},
(b) Sr = {plq lp e N*,4 N*, 1,<p < 3 and 2< q < 4}.
lity, union, and intersection
Two sets A and B are said to be equal if they contain exactly the same elements. If
this is the case, we write
A: B.
tir
T-;I
U)
FlJJ
a
to
()
p are integers)
For example,
A= {1,2,3}, C= {3, 1,2,I}
are all equal, that is A = B - C. The order of the elements is immaterial, and
repeated elements are discounted.
In a given context, the set of all elements of interest is known as the universal
set, usually denoted by U. The definition of U depends on the context. For example,
for the set Á above, the universal set might be N (the set of all positive integers), or
R* (the set of all positive numbers), or some other set which includes {1,2,, 3},
depending on the particular application.
'
í'enow define how sets can be combined to create new sets. The union of two
sets Á and B is the set of all elements that belong to A, or to B, or to botb.It ís
written as
Aw B - {xlx e Aoíx , B or both},
and read as'Á union B'.
Example 35.1 Find the union of
A_ {x|xeRandO<tr<2} and B- {x|xeRand1 <rc<3}.
The elements in the union have to belong to one or other of the intervals 0 { x { 2, or
1 šx š3, or to both. The condition is satisfied by all numbers in the interval0 šx { J,
and by no others. Hence
AwB= {xlRandO<x<3}.
The intersection of two sets A and B is the set Á n B that contains all elements
common to both A and B. It is written and defined by
AaB- {xlxe Aandx e B}.
Exarnple 35.2 Find tbe intersection of the sets A and B in Example 35.1.
The elements in the intersection have to belong simultaneously to both intervals, that
is to the overlappingpaít of the intervals |0,2) and [1,3], which is [1,2]. Thus
AaB={x|xeRandlšx<2}.
In the definitions of Á u B and A r-l B above, we can see that the logical operation'or'is
associated with union, while'and'is associated with intersection.
If A and B have no elements in common, then Á and B are said to be disjoint.
The set with no elements is called the empty set and denoted by a. Thus, if Á
andBaredisjoint,then AaB-a.Thus if A= {1,2,3} and B= {4,5,6} then
AaB-a.
The complement of a set Á is the set of all those elements which belong to the
universal set U but do not belong to Á. 7e denote this set by Á 1the notations
A'and A' are also frequently used): it will depend on the definition oít].Hence,
the complement of Á is, assuming that x e IJ,
B = {3, Z, t},
G)
íJ,
N)
m
o
C
]-
5
c
z
o
?
zo
ž_{
m
,@
m
o{
o
z
lD a
ttJ
O
[o
C9
Á-{x|xeA}.
7e say that A is a subset of B, expressed as A c B, if every element of Á also
belongs to the set B. It follows that A e U ííB e I].If there are elements of B
which afe not in A, then Á is called a proper subset of B and written A c B. The
statement A e Bincludes the possibility that A = B,while A c. Bdoes not. If A
=B
and B c Á, then all elements in Á are contained in B, and vice versa; in other words,
A= B.
The sets of integers Z and rational numbers Q are proper subsets of the real
numbers R, that is
ZcR, and QcR.
7e can summarize the results as follows.
Seť operatiOnS
(a) Union: AwB= {xl xeAorrc Borboth}.
(b) Intersection: A n B - {x|x e A and x B}.
(c) Complement, Á= {xlxéA|.
(d) Empty seť a, the set with no elements.
(e) Subset: A e B means that A is a subset of B.
(f) Proper subset: AcBmeans thatÁ c B but A*B. (35.3)
Self-test 35.2
Find the union and intersection oíA - {x1* e R and -]. < x 4 23,
B-{x|xeN*andl<x<4}.
diagrams
Useful graphical views and interpretations of sets and operations on them can
be provided by Venn diagrams. 'tJíe represent sets by regions in the plane, with
the interpretation that the region stands for those elements belonging to the given
set. The diagrams are symbolic: the set A = {1, 2} , for example, could be represented
by the circle as shown in Fig. 35.1. Usually, sets are represented by the
interiors of circles, but any closed curves can be used. In a given context, all the
sets are subsets oía certain universal set U, whose nature will differ according to
the context.
If the universal set is represented by a íectangle, then a subset A oÍ U is represented
by the interior of a circle within the rectangle shown in Fig. 35.2. This is a
Venn diagram for U and Á. Remember that A could represent an infinite number
of elements, or one element, or be the empty set a. Two regions in U may have
elements in common. For example, A = {1,2, 3} and B = {3,4, 5} have the common
element 3. In a Venn diagram this is represented by intersecting regions Á and B as
in Fig. 35.3a.
th
de
di,
(
(
(
l.-
G)
íJ'
(r)
m
zz
o
F
o
f,
@
Fig.35.1 Fig. 35,2 Venn diagram for the universal
set U and a set Á.
Fig. 35.3 (a) Union A w B, (b) Intersection Á n B. (c) Complement Á. 1d; lroper subset A c B.
The union, intersection, complement, and proper subset can be represented by
the Venn diagrams shown in Fig. 35.3. The shaded regions indicate the elements
defined by the operations.
From the definitions of union, intersection, and complement, or from Venn
diagrams, the following laws of the algebra of sets can be deduced:
(b)(a)
U
U U
U
(d)
Algebra of sets
Aw A_ A, An A= A.
commutative laws:
AwB=Bu)A, AaB_BaA.
Associative laws (see Fig. 35.4):
(ÁuB) \-,'C=Áu(BuC),
(AnB) nC=Án(BnC).
(a)
(b)
(c)
,
(c)
U)
ul
CD
to
()
(a) (b)
-tsx
sh,
(a)
Ve
Fig.35.4 (") (AuB)u CorAu (BuC).(b) (ÁnB)nCorAn(BnC).
iliiiiffi].
Sets also satisfy the following identity and complementary laws:
For example, Á consists of all elements that do not belon gto A, and none that do;
so there are no elements common to Á and Á. Therefore Á n A = a.
The diffefence of the sets Á and B, written as Á\B, consists of the set of those
elements that belong to Á but do not belong to B. Thus
Á\B= {xIxeÁand xeB} or E^B
^A.
(The notation A - B is also used for Á\B.) Figure 35.5b shows a Venn diagram
for Á\B.
Er
;
sha
(a)
(d)
Tht
(A,
(35.4)
(35.5)
Fig, 35.5 Venn diagram for the difference
A\B (shaded).
Fig.35.6
ExamPle 35.3 Using Fig. 35.6 as the Venn diagram of tuo sets A and B, mark by
shading the follouing sets:
(a) AuB, (b) AaB, (.) Á n B, (d) ÁvB, (e) Á u B, (f) Á n B.
Venn diagrams of the sets are shown in Fig. 35.7.
T ,Z\. x
^
B
.il \./ Á
(c)
r,^.x
A B
b* \./ /l,
(e,l
Fig.35.7
(..)
crl
i^'
m
zz
o
F
o
,
U)
Examples 35.3c, e and 35.3d confirm de Morgan's laws, which are
De Morgan's laws
AwB=A^B, AaB_ÁwB. (35.6)
Example 35.4 Using Fig. 35.B as tbe Venn diagram of tbree sets A, B, and C,
shade the follouing sets:
(a) (ÁnB) uC, (b) (ÁnB) nC, (c) (ÁnB) n(ÁnC),
(d) (ÁuB) u(ÁnC).
The required sets are shown in Fig. 35.9. (Figs. 35.9b, c confirm that
(AnB) . C= (Á nB) n (An C).)
'
B
(a) (b)
(d)
(f)
U)
[!
o
lo
ť)
Examp|e 35.4 continued
(") (ÁnB) uC (b)
:
(ÁnB) nC:
:l] :;],. ]l:_]]ij
]::]|,:i]:]]]:',:i ::,: ]]
Fig.35.9
(c) (A n B)n (Á n C) (d) (A u B)u (A n C)
Example 35.5 Sbow tbat (A n B) u (A n B) - A.
By the distributive law (35.4),
(AnB) u(AnB)=An(BuB)
= A a(J (by the complementary law)
- A (by the identity law).
This can be confirmed graphically by drawing a Venn diagram.
_E
Fig.35.8
I
I
Example 35.6 Sbow that (A u B) u (Á\B) - Av B.
From Fig. 35.5, we can observe that A\B = A
^
B. Hence
(ÁuB) u(Á\B) =(ÁuB) u(AnB)
= A w (B w (A n B)) (associative law)
= Aw ((B r--,,Á) n (B u B)) (disrributive law)
=Au((BuÁ) nU)
= Aw (B u A) (identity law)
= (B u A) w A (commutative law)
=B(J (AwA)=BwA
=AwB.
Alternatively, and more intuitively, we may notice that, since Á\B is a subset of Á, it is
therefore also a subset of A r.,l B, and so adds nothing to Á u B when united with it.
Example 35.7 ln a manufactwringprocess, a product passes tbrougb three
Production stages and is giuen a quality cbeck at all three stages, uhich it either
Passes or fails. Let P, rePresent tbe set of products passing tbe quality cbeck at
stage i. Drau a Venn diagram of the process. lnterpret the quality failures of
the Products in the sets giuen by P r, P2\ (P1 U Pr), and (P, U Pr) a P r. Wbat set
rePresents the completely satisfactory Products?
A Production run of 1000 occurs) of whicb 8 fail all stages,20 pass only stage
Pb 31 only stage Pr, and 17 only stage Pr;814 pass stage.s P, and P2,9O2 stages P.,
and Pr, and 800 stages P, and Pr. Determine tbe final number uhich pass all
quality checks.
P, represents all products which fail the P, quality check.
Pr\ (& u Pr) represents those products which pass only Prstage.
(PrW Pr) n P, rePresents those products which are satisfactory at stages P, and P, ot Pr.
The set P, r> Pró P, represents those products which are satisfaďory at all stages.
The numbers associated with each subset of the universal set U are shown in Fig. 35.10.
Since 8 fail all quality checks, then the number of elements in Q u (Pzu Pr) is 992.In
the figure, A represents the number of products which pass all th. q,r"lity checks. Hence
800 - k,, Íorexample, represents those products which are satisfactory in stages P, and
Pr,but fail in Pr. Thus Prw Pru P, contains
cD
O|
t^'
m
zz
o
>
o
IJ
@
Fig. 35.10
,
U,
FlJJ
U)
Example 35.7 continued
992=Z0 + 3I + 17 + (814 - k) + (902- Ř) + (800 - k) + k
products. Flence 992 = 2584 - 2k, and so
k-=796.
Of the 1000 products manufactured, 796 passed all the quality checks.
In the previous Example, we are really interested in the numbers of elements
in each of the sets. For example, the number of elements in U is 1000 and the
number of elements in Pr\(P, u &), those products which pass only stage 2, is 31,.
' 7e write
n(U) = 1000, n[Pr\(P, u &)] =31,.
The number of elements in the set S is n(S): this number is known as the cardinality
of S. Many sets can have infinite cardinality. For example, n(Q), where
Q is the set of rational numbers, is an infinite number. 7e write n(Q) - "o. The
empty seta has no elements: hence n(a) - g.
The following results apply to finite sets.Ií two finite sets Á and B are disjoint,
then they have no elements in common. It follows that
n(AuB) =n(Á) +n(B).
This result applies to any number of disjoint sets. It is clear that they must be
disjoint, since otherwise elements would be counted more than once.
This last result is also a useful method of counting elements when combined
with a Venn diagram. Consider just two sets Á and B as shown in Fig. 35.11. The
sets representing each of the subsets in the Venn diagram Á\B, A n B,and B\Á are
shown in Fig.35.11. Since these sets are disjoint, then we can obtain a formula for
the number of elements in the union of Á and B, namely
n(ÁuB) =n(Á\B) +n(ÁnB) +n(B\Á).
For sets A and B separately,
n(Á) _ n(A\B) + n(Á n B), n(B) - n(B\Á) + n(Á n B).
Elimination of n(Á\B) and n(B\A) between (35.7) and (35.8) leads to the alternative
result
n(ÁuB) =n(Á) +n(B) _n(AnB).
(35.7)
(35,8)
A B
A\B ÁnBI B\A
Fig. 35.11 Counting elements in
the union of two sets.
-T
^J| ,,"
l
For three finite sets A, B, and C the corresponding result is
n(ÁuBuC) :n(Á) +n(B) +n(C) +n(ÁnBnC) _n(BnC)
-n(CnÁ) -n(ÁnB).
This result can be constructed from the Venn diagram.
Further discussion of sets and their algebra can be found in Garnier and
Taylor (1991).
Self-test 35.3
In Fig. 35.8, shade
(a) Án(BnC); (b) Av B; (c) (ÁuC) n(BuC).
T,
7
o
t!
m
a
(") A= {x|x e R, and -24 x < 1},
P= {xlx e R, and -1 < r < 2};
(b) Á = {x|xe N*and-5 šx < 2},
3={x|xeR,and-5šx<2};
(.) Á = {n|n=llm andm N*},
B= {n|n=llmL and m
=
N*};
(d) A = {x|xe R and * -3x +2=0),
B= {x|x e R and 2x2+ x -3 =0};
(e) Á = {x|xe R and l"l < 2},
B= {x|x e R and Ix- 1l < 1}.
35.5 (Section 35.3). Construct a set formula for
the shaded sets of Fig. 35.12
(a)
(b)
Fig. 35,12
FrohIems
35.1 (Section 35.1). List the elements in the
following sets:
(a) S= {x|x eNnand3 { x < 10};
(b) S= {x|xeN*and-24x <4};
(c) S= {x|xeZand-Z4x <4};
(d) S = {x|x e N* or N-, and -2 4 x < 4};
(e) 5= {1lx|x e N*and3 šx< 8};
(f) 5= {x2|x e N* and l"l < 3};
(g) S={x+iyIxeN*,} N*, 1šxš4,
2<y<5}.
35.2 (Section 35.3). Show on Venn diagrams the
following sets:
(a) AuB; (b) ÁnB;
(c) Án(BuC); (d) (ÁnB) u(BnC);
(e) ÁnB;
(f) (A\B) n C;
(g) Á\ (B n C);
(h) (ÁBIúG\O.
35,3 (Section 35.2). Determine the union Av B
of each of the following pairs of sets Á and B:
(a) A={x|xe Rand-1 {x<2},
3={x|xeRand-1 šx<4};
(b) Á = {x|xe R and-1 šx < 0},
B={x|xeRandO<r<1};
(c) Á = {I,2,3, 4\ , B = {-4, -3, -2, -1,} ;
(d) Á = {yly=cosrc, x e R, and 0 <, < in},
B= {yly=sin)úlx R, and-|n<
"
< in}.
35.4 (Section 35.2). Determine the intersections
A a B of the following sets:
tp (.) S , t * The cr,rte sia* grr*ti t-lct of two sets Á and B is
the set of all ,*rciet,,;el pllil,s {(a, b)}, where a e A and
b eB.It is written as
Á x B = {(a, b)|a eÁ and b e B}.
If A= B, then we write Ax A=,Az.Let n= {I,2}
and B = {1,2,3}; write down all the elements in
the sets A x B, B x A, Az , and Bz.
35.X"! The cartesian product extends to the
products of three or mofe sets. Thus
Ax Bx C= {(a, b, c) | a eA and b e B and c e C}.
Let A = {1,2,3}, B = {0, 1}, and C = {1,2}.
\ff/rite
down all the elements in
AxBx C, Az x C, (Au B) x C, (Á n B) x C.
5.X2 At the end of a production process,500
electrical components pass through three quality
checks P, Q, and R. It is found that 38 components
fail check P,29 ía1lr Q, 30 fail R, 7 fallP and Q, 5
fail Q and R, 8 fail R and P, and 3 fail all checks.
Determine how many components:
(a) pass all checks,
(b) fail just one check,
(c) fail just two checks.
35. 1 3 (Section 35 .4) . For three finite sets A, B, and
C, show that the number of elements in the union
of the sets is given by
n(A u B u C) = n(Á) + n(B) +n(C)
+n(ÁnBnC)-n(BnC)
-n(CnÁ)-n(ÁnB).
35.14 If Á and B are two finite sets, explain why,
for the cartesian product (defined in Problem 35.10
above),
n(ÁxB):n(A)n(B).
35.15 The menu in a restaurant contains three
courses: 4 starters (set Á),5 main courses (set B),
and 3 sweets (set C). Customers can choose either
the full menu or, alternatively, a main course and a
sweet. In terms of cartesian products what is the set
of all possible meals (the answer is really a set of
pairs and triples). For how many different orders
can customers ask?
35.16 Given A= 1,2,3},B = {3,4}, and C = {2,3,
4, 5}, findthe elements in the sets B U C,B nC, and
the cartesian products Á x B and Á x C. Verify that
Ax (BtJ C) = (A x B) u (Á x C),
Áx(BnC)=(ÁxB) n(ÁxC).
(This example suggests general results which are
true for all sets.)
a
llJ
Cl)
to
ď)
(d)
Fig. 35.12 (continwed)
35.6 The set S consists of products, each of which
is given n passlíail tests, numbered 1 to z. The set
S,, consists of those products that pass test r. \il/hat
is the set of products that
(a) fails all tests, (b) fails only test 1,
(c) fails some tests?
35.7 At Keele University, all first-year students
must take three subjects of which at least one must
be a science subject, and at least one must be a
humanities or social science subject. Let Á be the
set of all first-year students in a given year, A,
the set of students who take exactly one science
subject, B, the set of students who take just one
humanities subject, and Brthe set of those who
take two social science subjects. Draw a Venn
diagram to represent the different sets of students
classified by groups of subiects. Give set formulae
for students who take
(a) just one social science subject,
(b) no humanities subject,
(c) one subject from each group.
35.8 (Section 35.3). The rules listed in (35.4)
illustrate the duality principle which states that
every statement involving sets which is true for all
sers has a dual in which u and n are interchanged,
and a and U are interchanged everywhere.
Use Venn diagrams to establish the following:
(a) (A\B) oC=(ÁnC)\B;
(b) Á n (Bu C) = (AnB) u (An C).
\ť{/hat are their dual identities?
35.9 Three sets Á, B, and C satisfy
AaB.tC=(ÁnC) u(BnC).
Explain why the duality principle of Problem 34.8
does not apply. \il/hat condition of the duality
principle is violated?
coNTENTS
36.1 Laws of Boolean algebra 801
36.2 Logic gates and truth tables 803
36.3 Logic networks 805
36.a The inverse truth-table problem 808
36.s Switching circuits aoo
Problems 812
We are now going to present some new operations between special entities. They
have analogies with ordinary addition and multiplication, and the symbols for
them will be similar; but not the same, since we need to emphasize that these are
Boolean operations. The algebra involved is named aíterGeorge Boole (1815-
64) who first developed the modern ideas of symbolic logic. Boolean algebra has
applications in logic and switching circuits.
of Boolean algebra
Consider a set B which consists of just two elements 0 and 1, that is B = {0, 1} . 7e
shall denote the sum of two elements a and b oíB by a @ b (the notations v, U,
and +, and the alternative term ioin are also used); we denote the product of the
two elements by a'l b (thenotations A, A, X, and ., or simply ab,and the alternative
term meet are also in use) and the complement of aby a (-a and -ta áíeused
in logic). These binary operations applied to the members oí B aredefined to give
the elements shown in Table 36.1,.
Table 36,1 Binary operations
Sum Product Complement
00
01,
10
1, l
0
1,
1
t
00
01,
10
11,
0
0
0
1
,ii
i.]].i:ii
Boolean algebra: logic gates
and switchr tioňs
ab A,, b
u,
z
o
tr
o
zf
ll
o
z
t
oF
=a
o
z
aLlJ
o
9
o
o
<
tr
dl
lJJ
(,
z
tu
o
o
dl
(o
()
Thus, for example
0@1-I, l(D],=1, 0*0-0, !,r!-!, 0=1, T=0.
The elements of B areknown as Boolean variables.' íe have restricted ouf set B
to one with just two elements or binary digits, because this is the main application
in circuits and computer design, but definitions can be interpreted for more
general sets. A Boolean algebra is a set with the operations @, ,'-, and - defined on
it, together with the following laws on any elements A, b, c which belong to B:
In addition, the set must contain distinct identity elements 0 and 1 for the operations
(D and ,l- respectively. For these elements we must have the identity and complement
1aws:
To summ aríze,we can say that a Boolean algebra consists of the collection
(B, @, ,r, -,0, 1),
in other words, a set B, the binary operations (D and ,,, the complement -, and the
identity elements 0 and 1.
In our case B = {0, 1_}, the binary set, which consists simply of identity elements.
7e can check that the definitions in Table 36.]. satisfy the laws in (36.I). They are
essentially the laws of set operations with sum (D and product * replacing union U
and intersection n, and with 1 replacing the universal set U and 0 the empty seta.
Just as with sets, we can deduce further laws, some of which are included
in (36.3):
r
cclrnnrutative lalvs:
a@b-b@a, 4,1 $-b"a;
Associative iirlvs:
a@ (b @c) = (a@b)@ c, a" (b* 6)-(a*b),l 6,
I }i stl,itr-l tlt r v* laivs:
a,, (b @ c) = (a" b) @ (a,r c),
a@ (b,, c) - (a@ b) " (a@ c).
ldentitv lar.r,s:
a@O=a, A,,1-A
Complement iaws:
a@a=1, a*a-0
(36.1)
(36.2)
(36.3)
Identity laws:
1,@ a _ a@ 1=I, 0,r A- a * 0-0;
Reflexivelaw:á-a.
Note that ,l takes precedence ouer (D in the absence of brackets. Thus, in the first
absorption law, a @ a,l b means a @ (a,r b); in the second absorption law, the
brackets are essential.
\J7e will prove one of the absorption laws to illustrate how proofs are approached
in Boolean algebra.
Example 36.1 Proue that a @ a,, b - a.
For all a,b eB
a@ a* fu- 6,1t@ 4* $ (identity law)
= 6 " (1 @ b) (distributive law).
Now
1@ b= (1 O b) * 1 (identity law)
= ! * (b @ 1) (associative law)
= (b @ U) - (U O t) (complement law)
=b@ b " 1, (distributive law)
=b@b (identitylaw)
- 1, (complement law).
Finally
a@a,rb-A*l:A.
gates and truth tab|es
Any expression made up from the elements of B and the operations @, *-, and - is
known as a Boolean expression. For example,
a@b, a@b, a@a,rb,
are Boolean expressions. For the binary set, the elements 1 and 0 can represent
'on' or 'off' states in digital circuits. The basic components in a computeí aíe
logic gates which can produce an output from inputs. All the outputs and inputs
can be in one of two states, usually either low voltage (0) or high voltage (1).
The fundamental Boolean operations of (D, x-, and - correspond to devices
known respectively as the oR gate, AND gate, and },ror gate. As with circuit components
such as resistance and inductance, each has its own symbol.
The on gate has two inputs and a single output represented by the symbol in
Fig. 36.1. The output is /= a @ b. The inputs a and b can each take either of the
values 0 or 1. Hence there are four possible inputs into the device as listed in
Table 36.2. The final column f can be completed using the sum rule in Table 36.I.
Then, iÍa is 'on' (1) and b is 'off' (0), the output f is 'on' (1). Table 36.2is known
as the truth table of the oR gate.
G)
9,
N)
o
o
o
o
-{
m
a
z
o
_{
T
c{J
{
tD
m
U)
(í)
z
o
tr
o
z3lL
(,
z
o
=
Cí,
o
z
allJ
o
9
o
o
<
É,
r!
lJJ
(,
z
lJJ
o
o
o
Table 36.2 Truth table for the oR 4ate
f=a@b
Fig. 36.1 The on gate.
0
0
1
1
0
1
0
1,
0
1,
1
1,
The symbol and truth table for the AND gate are shown in Fig. 36.2 and
Table 36.3. Again the device has two inputs and the single output f = r " b,the
product of a and b.
Table 36,3 Truth table for the AND gate
a b f:a*b
Fig. 36.2 The eNo gate.
0
0
1
1
0
1,
0
1,
0
0
0
1
Finally the Nor gate is shown in Fig. 36.3 with its truth table given as
Table 36.4. The Nor gate has a single input and a single output which is the complement
of its input.
Table 36.4 Truth table for the Nol gate
a f=a
Fig. 36.3 The Nor gate.
0
1
There is further jargon associated with these gates. The output a@ á is known
as the disjunctio n oía and b, while A * b is known as the conjunction of a and b,
and a is called the negation of a.
These devices can be connected in series and parallel to create new logic
devices, each of which will have its own truth table.
A series connection between a NoT gate and an AND gate is shown in Fig. 36.4a.
The output a,,, b of.the eNo gate becomes the input of the NoT gate which results
in the output A * b. This combined device is known as the NAND gate, and it has
its own symbolic representation shown in Fig. 36.4b.Its truth table is given in
Table 36.5.
1,
0
E
Table 36.5 Tnlth table for the NlNo gate
f=all
0
0
1
1
0
1
0
1
1,
1
1,
0
G)
o)
G)
o
o
o
zm
É
o
T
^@
A series connection between a NoT gate and an oR gate produces the NoR gate
as shown in Fig. 36.5a. The output /is the complement of the sum of a andb.The
NoR gate also has its own symbol contraction shown in Fig. 36.5b. It has the truth
table shown in Table 36.6.
(b)
Fig. 36.4 The NaNo gate.
;
Table 36.6 Truth table for the Non gate
a b f=oab(a)
0
0
1,
1,
0
,],
0
1,
1
0
0
0
Fig. 36,5 The Non gate.
Self-test 36.1
The output of an AND gate (Fig. 36.2) is attached to a NoT gate (Fig. 36.3).
Construct the truth table for the system.
networks
The five gates introduced
parallel combinations to
presented here.
in the previous section can be
create further logic networks.
linked in series and
Some examples are
Example 36.2 Construct the Boolean exPression for the outPut f of the deuice
shoun in Fig.36.6.
Starting from the left in Fig.36.6, the upper AND gate produces an output a ,, b andthe
lower oR gate has an output c @ d. These become the inputs into the oR gate on the
right. Hence the final output is
'
ffi\--
Lí
!.,
a
z
o
tr
o
zf
lJ.
o
=I
oF
=a
o
z
altJ
(,
9
o
o
É.
íl
l,tJ
(,
z
lJJ
o
o
d]
(o
(9
Example 36.2 continued
Fig,36.6
f=(o*b)@c@d.
Since there are four inputs, the output f canbe determined for each of the 2a :1,6
possible inputs. Hence if, for example, A = 1, b :0, c = 0, d = 1, then the output /: |.
Example 36.3 Figure 36.7 sbous a logical netuork uith three inPuts a, b, c, and
four deuices. Find a Boolean expression for tbe owtPut f. Write doun the truth
table for the system.
Note that the input á is the same in both devices P and Q. The output from the AND gate
P is a,, b, andthe output from R is a ,;l. The output from Qis b @ c. Hence the inputs
a,,, b and b @ cinto S produce an output
f:a,"l@b@c.
The truth table for this network is given in Table 36.7.Whatever the inputs, the device
is always'on'.
Table 36.7
;4 b@c a;To(b@c)
0
0
1
1
0
0
1,
1,
Fig.36.7
;
n
G
o,
D,
gl
r(
E
r
F
a
a
a
1
,],
1,
1,
1,
1,
0
0
0
0
0
0
0
0
1
L
0
1,
0
1,
0
1,
0
1,
0
0
0
0
1,
1,
1,
1
"T_.;l
|--
Example 36.4 Sbou that, using just rĎe Non gate, it is possible to build a logic
netu,lork- to model any Boolean exPression.
Given inputs a and b,we have to show that devices can be constructed using just Non
gates with outputs of a @ b, a,r b, and a.For inputs oía and b,the single NoR gate
generates an output of a @ á. Figure 36.8 shows three devices which simulate the
required outputs.
G)
9)
G)
o
o
o
zm
{
É
o
1
^@
(a) ., ---------{-\ .l e, /, ;---{-\ .;óTél o /, -.t@ t,
l )H l )o--./ ./
(b)
(.)
Fig. 36.8 The simulations are: (a) on gate; (b) eNo gate (c) NoT gate.
Example 36.5 Design a logic networkusing oR, AND, andNor gates to
reProduce tbe Boolean exPression f = A * b @ a for inpwts a and b.
From input á we obtai n b by a NoT gate. The inputs a and b are thenfed into an AND
gate to produce o,, 6. Finally a spur from the a input and the a ,, b output are fed into
an oR gate as shown inFig.36.9.
Fig.36.9
SeIf-test 36.2
An eNo gate with inputs a and b, and a NoT gate with input c aíe connected
to a NoR gate. Find a Boolean expression for the output f, and construct a
truth table for the System.
inverse truth-table problem
In this problem we attempt the inverse problem; of creating a Boolean expression
íora given truth table. For example, Table 36.B is a truth table for two inputs a
and b. 7e illustrate a method for the construction of a Boolean expression which
willgeneratethistruthtable.Pickoutcasesforwhich f =l.Forthe casea:O,b=L,
write down a,, b, and for A=lrb=0 write down A,? b, using in the products,
the complement of any zero element. Thus, for example, if a - 0 and b = 1, then
a=Ianda,,, b- ]-. Similarly a,, b -1. HencebyTable36.3
a,rb@A,rb=I
Table 36.8 Truth table for EXOR gate
0
0
I
1,
0
t
0
I
0
1
1
0
Fig- 36.10 The exclusive-on gate.
for these cases. /remains zero íor the remaining outputs. íe obtain
f=a,rb@A,,,b,
and the final output f can be checked.
This particular gate is known as the exclusive-oR gate, or ExoR gate, and has
its own symbol shown in Fig. 36.1,0. This form of f obtained by the construction
just described is known as the disiunctive normal form. By the definitions in
Table 36.1,,the construction guarantees a Boolean expression for any truth table.
Applied to the truth table for the oR gate (Table 36.2),the disjunctive form gives
f=@@b) O (a@b)@(a@b),
which is evidently a more complicated version oía @ b.
The method can be applied to more complex truth tables. Table 36.9 shows an
output for three inputs. The output ]. appears in rows Z,4,5,7,8.Inrow 2, A=0,
Table 36.9
0
0
0
0
L
1,
1
1,
0
0
1,
I
0
0
1,
1
0
-],
0
1,
0
t
0
,],
(36.4)
0
1,
0
1,
L
0
1,
1,
Cl)
z
o
tr
o
z)tL
o
z
J-
oF
=a
o
z
U)
uJ
o
9(,
o
<
É,
d)
tJJ
o
z
trJ
o
o
E]
E
b = 0 and c = 1. F{ence we introduce a ,' b * c which equals 1. Apply the same procedure
to rows 4,5,7,8 introducing the complement for zero Boolean variables.
The disjunctive normal form for a corresponding Boolean expression is, following
the rules for products of elements and their complements,
f= a,, [,, 6@ a,, b,, c@ a * b,l a(} 4,r [,r č@a,,, b,, c.
Check that f does give the required output. The disjunctive normal form always
guarantees an answer, but it is not necessarily the simplest or most efficient in
circuit architecture.
ing circuits
A circuit of on-off switches can also be represented by Boolean expressions. For
example, Fig. 36.11 shows a simple on-off switch in part of a circuit. Current
flows if the switch S is in the on or closed position (a _ I), and does not flow if the
switch is in the off or open position (a
- 0). The variable 4 represents the state of
the switch.
,: zÝ
}--->Fig.
36.1'l On-off switch.
Consider two switches S, and S, in series (Fíg.36.12). Current only flows if both
switches are closed, that is when dt= I and ar= 1, where a, and a2 íepíesentthe
states of the switches. Hence the truth table for the series switches is as shown in
Table 36.1,0. Thus the state of current flow is given by f - d,, b, the product of
a and b.
Similarly two switches in parallel (Fig. 36.13) correspond to the sum of a and b.
The truth table is given in Table 36.1,1,. The final column indicates that f _ a @ b.
The complement oía, the state of switch Sr, is another switch S, in the circuit
which is always in the complementary state to Sr, off when S, is on and vice versa.
(^)
P(r|
Cn
=o
=o
o
1
o
c
=v)
Self-test 36.3
Construct a Boolean expression for the truth table
;4
1
1
1
0
0
0
1
I
0
1
0
1
using the disjunctive normal form. Compare the answer with the answer of
Self-test 36.Z.
U)
z
o
tr
o
zf
l.L
CI
z
I
o
t
=a
o
z
alJJ
(,
9(,
o
<
É,
d)
lJJ
o
z
lJJ
o
o
m
(o
ť)
Table 36.10 Trutb table for tluo stuitches
in series
5, ,žf 5: .n
*dc+-_/ o>-
all
Fig. 36.12 Two switches in series.
0
0
1,
1
0
I
0
1,
Table 36.11 Truth table for tluo stl,.titches
inparallel
0
0
0
1,
Fig. 36,13 Two switches in parallel.
0
0
1,
1,
0
,],
0
1,
0
1,
,],
L
Fig. 36.14 Complement of a
switch using a rigid tie.
It can be represented symbolically by Fig. 36.14, in which the switches S, and S,
are joined by a rigid tie.
These devices are analogous to the gates of Section 36.3. For switching circuits,
the Boolean expressions are often referred to as switching functions.
Example 36.6 Find a sluitcbing function f for the system sbown in Fig. 36.1,5.
Fig. 36.15
,
rc
Example 36.6 continued
Let ar, d1.21 d3l A4 tepíesent respectively the states of each switch Sr, Sr, Sr, So. Since S, and
S3 are in parallel, their output will be ar@ ar. This combined in series with aowill give
an output of (ar@ ar) ,, ao.In turn, this is in parallel with Sr. Hence, the final output is
(ar@ ar) * aa,@ ar
Example 36.7 A light on a staircase is controlled by two switcbes S, and Sr, one
at the bottom of the stairs and one at the top. Suitcbes can be separately 'wp' or
'down'.lf both sLuitcbes are up, the ligbt is off. Either switch changed to doun
switches the ligbt on, and any subsequent cbange to a switch alters tbe state of
the light. Design a trutb table for tbe circuit.
The truth table is shown in Table 36.12, where the state of S, (i = I,2) is A,=0 when the
switch is up (off ) and a,= 1 when the switch is down (on). The light on is /= 1,
"rr4the light off is /:0. This truth table is the same as that for the exclusive_on gate in
Section 36.4. Hence, from (36.4), the circuit can be represented by the switching
function
|= dt,|- az@ d,,, d2.
The actual circuit is shown in Fig. 36.1,6,where S, and S, are one-pole two-way switches.
At Sr, the state 41 represents the switch'up' and its complement a, is the switch down.
A similar state operates at 52.
Table 36.12
Switch S, Switch S, Light
G)
9)
(,l
a
={o
J
ž
o
9
T
o
c
=@
A2a1
up
down
down
up
up
up
down
down
off
on
off
on
0
1,
1,
0
0
0
1,
1,
0
1,
0
,],
Fig, 36.16 Two-switch light
control.
Further explanation of Boolean algebra with many applications to switching
circuits can be found in Garnier and Taylor (1991).
AI
AC
srrpply
a
z
o
F
o
z]tL
(,
z
o
t
=a
o
z
alJJ
o
9
CI
o
<
tr
m
lJJ
o
z
IJJ
o
o
o
::]
Prob!enns
36,1 Read through Example36.1,. Now prove the
other absorption law:
d,ra@b=a.
(Example 36.I aná this result illustrate the duirlitv
principlc, which states that any theorem which
can be proved in Boolean algebra implies another
theorem with ,, and @ interchanged for the same
elements.)
S6. (Section 36.1). Prove the de Morgan result
,@b-a,rb,
by showing that (a @ á) O @ " b) = 1. Explain how
the duality result (Problem 36.1) gives the other de
Morgan theorem.
3fi,3 (Section 36.1). Let B be the Boolean algebra
with the two elements 0 and 1. For arbitrary
a,b eB,prove the following:
(a) a"@@b):o,;:b;
(b) (a @ b) ,, (a @_b) = 6;
(.) (a@b)*4,1S-Q.
3S.,,i. (Section 36.1). Using the laws of Boolean
algebra for the set with two elements 0 and 1,
show that:
(a) a,,b@a_,rb-a;
(b) a @ 6 * 12,,, c- a@ b,, c.
use the result to obtain the truth tables in each case.
:3{i.5 (Section36.4),In Problem 36.4b, it is
shown that
a@a,,,b,rr-a@b,rc.
Design two sequences of gates which give the same
output for the inputs a, b, and c. The resultant
gates are said to be lurq,,;.iiii ;rji,i:r.,iiťlli,.
.1,1íi f.i (Section36.4). Design a circuit of gates to
produce the output
(a@b)"(a@č).
construct the truth table for this Boolean
expression.
;:iŤ, .i' (Section 36.1). Show that the Boolean
expressions (a @ b) * @O á) O a and a @ b are
equivalent.
'::t ::, (Section 36.1). Show that the following
Boolean expressions are equivalent:
(a) a@b; (b) a@b-b.
1
1
1
I
(c)
(d) |i
(Section 36.3). Find a Boolean expression /
which corresponds to the truth table shown in
Table 36.13,
1,
1,
0
0
I
1
0
0
0
0
1,
1,
0
0
1
1
0
1.
0
1
0
1
0
1,
(Section 36.3) . Construct Boolean
expressions for the output /in the devices shown
in Figs 36.17a-d. Constfuct the truth tables in
each case.
Fig. 36.17
Table 36.16
T]
T
o
tD
m
U)
a
0 0
0
1,
1
0
0
1
1
0
1
0
1,
0
1,
0
1,
1
0
0
1
1
0
1,
0
36.15 (Section 36.4). Find switching functions for
the switching circuits shown in Figs 36.19a,b.
li:+;]: :i :l i:;
íÉ
_l 813
L--
36.11 Find the outputs f and g in the logic circuits
shown in Fig. 36.18, This device can represent
binary addition in which g is the 'carry' in the
binary table shown in Table 36.14. The output g
gives the '1'in the '10' in the binary sum 1 + 1 = 10.
*i$rffi:l|i
lt,|';.,'fg'bl . 6114
X+y
0
1
l
10
Fig. 36.19
36.1 6 A lecture theatre has three entrances and the
lighting can be controlled from each entrance; that
is, it can be switched on or off independently, The
light is 'on' if the output /equals 1 and 'ofí' if 1: g.
Let a,= 1, (i = 1,,2, 3) when switch i is up, andlet a,
= 0 (i = 1, Z,3) when it is down. Construct a truth
table for the state of the lighting for all states of the
switches. Also specify a Boolean expression which
will control the lighting.
0
1
0
1
0
0
l
1
36.12 (Section 36.3). Reproduce the logic gate in
Fig.36.6 using just the NoR gate.
3 .13 (Section 36.4). Using the disjunctive normal
form, construct a Boolean expression /for the truth
tables given in Tables 36.15 and36.16.
36.14 (Section 36.3). Show that any Boolean
expression can be modelled using just a NAND gate.
(Hint: use a method similar to that explained in
Example 36.4.)
Table 36.15
0
0
1
1,
0
1,
0
1
0
1
1
1
coNTENTs
37.1 Examples of graphs 815
37.2 Definitions and properties of graphs 81z
37.3 How many simple graphs are there? 818
3z.4 Paths and cycles 820
37,5 Trees 821
37,6 Electrical circuits: the cutset method 823
37.7 Signal-flow graphs 82z
37.8 Planar graphs 831
37.9 Further applications 834
Problems 837
A graph is a network or diagram composed of points, or nodes or vertices, joined
together by lines or edges, each of which has a vertex at each end. Figuíe 37.1,
shows a graph which has four vertices {", b, c, d} and six edges {ab, ab, ad, bd, bc,
cd}. Two vertices are not joined in this graph, namely a and c, while a and b are
joined by two edges. Generally, it is not the shape of the graph which is important;
it is usually the number and connection of the edges which is significant. The
terminology is unfortunate. Graphs in this context should not be confused with
curves generated by functions as in Chapter I.'Networks' might be a more
appropriate term but historical precedent is difficult to overturn. However the
context usually fixes the meaning.
Fig.37.1
Grá áňd
its
ples of graphs
Here are some practical examples of situations and objects which can be usefully
represented by graphs.
(i) Electrical circuits. Figure 37.Za shows an electrical circuit with three resistors
Rr, Rr, and Rr, an inductor L, and a voltage source V1. Each edge has just one
component, and the joins between components are the vertices (the term node is
frequently used in circuit theory) in the graph. Care has to be taken with the
definition of nodes (see Section37.6): they are not necessarily where three or more
wires meet. This circuit has four vertices a, b, c, d, and it can be represented by the
graph in Fig. 37.2b if we are only interested in the links, not what they contain. The
presence of a line or edge between two nodes in the graph indicates that there is a
component between the nodes.
Fig.37.2
Figure 37.3 shows another circuit with six vertices in which the boxes indicate
electrical components. The wires joining c to f and b to e cross over each other.
In the design of printed circuits, it is useful to know whether the circuit can be
redrawn so that no wires cross. Such a gtaph, with no edges crossing, is known
as a planar graph. The graph in Fig. 37.2 ísplanar, but the graph of the circuit in
Fig.37.3 has no planar drawing: at least two edges will cross in any plane diagram
of it. íe shall discuss this notion in Section 37.8.
(l)
:
m
x
T]
m
@
o,Tl
o
7
1,
@
d(b)(a)
Fig.37.3
(ii) Chemical molecules. Molecular diagrams look like candidates for graphs. The
molecule of ethanol can be represented by Fig.37.4a. In its graph representation
in Fig. 37.4b, the vertices represent atoms and the edges bonds. The number of
Rl
d
R,
ILI
l
?,| X, Rr
(a)
Fig.37.4
a
z
o
tr
o
=íL
íL
O
t
o
z
É,
ollJ
I
íL
cí
o
ť)
-o
Ethanol molecule.
Fig. 37.5 (a) Traffic flow in a road grid, (b) Digraph representation of the roads in (a).
bonds which meet at an atom is the valency of the atom. Thus carbon (C) has
valency 4, oxygen (O) valen cy Z, andhydrogen (H) valency 1. Generally in graphs,
the number of edges that meet at aveítex is known as the degree of the vertex.
(iii) Road maps. Road maps and street plans are graphs with roads as edges and
junctions as vertices. However, most road networks include one-way streets.
Hence graphs need to be modified to indicate directions in which movement or
flow is permitted. Figure 37.5a shows a typical section of a street plan with some
one-way streets.
Íe
have to associate directions with the edges as shown in the
graph of the plan in Fig. 37.5b. Note that two-way streets now have two directed
edges associated with them. This is an example of a directed graph, which is also
known by the shortened term digraph.
(iv) Sbortest patbs. Figure 37.6 shows a digraph with weights associated with
each edge. The graph could represent routes between towns S and F which pass
HH
ll
llHH
Fig.37.6
through intermediate towns A, B, ... , the weights associated with each directed
edge could stand for distances or times. This graph is shown as a digraph, but
weights could be present without directions in some cases. 7e might be interested
in this example in the shortest distance between the start (S) and the finish (F).
ritions and properties of graphs
As we have seen, a graph is an object composed of vertices and edges with one
vertex at each end of every edge. An edge which joins a vertex to itself is known
as a loop. If two or more edges join the same two vertices then they are known as
multiple edges. A graph with no loops or multiple edges is known as a simple
graph. A graph with loops andlor multiple edges is known as a mtrltigraph.
A graph in which every vertex can be reached from every other vertex along
a succession of edges is said to be connected. Otherwise the graph is said to be
disconnected. A connected graph is in one piece; a disconnected graph is in two
or more pieces.
The degree of a vertex x is the number of edges that meet there, denoted by
deg(x). If, in a graph G, all the vertices have the same degree r, then G is said to be
regular oídegree r.
Example 37.1 Find the degree of the uertices in the graph in Fig.37.1,.
Three edges meet at the vertex a. Hence deg(a) = 3. Four edges meet at b. Hence
deg(b) = 4. Similarly, deg(c) =2 and deg(d) = 3.
A simple graph in which every vertex is joined to every other vertex by just one
edge is called a complete graph (see also Section 37.S).
Figure 37.7 shows some examples of the various graphs described above.
Multiple
edges
G)
:]\)
o
m,Ťl
z
]o
z@
zo
T]
n
o
T,
m
f,]
_{
m
U)
o,T
o
T
T,
J
U)
c
(a)
",., eftil ',j,
Fig.37,7 (a) Connected simple graph. (b) Connected multigraph. (c) Disconnected multigraph.
(d) Regular graph of degree 3. (e) Complete graph with five vertices: deg(a) = {.
a
z
o
F
o
J
íL
íL
aF
o
z
É,
otJJ
I
íL
t(,
ť)
Since every edge has a vertex at each end, it follows that the sum of all the vertex
degrees equals twice the number of edges. This is known as the handshaking
lemma. For example, from Example 37.1,,
deg(a) +deg(b) +deg(c) +deg(d) -3+4+2+3=t2,
which is twice the number of edges in the graph shown in Fig. 37.1,.
There are two immediate consequences of the handshaking lemma:
(i) the sum of all the vertex degrees in a graph is an even number;
(ii) the number of vertices of odd degree is even.
Self-test 37.1
List the degrees of each vertex, as an increasing sequence, for each graph
in Fig. 37.7.
ow many simple graphs are there?
Graphs can be described as labelled, in which case the vertices are distinguishable
as in Fig. 37 .8a or unlabelled as in Fig. 37 .8b.If we look at graphs with just three
vertices, there are eight labelled simple graphs as shown in Fig. 37.9, but there are
just four distinct unlabelled graphs as shown in Fig. 37 .I0. In Fig. 37 .9 , the three
labelled graphs with one edge will correspond to the one unlabelled graph in
Fig.37.1,0.
The number of labelled simple graphs with n vertices is fairly easy to calculate.
Between any two vertices, there is the possibility of an edge. Any vertex can be
joined to n- 1 other vertices. Since this will duplicate edges, there will be ln(n- 1)
possible edges. Each edge may be either present or not. Hence the number of
possible combinations of present and absent edges will be 21n@-t), which is the
number of labelled graphs (this number increases extremely rapidly, with z).
Thus there must [, 2i+t+-tl = 26 = 64labelled graphs with four vertices; of these,
(a) a
Fig.37.B
(b)
a
o
H
bc
bcbc
Fig. 37.9 Labelled graphs with three vertices.
OOO#
Fig. 37.10 Unlabelled graphs with three vertices.
úJ
i,'
o
É
š
z
9,
T,
m
o
u
T,
@
l
m
J
m
l
m
.o
H
11 can be identified as unlabelled graphs. The latter graphs are shown in Fig. 37.11,.
Of the 11 unlabelled graphs it can be seen that six are connected and four are
regular.
For applications involving electrical circuits, the main interest is in connected
graphs. The numbers of the various categories of graphs up to n -7 vertices are
X
^^
H
7
n
Ň
Z
ň
Fig, 37.11 All unlabelled graphs with four vertices.
a
z
o
tr
o
=íL
íL
U)
F
o
z
E
olJJ
I
I
íL
tE
o
Table 37.1
Labelled graphs
Unlabelled graphs
Connected graphs
Regular graphs
t
1
1
1
2
2
1,
2
8
4
z
2
64
1,1,
6
4
1024
34
2l
1
J
32768
156
1,1,2
8
2097 1,5z
1 044
853
6
given in Table 37 .1,.It can be seen from the table that the number of unlabelled
graphs is a considerable reduction on the labelled set, and that regular graphs
are comparatively rare. The counting of unlabelled graphs does not follow from a
simple formula.
Self-test 37 .2
List all unlabelled simple graphs with five vertices. Indicate which graphs
are connected, and which are regular. íhat are the degrees of the regular
graphs?
and cycles
Suppose we follow a succession of connected edges between two vertices a and z
in a graph, along which there may be repeated edges and vertices. This is known
as a walk between a and z. Iíall the edges walked are different (i.e. no edge is
covered more than once but vertices may be visited more than once), then the walk
defines what is known as a trail. A trail is said to be closed if the first and last
vertices are the same. If all the vertices on a trail are diÍÍerent, except possibly the
end pair, then the succession defines a path. A closed path is known as a cycle. For
example, in Fig. 37.12,a-f-b-c-d is a path between a and d, but a-b-f-e-b-c-d
is only atraíIsince vertex b is passed through twice. Also, a-b-c-d-e-Í-a is an
example of a cycle.
Fig,37,12
Example 37.2 Electrical circuits are usually sucb that euery edge of their
rePresentatiue graPh is Part of a cycle. List all the distinct cycles in the grapb
in Fig.37.2a.
The graph of the circuit is repeated in Fig. 37.1,3. The complete list of cycles is:
3-edge cycles: a-b-c-a, a-b-d-a, a-d-c-a, b-d-c-b;
4-edge cycles: a-b-d-c-a, a-d-b-c-a, a-b-c-d-a.
Fig. 37.13
Fig.37.14
Some graphs have special closed-path and cycle properties. A connected graph
G is said to be eulerian if there exists a closed trail that includes every edge in G.
A connected graph G is said to be hamiltonian if there exists a cycle that includes
every vertex in G. The graph in Fig. 37.I3 is hamiltonian but not eulerian. One
hamiltonian cycle in its graph is a-b-d-c-a. Note that this cycle does not have to
cover euery edge in the graph.
The graph in Fig. 37.1,4 is both eulerian and hamiltonian. An eulerian trail is
a-b-c-d-e-f-g-e-c-g-b-f-a,
and a hamiltonian cycle is
a-b-c-d-e-g-í-a.
It can be shown that a connected graph is eulerian if and only if every vertex
has even degree. This provides an easy test for the eulerian property of a graph.
A connected graph which has no cycles is known as a tree. An example of a tree is
shown in Fig. 37 .15. The edges in a tree are called branches.
Suppose that a graph G consists of the set V(G) of vertices and the set E(G) of
edges. Then any graph whose vertices and edges are subsets of V(G) and E(G)
respectively is called a subgraph. It is important to note that the subgraph must
be a graph whose vertices and edges come from G; and only edges that join two
vertices of the subgraph are permitted in the subset of E(G).
G)
:ol
-{
1
m
m
@
a
z
o
tr
o
=íL
íL
U)
F
o
z
É,
olJJ
J-
J-
íL
íE
CI
()
Fig. 37.15 An example of a tree.
Suppose that G is a connected graph.
Figure 37.1,6a shows a connected graph G and Fíg.37.í6bshows a spanning tree
of G. Graphs can have many different spanning trees. The set of edges that are not
part of the spanning tree (the broken edges in Fig. 37.16b) is known as the cotree
and its edges are called links.
Fig. 37.16 (a) Connected graph. (b) The same graph with a spanning tree.
Construct a tree from a vertex by adding edges. Each edge added must introduce
a new vertex, since otherwise a cycle would be created and the graph would no
longer be a tree. A tree with two vertices has one edge, a tree with three vertices
has two edges and so on. Hence a tree with z vertices must have just n - 1,
branches. It follows that agraph with nvertices must have a cotree with e - n * 1,
links, where e is the number of edges of the graph.
íe now introduce the cutset, by which we can disconnect a graph into two subgraphs
which together contain all the original vertices, by removing a minimum
set of edges in the graph.
(b)
G)
:o)
m
m
o
lo
o
lJ
o
c
=9
m
o
C
-.{
U)
m
m
-o
o
(a)
Fig.37.17 A cutset of a graph.
A proper subset of the cutset is one which does not include the cutset. There must
be no redundancy in the cutset. Thus, for example in Fig. 37.17a, the broken line
Cr, which removes the edges ba, bf, and bc, defines a cutset {ba, bf, bc}, since {á}
and {a, c,, d, e, f} are disconnected subgraphs. CrinFig.37.17b does not define a
cutset, since the subset {ab, bl bc} of edges disconnects the graph.
circuits: the cutset method
In this section we give a brief description of the representation of circuits by
graphs, and show how Kirchhoff's laws can be applied to cutsets of the resulting
graphs. Figure 37.1,Ba shows a plan of a circuit with seven resistors, a voltage supply,
and two capacitors. This particular circuit has 10 components and 10 edges.
Self-test 37.3
(a) 7hat are the degrees of the vertices in the spanning tree in Fig.37.16(b)?
Design a spanning tree with vertex degrees {I, 1,2, Z,2). (b) Indicate spanning
trees of the graph in Fig. 37 .1,4 with vertex degrees (i) {1, I,2,2,Z,Z,Z\ ,
(a)
Fig. 37.18 A circuit and its graph.
C) R6B C D
E
C],
Rí
R,: V(
h
a
z
o
tr
o
íL
íL
U)
F
o
z
É,
olJJ
J-
íL
É,
(,
ť)
Note that A will be a vertex or node (a preferred term in circuits) but that the
joins B, C, and D are not separate nodes but can be coalesced into a single node.
The equivalent graph is shown in Fig. 37.1,Bb: it has five nodes and ].0 edges. Note
that it is a multigraph with two nodes joined by two edges and two nodes joined
by four edges.
A circuit loop in the circuit is a cycle in the graph.
Kirchhoff's laws have already been stated in eqn (2I.8), but for convenience they
are given again here in graph terms. They state (i) that the algebraic sum of the
uoltages around any looP is zero, and (ii) that the algebraic sum of tbe currents
entering any node is zero.
In addition, for resistors we also have Ohm's law which states that the uoltage
across a resistor is directly proportional to the current flowing through ir, that is
uni or u=Ri,
where the constant R is measured in units called obms (Q). Figure 37.I9 shows a
circuit with two independent maintained current sources irand ir: the symbol of
the circle enclosing an arrow represents a maintained current in the direction
of the arrow.
The corresponding six-node digraph with currents ir, ir, ... , irin the directions
indicated is shown in Fig. 37.Z0.If any current turns out to be negative then its
direction will be opposite to that shown.
Fig. 37.19
Now introduce nodal voltages uo1 u61 ..., uf as shown in Fig. 37.21. The use
of nodal voltages means that effectively Kirchhoff's first law is automatically
satisfied. The earthing at e makes u"= 0 and other voltages can be measured relative
to this zero ground potential.
This circuit has 13 unknowns: 8 currents and 5 nodal voltages. The problem
with circuits is the selection of the minimum number of consistent equations
from kirchhoff 's laws and ohm's law sufficient to determine the unknowns.
The graph of this circuit is the same as that in Fig. 37.I6a, and we shall use the
same spanning tree as shown in Fig. 37.I6b.In this graph, the number of nodes z is
6, the number of edges e is 10. Hence the cotree has, from the previous section,
e-nt ]. = 1,0-6 * ] =5links. Anycutsetof the original graphs whichcontains
one and only one branch of the spanning tree (the rest of the cutset consisting of
links) is known as a fundamental cutset of the circuit. Hence we can associate five
Fig.37.21 Fig.37.22
fundamental cutsets with the spanning tree in Fig. 37.1,6b. Five possible cutsets
Cr, Cr,... , C, are shown in Fig. 37 .Z2.
By repeated use of Kirchhoff 's second law to the nodes on one side of a cutset,
it follows that the algebraic sum of the currents crossing the cutset must be zero.
Hence the five cutset equations are:
Cr: ir- is* ix=0,
Cr: ir- is* io+ ir* ir- is=0,
C3: i,- irt i, - ir: g,
Co: ir- i5- ir+ ir_0,
Cr:ir-is=0.
These equations must be independent since each one contains a current from a
branch of the spanning tree which does not appeaí in any other equation. Further
any non-fundamental cutset equation will be a linear combination of the five
fundamental cutset equations. The number of branches in the spanning tree
defines the number of independent equations.
7e can also apply Ohm's law to each resistor (note that current flows from
high to low potential). Thus the voltage difference across R, is tl, - ub, so that
it= (u,- u5)lRr.
Similarly
ir- (u1- u,)lRr,
il: (uu- u1)lRl,
io- (u1- u)lRo,
i, - ullRr,
io: |u,)lRn,
ir: urlRr,
ia= (ua- u,)lRr.
e can now substitute for the currents from (37.6) to (37.I3) into (37.1) to (37.5)
resulting in five linear equations to determine the nodal voltages uo, ub, u", u6, uliít
terms of the known currents i, and i". The remaining currents can then be
calculated from (37.6) to (37.1,3).
o)
Jo)
m
m
o
f]
o
9
a
o
c
=?
m
o
c
@
m
{
m
J-
o
o
(37.1)
(37.2)
(37.3)
(37.4)
(37.5)
(37.6)
(37,7)
(37.8)
(37.9)
(37.10)
(37.11)
(37.12)
(37.13)
a
z
o
F
o
=íL
íL
C)
F
o
z
cí
otJJ
íL
ír
o
ď)
Example 37.3 Using the cutset metbod, find all currents and nodal uoltages in
the circuit shoun in Fig.37.23.
R,=ja
-= Fig.37.23
The circuit can be represented by a graph with five nodes (Fig.37.24) with the currents
il, i2, i3, io, i, in the directions shown.
Fig,37.24
A spanning tree with three links is shown in Fig. 37.Z5 together with cutsets Cr, Cr,
Cr, Co. Hence Kirchhoff's second law implies:
C; i1- i.+ ir=0,
C2: iy- irt iz=0,
C3: -iy* ir- ir+ ir=0,
C.: -iy + i4+ iz= 0.
íith u"=0, the currents in terms of the nodal voltages uo, ub, u"l u7áíe ,, by Ohm's law:
it: (uo- u6)lRr=Z(uo- uu),
iz= (u,- u6)l&r= +(u, - u),
iz= (ua - ua)lRr= ub - ud,
iq= (u,- ua)lRo: +@, - u),
is=udl&r= tuo.
Eliminate the currents in (37 .14) to (37.17) using (37.I8) to (37.2Z):
2u"-!u5*!u,*ud=0,
1rr-!u,-ud=2,
-1rr*!u"-iro=2,
-tru* |u, - iro = 1,.
(37,14)
(37.15)
(37.16)
(37,17)
(37.18)
(37.19)
(37.2o)
(37.21)
(37.22)
(37.23)
(37,24)
(37,25)
(37,26)
,
R:= 1Q
; _]
^
Rs=2f)
Fig. 37,25 Fundamental cutsets.
I
Example 37.3 continued
These are linear equations which can be solved using the methods of Chapter 12.
Computer algebra is also very useful in solving sets of equations of this type (see the
computer algebra applications for Chapter 12 in Chapter 42). The answers are
uo= 5 Y, u6-- 4Y, u,= 4V, ua:ZY.
Since u,= ub, no current flows through the resistor on bc.
7e can summarize the result for an earthed circuit which contains only resistors and
cuffent sources. Suppose that the representative graph of the circuit contains n nodes and
e edges of which fcontain known current sources. The curcuit will have e - /unknown
curfents andn- 1unknown nodal voltages giving e-f +n-lunknowns in total. Its
spanning tree will have n - 1 edges which will lead to n- 1 fundamental cutset equations,
and Ohm's law will apply to e - /resistors. Hence we shall always have a consistent set
of e - f + n - 1 equations to find the unknowns.
This result can be extended to circuits with current sources, voltage sources (batteries),
and resistors. If the representative graph has n nodes and e edges of which /contain
current sources and s maintained voltage sources, then the number of unknown currents
will be e - f andthe number of unknown nodal voltages will be n - 1 -s since the nodal
voltage difference across abattery will be known. Hence the number of unknowns is
e- f + n-!- s which will satisfy z - 1cutset equations and e- f - s Ohm's laws.
iSrgnal-flow 9raphs
Figure 37.26 shows a block diagram of a negative-feedback control system. The
input into the system is P(s) and the output Q(s).All operations are defined by their
transfer functions (see Secti on 25.4). The boxes represent devices or controllers.
The circle represents a sum operator, and the return sign on F(s) indicates positive
or negative feedback. The output signal Q(s) is fed back into the input through
H(s), and it is a negative feedback which will reduce the output. In a later problem,
we shall consider a device with a positive feedback. Thus the input into G(s) is
A(s) -P(s) -F(s).
The boxes each produce outputs given by the transfer functions
Q(s) _ G(s)A(s),
F(s) - H(s)Q(s).
7e wish to find Q(s) in terms of P(s), G(s) , and H(s), from the equatíons (37.27)
to (37.29). Thus, from (37.28)
Q(s) = G(s)Á(s) - G(s)[P(r) - F(r)], = G(s)[P(s) - H(s)Q(s)].
Fig. 37 .26 Negative-feedback
control system.
oo
\
q.
o
z
l
,Tl
o
=o
T
T]
J
Cn
(37.27)
(37.28)
(37.29)
a
z
o
F
o
J
íL
íL
U)
F
o
z
É,
otJJ
I
J-
íL
cí
(, Hence the output transfer function is
o(s) =
G(') r,(r).
1 + G(s)H(s)
This is the closed-loop transfer function. The actual signal can be obtained by
finding the inverse Laplace transform for Q(s). Flence the system is equivalent to
that shown in Fig. 37.27.
If the feedback reinforces the input signal it is called positive feedback.
Figure 37.28 shows a multiple-feedback control system with a positive and a
negative feedback. The output signal is given by
which can be obtained by the method of block-díagram reduction. For example,
the feedback through Hr makes the system equivalent to that shown in Fig. 37.Z9.
7e can now combine the series devices which reduce the system to the negativefeedback
control system considered at the beginning of this section. The details
are omitted here.
Fig,37.29 First stage in the block reduction of the multiple-feedback control system.
(37.30)
This block-reduction method can get quite complicated for a complex feedback
system. Instead of using block reduction in this way, represent the system by a
weighted digraph as shown in Fig. 37.30, where the weights are the transfer
functions - except that the edges representing the input and output are assigned
Fig. 37.27 Block-reduced diagram
for Fig. 37,26.
-H_,(.)
Fig. 37.30 Signal-flow graph for the multiple-feedback control system shown in Fig. 37.28.
weight 1 since they carry no devices. Also the negative feedback is replaced by
-Hr(s), to make sure that it reduces the input into Gr(s). This is the signal-flow
graPh of the system. Let the inputs into the nodes be xr, x2, x3, and xoas shown;
then, for the positive-feedback cycle,
Xu= Grxr, X2= GtXtl Hrxr.
(The argument (s) has now been dropped from the working.) Hence
G,G. x.
.. <
-
-
.
" I_GrH,
In other words, we can replace (") by (b) in Fíg.37.31,.
(^)
:N
9,
o
z
I
,1,1
o
o
T
T]
J
U)
(a) (b)
Fig. 37.31
There are other rules, and acomplete list now follows for the replacements for
subgraphs in the graph.
(a) Multiple edges. See Fig. 37.3Z. This follows since
xr= Gxr* Hxr- (G + H)xr.
(;lGr
1_ C)HI
bY *--<
Xl x3
G
-,,^.. c+H
*, \>/", x| x2
H Fig. 37,32 Multiple edges.
(b) Edges in series. See Fig. 37.33. This follows since
xr= Hxr- H(Gxt) - HGxr.
(;HGH
+ by+--}--<
x1 X2 X3 x-L x3 Fig, 37.33 Edges in series.
_t 829
\
---
(c) Cycles. See Fig. 37.34. This follows since
xr= HX, and xr= Gxr* Jxr.
Assume that HJ + 1; otherwise there is infinite gain.
(d) Loops. See Fig. 37.35. This follows since
xr= Gxr* Hx,
with H*I.
(e) Stems. See Fig. 37.36. This follows since
xr= Gxr, x3= HXr= HGXI X+= Jxz- JGx1.
Apply these rules to the successive reduction of the feedback system in Fig. 37.30.
The sequence of steps in the reduction of the signal-control graph to a single-edge
graph is shown in Fig. 37.37. The weight of the final edge agrees with the output in
eqn (37.38).
U)
z
o
tr
o
=íL
íL
a
t
o
z
É,
olJJ
íL
É,
(,
ď)
(;
r-H
by O---*e
x1 Xz
Fig.37,36
x^
Stem.
GlG]Grl(1 - H,G.)
CrGr.
1* HlG2
GH
,|-H|
by .--4lx1
x3
x1 Gx
Fig.37.35 Loop.
X4
l rule (c)
t
l ,ule (c)
Ý
Gl(;rC;r
p(s) l*HlC,+(i,(i,G3H, Q(r)
lrl
I
Ý
ClC;]C;]
I-H|G,+C,C}.G,Fl,
#
Fig.37.37 Successive steps in the
reduction of the signal-flow graph of
the control system shown in Fig. 37.Z8.
-
Essentially the operations in a signal-flow graph are those applied to a
weigbted digraph as illustrated in the following example.
Example 37.4 Find the outPut-inPut relation in the signal-flou) graph shown in
Fig.37.38.
Applying rule (a) to the multiple edge, and rule (c) to the cycle, the graph is reduced
to Fig. 37.39. Apply the series rule to the divided edges to give Fig.37.40. Finally the
multiple-edge and series rules give Fig.37.41,. Thus the output is given by
abd
q=:*+he(g+f).
I-bc
In the actual control system A,b, c,... will be transfer functions.
Fig.37.38 Fig.37.39
q)
I@
T
z
T
o
1
!
Cn
abd
I-bc
,tbd
;-----,| he|g + í)I-0c
Fig.37,41
Fig.37.40
Self-test 37 .4
Suppose that c is in the opposite direction in the signal-flow graph Fig.37.38.
Find the new output-input relation.
As we remarked in Section 37.1,, planar graphs are important in circuit design
since planar circuits can be manufactured as a single board. A planar graph is
a graPh that can be drawn with no edges crossing or meeting except at vertices.
The standard example of a simple application which cannot be represented by a
Planar graph is the delivery of three services, water flJ7), gas (G), and electricity (E),
to three houses A, B, C (Fig. 37.42). This graph has no plane drawing. The reorganization
of the graph in Fig. 37.43 shows the impossibility of this; if 7 and C are
connected last then this edge must cross either AE or BG.
b(g+ f)e
u)
z
o
F
o
íL
íL
U)
L
o
z
íE
otJJ
-L
I
íL
cr
o
Fig.37,42 Bipartite graph Kr,.. Fig.37,43
The graph in Fig. 37.42 is an example of a bipartite graph in which one set
of vertices may be connected to another set of vertices, but not to vertices in the
same set. If every vertex in one set is connected by one edge to every vertex in the
other set then it is called a complete bipartite graph. If the sets have m and n
vertices respectively, then the notationK*,,denotes the complete bipartite graph.
Figure 37.4Z shows the graph Kr' and this graph is not planar. Check that the
graphs Kr,randK,r, are planar.
In planar graphs there is a relation between the numbers of vertices, edges, and
faces. In a plane drawing oía graph, the plane is divided into regions called faces.
One face is the region external to the graph. Figure 37.44 shows a planar graph
with five vertices and seven edges, and with four faces: A, B, C, and the external
face D.
A remarkable formula, due to Euler, links the numbers of vertices, edges, and
faces of a graph.
Theorem (Euler). Suppose that the graph G has a planar drawing, and let y be
the number of verti ces) e the number of edges, and f the number of faces of G.
Then
U-e*f=2.
Proof. For the graph G, define a spanning tree (see, for example, Fig. 37 .45). The
spanning tree must have n vertices and n - 1 edges (see Section 37 .5). It must also
have just one face. Since
n- (n- 1) + I=2,
Euler's formula holds for the spanning tree. Successively replace the other edges
in the graph. Each time an extra edge is added, aíaceis divided and one extra face
is added. However, algebraically, this cancels the additional edge in the accumulation
to Euler's formula for the spanning tree. Hence
U-e+f=Z
reconstructed
I
Fig. 37.45 A graph with a spanning tree.
o)
b
T]
z
1
o
1
1,
J
Cn
Fig.37.44 A planar graph with
fiver vertices, seven edges, and
four faces.
The complete graph wíthnvertices is denoted by K,.Since every vertex is joined
to n - 1 vertices, Knhas *r@ - 1) edges. The graphs of K2, K3, Ko, and K, are
shown in Fig. 37.46. Of these graphs, Kr, Kr, and Ko are planar, but K, and all
succeeding complete graphs are not.
Fig.37.46 The complete graphs K, for n=2,3,4,5.
The graphs K:,: and K, are the keys to tests for planarity of graphs, and whether
it is possible to design, for example, a plane printedcircuit board to make the required
connections between electronic components. It was proved by Kuratowski
in 1930 that every non-planar graph contains subgraphs which are either Kr,, or
Kr, or Kr,, or K, with additional vertices on their edges.
Further discussion of graph theory with many applications can be found in the
introductory text by 7ilson and Watkins (1990).
Self-test 37.5
(a) A regular dodecahedron has 12 faces (pentagons) and 30 edges. How
many vertices does it have?
(b) An icosahedron has 20 faces (triangles) and 12vertices. How many edges
does it have?
\-
^
l
o
b
cr
b
fl
o
b
T
(s
b
a
z
9
o
íL
íL
aF
o
z
cr
ollJ
-L
F
J-
íL
tr
o
ť)
fther applications
Braced frameworks
Consider a Írame which consists of four struts in the shape of a rectangle
(Fig.37.47a) with pin joints at each corner.
'
7ithout a diagonal tie the structure will
not support a veitical load, but will collapse into a parallelogram as shown in
Fig.37.47b. The structure can be made rigid and load bearing by the insertion of
a diagonal strut as in Fig. 37.48.
Fig. 37.47 Single unbraced
pin-jointed frame.
Fig. 37,48 Braced frame.
Consider now a pinjointed framework with m X n rectangular frames with
some individual frames braced. How can we decide whether a particular framework
is braced, that is no part of it can be sheared? And if it is braced, how many
ties could be removed to leave a minimum bracing? The framework is similar to a
vertical section of scaffolding or a steel-framed building, although in both cases
the joins are bolted but can still need bracing to ensure rigidity.
Figure 37.49 shows a 5 X 6 framework with 11 braces as shown (braces can be
diagonal struts in either direction). Label the cell rows ťb T2, ... , T5 and the cell
columns cb c2, ... , c6 as shown in Fig. 37 .49. The framework will be represented
by a bipartite grapb (see Section 37.8) with the cell rows and columns as vertices.
Arrange them in rows as shown in Fig. 37.50.
ca
r1
r5
Fig. 37.49 5 x6framework.
I]
\1
tl
a
b
\^
ft
cr1
b,
ib
ri
t1
P
Fl
w
si
si
H
csc4czc1
r4
,./-t\
I
,y -/ gycl9
í
É -/ I
I
É -/
IÍa partícular rectangular cell is braced then the identifying row and column
vertices are joined by an edge. Thus the cell rrcris braced so that an edge joins r,
and crin the bipartite graph. No edge joins r, and c, since this cell is not braced.
The bipartite graph representing the framework is shown in Fig. 37.50.If the
graPh is connected,thenthe framework is braced since the shearing of any cell or
group of cells is not then possible. The graph is connected in this case, and the
framework is braced. Can any braces be removed in such a way that the framework
is still braced? Any brace which is removed must not disconnect the graph.
If the graph contains a cycle (Section 37 .4) then any edge removed from the cycle
will not disconnect the graph. This removal rule can be applied to each cycle in
the graph . If, at the end of this process, there are no cycles remaining and the
graph remains connected, then the framework is said to have a minimum bracing.
The framework graph in Fig. 37.50 contains just one cycle, namely rlc{3car4c6r2c2rl
(see Fig. 37 .49). Ary edge can be removed from this cycle leaving a minimum
bracing. The removal of any further edges will disconnect the graph.
If every cell is braced in a framework then the bipartite graph will be complete,
and the framework will be seriously overbraced. You might note that acomplete
biPartite graph K*,,has mn edges but a minimum bracing íor an m X n framework
hasm*n- 1edges: for example, if m- 5 andn_ 6 then mn=30 whilst
m*n-1=10.
Figure 37.51, shows an unbraced 4X 5 framework, its (disconnected) graph, and
the same framework sheared.
c1 ca
r1
Fig. 37.51 An unbraced framework.
Phasing of traffic signals
Figure 37 .52 shows a roadjunction with eight incoming lanes oítraífrcand a onewaY
exit. Suppose that each lane can be controlled by its own individual signal.
One solution for trafficmanagement would be to allow each lane to have a green
signal in sequence with the remaining all on red, but this would be inefficient
since obviously several lanes of traífrc can move simultaneously without risk.
How can an efficient phasing of the signals be designed?
Label each incoming lane a, b, c, ... , h as shown, and let these be vertices of a
graPh (Fig. 37.53). Starting, say, with a we decide which traffrclanes aíecompatible
with a;that is, which lanes can also have green lights simultaneously without
risk of a collision. Thus a and b are compatible, and we therefore join a and, b by
G)
I(o
.Tl
c!
-m
a)
T,
T,
l-
o
{
o
z@
c2
U)
z
o
F
o
J
íL
íL
@
F
o
z
É,
olJJ
I
íL
tr
o
ď)
Fig.37,53
an edge. Lanes a and c aíe also compatible, and we therefore join a and b by an
edge. Lanes a andc are also compatible, but a and e aíe not, and so on. The graph
G in Fig. 37.53 shows which lanes are compatible, and is known as the compatibility
graph for this junction.
'
Ve now look for complete subgraPhs (Section 37.S) in G. An edge is a complete
subgraph (Kr), a triangle (Kr) is a complete subgraph with three vertices, Ko with
four vertices, and so on.
' 7e try to use the largest subgraphs in any couering of G,
that is a list of subgraphs which includes all vertices. In G, abcd, abdf, and abfg
are K. subgraphs, and there are a large number of triangles. For example, we can
cover G by the set of subgraphs
{abcd, abfg, def, fgh}.
Generally, we include as many large subgraphs as possible. In this list it is better
to use fgh rather than just gh: this could be chosen since / is included in other
subgraphs.
Suppose that the period of the traíficsignal sequence is 7 seconds with each
lane having a green light for at least {r. There are four different traffrc flows
represented by the subgraphs. Suppose that each subgraph list of lanes has a
green light íor |T. The green/red phasing sequence is shown in Table 37.2.
The actual phasing lane by lane is shown in Fig. 37.54 where the solid line
indicates the green light for alane. For example, between!T andtT,lanes A, b, e,
f are on green with the others on red.
Table37.2
Subgraph
Time abcd abfs drf fsb
0-+T
ir-*r
ir-ir
ir-r
green
red
red
red
red
8reen
red
red
red
red
red
gfeen
red
red
green
red
Fig. 37.52 Road junction.
. abcd_ abfg- j.gf _fgh-
abcd
abfg
_def- fsh
-,,
j ]
:í
Fig. 37.54 Traífrcphasing. Fig.37.55
The total waiting time for the traífrc at the junction is a measure of the efficiencYof
thetimingsandphases. Letto,tb,t",... bethewaitingtimesof thelanesso
that, from Fig.37.54, we can see that to=*T, tu=iT, t"=1T,etc. Hence the total
waiting time V/, is given by
Wr=ta+tb+... + t, _ tT + +r + iT + +T + +T + +r + +T + +T _ZT.
Can the waiting time be reduced within the time constraints by choosing either
a different set of subgraphs to cover G, or a different sequence of timings?
Figure 37.55 shows the same choice of subgraphs but with different timings.
The result is a slightly shorter waiting time oílT.
T]
D
o
tD
m
@
f
a
h
f
h
(Section 37.2). \ň/rite down the degree of each
vertex in the graph in Fig. 37.56.
(Sectio n 37 .2) . Draw the complete graph with
six vertices. How many edges does it have?
unlabelled graphs with five vertices. How many of
them are planar?
37.4 Sketch the eight regular graphs with six
vertices. How many of them are connected?
37.5 The adjacency matrix of a graph G with
no loops is a vertex-vertex matrix, in which
the element in the ith row and jthcolumn is 0
if vertices i and jare not joined by an edge,
and r if i and jare joined by r edges. Thus,
if we list the vertices a, b, c, d as 1, 2,3,4
respectively, then the adjacency matrix of
the graph in Fig. 37.I is
Note that the leading diagonal has zeros if there
are no loops. The adjacency matrix is a formula
for the graph.
Evaluate Á2. ťhat is the interpretation of the
matrix in terms of the edges of G?
[o 2 0 1l
. lz 0 1 1l
o=l0 1 0 1l,
[r 11 0]
837
u)
z
o
tr
o
=íL
íL
U)
t
o
z
E
ouJ
íL
E,
CI
ť)
-tij" Draw the graphs defined by the following
adjacency matrices:
,", o [i ?ii| ,,,
^
|; 1l ilLl 1i10_] Lu
37.7 ' 7rite down the adjacency matrices of
the graphs in Fig. 37.7. Note that a single loop
introduces an element ]. into the appropriate
position on the leading diagonal.' 7hat
characterizes the matrix of a disconnected graph?
37.8 (Section37.4). How many different cycles
pass through a single vertex in a complete graph
with four vertices?
37.9 (Section 37 .4). List all trails between vertices
a and f in the graph shown in Fig. 37.57.Identify
which trails in the list are also paths.
37.10 (Section 37.4).Is the graph in Fig. 37.57
eulerian? If it is find an eulerian closed trail. Is it
hamiltonian?
37.11 (Section 37 .5). Construct a spanning tree
for the graph shown in Fig. 37.57. Draw its cotree.
Show that there is a spanning tree in which no
vertex has degree more than two.
Fig.37.57
37.12 Figure 37 .58 shows a graph with seven
vertices.
(a) Decide whether the graph is eulerian.
(b) Construct a spanning tree for the graph.
How many branches does the tree have?
(c) Draw a cutset which disconnects the vertices
á,b, g, f from the vertices c, d, e.
i^ QT ÁQl ,u- í.JU
7-13 Figure 37.59 shows a digraph. How many
trails are there between a and e? which of them
are also paths? Can you find a four-edge cycle ?
Fig- 37,59
3V"14 (Section 37.6). Figure 37.60 shows a circuit
with an independent current source lo. Represent
the circuit by a graph. How many vertices does the
graph have?
R2 R3 R4
trý
iR,
*/iR. ( ),. R7
í:ig. 37,-6{t
*?.1 (Section 37 .6). A circuit is represented by the
graph shown in Fig. 37.61.. The current io is from
an independent source, and all other edges contain
a resistor in which the current i, passes through a
resistor R, and so on. Define a spanning tree for the
lx= 1A
T]
T
o(p
m
U)
A
t/!
li
^|v
ll
N
|
"3P/
|\
+ilii:i:i:::iii]]+ini]lil|ilin]i]i] iji1 :,]]::l
ffi
Rr=3f2
Re=lQ
Rl=1 )
Rg=lf)
l"I
=
Rr=tO {
I
Rl=1Q I
L^^^|
(a)
Fig.37.62
Fig.37.63
!g. *:7.6x
graph. How many fundamental cutsets are required?
''0ťrite
down the current equations associated with
each of the cutsets. If ir=2 A, a maintained current,
u.=0 (earthed), and Rp: 1 ) for k_=0,1,,2, ...,7,
find the remaining voltages ual ub> t/d, u..
7"'1S (Section 37.6). Figures 37.62a,b show two
circuits with current sources and resistors. use
the cutset method to find the modal voltages and
currentS through the resistors.
3Y."í l Complete the block-reduction method
for the multi-feedback control system shown
in Fig. 37.28.
3 P" ' (Section 37 .5). Figure 37.63 shows a
positive-feedback control system. If P(s) is the
system input, find its output Q(s), and the transfer
function of a single equivalent device.
; "X S (Section 37 .7). Find the outputs in the
systems shown in Figs 37.64a,b by progressively
replacing parts of the system by equivalent devices
until just one device remains. Find the transfer
function of the resulting equivalent single device.
Fig. 37.64
R:=3 )
lx=lA
U)
z
o
F
o
íL
íL
@
F
o
z
É,
ouJ
F
íL
E
o
ď)
Fig.37.65
37.2O (Section 37 .7). Reduce each of the signalflow
graphs in Figs 37.65a,b,c,d to an equivalent
single edge, and (e) to a stem, and find the transfer
function in each case.
37.21 (Section 37.S). Label the edges, vertices, and
faces of the graphs shown in Figs 37.66a,b and
verify Euler's formula.
Fig. 37,66
37.22 (Section 37.8). Show that the bipartite
graph Kr' has a planar representation.
37 .23 (Section 37 .8). The complete graph K, does
not have a plane drawing. What is the minimum
number of edge crossings in a plane representation
of the graph?
Fig.37.67
G]G,G]G
Fit
*?,*d} (Section 37 .I). List all the paths between
S and T in the network given in Fig. 37.6, and
hence find the shortest and longest paths. (This
method of simply listing all paths can become very
extensive for larger networks: efficient algorithms
are really required to reduce the number of
calculations.)
it7"i:'.S (Section 37 ,9). Show that the framework
in Fig. 37.67 is overbraced. How many ties can
be removed to leave a minimum bracing?
b
Fit
x5
(a)
(b)
(c)
Fig.37.68
Fig.37,69
37.28 (Section 37 .9) . The framework in Fig. 37 .69c
is required to be strengthened so that it is
overbraced with each diagonal tie as an edge in at
least one cycle in the associated bipartite graph.
7hat is the minimum number of ties which must
be added?
37.29 Figure 37 .70 shows a junction with eight
distinct lanes of traffrc each controlled by a
separate traífrc signal. This is really a'design and
solve ' problem. Here is one model: of the doubtful
cases assume that lane a is compatible with both
c and e, and that e is compatible with b.Draw
the compatibility graph for this junction. List all
complete subgraphs with four and three vertices.
If the period of the traífrc signal cycle is 7 and the
subgraphs
{abef, cdg, aeh}
are chosen with each allowed green for jT,
calculate the total waiting time. Suppose thať
the subgraph abef runs íor lT and the others
for jr each. How does this áffrrtthe total
waiting time?
Fig.37.70
T]
u
o(p
m
a
841
|-------
Lt---:-: --
coNTENTs
38.1 Discrete variables 842
38.2 Difference equations: general properties 845
38.3 First-order difference equations and the cobweb g+z
38.4 Constant-coefficient linear difference equations 849
38.5 The logistic difference equation 854
Problems 859
In many applications, functions can only take discrete values - that is, they cannot
(for various reasons) take a continuous spectrum of values. It is reasonable to
model the temperature in a room by a function which varies continuously with
time - most of the calculus in this book is concerned with such functions. on the
other hand, the population size of a country can only take integer values. As
births and deaths occur, the population size is discontinuous in time, and the
graph of population size against time will be a step function. Between births and
deaths the population number wilI be constant so that we are only concerned
with changes which take place at these events. In this problem jumps occur at
variable time intervals.
' 7e can obtain discrete data from a continuous signal or function by sampling
the signal at regular time steps rather than keeping a continuous record. This is
often the situation in microprocessor-driven operations.
The progress of events is often described in the form of equations linking several
successive events: so-called difference equations. The reader may notice analogies
between the solutions of these and the solutions of differential equations.
screte variabIes
Let us start by considering a simple financial application which generates discrete
values. In compound interest the sum of {Po is invested in an account to which
interest accrues annually at a compound rate of t00l%.Ií fPl is the amount in
the account at the end of the first year, then
P-,_(I+1)P0. (38.1)
Let fP,be the sum after n yeaís. Then, similarly
P..: (I + 1)P_. ,.
This is an example of a difference equation or recurfence relation. It gives the
values of P, at the integer values 1,2, ... in terms of the immediately preceding
value. Treating the variable as n, the difference in this case is 1. The notation P(n)
instead oÍ P, is often used to emphasize the function aspect of P but we have
chosen the more economical subscriptíormP,.
It is fairly easy to solve (38.2) by repeated application of the formula starting
with (38.1). Thus
Pr- (1+l)Pl: (1 + l)'Po,
&= (1 +l)P2_ (1 +I)rPo,
and so the formula
P,: (1+ l)"P, (38.3)
holds at least for values oín up to 3. Suppose that (38.3) holds for n _ Ř. Then
(3B.2) implies that
Ph*t: (1 + I)Pu - (1 + l)k*rP'.
So the same formula holds for Pp*r. Hence, if the result is true for kthen it is also
true for k+ 1,. Equation (3B.1) confirms that it is true íor k- ].. It follows sequentially
that it is true for n = 2, ft = 3, and so on. (This method of proof is known as
induction.)
Example 38.1 {1000 is inuested for 5 years at the follouing rates: (a) 5%
annually; (b) +% calendar montbly; (b) *% daily (ignoring leap years).
(c) Calculate the final amount in the account in each cAse.
In each case the formula is
P,= (I + l)"P',
with Po = 1000, but the 1and n difíer.
(a) This is the original problem withn= 5 and 1:0.05. Hence
P, : (1 + 0.05)5 x 1000: 1.055 x 1000 = 1276.28
(in {, to the nearest penny).
(b) This account has 12 com7ounding Periods eachyear, giving a total of 60 over the
5 years. Hence we require
_ ( 0.0_5 )nn
P^n=|l+ -'-- l x1000 =1283.36.
( tz)
(c) For the daily rate, there are 365 X 5 = 1825 compounding periods. Thus we require
ptszs
=(, * 9
)""
*
There is a slight gain with increasing number of compounding periods.
(38.2)
1284.00.
o
6
o
T
m
m
!
F
tD
m
U)
U)
z
o
F
D
ottJ
uJ
o
zlJJ
É,
uJ
tL
tL
a
The following financial application of a loan repayment leads to a difference
equation.
The general mortgage problem is as follows. An amount fP is borrowed for a
period of N years, at an interest tate of i"/o per annum (as a fraction l this is equivalent
to [,(il1,00) per yeaíper pound of debt). Repayment is made by } equal
payments f,A, one at the end of every yea\ starting at the end of of the first year.
There are two constituents of each payment Á. One part goes to pay the interest
on the debts that was carried during the previous year. The rest is used for capital
repaymenl to reduce future debt. Given P, } and 1, we want to know the regular
annual repayment Á required to exactly clear the debt at the end of year N. (There
are other mortgage models that are used which calculate interest daily or
monthly: the above method can be adapted by changing N to handle these cases.)
The nth payment Á is made at the end of yeaí n, after which the debt outstanding
is denoted by ,o. The payment Á comprises:
(interest owed on vln_| through yeat n) + (a capital repayment)
Therefore
A=lu,_r* (u,_t- u,) or u,=-A+ (1 + l)u,_, (38.4)
where fl=Ir2, ... ,N,uo= P, and the constant A is to be chosen so that the final
payment clears the debt, that is uN = 0.
The difference equation can be solved by step-by-step employment of the
recurrence relation (3B.4). In general
u,= -A * Fr,_, (we put ]. + 1
- B, for brevity).
Start with uo=P, and calculate the sequence Llb L!2, u3, ... , uNi
ut= -A + BP,
uz= -A + Frr- -A + B(A+ BP) = -A(1 + B) + BLP,
ul=-A+ Frr- -A+ B{-A(I + F) + F'P} =-A(1 + B+ 1 + F'P,
and so on - the rule for subsequent terms of the sequence is clear. Use eqn (I.36)
to sum N terms of the emerging geometric series in B; then
uN= -'A(! + F + F, + ... + Brv-r; + B*p = -^,'á_;i'' + B'p.
Using the conditíon u* = 0, we find that
^ l(I + /)NP_:-
(1+l;N_,,
Example 38.2 Tbe sum of í50000 ls borroued ouer 25 years to be repaid in
equal instalments, the interest on tbe outstanding balance in any year being8%.
Find the annual repayments ouer the term of tbe loan.
In the notation above, P = í50 000,1:0.08, N = 25. Therefore the annual repayment to
El
T]
T1
w]
@
ť)
(
A
(r,
oí
dr
th
T]
oI
Ca
fe
is
oI
fir
te
Se
k,
Sr_
ar
the nearest penny is
^ l(I + l)NP
,_. _ ----------------_
(1+1)^-1
0.08 x 1.0825 x 50 000
= {,4683.94
1.0825 _ 1
Example 38.2 continued
The total repayment over 25 years is
NÁ: Z5A= [,1,17 098.47.
The capital repayment included in A at the end of year 1 is only
uo-ut- A-lP={"683.94,
which indicates how interest payment predominates in the early years of the mortgage.
equations: general properties
Any equation of the form
un-f(un_l1l!n_2l ... ru,_*) (38.5)
(where m Ís an integer >- 1) íorconsecutive sequence of integers n, which may
or may not terminate, is known as a difference equation. The term discrete
dynamical system is also frequently used. Thus
ur=2ur_r*2,
ur=3Llr_, l2ur_2* n',
un+1,= ku,("l - u,)
are examples of difference equations.
The number m in (38.5) is known as the order of the difference equation: it is
the difference between the largest and smallest subscripts attached to u, namely
n-(n-m)=m.
Thus (38.6) and (38.B) are first-order difference equations, while (3B.7) is secondorder.
The sequence of integers attached to u can be translated (i.e. any integer
can be added to the index z) without affecting the difference equation. The difference
equation
un+2= 3u,+t * 2u, + (n + 2)2,
is the Same as (38.7) : nhas been replaced by n +2 throughout, although the limits
on n change.
Given initial conditions, the successive terms are very easy to compute. For a
first-order difference equation, we can assume that zo is given, but it could be any
term, say uD which is taken as the initial condition. Generally, our aim is to find a
sequence {u,} anda formula Íot unÍor n > r which satisfies the difference equation.
The difference equation (3B.8) (which is known as the logistic equation) with
k=2 is
G)
Pl\)
9
Tl.Tl
m
f,
m
zom
m
oc
-|
o
z
?
o
m
zm
B
T,
D
o
T,
m
aJ
{
m
U)
(38.6)
(3B.7)
(38.8)
(38.9)ur+,l,=2ur(1- u,).
Suppose that we put u0- }; then
,,
J
Ul = -, lrt,l
-8
the sequence
65 53515 255
c uaz
-
32, 512
. Ur=
1,31072' " ' )
U)
z
o
F
=)ouJ
uJ
o
ztJJ
É,
lJJ
lL
!J.
o
@
ď)
'r, Lt3 Lt4
Fig, 38,1 Iterations of the sequence
u,*r= Zw,(1 - u,) wíth uo= *.
follows by successive substitution. This sequence of numbers is actually approaching
the value t as n increases. íecan sketch the sequence by discrete values at
integer values of x in the usual cartesian axes. The series of dots in Fig. 3B.1 is a
graphical representation of the sequence.
The implied limiting value oí u,as n -) "o for this particular sequence suggests
that u,- j is a constant solution of the difference equation (38.9), and this can be
confirmed. \)7e can find all constant solutions by simply putting un= u íora|l n.
From (38.9), the constant solutions are given by
u-Zu(l-u), or2u2-u=0,
which implies that u = 0 and u =i are solutions. These are also known as the fixed
points or equilibrium values of the difference equation.
Fixed points or equilibrium values
For any first-order difference equation un+l= f @,), its fixed points are given
by solutions of
,=f(u). (3B.1o)
You might notice, by trial computation, that the solutions of (38.9) vary quantitatively
with the initial value, uo.If 0 1 uo ( 1, then un appeaís to approach j as
nbecomes large, but, if uo} I oítl, { 0, then unbecomes unbounded for large n.
e shall discuss the logistic equation further in Section 3B.5.
For the second-order difference equations, the same process gives equilibrium
values. For example, if
un*r-Zur*r* 4ur:6,
then this equation has an equilibrium value obtained by putting un+z= un+1= un= u,
so that
u-2u*4u-6 or u:2.
On the other hand, the second-order difference equation (38.7) has no equilibrium
values since
u-3u-2u-nz=-4u-n2
can never be zero for constant u and all n.
Self-test 38.í
(38.2) The sum of f100 000 is borrowed over a 25 year term at an annual
interest tate oÍ 6.5%. Find the annual repayment assuming that the interest
rate remains the same throughout. At the end of 5 years, the interest rate is
increased to7o/". \ /hat should the annual repayments be increased to repay
the outstanding loan over the remaining 20 years?
|-order difference equations and the cobweb
An alternative method of representing solutions of difference equations graphically
is the cobweb construction. Consider the first-order difference equation
un+.,= f(r,) _ }u,+ 1,.
The equation has a fixed point or equilibrium value where
4-tw+1, sothat u=2.
\J7ith this in view plot the lines y = x and y _ +x+ 1 (Fig. 3B.2) in the x,y p|ane.
These straight lines intersect at x = | = 2, which corresponds to the fixed point.
Select an initial value, say) u0- t, andrepresent it by the point Pr: (ur,0) - (+, 0)
in the x,y plane. From the difference equation
ut=iuo*1=*.i*t=ž.
7e can represent this by the point Pr: (uo, ur) = É,i) i" Fig. 38.2. Join Po to Pr, and
then to Qt: (urur) = (*,
*)
""
the line != x. Now join Q, toPr- (ut,uz) = qJ, f;) on
y - +x * 1. Repeat the process by drawing lines between ! = x and y _
lx +'1 using
the same rules.
The usefulness of the method is that a graphical representation and interPretation
of the solutions can be achieved by simple line drawings as shown in
Fig. 38.2 and in the following example. It is particularly helpful for finding fixed
points and assessing their stability. The connected lines are known as cobwebs
for obvious reasons. ' 7e can observe that this difference equation has only one
fixed point at (Z,2), which is stable, since all cobwebs approach the point form
any initial point.
Fig.38.2
.Tl
f,
u)
-.{
t
o
T
o
m
T
o.Ťl
-11
m
7J
m
zom
m
o
c
{
o
zU,
z
o
-lJ
m
o
o(D
m
(p
U)
z
o
F
f
g
lJJ
lJJ
o
ztJJ
É,
lJJ
tL
lL
o
@
(Ý)
For a general difference equation un+1 = f@,), the cobweb construction takes
place between the straight line ! = x and the curve y - f(x).
Example 38.3 Sketch a cobweb solution for
Un+,=-kur+ k,
for (a) k = *, (b) Ř - *, (r) k-= 1, using tbe initial ualue uo = 1 in eacb case.
Fig, 38.4 Cobweb for
un*r= -Z11,+ 2 with uo=i.
(a) Plot the lines = x and y = -+x + }. They intersect at the fixed point (+, +). Starting
from Po , (*, 0), the cobweb traces PoPlQlP,QrP, . . .in Fig. 38.3. Evidently it approaches the
fixed point as n -) -, indicating stability.
(b) The lines are ! = x and y = -+x + ;. The fixed point is at (+, i), and the cobweb
path is POP.QI,Q,_ ... i. Fig. 38.4. The path moves away from the fixed point implying
its instability.
(c) The lines are y= x and!=_x+ 1with fixedpoint (+,+).Thepath starting atpo:
(+, 0) follows the rectangle PrQrPrQr, indicating periodicity (Fig. 38.5). This is true for
any starting value except that of the fixed point itself.
Graphs of the sequences uu versus rz are shown in Fig. 38.6.
Fig. 38.3 Cobweb for
un*t=-iu,+} with uo=i.
Fig. 38.5 Cobweb for
iln+l=-un+ 1with uo=1.
Fig,38.6 Solutions of L!n*r=-k(u,+ 1)for (a) k: *, (b)á= Z,(c) k=7.
(c)
ii\ /\ /
\,(l.(t/ t/
ťťly
l} r >t>l >I
The stability of the fixed point of the general first-order linear difference equation
can be summarizedas follows.
Stability
The first-order difference equation u,*r- -k n+ ahas a fixed point at
u = al (1 + k), (k * -I). The fixed point is stable if I Ř l { 1, unstable if l Ř l > 1,
and periodic if l<= 1.
Ií k= -1, the equation has no fixed point unless a = 0.
G)
@
o
o
z@
z
I
o
om,Ťl
,n
9
m
z_.|
|-
zm
n
o.Tl
.Tl
m
!
m
zom
m
oC
{
o
zU,
Self-test 38.2
Consider the difference equa tion u,*, - f(u,) - + - u2,. PIot the curve y - f(x) _
}, - ,'and the straight line y - r. 7hat are the coordinates of the fixed point
in the x,y plane? Given u, = 0.2, compute Llz, Ll3, t4+, Lts. Draw the corresponding
cobweb. Does it indicate stability of the fixed point?
-coefficient linear difference equations
Any difference equation of the form
url an_rUn_t * . .. * A,_*tlr_*= f (n) ,
where the a, (i
- n - ffi, ... ) n- 1) are constants, is a constant-coefficient linear
difference equation.
'
7e shall look in detail at the second-order case
u,+z* Zau,*r+ bu,= f (n), (38.12)
where a and b are constants and f(n) is a given function. The methods gener alíze in
a íaírlyobvious way to higher-order systems.
There are many parallels between the difference equation (38.12) andsecondorder
constant-coefficient equations (Chapters 18-19). The equation is said to be
homogeneous if f (r) - 0, and inhomogeneous otherwise, just as in the case of
second-order differential equations. However, this section is self-contained and
reference back is not necessary. The general solution of the inhomogeneous case
requires that of the homogeneous case: hence we start with the latter.
Homogeneous equations
' (l'e can see how to proceed by looking at the first-order constant-coefficient equation
un+1,- ctt,=Q. (38.13)
As can be seen from (38.Z) or verified directly, the general solution of this equation
is
(38.11)
(38.14)Ltr= Ac,,
where Á is any constant. Notice that we could equally well write
Ur=Acn-l, Oí tlr= Ac'*l:
cr)
z
o
l-
f
ouJ
ttl
o
zlJJ
tr
lJJ
lJ.
lJ_
n
@
ď)
the result would be equally correct, although A would take different values for the
same initial condition. The significantproperty of (38.13) and its solution (38.1a) is
that un*ris a constant multiple oÍu,.
7ith this in view, we attempt to find solutions of
iln+z*2Aun*1* bun-g
in the form u,:?n,where p is aconstant. Thus
u,+z* 2Au,*r+ bu,= p"2 + 2ap"+1 + bp" _ (p2 + Zap + b)p" _ g,
forall n,ííp=Oor
p2+Zap*b=0.
The case P = 0 leads to the self-evident solutiofl u, = 0.
'
7e are interested in
solutions of (3B.16), which is known as the characteristic equation of (38.15).
There are various cases to consider. Suppose that the roots of (38.16) are the distinct
numbers p, and pr. Hence u, - pT and u,- p! arc solutions of (38.15). Since
this equation is homogeneous and linear, it follows that any linear combination
of pr and p3 is also a solution. 7e state this as follows.
The general solution of u,*r*Znu,*r+ bu,= 0 for distinct roots prandpzoí
(38,15)
(3B.16)
p2+Zap+á=Ois
(38,17)
u,_ ApT+ Bpi, íorany constants A and B.
Example 38.4 Find tbe general solution of
iln+2- Un+l - 6ur- g.
The characteristic equation of (38.18) is
p2-p-6=0, or (p-3)(p+Z)=0.
The roots aíeP1=3,pz:-2.Hence the general solution is
Un: A,3" + B(-2)".
(38,18)
Example 38.5 Find the solution of
U,+zl2ttr+t - 3u,- 0
tbat satisfies uo= "l,,
ur:2.
The characteristic equation is
pz+Zp-3=0, or (p+3)(p-1):O.
The roots aíeP1- -3, Pz= 1. Hence the general solution is
u,= A(-3)" + B,1" = A(-3)" + B.
From the initial conditions,
uo:1= A+ B, ut=2:_3A+ B.
Hence l = -i and B = f,. The required solution is
u,= -+.(-3), + +.
The characteristic equation can have equal roots, which is a special case.
Consider the difference equation
U n+2 - ZAI,! r*, * Azli, -
g,
where a # 0.Its characteristic equation is
p' -Zap + a2 =0, or (p - a)' _0,
which has the repeated íootp - a. One solution is Aa"; but we require a second
independent solution. Consider the expressiofl u,= na".Then
un+z- 2Au,*1+ azu,_ (n * 2)a"*'* 2(n + I)a"+z + nA'+z
= A"+z(n + 2 - 2(n + 1) + n1 -
g.
Hence a further independent solution is u,= BnA'.
Roots can also be complex. Consider the difference equation
ur+z* 2rr*r* 2u,- g.
Its characteristic equation is
p'+Zp+2_0
with roots Pt= -1, * i, Pz- -1 - i. The method still works and the general solution
becomes
u,_ A(-I + i)" + B(-1- i)".
For a real-valued problem, the constants A and B will be complex conjugates
which ensure that u, is real. The solution can be cast in real form by using the
polar forms (Section 6.3) oíthe complex numbers. In this case
-1 +i _^lr.t|ni.
Hence
u, - !)i" eln;" * p2i" r-lni"
_ 2Ž"|A(cos }nn* i sin *n") * B(cos in, - i sín }nn)]
_ 2+"(C cos Jnn* D sin inr),
where C _ A+ B and D = (A- B)i.
G)
@
o
o
z@
{
z
-|I
o
o
m.Tl
.Tl
9
m
z
|-
zm
f,]
9.T.|
.Tl
m
7
m
z
o
m
m
o
-J
o
z@
The general solution oíu,*..- ZAI,t,n, * azu,= 0 is
u,= (A* Bn)a". (3B.19)
Complex roots, at 1P:= y siqi
The general complex solution of
U,+z*2ALt,*r* bu,=0,
where az 1b,is
u,= A(oc+ iF)" + B(a- iB)".
The general real solution is
un=ť(C cosnO+D sinn0). (38.20)
U)
z
o
tr
:)
oul
lJJ
o
ztlJ
É,
IJJ
l.L
lJ.
o
@
ď)
Example 38.6 Obtain the general solution of
Ur+z* Ur=0.
The characteristic equation is
p2 + l=0,
giving roots Pt= i, ?z=,i. Hence
U,= Ai" + B(-i),.
In polar form, i = ej'', -| : g-jfii. Hence the real form of the solution is
u,=Ccostnn+Dsintnn.
l nhomogeneous equations
The general inhomogeneous equation is
u,+z* 2au,*1+ bu,= f(n)
(See (3B.12)). Let u,=u,* 4n,where u,isthe general solution of the corresponding
bomogeneous equation. Substitute this form oÍu,into (3B.21):
(u,*zl 4n*z)
-| 2a(u,*r* 4,*r) + b(u,-| q,) = f (n),
or
(un*z* 2nun*r+ bu,) * (4,*r+ Zaqn*r+ bq,) = f (n).
Since u,satisfies the homogeneous equation, it follows that
cl+z* Zdcl+l* bq,= f (n),
which means that q, must be a particular solution of the inhomogeneous equation.
As in differential equations) unis known as the complementary function.
7e construct particular solutions by appropriate choices of functions usually
containing adjustable parameters which are suggested by the form of the function
f (n).Ií a particular choice fails, then we reject it and try something else.
Example 38.7 Obtain tbe general solution of
Un+2- Un+l- 6un-4.
From Example 38.4, the complementary function is
Un=3"A+ (-2)"B.
For the particular solution, we tfy Qn= C, since f(n) = 4. Then
4,+z- 4,+t- 6q,- 4 : C - C - 6C - 4 = -6C - 4 = 0,
if C = -]. Hence Q,= -3, and the general solution is
%,=3"A+(-z)"B-+.
Example 38.8 Obtain tbe general solution of
Ur+z* ZUn+t- 3ur- 4.
From Example 38.5, the complementary function is
u,= (-3)"A* B.
Exa
In tl
the,
q
The
q
ifC
u
l
ticu
dirt
Tab
f(n)
a
k"
n
nP (i
;
u
The
p
The
L',
For
q
The
q
The
Her
,
(38.21)
sin J
,
Example 38.8 continued
In this case we expect the choice Qn= c to fail, since it must make the left-hand side of
the difference equation vanish. 7hen this happens, we try
Q,= Cn.
Then
Q,+zl ZQ,*r- 3q,- 4 = C(n + 2) + ZC(n + 1) - 3Cn - 4 - 2C + 2C - 4 = 4C - 4 = 0,
iíC = 1. Hence the general solution is
u,= (-3)" A+ B + n.
oo
P
o
o
z@
z
I
o
o
m.Ťl
-Tl
9
m
z_.{
r
zm
f,
o,1,1
.Tl
m
:0
m
z
o
m
m
oc
_.|
o
za
Table 3B.1 lists some simple forcing terms
ticular solution and alternatives containing
direct substitution.
Tab|e 38.1
f (n) wíth suggested forms of parparameters
to be determined by
f(") Trial solution 4,
Ř (a constant)
kn
n
nr (p an integer)
sin kn or cos kn
C; or Cn, if C fails;
or Cnz, if C and Cn fall; etc.
Ck"; or Cnk", if Ck" fails; etc.
Co+ Crn
Co+ Crn + ...+ CrnP (may need higher
powers of n ln special cases)
C, cos kn * Crsin kn
Example 38.9 Find tbe general solution of
Un+2- 4u, - 1,1.
The characteristic equation is
p2 - 4:0, or (p -Z)(p +Z) =O.
The roots are P1= 2, pz= _2. Hence the complementary function is
U,=2"A+ (-z)"B.
For the particular solution, try (choosing from Table 38.1)
4,= Co* Crn.
Then
4n+2- 44,*r- tr= Co+ Cr(n +Z) - 4Co- 4Crn- n= (-3CO+ZC1) + n(-3Cr- 1).
The right-hand side vanishes for all n if
-3Co + 2C1- 0, -3Cr- 1 = 0.
Hence C, = -{, Co=2Ctl3 = -i, and the general solution is
u,=2"A+(-2)"B-i-i".
U)
z
o
tr
f
g
ut
llJ
o
zIJJ
É,
lJJ
l.L
!J.
o
Self-test 38.3
Find the general solution of u,*2- 4un+tl4un- 2".
logistic difference equation
Consider again the logistic difference equation
iln+I= au,(l - U,), (38,22)
where a,is aparameter which will take various values. Thís nonlinear equation can
model population growth of generations. If u, represents the population size of
generation n and a is the birthrate, then we might expect the population size of
the next generation to be duninthe absence of any inhibiting factors such as lack
of resources or overcrowding. lf a> 1, then the population model given by the
first-order difference equatiofl un+1,= dLl,would imply that the population would
gfow to infinity, since the equation has the soluti on t n = d'tl,. To counter this
possibility, we can introduce a feedback term -uu?, which will tend to reduce
population growth when the population is large.
Fixed points of the equation (38.22) occur where
u= au(l- u);
that is, íor u= 0 and u - '],
- Il a.' 7'e can adaptthe cobweb method of Section 38.3
to this nonlinear difference equation by plotting graphs of the parabola y - f (x) ax(I
- x) and the straight line ! = x. Fixed points of the difference equation occur
where the line and the parabola intersect. The values of x at these points are given
by the solutions of
ax('I - x) = x, or x(ax _ 1 _ a) =0.
In the cobweb, the fixed points have coordinates (0, 0) and P : (1 - (Ila),1, - (1,1a)).
''
íeshall only look at values of a ) 1, so that one fixed point is in the first
quadrant, x } 0,y ž 0. A cobweb solution starting at for the case d=2.8 is
shown in Fig. 38.7.
Notice that, for this choice of a and uo, the fixed point P appears to be stable;
that is, the cobweb solution approaches P. The slope of the graph oíy - ax(l - x)
at P determines the stability or instability of the solutions. The slope at P is
Fig, 38,7 Cobweb solution for
u,*r=2.8u,(1 - ,,) showing a
solution starting from x = uo
approaching the fixed point at P.
38.5
mf '(I - (IlaD - a- 2a(1, - (IlaD = -d,* 2.
As with the cobweb for two intersecting lines for the linear difference equation
in Section 38.3, the fixed point P is locally stable iím _ 2 - a ž -I,in that all
cobweb paths starting close to (a- I)la approach the fixed point P as n+ oo. This
inequality implies that u< 3. Notice also that, if 1 < d 1 2,then y _ r intersects
the parab ola y - dx(l - x) between the origin and its maximum value. This
followssincethemaximumoccursatrc - tandO< 1 -1la< jimplies 1{ a<2.
For d, > 3 the solutions become more complicated. The fixed point at the
origin is unstable: hence there is no stable fixed point to which solutions can
aPproach. 7e can obtain a clue as to what happens if we look at the function of a
function given by
y - f(f(x)) - alax(l- rc)] |1, - ax(l, - x)] _ ďx(I - x) - a3xz(I - x)2.
\ /hen a, = 3,this curve intersects ! = x at x =0 and at P only. This can be
checked by noting that fixed points can be found from
x - 9x(I - x) -27 x'(1 - *)'
which can be written as
x(27x3 - 54x2 + 36x - 8) = 0, or x(3x -2)'=0.
Graphs of the curves y = f(x) and y - f(f(x)) for a= 3 are shown in Fig. 38.3a.
The fixed point P on y = f(x) is at (], 3). a. d increases two additional fixed
points develop on the line y = x. Further graphs of the two functions y _ f(x)
and y = f(f(x)) for a,
- 3.4 areshown in Fig. 38.8b, together with the line ! = x. The
graph indicates that there are now four fixed points at O, A, B, C.
For general a,the fixed points oí y - f(f(*)) occurs where
or*
= a2x(1, - x) - a3 x2 (I - x)2,
x(l - a - ux)la'*' - a(l + a)x+ 1 + d) = O,,
o)
P(,l
J-
m
o
o
ó{
o
o,Tl
,T
m
D
m
zo
m
m
o
c
{
o
z
Fig. 38.E
,(a) Graph of y = f(f(x)) for the critical case ď= 3. (b) Graph oíy = f 1f@)) for d,= 3.4
showing fixed points (), A,B, C. The dashed curve shows y = f(x) in both."i"r.
a
z
o
tr
f
g
lJJ
lrl
o
ztlJ
É,
IJJ
lJ.
tL
o
@
C)
where we could have predicted the soludon tr - (1 - a)la corresponding to the
point B in Fig. 3B.Bb. The solutions of
o xz-u(l+a)x+I+a-0 (38.23)
are
1'} =lr, + al{{(a+ 1)(a-3)}] (a> 3)
xz) 2a'
which determine, respectively, the coordinates of Á and C.
From (38.23)
xrl xr- (1 + u)la.
Also
f(*r) - Mt(I - xt) = axt- M?
= dxt- íla)|a(I + d)xt-I - a] (using (38.23))
-1Ila)(-axr+1+ d)=xz
by eqn (38.24). Similarly f(rr) = *r.
It follows that
f(f(xr)) = f(xr) = x, and f(f(*r)) = f(xr) = x2.
Hence ífx = x, initially then subsequently x alternates between x, and x, shown
by the square in Fig. 3B.8b. This phenomenon is known as period doubling.
The values ,c = x, and x = x2 are fixed points of y - f(f(*)), and their stability is
determined by the slopes oí y - f(f(*)) at the points.
The critical slopes for stability at A and C are both (-1); we now find the value
oí a at which this occurs.
' 7e have
! r'r'rr' _ ty.z
-2a2x - a3(2x -6x2 + 4x3)
d*'r'
\&ll- u
(3B,24)
(38.25)_ a2 -Za,'(I + a)x + 6a,3xz -4a3x3.
'
íe require the value of a given by
íl
Ť f(f(x)) _ -1 or 4a,3x3 -6a,3x2 + Zaz(L + a)x - d2 = L, (38.26)
d,x
when x satisfies (3B.23).
Remove the x3 term from (38.26) by multiplying (38.3) by 4ax, and subtracting
it from (38.26). Then
-2,u2(a-2)x2+2a(a-2)(a+í)x- (í+a2) _g. @8.27)
Equations (38.26) and (38.27) must have the same roots in x. In each case, make
the coefficient of xz equal to 1. The equations for comparison are
@ +I\ @ +I\
x2_)-r*' '-0.
aaz
@+1\ @2+I\
Ť2- ' r* -0.a Zuz(a - 2)
These equations have the same roots if
a+1_ (a2+1)
u2 2a2(u - 2)'
or
a2-2u-5=0.
' 7e are interested in values oía ) 3, so that the required root of (38.29) is
d,- 1+ r/6 = 3.449... . In fact the slopes at both A and C both become -1 for this
value oía. Thus, for
31a<l+tl6,
theZ-cycle solution is stable.
As a in creases from 1, the stable fixed point at x = (a- 1)labecomes unstable
at d - 3. This bifurcates into a stable period 2 solution.
At a- 1 + r/6, th. system bifurcates againinto a 4-cycleor period-4 solution,
which corresponds to the set of stable fixed points oíy - f(f (f(f(*)))). A graph of
this function for d,=3.54 is shown in Fig. 3B.9 together with the eight fixed points.
The cycle doubles again at about a= 3.544, ... and so on. The intervals between
the bifurcations of the period doubling rapidly decrease, until a limit is reached
at about a=3.570, ... beyond which chaos occurs. The iterations are no longer
Periodic for most values oÍ a beyond this point, although there are some brief
intervals of periodicity.
(38.29)
C,)
PO,
m
o
o
6
-{
o
o.Tl
,Ťl
m
T
m
zo
m
m
oc
-{
o
z
Fig. 38.9 Fixed points of
v = f(f(f(f(x)))) for d,= 3.54,
given by the intersection of
the curve and the line y = 1,
Logistic equation
un+l=f@,)=au,(I-u,).
Fixed point Íot a ) 0, x } 0 at xo= (d* I)la.
Fixed point xo stable if
f '@o) - a- 2axo= _u+ 2 } _1, that is if a < 3.
Period-2 solution: fixed points (a > 3)
xl,xz= {1 + aT r/t(a+ I)(a- 3)]}l(2a).
Period-2 solution stable if 3 < a < !+ !6. (38.28)
a
z
o
tr
:)
alJJ
LlJ
o
zlJJ
íE
lJJ
lL
lL
a
@
(9
The sequence of period-doubling bifurcations is known as the Feigenbaum
sequence, and it has certain universal aspects in that it is not just a consequence of
the logistic equation, but has common features with other difference equations
which generate period doubling.
The simplest way to view the progressively complex behaviour is through a
computer-drawn picture of the iterations of
un+1,= aur(1, - ur)
for stepped increases in astarting at d,=2.8 up to a,-3.B,which covers the main area
of interest. The result is shown in Fig. 38.10. The series of single dots for each a,
in 2.8 < ď < 3 indicates the fixed point, which then bifurcates into a stable Z-cyc\e
attractorfor3{d<1+{6.Thisinturnbifurcatesintoastable4-cyc\eattíactoí
at a= r + r/o and so on. The effect of infinite period doubling is that the solution is
ultimately non-periodic. The generally chaotic and noisy behaviour of the difference
equation can clearly be seen in the large number of dots for larger values oí a.
These non-periodic sets are known as strange attractors. The successive iterates
of the logistic equation wander about in a seemingly random but bounded manner,
and never settle into a periodic solution. However, within the chaotic band of
ďvalues, there appear windows of periodic cycles. Problem 38.26, for example,
confirms that there is a 3-cycle around a=3.83.
The logistic equation can be thought of as a relatively simple model example.
Many similar nonlinear difference equations also exhibit similar period-doubling
bifurcations and strange attractors.
l,ů
{].8
ů.{i
i] i| li i;i, :
{i,1
{}" ]
:"S ,j"{] .1.: 'i"4 .],íl _]"lj
Fig. 3B,10 Period doubling for the
logistic equation for increasing a,
followed by chaotic iterations
beyond about a=357.
Fnobíems
38.1 {1000 is invested over 10 years at an interest
rate of 60/o annually. Find the final total investment.
'
7hat should the montbly interest rate be to achieve
the same final total?
38.2 The sum of í50000 is borrowed over 25
years and the money is repaid in equal annual
instalments. The interest rate on the outstanding
balance in any year is 10%. Find what the annual
repayments would be. After 5 years, the interest
rate is reduced to 9o/o.
(a) Find the required adjustment to the annual
repayments for the loan to be repaid over the
original term.
(b) If the repayments are not changed, by how
much will the mortgage term be reduced?
38,3 Find the fixed points of the following
difference equations:
(a) u,*r= u,(2 - w,);
(b) ,,*r= un(l + u,) (2 - 3r,);
(c) u,*r= sin u,; (d) u,*r= j sin u,;
G\ u ,.=e""-1.
38,4 Given the initial value urin each case,
calculate the sequence of terms up to u5 for each
of the following first-order difference equations:
(a) u,*r= 2u,(3 - u,), uo= l;
(b) u,*r: 2u,(1 - u,), uo= lri
(c) un+1,= 3.2u,(1 - un), uo= i)
(d) u ,*, = 4u ,('l - u,) , uo = !.
38.5 (Section 38.3). Sketch the cobweb solutions
for the following first-order equations with the
stated initial conditions, and discuss the stability
of the fixed point:
(a) u,*r= žr,+ j, ro= t and uo= tr;
(b) u,*r- 2rn- 2, ilo= ! and uo= 1z)
(c) un+1= -u,l 2, uo= } and uo= 1;
(d) u,*r=-ir,+ },uo= jand uo=1i
(e) un+!= -2u,-| 3, uo=j and uo= 1.
38"6 The function /(n) satisfies
f(n)=f(*n)+L
Put n=2- and g(m) = f(2-), and show that
g(m) = g(m- 1)+ 1.
Hence frnd f (n) given that /(1) = 6.
38,7 Use the method suggested in the previous
problem to solve
f(n) =f(!fl + l,
given the initial condition f(t) =O.
38,8 (Section 38.3). Find the general solutions of
the fo] lowing difference equations:
(a) u,*r* 2u,*1- 3u,- 0;
(b) ,,*r* 9u.= g,
(c) il,+zl9u,=01
(d) u,- 4u,_r* 5u,-= 0;
(e) u,+2- 4lt,*rl 4u,:01
(f) Un+3- U,+z* il,+I- u,=0j
(g) u,*r- Lt,=0;
(h) u,*, - 3u,*zt 3unn, - un= 0;
(i) Un+2- un+1- l1,* tl,_r= 0.
38,9 Express the solution of the initial-value
problem
Ur+z- 6u,*r* I3un=0,
in real form.
ilo= 0, Ut= 1,
38.10 Find the difference equation satisfied by
u,= A,2" + B,(-5)",
for all Á and B.
38.11 Obtain particular solutions of the following
inhomogeneous difference equations:
(a) u,*, * 2un*, - 3Ll, = f (n), where
(i) f (n) =2"; (it) f (r) = n; (i11) f (n) =2
(iv) f(n) = (-3)".
(b) u,*r * 2un*, * Ztl n = f @), where
(1) f(n) = 1; (ii) f(n) = n * 3;
(tli) f (n) =ro"lnn.
(c) un+3 - 3u,u* 3un*rl u,= f (n), where
(1) f (") = 1; (ii) f (r) = n; (111) f (n) = n'.
(d) u,*, - 6u,*, * 9un = f (n), where (1) f (n) = 2";
(ii) f (n) = 3; (iii) f (n) = 3'; (iv) f (n) = n3".
38,12 A ball bearing is dropped from a height
z= boon to a metal plate, and the coefficient of
restitution between the ball and the plate is g
where 0 { e { 1. Set up a difference equation for
the maximum height reached aftet n impacts.
Solve the equation. (Assume that a ball dropped
from a height á hits the plate with speed , =.,l(zgh),
where g is the acceleration due to gravity. The
rebound speed of the ball is ez.) Instead of being
stationary, the plate now oscillates so that it is
moving upwards at a speed u (a constant) at the
moment of each impact with the ball. Find the
difference equation fot b,. Show that the difference
equation has a fixed point and interpret its
meaning.
1]
1
o(D
m
Cn
38.13 D,(*) is the n x n determinant defined by
a
z
o
tr
f
olJJ
lJJ
o
zuJ
É.
llJ
tL
l!
o
@
ď,
|r*
o,t"): l 1
I
|0
,^-, =|ri
Show that
oI
,:, 9l @>2),
:. ,'.*|
Dr(x) = 2y.
10
2x1
óó
tl
2r|'
D,(r) =ZxD,_r(x) - D,_r.(x).
Solve the difference equation for x * 1 and x = 1,.
38.14 Let {u,} (n=0,1, ... ) be a sequence. The
power series
š
í(r,,*) - L r, *'
n=0
is known as the generating functiorr of the
sequence. Thus, for example,íf u,= (*l)"ln!,then
6 l l\
š t-l'
í(u,, x) =
A;x"
= e-',
which means that e-" is the generating function
of {u,}.
The generating function of {z,*,} is
Conside r the difference equation
Un+Zl Un+I- 2Ll,= 0, Uo= 1, ut= -2
By taking the generating function of the eq
show that
,1
ífu... x\ ]
-.
' 1+2x
Using the binomial theorem frndu,.
13.5 to fir
38.15 A Fiborracci sequence is defined as a differenct
sequence in which any term is the sum of the two--1-------
preceding terms. For the Fibonacci sequence 38.21
starting with ur= I, xrz= 2, frnd and solve the equat
difference equation for u,. u,.
T\_^,-.
38.16 Solve the initial-value difference equation
and show that u,-+ { as n ) a.
38.17 A symmetric random walk takes place on 3
the integer steps on the line between x = 0 and u
x = N. At any position x = r (1 š r š N - 1), the
S
a
d
O
\
t]
ffi
probability that the walker moves to either x = r * 1,
or ]c = r - ! at any stage is j. The probability ul,that
the walker reaches x = 0 first, given an initial
position x: l<, satisfies the difference equation
ut = Žut_t+ )ulr*1, Uo=1, ilN=O,
for 1 < A < N- 1. Find wn,Whatis the probabiliry
that the walker reaches x: N first?
If dp is the expected number of steps in the walk
before it reaches 0 or N, then dl,satisfies
d, = !(1* dnnr) + t1L+ du_,), do= d*=g
for 1 š A < N- 1. FirT d the expected duration of
the walk.
:, ' -, : Show that u,= n! is a solution of the secondorder
difference equation
un+2= (n + 2)(n * 1)u,,.
By using the substitution u,: unfr|., find a second
irrdeperrdent solution.
l,,:]. -. Given that
n
,,:)Ř',
,{= 1
find a first-order difference equation for s,. Solve
the equation to find a formula for the sum sí.
!ij,,';;:.i,: Show that the difference equation
u_,, ,l 2au__,, ,l bu = 0
can be expressed as
^ _
^-,d,r,4
-
l1Lnl
where
ó
b
lt
f,
C
t]
L}
f,
,.. =|',1^ A =|-z:Nn
Lr,,)' L -l
Deduce that
zr= A"zO.
31
3S.26 By starting ítom uo= 0.957 417 , compute
u1, u2, ... , xls for the difference equation
U,+1= au,(L - U,), u= 3.83,
and confirm that the logistic equation appears to
have a 3-cycle for this value of a.
38.27 Find the fixed points of the difference
equation
H,+1.= au,(1 - U,)',
in the three cases (a) a=9, (b) a= 4, (Q a= 2r.
Discuss the stability of the fixed points in each case,
38.2E Show that the special logistic equation
iln+I= 4u,(1 * u,)
has the solution
u,= sin2(2"Cn)
where C is any constant. This general solution
includes closed-form chaotic solutions. For
example, if C=lln,then
T,
T
o
t!
m
o
u,= sinz(2")
which never repeats itself for n:0,1,2, ..- .