《关系与序关系》PPT课件.ppt

《《关系与序关系》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《关系与序关系》PPT课件.ppt（81页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、 的定义域，记为 Dom(S)或Domain(S)。值域值域 设二元关系 S。由S 的所有对象 y 组成的集合称为 S 的值域，记为 Ran(S)或 Range(S)。域域 设二元关系 S。记 F(S)=Dom(S)Ran(S)，称为 S 的域。v描述：Dom(S)=x|(y)(S)Ran(S)=y|(x)(S)72.1 关系的概念关系的概念v若干特殊关系：X 到Y 的全域关系：Ex,y=XY 特别地：Ex,x=XX 空关系：X 上的恒等关系：Ix=|xiX例 设 X=1,2,3,4，求 X 上的关系“”(大于)及其定义域、值域。82.2 关系的表示方法关系的表示方法(1)集合表示法集合表示法

4、 借用集合的各种描述方法对表示关系的序偶集合进行描述(2)关系矩阵关系矩阵 设 X=x1,x2,xm，Y=y1,y2,yn，m,n+R 是 X 到 Y 的二元关系。称矩阵MR=mijmn，mij=1R0 其它为X到Y的关系矩阵。92.2 关系的表示方法关系的表示方法例例非0行对应元素构成 Dom(S)非0列对应元素构成 Ran(S)102.2 关系的表示方法关系的表示方法(3)关系图表示法关系图表示法 用结点表示 X、Y 上的元素；若 R 则从结点 x 到结点 y 画一条弧。例例 上述 Teaching 关系的关系图：112.2 关系的表示方法关系的表示方法 例例 设 X=1,2,3,4，X

5、上的关系“”：122.3 关系的性质关系的性质定义定义 设 R 是 X 上的二元关系，则：R 是自反的(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)132.3 关系的性质关系的性质例例 整数集合上的若干关系及其性质整除=自反性对称性传递性反自反性反对称性 v判定关系“”的反对称性的前提条件总为F,理论上反对称性成立。142.3 关系的性质关系的性质存在着既非自反也非反自反的关系，如：存在着既对称又反对称的关系，如：

6、152.3 关系的性质关系的性质存在着既非对称又非反对称的关系，如：162.3 关系的性质关系的性质v从关系矩阵和关系图看关系的性质：R 是自反的：MR 的对角元均为1；关系图为自环图。R 是对称的：MR 为对称矩阵；关系图中弧成对出现。R 是反自反的：MR 的对角元均为0；关系图为无自环图。R 是反对称的：MR 为反对称矩阵；关系图中只出现单向弧。172.3 关系的性质关系的性质例例 在正整数上定义关系 R：R iff x 和 y 的最大公因子是1。讨论R 的关系性质。解 自反性：的最大公因子是2，故 R 即 R 非自反；对称性：成立；传递性：R 且 R 但 R 即 R 非传递；反对称性：R

7、 且 R 故 R 非反对称。182.4 集合的划分与覆盖集合的划分与覆盖定义定义 给定集合 S,A=A1,A2,An,AiS,i=1.n。若成立且对于 ij，有 AiAj=，则说 A 是S 的一个划分，并称 A1,A2,An为此划分的块。v从定义看，给定集合 S 的划分与覆盖都是 S 的幂集的子集。v划分是一种特殊的覆盖，但覆盖不一定形成划分。192.4 集合的划分与覆盖集合的划分与覆盖例例自然数集合 N=0,1,2,3,4,。取 A0=0,6,12,18,模6同余0 A1=1,7,13,19,模6同余1 A2=2,8,14,20,模6同余2 A5=5,11,17,23,模6同余5则 A=A0

8、,A1,A2,A3,A4,A5是N的一个划分。取 B0=奇数，B1=偶数，B2=素数则 B=B0,B1,B2是N的一个覆盖，但不是划分。202.4 集合的划分与覆盖集合的划分与覆盖例例 S=a,b,c 取 A=a,b,c B=a,b,c C=a,b,c A、B、C 均构成对 S 的划分。显然有|A|B|C|。实际上可以确认，在 S 的所有划分中，A 和 C 分别具有最大阶和最小阶，将 A 称为最大划分；将 C 称为最小划分。212.5 等价关系等价关系等价关系等价关系 集合X上的关系 R 若具有自反性、对称性和传递性，则称 R 为 X 上的一个等价关系。例 N上的模6同余关系。写成：R=|x,

