二元关系闭包次序等价PPT讲稿.ppt

二元关系闭包次序等价二元关系闭包次序等价第1页，共57页，编辑于2022年，星期四3.3 关系上的闭包运算关系上的闭包运算 3.3.1 逆关系逆关系定义定义 3.31 设 R 是从 A 到 B 的二元关系，关系关系 R 的逆的逆是一个从 B 到 A 的二元关系，记为定义如下：例1 (a)I 上的关系 相等关系相等关系的逆逆是相等关系相等关系空关系空关系,第2页，共57页，编辑于2022年，星期四 z(y,z R z,x S)定理定理3.31 设 R 是从 A 到 B 的关系，而 S 是从 B 到 C 的关系，则证 x,y y,x x,y z(x,z z,y)第3页，共57页，编辑于2022年，星期四定定理理3.32 设 R、R1 和 R2 都是从 A 到B 的二元关系，那么下列各式成立：(a)设 a,b 是 R 的任一元素。那么，b,a a,b a,b R(b)a,b b,a b,a b,a a,b a,b a,b (c)第4页，共57页，编辑于2022年，星期四(d)a,b 表示 ABR b,a b,a a,b a,b (e)(f)b,a R1 b,a R2 a,b R1 a,b R2第5页，共57页，编辑于2022年，星期四定理定理3.33 设 R是 A 上的二元关系，那么 R 是对称对称的当且仅当当且仅当证证设 ，b,a R R是对称对称的设 R 是对称对称的，b,a R a,b R a,b R 对于任意的元素对 a,b R 则对于任意的元素对 a,b 第6页，共57页，编辑于2022年，星期四3.3.2 关系的闭包运算定义定义3.32 设R是A上的二元关系,R的自反自反(对称,传递)闭包闭包是关系R,使 (i)R是自反是自反的(对称的,传递的)(ii)RR (iii)对任何自反的(对称的,传递的)关系R,如果 RR,那么RRR的自反,对称和传递闭包分别记为r(R),s(R)和t(R).R的自反(对称,传递)闭包是包含包含R并且具有自反自反(对称,传递)性质的最最小关系小关系.第7页，共57页，编辑于2022年，星期四构造构造 R 的自反自反，对称对称和传递传递闭包闭包的方法给 R 补充补充必要的序偶序偶，使它具有所希望的特性所希望的特性每个每个结点结点上都有有自回路自回路123自反关系的有向图G123第8页，共57页，编辑于2022年，星期四 定理定理3.35 设 R 是集合 A 上的二元关系，那么，且 R Rr(R)=REE是 A上相等关系证证设 R=RER是自反的，显然，只需证明最小性假设R”是A上的自反关系，且R”RR”是自反因为 R”E R”RE=R R=r(R)第9页，共57页，编辑于2022年，星期四对称对称关系的有向图如果有a到b的弧，一定有b到a的弧123G123第10页，共57页，编辑于2022年，星期四 定理定理3.36 设 R 是集合 A 上的二元关系，那么，R R证证显然，假设R”是对称的是对称的，且R”R又又R”是对称的是对称的s(R)=R设 R=R R是对称的设任 a,b R1)如果 a,b R a,b R”那么 b,a R b,a R”a,b R”R R”需证R”Rs(R)=RR 是对称对称的当且仅当当且仅当如果 a,b 2)第11页，共57页，编辑于2022年，星期四传递传递关系的有向图如果从 a 到 b 存在一条有向路径有向路径，则 a 到 b 也存在一条弧弧12341234G这条弧出现在 Rn 的关系图中第12页，共57页，编辑于2022年，星期四 a，ct(R)和c，bt(R)Rn+1 t(R)a，bt(R)t(R)是传递的，定理定理3.37 设 R 是集合集合 A 上的二元关系，那么 (1)n=1，证证（a）(2)假设 n 时 有 Rn t(R)成立，设a，bRn+1，现证现证 n+1 时 Rn+1 t(R)存在cA，使a，cRn 和c，bRRn+1=RnR若a，b是是的任一元素，则存在一 n，使a，bRn，Rn t(R)a，bt(R)先用归纳法证明n 0，Rn t(R)从传递闭包定义传递闭包定义，得到 R t(R)对一切 n 0，Rn t(R)第13页，共57页，编辑于2022年，星期四(b)首先证明是传递的。设 a，b和和b，c是是 的任意元素，的任意元素，对某整数 s1和 t 1，a，bRs 和 b，cRt那么a，cRs Rt=Rs+t a，c是传递的。t(R)包含于每一含有R的传递关系中第14页，共57页，编辑于2022年，星期四例例2 (a)整数集合 I 上的关系(b)整数集合 I 上的关系(c)E对称对称闭包闭包是关系传递传递闭包闭包是关系自反自反闭包闭包是自反自反闭包闭包是对称对称闭包闭包是传递传递闭包闭包是自反自反闭包闭包是对称对称闭包闭包是传递传递闭包闭包是(d)对称对称闭包闭包是自反自反闭包闭包是传递传递闭包闭包是自身自身自身自身全域关系全域关系自身自身EEE全域关系全域关系自身自身全域关系全域关系传递传递反自反反自反反对称反对称传递传递自反自反反对称反对称传递传递自反自反对称对称 反对称反对称反自反反自反对称对称反自反反自反第15页，共57页，编辑于2022年，星期四s(R)(f)设 R 是 I上的关系，xRy 当且仅当 y=x+1，(e)非空集合的空关系对称对称闭包自反自反闭包传递传递闭包自身自身相等关系相等关系那么 t(R)是关系传递传递反自反反自反对称对称自身自身反对称反对称反自反反自反反对称反对称r(R)第16页，共57页，编辑于2022年，星期四 定理定理3.37 设 R 是集合 A 上的二元关系，那么定理定理 3.38 设设 R 是集合是集合 A 上的二元关系，这里上的二元关系，这里|A|=n，那么那么 第17页，共57页，编辑于2022年，星期四 例例3 设 A=a，b，c，d，R 如图(a)所示，t(R)=则RR2R3R4第18页，共57页，编辑于2022年，星期四(1)如果 R 是自反自反的，那么s(R)t(R)R 是自反的自反的当且仅当当且仅当 EA R 若R 是自反的，自反的，则则 必有必有EA Rs(R)=R必有必有EA R s(R)s(R)是自反自反的必有必有EA R t(R)t(R)是自反自反的是自反自反的证明：定理定理3.39第19页，共57页，编辑于2022年，星期四定理定理3.39(2)如果 R 是对称对称的，那么 r(R)t(R)R 是对称对称的r(R)=REE 是对称对称的r(R)是对称对称的（理由：P98习题13表）证明：证明：是对称对称的第20页，共57页，编辑于2022年，星期四(3)如果 R 是传递传递的，那么 r(R)是传递传递的证明：设设 a,b r(R)b,c r(R)只要能证明 a,c r(R)即可即可r(R)=REv 若若 a,b E (无论 b,c 属于哪个集合)则 a=b a,c r(R)v 若若 b,c E (无论 a,b 属于哪个集合)则 b=c a,c r(R)a,b 与与 b,c 必在必在 R 或 E 中中v 若若 a,b R，b,c RR是传递的 a,c r(R)a,c r(R)第22页，共57页，编辑于2022年，星期四补充：(3)如果 R 是传递传递的，那么 s(R)是不一定是传递传递的例如：A=1，2，3，4 R=1,2 ，2,3 ，1,3 s(R)=1,2 ，2,3 ，1,3 ，2,1 ，3,2 ，3,1 不是不是传递的传递的是传递是传递的第23页，共57页，编辑于2022年，星期四 作业作业 P109 4.证证自反、对称、传递自反、对称、传递 8 9(2)14(1)第24页，共57页，编辑于2022年，星期四注注 意：意：3.4 次序关系次序关系 定定义义3.41 如果集合 A 上的二元关系 R 是自自反反的的，反反对对称称的的和传递的传递的，那么称 R 为 A 上的偏序偏序。3.4.1 偏序集合偏序集合序偶A，R称为偏序集合偏序集合如果 R 是偏序偏序,A，R常记为 A，读做“小于或等于小于或等于”R是偏序偏序时，aRb 就记成v如果R是集合 A上的偏序，则是 A上的偏序；v如果用 表示 R，可用 表示数集上的小数集上的小于等于关系于等于关系是是偏序偏序v A，和A，都是偏序集合偏序集合，并互为对偶对偶。a b第25页，共57页，编辑于2022年，星期四例1(1)I，是偏序集合偏序集合 表示整数中的“小于或等于”关系(2)(A)，是偏序集合偏序集合第26页，共57页，编辑于2022年，星期四D=M=例1(3)A=2,4,6,8，D代表整除整除关系，M代表整倍数整倍数关系，则A，D是偏序集合偏序集合，且互为对偶对偶2,2,4,4,6,6,8,8,2,4,2,6,2,8,4,82,2,4,4,6,6,8,8,4,2,6,2,8,2,8,4A，M第27页，共57页，编辑于2022年，星期四x y,xy,且不存在不存在元素 zA，使得 x z 且 z y对偏序关系的关系图作简化关系图作简化v偏序关系自反自反，各结点处均有环环，可全部略去全部略去。v偏序关系反对称反对称，任何两个不同结点之间没有相互到达的边没有相互到达的边，若把点点按从下小上大层次排列下小上大层次排列，则边的箭头方向都是向上边的箭头方向都是向上，可省省略全部箭头略全部箭头。v偏序关系传递传递，可将由传递关系可推出的边省去传递关系可推出的边省去。D=2,2,4,4,6,6,8,8,2,4,2,6,2,8,4,82468哈斯哈斯（Hasse）图第28页，共57页，编辑于2022年，星期四例2(1)P=1，2，3，4，P，的哈斯图 =1,1,2,2,3,3,4,4,1,2,1,3,1,4,2,3,2,4,3,42431第29页，共57页，编辑于2022年，星期四(2)A=2，3，6，12，24，36，A，整除的哈斯图。D=2,2,3,3,6,6,12,12,24,24,36,36,2,6,2,12,2,24,2,36,3,6 3,12,3,24,3,36,6,12,6,24,6,36,12,24,12,36236122436第30页，共57页，编辑于2022年，星期四(3)A=1，2，12，A，整除的哈斯图。D=1,1,2,2,6,6,12,12,1,2,1,3,1,4,1,5,1,6,1,7,1,8,1,9,1,10,1,11,1,12,2,4,2,6,2,8,2,10,2,12,3,6,3,9,3,12,4,8,4,12,5,10,6,12第31页，共57页，编辑于2022年，星期四A=a,b,c,(A)，的哈斯图。补充例补充例第32页，共57页，编辑于2022年，星期四由图所示的哈斯图，写出对应的偏序关系、关系矩阵。关系矩阵 A=a,b,c,d,e 偏序关系=解解:a,a,b,b,c,c,d,d,e,e,补充例补充例c,a,c,b,d,c，d,a,d,b第33页，共57页，编辑于2022年，星期四定义定义3.42 设A，是一偏序集合，B是A的子集(1)元素bB是 B 的最大元素最大元素，如果对每一元素每一元素 xB，xb例3(2)元素bB是 B 的最小元素最小元素，如果对每一元素每一元素 xB，bx在偏序“整除”下整数1到6的集合(1)B=1，2，3，6B的最大元素最大元素B的最小元素最小元素是1是6(2)B=2，3B 没有没有最小元素和最大元素(3)B=4B的最大元素最大元素B的最小元素最小元素是4最大最大(小小)元素要求元素要求它与它与其它元素其它元素都可比都可比第34页，共57页，编辑于2022年，星期四定定理理3.41 设A,是一偏序集合，且 B A，如果B有最最大大(最小最小)元素，那么它是唯一唯一的。证：那么 a b b a假设 a 和 b 都是 B 的最大最大元素当 a 和 b 都是 B 的最小最小元素时，证明是类似类似的 是反对称的反对称的a=b结论：结论：最大最大(最小最小)元素未必存未必存在在，若存在若存在则必唯一。唯一。第35页，共57页，编辑于2022年，星期四例例(A)=定义定义3.43 设A，是一偏序集合，B是 A 的子集 (1)如果 bB，且 B 中不存在不存在元素 x，使 bx 且 b x，那么元素 bB 叫做 B 的极大极大元素。(2)如果 bB，且 B 中不存在不存在元素 x，使 bx 且 x b，那么元素 bB 叫做 B 的极小极小元素。集合A=a,b,c的幂集,a,b,c a,b,a,c,b,c,a,b,c“”关系是一个偏序偏序关系关系设 B=a,b,b,c,b,c,极大极大元素：a,b,b,c极小极小元素 最大最大元素：无无最小最小元素：极大极大(小小)元素不要求元素不要求它与它与其它元素其它元素都可比，都可比，只要没有比它更大（小）的元素就可以只要没有比它更大（小）的元素就可以第36页，共57页，编辑于2022年，星期四 如果 a 是一下界下界并且对每一 B 的下界 a有a a，那么元素 aA 叫做 B 的最大最大下界下界。定义定义3.44 设A，是一偏序集合，B 是 A 的子集(1)如果对每一 bB，b a，那么元素 aA 叫做 B 的上界上界；如果对每一 bB，a b，那么元素 aA 叫做 B 的下界下界。(2)如果 a 是一上界上界并且对每一 B 的上界 a有 a a，那么元素 aA 叫做 B 的最小最小上界上界。记为glb记为lub注意：注意：第37页，共57页，编辑于2022年，星期四例例4(3)考虑偏序集合2,5,6,10,15,30,整除整除,其哈斯图如图。设B=2,5,6,10,15,30,那么极小元素：2、5；没有最小元素、下界、最大下界；30是 最大元素、极大元素、上界、最小上界。设B=2,6,10,设B=6,10,15,设B=2,5,设B=2,5,10,第38页，共57页，编辑于2022年，星期四结论：结论：设A，为偏序集，B A（1）若 b为B的最大最大(小小)元元，则 b为B的极大极大(小小)元元和最小上最小上(大下大下)界界。（2）最大最大(最小最小)元元 未必存在，若存在，则唯一唯一。（3）若B为非空有限集有限集，则 B 的极大极大(小小)元元 恒存在恒存在；但不唯一不唯一，若有多个，它们之间不可比不可比。（4）最大最大(小小)元元与极大极大(小小)元元都必须是子集子集B中的中的元素。（6）若b是B的一个上上(下下)界界且bB，那么b是B的最大最大(小小)元元。定理定理3.4-2 3.4-4（5）最小上最小上(大下大下)界界未必存在，若存在，则唯一唯一。第39页，共57页，编辑于2022年，星期四 3.4.2 拟序集合拟序集合 定定义义3.45 如果集合A上的二元关系R是传传递递的和反反自自反反的,那么R叫做A上的拟序拟序.A,R称为拟序集合拟序集合.常借用符号表示拟序。拟序是反对称的拟序是反对称的。证明证明：如果xRy和yRx,由R的传递性得xRx,但这与R的反自反性矛盾,所以xRyyRx常假,于是 xRyyRxx=y 常真,【无义证明法】即R是反对称的.第40页，共57页，编辑于2022年，星期四 例例5 (1)实数集合中的是拟序关系 (2)集合族中的真包含是拟序关系 拟序集合和偏序集合是紧密相关的,唯一区别是相等关系E.定理定理3.45 在集合A上,(1)如果R是一拟序拟序,那么r(R)=RE是偏序偏序.(2)如果R是一偏序偏序,那么R-E是一拟序拟序.证明证明：习题12。第41页，共57页，编辑于2022年，星期四 3.4.3 线序集合线序集合 如果是一偏序,若ab或ba,我们说a和b是可比较的.偏序集合中的元素不一定都可比较,所以叫“偏”序.定定义义3.46 在偏序集合A,中.如果每一a,bA,或者ab,或者ba.那么叫做A上的线线序序(或全序),A,叫做线线序序集合集合或链.第42页，共57页，编辑于2022年，星期四 例例6 (1)P=,a,a,b,a,b,c,P,是线序集合,其哈斯图如图3.48所示 (2)I,是线序集合,其哈斯图(不完全)如图3.49所示 (4)1,2,3,6,整除不是线序集合;如果A是多于一个元素的集合,那么(A),不是线序集合.图3.48 图3.49 第43页，共57页，编辑于2022年，星期四作业作业 P1191.(3)(5)5.良序集合改为等价关系良序集合改为等价关系610.(2)提示提示R含义，保持含义，保持R所有性质所有性质12第44页，共57页，编辑于2022年，星期四3.5 等价关系和划分等价关系和划分 定义定义3.51如果集合A上的二元关系 R 是自反的自反的，对称的对称的和传递的传递的，那么称 R 是等价关系等价关系。3.5.1 等价关系等价关系设 R 是 A上的等价关系等价关系，a，b，c 是 A 的任意元素如果 aRb记作 a b读做“a 等价于等价于 b”第45页，共57页，编辑于2022年，星期四等价关系等价关系：自反的自反的，对称的对称的和传递的传递的(1)自反性自反性(2)对称性对称性(3)传递性传递性有向图有向图上，每一结点每一结点都有自回路自回路有向图有向图上，如果有从有从 a 到到 b 的弧的弧，那么也有从有从 b 到到 a 的弧的弧有向图有向图上，如果从从 a 到到 c 有一条路径有一条路径，则从从 a 到到 c 有一条弧有一条弧每一元素每一元素都和自己自己等价等价如果 a 等价等价于 b，则 b 也等价等价于a如果 a 等价等价于b，b 等价等价于c，则 a 等价等价于c第46页，共57页，编辑于2022年，星期四R=例例1(1)同学集合A=a，b，c，d，e，f R：“住在同一房间”等价关系等价关系现假设 a 和 b 同住一间，d，e，f 同住一间，c 住一间则 a,a,b,b,c,c,d,d,e,e,f,f,a,b,b,a,d,e,e,d,e,f,f,e,d,f,f,d 每个连通分连通分图图是完全图完全图每一结点每一结点都有自回路自回路，每两每两结结点间有点间有两条不同两条不同方向方向的的边边第47页，共57页，编辑于2022年，星期四(iii)x y zx y z xRyyRzxRz(2)数中的相等关系相等关系集合中的相等关系相等关系命题演算中的 关系关系等价关系等价关系(3)空集合 中的二元关系 R(i)x(x xRx)(ii)x yx y xRy yRx自反的自反的等价关系等价关系对称的对称的传递的传递的(4)集合 A 上的全域关系全域关系 R=AA等价关系等价关系第48页，共57页，编辑于2022年，星期四定义定义3.52 设 k 是一正整数正整数而 a，b I。如果对某整数整数 m，a-b=mk，那么 a 和 b 是模模 k 等价等价。整数 k 叫做等价等价的模数模数 ab(mod k)写成第49页，共57页，编辑于2022年，星期四 (iii)设 a b(mod k)和 b c(mod k)，定理定理3.51 模 k 等价是任何集合 A I上的等价关系等价关系(1)如果 A=，证证:是等价关系等价关系(2)如果 A 则(i)对任一a，a-a=0k，自反的自反的(ii)a b(mod k)时，那么存在 m1，m2I，使 a-b=m1k 和 b-c=m2k，将两等式两边相加将两等式两边相加，a-c=(m1+m2)k，a c(mod k)a a(mod k)b a(mod k)存在某 mI，使 a-b=mk，b-a=-mk，对称的对称的传递的传递的第50页，共57页，编辑于2022年，星期四定定义义3.53 设 R 是集合 A上等等价价关关系系，对每每一一a A，a 关于R 的等价类等价类是集合集合对每一每一 a A，等价类 a R 非空非空 a R xxRa 简记为 a a 为等价类等价类 a 的表示元素表示元素 a a Rv 如果等价类等价类个数个数有限有限，则 R 的不同不同等价类等价类的个数个数叫做 R 的秩秩；v否则秩秩是无限无限的第51页，共57页，编辑于2022年，星期四12=14=例2 (1)若 R 是 I 上模模 4 等价关系，则34=04=-8，-4，0，4，8-7，-3，1，5，924=-6，-2，2，6，10-5，-1，3，7，11(2)若 R 是 I 上模模 2等价关系，则 02=-4，-2，0，2，4-3，-1，1，3，5每一集合中的数相互等价相互等价(3)时钟是按模模12方式记数的设备13点钟和 1点钟有相同的记数，13=1=1,13第52页，共57页，编辑于2022年，星期四 (1)A=a，b，c，d，e，f 则等价关系等价关系 R 的等价类等价类：例 3R=a=b=c=a,a,b,b,c,c,a,b,b,a,a,c,c,a,b,c,c,b,d,d,e,e,d,e,e,d,f,f d=e=a，b，cf=d，e f R 的秩秩是3第53页，共57页，编辑于2022年，星期四 (2)I上模模4等价的等价类等价类是(3)集合A上相等关系相等关系的秩秩等于I上模模2等价的等价类等价类是04，14，24，3402，12A的元素个数元素个数第54页，共57页，编辑于2022年，星期四定理定理3.52 设 R 是非空集合 A 上的等价关系等价关系，aRb 当且仅当当且仅当aa证：证：“”“”即 ab=b设a=b aRb设 aRb x a xRaR具有传递性传递性需证 aRb需证 a=b xRb 即 x b a b类似可证b aa=ba=b第55页，共57页，编辑于2022年，星期四定定理理3.53 设 R 是集合 A上的等等价价关关系系，则对所所有有a，bA，或者a=b，或者ab=根据定理定理3.52证：证：v 如果 A=断言无义地真无义地真v 设 A 假设ab a b则存在某元素 ca和 cbR 是 等价关系等价关系，aRb 当且当且仅当仅当a=ba=c=b这与假设相矛盾矛盾第56页，共57页，编辑于2022年，星期四作业作业 P1293.(2)(4)4.(1)5.(3)证明是等价关系证明是等价关系P11910.(5)改为等价关系改为等价关系第57页，共57页，编辑于2022年，星期四