Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

36 RELATIONS [CHAP. 2

(b) The matrices ofMR,MS, andMR◦Sfollow:

MR=

1

2

3

⎡abc

⎣

010

101

000

⎤

⎦ MS=

a

b

c

⎡xyz

⎣

010

100

011

⎤

⎦ MR◦S=

1

2

3

⎡ xyz

⎣

100

011

000

⎤

⎦

MultiplyingMRandMSwe obtain

MRMS=

⎡

⎣

100

021

000

⎤

⎦

Observe thatMR◦SandMRMShave the same zero entries.

2.6. Consider the relationR={( 1 , 1 ), ( 2 , 2 ), ( 2 , 3 ), ( 3 , 2 ), ( 4 , 2 ), ( 4 , 4 )}onA={ 1 , 2 , 3 , 4 }.

(a) Draw its directed graph. (b) FindR^2 =R◦R.

(a) For each(a, b)∈R, draw an arrow fromatobas in Fig. 2-7(b).

(b) For each pair(a, b)∈R, find all(b, c)∈R. Then(a, c)∈R^2. Thus

R^2 ={( 1 , 1 ), ( 2 , 2 ), ( 2 , 3 ), ( 3 , 2 ), ( 3 , 3 ), ( 4 , 2 ), ( 4 , 3 ), ( 4 , 4 )}

2.7. LetRandSbe the following relations onA={ 1 , 2 , 3 }:

R={( 1 , 1 ), ( 1 , 2 ), ( 2 , 3 ), ( 3 , 1 ), ( 3 , 3 )},S={( 1 , 2 ), ( 1 , 3 ), ( 2 , 1 ), ( 3 , 3 )}

Find(a) R∪S, R∩S, RC; (b) R◦S; (c) S^2 =S◦S.

(a) TreatRandSsimply as sets, and take the usual intersection and union. ForRC, use the fact thatA×Ais the

universal relation onA.

R∩S={( 1 , 2 ), ( 3 , 3 )}

R∪S={( 1 , 1 ), ( 1 , 2 ), ( 1 , 3 ), ( 2 , 1 ), ( 2 , 3 ), ( 3 , 1 ), ( 3 , 3 )}

RC={( 1 , 3 ), ( 2 , 1 ), ( 2 , 2 ), ( 3 , 2 )}

(b) For each pair(a, b)∈R, find all pairs(b, c)∈S. Then(a, c)∈R◦S. For example,( 1 , 1 )∈Rand (1, 2),

( 1 , 3 )∈S; hence( 1 , 2 )and( 1 , 3 )belong toR◦S. Thus,

R◦S={( 1 , 2 ), ( 1 , 3 ), ( 1 , 1 ), ( 2 , 3 ), ( 3 , 2 ), ( 3 , 3 )}

(c) Following the algorithm in (b), we get

S^2 =S◦S={( 1 , 1 ), ( 1 , 3 ), ( 2 , 2 ), ( 2 , 3 ), ( 3 , 3 )}

2.8. Prove Theorem 2.1: LetA,B,CandDbe sets. SupposeRis a relation fromAtoB,Sis a relation fromBto
CandTis a relation fromCtoD. Then(R◦S)◦T=R◦(S◦T).
We need to show that each ordered pair in(R◦S)◦Tbelongs toR◦(S◦T), and vice versa.
Suppose(a, d)belongs to(R◦S)◦T. Then there existsc∈Csuch that(a, c)∈R◦Sand(c, d)∈T. Since(a, c)∈R◦S,
there existsb∈Bsuch that(a, b)∈Rand(b, c)∈S. Since(b, c)∈Sand(c, d)∈T, we have(b, d)∈S◦T; and
since(a, b)∈Rand(b, d)∈S◦T, we have(a, d)∈R◦(S◦T). Therefore,(R◦S)◦T ⊆R◦(S◦T). Similarly
R◦(S◦T)⊆(R◦S)◦T.Bothinclusion relations prove(R◦S)◦T=R◦(S◦T).