9、yN (xy)=6L，L为整数 自反性：对称性：传递性：222.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)故 xRz232.5 等价关系等价关系等价类等价类 设 R 为 X 上的一个等价关系，对任何 xX，所有与 x 有关系 R 的元素的集合，称为 X上由 x 生成的 R等价类。记为 xR。xR=y|yX xRy例例 X=1

10、,2,3,4,5,6,7，R 为 X 上的模3同余关系。则 1R=1,4,7，2R=2,5，3R=3,6242.5 等价关系等价关系性质性质 设 R 为 X 上的一个等价关系，则 X 中的任何一个元素，至少属于一个 R等价类。若 x,yX，则 x,y 或属同一 R等价类，或属两个不同的 R等价类且此两个不同等价类的交集为（不相交）。证明 252.5 等价关系等价关系结论结论 对 X 上的等价关系 R，任意 xX 属于且只属于一个 R等价类；若 xRy，则xR=yR，否则 xR yR=。262.5 等价关系等价关系定理定理 集合 X 上的一个等价关系 R 产生对此集合的一个划分，该划分的块对应于

11、 R 的等价类。证明 由上述结论得到。v将该划分记作：X/R=xR|xXv另外的描述：集合 X 上的一个等价关系 R 的所有等价类构成对此集合的一个划分。272.5 等价关系等价关系定理定理 X 上的任一个划分均可确定一个等价关系。证明 设 X 上的一个划分为 A=A1,A2,An，定义 R=|x,yX(Ai)(AiAxAiyAi)可以证明 R 具有 自反性：对称性：传递性：282.5 等价关系等价关系讨论讨论X 上由不同方法定义的等价关系 R1、R2，若产生的等价类相同，则 R1=R2。不等价关系也能产生划分。29例例 设关系 R 定义在所有8-bit字符构成的集合上：若字符char1和ch

12、ar2的前4个bit相同，则它们之间有关系 R。证明 R 是一个等价关系；共有多少个等价类？列出每个等价类的一个成员。解 容易证明 R 是自反的、对称的和传递的；等价类数目：24=16；0000,0001,0010,0011,1110,11112.5 等价关系等价关系302.6 相容关系相容关系相容关系相容关系 X 上的二元关系 R，若 R 是自反的、对称的，则称 R 为 X 上的一个相容关系，记作 。例例 设 X=2661,243,315,648,455，定义 R=|x,yX，x 与 y 至少含有一个相同数字 容易看出，R 具有自反性、对称性。R 不具有传递性：如,R 但 R 因此 R 不是

13、等价关系，R 是一个相容关系。312.6 相容关系相容关系相容类相容类 设 是集合 X 上的一个相容关系，Ai X。称 Ai 是 X 上的一个相容类当且仅当 Ai 中任二元素相容，即(x)(y)(x,yAi x y)。最大相容类最大相容类 设 Ai 是X上的一个相容类，若 X-Ai 中不存在与 Ai 中所有元素相容的元素，则称 Ai 为 X的一个最大相容类。最大相容类不一定是含有最多元素个数的相容类在相容关系的关系图中，最大相容类对应于一个最大完全子图（在图论中进一步讨论）。322.7 关系的运算关系的运算v假设以下讨论的集合 X、Y、Z、W 都是非空集合。(1)关系的一般运算关系的一般运算定

14、义定义 设 R、S 是 X 到 Y 的二元关系，定义运算如下：RS=|xRyxSy RS=|xRyxSy RS=|xRyxSy R=XYR332.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)342.7 关系的运算关系的运算例

