离散数学,二元关系与运算
60页1、二元关系和运算,第四章,1. 二元有序组:由两个元素x和y按一定顺序排成二元组,记作: 。,4.1 二元关系的概念,如: 平面直角坐标系中点的坐标,一、二元关系的概念,二元有序组的性质,(1) 当x y时, ,(2) = ,当且仅当x = u,y = v,(1)、(2)说明有序组区别于集合,n元有序组:由n个元素x1,x2,xn,按一定顺序排成的n元组,记作:(x1,x2,xn) 。,2. 一种新的集合运算 积运算 :,设A、B为两集合,用A中元素为第一元素,B中元素作为第二元素构成的二元有序组的全体叫做A和B的笛卡儿积。,记作:A B,符号化:A B = | xA y B,例4.1 设A=a,b,B=0,1,2 ,求AB,BA,解:根据笛卡儿积的定义知,A B = , , , ,B A = , , ,一般地:如果|A|=m,|B|=n,则 |AB|=|BA|=m n, , , , ,积运算的性质,(1) 若A,B中有一个空集,则笛卡儿积是空集,即: B = A = ,(2) 当AB,且A,B都不是空集时,有ABBA,(3) 当A,B,C都不是空集时,有(AB)C A(BC),因为(A
2、B)C中的元素, z,而A(BC)中的元素为 。,(4) A(BC) = (AB)(AC) (对的分配律),(BC)A = (BA)(CA),A(BC) = (AB)(AC),(BC)A = (BA)(C A),我们证明:,A(BC) = (AB)(AC),( ? ),( ? ),( ? ),证明思想,要证明两个集合相等,通常有两种方法:一是证两个集合相互包含;,二是利用已有的集合运算的性质(算律和已证明过的公式),仿照代数恒等式的证明方法,一步步从左(右)边推出右(左)边,或从左、右边分别推出同一个集合式子。,一般说来,最基本的集合相等关系要用第一种证法,比较复杂的集合相等关系用第二种方法更好,但第二种方法的使用取决于我们对算律和常用公式的熟练程度。,证明: 用第一种方法,对于任意的 A ( BC ), xAy(BC), xA(yByC ), (xAyB)(xAyC), ABAC, (AB)(AC), A(BC)=(AB)(AC),例4.2 设A=1,2,求P(A)A,解: P(A)A,= ,1,2,1,2,= ,,n阶笛卡儿积:,= (x1,x2, xn) | x1A1x2A2 x
3、nAn,A1 A2 An,1,2,,,,,,,二元关系:如果一个集合的元素都是二元有序组,则这个集合称为一个二元关系,记作:R 。,如果 R ,记作 x R y,3、二元关系的数学定义,从A到B的二元关系:设A,B为集合,A B的任何子集所定义的二元关系叫做从A到B的二元关系。,若A=B,叫做 A上的二元关系;,若|A|n,则|AA|n2。,就是说,A上有 个不同的二元关系,其中包括空关系、全域关系UA和恒等关系IA。,AA的所有子集有 个。,例4.3 设A = a,b,写出P(A)上的包含关系R :,解: P(A) = ,a,ba,b,R = , , , ,A上关系的表示法,1. 关系矩阵:,设A=x1, x2, , xn),R是A上的关系,,则 (rij)nxn =,是R的关系矩阵,令:,二、二元关系的表示方法,2. 关系图:,以E = | xiAxjAxiRxj为有向边集组成的有向图G = ,以V=A=x1, x2, xn 为顶点集,,例4.4 设A=1,2,3,4,R=,是A上的关系,试写出R的关系矩阵并画出关系图:,解: 关系矩阵 :,0 0 1 1,0 0 0 0,0 1
4、0 0,关系图 :,4.2 关系的运算,关系R的定义域: domR = x | (y)R (即R中有序组的第一个元素构成的集合),关系R的值域: ranR =y | (x)R (即R中有序组的第二个元素构成的集合),一、关系的定义域与值域,例4.5 下列关系都是整数集Z上的关系,分别求出它们的定义域和值域:,(1) R1= | x, y Z xy,(2) R2= | x, y Z x2+y2=1,(3) R3= | x, y Z y=2x,(4) R4= | x, y Z |x|=|y|=3,解: domR1 = ranR1 = Z,解: R2 = , ,domR2 = ( ? ),ranR2 = ( ? ),(1) R1= | x, y Z xy,(2) R2= | x, y Z x2+y2=1, ,解: domR3 = Z, ranR3 = 偶数,解: domR4 = ranR4 = ( ? ),(3) R3= | x, y Z y=2x,(4) R4= | x, y Z |x|=|y|=3,二、关系的常用运算,F是任意关系,F的逆F1= | yFx,F、G是任意两个关系,F与G的
《离散数学,二元关系与运算》由会员suns****4568分享,可在线阅读,更多相关《离散数学,二元关系与运算》请在金锄头文库上搜索。
土地管理与地籍测量---第八章界址点测量
人机工程学案例分析(2)
工程安全培训_201303
第9章房地产投资决策分析
第2章房地产经纪制度
ACM程序设计-东北林业大学acm05
《亲爱的汉修先生》读书交流会
中原_深圳新世界尖岗山项目市场汇报_40P_2012年_别墅_项目分析_量价走势
五年级数学质量分析演示文稿
人工智能小镇-智慧小镇建设20180525
景观基本知识及发展历程
建设工程信息管理(2)
机电驱动技术第二章步进驱动技术
工程力学-第9章圆轴扭转时的应力变形分析与强度刚度设计
第一章第二节幼儿园文化环境建设的原则
第一章检测技术的基础知识
第一章__现代表面工程技术
第六章钢结构工程
第9节项目试运行管理
班主任工作经验交流课件(4)
2023-12-11 28页
2023-12-11 28页
2023-12-11 27页
2023-12-11 31页
2023-12-11 27页
2023-12-11 27页
2023-12-11 33页
2023-12-11 28页
2023-12-11 26页
2023-12-11 29页