北京郵電大學(xué)計(jì)算機(jī)學(xué)院離散數(shù)學(xué)9.1~9.3-relations

1、Yang JCollege of Computer Science & TechnologyBeijing University of Posts & TelecommunicationsRelations22021-10-16College of Computer Science & Technology, BUPT 9 Relationsn9.1 Relations and Their Properties關(guān)系及關(guān)系性質(zhì)n9.2 n-ary Relations and Their Applications n元關(guān)系及應(yīng)用n9.3 Representing Relations 關(guān)系的表示n9

2、.4 Closures of Relations 關(guān)系閉包n9.5 Equivalence Relations 等價(jià)關(guān)系n9.6 Partial Orderings 偏序關(guān)系Yang JCollege of Computer Science & TechnologyBeijing University of Posts & TelecommunicationsRelations and their properties42021-10-16College of Computer Science & Technology, BUPT Ordered pair(序偶)nAn ordered pai

3、r (a, b) is a listing of the objects a and b in a prescribed order, with a appearing first and b appearing second. nThe ordered pairs (a1, b1) = (a2, b2) nif and only if na1 = a2 and b1 = b252021-10-16College of Computer Science & Technology, BUPT Cartesian product(笛卡爾積)nIf A and B are two nonempty

4、sets, we define the product set or Cartesian product A B as the set of all ordered pairs (a, b) with a A and b BnA B = (a, b) | a A and b B62021-10-16College of Computer Science & Technology, BUPT A1 A2 AmnThe Cartesian product A1 A2 Am of the nonempty sets A1, A2, , Am is the set of all ordered m-t

5、uples (m元組) (al, a2, . , am), where ai Ai, i = 1, 2, . . . , mnThusnA1 A2 Am = (al, a2, . , am) | ai Ai, i = 1, 2, . . . , m.72021-10-16College of Computer Science & Technology, BUPT PartitionsnA partition(劃分) or quotient set(商集) of a nonempty set A is a collection P of nonempty subsets of A such th

6、atnEach element of A belongs to one of the sets in PnIf A1 and A2 are distinct elements of P, then A1 A2 = nThe sets in P are called the blocks or cells of the partition.82021-10-16College of Computer Science & Technology, BUPT ExamplenLet A = a, b, c, d, e, f, g, h. nConsider the following subsets

7、of AnA1 = a, b, c, dnA2 = a, c, e, f, g, h nA3 = a, c, e, gnA4 = b, dnA5 = f, h92021-10-16College of Computer Science & Technology, BUPT RelationsnThe notion of a relation between two sets of objects is quite common and intuitively clearnExamplesnx is the father of ynx ynA relation is often describe

8、d verbally and may be denoted by a familiar name or symbol.102021-10-16College of Computer Science & Technology, BUPT RelationsnDiscuss any possible relation from one abstract set to another.nThe only thing that really matters about a relation is that we know precisely which elements in A are relate

9、d to which elements in B112021-10-16College of Computer Science & Technology, BUPT DefinitionnLet A and B be nonempty sets. A relation R from A to B is a subset of A B. nIf R A B and (a, b) R, we say that a is related to b by R, and we also write a R b. nIf a is not related to b by R, we write a R b

10、.nFrequently, A and B are equal. In this case, we often say that R A A is a relation on A.122021-10-16College of Computer Science & Technology, BUPT ExamplesnLet A = 1, 2, 3 and B = r, s. Then R = (1, r), (2, s), (3, r) is a relation from A to B.nLet A and B be sets of real numbers. We define the fo

11、llowing relation R (equals) from A to B:na R b if and only if a =bnLet A = 1, 2, 3, 4, 5. Define the following relation R (less than) on A:na R b if and only if a bnR = (1,2), (1, 3), (1,4), (1,5), (2, 3), (2. 4), (2, 5), (3,4), (3, 5), (4,5)132021-10-16College of Computer Science & Technology, BUPT

12、 ExamplenLet A = R, the set of real numbers. Define the following relation R on A:nx R y nif and only if nx2/4 + y2/9 = lnThe set R consists of all points on the ellipse shown in Figure142021-10-16College of Computer Science & Technology, BUPT Sets Arising from RelationsnLet R A B be a relation from

