离散数学是计算机科学的基础理论，离散结构的基础知识和逻辑思维的形式化是信息技术类学生的基本功，离散数学的基本概念是理科专业学生进行信息类课程学习的重要基础。 本课程介绍计算机科学和信息技术理论基础的概念和思想方法，介绍数理逻辑、集合论、图论、抽象代数和形式语言与自动机等各部分的基本概念，介绍离散数学基本概念和空间信息技术之间的联系与结合，培养学生理解和掌握离散数学基本概念，采用形式化方法分析问题，并能自觉运用逻辑分析、结构层次分析和同构类比等思想方法解决问题的能力。
46-关系合成运算
Loading...
Do curso por Peking University
离散数学概论 Discrete Mathematics Generality
137 ratings
Na lição
集合论：集合代数
Conheça os instrutores
陈斌副教授
北京大学
[音乐] 好，欢迎回来。
下面呢我们来看看这个 关于二元关系的一个更为高级的一种运算。
称之为关系的合成运算，那么合成运算是这样定义的。
R呢是A到B的一个二元关系，S呢是B到C的一个二元关系。
那么R和S的合成，那么我们把它 记作一个圈，叫R圈上S，就是R，S的合成，那么定义为
x,z的二元组的一个集合，那么x呢是来自于A，
然后z呢是来自于C，因为我们R是A，A到B，然后呢S呢是B到C，
那么如何选这个x,z呢？那么它的这个选择的这个条件就是
它会要存在一个y，y是属于B的， 会有xRy，并且呢会有R，会有ySz,
也就是说在这个B当中会有一个y，这么一个媒介，或者叫中介的一个元素，
能够把这个x和z联系在一起，那么我们就把这样的x,z全都选出来，
作为R和S的合成的这个结果。
那么当然它的简化的形式可以写成这样，就是R，S和合成就是x,z。
那么x,z呢就会有存在一个y，会有xRy，和取上ySz，
那么就是说它们之间会有一个桥梁，把它们搭在一起。
把所有的这样的x,z的这些对，把它选出来放在那儿，就是合成的这个结果了。
那么最后它得到的这个结果 它应该是A到C的一个二元关系，它是A到C的一个二元关系。
所以呢，因为参加合成运算的第一个关系的这个陪域要等于第二个关系的前域。
所以我们说一般来讲，只要A,B,C它们不是相同的一个集合，
那么它这个合成运算它都不会满足这个交换律，不会满足交换律。
我们来看看几个关系合成运算的这个例子。
我们假设EA呢是A上的相等关系，EB呢 B上的相等关系。
然后呢R是A到B的一个二元关系， 那么首先呢EA和R做这个合成，
以及呢R和EB做合成，因为它们都是相等关系，相等关系在矩阵里头，它是一个单位矩阵。
所以你要这么做的话，最终呢它还等于它自己，相等关系和
任何的这个关系做合成，还等于 这个关系本身。
那么当然也可以预期 这个空关系跟R做合成，以及R和空关系做合成的话，
那么它都等于空关系。
还有呢，R和R的逆做 这个合成，因为R是A到B，那么R逆呢是B到A的，那么这样的一合成，
那么它就会等于EA，就是A到AE上的一个相等关系。
这个呢我们可以用它的这个合成的
这个定义来进行证明，是吧？它是存在，它必定
会存在一个y，使得每一个xRy和yRx都会
有，当中会有一个y把它联系在一起，所以呢就会有所有的这个x和x 这样。
那么倒过来，R的逆和R做这个合成，那么它就会等于EB， 就会等于EB。
那么这个呢 ，也是一样的，它会 把所有的这个来自于B的这个y收集在一起，
那么得到B上的一个相等关系。
那么如果是用生活当中的例子 来讨论这个合成的话，我们实际上可以用
这个兄弟关系和父子关系的这个合成 就合成，就等于是一个叔侄关系。
也就是说父辈是兄弟，然后呢子辈是这个 然后呢再加上父子的话
，那么父辈的兄弟 跟这个子辈之间，它们就会有这个叔侄，所以呢它会
父辈呢会叫子辈叫做侄子，那么子辈这边往上叫，就会叫做叔，或者叫做伯。
这样的，这个呢我们 可以从生活当中来理解这个合成关系。
那么当然我们也可以用关系图来理解 这个合成运算。
我们首先看一下前域和陪域不同的这种
关系图，那么我们会有A,B,C三个，是吧？R呢是A到B的关系，
S呢是B到C的关系，那么这样呢就会有三个圆，然后每个圆里面都会有相应的这个圆圈
来表示这个元素。
那么这个红色的箭头呢就代表 A到B的，这个S，R，R呢就会有三个二元组，
那么B到C呢也是绿色的，它有三个二元组。
那么我们如何看到R和S的合成呢？ 我们就会找到A到B的一个箭头，
如果到了这个B的这个箭头所指的这个同一个元素，
它还有到C的这个箭头的话，那么我们就会拉一条箭头，从A到C拉一条箭头，
那么这样呢，一个三角形，红绿蓝这么一个三角形
那么我们，我们一看呢，很像，是什么？是这个矢量合成，对吧？这像是一个矢量合成。
A到B，然后B到C，然后合成成为A到C，所以我想可能这就是为什么
这个运算呢也称为合成，它当然跟矢量，或者说跟这个力矩这个合成它都有关系。
那么如果是前域和陪域相同的这样的 一个关系图，那么我们也可以看出是这么，可以这么画，
我们首先找到从一个节点到另外一个节点，第一个节点到第二个节点的一条边， 然后从第二个节点出发到第三个节点，
那么再把这个第一个节点到第三个节点 画一条边，这就是虚线，那么就是R和自身的一个合成。
所有的这个虚线的箭头就是R和自身的合成，那么 这个呢也是在前域、
陪域相同的这么一个图里面 一个一个地找这个矢量合成，这么一个三角形，对吧？矢量三角形。
那么我们当然也可以用关系矩阵来表示这个合成运算，
我们说过，关系呢用矩阵来表示，它是非常方便的。
那么我们可以通过矩阵的一些运算，来表示关系的一些运算。
那么这样呢，我们用矩阵乘法就可以表示关系的这个合成运算了。
只不过说在矩阵乘法的时候，涉及到的乘法呢我们就会换成这个合取， 把数加换成这个析取。
我们来看看这个是怎么定义的。
首先A它的基数是m，就是说A呢有m个元素， B呢有n个元素，C呢有p个元素这么多。
那么R呢是A到B的一个二元关系。
S呢是B到C的二元关系， 那么R的关系矩阵和S的关系矩阵，分别都有这样的一个定义。
那么显然，R的关系矩阵呢有m行，n列。
S的关系矩阵呢有n行，p列。
我们把这个R和S和合成 的结果是T的话，那么T呢就是A到C的一个二元关系。
那么A到C，那么它的所对应的关系矩阵 就是MR和MS的一个矩阵乘法得到的结果。
那么既然是矩阵乘法，当然我们看它确实是满足了m行n列和m行p列
最后乘的这个结果呢得到的应该是一个m行p列 的这么一个矩阵，那么这个矩阵呢就正好就是T的关系矩阵。
那么T当中的每一个元素，tij
跟我们的这个矩阵乘法里头每一个分量是一致的，是吧？那么它是把这个
A当中的这个M，R当中的每一行和S当中的每一列
来，然后拿出来两两做这个数乘，做这个数乘，就是换成合取啊。
合取完了以后，再把它们做一个累加，那么把累加呢就换成
累析取，把它们累析取，那么这样呢就确定了每一个i行j列
pij的这个值。
那么合成运算呢对于其他的运算来讲， 它也具有一定的性质。
我们首先呢来看合成运算对于 并运算，并运算，它既满足左分配律，又满足右分配律。
比如说左分配律，也就是说R和，S和T的这个并域，
并关系，然后呢再做合成，它实际上呢是可以先把R和S做合成，
R和T做合成，然后呢再把它们做一个并运算，这样的结果是可以的。
那当然这个证明呢我们是可以通过一个逻辑等价式来进行证明。
因为这个合成运算它是说有一个 存在，存在量词，我们说x存在一个y，xRy
然后呢，并且有yRz，然后再把x,z选出来嘛，所以呢我们就找
就会有对应的这个逻辑等价式，就是存在xA(x)
然后呢它析取上，因为析取是对应，可以定义并运算的，
析取上B(x)，它是等价于这个存在xA(x) 和存在xB(x)，然后再做析取，
可以用这样的一个逻辑等价式来证明这个合成运算对于 并运算的这个左分配以及右分配，这是可以的。
但是呢合成运算对于交运算来讲，就没有那么好了， 那么它不是一个相等，它并不满足左分配右分配，
但是呢它也还是有一定关系的，也就是说如果R和S和T的这个交集，
做这个合成运算的话，那么它是 这个分别做合成运算再做交集，
它们之间呢有一个被包含的关系，也就是一个子集的关系， 那么我们如果要证明的话很显然这个子集关系呢会
用这个逻辑蕴涵，逻辑蕴涵，那么它这个呢式子就是存在量词
对于这个合取来说，它是一个逻辑蕴涵，存在xA(x)
合取上B(x)的话，那么你如果要把这个存在量词的辖域 分布加到A(x)，B(x)这两个谓词里面的话呢，
它们就还仍然保留这个合取，但是呢它已经不是逻辑等价了，它只是逻辑蕴涵，
那么通过这么一个逻辑蕴涵式我们同样也可以来证明它。
那么合成运算对于这个逆运算，
那么当然逆运算呢是没有什么本质的变化，但是呢逆运算它会把前域和陪域颠倒过来，
所以呢，就是R和S合成求逆的话， 那么它是S求逆和R求逆然后再做合成，
它们求逆了以后就要把S，R和S的这个顺序颠倒一下，
这个是成立的，然后最后呢，合成运算它自身是满足结合律的，
也就是R和ST合成的结果做合成，
它是等于R和S的合成的结果再跟T做合成， 这两个是相等。
我们下面呢可以来进行证明， 那么证明的思路呢也还是用两个集合相等这个思路来证明，
我们就从R和ST合成的结果做合成，它最终的结果当中提取出一个
二元组，也就是x，y，x，y属于它的这个完整的合成结果。
然后呢把它拆开，那么x，y属于这个合成呢，它就肯定会存在一个u，
那么x，u呢是属于R的，然后u，y呢是属于S和T的合成，
对吧，这是R和ST合成的结果进行合成， 它的定义是这样的。
然后接下来呢我们再把这个u，y 属于这个ST的合成进行
返回到它的这个定义里边，那么也就是说会存在一个v u，v呢是属于S的，然后v，y呢是属于T，
这样呢，到第三步，我们就把所有的这个合成全部都拆开了，
拆开完了以后呢我们再利用这么一个逻辑等价式， 也就是当你如果没有这个自由变元x的情况下，
我这个B呢是可以自由地进入到这个x存在量词的这个辖域里边的， 首先它是一个合取，是一个合取，它是可以自由地进入
那么自由地进入呢，我们就把这个存在u，存在v统统都提到最左边来， 这个呢有一个术语叫做前束范式，
当然我们前面没有，并没有涉及到过，但是我们 可以把u，v全部都提到最外层来。
然后呢再进行一个重新组合，
因为既然存在u，存在v，这样的一个，然后呢再把这个存在u的这个辖域进行缩小，
缩小，缩小到呢它只包含这些u呢，那么就会有， 存在u，x，u属于R，然后呢u，v呢属于S，
那么这样呢，既然会有x，u，有u，v，那么我们就很显然
它是一个是从R来，一个是从S来，那么就会有x，v是属于R和S的合成，
然后再有呢，u有v，y属于T，
那么这，前面呢，最前面有一个存在V， 那么很显然呢，在按照合成运算的这个
定义再返回去的话，我们就得到了x，y是属于 R和S的合成，再跟T进行合成，
那么从第一步到最后一步我们一直呢都是这个逻辑等价，
所以呢我们就证明了这两个集合实际上是相等的。
那么把这个合成运算进行一个推广， 那么我们就会有了关系的幂运算，R的n次幂。
R的n次幂呢定义为这个关系的自身的n次合成，
那么也就是说R的n次幂呢就相当于R和R进行合成，再跟自己合成，
然后n个R进行合成，当然我们特别的 因为有自然数的话，那么n是一个自然数，那么我们就把零次幂
做一个定义，做一个规定，它就规定是A上的一个相等关系， 这么一个规定。
那么幂运算的性质呢，就是说
R的m次幂和R的n次幂进行合成的话，那么它是等于R的m加n次幂，
它是一个指数一个加，这个跟我们在 自然数或者整数当中这个算术运算里头的幂运算的法则
是类似的，是类似的，当然也有R的m次幂，然后 再做n次幂，它实际上是R的m乘n这么多个次幂。
那这个呢实际上是可以进行证明的，这个用数学归纳法很容易证明，因为它虽然是两个参数，
m和n，我们可以把m看作是一个参数，然后对n进行数学归纳法， 最终就可以证明了。
那么关于这个幂运算还有一个幂关系的有限定理，有限定理。
这个定理是说，如果一个集合A它的基数为n，它是一个有限集合，
那么R呢是A上的一个二元关系，那么它 肯定会存在两个不相同的自然数，R，i，j，
这个i，j呢是从0到2的n平方次幂之间，
这个范围是挺大的，但是呢它说这个i和j可以是不同的，
那么在这个范围里头我必定可以找出两个不同的数，
会有Ri次幂等于R的j次幂，这个次幂的运算。
我们实际上可以证明，这个证明呢也并不是很困难， 那么首先我们基于这样的一个事实，
就是R的任意次幂的运算，因为它跟自身不管有多少次合成， 它的结果还是A上的二元关系，
对吧，这个是由于这个运算的封闭性决定的，也就是说二元关系，它不管经过什么
样的运算，它最终呢还是等于二元关系，所以呢，它的任意次幂的运算，仍然是A上的二- 元关系。
那么其次，第二个事实，就是说有限
集合A上的不同的二元关系的数量它实际上是有限的， 是有限的，那么既然是有限，它是有多少呢？
我们来看二元关系是什么？二元关系是AxA上的一个子集，
这就好办了，我们知道AxA的子集它的个数是有限的，它有多少个呢？
如果说A的基数是n的话，那么它的，AxA的子集的个数
AxA的子集的个数就是，2的，恰好是2的n平方次幂这么多个，
因为AxA的这个集合，就是全关系的集合，会有n平方这么多个，
这个二元组，那么n平方呢，再进行子集的这个组合的话，那么就是2的n平方次幂。
那这样呢我们根据这个组合里边的鸽笼原理， 在0到2的n平方次幂这么多个
这么多个数，这有多少个数呢，就是恰好是2的n平方加1这么多个数，
这么多个R的幂关系当中，而你不同的关系只有2的n平方次幂这么多个，
那么正好相差1，那么这样呢就必定会有两个是相同的。
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
