书签 分享 收藏 举报 版权申诉 / 70
上传文档赚钱

类型第2章关系与序关系课件.ppt

  • 上传人(卖家):晟晟文业
  • 文档编号:4642756
  • 上传时间:2022-12-28
  • 格式:PPT
  • 页数:70
  • 大小:231KB
  • 【下载声明】
    1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
    2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
    3. 本页资料《第2章关系与序关系课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
    4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
    5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
    配套讲稿:

    如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

    特殊限制:

    部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

    关 键  词:
    关系 课件
    资源描述:

    1、1第二章第二章 关系与序关系关系与序关系2.1 2.1 关系的概念关系的概念二元关系 一对对象之间的关系称为二元关系。22.1 2.1 关系的概念关系的概念 例例 teachers=a,b,c,students=x,y,z 建立教学关系 T:aTx iff a TEACHING x 用序偶集合表示为:T=,T teachers students 图示为:32.1 2.1 关系的概念关系的概念 例例 Subroutines=a,b,c,d,e 子程序间调用关系 Calling=,Calling Subroutines Subroutines 图示为:42.1 2.1 关系的概念关系的概念二元关系

    2、的集合定义二元关系的集合定义 任何一个序偶的集合 R=|xXyY 都确定了一种二元关系,称为从X到Y的二元关系。R可记为 xRy,显然 R X Y R可记为 xRy当 X=Y 即 X 与 Y 同一时,称 R 为 X 上的一个二元关系。从X到Y的任何二元关系,都可用一个序偶集合来表示:R=|xXyYxRy52.1 2.1 关系的概念关系的概念例 F=|x是y的父亲 S=|x,y为正整数且x可整除y T=|y为实数62.1 2.1 关系的概念关系的概念定义域定义域 设二元关系S。由 S的所有对象 x 组成的集合称为S的定义域,记为Dom(S)。值域值域 由S的所有对象 y 组成的集合称为S的值域,

    3、记为Ran(S)(Range(S)。记 F(S)=D(S)R(S),称为 S 的域。v描述:Dom(S)=x|(y)(S)Ran(S)=y|(x)(S)72.1 2.1 关系的概念关系的概念v若干特殊关系:X 到Y 的全域关系:Ex,y=XY 特别地:Ex,x=XX 空关系:恒等关系:Ix=|xiX例 设 X=1,2,3,4,求 X 上的关系“”(大于)及其定义域、值域。82.2 2.2 关系的表示方法关系的表示方法(1)集合表示法 借用集合的各种描述方法对表示关系的序偶集合进行描述(2)关系矩阵 设 X=x1,x2,xm,Y=y1,y2,yn,m,n+R是X到Y的二元关系。构造矩阵MR=mi

    4、jmn,mij=1 R0 其它92.2 2.2 关系的表示方法关系的表示方法例非0行对应元素构成 D(S)非0列对应元素构成 R(S)101010011TeachingMaxbcyz102.2 2.2 关系的表示方法关系的表示方法(3)关系图表示法 用结点表示X、Y上的元素;若 R 则从结点x到结点y画一条弧。例 上述Teaching关系的关系图:112.2 2.2 关系的表示方法关系的表示方法例 设 X=1,2,3,4,X 上的关系“”:122.3 2.3 关系的性质关系的性质定义定义 设R是X上的二元关系,则:R 是自反的(x)(xXxRx)R 是对称的(x)(y)(x,yXxRyyRx)

    5、R 是传递的(x)(y)(z)(x,y,zXxRyyRz xRz)R 是反自反的(x)(xX(xRx)R 是反对称的(x)(y)(x,yXxRyyRx x=y)132.3 2.3 关系的性质关系的性质例 整数集合上的若干关系及其性质整除=自反性对称性传递性反自反性反对称性 v判定关系“”的反对称性的前提条件总为F,理论上反对称性成立。142.3 2.3 关系的性质关系的性质存在着既非自反也非反自反的关系,如:0101存在着既对称又反对称的关系,如:100010001152.3 2.3 关系的性质关系的性质存在着既非对称又非反对称的关系,如:111100001162.3 2.3 关系的性质关系的

    6、性质v从关系矩阵和关系图看关系的性质:R是自反的:MR的对角元均为1;关系图为自环图。R是对称的:MR为对称矩阵;关系图中弧成对出现。R是反自反的:MR的对角元均为0;关系图为无自环图。R是反对称的:MR为反对称矩阵;关系图中只出现单向弧。172.4 2.4 集合的划分与覆盖集合的划分与覆盖定义定义 给定集合S,A=A1,A2,An,AiS,i=1.n。1ASAS;,nii 若有则说 是 的一个覆盖 若成立且AiAj=(若ij),则说A是S的一个 划分,并称 A1,A2,An为此划分的块。182.4 2.4 集合的划分与覆盖集合的划分与覆盖例 N=0,1,2,3,4,自然数集合。取 A0=0,

    7、6,12,18,A1=1,7,13,19,A2=2,8,14,20,A5=5,11,17,23,则 A=A0,A1,A2,A3,A4,A5是N的一个划分。192.4 2.4 集合的划分与覆盖集合的划分与覆盖例 S=a,b,c 取 A=a,b,c B=a,b,c C=a,b,c 均构成对S的划分。显然有|A|B|C|可以将 A 称为最大划分;将 C 称为最小划分。202.5 2.5 等价关系等价关系等价关系等价关系 集合X上的关系R若具有自反性、对称性和传递性,则称R为X上的一个等价关系。例 N上的模6同余关系 R=|x,yN (xy)=6L,L为整数 自反性:对称性:传递性:212.5 2.5

    8、 等价关系等价关系定理定理 N上的模m同余关系是等价关系。证明 自反性:xx=0,故 xx=mL,这里L=0。对称性:设 xRy 即 xy=mL,L为整数 则 yx=mL,故 yRx。传递性:设 xRy 且 yRz,即 xy=mL1,yz=mL2,L1、L2 为整数 则 xz=mL1+mL2=m(L1+L2)故 xRz222.5 2.5 等价关系等价关系等价类等价类 设R为X上的一个等价关系,对任何xX,所有与x有关系R的元素的集合,称为X上由x生成的R等价类。记为 xR。xR=y|yX xRy例 X=1,2,3,4,5,6,7,R为X上的模3同余关系。则 1R=1,4,7,2R=2,5,3R

    9、=3,6232.5 2.5 等价关系等价关系性质性质 设R为X上的一个等价关系,则 X中的任何一个元素,至少属于一个等价类。若x,yX,则x,y或属同一等价类,或属两个不同等价类但此两个不同等价类的交集为(不相交)。证明242.5 2.5 等价关系等价关系结论结论 对X上的等价关系R,任意xX属于且只属于一个等价类;若xRy,则xR=yR,否则 xR yR=。252.5 2.5 等价关系等价关系定理定理 集合X上的一个等价关系R产生对此集合的一个划分,该划分的块对应于R的等价类。证明 由上述结论得到。v将该划分记作:X/R=xR|xX262.5 2.5 等价关系等价关系定理定理 X上的任意划分

    10、均可确定一个等价关系。证明 设X上的一个划分为 A=A1,A2,An,定义 R=|x,yX(Ai)(AiAxAiyAi)可以证明R具有 自反性:对称性:传递性:272.5 2.5 等价关系等价关系讨论X上由不同方法定义的等价关系R1、R2,若产生的等价类相同,则R1=R2。不等价关系也能产生划分。282.6 2.6 相容关系相容关系相容关系相容关系 X上的二元关系R,若R是自反的、对称的,则称R为X上的一个相容关系,记作 。例 X=2661,243,315,648,455 R=|x,yX,x与y至少含有一个相同数字 容易看出,R具有自反性、对称性。R不具有传递性:如,R 但 R 因此R不是等价

    11、关系,R是一个相容关系。292.6 2.6 相容关系相容关系相容类相容类 设 Ai X,是X上的一个相容关系。称Ai是X上的一个相容类当且仅当Ai中任二元素相容。即(x)(y)(x,yAi x y)。最大相容类最大相容类 设 Ai是X上的一个相容类,若X-Ai中不存在与Ai中所有元素相容的元素,则称Ai为X的一个最大相容类。最大相容类不一定是含有最多元素个数的相容类在相容关系的关系图中,最大相容类对应于一个最大完全子图。302.7 2.7 关系的运算关系的运算(1)关系的一般运算关系的一般运算定义定义 设 R、S是X到Y的二元关系,定义运算如下:RS=|xRyxSy RS=|xRyxSy RS

    12、=|xRyxSy R=XYR312.7 2.7 关系的运算关系的运算(2)关系的复合运算关系的复合运算复合关系复合关系 设二元关系R:XY,S:YZ,则称 RS=|xXzZ(y)(yYxRyySz)为R和S的(右)复合关系,或(右)复合运算结果。v注意关系的复合运算定义中的右复合和左复合给出的构造定义不同:右复合 RS 中右边的S在R之后进行第二步复合构造。在函数理论中,与右复合函数 S*R对应:S*R=RS 即 S*R(x)=S(R(x)322.7 2.7 关系的运算关系的运算例 X=x1,x2,x3,Y=y1,y2,y3,y4,Z=z1,z2,z3 R=,S=,v 显然有:Dom(RS)D

    13、om(R)Ran(RS)Ran(S)RS=,332.7 2.7 关系的运算关系的运算v关系的复合运算没有交换律。定理定理 关系复合运算的结合律:设二元关系 R:XY,S:YZ,P:ZW,则有 (RS)P=R(SP)证明342.7 2.7 关系的运算关系的运算定理定理 关系复合运算与一般运算的结合律:设二元关系R1:XY,R2,R3:YZ,R4:ZW,则有R1(R2R3)=(R1R2)(R1R3)R1(R2R3)(R1R2)(R1R3)(R2R3)R4=(R2R4)(R3R4)(R2R3)R4(R2R4)(R3R4)证明按照定义转换为逻辑运算,证明逻辑等值式。352.7 2.7 关系的运算关系的

    14、运算关系的幂运算 设R为X上的二元关系,RRR 记为Rn,规定 Rn=Rn1R,R0=IX362.7 2.7 关系的运算关系的运算(3)关系的逆运算关系的逆运算逆关系逆关系 设二元关系 R:XY,定义 R-1=|xXyYR 为R的逆关系。性质性质(R-1)-1=R(RS)-1=R-1S-1(RS)-1=S-1R-1 (RS)-1=R-1S-1 R=S R-1=S-1(R)-1=(R-1)RS R-1S-1-1=372.7 2.7 关系的运算关系的运算(3)关系的逆运算关系的逆运算逆关系逆关系 设二元关系 R:XY,定义 R-1=|xXyYR 为R的逆关系。性质性质(R-1)-1=R,-1=(R

    15、S)-1=R-1S-1,(RS)-1=R-1S-1(R)-1=(R-1)(RS)-1=S-1R-1 R=S R-1=S-1 RS R-1S-1382.7 2.7 关系的运算关系的运算(4)关系的闭包运算关系的闭包运算闭包闭包 设R为X上的二元关系,若另有一关系R,满足:R 是自反的;R R;对于任何自反(对称/传递)的关系R,若 R R,则R R 。则称 R为R的自反(对称/传递)闭包,记为r(R)(s(R)/t(R)。392.7 2.7 关系的运算关系的运算例 整数集上的“”关系的自反闭包是“”,对称闭包是“”,传递闭包仍然是“”。例 整数“=”的自反、对称、传递闭包都是它本身。例 有关系矩

    16、阵101000011RM 求 Mr(R)、Ms(R)、Mt(R)402.7 2.7 关系的运算关系的运算101000011RM101010011r RM()101001111s RM()111000011t RM()412.7 2.7 关系的运算关系的运算定理定理 设R为X上的二元关系,则 r(R)=RIx s(R)=RR-11()iit RR证明 422.8 2.8 偏序关系偏序关系偏序关系偏序关系 集合A上的一个关系R满足自反性、反对称性和传递性时,称R是A上的一个偏序关系,记为“”,用二元组A,表示该偏序结构,或称之为偏序集。例 A=2,3,6,8,“”=|x,yA(x整除y)“”=.容

    17、易验证,上述关系为偏序关系。432.8 2.8 偏序关系偏序关系vx、y之间存在偏序关系时,说 x、y(在该关系下)可比较,否则说 x、y 不可比较。上例中,2和3不可比较(在上述定义的“”下)。盖住盖住 盖住(紧邻遮盖)。设A,,x,yA,y盖住x xyxy(z)(xzzy)(x=zy=z)记 covA=|x,yA(y盖住x)442.8 2.8 偏序关系偏序关系v表达偏序关系的 Hasse图 设有偏序关系 用结点表示集合元素 若 covA,则用线段连接结点x,y,且令x(小者)在y的下方。452.8 2.8 偏序关系偏序关系例例 Hasse图如右图 默认aa,bb,cc ac,cb ab a

    18、 c bHasse Diagramv 由画法可见:自反关系为默认;反对称关系体现在“上”、“下”位置上;由上到下的可达性表达了传递性。462.8 2.8 偏序关系偏序关系v上述Hasse图表示的对应关系集合为:,对应关系图如下:a c bHasse Diagram a c b关系图472.8 2.8 偏序关系偏序关系例例 由偏序关系的关系图构造相应的Hasse图 c a b关系图 d a b cHasse Diagram d482.8 2.8 偏序关系偏序关系例例 2,3,6,12,24,36上的整除关系的Hasse图。2 6 24Hasse Diagram 36 12 3492.8 2.8

    19、偏序关系偏序关系例例 A的幂集上的关系的Hasse图。A=a a a,bA=a,bba 502.8 2.8 偏序关系偏序关系例例 A的幂集上的关系的Hasse图。a,b,cA=a,b,cba c a,b a,c b,c512.8 2.8 偏序关系偏序关系最大最小元最大最小元 对偏序集 y0A为最小元 (x)(xAy0 x)y0A为最大元 (x)(xAxy0)定理定理 中最大(最小)元若存在则唯一。证明极大极小元极大极小元 对 y0A为极小元 (x)(xAxy0(x y0)y0A为极大元 (x)(xAxy0(y0 x)522.8 2.8 偏序关系偏序关系例 2,3,6,12,24,36上的整除关

    20、系的Hasse图。2 6 24 36 12 3 2,3 为极小元 24,36 为极大元 没有最小元和最大元532.8 2.8 偏序关系偏序关系例 A的幂集上的关系的Hasse图。a,b,cA=a,b,cba c a,b a,c b,c 为最小元 a,b,c 为最大元542.8 2.8 偏序关系偏序关系上下界上下界 对,BA,aA a是B的一个上界 (x)(xBx a)a是B的一个下界 (x)(xBa x)v说明:a不一定是B的元素,即可能 aA-BB的上(下)界不一定存在,存在也不一定唯一。552.8 2.8 偏序关系偏序关系例 2,3,6,12,24,36上的整除关系的Hasse图。2 6

    21、24 36 12 3令B1=2,3,6 B1的上界是 6,12,24,36 6B1,而12,24,36B1 B1没有下界令B2=2,6,12,24 B2的上界是24,下界是2562.8 2.8 偏序关系偏序关系上确界上确界 对,BA,aA是B的一个上界。a是B的上确界 (y)(y是B的上界a y)上确界若存在则唯一。下确界下确界 对 ,BA,bA是B的一个下界。b是B的下确界 (x)(x是B的下界x b)下确界若存在则唯一。572.8 2.8 偏序关系偏序关系例例 2,3,6,12,24,36上的整除关系的Hasse图。2 6 24 36 12 3令B1=2,3,6 B1的上界是 6,12,2

    22、4,36 B1的上确界是 6 B1没有下界也没有下确界令B2=2,6,12,24 B2的上界和上确界是24 B2的下界和下确界是2582.8 2.8 偏序关系偏序关系链与反链链与反链 对,BA,若B中任两个元素之间都是可比较的,则称B是A中的一条链。若B中任两个元素之间都是不可比较的,则称B是A中的一条反链。2 6 24 36 12 3例 右边所示Hasse图中,2,6,12,24 是一条链 2,3和24,36是反链v注意:2,3,24,36并非反链592.8 2.8 偏序关系偏序关系例 在正整数上定义关系R:R iff x和y的最大公因子是1。讨论R 的关系性质。解 自反性:的最大公因子是2

    23、,故 R 即 R非自反;对称性:成立;传递性:R 且 R 但 R 即R非 传递;反对称性:R 且 R 故R非反对称。602.8 2.8 偏序关系偏序关系例 设关系R定义在所有8bits字符构成的集合上:若字符char1和char2的前4bits相同,则它们之间有关系R。证明R是一个等价关系;共有多少个等价类?列出每个等价类的一个成员。解 证明R是自反的、对称的和传递的;等价类数目:24=16;0000,0001,0010,0011,1110,1111612.9 2.9 其他次序关系其他次序关系(1)全序关系全序关系全序关系全序关系 设偏序集,若A是一条链,则称“”为A上的一个全序关系,此时称

    24、是一个全序集合。(2)偏序关系的逆关系偏序关系的逆关系定义定义 设偏序集 ,定义A上的关系“”xy x,yAyx 集合A和关系“”仍然构成一个偏序集。622.9 2.9 其他次序关系其他次序关系(3)拟序关系拟序关系拟序关系拟序关系 集合A上的关系R满足反自反性和传递性时,称为A上的一个拟序关系,用二元组 A,表示该结构。v拟序关系是反对称的,也称为严格偏序关系。定理定理 若R为A上的偏序关系,则R-IA为A上的拟序关系。若R为A上的拟序关系,则RIA为A上的偏序关系。632.9 2.9 其他次序关系其他次序关系定理定理 设有拟序集 A,,对任何 x,y,zA,xy,x=y,yx 中至多有一种

    25、情况成立(三分律);xyx 则 x=y,这里 xy 表示 xy 或 x=y。证明 利用拟序集的反自反性和传递性。642.9 2.9 其他次序关系其他次序关系(4)(4)词典次序词典次序v设字母表为X,“”为X上的自然次序。显然 为全序集合。长度为2的词库 A=X X 在A上定义全序关系S:S (x1x2)(x1=x2y1y2)S S 652.9 2.9 其他次序关系其他次序关系 长度不大于n的词库 A=XX2.Xn 在A上定义全序关系S:设,A,其中pqn。S 当且仅当下列三个条件之一得到满足:()=()x1y1且在X中有x1y1 ()xi=yi,i=1.k,kp,xi+1yi+1且在X中有

    26、xi+1yi+1 否则 S662.9 2.9 其他次序关系其他次序关系(5)(5)格格格 设偏序集合,若其中任何二个元素在A中都有上、下确界,则称 为一个格。例 如下的Hasse 图描述了三个格:672.9 2.9 其他次序关系其他次序关系例 如下的Hasse 图描述的不是格:(没有下确界)例,I+正整数,a“”b iff a 整除 b。任何 x,yI+,其上确界为其最小公倍数,下确界为其最大公约数,均存在于I+中。故 为格。682.9 2.9 其他次序关系其他次序关系上下确界上下确界 设 为格,对任意 a,bA,记 a,b的上确界元素为ab,下确界元素为ab。性质性质 设 为格,对任意 a,b,c,dA,有 a ab,ab a 若 a b,c d,则 ac bd,ac bd ab=ba,ab=ba (交换律)a(bc)=(ab)c,a(bc)=(ab)c(结合律)a(ab)=a,a(ab)=a (吸收律)692.9 2.9 其他次序关系其他次序关系(6)(6)良序集合良序集合良序集合良序集合 设偏序集合 ,若其任意非空子集都在该子集中存在最小元,则称 为良序集合。例 如图的偏序集不是良序集。702.9 2.9 其他次序关系其他次序关系定理定理 每个良序集合本身也是一个全序集合。有限阶的全序集合是一个良序集合。证明

    展开阅读全文
    提示  163文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    关于本文
    本文标题:第2章关系与序关系课件.ppt
    链接地址:https://www.163wenku.com/p-4642756.html

    Copyright@ 2017-2037 Www.163WenKu.Com  网站版权所有  |  资源地图   
    IPC备案号:蜀ICP备2021032737号  | 川公网安备 51099002000191号


    侵权投诉QQ:3464097650  资料上传QQ:3464097650
       


    【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。

    163文库