离散数学 二元关系精选文档.ppt

《离散数学 二元关系精选文档.ppt》由会员分享，可在线阅读，更多相关《离散数学 二元关系精选文档.ppt（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学 二元关系本讲稿第一页，共十二页2 有序对的性质：有序对的性质：1）有序性有序性 （当（当x y时）时）2）与与 相等的充分必要条件是相等的充分必要条件是 =x=u y=v例例4.1 =，求，求 x,y.解解 3y 4=2,x+5=y y=2,x=3 4.1 4.1 二元关系的概念二元关系的概念1.有序对有序对/序偶序偶序偶序偶：由两个元素由两个元素x和和y按一定顺序按一定顺序排成的组合。记作：排成的组合。记作：。其中。其中x称作称作第第一个元素一个元素；y称作称作第二个元素第二个元素。本讲稿第二页，共十二页3 注：注：x1,实例实例：1.空间直角坐标系中的坐标空间直角坐标系中的坐标

2、是有序三元组是有序三元组2.图书馆记录图书馆记录是一个是一个有序六元组有序六元组.2.有序有序n元组元组元组元组：一个有序一个有序 n(n 3)元组元组 是一个有序对，其中是一个有序对，其中第一个第一个元素元素是一个有序是一个有序 n-1元组，即元组，即 ,xn=。我们将来的研究重点为有序二元组，即有序对/序偶本讲稿第三页，共十二页4例例4.2 A=1,2,3,B=a,b,c,C=A B=,B A=,A A=,A C=C A=3.笛卡儿积笛卡儿积：设设A,B为集合，用为集合，用A中元素中元素为为第一第一个元素个元素，B中元素中元素为为第二个元素第二个元素，构成有序对构成有序对.所有这样的有序对

3、组所有这样的有序对组成的集合叫做成的集合叫做 A与与B 的笛卡儿积的笛卡儿积 记作记作A B,即即 A B=|x A y B。本讲稿第四页，共十二页5笛卡儿积的性质：笛卡儿积的性质：1.不适合交换律不适合交换律 A B B A (A B,A,B)2.若若A或或B中有一个为空集，则中有一个为空集，则A B就是空集就是空集.A B=B A=3.若若|A|=m,|B|=n,则则|A B|=mn 4.不适合结合律不适合结合律 (A B)C A(B C)(A,B)例：例：A=1,B=2,C=3A B=,(A B)C=,3=B C=,A(B C)=1,本讲稿第五页，共十二页6二元关系二元关系：集合中两个元

4、素之间的某种关系：集合中两个元素之间的某种关系例例4.3 甲、乙、丙甲、乙、丙3个人进行乒乓球比赛，任何两个人之间都要比赛一场。假个人进行乒乓球比赛，任何两个人之间都要比赛一场。假设比赛结果是乙胜甲，甲胜丙，乙胜丙。设比赛结果是乙胜甲，甲胜丙，乙胜丙。比赛结果可表示为：比赛结果可表示为：，其中，其中表示表示x胜胜y.它表示了集合它表示了集合甲甲,乙乙,丙丙中元素之间的一种胜负关系中元素之间的一种胜负关系.例例4.4 有有A、B、C3个人和四项工作个人和四项工作G1、G2、G3、G4，已知，已知A可以从事工作可以从事工作G1和和G4，B可以从事工作可以从事工作G3，C可以从事工作可以从事工作G1

5、和和G2.那么，人和工作之间的对应关系可以记作那么，人和工作之间的对应关系可以记作 R,它表示了集合它表示了集合A,B,C到工作到工作G1,G2,G3,G4之间的关系之间的关系本讲稿第六页，共十二页如如R,可记作可记作 xRy；如果；如果 R,则记作则记作xR y实例：实例：R1=,R2=,R3=,3,4，R4=|xNy ZR1,R2,R4是二元关系；是二元关系；R3不是二元关系。不是二元关系。4.二元关系二元关系二元关系二元关系：如果一个集合满足以下条件之一：如果一个集合满足以下条件之一：（1）集合非空）集合非空,且它的元素都是有序对且它的元素都是有序对（2）集合是空集）集合是空集则称该集合

6、为一个则称该集合为一个二元关系二元关系,简称为简称为关系关系，记作，记作R.本讲稿第七页，共十二页85.从从A到到B的关系与的关系与A上的关系上的关系设设A,B为集合为集合,AB的的任何子集任何子集所定义的二元所定义的二元关系叫做关系叫做从从A到到B的二元关系的二元关系,当当A=B时则叫做时则叫做 A上上的二元关系的二元关系.例例4.5 A=0,1,B=1,2,3,R1=,R2=AB,R3=,R4=.那么那么 R1,R2,R3,R4是从是从 A 到到 B 的二元关系的二元关系,R3和和R4同时也是同时也是 A上的二元关系上的二元关系.计数：计数：|A|=n,|B|=m,|AB|=nm,AB的子

7、集有的子集有 个个.所以所以 A到到B上上有有 个不同的二元关系个不同的二元关系.|A|=n,|AA|=,AA的子集有的子集有 个个.所以所以 A上有上有 个不同的二元关系个不同的二元关系.例如例如|A|=3,则则 A上有上有512个不同的二元关系个不同的二元关系.本讲稿第八页，共十二页9设设 A 为任意集合，为任意集合，是是 A 上的关系，称为上的关系，称为空关系空关系EA,IA 分别称为分别称为全域关系全域关系与与恒等关系恒等关系，定义如下：，定义如下：EA=|xAyA=AA IA=|xA例如例如,A=1,2,则则 EA=,IA=,注：注：IA;IA本讲稿第九页，共十二页10小于等于关系小

8、于等于关系 LA,整除关系整除关系DA,包含关系包含关系R 定义：定义：LA=|x,yAxy,A R，R为实数集合为实数集合 DB=|x,yAx整除整除y,B Z*,Z*为非为非0整数集整数集 R=|x,yP(A)x y,P(A)是集合是集合A的幂集的幂集.类似的还可以定义大于等于关系类似的还可以定义大于等于关系,小于关系小于关系,大于关系大于关系,真包含关系等等真包含关系等等.本讲稿第十页，共十二页11例例4.6 A=1,2,3,B=a,b,则则 LA=,DA=,P(B)=,a,b,a,b,则则 B上的包含关系是上的包含关系是 R=,本讲稿第十一页，共十二页1.1.了解有序对和有序了解有序对和有序n n元组的概念；元组的概念；元组的概念；元组的概念；2.会会会会计计计计算算算算集集集集合合合合的的的的笛笛笛笛卡卡卡卡尔尔尔尔积积积积。掌掌掌掌握握握握笛笛笛笛卡卡卡卡尔尔尔尔积积积积的的的的性性性性质。质。质。质。3.3.重重点点掌掌握握二二元元关关系系的的概概念念，了了解解二二元元关关系的计数问题。系的计数问题。4.4.掌握几种特殊的二元关系。掌握几种特殊的二元关系。本讲稿第十二页，共十二页