2014.7.3 二元关系.ppt

1,The fourth chapter binary relation,Relationship：Relationships of people have friends relationship,parent-child relationships, parent-child relationships, classmates. There are greater than, less than, equal to relations, and divisible, congruence relations between two figures. Two variables, such as function relationship.Relationship of mathematical concept is to establish the concept of relationships in daily life.,2,eg suppose set A=a,b,c,d is made up from male team membersone of one table-tennis team. Set B=e,f,g is made up from female team membersone . If there are mixed doubles match relationship between A and B ,stant for a and g，d and e。so can be expressed as： R=，“R” is stant for the sequence pair set which is have mixed doubles match relationship.All the sequence pair set that may have the mixed doubles match relationship are: A×B=|xAyB =，,3,There are people A，B，C,and four operating post,. A can take up workand ，Bcan take up work ，C can take up work and。So, the relatioship of people and work can be expressed as: R=, This is the relationship between setA,B,C and set,.,4,4.1 Relationship and its representation,一、Definition of relationship(1) The subset of A×B can be seen as a binary relation A to B.(2) The subset of A1×A2××An(n1) can be seen as a n-ary relation about A1×A2××An.,(3)The subset of can be seen as a n-ary relation about A.From the concept can know relationship is a set.The methodused to definit set is appropriate for relationship.,5,For example,the binary relation about real number R can be definit as follow: =|xRyRxyThe most important is binary relation.This chapter mainly discuss the binary relation，The term "relationship" refers to the binary relation.Binary relations have their own special notation and several new terms.Otherwise will be noted especially.,6,suppose set A=x1,x2,x7， B=y1,y2,y6 R=，obvious R，can be wright as x3Ry1，also called infix notation：x3 and y1 have the relation R.infix notation used to expressed the relationship of “=”，“”，“”and so on，for example ，can be wright as 35.A can be seen as the former domain of relationship R，B can be seen as codomain of the relationship R. D(R)=x|y(R) can be seen as domain of definition of relationship R. R(R)=y|x(R)can be seen as range of relationship R.,7,Relationship is a set of ordered pair,and can be operat as well as set.The result definit a new relationship.Suppose R and S are two binary relation about the given set.Then RS、RS、R-S，R can be definited as follow: x(RS)y xRyxSy x(RS)y xRyxSy x(R-S)y xRyx$y x(R)y x R y,8,Thought：if |A|=m，|B|=n ，how many relationship exist from A to B？,solve：Due to the relation is a subset of AB.So the subset of AB are 2mn, according to the conclusion of the number of power set.So ，there are 2mn relations from A to B.specially ，when A=B，then there are 2n2 relations about A.,9,二、Some special relations For arbitrary set A there are three kinds of special relationships: empty relation、Global relationshipUA和 identity relation A.Definition：For arbitrary set A,there are three special subset about AA:(1) is a subset of AA，from the definition of on A，called the empty relation on A.(2) AA itself is a subset AA，from the definition of AAabout A,called Global relationship about A. denote as UA, UA=aAbA(3)A=aA was called identity relation about A.,10,eg suppose setA=0,1,2，then：UA=,Due to UAis global relations upon A, obvious UA=A×A=9 A=,If is A identity relation upon A,then A=A=3,11,三、Example for commonly relationeg1 Less than or equal to relationship.A=1,2,3，definition the relation upon A LA=a,bAab。then LA =,eg2 Aliquot relationship.suppose set B=1,2,3,4,5,6，definition the binary relation upon B DB= a,bBbaN.then：DB=,，,attention：baN,in other word is "a can exact division b",or " b can be exacted division by a".,12,eg3 congruence relation A=1,2,3,4，the binary relation upon set A is: R=( a-b)/2Za,bA。then R=, Description：The relation is called “module2 congruence relation”，denoted a=b(mod2).,13,eg 4 inclusion relation suppose set A，define R is a relation upon (A), R=u(A)，v(A)，and uv。eg，suppose set A=a,b, (A)= ,a,b,A，thenR=，,14,eg 5 suppose set A=2,3,4,5,6，Express the following relationship with enumeration method：R=a is the integer times of bR=(a-b)2AR=a/b is prime number R=ab R=a,b coprime numbers,15,solve ： because set A=2,3,4,5,6，R=a is the integer times of b。R=， R=(a-b)2A。R=， R=a/b is prime number。R=， R=ab。R=EA-A，there are 25-5 ordered pairs. R=a,b coprime numbersR=，,，,16,四、Representation of the relation The relation that have been arisen previous are defined with the definition of set. We can express the binary relation of finite set with matrix of relation and relation diagrams.Definition: suppose set A=a1, ,am，B=b1,bnR is a relation of A to B，then the matrix of relation of R is a mn-matrix MR=(rij)mn rij =1，when R rij =0，when Rif R is a relation upon set A, then the matrix of relation is a square matrix,17,eg set A=a,b,c,d， B=x,y,z， R=, Due to |A|=4，|B|=3, then MR is 4×3 matrix： eg A=2,3,4,5,6，then the matrix of relation of R1=|a is the integer times of b is ：,18,Related description： All of the elements of the matrix of relation M of empty relation are 0. All of the elements of the matrix of relation MU of global relationship UA are 1. All the diagonal elements of matrix of relation MI of identity relation A are 1, undiagonal elements are 0 .The matrix is called unit matrix in linear algebra, and denoted .,19,Definition suppose set A=a1,am，B=b1,bn，(AB) R is a relation of A to B，the amounts of circle is m+n, respectively represent a1,am and b1,bn(On both sides respectively)，the circles are called knot.If R,then connect a directed edge (arc)from ai to bj , if R，then do not connect the corresponding edge (arc).This graph is called relational graph of relation R. If R is a relation upon A, then only make m circles represent a1,am,(Dot not make 2m circles,and No longer on both sides respectively ) directed edge (arc),the mathod is same as the ，if R，then make a directed arc from ai to ai，this arc is called self-contained loop.,20,eg 1 A=a,b,c,d， B=x,y,z， R=, The following is relational graph of relation R.,21,eg2 suppose setA=1,2,3,4，R=, is a relation upon A.Then the matrix of relation and relational graph of R :In the relational graph, the vertices is 1,2,3,4 ，From ,R can know，there is an edge from 1 to 1 in the graph ,(the loopthrough 1a ring)，There is one edge from 1 to 2. The others edges of ordered pairs can be made similarly.,22,eg3 suppsose set A=2,3,4,5,6，draw up the matrix of relation and relational graph of the following relation: R=A multiple of a is b.R=(a-b)2A.R=a/b is prime number.R=a,brelatively prime numbers,23,一、The synthesis of relationCited examples：people a,b,c，a,b brother and sister ，b,c are mother-child relationship,then a,c are uncles and nephews relations.If R represents brother and sister relation，S represents mother-child relationship，T is uncles and nephews relations which synthesis of R and S.If R represents set membership，synthesis of R and R is grandparenthood.,4.2 he operation of relation,24,（1）Definition of synthesis of relation Definition: suppose sets A,B,C，R is the relation of A to B，S is the relation of B to C，then the synthesis of relation of R and S is a relation of A to C,denoted RS.definition：R S=xAzCyB，then R,S,25,Instructions of definition: The necessary condition of synthesis for R and S is the range of R and the definition of S constitute a same set B. The definition of synthesis for : there is an element y acted as middle bridge at lest, then, there is a relation R for x and y and S for y and z. eg1 A=1,2,3,4,5，B=3,4,5，C=1,2,3 suppose R=|x+y=6=,，then R is a relation for A to B. suppose S=y-z=2 =, ，then S is a relation for B to C.,26,searching in ordered pair of the two relations： R,S,RS R,S,R S R,S,R Swhile ,RS=,Can be derived mathematically: x+y=6，y-z=2， cancellat y then x+z=4,27,3,relational graph: A B C,1,2,4,3,4,5,1,2,3,5,3,1,2,4,5,1,2,3,then then relational graph of RS,28,eg2 set A=a,b,c,d,e，the relation of R、S upon A: R=,，S=, then：R S=, S R= , R R=, S S=from the example we can know:R SS R,29,Instructions of definition： commutative law is not suitable for the operation of synthesis of relation  R is a relation of A to B，S is a relation of B to C，RS have definition but can not been synthesized at all. if A=C，then RS is a relation upin A，SR is a relation upon B，It is impossible equivalent for both relation. if A=B=C，R、S are relations upon A，RS and S R are relations upon A also，so we can obtain R SS R from the above example in generally.,30,（2）matrix of relation of compositive relationTheorem : suppose sets A=a1,am，B=b1,bn，C=C1, CP R is a relation of A to B，matrix of relation MR is m×n-matrix. S is a relation of B to C，matrix of relation MS is n×p-matrix.compositive relation R S of A to C，its matrix of relationMR S is m×p-matrix, then MR S=MR×MS Attention:× is matrix multiplication by the Boolean operation.,31,eg suppose sets A=a,b,c,d，R=,， 0S=, MR= MS= then，MR S= MR ×MS = 而 MS R= MS×M R = verification：R S=, S R=,eg suppose sets A=a,b,c,d，R=,， 0S=,32,（3）The properties of composition relation compositional operation for distributive law of ,Theorem: suppose is R a relation of A to B，S and T are relation of B to C . U is a relation of C to Dthen (1). R(ST)=R SR T； (2). R(ST) R SR T； (3). (ST) U=S UT U； (4). (ST) U S UT U；,33,prove：(1)R (ST) yB，then RST y( R(ST) y(RS) y(RT) R SR T) R SR Tso： R SR T= R (ST),34, compositional operation conform to associative lawTheorem: suppose R，S，T are relations of A to B，B to C and C to D， then (R S) T = R (S T)。,35,prove： (R S) T zC，then R ST yB，then RST RS T R (S T) (R S) TR (S T） similarly，R (S T)( R S) T so (R S) T = R (S T),36,（4）The power of relationDefinition: suppose R is a binary relation upon A上，nN，then the definition of n th power operation Rn of R ： (1). R0 =A is identity relation upon A，R0=|xA； (2). Rn+1=Rn R Introductions：If R is a relation of A to B，and AB，R2 is without meaning obvious.Because R R cannot be composite.,37,Theorem: suppose R is a relation upon set A，m,nN，then （1） Rm Rn=Rm+n (The first exponential law）（2）(Rm)n=Rmn (The second exponential law）The theorem can be proved with mathematical induction,prove：(1)For any mN。 if n=0，then,So for all m,nN： Rm RnRm+n。,Rm R0,Rm,Rm+0,supposeRm Rk=Rm+k，then,Rm Rk+1,Rm (Rk R),(Rm Rk) R,Rm+k+1，,Rm IA,38,Attention:Generally speaking,The third exponential law is false. so (R S)nRn Sn eg (R S)2=(R S) (R S)=R (S R) S while R2 S2=R R S S=R (R S) Sobvious ，The third exponential law is false when the commutative law is false.,39,eg suppose A=1,2,3,4,5，R is a relation upon A R=，.then different power operation of R :R0 =A =，R1=RR2=，R3=R2 R=，R4= R3 R1=，R5=R4 R1=，,40,n-th power operation of relation from relational graph R： R2： R2 is a path of the length is 2, which set out from any knot of the relational graph，if the terminal point of the path is y，then there is a directed edge from x to y in the relational graph.Other etc:,R3：,R4：,41,Theorem:suppose |A|=n，R A×A，certainly i，jN ,0ij2n2，使得Ri=Rj。,so, there are differet binary relation upon A,while there are +1 binary relation R0、R1、R2、 upon A Therefore, there are at least two of these power is equal,prove：because A×A|=n2，(A×A)=,42,Theorem: suppose set A，R A×A，if i，jN，ij， Ri=Rj，then . for any kN，Ri+k=Rj+k; . for any k,mN，Ri+md+k=Ri+k(d=j-i); . for any nN， Rn R0,R1,Rj-1;,prove： (1) Ri+kRi RkRj RkRj+k,(2)Induction m.if m=0，then Ri+0*d+kRi+k suppose ,Ri+nd+kRi+k，dj-i，when m=n+1，then,Ri+(n+1)d+k,Ri+nd+d+k,Ri+k Rd=Ri+k+d,Ri+k+j-i,Rk+j,Rk+i,Proposition by induction card,Ri+nd+k Rd,43,conclusion When calculating the power of relationship, if j-th power operation of R is different from i-th power operation that have obtained previous, then the process that calculate the power operation of relations upon finite set would be stop, that is to say power of all the natural numbers.Given the relationship R upon A and natural number n，then how to calculate Rn？The method is shown below：,44,if R is expressed by set expression, Rn can be obtained by the n-1 compositional operation. if R is expressed by matrix of relation M, then matrix of relation of Rn is Mn, the product of n matrixes M. that：Mn=M×M××M if R is expressed by relational graph G，relational graph G of Rn can be elicited by graph G.The vertex set of G is same with G. Inspects each vertex x of G , if set from xi to xj across n step size in G, then add an edga in G from xi to xj .Graph G is obtained when all these edgas is found.,45,eg：suppose Aa,b,c,d，R,，calculate all the power of all the natural numbers. (Represented by relation matrix),solve：,46,Due to M4=M2，so the set of power of all the natural numbers is ：R0，R1，R2，R3。,47,三、the inverse operation of relationshipDefinition: suppose R is a binary-relation of A to B，then define a binary-relation R-1=|R，from A to B,called inverse relation of R，markR-1 . Introductions：（1）R-1 is made up from ordered pair that the elements have been exchanged order of R, so |R|=| R-1|；（2）matrix of relation of R-1 is transposition of matrix of relation R，that is ： M R-1=MR（3）relational graph of R-1 can be obtained by changing the direction of edga on the right side (arc) of the relational graph R .,48,eg suppose set A=a,b,c,d，the relation R upon Ais :R=，then:R-1=，,