离散数学-第七章-二元关系

1漳州师范学院计算机科学与工程系第七章二元关系2第七章二元关系有序对与笛卡儿积二元关系关系的运算关系的性质关系的闭包等价关系与划分偏序关系3第七章二元关系知识点：序偶与笛卡尔积、关系及表示、关系的性质、复合关系和逆关系、关系的闭包运算、集合的划分、等价关系与等价类、偏序关系教学要求：深刻理解和掌握关系的基本概念和基本运算教学重点：关系及关系的运算、等价关系、偏序关系学时:1247.1有序对与笛卡儿积定义7.1由两个元素x和y（允许x=y）按一定顺序排列成的二元组叫做一个有序对(orderedpair)或序偶，记作x,y，其中x是它的第一元素，y是它的第二元素。有序对x,y具有以下性质：（1）当x≠y时，x,y≠y,x。（2）x,y＝u,v的充分必要条件是x＝u且y＝v。说明有序对中的元素是有序的集合中的元素是无序的5例7.1例7.1已知x+2，4＝5，2x+y，求x和y。由有序对相等的充要条件有x+2＝52x+y＝4解得x＝3,y＝-2。解答6定义7.2设A，B为集合,用A中元素为第一元素，B中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做A和B的笛卡儿积(Cartesianproduct)，记作A×B。笛卡儿积的符号化表示为A×B＝{x,y|x∈A∧y∈B}笛卡儿积的定义A表示某大学所有学生的集合，B表示大学开设的所有课程的集合，则A×B可以用来表示该校学生选课的所有可能情况。令A是直角坐标系中x轴上的点集，B是直角坐标系中y轴上的点集，于是A×B就和平面点集一一对应。举例7笛卡尔积举例设A={a,b},B={0,1,2}，则A×B={a,0,a,1,a,2,b,0,b,1,b,2}B×A={0,a,0,b,1,a,1,b,2,a,2,b}举例说明如果|A|=m,|B|=n,则|A×B|=mn。设A={x|0x2},B={y|0y1},则AB={x,y|0x2且0y1}举例O12ABxy8笛卡儿积的运算性质(1)对任意集合A，根据定义有A×＝,×A＝(2)一般的说，笛卡儿积运算不满足交换律，即A×B≠B×A(当A≠∧B≠∧A≠B时)(3)笛卡儿积运算不满足结合律，即(A×B)×C≠A×(B×C)(当A≠∧B≠∧C≠时)(4)笛卡儿积运算对并和交运算满足分配律，即A×(B∪C)=(A×B)∪(A×C)(B∪C)×A=(B×A)∪(C×A)A×(B∩C)=(A×B)∩(A×C)(B∩C)×A=(B×A)∩(C×A)(5)AC∧BDA×BC×D9A×(B∪C)=(A×B)∪(A×C)的证明任取x,yx,y∈A×(B∪C)x∈A∧y∈B∪Cx∈A∧(y∈B∨y∈C)(x∈A∧y∈B)∨(x∈A∧y∈C)x,y∈A×B∨x,y∈A×Cx,y∈(A×B)∪(A×C)所以A×(B∪C)=(A×B)∪(A×C)10关于A×BC×DAC∧BD的讨论该性质的逆命题不成立，可分以下情况讨论。（1）当A=B=时，显然有AC和BD成立。（2）当A≠且B≠时，也有AC和BD成立，证明如下：任取x∈A，由于B≠,必存在y∈B,因此有x∈A∧y∈Bx,y∈A×Bx,y∈C×Dx∈C∧y∈Dx∈C从而证明了AC。同理可证BD。11关于A×BC×DAC∧BD的讨论（3）当A＝而B≠时，有AC成立，但不一定有BD成立。反例：令A＝,B＝{1},C＝{3},D＝{4}。（4）当A≠而B＝时，有BD成立，但不一定有AC成立。反例略。12例7.2例7.2设A={1,2},求P(A)×A。P(A)×A＝{,{1},{2},{1,2}}×{1,2}＝{,1,,2,{1},1,{1},2,{2},1,{2},2,{1,2},1,{1,2},2}解答13例7.3例7.3设A，B，C，D为任意集合，判断以下命题是否为真，并说明理由。(1)A×B＝A×CB＝C(2)A-(B×C)＝(A-B)×(A-C)(3)A＝B∧C＝DA×C＝B×D(4)存在集合A，使得A⊆A×A(1)不一定为真。当A＝，B＝{1},C＝{2}时，有A×B＝＝A×C，但B≠C。(2)不一定为真。当A=B={1},C＝{2}时，有A-(B×C)＝{1}–{1,2}＝{1}(A-B)×(A-C)＝×{1}＝(3)为真。由等量代入的原理可证。(4)为真。当A＝时，有A⊆A×A成立。解答14§7.2二元关系A={a,b,c}表示一个班级,B={1,2,3,4}表示开设的课程a选修课程1,3b选修课程1,3,4c选修课程2,4如何用集合表示学生和课程的关系?R={a,1,a,3,b,1,b,3,b,4,c,2,c,4}S={1,a,1,b,2,c,3,a,3,b,4,b,4,c}R中的元素表示某个学生选修了某门课S中的元素表示某门课被某个学生所选修RAB,SBA两个集合的笛卡尔集的子集可以表示这两个集合中元素之间的某种关系®157.2二元关系(binaryrelation)定义7.3如果一个集合满足以下条件之一：（1）集合非空，且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系，记作R。二元关系也可简称为关系。对于二元关系R，如果x,y∈R，可记作xRy；如果x,yR，则记作xRy。设R1＝{1,2,a,b}，R2＝{1,2,a,b}。则R1是二元关系，R2不是二元关系，只是一个集合，除非将a和b定义为有序对。根据上面的记法可以写1R12，aR1b，aR1c等。举例16集合A上的二元关系的数目依赖于A中的元素数。如果|A|=n，那么|A×A|=n2，A×A的子集就有个。每一个子集代表一个A上的二元关系，所以A上有个不同的二元关系。例如|A|=3，则A上有个不同的二元关系。7.2二元关系定义7.4设A，B为集合，A×B的任何子集所定义的二元关系叫做从A到B的二元关系；特别当A=B时，则叫做A上的二元关系A={0,1}，B={1,2,3}，那么R1={0,2}，R2=A×B，R3=，R4={0,1}等都是从A到B的二元关系，而R3和R4同时也是A上的二元关系。举例22n512223说明22n17常用的关系定义7.5对任意集合A，定义全域关系EA={x,y|x∈A∧y∈A}=A×A恒等关系IA={x,x|x∈A}空关系设A={1,2}，那么EA={1,1,1,2,2,1,2,2}IA={1,1,2,2}举例18其它常用的关系小于或等于关系：LA={x,y|x,y∈A∧x≤y}，其中AR。整除关系：DB={x,y|x,y∈B∧x整除y}，其中BZ*Z*是非零整数集包含关系：R＝{x,y|x,y∈A∧xy}，其中A是集合族(1)设A={1,2,3}，B＝{a,b}则LA={1,1,1,2,1,3,2,2,2,3,3,3}DA={1,1,1,2,1,3,2,2,3,3}(2)令A=P(B)={,{a},{b},{a,b}}，则A上的包含关系是R＝{,,,{a},,{b},,{a,b},{a},{a},{a},{a,b},{b},{b},{b},{a,b},{a,b},{a,b}}举例19例7.4例7.4设A={1,2,3,4}，下面各式定义的R都是A上的关系，试用列元素法表示R。(1)R={x,y|x是y的倍数}(2)R={x,y|(x-y)2∈A}(3)R={x,y|x/y是素数}(4)R={x,y|x≠y}解答(1)R={4,4,4,2,4,1,3,3,3,1,2,2,2,1,1,1}(2)R={2,1,3,2,4,3,3,1,4,2,2,4,1,3,3,4,2,3,1,2}(3)R={2,1,3,1,4,2}(4)R=EA-IA={1,2,1,3,1,4,2,1,2,3,2,4,3,1,3,2,3,4,4,1,4,2,4,3}20关系的表示方法关系的三种表示方法：集合表达式关系矩阵关系图关系矩阵和关系图可以表示有穷集上的关系。21关系矩阵和关系图的定义设A={x1,x2,…,xn},R是A上的关系。令则是R的关系矩阵，记作MR。22设A={x1,x2,…,xn},R是A上的关系。令图G=V,E，其中顶点集合V=A，边集为E。对于xi,xj∈V，满足xi,xj∈ExiRxj称图G为R的关系图，记作GR。关系矩阵和关系图的定义23关系矩阵和关系图的实例设A={1,2,3,4}，R={1,1,1,2,2,3,2,4,4,2}，则R的关系矩阵和关系图分别是0010000011000011MR247.3关系的运算定义7.6设R是二元关系。(1)R中所有有序对的第一元素构成的集合称为R的定义域(domain)，记为domR。形式化表示为：domR＝{x|y(x,y∈R)}(2)R中所有有序对的第二元素构成的集合称为R的值域(range)，记作ranR。形式化表示为ranR＝{y|x(x,y∈R)}(3)R的定义域和值域的并集称为R的域(field)，记作fldR。形式化表示为fldR＝domR∪ranR例7.5求R={1,2,1,3,2,4,4,3}的定义域、值域和域。解答domR＝{1,2,4}ranR＝{2,3,4}fldR＝{1,2,3,4}RXYdomRranRfldR25关系的逆和右复合运算定义7.7设R为二元关系，R的逆关系，简称R的逆(inverse)，记作R-1,其中R-1＝{x,y|y,x∈R}定义7.8设F,G为二元关系，G对F的右复合(composite)记作FG，其中FG＝{x,y|t(x,t∈F∧t,y∈G)}说明可以把二元关系看作一种作用，x,y∈R可以解释为x通过R的作用变到y。FG表示两个作用的连续发生。例:设FA×B,GC×D,则F￮GA×D,F￮G的生成如下图所示xtyFG(A)(BC)(D)26关系的限制和像例7.6设F＝{3,3,6,2},G={2,3}，则F-1＝{3,3,2,6}FG＝{6,3}GF＝{2,3}定义7.9设R为二元关系，A是集合(1)R在A上的限制(restriction)记作R↑A，其中R↑A={x,y|xRy∧x∈A}(2)A在R下的像(image)记作R[A]，其中R[A]=ran(R↑A)说明R在A上的限制R↑A是R的子关系。A在R下的像R[A]是ranR的子集。RR|AAR[A]27例7.7设R＝{1,2，1,3，2,2，2,4，3,2}R↑{1}＝{1,2，1,3}R↑＝R↑{2,3}＝{2,2，2,4，3,2}R[{1}]＝{2,3}R[]＝R[{3}]＝{2}28§7.3关系的运算关系是集合,因此关系也具有集合的并、交、差、补、对称差运算设R,S是A到B的两个二元关系，则(RA×B,SA×B)R,S的并R∪S={x,y|xRy∨xSy}R,S的交R∩S={x,y|xRy∧xSy}R,S的差R-S={x,y|xRy∧x$y}R,S的对称差RS=(R∪S)–(R∩S)R的补~R=(A×B)–R={x,y|x∈A∧y∈B∧x℟y}®29例题设A表示是学校的所有学生的集合，B表示学校的所有课程的集合，