离散数学 二元关系优秀课件.ppt

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

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 二元关系的概念1.有序对 有序对/序偶 序偶：由两个元素x和y 按一定顺序排成的组合。记作：。其中x称作第一个元素；y称作第二个元素。第2 页，本讲稿共12 页3 注：x1,实例：1.空间直角坐标系中的坐标 是有序三元组2.图书馆记录 是一个有序六元组.2.有序 有序nn 元组 元组：一个有序 n(n 3)元组 是一个有序对，其中第一个元素是一个有序 n-1 元组，即,xn=。我们将来的

2、研究重点为有序二元组，即有序对/序偶第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 中元素为第二个元素，构成有序对.所有这样的有序对组成的集合叫做 A 与B 的笛卡儿积 记作A B,即 A B=|xA 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(

3、B C)(A,B)例：A=1,B=2,C=3A B=,(AB)C=,3=B C=,A(B C)=1,第5 页，本讲稿共12 页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,

4、G3,G4 之间的关系第6 页，本讲稿共12 页 如 R,可记作 xRy；如果 R,则记作xR y 实例：R1=,R2=,R3=,3,4，R4=|x N y Z R1,R2,R4 是二元关系；R3 不是二元关系。4.二元关系二元关系：如果一个集合满足以下条件之一：（1）集合非空,且它的元素都是有序对（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,

5、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 页9设 A 为任意集合，是 A 上的关系，称为空关系EA,IA 分别称为全域关系与恒等关系，定义如下：EA=|xA y A=AA IA=|xA例如,A=1,2,则 EA=,IA=,注：IA;IA第9 页，本讲稿共12 页10小于

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