15、例 X=x1,x2,x3，Y=y1,y2,y3,y4，Z=z1,z2,z3 R=,S=,v 显然有：Dom(RS)Dom(R)Ran(RS)Ran(S)RS=,352.7 关系的运算关系的运算v关系的复合运算没有交换律。定理定理 关系复合运算的结合律：设二元关系 R：XY，S：YZ，P：ZW，则有 (RS)P=R(SP)证明362.7 关系的运算关系的运算定理定理 关系复合运算与一般运算的结合律：设二元关系 R1:XY，R2,R3:YZ，R4:ZW，则有R1(R2R3)=(R1R2)(R1R3)R1(R2R3)(R1R2)(R1R3)(R2R3)R4=(R2R4)(R3R4)(R2R3)R4(

16、R2R4)(R3R4)证明按照定义转换为逻辑运算，证明逻辑等值式。372.7 关系的运算关系的运算关系的幂运算关系的幂运算 设R为X上的二元关系，RRR 记为 Rn，规定 Rn=Rn1R，R0=IXv注意到笛卡尔乘积 AA .A 记为 定理定理 设R为X上的二元关系，m,n N（自然数），则：Rm Rn=Rm+n；(Rm)n=Rmn。382.7 关系的运算关系的运算定理 设R为X上的二元关系，m,n N（自然数），则：Rm Rn=Rm+n；(Rm)n=Rmn。证明：对任意给定的 m，施归纳于 n。n=0 时，有 Rm R0=Rm IX=Rm=Rm+0；设 n=k 时结论成立，即有 Rm Rk=

17、Rm+k；当 n=k+1 时：RmRn=Rm Rk+1=Rm(RkR)=(RmRk)R（结合律）=Rm+kR（归纳假设）=Rm+k+1=Rm+n；由归纳原理，结论成立。392.7 关系的运算关系的运算定理 设R为X上的二元关系，m,n N（自然数），则：Rm Rn=Rm+n；(Rm)n=Rmn。证明：对任意给定的 m，施归纳于 n。n=0 时，有(Rm)0=IX=R0=Rm0；设 n=k 时结论成立，即有(Rm)k=Rm k；当 n=k+1 时：(Rm)k+1=(Rm)kRm=Rm(RkR)=RmkRm（归纳假设）=Rmk+m（结论）=Rm(k+1)=Rmn；由归纳原理，结论成立。402.7

18、关系的运算关系的运算定理定理 设 R 为 X 上的二元关系，|X|=n+，则存在自然数 s 和 t，使得 Rs =Rt。证明 对任意 kN，Rk 也是 X 上的二元关系。RkXX 或 Rk(XX)又：|X|=n，|XX|=n2，|(XX)|=2n2列出R的各次幂：由鸽巢原理，必有 s,t0,1,.,2n2,2n2+1,.，使得 Rs =Rt。412.7 关系的运算关系的运算(3)关系的逆运算关系的逆运算逆关系逆关系 设二元关系 R：XY，定义 R-1=|xXyYR 为R的逆关系。性质性质(R-1)-1=R，-1=(RS)-1=R-1S-1，(RS)-1=R-1S-1(R)-1=(R-1)(RS

19、)-1=S-1R-1 R=S R-1=S-1 RS R-1S-1422.7 关系的运算关系的运算(4)关系的闭包运算关系的闭包运算闭包闭包 设 R 为 X 上的二元关系，若另有一关系 R，满足：R 是自反的（对称的/传递的）；R R；对于任何自反（对称/传递）的关系R，若 R R，则R R 。则称 R为R的自反（对称/传递）闭包，记为 r(R)（s(R)/t(R)）。432.7 关系的运算关系的运算例例 整数集上的“”关系的自反闭包是“”，对称闭包是“”，传递闭包仍然是“”。例例 整数“=”的自反、对称、传递闭包都是它本身。例例 有关系矩阵 求 M r(R)、M s(R)、M t(R)442.

20、7 关系的运算关系的运算452.7 关系的运算关系的运算定理定理 设 R 为 X 上的二元关系，则 R 是自反的当且仅当 r(R)=R；R 是对称的当且仅当 s(R)=R；R 是传递的当且仅当 t(R)=R。证明 练习462.7 关系的运算关系的运算定理定理 设R为X上的二元关系，则 r(R)=RIx s(R)=RR-1证明 472.7 关系的运算关系的运算证明：分别证明 a 欲证，由于只需证明具有传递性，则由 t(R)的定义可得结论。设不妨设则即具有传递性。482.7 关系的运算关系的运算 b 欲证，先归纳证明对任意的 k，有设 k=n 时，有由复合的定义当 k=1时，显然当 k=n+1时，

21、对任意又且（归纳假设）故有由 t(R)的传递性由归纳原理，因此，492.7 关系的运算关系的运算证明：设设，显然 R 是自反的，且设有 R 是自反的，且，欲证a 若 x=y，因 R 是自反的，有b 若 xy，因，必有 由得到综合 ab，得由自反闭包的定义，R=r(R)。502.7 关系的运算关系的运算证明：仿照证明完成练习。v提示：构造a 若b 若512.7 关系的运算关系的运算定理定理 设 R1 和 R2 为 X 上的二元关系且 R1 R2，则 r(R1)r(R2)；s(R1)s(R2)；t(R1)t(R2)。证明 练习522.8 偏序关系偏序关系偏序关系偏序关系 集合 A 上的一个关系 R

