关系和关系图(ch4.doc

第四章 关系和关系图（ch4. Relations & Digraph）先修知识（Prerequisisites:) ：第一章&第二章要求：仔细阅读教材内容，做所有的例题，并且注意知识的前后连贯性及其内在的逻辑联系。要点：在前述集合论和数理逻辑的基础上，讨论集合上的个体成员间所具有的关系，并研究这些关系的性质以及在这些关系上可以进行的运算。（1） 掌握集合的笛卡儿积概念（2） 掌握关系的概念，注意和集合概念的联系（3） 掌握关系的各种表示方法（4） 掌握关系上的运算（*）（5） 掌握关系的性质（*）（6） 掌握典型二元关系：等价关系及其相关概念（*）难点：（1）关系的集合涵义（2）等价关系、等价类、划分及商集的概念及其间的联系（3）关系性质 n “关系”概念提出的理论基础集合的笛卡儿积4.1集合的笛卡儿积运算和集合上的划分（Products Sets & Partitions）一、 集合的笛卡儿积运算(Product Sets or Cartesian product)1、 有序对（序偶/二重组）（Ordered Pair）： 2、 n重组：=，an注：（1）有序性 （2）分量 （3）两n重组相等：= iff ai=bi3、 笛卡儿积的归纳定义：（1） AB=aA bB （2） A1A2An= (A1A2An-1) An (n2) =aiA 1in注：（1）A=(2) 运算性质：I. 不可交换 ABBAII. 不可结合 (AB)CA(BC)III. 在与上可分配 (AB)C(AC)(BC) (AB)C(AC)(BC) A(BC)(AB)(AC) A(BC)(AB)(AC) (3) A1A2AnA1A2AnAi：有限集合（ 1in） （证明略）练习：1、 设A=1，2，求P（A）A2、设A、B、C、D为任意集合，判断下列等式是否成立： （1）(AB)(CD)= (AC）（BD) （正确，利用集合相等涵义证明） （2）(AB)(CD) = (AC）（BD) （错误，特例反证） （3）(AB)(CD) = (AC）（BD) （错误，特例反证） （4）(AB)(CD) = (AC）（BD) （错误，特例反证）二、 集合上的划分（Partitions）1、 定义： 给定A P=A1，A2An 若有 （1）A= A1A2An（2）AiAj= 或 Ai=Aj （i ,j =1,2,，n),则P叫做集合A的一个划分 其中Ai称为划分P的块（blocks or cells)2、 例：（1）将一张纸撕成几片，则所得的各个碎片是该纸的一个划分（2）班集体划分： 按寝室划分；按男女同学划分；按年龄划分。 (3) 整数集合被划分成奇整数集合和偶整数集合。练习4.1 p1054.2 关系和二元关系图（Relations & Digraphs）一、 关系l 概念的引入： 集合+其上的成员关系 该集合所代表的事物结构例1、 A=甲、乙、丙、丁 （man集合）B=张、王、李、赵 （woman集合）C=小甲，小乙 （chile 集合）则家庭关系是 A BC 的某个子集例2、 一堆人的集合A，这些人之间有的有兄弟关系，朋友关系，师生关系，同学关系等等，则每一种关系确定了AA的某一个子集。例3、 电影票与座位见的“对号关系R”设X：电影票的集合，Y：座位集合则对于 必有：对号 或记作 xRyx和y 不对号 或记作 xRy (*)1、 二元关系的定义：R：AB的子集。 “A到B的二元关系”（relation R from A to B)若A=B，则称R为“A上的二元关系”（a relation on A) 推广：（1） n元关系：A1A2An （n1)的子集 A1A2An上的一个n元关系（2） A上的n元关系：AAA（n1) 的子集（*） 注： （1）关系是一个集合。所以关系的描述和运算均可采用集合中的方法来进（2） 关系相等涵义：n元组相等，即有序元对应相等（3） 关系个数： P(AB)（4） 对于任何集合A，都有下述三种特殊的关系： ：空关系 EA：全域关系：= AA IA：恒等关系： 推出 ：二元关系的一般定义： 若一个集合为空或它的元素都是有序对，则称这个集合是一个二元关系。2、关系的表示（定义）方法：（1） 集合表达a. 列举法：列出一个关系，如家庭关系b. 描述法（命题法）：使用谓词刻画其元素的共同属性。如： =x,y是实数且xy R=P(x,y)c. 归纳定义：如自然数集合上的小于关系d. 图示法：针对有限集合可有关系图法（有向图）例1A=0，1，2，则 EA=,IA= 例2AR (实数集），定义A上的“”关系： = x,yA xy例3AI+，定义A上的整除关系“”： =x,yA xy 例4“”关系： =A，B是集合且A是B的子集练习：设A=a，b，R是P（A）上的包含关系。求R。 关系导出的集合（Sets Arising from Relations）：1关系的域集合：设RAB ，则：R的前域：A R的陪域：BR的定义域 ：domR=x（R）R的值域：ranR=yx（R）R的域：fldR= domRranR（例略）2与前域相关的集合：（1）与前域元素相关的集合：（the R-relative of x)设RAB ， 则： R(x)= y xRy （2）与前域子集相关的集合：(the R-relative of A1)设RAB ，若A1A ，则有： R(A1)= y xRy for some x yin A1 (例略） 两个性质定理：th1： 设RAB，A1A，A2A 则有： （1）若A1A2，则有R（A1）R（A2）（证明略） （2）R（A1A2）= R（A1）R（A2）（证明略） （3）R（A1A2）R（A1）R（A2）证明（3）： 证毕。（2） 关系矩阵：（the Matrix of a Relation ） 设A= a1,a2,，am, B= b1,b2,，bn R为A到B的二元关系。定义MR= rij： 1 if aiRbj rij= 1im 1jn 0 if aiRbj则MR称为关系矩阵（mn阶）特别地：当A=B时，表示为A上的m阶方阵，即为A到A 的二元关系。例：A=1，2，3，4 R=, 则 1 1 0 0 MR = 0 0 1 1 0 0 0 0 0 1 0 0 行：原象集合。列：象集合（3） 关系图（the Digraph of a relation)设 V：顶点集合（vertices/vertex)E：边集（edge)令V=A= x1,x2,xn 对应元素的集合若xiRxj 则有向边 E则G=V，E就是R的关系图。（*）如上例可得：1 2 4 3 小结：关系的上述三种表示是等价的，并且可以相互转换。集合表示的方法揭示了关系的本质，矩阵表示适用于在计算机中去表示二元关系，二元关系图则比较形象直观地刻画了关系。练习：p114-115 4.3 二元关系图中的路径概念（Paths in Relations & Digraphs）一、 概念引入：例：驿站-路与路长例：设A=a,b,c,d,R=, 则得其关系图如下：（*） a b c d则从a到d的路径是一个有穷序列：S: a, b , a, ba, b ,c, d 即： aRb, bRa, aRb, aRb, bRc, cRd 注意：此序列中可出现重复点 从a到d的路长即为在关系图（有向图）中，体现上述关系序列的从a到d的有向边个数。注意：边可重复出现如上例，如有序列：a,b,a,b,c, 则表示从a到c的路长为4的一条有向路径，即： aRb, bRa, aRb, bRc 等边。 而序列a,b,a, 则表示从a到a的路长为2的一条有向路径，即aRb, bRa。二、 相关概念：1 回路（cycle)：有向路径的起点与终点相同。2 幂运算的定义及其在关系图中的意义：设R为A上的关系，nN, 定义：R0=IA= x ARn： 对R的关系图任一结点x考虑从x出发的长为n的路径，若路径终点y, 则Rn ，相应在Rn的有向图中，从x到y画一条有向边。如上例可有下述结果：R0=a,a,b,b,c,c,d,dR1=a,b,b,a,b,c,c,dR2=a,a,a,c,b,b,b,dR3=a,b,a,d,b,a,b,cR4=a,a,a,c,b,b,b,dR5=a,b,a,d,b,a,b,c有R2= R4= R6= R3= R5= R7=注：1、可以证明，对于有穷集A和A上的关系R，R的不同幂只有有限个（证明略）。2、可以看出，关系的幂运算其结果具有封闭性，仍为A上的二元关系。3、R的意义：对R的关系图中连通性（connectivity）的描述, 如R(x)描述的就是在R的关系图中，所有结点x所能到达的结点的集合。如上R=a,a,a,b,a,c,a,db,a,b,b,b,c,b,dc,d 即：x Ry iff xRy 或 x R2y 或 x R3y 则有： R=RR2R3Rn但是，当|R|很大的情况下，仍在关系图中去一一查找显然是不明智的，我们有另一种比较简便的方法使用关系矩阵。 幂运算的矩阵表达：th1 (p117)：设A=a1,a2,an RAA，则MR2=MRMR证明：设MR=mij，MR2=nij，由运算定义，iff mik=1 且 mkj=1 (1kn)时，即当有aiRak,和akRaj时，也即aiR2aj时，MRMR的第i行第j列位置值才为1，而此时也才有nij=1，即 nij=1 iff MRMR的第i行第j列位置值1。所以有MR2=MRMR（例略）th2(p118): 设|A|=n（n2)，RAA，则有：MRn=MRMRMR （n个因子）证明：采用归纳证明方法如下： 当n=2时,原命题即定理1。 假设当n=k时也成立上述论断，即有MRk=MRMRMR （k个因子） 设MRk+1=xij MRk=yij MR=mij 则如果xij=1，意味着有一条从ai到aj的路长为k+1，假设as是序列中与aj相邻的在其之前的点，则必有从ai到as的路长为k，而从as到aj的路长为1,所以有 yis=1且ysj=1，则MRkMR在第i行第j列位置值为1 同理可证如果MRkMR在第i行第j列位置值为1，也有xij=1 即当n=k+1时，MRk+1=MRkMR=(MRMRMR) MR =MRMRMR （k+1个因子) 所以对于所有的n2，都有MRn=MRMRMR （n个因子）成立。 另有结论（4.7节待证）（1）MRS=M RM s（2）MR=M RR2R3Rn =M RM R2M R3M Rn =M R（M R）2（M R）3（M R）n （可达矩阵）3、路径的合成：p1：a,x1 ,x2 xm-1,b (设路长为m) p2：b,y1 ,y2 yn-1,c (设路长为n) 则从a到c存在路p=p1p2 其路长为m+n 上述过程可表示为：Rm+n=RmRn 则由路径的合成可直接推出关系的合成 概念（4.7节细述）练习p120-1214.4 关系性质（Properties of Relations）本节主要讨论A上的二元关系R所具有的一些性质。一、 自反和反自反（Reflexive & Irreflexive Relations）1、 自反性（Reflexive）(1) 定义：(2) 关系矩阵特点：主对角线元素全是1(3) 关系图特点：图中每个顶点都有自回路。例：EA，IA，|，2、 反自反性（Irreflexive）（1） 定义：（2） 关系矩阵特点：主对角线元素全为0（3） 关系图特点：图中每个顶点都无自回路。 例： , 注：1）设，则A上的关系可以是自反的，也可以是反自反的，或者两者都不是；2）若，则其上的空关系既是自反的又是反自反的。 推论：1) R是自反的 iff 2) R是反自反的 iff 二、 对称、不对称和反对称（Symmetric,Asymmetric,and Antisymmetric Relations）1、 对称性（Symmetric）(1) 定义：(2) 关系矩阵特点：对称阵（关于主对角线对称）(3) 关系图特点：若两顶点间有边，一定是一对方向相反的有向边。例：= ， 2、 反对称性（Antisymmetric）（1） 定义： 即：（2） 关系矩阵特点：若 若（3） 关系图特点： 若两顶点间有边，一定是一条有向边；若有两边，即形成回路，则此两点必重合例：令A=1，2，3 ，则考虑下述关系的自反特性： R1=, 是自反的 R2=, 是反自反的 R3=, 既不是是自反也不是反自反 R4= 是反自反的 考虑下述关系的对称特性： R5=, 是对称的 R6=, 是反对称的 R7= 既是对称的又是反对称的 R8=, 既非对称也非反对称注：1）不管A是否为，其上空关系既是对称的又是反对称的。2）若R既是对称的，又是反对称的，则R三、 传递性（Transitive ）1、传递性：（1） 定义：（2） 关系矩阵特点：不体现传递性；（3） 关系图特点：若顶点x到顶点y有边，y到z有边，则从x到y 有边。 例： , ，= ，p126例10（略）2、 两个定理：th1：关系R具有传递特性当且仅当它满足下述条件：若从顶点a到b有一条长度大于1的路径，则由a到b有一条长度为的路径。 用代数观点去描述即为： R是传递的iff 对于所有的n1,有成立。（证明过程略） th2：设R是A上的二元关系，则有：（1） R是自反的意味着对于A中的任一个元素a有aR（a）（2） R是对称的意味着aR（b）iff bR（a）（3） R是传递的意味着如果bR（a）,且cR（b）,则有cR（a）(证明过程略）练习：p127-1284.5等价关系（Equivalence Relations）本节主要讨论一类典型二元关系等价关系及其相关性质。一等价关系：1定义：若集合A上的二元关系R是自反的，对称的，传递的，则R是等价关系。 若xRy 则可记作xy2等价关系的关系图特点：每一分图是完全图（1） 结点有自回路（2） 任两点间有两条不同方向的边的图形（3） 反映传递性蕴涵的边例：年龄上的相等关系反例：朋友关系特例：（1）空集合上的空关系是等价关系（2）全域关系（3）模数等价关系（*） 模k等价：设k 则a和b是模k等价(a is congruent to b mod k)，写成： 即a-b可以被k整除，k称为模数（modulus)。例4（P129) ：证明模2等价是一个等价关系。（证明略）例5（p129)：证明“模k等价”是任何集合A证明：（1）若A为空集，由特例（1）知其是等价关系 （2）若A不为空，则有： a. ，满足“自反性”。 b 满足“对称性” c. 满足“传递性”原命题得证。例：设A=1，2，8 R=|x,y 则x-y可以被3整除。则R为A上的一个等价关系。关系图为：（*）147 258 36另有：R（1）=1，4，7=R（4）=R（7） R（2）=2，5，8=R（5）=R（8） R（3）=3，6=R（6） 练习：整数集合上的模4等价（略）二、等价关系和划分（Equivalence Relations and Partitions) 1给定划分可确定一个等价关系： th1.(p129)：设P是非空集合A上的一个划分，定义A上的二元关系R如下： aRb iff 则R是A上的等价关系。 证明：R是自反的，因为A的每一元素是在P的某块B中，所以，对每一R是对称的，假设有aRb，则有某块BR是传递的，假设有aRb和bRc，则有某块B1 则有所以有aRc成立。综上，R是等价关系。称之为由划分诱导出的等价关系（equivalence relation determined by p)例：设A=1，2，3，4，有划分为P=1，2，34 由定理1可得等价关系R=, 同样有R（1）=R（2）=R（3）=1，2，3 R（4）=4下面我们证明A上的任一个等价关系都可以由某一个划分来诱导而出。2等价关系与划分的一一对应性：（1） 预备定理（lemma )：设R是A上的等价关系，并且设有,则有 aRb iff R(a)=R(b) 证明：必要性：假设R(a)=R(b)，则因为R是自反的，所以b 充分性： 假设aRb,则有i:) 由R具有对称性 必有：ii) a 则欲证R(a)=R(b) 对于即有bRx成立。因为R具有传递性，所以有aRx成立 即 所以，同理可证。 所以R(a)=R(b)(2)定理2：设R是非空集合A上的等价关系，P=，则P是A上R诱导的划分，而R就是由P诱导的等价关系。 （等价描述：设R是A上的等价关系，P是A的一个划分，则P诱导出R当且仅当R诱导出P。） 证明：必要性：假设P诱导出R，R诱导出P1设a是A的任一元素，并设B和B1分别是P和P1的块，使a，则对于任意b, 所以B=B1。又因为a是A的任一元素，而P和P1都是A的划分，所以P=P1。充分性：假设R诱导出P，P诱导出等价关系R1，则对于任意a,b 所以 R=R13 等价类（equivalence classes）（1）定义：R（a）=（2）等价类的表示元素： a（3）等价类的秩：R上不同等价类的个数 （即R关系图中，强分图的个数）（4）等价类特性：i：ii：若xRy,则R(x)=R(y)iii：若xRy,则iv：注：a.等价类的表示元可以是该类中的任一元素 b.集合上相等关系的秩等于|A|（因为A中元素具有互异性，仅存在自身与自身的相等）4 商集（quoitient sets of A)（1）定义：设R是非空集合A上的等价关系，则称划分或等价类的集合R(a)|a是A中任一元素为商集A/R ，也叫A模R。（2）定理：设R1和R2是非空集合A上的等价关系，则R1=R2 iff A/R1=A/R2 （证明留作练习） 如前例：设A=1，2，3，4，有划分为P=1，2，34 由定理1可得等价关系R=, 同样有R（1）=R（2）=R（3）=1，2，3 R（4）=4 而A/R=1，2，3，4 求A/R的一般步骤：（1） 选取A中任一元素a，计算R（a）（2） 如果R（a），则在A中选取不在R（a）中的任一元素b，计算R（b）（3） 如果A，则在A中选取不在R（a）和R(b）中的任一元素x，计算R（x）（4） 重复步骤（3），直至A中所有的元素都找到其归属的等价类小结： 诱导图示： 等价关系 划分 集合 商集 等价类4.6 关系和二元关系图在计算机中的表示(略）（Computer Representation of Relations & Digraphs）4.7 Operations on Relations（关系上的运算）本节主要介绍几种典型的关系关系（补、逆、合成、闭包）一、 关系上的运算：（1） 运算对象：关系（2） 运算：i： 例1（略） p140ii：求关系的域iii：求关系的幂、逆、合成、闭包（3） 结果：关系（4） 关系运算的方法： i：利用集合表示进行关系运算 （如p140-141例1） ii：利用关系图（如例3） iii：利用关系矩阵（如例4）二、 典型关系运算：A：关系的逆运算（inverse）（由对称性引入）（1） 定义：例：A=1，2，3 B=a,b R=, 则（2） 性质：设 则： i： ii： iii：定理3（P143）(预备定理） a).若R是对称的，当且仅当 R= b).R反对称，当且仅当证明a)： 证明b):（过程略）（3） 定理 （集合上的运算仍适用于关系）定理1（P142）：设R，R1，R2 证明 e) 关系性质在进行关系运算后的保持 定理2（P143） 设 则： 则：（定理3，P143） 证明：a) 如果R是自反的，显然有 所以R-1也是自反的。 b)和c)的证明过程略。 定理4：（P144） a).如果R是对称的，则 b) 如果R和S是对称的,则 证明：a).如果R是对称的，则由前述预备定理，有 所以也是对称的。 如果R是对称的，则b)证明过程略。例6（P144）略。定理5 （P144） 设R，S是A上的二元关系，则有：a). b). 如果R，S都是传递的，则也是传递的c). 如果R，S是等价关系，则也是等价关系。证明：a) 采用几何的方法去证明： ab iff 在关系中从a到b有一条路径长度为2 这条路径所涉及的边都是既在R也在S的关系图中出现。 所以aR2b，aS2b 。即有a()bb) c)证明过程略。 例7（P144）（对c的说明）略。B合成运算（composition）(1) 定义：R：A到B的关系，S：B到C的关系 例：定义R是父子关系，S是父女关系若有， 则：祖孙关系。l 合成运算的顺序（定理6 P146） （证明略）l 关系幂运算的合成意义：Rn+1=RRn相关定理：（1） RmRn=Rm+n(2) (Rm)n=Rmn 证明过程略。（2）运算性质及证明。 I II III分配性： IV不可交换性： V可结合性： 证V：设R：A到B的二元关系；S：B到C的二元关系；T：C到D的二元关系VI 合成关系的逆：（定理8 P148） 设A，B，C为任意的集合， 则有： 证明：（3）表达方法：集合形式依据定义II. 关系矩阵(布尔矩阵boolean matrix) （证明过程略） MR MS: （*） Cij=i=1,2,，m j=1,2,，p例1：A=1，2 B=x,y C=m,n R=, S=,则I：=, II： （*）注：对应合成运算的结合性，关系矩阵的乘法运算也是可结合的证明：III关系图 1x m 2 y nC闭包（Closures） 思考：为什么要引入关系的闭包运算？ -注意:关系性质,指在论域中普遍存在的特性,闭包,一方面讨论的是具有某类性质的关系,另一方面讨论的是具有这类性质的最小的关系集合. 例：设A=1，2，3，R=,求含R在内的元素个数最少的具有自反（对称/传递）性的关系R。 解：1）自反R=, 2) 对称R=, 3) 传递R= (1) 定义：设R，若，满足： I IIR是自反的（对称的/传递的） III若，且满足： a. b. R是自反的（对称的/传递的） c. 称R为R的自反（对称/传递）闭包 记作r(R) (s(R) / t(R) 注：1）给定R，R总能唯一确定闭包唯一 证明：设R1,R2均满足定义，则有 所以 R1=R2 2) 构造方法： 法I由R构造R,添加必要的序偶，使其具有所希望的性质。（但若R本身具有自反（对称/传递）性，则R=R。 法II. 关系图： 求自反闭包：在R的关系图上使得每个结点都有自回路 求对称闭包：使原图中的有向边成为双向。 求传递闭包：若两点间有路径长度1,则在两点间联一有向边,方向与路径方向相同. 如上例(图略)(2) 闭包性质：定理：设，则）自反