离散数学4.

离散数学第四章二元关系及其函数第四章二元关系及其函数离散数学第四章二元关系及其函数本章主要内容:4.1集合的笛卡尔积与二元关系4.2关系的运算4.3关系的性质4.4关系的闭包4.5等价关系与划分4.6偏序关系4.7函数的定义和性质4.8函数的复合和反函数本章小结离散数学第四章二元关系及其函数4.1集合的笛卡儿积与二元关系§4.1.1有序对定义4.1由两个元素x和y(允许x=y)按一定的顺序排列成的二元组叫做一个有序对(也称序偶),记作x,y,其中x是它的第一元素,y是它的第二元素。例如,平面直角坐标系中点的坐标就是有序对,(1,-1),(2,0),(1,1),(-1,1),…都代表坐标系中不同的点。有序对的特点：1.当xy时,x,yy,x。2.两个有序对相等,即x,y＝u,v的充分必要条件是x＝u且y＝v。离散数学第四章二元关系及其函数§4.1.1有序对定义4.2一个有序n元组(n≥3)是一个有序对,其中第一个元素是一个有序n－1元组,一个有序n元组记作x1,x2,…,xn,即x1,x2,…,xn=x1,x2,…,xn-1,xn例如,空间直角坐标系中点的坐标1,-1,3,2,4.5,0等都是有序3元组。n维空间中点的坐标或n维向量都是有序n元组特别地x1,x2,…,xn-1,xn=y1,y2,…,yn-1,yn(x1=y1)∧(x2=y2)∧…∧(xn=yn)4.1集合的笛卡儿积与二元关系离散数学第四章二元关系及其函数§4.1.2笛卡儿积定义4.3设A,B为集合,用A中元素为第一元素,B中元素为第二元素,构成有序对,所有这样的有序对组成的集合叫做A和B的笛卡儿积,记作A×B.符号化表示为:A×B＝{(x,y)|xA∧yB}.4.1集合的笛卡儿积与二元关系离散数学第四章二元关系及其函数§4.1.2笛卡儿积例4.1A={a,b},B={0,1,2},求A×B，B×A,A×A,B×B,(A×B)∩(B×A)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×A={a,a,a,b,b,a,b,b}B×B={0,0,0,1,0,2,1,0,1,1,1,2,2,0,2,1,2,2}(A×B)∩(B×A)=4.1集合的笛卡儿积与二元关系离散数学第四章二元关系及其函数§4.1.2笛卡儿积如果A中有m个元素,B中有n个元素,则A×B和B×A中都有多少个元素?m*n个若x,yA×B,则有xA和yB。若x,yA×B,则有xA或者yB.4.1集合的笛卡儿积与二元关系离散数学第四章二元关系及其函数§4.1.2笛卡儿积笛卡儿积运算的性质1.若A,B中有一个空集,则它们的笛卡儿积是空集,即B=B×=.2.当A≠B且A,B都不是空集时,有A×B≠B×A.所以,笛卡儿积运算不满足交换律.3.当A,B,C都不是空集时,有(A×B)×C≠A×(B×C).所以,笛卡儿积运算不满足结合律.4.1集合的笛卡儿积与二元关系离散数学第四章二元关系及其函数由笛卡尔积定义可知：当A,B,C都不是空集时(A×B)×C={a,b,c}|(a,bA×B∧cC}={a,b,c}|(aA)∧(bB)∧(cC)}A×(B×C)={a,b,c}|(aA)∧b,cB∧C}由于a,b,c不是三元组，所以，(A×B)×C≠A×(B×C)（不适合结合律）4.1集合的笛卡儿积与二元关系离散数学第四章二元关系及其函数§4.1.2笛卡儿积笛卡儿积运算的性质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×D4.1集合的笛卡儿积与二元关系离散数学第四章二元关系及其函数§4.1.2笛卡儿积笛卡儿积运算的性质例4.2证明A×(B∪C)＝(A×B)∪(A×C)证明:对于任意的x,y,x,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)。4.1集合的笛卡儿积与二元关系离散数学第四章二元关系及其函数§4.1.2笛卡儿积笛卡儿积运算的性质例4.3设A={1,2},求P(A)×A.(P103例7.2)解.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}例4.4设A,B,C,D为任意集合,判断以下等式是否成立,说明为什么.(1)(A∩B)×(C∩D)＝(A×C)∩(B×D)；(2)(A∪B)×(C∪D)＝(A×C)∪(B×D)；(3)(A－B)×(C－D)＝(A×C)－(B×D)；(4)(AB)×(CD)＝(A×C)(B×D)。4.1集合的笛卡儿积与二元关系离散数学第四章二元关系及其函数解.(1)成立.因为对于任意的x,y,x,y(A∩B)×(C∩D)xA∩B∧yC∩DxA∧xB∧yC∧yDx,yA×C∧x,yB×Dx,y(A×C)∩(B×D)(2)不成立。事实上：x,y(A∪B)×(C∪D)xA∪B∧yC∪D(xA∨xB)∧(yC∨yD)4.1集合的笛卡儿积与二元关系离散数学第四章二元关系及其函数(xA∧yC)∨(xA∧yD)∨(xB∧yC)∨(xB∧yD)x,yA×C∨x,yA×D∨x,yB×C∨x,yB×D(A×C)∪(A×D)∪(B×C)∪(B×D)举一反例如下：若A＝D＝,B＝C＝{1},则有：(A∪B)×(C∪D)＝B×C＝{1,1},(A×C)∪(B×D)＝∪＝.4.1集合的笛卡儿积与二元关系离散数学第四章二元关系及其函数(3)(A－B)×(C－D)＝(A×C)－(B×D)不成立反例如下：若B＝,A＝D＝{1},C={1,2},则有(A－B)×(C－D)＝{1}×{2}＝{1,2},(A×C)－(B×D)＝{1}×{1,2}={1,1,1,2}(4)(AB)×(CD)＝(A×C)(B×D)不成立反例如下：若A＝D＝,B＝C＝{1},则有(AB)×(CD)＝B×C＝{1,1}(A×C)(B×D)＝＝.4.1集合的笛卡儿积与二元关系离散数学第四章二元关系及其函数例4.5设A,B,C,D为任意集合,判断以下命题的真假.(1)若AC且BD,则有A×BC×D。(2)若A×BC×D,则有AC且BD.解.(1)命题为真.x,yA×BxA∧yB又因AC且BDxC∧yDx,yC×D故有A×BC×D(2)命题为假.当A＝B＝时,或者A≠且B≠时,该命题的结论是成立的.但是当A和B之中仅有一个为时,结论不一定成立,例如,令A＝C＝D＝,B＝{1},这时A×BC×D,但BD.4.1集合的笛卡儿积与二元关系离散数学第四章二元关系及其函数§4.1.2笛卡儿积n阶笛卡儿积定义4.4设A1,A2,…,An是集合(n≥2),它们的n阶笛卡儿积,记作A1×A2×…×An,其中Al×A2×…×An＝{x1,x2,…xn|x1Al∧x2A2∧…xnAn}故:A1×A2×…×An是有关n元组构成的集合.特别地A×A=A2A×A×A=A3A×A×…×A=An|-----------n个-----------|4.1集合的笛卡儿积与二元关系离散数学第四章二元关系及其函数§4.1.3二元关系(Relation)定义4.5如果一个集合为空集或者它的元素都是有序对,则称这个集合是一个二元关系,一般记作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等.注:因一般地x,yy,x,故一般地xRyyRx.4.1集合的笛卡儿积与二元关系离散数学第四章二元关系及其函数§4.1.3二元关系定义4.6设A,B为集合,A×B的任何子集所定义的二元关系称作从A到B的二元关系,特别当A＝B时,则叫做A上的二元关系.①关系RAB,R从A到B一个关系.②RAA,R是A上的关系.例如A={0,1},B={1,2,3},那么R1={0,2},R2=AB,R3=,R4={0,1}等都是从A到B的二元关系,而R3和R4同时也是A上的二元关系.4.1集合的笛卡儿积与二元关系离散数学第四章二元关系及其函数§4.1.3二元关系二元关系的数目如果|A|=n,那么|A×A|=n2,其中每一个子集代表一个A上的二元关系.由于|P(A×A)|=2n2,A上有2n2个不同的二元关系.例如|A|=3,则A上有232=512个不同的二元关系.集合的3种特殊关系:空关系:若R=,则R称做空关系；全域关系EA和恒等关系IA:对任何集合A,IA＝{x,x|xA},EA＝{x,y|xA∧yA}＝A×A例4.6A={0,1,2},则EA＝{0,0,0,1,0,2,1,0,1,1,1,2,2,0,2,1,2,2｝IA＝{0,0,1,1,2,2)}4.1集合的笛卡儿积与二元关系离散数学第四章二元关系及其函数§4.1.3二元关系常用的关系:小于等于关系、整除关系、包含关系.例如:设A为实数集R的某个子集,则A上的小于等于关系定义为LA＝{x,y|x,yA∧x≤y｝设B为正整数集Z＋的某个子集,则B上的整除关系定义为DB＝{x,y｜x,yB∧xy}.例4.7A={4,0.5,-1},B={1,2,3,6},则LA={-1,-1,-1,0.5,-1,4,0.5,0.5,0.5,4,4,4｝DB={1,1,1,2,1,3,1,6,2,2,2,6,3,3,3,6,6,6}.4.1集合的笛卡儿积与二元关系离散数学第四章二元关系及其函数例4.8设A＝{a,b},R是P(A)上的包含关系,R＝{x,y|x,yP(A)∧xy,则有P(A)＝{,{a},{b},A}.R＝{,,,{a},,{b},,A,{a},{a},{a},A,{b},{b},{b},A,A,A}.注:①类似的,还可以定义大于等于关系,小于关系,大于关系,真包含关系等等.②关系是有序对的集合,因此对它可进行集合运算,运算结果定义一个新的关系.例如设R和S是给定集合上的关系,则R∪S,R∩S,R－S,R分别称为关系R与S的并关系,交关系,差关系和R的补关系.4.1集合的笛卡儿积与二元关系离散数学第四章二元关系及其函数§4.1.4二元关系的表示前面所学可知：X到Y的关系R是X×Y的子集.若令X,Y均为有限集,有限集X,Y上的关系R,可用序偶集合的形式表示,这种表示方法叫集合表达式.此外,还可用关系矩阵和关系图给出.定义4.8设给定两个有限集X={x1,x2,…,xm},Y={y1,y2,…,yn},R是从X到Y的一个二元关系.则对应关系R有一个关系矩阵MR=[rij]m×n,其中,如果xi,yjR,则rij=1;如果xi,yjR,则rij=0