22、 满足自反性、反对称性和传递性时，称 R 是 A 上的一个偏序关系，记为“”，用二元组 表示该偏序结构，或称之为偏序集。“”通常可简写为 x y，读成“x 小于等于 y”。例例 A=2,3,6,8,“”=|x,yA(x整除y)“”=.容易验证，上述关系为偏序关系。532.8 偏序关系偏序关系vx,y 之间存在偏序关系时，说 x,y（在该关系下）可比较可比较，否则说 x,y 不可比较。上例中，在定义的“”下，2和3不可比较。盖住盖住 盖住（紧邻遮盖）。设，x,yA，y 盖住 x xyxy(z)(xzzy)(x=zy=z)记 covA=|x,yA(y盖住x)542.8 偏序关系偏序关系v表达偏序关

23、系的 Hasse 图 设有偏序关系 用结点表示集合元素 若 covA，则用线段连接结点 x,y，且令 x(小者)在 y 的下方。552.8 偏序关系偏序关系例例 Hasse 图如右图 默认 aa,bb,cc ac,cb ab a c bHasse Diagramv 由画法可见：自反关系为默认；反对称关系体现在“上”、“下”位置上；由上到下的可达性表达了传递性。562.8 偏序关系偏序关系v上述 Hasse 图表示的对应关系集合为：,对应关系图如下：a c bHasse Diagram a c b关系图572.8 偏序关系偏序关系例例 由偏序关系的关系图构造相应的 Hasse 图 c a b关系

24、图 d a b cHasse Diagram d582.8 偏序关系偏序关系例例 2,3,6,12,24,36上的整除关系的 Hasse 图。2 6 24Hasse Diagram 36 12 3592.8 偏序关系偏序关系例例 A 的幂集上的 关系的 Hasse 图。A=a a a,bA=a,bba 602.8 偏序关系偏序关系例例 A 的幂集上的 关系的 Hasse 图。a,b,cA=a,b,cba c a,b a,c b,c612.8 偏序关系偏序关系最大最小元最大最小元 对偏序集 y0A为最小元 (x)(xAy0 x)y0A为最大元 (x)(xAxy0)定理定理 中最大(最小)元若存在

