北大离散数学chap4

第四章二元关系和函数第一节集合的笛卡儿积和二元关系内容：有序对，笛卡儿积，二元关系。重点：(1)掌握有序对的概念，(2)笛卡儿积及性质，(3)二元关系的定义及三种表示法，(4)一些特殊的二元关系。了解：有序nn阶笛卡儿积。元组和一、笛卡儿积。2、笛卡儿积。,|ABxyxAyB1、有序对，记,xy。特点：(1)xy,,xyyx，时，(2),,,xyuvxuyv。有序n(3)n12,,nxxx。，记元组定义：集合ABAB。的笛卡儿积，记作和解：0,,0,,0,,1,,1,,1,ABabcabc,0,,1,,0,,1,,0,,1BAaabbcc0,0,0,1,1,0,1,1AAAB例1、，0,1,,,ABabc求ABBAAAAB。，，，，解：(),{},{},PAabA(),,,{},,{},,,APAaaaabaA,,,{},,{},,bbabbbA(2)笛卡儿积是集合，有关集合的运算都适合。例2、设{,}Aab()APA。，求注意：(1)若则AmBnABmn元集，是元集，是元集。为(3)一般，ABBA。(1)()()()ABCABAC(2)()()()BCABACA(3)()()()ABCABAC(4)()()()BCABACA3、笛卡儿积运算对满足分配律。或例3、证明：()()()ABCABAC,()xyABC()xAyBCxAyByC()()xAyBxAyC证明：对任意,xy，,()()xyABAC,(),()xyABxyAC例3、证明：()()()ABCABAC,()xyABC证明：对任意,xy，故()()()ABCABAC。12nAAA121122,,,|nnnxxxxAxAxA4、n(2)n笛卡儿积。阶特别，当12nAAAA记为nA时，。如{,}Aab2,,,,,,,Aaaabbabb，二、二元关系。1、定义：(1)若集合则称RR为空集或它的元素都是有序对，为二元关系。若,xyRxRy否则，记作xRy，，则记作。(2)ABAB的关系，到的任何子集都称作从特别，当ABA上关系。时，称作设1,0,,0,,2Rabb2R3RAB4,1Rb则1234,,,RRRRAB的关系。到都是从例4、{,}Aab{0,1,2}B，2、A上不同关系的数目。若AnAn则2AAn，元集，记为，的子集共有AA22n个，元集nA22n个。上不同的关系共有3、特殊的关系。空关系AEAI。，恒等关系，全域关系对任意集合A，空关系，全域关系,|AExyxAyAAA，恒等关系,|AIxxxA。4、常用关系。(1)设ARA,,ALxyxyAxy上小于等于关系：，(2)设BZB,,|BDxyxyBxy上整除关系：，(3)幂集()PAR,|,()RxyxyPAxy：上的包含关系解：2,2,2,3,2,6,2,8,3,3,AL3,6,3,8,6,6,6,8,8,82,2,2,6,2,8,3,3,3,6,6,6,8,8AD例5、{2,3,6,8}AALAD。，，求解：，(),{},{},PAabA,,,{},,{},Rab,{,},{},{},{},,abaaaA{},{},{},,,bbbAAA例6、{,}Aab()PAR。上的包含关系，求有三种集合表示法矩阵表示法图形表示法5、A上二元关系的表示法。解：0110110000100010RM关系图：例7、已知{1,2,3,4}AA1,2,1,3,2,1,2,2,3,3,4,3R求RRM，上关系，和关系图。的关系矩阵一般：设12{,,,}nAxxx()RijnnMr，其中10ijijijxRxrxRx关系图表示点(边(每个有序对对应一条有向弧)n个顶点)第二节关系的运算内容：关系的定义域，值域，逆关系，合成关系。重点：(1)掌握逆关系，合成关系的概念及求法，一般：关系的定义域，值域。(2)掌握关系n次幂的概念及性质。一、逆关系，合成关系。1、关系的逆。(1)定义：关系R1,,RyxxyR的逆关系定义为解：12,2,3,3,3,2,6,2,6,3,6,6AL,,xyxyAxy12,2,6,2,3,3,6,3,6,6AD,|,xyxyAxy是的倍数例1、{2,3,6}AALA为ADA1AL1AD上小于等于关系，为，。，上整除关系，分别求出即1ALA上大于等于关系。为即1ADA上的倍数关系。为2、关系的合成(复合)。(1)定义，关系R和S的合成关系定义为：,()RSxyzxSzzRy(2)1R1RMRRM，的关系矩阵与的关系矩阵满足1RRMM的转置。的关系图只需将改向即得。1RR的关系图中的有向弧(3)11()RR。例2、设1,2,2,2,3,4R1,3,2,5,3,1,4,2,4,5S求RRRSSRSS()RRR，，，，()RSR，。解：1,4,3,2,4,2RS1,5,2,5,3,2,3,5SR1,2,2,2RR例2、设1,2,2,2,3,4R1,3,2,5,3,1,4,2,4,5S求RRRSSRSS()RRR，，，，()RSR，。1,1,3,3,4,5SS解：()1,2,2,2RRR()3,2RSR逻辑加法：000011101111，，，。(2)RSRSM,RS,RSMM满足RSSRMMM的关系矩阵与的关系矩阵。的关系图可将RS,RS起来求得。的关系图连接如例2中，次幂的运算满足：nmnmnRRR，()mnmnRR(,)mnN(3)合成关系满足结合律：()()RSTRST。(4)关系Rn次幂。的定义：设RAnN的Rn①0,|RxxxA②1(1)nnRRRn次幂规定为：，上关系，为[解法一]用集合表示。0,,,,,,,Raabbccdd10RRRR21,,,,,,,RRRRRaaacbbbd例3、{,,,},,,,,,,,AabcdRabbabccd求iR0,1,2,3,4,5i。，543,,,,,,,RRRabadbabcR432,,,,,,,RRRaaacbbbdR32,,,,,,,RRRabadbabc[解法一]用集合表示。例3、{,,,},,,,,,,,AabcdRabbabccd求iR0,1,2,3,4,5i。，[解法二]用关系图表示。例3、{,,,},,,,,,,,AabcdRabbabccd求iR0,1,2,3,4,5i。，[解法二]用关系图表示。[解法三]用矩阵表示(略)。例3、{,,,},,,,,,,,AabcdRabbabccd求iR0,1,2,3,4,5i。，3、关系的逆与合成间的联系。111()RSSR证明：任取,xy1,()xyRS,yxRS,,zyzSzxR11,xySR11,,zzySxzR3、关系的逆与合成间的联系。111()RSSR证明：任取,xy1,()xyRS故111()RSSR。dom,RxyxyRran,RyxxyRflddomranRRR二、关系RdomR值域ranRfldR，的定义域。和域例4、分别求出以下关系的定义域和值域。(1)1,,RxyxyZxy解：11domranRRZ20,1,0,1,1,0,1,0R解：(2)222,,1RxyxyZxy22domran{0,1,1}RR例4、分别求出以下关系的定义域和值域。(3)3,,2RxyxyZyx解：3domRZ(4)4,,3RxyxyZxy解：43,3,3,3,3,3,3,3R44domran{3,3}RR3ran{|2}RttkkZ即偶数集第三节关系的性质内容：关系的自反性，反自反性，对称性，反对称性，传递性。重点：(1)掌握自反性，反自反性，对称性，反对称性，传递性的定义及关系矩阵和关系图的特征，(2)掌握关系五种性质的判断和验证。一、关系的五种性质(自反，反自反，对称，反对称，传递)。1、定义及关系矩阵，关系图特征由下表给出(RA上关系)为定义关系矩阵的特点关系图的特点自反性xA，都有,xxR主对角线元素全为1图中每个顶点都有环反自反性xA，都有,xxR主对角线元素全为0图中每个顶点都无环定义关系矩阵的特点关系图的特点对称性对称矩阵若两顶点间有边，必是一对方向相反的边反对称性若两顶点间有边，必是一条有向边若,xyR则,yxR，若,xyRxy则,yxR，且若1ijrij则0jir，且定义关系矩阵的特点关系图的特点传递性若,xyR,yzR,xzR，则且若顶点ixjxjxkx则ixkx有边，到有边，到必有边到(1)11,1,1,2,2,1R(2)21,2,2,3,1,3R例1、{1,2,3}AA1234,,,RRRR如下所示，判断1234,,,RRRR各有哪些性质。上关系，解：1R是对称的，不是传递的。既不是自反又不是反自反，解：2R是反自反的，反对称的，传递的。(3)31,1,3,3R(4)41,1,2,2,3,3,1,2,1,3,2,1R例1、{1,2,3}AA1234,,,RRRR如下所示，判断1234,,,RRRR各有哪些性质。上关系，解：3R既是对称又是反对称的，传递的。既不是自反又不是反自反的，解：4R不是传递的。是自反的，既不是对称又不是反对称的，例2、判断下图中的关系分别具有哪些性质。解：1R是反自反，反对称，不是传递的。例2、判断下图中的关系分别具有哪些性质。解：2R既是对称又是反对称的，传递的。是空关系，是反自反，例2、判断下图中的关系分别具有哪些性质。解：3R既是对称又是反对称的，传递的。是恒等关系，是自反的，例2、判断下图中的关系分别具有哪些性质。解：4R传递的。是全域关系，是自反的，对称的，例2、判断下图中的关系分别具有哪些性质。解：5R反对称的，传递的。既不是自反也不是反自反的，例2、判断下图中的关系分别具有哪些性质。解：6R又不是反对称，不是传递的。是反自反的，既不是对称则有以下文氏图。2、若把A上所有关系看成一个全集，则有以下文氏图。2、若把A上所有关系看成一个全集，二、五种性质的其它判断方法。设RAAIA上恒等关系，则为上关系，是1、RAIR，是自反的当且仅当2、RAIR，是反自反的当且仅当3、R1RR，是对称的当且仅当4、R1ARRI，是反对称的当且仅当5、RRRR。是传递的当且仅当例3、设1,2,3AA11,2,1,3R21,2,2,1,1,3,2,3R判断12,RR是否传递的。上关系，，解：因111RRR1R是传递的。，所以因2221,1,1,3,2,2,2,3RRR所以2R，不是传递的。三、关系在各种运算下保持原有特性问题。证明：对任意,xy12,xyRR12,,xyRxyR12,,yxRyxR12,yxRR例如：设12,RRA证明12RRA上的对称关系，为上的对称关系。也是所以12RRA上是对称的。在又如：设12,RRA证明A12RR上反对称关系，为上的反对称关系。不一定是反例：12{1,2},1,2,2,1ARR都是A上的反对称关系，但121,2,2,1R