资源预览内容
第1页 / 共141页
第2页 / 共141页
第3页 / 共141页
第4页 / 共141页
第5页 / 共141页
第6页 / 共141页
第7页 / 共141页
第8页 / 共141页
第9页 / 共141页
第10页 / 共141页
亲,该文档总共141页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第四章 二元关系主要内容:关系的概念及表示方法 关系的性质关系的运算:关系的复合,求逆关系,关系的闭包。三种关系: 等价关系,相容关系, 次序关系。 Date1一、序偶与有序n元组1.定义:由两个对象x、y组成的序列称为有序二元 组,也称之为序偶,记作;称x、y分别为 序偶的第一,第二元素。注意,序偶与集合x,y不同: 序偶:元素x和y有次序; 集合x,y:元素x和y的次序无关紧要。4-1 序偶与集合的笛卡尔积Date22.定义:设,是两个序偶,如果x=u和y=v则称和相等,记作=。3 .定义:有序3元组是一个序偶,其第一个元 素也是个序偶。 有序3元组, c可以简记成 , 但不是有序3元 组。 Date34.定义:有序n元组是一个序偶,其第一个元素本身是个有序n-1元组,记作, xn。且可以简记成。5. 定义=( x1= y1) ( x2= y2) ( xn= yn)Date4例如“斗兽棋”的16颗棋子, 豹猫虎象狮狗鼠虎象狮豹狼鼠猫狗狼设:A=红,蓝B=象,狮,虎,豹,狼,狗,猫,鼠 每个棋子可以看成一个序偶,斗兽棋可记成集合AB : , , , , Date51.定义:设A、B是集合,由A的元素为第一元素,B 的元素为第二元素组成序偶的集合,称为A和B 的笛卡尔积,记作AB,即AB=|xAyB例1 设A=0,1,B=a,b,求AB , BA, AA 。解: AB=,BA=,AA=, 可见 ABBA 所以,集合的笛卡尔积运算不满足交换律。Date6v另外 (AB)C=,c|AB cCA(BC)=|aA BC,因 不是有序三元组,所以(AB)CA(BC)。故也不满足结合律。2.性质1) 如果A、B都是有限集,且|A|=m, |B|=n,则 |AB |=mn。 证明:由笛卡尔积的定义及排列组合中的乘法 原理,直接推得此定理。2) A=B= Date73) 对和满足分配律。设A,B,C是任意集合,则 A(BC)= (AB)(AC); A(BC)= (AB)(AC); (AB)C= (AC)(BC); (AB)C= (AC)(BC);证明 :任取A(BC) xA yBC xA(yByC) ( xA yB)(xAyC)ABAC (AB)(AC) 所以式成立。(其余可以类似证明)Date84) 若C, 则 AB(ACBC) (CACB) 证明:充分性: 设AB,求证 ACBC任取AC xAyC xByC (因AB)BC 所以, ACBC。必要性:若C, 由ACBC 求证 AB 取C中元素y, 任取 xAxAyC ACBC (由ACBC )xByC xB 所以, AB。所以 AB(ACBC)类似可以证明 AB (CACB)。Date95) 设A、B、C、D为非空集合,则ABCDACBD 证明:首先,由ABCD 证明ACBD任取xA,任取yB,所以 xAyBABCD (由ABCD )xCyD 所以, ACBD。其次, 由AC,BD 证明ABCD任取AB xAyB xCyD (由AC,BD)CD 所以, ABCD 证毕。Date106)约定 (A1A2)An-1)An)=A1A2An 特别 AAA = An v设R是实数集合,则R2表示笛卡尔坐标平面,R3表示三维空间,Rn表示n维空间。3. 应用1)令A1=x|x是学号 A2=x|x是姓名 A3=男,女A4=x|x是出生日期 A5=x|x是班级 A6 =x|x是籍贯 则A1A2A3 A4A5 A6中一个元素:这就是学生档案数据库的一条信息,所以学生的档 案就是A1A2A3 A4A5 A6的一个子集。Date112) 令A=a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v, w,x,y,z 是英文字母表一个英文单词可以看成有序n元组:如 at=, boy=, data=, computer=于是可以说:atA2 ,boyA3,dataA4,computerA8,所以英文词典中的单词集合可以看成是AA2An 的一个子集。作业 P105 Date124-2 关系及其表示法相关 按照某种规则,确认了二个对象或多个 对象之间有关系,称这二个对象或多个对象是相 关的。例1: 大写英文字母与五单位代码的对应关系R1:令=A,B,C,D,Z=30,23,16,22,21是五单位代码集合=11000, 10011, 01110, 10010, 10001R1=,.,Date13例2:令=1,2,3,4, A中元素间的关系R2 : R2= , , ,AA关系的定义定义1: 设A、是集合,如果AB,则称R是一 个从A到B的二元关系。如果 RAA,则称R是A上 的二元关系。二元关系简称为关系。定义2: 任何序偶的集合,都称之为一个二元关系 。如:R=,基本概念基本概念Date148R xRy 也称之为x与y有关系。 后缀表示中缀表示8R xRy 也称之为x与y没有关系。例3. R是实数集合,R上的几个熟知的关系x2+y2=4=xyv 从例3中可以看出关系是序偶(点)的集合( 构成线、面)。Date15关系的定义域与值域 定义域(domain):设RAB,由所有R的第 一个元素组成的集合,称为R的定义域。记作dom R,即 dom R=x|y(R) 值域(range):设RAB,由所有R的第二 个元素组成的集合,称为R的值域。记作ran R,即 ran R=y|x(R) 令: R1= , , , , , dom R1 =1,2,3,4ran R1 =1,2,3,4Date16 枚举法:即将关系中所有序偶一一列举出,写在大括号内。 如R = , , , , , , , 。 谓词公式法:即用谓词公式表示序偶的第一元素与第二元素间 的关系。例如 R=|xR时,从x到y引一条有向弧(边 )。这样得到的图形称为R的关系图。关系的表示方法关系的表示方法Date17例 设A=1,2,3,4,B=a,b,c, R1 AB,R2 AA,R1 = ,R2 = ,R2 :3214AB abc1234R1 :R1 、R2的关系图如下:Date18 矩阵表示法:设A=a1, a2, , am,B=b1, b2, , bn是个有限 集, RAB,定义R的mn阶矩阵 MR=(rij)mn,其中1 若R0 若R(1im,1jn)rij=例:R1= , R2= ,1 0 1 0 1 0 1 0 0 0 0 1431 2 3 4a b c上例中 MR1 =MR2=1 0 0 1 0 0 1 01 1 0 01 0 0 1441 2 3 41 2 3 4Date19 空关系:因为AB,(或AA),所以也是一个从 A到B(或A上)的关系,称之为空关系。即无任何元素的关系,它的关系图中只有结点,无 任何边;它的矩阵中全是0。 完全关系(全域关系) :AB(或AA)本身也是一个从A到B(或A上) 的关 系,称之为完全关系。即含有全部序偶的关系。它的矩阵中全是1。三个特殊关系三个特殊关系Date20 A上的恒等关系IA:IAAA,且IA =|xA为A上的恒等关系。 例如例如 A=1,2,3, 则IA =, A上的、完全关系及IA的关系图及矩阵如下: 1 1 1 1 1 1 1 1 133MAA=1。2。31。2。31。2。3 AA IAMIA =1 0 0 0 1 0 0 0 1330 0 0 0 0 0 0 0 033M=Date21v 由于关系就是集合,所以集合的、-、 和运算对关系也适用。 例如 A是学生集合,R是A上的同乡关系,S是A上 的同姓关系,则 RS:或同乡或同姓关系 RS:既同乡又同姓关系 R-S :同乡而不同姓关系 RS:同乡而不同姓,或同姓而不同乡关系 R:不是同乡关系, 这里R=(AA)-R作业 P109 、c)d)关系的集合运算关系的集合运算Date22v本节中所讨论的关系都是集合A中的关系。 v关系的性质主要有:自反性、反自反性、对称性 、反对称性和传递性。 一. 自反性 定义:设R是集合A中的关系,如果对于任意xA都 有R (xRx),则称R是A中自反关系。即 R是A中自反的关系x(xAxRx)例如:在实数集合中,“”是自反关系,因 为,对任意实数x,有x x. 4-3 关系的性质Date23v从关系有向图看自反性:每个结点都有环。 v从关系矩阵看自反性:主对角线都为1。 令A=1,2,3,确定以下八个关系中哪些是自反的?1。2。3 R21 。2。3 R11。2。3 R31 。2。3 R41。2。3 R51 。2。3R61。2。3R71。2。3R8Date24二.反自反性 定义:设R是集合A中的关系,如果对于任意的 xA都有R ,则称R为A中的反自反关系。即 R是A中反自反的x(xAR) v 从关系有向图看反自反性:每个结点都无环。 v 从关系矩阵看反自反性:主对角线都为0。 如 实数的大于关系,父子关系是反自反的。 注意:一个不是自反的关系,不一定就是反自反 的,如前边R6、R7非自反,也非反自反。Date25R2、R5、 R8、均是反自反关系。1。2。3 R21 。2。3 R11。2。3 R31 。2。3 R41。2。3 R51 。2。3R61。2。3R71。2。3R8观察下图:Date26三.对称性 定义:R是集合A中关系,若对任何x, yA,如果有 xRy,必有yRx,则称R为A中的对称关系。R是A上对称的xy(xAyAxRy) yRx) v从关系有向图看对称性:在两个不同的结 点之间,若有边的话,则有方向相反的两 条边。 v从关系矩阵看对称性:以主对角线为对 称的矩阵。 例 邻居关系和朋友关系是对称关系。Date271。2。3 R21 。2。3 R11。2。3 R31 。2。3 R41。2。3 R51 。2。3R61。2。3R71。2。3R8R3、R4、 R6 、 R8均是对称关系。Date28四.反对称性 定义:设R为集合A中关系,若对任何x, yA,如果有 xRy,和yRx,就有x=y,则称R为A中反对称关系 。RR是A上反对称的xy(xAyAxRyyRx) x=y)xy(xAyAxyxRy)y x) (P112) v 由R的关系图看反对称性:两个不同的
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号