25、则唯一。证明极大极小元极大极小元 对 y0A为极小元 (x)(xAxy0(x y0)y0A为极大元 (x)(xAxy0(y0 x)622.8 偏序关系偏序关系例例 2,3,6,12,24,36上的整除关系的 Hasse 图。2 6 24 36 12 3 2,3 为极小元 24,36 为极大元 没有最小元和最大元632.8 偏序关系偏序关系例例 A 的幂集上的 关系的 Hasse 图。a,b,cA=a,b,cba c a,b a,c b,c 为最小元 a,b,c 为最大元642.8 偏序关系偏序关系上下界上下界 对,BA,aA a 是 B 的一个上界 (x)(xBx a)a 是 B 的一个下界

26、(x)(xBa x)v说明：a 不一定是 B 的元素，即可能 aA-BB 的上(下)界不一定存在，存在也不一定唯一。652.8 偏序关系偏序关系例例 2,3,6,12,24,36上的整除关系的 Hasse 图。2 6 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，下界是2662.8 偏序关系偏序关系上确界上确界 对,BA,aA 是 B 的一个上界。a 是 B 的上确界 (y)(y 是 B 的上界a y)上确界若存在则唯一。下确界下确界 对 ,BA,bA 是 B 的一个下界。

27、b 是 B 的下确界 (x)(x 是 B 的下界x b)下确界若存在则唯一。672.8 偏序关系偏序关系例例 2,3,6,12,24,36上的整除关系的 Hasse 图。2 6 24 36 12 3令 B1=2,3,6 B1的上界是 6,12,24,36 B1 的上确界是 6 B1 没有下界也没有下确界令 B2=2,6,12,24 B2 的上界和上确界是24 B2 的下界和下确界是2682.8 偏序关系偏序关系链与反链链与反链 对,BA,若 B 中任两个元素之间都是可比较的，则称 B 是 A 中的一条链。若 B 中任两个元素之间都是不可比较的，则称 B 是 A 中的一条反链。2 6 24 36

28、 12 3例例 右边所示 Hasse 图中，2,6,12,24 是一条链 2,3和24,36是反链v注意：2,3,24,36并非反链692.9 其他次序关系其他次序关系(1)全序关系全序关系全序关系全序关系 设偏序集，若 A 是一条链，则称“”为 A 上的一个全序关系，此时称 是一个全序集合。(2)偏序关系的逆关系偏序关系的逆关系定义定义 设偏序集 ，定义A上的关系“”xy x,yAyx 容易证明，集合 A 和关系“”仍然构成一个偏序集。702.9 其他次序关系其他次序关系(3)拟序关系拟序关系拟序关系拟序关系 集合A上的关系 R 满足反自反性和传递性时，称为A上的一个拟序关系，用二元组 A,

29、表示该结构。v拟序关系是反对称的，也称为严格偏序关系。定理定理 若 R 为 A 上的偏序关系，则 R-IA为 A 上的拟序关系。若 R 为 A 上的拟序关系，则 RIA为 A上的偏序关系。712.9 其他次序关系其他次序关系定理定理 设有拟序集 A,，对任何 x,y,zA,xy,x=y,yx 中至多有一种情况成立(三分律)；xyx 则 x=y，这里 xy 表示 xy 或 x=y。证明 利用拟序集的反自反性和传递性。722.9 其他次序关系其他次序关系(4)词典次序词典次序v设字母表为X，“”为X上的自然次序。显然 为全序集合。长度为2的词库 A=X X 在 A 上定义全序关系 S：S (x1x

30、2)(x1=x2y1y2)S-1 S 732.9 其他次序关系其他次序关系 长度不大于 n 的词库 A=XX2.Xn 在 A 上定义全序关系 S：设,A,其中 pqn。S 当且仅当下列三个条件之一得到满足：()=()x1y1且在 X 中有x1y1 ()xi=yi,i=1.k,kp,xi+1yi+1且在 X 中有 xi+1yi+1 否则 S742.9 其他次序关系其他次序关系(5)格格格格 设偏序集合,若其中任何二个元素在A中都有上、下确界，则称 为一个格。例例 如下的 Hasse 图描述了三个格：752.9 其他次序关系其他次序关系例例 如下的 Hasse 图描述的不是格：（没有下确界）例例，

31、I+正整数，a“”b iff a 整除 b。任何 x,yI+，其上确界为其最小公倍数，下确界为其最大公约数，均存在于 I+中。故 为格。762.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 （吸收律）772.9 其他次序关系其他次序关系证明证明 若 a b,c

32、d，则 ac bd,ac bd先证：ac bd由定义，bd是 b,d的上确界，故 b bd 考虑条件 a b，由格的传递性，得 a bd 同理有 c bd故 bd是 a,c的一个上界。而 ac是a,c的上确界。故 ac bd完全类似证明 ac bd782.9 其他次序关系其他次序关系证明证明 a(bc)=(ab)c,a(bc)=(ab)c设 u=a(bc),v=(ab)c由定义，u是 a,bc的下确界，故 u a,u bc又 bc 是 b,c的下确界，bc b,bc c 由格的传递性，得 u b,u c考虑到 u a，可知 u是a,b的一个下界。由下确界定义有 u ab，故 u 也是 ab,c

33、的一个下界。由下确界定义有 u (ab)c=v同理可以证明 v u由反对称性，得到 u=v，即 a(bc)=(ab)c。完全类似证明 a(bc)=(ab)c792.9 其他次序关系其他次序关系证明证明 a(ab)=a,a(ab)=a由定义，a(ab)是 a,ab的上确界，故 a a(ab)由定义，ab 是 a,b的下确界，故 ab a 又由自反性 a a,故 a 是a,ab的一个上界。故 a(ab)a由反对称性，得 a(ab)=a完全类似证明 a(ab)=a 802.9 其他次序关系其他次序关系(6)良序集合良序集合良序集合良序集合 设偏序集合 ，若其任意非空子集都在该子集中存在最小元，则称 为良序集合。例例 如图的偏序集不是良序集，因为 a,b没有最小元。812.9 其他次序关系其他次序关系定理定理 每个良序集合本身也是一个全序集合。有限阶的全序集合是一个良序集合。证明