《离散数学 二元关系优秀PPT.ppt》由会员分享，可在线阅读，更多相关《离散数学 二元关系优秀PPT.ppt（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学 二元关系现在学习的是第1页，共12页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称作称作第二个元素第二个元素。现在学习的是第2页，共12页3 注：注：x1,实例实例：1.空间直角坐标系中的坐标
2、空间直角坐标系中的坐标 是有序三元组是有序三元组2.图书馆记录图书馆记录是是一个有序六元组一个有序六元组.2.有序有序有序有序n n元组元组元组元组：一个有序一个有序 n(n 3)元组元组 是一个有序对，其中是一个有序对，其中第一个元第一个元素素是一个有序是一个有序 n-1元组，即元组，即 ,xn=。我们将来的研究重点为有序二元组，即有序对/序偶现在学习的是第3页，共12页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。现在学习的是第4页，共12页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,现在学
4、习的是第5页，共12页6二元关系二元关系：集合中两个元素之间的某种关系：集合中两个元素之间的某种关系例例4.3 甲、乙、丙甲、乙、丙3个人进行乒乓球比赛，任何两个人之间都要比赛一场。假设比个人进行乒乓球比赛，任何两个人之间都要比赛一场。假设比赛结果是乙胜甲，甲胜丙，乙胜丙。赛结果是乙胜甲，甲胜丙，乙胜丙。比赛结果可表示为：比赛结果可表示为：，其中，其中表示表示x胜胜y.它表示了集合它表示了集合甲甲,乙乙,丙丙中元素之间的一种胜负关系中元素之间的一种胜负关系.例例4.4 有有A、B、C3个人和四项工作个人和四项工作G1、G2、G3、G4，已知，已知A可以从事工作可以从事工作G1和和G4，B可以从
5、事工作可以从事工作G3，C可以从事工作可以从事工作G1和和G2.那么，人和工作之间的对应关系可以记作那么，人和工作之间的对应关系可以记作 R,它表示了集合它表示了集合A,B,C到工作到工作G1,G2,G3,G4之间的关系之间的关系现在学习的是第6页，共12页如如R,可记作可记作 xRy；如果；如果 R,则记作则记作xR y实例：实例：R1=,R2=,R3=,3,4，R4=|xNy ZR1,R2,R4是二元关系；是二元关系；R3不是二元关系。不是二元关系。4.二元关系二元关系二元关系二元关系：如果一个集合满足以下条件之一：如果一个集合满足以下条件之一：（1）集合非空）集合非空,且它的元素都是有序
6、对且它的元素都是有序对（2）集合是空集）集合是空集则称该集合为一个则称该集合为一个二元关系二元关系,简称为简称为关系关系，记作，记作R.现在学习的是第7页，共12页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上的二元关系上的二元
7、关系.计数：计数：|A|=n,|B|=m,|AB|=nm,AB的子集有的子集有 个个.所以所以 A到到B上有上有 个不同的二元关系个不同的二元关系.|A|=n,|AA|=,AA的子集有的子集有 个个.所以所以 A上有上有 个不同的二元关系个不同的二元关系.例如例如|A|=3,则则 A上有上有512个不同的二元关系个不同的二元关系.现在学习的是第8页，共12页9设设 A 为任意集合，为任意集合，是是 A 上的关系，称为上的关系，称为空关系空关系EA,IA 分别称为分别称为全域关系全域关系与与恒等关系恒等关系，定义如下：，定义如下：EA=|xAyA=AA IA=|xA例如例如,A=1,2,则则 E
8、A=,IA=,注：注：IA;IA现在学习的是第9页，共12页10小于等于关系小于等于关系 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的幂集的幂集.类似的还可以定义大于等于关系类似的还可以定义大于等于关系,小于关系小于关系,大于关系大于关系,真真包含关系等等包含关系等等.现在学习的是第10页，共12页11例例4.6 A=1,2,3,B=a,b,则则 LA=,DA=,P(B)=,a,b,a,b,则则 B上的包含
9、关系是上的包含关系是 R=,现在学习的是第11页，共12页1.1.了解有序对和有序了解有序对和有序了解有序对和有序了解有序对和有序n n元组的概念；元组的概念；元组的概念；元组的概念；2.2.会会会会计计计计算算算算集集集集合合合合的的的的笛笛笛笛卡卡卡卡尔尔尔尔积积积积。掌掌掌掌握握握握笛笛笛笛卡卡卡卡尔尔尔尔积积积积的的的的性性性性质。质。质。质。3.3.重重重重点点点点掌掌掌掌握握握握二二二二元元元元关关关关系系系系的的的的概概概概念念念念，了了了了解解解解二二二二元元元元关关关关系的计数问题。系的计数问题。系的计数问题。系的计数问题。4.4.掌握几种特殊的二元关系。掌握几种特殊的二元关系。掌握几种特殊的二元关系。掌握几种特殊的二元关系。现在学习的是第12页，共12页