关系与序关系.ppt
《关系与序关系.ppt》由会员分享,可在线阅读,更多相关《关系与序关系.ppt(76页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、关系与序关系现在学习的是第1页,共76页2.1 2.1 关系的概念关系的概念例设A=Alice,Bob,Tom, B=Algebra,Graphs, Sets Alice选修了Graphs, Bob选修了Algebra, Graph和Sets; Tom选修了Algebra,Graphs;R=, AB, 表示了学生集合A与课程集合B之间的选修关系。现在学习的是第2页,共76页2.1 2.1 关系的概念关系的概念二元关系的一般性描述二元关系的一般性描述 一对对象之间的关系称为二元关系。 例例 teachers=a,b,c,students=x,y,z 建立教学关系 T: aTx iff a TEA
2、CHING x 用序偶集合表示为: T = , T teachers students 图示为:现在学习的是第3页,共76页2.1 2.1 关系的概念关系的概念 例例 Subroutines=a,b,c,d,e 子程序间调用关系图示为:Calling=, , Calling Subroutines Subroutines现在学习的是第4页,共76页2.1 2.1 关系的概念关系的概念二元关系的集合定义二元关系的集合定义 设X,Y是两个集合, X Y的任何一个子集 R 都确定了一种二元关系,称为从X到Y的二元关系。 R可记为 xRy,显然 R X Y R可记为 xRy当 X=Y 即 X 与 Y
3、同一时,称 R 为 X 上的一个二元关系。现在学习的是第5页,共76页2.1 2.1 关系的概念关系的概念例 F=| x是y的父亲 S=| x,y为正整数且x可整除y T=| y为实数v对上述的:x,y,R,有R 或 R,二者必居其一。现在学习的是第6页,共76页2.1 2.1 关系的概念关系的概念定义域定义域 设二元关系S。由 S的所有对象 x 组成的集合称为S的定义域,记为Dom(S) 。值域值域 由S的所有对象 y 组成的集合称为S的值域,记为Ran(S) (Range(S)。记 F(S) = D(S) R(S) ,称为 S 的域。v描述:Dom(S) = x| (y)(S) Ran(S
4、) = y| (x)(S)现在学习的是第7页,共76页2.1 2.1 关系的概念关系的概念v若干特殊关系: X 到Y 的全域关系: Ex,y = XY 特别地: Ex,x = XX 空关系: 恒等关系:Ix = |xiX例 设 X=1,2,3,4,求 X 上的关系 “ ”(大于)及其定义域、值域。现在学习的是第8页,共76页2.2 2.2 关系的表示方法关系的表示方法(1) 集合表示法 借用集合的各种描述方法对表示关系的序偶集合进行描述(2) 关系矩阵 设 X=x1,x2,xm,Y=y1,y2,yn,m,n + R是X到Y的二元关系。构造矩阵MR=mijmn, mij = R0 其它现在学习的
5、是第9页,共76页2.2 2.2 关系的表示方法关系的表示方法例非0行对应元素构成 D(S)非0列对应元素构成 R(S)101010011TeachingMaxbcyz现在学习的是第10页,共76页2.2 2.2 关系的表示方法关系的表示方法(3) 关系图表示法 用结点表示X、Y上的元素;若 R 则从结点x到结点y画一条弧。例 上述Teaching关系的关系图:现在学习的是第11页,共76页2.2 2.2 关系的表示方法关系的表示方法例 设 X=1,2,3,4,X 上的关系 “ ”:现在学习的是第12页,共76页2.3 2.3 关系的性质关系的性质定义定义 设R是X上的二元关系,则: R 是自
6、反的 (x)(xXxRx) R 是对称的 (x)(y)(x,yXxRyyRx) R 是传递的 (x)(y)(z)(x,y,zXxRyyRz xRz) R 是反自反的 (x)(xX(xRx) R 是反对称的 (x)(y)(x,yXxRyyRx x = y)现在学习的是第13页,共76页2.2 2.2 关系的性质关系的性质习题 设 X=1,2,3,4,画出X 上的关系 “ ”,“”和 整除“|”的关系图和关系矩阵,并判断其性质。习题 集合上的”is an element”以及”is a subset”具有什么性质?现在学习的是第14页,共76页2.3 2.3 关系的性质关系的性质例 正整数集合上的
7、若干关系及其性质整除=自反性对称性传递性反自反性反对称性 v判定关系“”的反对称性的前提条件总为F, 反对称性成立。现在学习的是第15页,共76页2.3 2.3 关系的性质关系的性质v从关系矩阵和关系图看关系的性质:R是自反的:MR的对角元均为1; 关系图为自环图。R是对称的:MR为对称矩阵; 关系图中弧成对出现。R是反自反的:MR的对角元均为0; 关系图为无自环图。R是反对称的:MR为反对称矩阵; 关系图中只出现单向弧。现在学习的是第16页,共76页2.3 2.3 关系的性质关系的性质存在着既非自反也非反自反的关系,如:0101存在着既对称又反对称的关系,如:100010001现在学习的是第
8、17页,共76页2.3 2.3 关系的性质关系的性质存在着既非对称又非反对称的关系,如:111100001现在学习的是第18页,共76页2.4 2.4 集合的划分与覆盖集合的划分与覆盖定义定义 给定集合S,A=A1,A2,An,AiS,i=1.n。1ASAS;,nii 若有则说 是 的一个覆盖 若成立且AiAj = (若ij),则说A是S的一个 划分,并称 A1,A2,An为此划分的块。现在学习的是第19页,共76页2.4 2.4 集合的划分与覆盖集合的划分与覆盖例 N=0,1,2,3,4, 自然数集合。 取 A0=0,6,12,18, A1=1,7,13,19, A2=2,8,14,20,
9、A5=5,11,17,23, 则 A=A0, A1, A2, A3, A4, A5是N的一个划分。现在学习的是第20页,共76页2.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 称为最小划分。现在学习的是第21页,共76页 关系IX 具有自反、对称和传递性; 设 X=1,2,3,4,写出X上的模同余关系,并判断其是否具有自反、对称和传递等性质。 具有自反、对称和传递性的关系称为等价关系。现在学习的是第22页,共76页2.5 2.
10、5 等价关系等价关系等价关系等价关系 集合X上的关系R若具有自反性、对称性和传递性,则称R为X上的一个等价关系。例 N上的模6同余关系 R=|x,yN (xy)=6L,L为整数 自反性: 对称性: 传递性:现在学习的是第23页,共76页2.5 2.5 等价关系等价关系定理定理 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) 故 xRz现在学
11、习的是第24页,共76页2.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=3,6现在学习的是第25页,共76页2.5 2.5 等价关系等价关系性质性质 设R为X上的一个等价关系,则 X中的任何一个元素,至少属于一个等价类。 若x,yX,则x,y或属同一等价类,或属两个不同等价类但此两个不同等价类的交集为(不相交)。证明现在学习的是第26页,共76页2.5 2.5 等价
12、关系等价关系结论结论 对X上的等价关系R, 任意xX属于且只属于一个等价类; 若xRy,则xR = yR ,否则 xR yR = 。现在学习的是第27页,共76页2.5 2.5 等价关系等价关系定理定理 集合X上的一个等价关系R产生对此集合的一个划分,该划分的块对应于R的等价类。 证明 由上述结论得到。v将该划分记作:X/R=xR|xX现在学习的是第28页,共76页2.5 2.5 等价关系等价关系定理定理 X上的任意划分均可确定一个等价关系。证明 设X上的一个划分为 A=A1, A2, An,定义 R=|x,yX(Ai)(AiAxAiyAi) 可以证明R具有 自反性: 对称性: 传递性:现在学
13、习的是第29页,共76页2.5 2.5 等价关系等价关系问题X上由不同方法定义的等价关系R1、R2,若产生的等价类相同,则R1=R2。不等价关系也能产生划分。现在学习的是第30页,共76页2.6 2.6 相容关系相容关系相容关系相容关系 X上的二元关系R,若R是自反的、对称的,则称R为X上的一个相容关系,记作 。例 X=2661,243,315,648,455 R=|x,yX,x与y至少含有一个相同数字 容易看出,R具有自反性、对称性。 R不具有传递性: 如 ,R 但 R 因此R不是等价关系,R是一个相容关系。现在学习的是第31页,共76页2.6 2.6 相容关系相容关系相容类相容类 设 A
14、X, 是X上的一个相容关系。称A是X上的一个相容类当且仅当A中任二元素相容。即 (x)(y)(x,yA x y)。最大相容类最大相容类 设 A是X上的一个相容类,若X-A中不存在与A中所有元素相容的元素,则称A为X的一个最大相容类。在相容关系的关系图中,最大相容类对应于一个最大完全子图。现在学习的是第32页,共76页2.6 2.6 相容关系相容关系例如,在上图表示的相容关系中,最大相容类为: a, b, d , f, d, c ,f, d, e, g问题相容类与覆盖的关系。现在学习的是第33页,共76页2.7 2.7 关系的运算关系的运算(1) 关系的一般运算关系的一般运算定义定义 设 R、S
15、是X到Y的二元关系,定义运算如下: RS=|xRyxSy RS=|xRyxSy RS=|xRyxSy R=XYR现在学习的是第34页,共76页2.7 2.7 关系的运算关系的运算(2) 关系的复合运算关系的复合运算复合关系复合关系 设二元关系R:XY,S:YZ,则称 S R=|xXzZ(y)(yYxRyySz) 为R和S的复合关系。v注意, 关系的复合运算定义和函数复合保持了一致。在某些课本上,以上关系的复合记作R S。现在学习的是第35页,共76页2.7 2.7 关系的运算关系的运算例 X=x1, x2, x3,Y=y1, y2, y3, y4,Z=z1, z2, z3 R=, S= ,v
16、显然有:Dom(S R) Dom(R) Ran (S R) Ran(S) S R=,现在学习的是第36页,共76页2.7 2.7 关系的运算关系的运算v关系的复合运算没有交换律。定理定理 关系复合运算的结合律:设二元关系 R:XY,S:YZ, P:ZW, 则有 (P S) R= P (S R)证明现在学习的是第37页,共76页2.7 2.7 关系的运算关系的运算定理定理 关系复合运算与一般运算的结合律:设二元关系R1, R2 :XY, S1 , S2:YZ,则有(S1 S2) R1 =(S1 R1)(S2 R1) (S1S2)R1 (S1R1)(S2R1)S1 (R1R1) =(S1R1)(S
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 关系
限制150内