离散数学 二元关系PPT讲稿.ppt
离散数学 二元关系第1页，共12页，编辑于2022年，星期日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页，编辑于2022年，星期日3 注：注：x1,实例实例：1.空间直角坐标系中的坐标空间直角坐标系中的坐标 是有序三元组是有序三元组2.图书馆记录图书馆记录是一个有序是一个有序六元组六元组.2.有序有序n元组元组：一个有序一个有序 n(n 3)元组元组 是一个有序对，其中是一个有序对，其中第一个元第一个元素素是一个有序是一个有序 n-1元组，即元组，即 ,xn=。我们将来的研究重点为有序二元组，即有序对/序偶第3页，共12页，编辑于2022年，星期日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中元素中元素为为第二个元素第二个元素，构，构成有序对成有序对.所有这样的有序对组成所有这样的有序对组成的集合叫做的集合叫做 A与与B 的笛卡儿积的笛卡儿积 记作记作A B,即即 A B=|x A y B。第4页，共12页，编辑于2022年，星期日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,第5页，共12页，编辑于2022年，星期日6二元关系二元关系：集合中两个元素之间的某种关系：集合中两个元素之间的某种关系例例4.3 甲、乙、丙甲、乙、丙3个人进行乒乓球比赛，任何两个人之间都要比赛一场。假个人进行乒乓球比赛，任何两个人之间都要比赛一场。假设比赛结果是乙胜甲，甲胜丙，乙胜丙。设比赛结果是乙胜甲，甲胜丙，乙胜丙。比赛结果可表示为：比赛结果可表示为：，其中，其中表示表示x胜胜y.它表示了集合它表示了集合甲甲,乙乙,丙丙中元素之间的一种胜负关系中元素之间的一种胜负关系.例例4.4 有有A、B、C3个人和四项工作个人和四项工作G1、G2、G3、G4，已知，已知A可以从事工作可以从事工作G1和和G4，B可以从事工作可以从事工作G3，C可以从事工作可以从事工作G1和和G2.那么，人和工作之间的对应关系可以记作那么，人和工作之间的对应关系可以记作 R,它表示了集合它表示了集合A,B,C到工作到工作G1,G2,G3,G4之间的关系之间的关系第6页，共12页，编辑于2022年，星期日如如R,可记作可记作 xRy；如果；如果 R,则记作则记作xR y实例：实例：R1=,R2=,R3=,3,4，R4=|xNy ZR1,R2,R4是二元关系；是二元关系；R3不是二元关系。不是二元关系。4.二元关系二元关系：如果一个集合满足以下条件之一：如果一个集合满足以下条件之一：（1）集合非空）集合非空,且它的元素都是有序对且它的元素都是有序对（2）集合是空集）集合是空集则称该集合为一个则称该集合为一个二元关系二元关系,简称为简称为关系关系，记作，记作R.第7页，共12页，编辑于2022年，星期日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的子集有的子集有 个个.所以所以 A到到B上上有有 个不同的二元关系个不同的二元关系.|A|=n,|AA|=,AA的子集有的子集有 个个.所以所以 A上有上有 个不同的二元关系个不同的二元关系.例如例如|A|=3,则则 A上有上有512个不同的二元关系个不同的二元关系.第8页，共12页，编辑于2022年，星期日9设设 A 为任意集合，为任意集合，是是 A 上的关系，称为上的关系，称为空关系空关系EA,IA 分别称为分别称为全域关系全域关系与与恒等关系恒等关系，定义如下：，定义如下：EA=|xAyA=AA IA=|xA例如例如,A=1,2,则则 EA=,IA=,注：注：IA;IA第9页，共12页，编辑于2022年，星期日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页，编辑于2022年，星期日11例例4.6 A=1,2,3,B=a,b,则则 LA=,DA=,P(B)=,a,b,a,b,则则 B上的包含关系是上的包含关系是 R=,第11页，共12页，编辑于2022年，星期日1.1.了解有序对和有序了解有序对和有序了解有序对和有序了解有序对和有序n n元组的概念；元组的概念；2.2.会会会会计计计计算算算算集集集集合合合合的的的的笛笛笛笛卡卡卡卡尔尔尔尔积积积积。掌掌掌掌握握握握笛笛笛笛卡卡卡卡尔尔尔尔积积积积的的的的性质。性质。性质。性质。3.重重重重点点点点掌掌掌掌握握握握二二二二元元元元关关关关系系系系的的的的概概概概念念念念，了了了了解解解解二二二二元元元元关关关关系系系系的计数问题。的计数问题。的计数问题。的计数问题。4.4.掌握几种特殊的二元关系。掌握几种特殊的二元关系。掌握几种特殊的二元关系。掌握几种特殊的二元关系。第12页，共12页，编辑于2022年，星期日
