离散数学课件第四章—二元关系和函数.ppt
《离散数学课件第四章—二元关系和函数.ppt》由会员分享,可在线阅读,更多相关《离散数学课件第四章—二元关系和函数.ppt(156页珍藏版)》请在三一文库上搜索。
1、刘师少,Tel: 86613747(h) E-mail: ,授课: 51学时,教学目标: 知识、能力、素质,Discrete Mathematics,第四章 二元关系和函数,4.1 集合的笛卡尔积与二元关系 4.2 关系的运算 4.3 关系的性质 4.4 关系的闭包 4.5 等价关系和偏序关系 4.4 函数的定义和性质 4.4 函数的复合和反函数 4.4 例题分析,说起关系这个词,对我们并不陌生,世界上存在着各种各样的关系,人与人之间的“同志”关系;“同学”关系;“朋友”关系;“师生”关系;“上下级”关系;“父子”关系;两个数之间有“大于”关系;“等于”关系和“小于”关系;两个变量之间有一定的
2、“函数”关系;计算机内两电路间有导线“连接”关系;程序间有“调用”关系等等。所以对关系进行深刻的研究,对数学与计算机科学都有很大的用处。,再如: 电影票与座位之间有对号关系。 设: X 表示电影票的集合 Y 表示座位的集合, 则,对于任意的x X和y Y, 必有 x 与 y 有对号 “对号”关系 则上述问题可表达为xRy或xRy , 亦可记为(x ,y)R或(x ,y)R 因此我们可以看到对号关系R是序偶的集合, 在这一章我们要研究集合内元素间的关系以及集合之间元素之间的关系,这就是“关系”与“函数”。它们是很重要的基本数学概念,在数学领域中均有很大的作用,并且对研究计算机科学中的许多问题如数
3、据结构、数据库、情报检索、算法分析、计算理论等都是很好的数学工具。,关系的引入 例4.0 设一旅馆有n个房间,每个房间可住两个旅客,所以一共可住2n个旅客,在旅馆内,旅客与房间有一定关系,用 R 表示“某旅客住在某房间”这种关系。 设 n=3 表示旅馆共有3个房间, 分别记以 1, 2, 3 可住6个旅客分别记以 a, b, c, d, e, f , 这些旅客住的房间如右下图所示,1,2,3,a,b,c,d,e,f,满足 R 的所有关系可看成是一个有序偶的集合,这个集合可叫 R R=, 若令 A = a, b, c, d, e, f B = 1, 2, 3 则例中关系的每一元素均属于AB 亦即
4、 R 是AB的子集,并称此关系为从 A 到 B 的关系 R。,4.1 集合的笛卡尔积与二元关系,定义4.1由两个元素x,y(允许x=y)按一定顺序排列成 的二元组叫做一个有序对或序偶,记作,其中x是 它的第一元素,y是它的第二元素。 有序对具有以下性质: (1) 当xy时, (2) = x=w y=v 例4.1:已知 = ,求 x 和 y。 解:由有序对相等的充要条件得 x+3 = y+7 y-2 = 3y-x 解得 x = 6, y = 2,4.1 集合的笛卡尔积与二元关系,定义4.2 一个有序n元组 (n3)是一个有序对, 其中第一个元素是一个有序n-1元组, 一个有序n元组记作,即 =
5、, xn 例如:空间直角坐标系中点的坐标 , 等都是有序3元组。 n维空间中点的坐标或n维向量都是有序n元组。 形式上也可以把看成有序1元组。,定义4.3 设A,B为集合,用A中元素为第一元素,B中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做A和B的笛卡儿积,记作AB。 笛卡儿积的符号化表示为: A B=|x A y B 例如:若A=1,2, B=a,b,c,则 AB=, , , , , BA=, , , , , 易知:若|A|=m,(即集合A的元素的个数),|B|=n,则 | AB|= |BA|= m n,4.1 集合的笛卡尔积与二元关系,主菜 鱼香肉丝 家常豆腐 宫保鸡丁 酸辣
6、土豆丝 蒜茸油麦菜,汤 紫菜蛋花汤 鱼头豆腐汤 鸡蛋西红柿汤 酸辣蔬菜汤,由前面的定义可知:有序对就是有顺序的数组,如,x,y 的位置是确定的,不能随意放置。 注意:有序对,以a,b为元素的集合a,b=b,a;有序对(a,a)有意义,而集合a,a不成立,因为它只是单元素集合,应记作a。 笛卡儿积是一种集合合成的方法,把集合A,B合成集合AB,规定 ABxA,yB 由于有序对中x,y的位置是确定的,因此AB的记法也是确定的,不能写成BA。 笛卡儿积也可以多个集合合成 A1A2An。 笛卡儿积的运算性质。,笛卡儿积的性质: 1、对任意集合A,根据定义有 A = A= 2、一般来说,笛卡儿积不满足交
7、换律,即 ABBA (当A B B 、A 时) 3、笛卡儿积不满足结合律,即 (AB) CA(B C) (当ABC时) 4、笛卡儿积运算对并和交运算满足分配律,即 A(BC)= (AB)(A C) (BC) A = (BA)(C A) A(BC)= (AB) (A C) (BC) A = (BA) (C A),4.1 集合的笛卡尔积与二元关系,例4.2 证明:(BC) A = (BA)(C A) 对于 (BC) A x(B C) y A xB x C y A xB x C y A y A (xB y A) (x C y A) B A C A (BA) (C A) (BC) A = (BA) (
8、C A),4.1 集合的笛卡尔积与二元关系,例4.3:设A, C, B, D为任意集合,判断以下命题是否为真,并说明理由。 (1) AB= AC =B= C (2) A-(BC)=( A-B)(A-C) (3) 存在集合A,使得A A A.,解: (1) 不一定为真。反例A= , B、C为任意不相 等的非空集合。 (2) 不一定为真。反例A= 1, B=2, C=3. (3) 为真。当 A= 时成立。,定义4.4 设A1,A2,An,是集合(n2),它们的n阶笛卡儿积记作A1A2An ,其中 A1A2An= | x1A1x2A2xnAn 当A1=A2=An=A时, 将起n阶笛卡儿积记作An例如
9、,A= a ,b ,则 A3=AAA=a,ba,ba,b =, , , ,4.1 集合的笛卡尔积与二元关系,例4.6 设集合 A=a,b,B=1,2,3,C=d, 求ABC,BA。 解 先计算AB, ABC ,d , BA, 例4.7 设集合A1,2,求AP(A)。 解 P(A)=,1,2,1,2 AP(A)1,2,1,2,1,2 =, , ,定义4.5 如果一个集合符合以下条件之一: (1) 集合非空,且它的元素都是有序对 (2) 集合是空集 则称该集合为一个二元关系,记作R,简称 为关系。 对于二元关系R,若 R,可记作xRy; 如果 R,则记作xRy。 例:R1=,R2=5,6,7 aR
10、1b, 1R12, 5R16,4.1 集合的笛卡尔积与二元关系,二元关系是两种客体之间的联系,例如某学生学习语文、数学、外语,表示为 A语文, 数学, 外语 功课的成绩分四个等级,记作 BA,B,C,D 于是该生成绩的全部可能为AB AB , , , 而该生的实际成绩 P, 可以看出P是AB的一个子集,它表示了功课与其成绩 的一种关系。 由此可见:两个集合之间的二元关系,实际上就是两个元素之间的某种相关性。,再如:若A=,B=1,2,3,求AB , BA, AA, BB,(AB)(BA),解:AB =(,1),(,2),(,3),(,1), (,2),(,3) BA =(1,),(1,),(2
11、,),(2,), (3,), (3,) AA = ( ,),(,),(,),(,) BB = (1,1),(1,2),(1,3),(2,1),(2,2), (2,3),(3,1),(3,2),(3,3) (AB)(BA)= 由上例可看出:ABBA,程序实现,定义4.6 设A,B为集合,AB的任何子集所定义的二元关系叫做从A到B的二元关系,特别当A=B时则叫做A上的二元关系。 例4.7:若A=a,b,B=2,5,8,则 A B= , 令 R1= , R2=, , R3= 因为R1 A B, R2 A B, R3 A B, 所以R1, R2和 R5均是由A到B的二元关系 因为只讨论二元关系,所以今
12、后无特别声明, 术语“关系”皆指二元关系?,又例:若A=a,b,B=2,5,8,则 BA= , 令 R4= , R5=, , 因为R4 BA, R5 BA, 所以R4和 R5均是由B到A的关系 又 BB=, , , 令 R6= , , R7=, , 因为R6 BB, R7 BB, 所以R6和 R7均是集合B上的关系。,若集合|A|=n,则集合A上的二元关系有多少个? 答曰: |A|=n,则|A A|=n2, A A的任一个子集就是A上的二元关系,即P(A)= 2n 个。,例4.8 A= 1,2 则A A有n2 个不同的二元关系 AA=1,21,2= , AA的任一个子集就是A A的幂集,即P(
13、A) P(A)= , , , , , , , , , , , , , , , , , , , , , , , , 集合中的元素不分顺序,若集合A= a,b,c 则A的幂集,P(A)为 P(A) = , a, b, c, a,b, a,c, b,c, a,b,c ( 注a,a= a b,b= b c,c= c ),三类特殊的关系 对于任何集合A,空集 是A A的子集,叫做A上 的空关系 定义EA=|xA yA= AA为全域关系 定义IA=|xA 为恒等关系 例:若A=1,2,则 EA= , IA =,除上述三类特殊的关系外,还有一些常用的关系,如: LA= |x,yA xy (A R)为实数集上
14、的小于等于关系。 DA= |x,yA x整除y (A Z*)为非正整数集上的整除关系。 R = |x,yA xy (A 是集合族)为集合上的包含关系。 类似地还可以定义大于等于关系、大于关系、小于关系、真包含关系等。,4.1 集合的笛卡尔积与二元关系,例4.9:设A=1,2,3,4,请表示下列关系。 (1) R= |x是y的倍数 (2) R= |(x-y)2 A (3) R= |x除y是素数 (4) R= |xy,4.1 集合的笛卡尔积与二元关系,解 (1) DA = , , , , , (2) R = , , , (3) DA = , (4) R= , , ,例4.9_1 设A= 1,2,3
15、 ,B= 4,5,6 , 并定义R1,R2为从A到B的关系; R3为从B到A的关系;(aA,bB) (1) 当且仅当:a能整除b时,aR1b; (2) 当且仅当:a是b的整数倍时,aR2b; (3) 当且仅当:b是a的整数倍时,bR3a; 试写出R1,R2,R3。 解: R1=(1,4),(1,5),(1,6),(2,4),(2,6),(3,6) R2=; R3=(4,1),(5,1), (6,1),(4,2),(6,2), (6,3),|A|=n, |B|=m, A , B中的元素已按一定的次序排列若A=x1,x2,xn ,B= y1,y2,ym 且RAB,若 1 若 xiRyj r ij=
16、 (i=1,2,n j=1,2,m) 0 若xiRyj 则称矩阵M(R)=(rij) n m 为R的关系矩阵。,有穷集合上的二元关系的三种表示方法: 集合表示法 (前已使用) 关系矩阵法 关系图 关系矩阵是表示关系的另一种有效的方法,其优点是可以利用矩阵作为研究关系的手段,而且这样做便于计算机进行处理。 设R:AB,A和B都是有限集,且,设A,B为集合,AB的任何子集Ri AB则称Ri所定义的二元关系叫做从A到B的二元关系,特别当A=B时则叫做A上的二元关系,则 r11 r12 r1n (r ij)= r21 r22 r2n rn1 rn2 rnn 是R的关系矩阵,记作MR。,关系矩阵法 若A
17、=x1,x2,xn ,B= y1,y2,yn 则R的关系矩阵是一个n行n列矩阵M(R)= (rij)nn , 其中元素 rij 为: 1 若 xiRyj r ij= (i,j=1,2,n) 0 若xiRyj,0 1 1 1 MR= 0 0 1 1 0 0 0 1 0 0 0 0,例4.10 A=1,2,3,4 R为A上的小于关系,则R为: R=, , , R的关系矩阵为:,1 2 3 4,1 2 3 4,例4.11 设集合A2,3,4, B=8,9,12,14. R是由A到B的二元关系,定义: R= | a整除b 写出R的表达式和关系矩阵. 解 R=, 8 9 12 14 2 1 0 1 1
18、R的关系矩阵为.MR= 3 0 1 1 0 4 1 0 1 0,关系图 关系图是表示关系的一种直观形象的方法,设R:AB,A和B都是有限集, A=x1,x2,xn , B= y1,y2,ym 关系R的有序偶 可用图中从结点xi 到yj 的有向边表示,这样即可将关系用图表示之。 例4.12 设 R: AB,A=x1,x2, x3, x4 , B= y1,y2,y3 R=, R的关系如下图所示,x1,x2,x3,x4,y1,y2,y3,关系图 关系图是表示关系的一种直观形象的方法,设R:AB,A和B都是有限集, A=x1,x2,xn , B= y1,y2,ym 关系R的有序偶 可用图中从结点xi
19、到yj 的有向边表示,这样即可将关系用图表示之。 例4.13 设 R: AA,A= a,b, c, d R=, , , R的关系如下图所示,a,b,c,d,其中 c 到 c的边称为环,定义4.8 设R是二元关系 (1) R中所有的有序对的第一元素构成的集合称为R的 定义域,记作domR,形式化表示为: domR= x| y( R) (2) R中所有的有序对的第二元素构成的集合称为R的值域,记作ranR,形式化表示为: ranR= y| x( R) (3) R的定义域和值域的并集称为R的域,记作fldR,形式化表示为: fldR= domR ranR,4.2 关系的运算,例4.14 下列关系都是
20、整数集Z上的关系,分别求出它们的定义域和值域 R1= |x,yZxy (2) R2= |x,yZx2+y2=1 (3) R3= |x,yZy=2x R4= |x,yZ|x|=|y|=3 解 (1) dom R1= ram R1= Z R2=, dom R2= 0, 1, -1 ram R2= 0, 1, -1 (3) dom R3=Z ram R3= 2z|zZ 即偶数集 (4) dom R4= -3, 3 ram R4= -3, 3 ,1,0,-1,-1,0,1,dom R2,ram R2,R2, 2 1 0 -1 -2 , 4 3 2 1 0 -1 -2 -3 -4 ,dom R3=Z,r
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 课件 第四 二元关系 函数
链接地址:https://www.31doc.com/p-3068216.html