离散数学第七章的课件.

1主要内容有序对与笛卡儿积二元关系的定义与表示法关系的运算关系的性质关系的闭包等价关系与划分偏序关系第七章二元关系27.1有序对与笛卡儿积定义7.1由两个元素x和y(允许x=y)，按照一定的顺序组成的二元组称为有序对或序偶，记作x,y.其中，x是它的第一个元素，y是它的第二个元素。有序对的性质:(1)有序性x,yy,x（当xy时）(2)x,y与u,v相等的充分必要条件是x,y=u,vx=uy=v.注意：区别二元集{x,y}与有序对x,y例7.1已知x+2,4=5,2x+y，求x和y。解由有序对相等的充要条件有x+2=52x+y=4解得x=3,y=-2。3笛卡儿积定义7.2设A,B为集合，用A中元素为第一元素，B中元素为第二元素构成有序对.所有这样的有序对组成的集合叫做A与B的笛卡儿积,记作AB.笛卡儿积的符号化表示为:AB={x,y|xAyB}.例（1）A={1,2,3},B={a,b,c}AB={1,a,1,b,1,c,2,a,2,b,2,c,3,a,3,b,3,c}BA={a,1,a,2,a,3,b,1,b,2,b,3,c,1,c,2,c,3}（2）A={},B=P(A)A={,{}}{}={,,{},}P(A)B=若|A|=m,|B|=n,则|AB|=mn4笛卡儿积的性质(1)若A或B中有一个为空集，则AB就是空集.A=B=(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×D5性质证明证明A(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).6实例例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}例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成立。7(3)A=B∧C=DA×C=B×D证明任取x,y，x,yACxAyCxByDx,yBD所以有A×C=B×D思考题：AC=BD是否推出A=B,C=D?为什么？不一定.反例如下：A={1}，B={2},C=D=,则AC=BD=,但是AB.空集是一个适合用来验证的极值。87.2二元关系定义7.3如果一个集合满足以下条件之一：(1)集合非空,且它的元素都是有序对(2)集合是空集则称该集合为一个二元关系,简称为关系，记作R.如果x,y∈R,可记作xRy；如果x,yR,则记作xy实例：R={1,2,a,b},S={1,2,a,b}.R是二元关系,当a,b不是有序对时，S不是二元关系，只是一个集合。根据上面的记法，可以写1R2,aRb,ac等.9A到B的关系与A上的关系定义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}R1,R2,R3,R4是从A到B的二元关系,R3和R4也是A上的二元关系.计数:|A|=n,|A×A|=n2,A×A的子集有2n2个.所以A上有2n2个不同的二元关系.例如|A|=3,则A上有232=512个不同的二元关系.10A上重要关系的实例定义7.5设A为任意集合,(1)空集是任何集合的子集，是A上的关系，称为空关系(2)全域关系EA={x,y|x∈A∧y∈A}=A×A恒等关系IA={x,x|x∈A}小于等于关系LA={x,y|x∈A∧y∈A∧x≤y},A为实数集R的子集整除关系DB={x,y|x∈B∧y∈B∧x整除y},B为非零整数集Z*的子集包含关系R={x,y|x∈A∧y∈A∧xy},A是由一些集合构成的集合族.11实例例如,A={1,2},则EA={1,1,1,2,2,1,2,2}IA={1,1,2,2}例如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}例如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}}类似的还可以定义：大于等于关系,小于关系,大于关系,真包含关系等.12实例例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={1,1,2,1,3,1,4,1,2,2,4,2,3,3,4,4}(2)R={1,2,1,3,2,3,2,4,3,4,4,3,4,2,3,2,3,1,2,1}(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}13关系的表示关系的表示方法有三种:集合表达式、关系矩阵和关系图。例7.4中的关系就是用集合表达式来给出的。1.关系矩阵若A={x1,x2,…,xm}，B={y1,y2,…,yn}，R是从A到B的关系，R的关系矩阵是布尔矩阵MR=[rij]mn,其中rij=1xi,yjR.2.关系图若A={x1,x2,…,xm}，R是A上的关系，R的关系图是GR=A,R,其中A为结点集，R为边集.如果xi,xj属于关系R，在图中就有一条从xi到xj的有向边.注意：关系矩阵适合表示从A到B的关系或A上的关系（A,B为有穷集）关系图适合表示有穷集A上的关系14实例例A={1,2,3,4},R={1,1,1,2,2,3,2,4,4,2},R的关系矩阵MR和关系图GR如下：0010000011000011RM15题目A={a,b,c,d},R={a,a,a,b,a,c,b,a,d,b},R的关系矩阵MR和关系图GR如下：001000000001011116作业练习书本130页：第1题第7题第12题17课堂提问环节书本130页：第1题第7题第12题187.3关系的运算关系的基本运算（7种）定义7.6设R是二元关系。（1）R中所有的有序对的第一元素构成的集合称为R的定义域，记作domR，形式化表示为domR={x|y(x,yR)}（2）R中所有的有序对的第二元素构成的集合称为R的值域，记作ranR，形式化表示为ranR={y|x(x,yR)}（3）R的定义域和值域的并集称为R的域，记作fldR，形式化表示为fldR=domRranR例7.5R={1,2,1,3,2,4,4,3},则domR={1,2,4}ranR={2,3,4}fldR={1,2,3,4}19关系运算(逆与合成)定义7.7关系的逆运算设R为二元关系，R的逆关系，简称R的逆，记作R-1，其中R1={y,x|x,yR}定义7.8关系的合成运算设F,G为二元关系，G对F的右复合记作FG,其中FG={x,y|t(x,tFt,yG)}例7.6F={3,3,6,2},G={2,3}求：F1、FG、GF解：F1={3,3,2,6}FG={6,3}GF={2,3}类似地也可以定义关系的左复合FG，即FG={x,y|t(x,tGt,yF)}右复合FG表示在右边的G是复合到F上的第二步作用左复合FG表示在左边的F是复合到G上的第二步作用20实例练习：R={1,2,2,3,1,4,2,2}S={1,1,1,3,2,3,3,2,3,3}求：R1、RS、SR解：R1={2,1,3,2,4,1,2,2}RS={1,3,2,2,2,3}SR={1,2,1,4,3,3,3,2}关系是集合，所以关于集合的运算均适用于关系运算，优先级是：逆运算关系运算集合运算21关系运算(限制与像)定义7.9设R为二元关系,A是集合(1)R在A上的限制记作R↾A,其中R↾A={x,y|xRy∧x∈A}(2)A在R下的像记作R[A],其中R[A]=ran(R↾A)说明：R在A上的限制R↾A是R的子关系，即R↾ARA在R下的像R[A]是ranR的子集，即R[A]ranR22关系运算(限制与像)例7.7设R={1,2,1,3,2,2,2,4,3,2},求R↾{1}，R↾，R↾{2,3}，R[{1}]，R[]，R[{3}]。解：R↾{1}={1,2,1,3}R↾=R↾{2,3}={2,2,2,4,3,2}R[{1}]={2,3}R[]=R↾{3}={3,2}R[{3}]={2}定义7.9设R为二元关系,A是集合(1)R在A上的限制记作R↾A,其中R↾A={x,y|xRy∧x∈A}(2)A在R下的像记作R[A],其中R[A]=ran(R↾A)23关系运算的性质定理7.1设F是任意的关系,则(1)(F1)1=F(2)domF1=ranF,ranF1=domF证(1)任取x,y,由逆的定义有x,y∈(F1)1y,x∈F1x,y∈F.所以有(F1)1=F.(2)任取x,x∈domF1y(x,y∈F1)y(y,x∈F)x∈ranF所以有domF1=ranF.同理可证ranF1=domF.24定理7.2设F,G,H是任意的关系,则(1)(FG)H=F(GH)(2)(FG)1=G1F1关系运算的性质证(1)任取x,y,x,y(FG)Ht(x,t∈FG∧t,y∈H)t(s(x,s∈F∧s,t∈G)∧t,y∈H)ts(x,s∈F∧s,t∈G∧t,y∈H)s(x,s∈F∧t(