13、 A to B. nDom(R), the domain of R is a subset of A, is the set of all first elements in the pairs that make up R.nRan(R), the range of R is the set of elements in B that are second elements of pairs in R.152021-10-16College of Computer Science & Technology, BUPT Sets Arising from RelationsnIf R is a

14、 relation from A to B and x A.nDefine R(x), the R-relative set of x, to be the set of all y in B with the property that x is R-related to y.nR(x) = y B | x R y.nSimilarly, if A1 A, then R(A1), the R-relative set of A1, is the set of all y in B with the property that x is R-related to y for some x in

15、 A1.nR(A1) = y B | x R y for some x in A1162021-10-16College of Computer Science & Technology, BUPT Theorem nLet R be a relation from A to B, and let A1 and A2 be subsets of A. Thenn(a) If A1 A2, then R(A1) R(A2)n(b) R(A1 A2) = R(A1) R(A2)n(c) R(A1 A2) R(A1) R(A2)172021-10-16College of Computer Scie

16、nce & Technology, BUPT Proof of If A1 A2 then R(A1) R(A2)nIf y R(A1), then x R y for some x A1. nSince A1 A2, x A2.nThusny R(A2)nwhich proves part (a).182021-10-16College of Computer Science & Technology, BUPT Proof of R(A1 A2) = R(A1) R(A2)nIf y R(A1 A2), then by definition x R y for some x in A1 A

17、2. nIf x is in A1, then, since x R y, we must have y R(A1).nBy the same argument, if x is in A2, then y R(A2).nIn either case, y R(A1) R(A2). nThus R(A1 A2) R(A1) R(A2).nConversely, nsince A1 (A1A2), part (a) tells us that R(A1) R(A1A2). nSimilarly, R(A2) R(A1A2). nThus R(A1) R(A2) R(A1 A2), and the

18、refore part (b) is true.192021-10-16College of Computer Science & Technology, BUPT Proof of R(A1 A2) R(A1) R(A2)nIf y R(A1 A2), then, for some x in A1 A2, x R y. nSince x is in both A1 and A2, it follows that y is in both R(A1) and R(A2); ny R(A1) R(A2). nThus part (c) holds.nQEDnWhy “” instead of “

19、=”?202021-10-16College of Computer Science & Technology, BUPT RemarknThe strategy of this proof is one we have seen many times in earlier sections:nApply a relevant definition to a generic object.212021-10-16College of Computer Science & Technology, BUPT ExamplenLet A = Z, R be “”, A1 = 0, 1, 2, and

20、 A2 = 9, 13. Then nR(A1) consists of all integers n such that 0 n, or 1 n, or 2 n. Thus R(A1) = 0, l, 2, .nSimilarly, R(A2) = 9, 10, 11, .nSo R(A1) R(A2) = 9, 10, 11, .nOn the other hand, A1 A2 = ; thus R(A1 A2) = nThis shows that the containment in theorem 1(c) is not always an equality.222021-10-1

21、6College of Computer Science & Technology, BUPT Theorem nLet R and S be relations from A to B.nIf R(a) = S(a) for all a in A, nthen R = SnProofnIf a R b, then b R(a). Therefore, b S(a) and a S b. nA completely similar argument shows that, if a S b, then a R b. nThus R = S.nQED232021-10-16College of

22、Computer Science & Technology, BUPT Special Properties of Binary RelationsnGiven:nA Universe UnA binary relation R on a subset A of UnSpecial Properties:nReflexive and Irreflexive（自反、反自反）nSymmetric, Asymmetric, and Antisymmetric（對(duì)稱、非對(duì)稱、反對(duì)稱）nTransitive（傳遞）242021-10-16College of Computer Science & Tec

23、hnology, BUPT Definition: renR is reflexive iffnxx A ( x, x )RnNote: nif A = then the implication is true vacuouslynThe void relation on a void Universe is reflexive!nIf U is not void then all vertices in a reflexive relation must have loops!252021-10-16College of Computer Science & Technology, BUPT

24、 Definition : irnR is irreflexive iffnxx A ( x, x ) RnNote: nif A = then the implication is true vacuouslynAny void relation is irreflexive!262021-10-16College of Computer Science & Technology, BUPT ExamplesbcdabcdabcdanRenNot IrnNot RenIrnNot RenNot Ir272021-10-16College of Computer Science & Techn

