[音乐] 嗨,欢迎回来。 那么我们在 讨论这个了5个基本特性的关系之后呢 我们来看看关于这个5个特性 的一些定理。 那么这些定理呢,一部分也可以用来判定 这个某一些二元关系是不是具有某一些性质 那么另外一些呢,可以用来判定说这个关系 的特性呢在关系进行运算进行变换的时候 它是不是还能够保留这些性质 我们先来看一些能够判定的一些定理 第一个呢是说,R自反 当且仅当说EA是R的子集,包含于这个R 这个是很明显的,对吧,它所有的都有这个圈,所以呢 如果你有EA是包含于R的话,那么R它就是一个自反关系 那么第二呢是说,反自反当且仅当EA交上这个R是空集的子集 那么所谓的空集的子集其实就是等于空集了 也就是说它跟EA呢不能够有任何的这个交集,这也是很自然的,这也很容易理解 第三个,R对称当且仅当R是R的逆的子集 R是R逆的子集,那么这个我们可以来证明一下,我们 先从左到右,也就是这个必要性,那么我们假设这个R是对称的 我们来看看是不是符合R是R的逆的子集 那么我们从这个R当中取出一个二元组<x,y>属于R 那么因为R是对称的,那么所以呢它就会有<y,x>属于R 那么<y,x>属于R呢是跟<x,y>属于R的逆它是等价的 因为逆呢只是把前域 陪域给它对调一下 所以呢我们就从<x,y>属于R 逻辑蕴含了<x,y>属于R的逆,那这样呢,很显然R是R的逆的一个子集 反过来我们来看这个充分性,我们先有了R是R逆的子集,这么一个条件 我们来看,那么从xRy出发 既然这个x R是R的逆的子集,那么xy属于R那么就意味着xy呢是属于R的逆的 对,所以第一步呢就会有这一个逻辑蕴涵 那么xy属于R的逆,它实际上就意味着 yx属于R的,那所以呢从左xRy到右yRx 那么所以呢意味着R是一个对称关系,是一个对称的 接下来是一个反对称 那反对称呢当且仅当R和R逆的交 是EA的子集,EA的子集 那么我们也可以用来证明。 首先呢,我们假设这个R是反对称的 我们来看看它和R的逆进行交集之后会不会是EA的子集 我们也是从这个R交上R的逆当中取出一个元素<x,y> 那么既然这个R和,<x,y>呢是属于R和 R逆的交,那么就意味着<x,y>是属于R的 同时呢<x,y>也是属于R的逆,因为它们是属于它的交集,对吧 那么这个式子呢就意味着 <x,y>属于R同时呢<y,x>属于R 因为<x,y>是属于R的逆,所以呢接下来它变换了一下,那么就是<y,x>属于R 那么根据这个R是反对称的,那么就有<x,y>属于R <y,x>属于R就逻辑蕴涵x=y 这个被标注成蓝色的这个是反对称的 这个定义,所以我们把它放在这了。 那么既然是x=y 那x=y就意味着说y,<x,y>这个 二元组是属于EA的,是属于EA 所以呢我们从这个一连串的这个推导式的第一个<x,y>属于R交上R的逆 一直到最后它蕴涵着<x,y>属于EA 那么也就是说,R交上R的逆是EA的子集,对吧 现在反过来,R交上R的逆是EA的子集 那么我们首先呢由这个<x,y>属于R 同时呢<y,x>属于R由这个出发那么就有 <x,y>属于R合取上<x,y>属于 R的逆,R的逆。 那么根据 这个R交上R的逆是EA的一个子集,那么我们就有蓝色的这一块 也就是<x,y>属于R交上R的逆,就逻辑蕴涵着<x,y>属于EA 属于EA。 那么这个呢最后等于说推导出来 因为它是一个子集,而且呢<x,y>属于EA,那么就意味 着x=y对吧,x=y。 那这样呢,从第一个 <x,y>属于R同时呢<y,x>属于R 那么就到最后有x=y,这个就正好是R是反对称的这个定义 所以呢我们说R是反对称的,这个也得到了证明 接下来呢是关于传递 如何判定一个关系是传递的,这有一个方法 R是传递呢当且仅当R²是 R的二次幂,这是一个幂关系,对吧,它的R和 自身的合成是它自己的一个子集,那这样呢就是有传递了 我们也可以来证明它。 首先呢我们看来必要性 我们先假设R是传递的。 那么我们从这个 R的二次幂当中取出个元素,就是<x,y>属于R的二次幂 那既然<x,y>是属于R的二次幂呢,那肯定 按照这个合成关系的,合成运算的定义 那么就必然会存在一个u,会有xRu并且呢uRy xRu并且又有uRy。 那么从这呢因为R是传递的 所以呢我们有xRu又有uRy,接下来R是传递的那么就会有 xRy,就会有xRy。 那么我们把这个存在u,这个存在量词先保留着 但是呢我们发现呢这个存在量词因为这个当中xRy已经没有u了 所以这个存在量词u可以去掉它,既然去掉就是xRy 那么既然xRy呢就意味着说<x,y>属于 R,是属于R的。 那么我们就从<x,y>属于R的二次幂 逻辑蕴涵了<x,y>属于R,那么所以呢 R²就是这个R的子集 那么现在反过来看这个充分性,R的二次幂是R的一个子集 那么这个子集呢我们来看 xRy并且呢yRz,xRy,yRz 那么它就意味着说是x平方z x平方z。 因为这是这个 R的这个合成,R的合成。 那么xR²z呢就意味着 xRz,xRz。 所以呢我们说R 是传递的,因为有xRy,又有yRz,最后得到了xRz 所以呢我们说R是传递性的 那么第二大部分的定理是关于说5个基本的特性 和这个运算的封闭性的问题 也就说某一些关系具有某一些特性,那么再 经过某一些运算,那么就包括并、 交、 插、 补 或者说合成运算啊,幂运算这些 运算之后,那么运算的结果是不是还保留这个特性的话 如果能够保留,就称之为这个特性呢相对于这个运算来讲就有,运算就有封闭性 那么我们说呢所有的5个特性 对与这个交运算都是封闭的。 也就是说如果R1,R2都有某个特性 那么R1交上R2仍然还保留了这个特性,比如说对称性 我们来看看这个证明这个例子 我们来证明说R1有对称性,R2有对称性,然后R1交R2 得到了这个结果的关系呢仍然具有对称性 我们就从xR1交R2y这个开始 那么既然是xR1交R2y那么意味着x y属于R1,同时呢x,y属于R2,因为这是交运算的这个定义 那么因为它是对称的,R1,R2都是对称的,所以呢就会有 yR1x也会有yR2x 那么这个一来呢,它就跟这个y x属于R1,yx又属于R2,那么当然就有yx属于R1交R2 那么这样的过来,就所以呢R1加R2他仍然保留了这个对称性 那么对于并运算来说就不是说有的,他只有自反,反自反 反自反对称,这三种性质对于并运算来讲是封闭的, 比如说自反,自反呢我们可以用来证明它对并运算的封闭, 封闭的,那么先有xR1x 那么既然xR1x呢,那么就蕴含着xR1x然后吸取上xR2x 那么这个呢是 一个逻辑蕴涵式,逻辑蕴涵式,只要是吸取我可以随便加一个,对吧 那么这个中间这个式子呢, 他就意味着说xx是属于 R1并上R2,那就说明只要R1有自反性 其实呢不管你R2有没有自反性,或者说R2是任何一个这个 二种关系都可以,那么R1并上R2都还保持了这个自反性,都有自反性 对于差运算而言呢 那么只有反自反对称和反对称对于差运算是封闭的 我们来看看反对称这个证明的例子 我们既然是差运算的反对称,所以我们就需要根据这个反对称的 这个定义来,我们有x.y属于R1-R2 然后又有yx属于R1-R2 如果最终我们能得到x=y的话,那么就证明 证明说R1-R2它是具有反对称的性质 那么这个中间的过渡是什么,xy既然 属于R1-R2的话,那么它就必然属于R1,对吧 那么所以呢接下来我们逻辑蕴含就会有XY属于R1,也就是xR1y 那么第二个yx属于R1-R2, 那么既然是yx属于R1-R2的话,那么它就必然会属于 R1,所以呢也有yR1x, 那我们就有了xR1y,并且又有了yR1x, 那么因为R1呢是由反对称的,具有反对称性质,所以呢 我们说它就逻辑蕴含着x=y,x=y, 那么我们从最开始到最后这个x=y,那么我们 能证明了R1-R2它具有反对称的性质, 那么实际上呢,只要,这里头我们只用到了这个R1的反对称性质, 对于R2来说它不管他具有什么样的特性,都无所谓 R1-R2都始终它具有反对称的性质 接下来我们来看看补运算 那么只有对称性对于补运算来讲是封闭的 我们可以来证明,就是xy属于R的补 那么我们要证明呢就必然会有yx也属于R的补, 那么我们假设呢我们用反证法证明,假设不是这样,那既然不是 不是这样,yx属于[iii]是否定的,不属于[iii] 那么既然如果是这样,那么既然不属于[iii],那么 它就一定是属于R,所以呢就会一定有yRx, 那么根据R的对称性,有了yRx,那就必然会有xRy了, 那么有xRy呢就正好跟我们已知条件是相互矛盾的, 因为已知条件是xRy是属于R补的,那么它就不会是属于 去属于R了,对吧,所以跟已知矛盾 那么跟已知矛盾,就是我们假设是错误的,既然错误的,那就一定会有yx属于R的补 那么这样呢,就说R的补既他是具有对称性的, 那么对于求逆运算而言,逆运算很好了 他基本上不会对[iii]有任何改变,只是把前域和陪域颠倒一下吗, 所以呢5个特性,毫无例外,5个特性呢 比如说这个传递性,我们来看看逆运算,逆关系他是否还保持这个传递性, 那么我们也可以从xR﹣y和yR﹣z开始,从这个出发 那么xR﹣y那么就意味着yRx, 对吧,它是逆么,所以它是反过来的,那么既然会有yz属于R的逆,也会有 zy属于R,有zy属于R,所以呢我们就到了第二步, 那么第二步呢,我们把这个前后对调一下,我们就实际上就可以看出来, 如果有zRy又有yRx的话 那么根据R是传递的,那么就必然会有zRx, 那么zRx,把这个R在求下逆,就意味这是 xz是属于R的逆的,这是逻辑等价 那么从第一个式子到最后一个是式子那就说明了 这个R的逆它具有传递性,这个传递性呢是由R的传递性保持过来的, 最后这个合成运算, 合成运算里面呢,只有自反 这个特性是对合成运算是封闭的,那么其他的性质呢 对于合成运算来讲都不封闭,那么为什么是自反呢,我们自反这边也可以用来一个证明 那么自反,就是xR1x, 并且有xR2x,因为R1、 R2都是自反的,那么它所以呢都成立, 那么这两个成立呢,实际上意味着说 x,x是属于R1合成上R2 合成上R2,因为这个中间这个x还是自己对吧,中间x 还是自己,所以呢他是满足xR1合成上R2的x, 所以这个说明呢,R1R2的合成它仍然满足这个自反性质。