25、ology, BUPT Definition: SynR is symmetric iffnxy( x, y ) R (y, x ) RnNote: nIf there is an arc ( x, y ) there must be an arc ( y, x )282021-10-16College of Computer Science & Technology, BUPT Definition: AsnR is Asymmetric iffnxy( x, y )R( y, x ) RnNote: nIf there is an arc ( x, y ) there must not b

26、e an arc ( y, x )292021-10-16College of Computer Science & Technology, BUPT Definition: AtsnR is antisymmetric iffnxy(x, y)R ( y, x )R x = ynNote: nIf there is an arc from x to y there cannot be one from y to x if x y.nYou should be able to show that logically: if (x, y) is in R and x y then (y, x)

27、is not in R.302021-10-16College of Computer Science & Technology, BUPT ExamplesnSynNot AsnNot AtsbcdabcdabcdabcdanNot SynAsnAtsnNot SynNot AsnAtsnNot SynNot AsnNot AtsWhat about other 4 cases?312021-10-16College of Computer Science & Technology, BUPT Definition: trnR is transitive iffnxyz( x, y ) R

28、( y, z ) R ( x, z ) RnNote: nif there is an arc from x to y and one from y to z then there must be one from x to z.322021-10-16College of Computer Science & Technology, BUPT ExamplesbcdabcdanTrnNot Tr332021-10-16College of Computer Science & Technology, BUPT Examples in Mathematicsn= (equality)n (in

29、equality)n (empty relation)342021-10-16College of Computer Science & Technology, BUPT nExample 15nIs the “divides” relation on the set of positive integers transitive?nExample 16nHow many reflexive relations are there on a set with n elements?352021-10-16College of Computer Science & Technology, BUP

30、T Combing relationsnR2 R1nR2 R1nR2 - R1nR2 R1nR1nExample 17-19362021-10-16College of Computer Science & Technology, BUPT CompositionnNow supposenA, B, and C are sets, nR is a relation from A to B, and nS is a relation from B to C. nThe composition of R and S, written as SR, is a relation from A to C

31、 and defined as: if a is in A and c is in C, thenna SR cnif and only ifnfor some b in B, a R b and b S c.372021-10-16College of Computer Science & Technology, BUPT Example nLetnA=1, 2, 3, 4nR=(1, 1), (1, 2), (1, 3), (2, 4), (3, 2)nS=(1, 4), (1, 3), (2, 3), (3, 1), (4, 1)nThennSR=(1, 4), (1, 3), (1,

32、1), (2, 1), (3, 3)382021-10-16College of Computer Science & Technology, BUPT Theorem nLet R be a relation from A to B and let S be a relation from B to C. Then, if A1 is a subset of A, we have(SR)(A1) = S(R(A1)392021-10-16College of Computer Science & Technology, BUPT Proof of (SR)(A1) = S(R(A1)1111

33、1111(),( , ),( , )( , ),(,( , )( , ),()( , )( ()()()( ()cS R AaAa cS RaAbB a bRb cSbBaAa bRb cSbB bR Ab cScS R AS R AS R A =402021-10-16College of Computer Science & Technology, BUPT nLet R be a relation on the set A. The power Rn,n=1,2,3 are defined recursively by R1=R and Rn+1=Rn。RnExample 2241202

34、1-10-16College of Computer Science & Technology, BUPT Theorem 1nThe relation R on a set A is transitive if and only if Rn R for n=1,2,3422021-10-16College of Computer Science & Technology, BUPT Homeworkn9.1 n40, 47, 48432021-10-16College of Computer Science & Technology, BUPT 9.2: n-ary RelationsnAn

35、 n-ary relation R on sets A1,An, written (with signature) R:A1An or R:A1,An, is simply a subset R A1 An.nThe sets Ai are called the domains of R.nThe degree of R is n.nR is functional in the domain Ai if it contains at most one n-tuple (, ai ,) for any value ai within domain Ai.442021-10-16College o

36、f Computer Science & Technology, BUPT Example 12 P530nLet R be the relation on consisting of triples (a, b, c), where a, b, and c are integers with a b 0.852021-10-16College of Computer Science & Technology, BUPT Proof: R transitive Rn RnUse a direct proof and a proof by induction:nAssume R is transitive.nNow show Rn R by induction.nBasis: Obviously true for n = 1.nInduction:nThe induction hypothesis:nassume theorem is true for n.nShow it must be true for n + 1862021-10-16College of Computer Science & Technology, BUPT Proof: