第四章相容关系

1/43第四章二元关系2/43回顾•关系的闭包•集合的划分和覆盖•等价关系–等价模数–等价类3/43三、相容关系定义：给定集合X中的二元关系R，如果R是自反的，对称的，则称R是相容关系，记作≈。也就是说，可以把R规定成：(1)()()(2)()()()xxXxRxxyxXyXxRyyRx显然，所有的等价关系都是相容关系，但相容关系并不一定是等价关系。例如，设集合X={2166,243,375,648,455}，X中的关系，可以看出R是自反的和对称的，因此是一相容关系。{,|,}yRxyxyXx和有相同的数字4/43三、相容关系在相容关系中，如果有xRy，则称x和y是相容的。例如前面的例子中，X={2166,243,375,648,455}，令x1=2166,x2=243,x3=375,x4=648,x5=455，则x1Rx2,x2Rx3，但是x1x3，可以看出相容关系是不可传递的。把R写出来是11121422212324253332354441424555525354{,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,}RxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxR5/43三、相容关系R的关系矩阵如下1101011111011011101101111RM由于相容关系是自反的，因而矩阵对角线上的各元素都应是l；相容关系是对称的，所以矩阵关于主对角线也是对称的。这样，仅给出关系矩阵下部的三角形部分也就够了。6/43三、相容关系R的关系图如下由于相容关系的自反性和对称性，关系图中的所有结点上都有环边；有相容关系的两个结点间都有往返弧线。如果找们删除全部结点上的环边，并且用一条直线取代两结点间的两条弧线，这样就可以把图简化2x1x3x4x5x7/43三、相容关系仍然以X={2166,243,375,648,455}为例{,|,}yRxyxyXx和有相同的数字x1=2166,x2=243,x3=375,x4=648,x5=455，令X1={x1,x2,x4},X2={x2,x3,x5},X3={x2,x4,x5}在集合X1，X2和X3中，同一个集合内的元素都是相容的。这些集合的并集就是给定的集合X，亦即X=X1。因此，集合A={X1,X2,X3}定义了集合X的一个覆盖，但它不能构成集合X的一个划分。23XX结论：集合中的相容关系能够定义集合的覆盖；而集合中的等价关系能够确定集合的划分。8/43最大相容类定义：设≈是集合中的相容关系。假定。如果任何一个，都与其它所有的元素有相容关系，而X-A中没有能与A中所有元素都有相容关系的元素，则子集称为最大相容类。AXxAAX寻找最大相容类的方法：关系图法关系矩阵法9/43关系图法寻找最大相容类关系图法的实质在于寻找出“最大完全多边形”。所谓最大完全多边形，系指每一个顶点都与其它所有顶点相连结的多边形。集合中仅关系到它自身的结点，是一个最大完全多边形。不都与其它的结点相连接的一条直线所连接的两个结点构成一个最大完全多边形。三角形的三个顶点构成一个最大完全多边形，对角线相连的四边形的四个顶点构成一个最大完全多边形，正五角星的五个顶点构成一个最大完全多边形，正六边形的六个顶点也是一个最大完全多边形。一个最大完全多边形对应一个最大相容类。10/43关系图法寻找最大相容类2x1x3x4x5x三角形x1x2x4,x2x3x5,x2x4x5是最大完全多变形；与他们对应的最大相容类是X1={x1,x2,x4},X2={x2,x3,x5},X3={x2,x4,x5}11/43关系图法寻找最大相容类例：下图中，给出了两个相容关系图。试求出它们的所有最大完全多边形,并求出与它们相应的最大相容类。126345(a)最大完全多边形有：四边形1234线段25，36和56；与它们相应的最大相容类分别是：{1，2，3，4}，{2，5}，{3，6}，{5，6}。12/43关系图法寻找最大相容类126345(b)最大完全多边形有：三角形123，136，356和孤立结点4；与它们相对应的最大相容类分别是：{1，2，3}，{1，3，6}，{3，5，6}和{4}。13/43关系矩阵法寻找最大相容类首先制定简化了的关系矩阵，继之按下列步骤求出各最大相容类：(1)仅与它们自身有相容关系的那些元素，能够分别单独地构成最大相容类，因此从矩阵中删除这些元素所在的行和列。(2)从简化矩阵的最右一列开始向左扫描，直到发现至少有一个非零记入值的列。该列中的非零记入值，表达了相应的相容偶对。列举出所有这样的偶对。14/43关系矩阵法寻找最大相容类(3)继续往左扫描，直到发现下一个至少有一个非零记入值的列。列举出对应于该列中所有非零记入值的相容偶对。在这些后发现的相容偶对中，如果有某一个元素与先前确定了的相容类中的所有元素都有相容关系，则将此元素合并到该相容类中去；如果某一个元素仅与先前确定了的相容类中的部分元素有相容关系，则可用这些互为相容的元素组成一个新的相容类。删除已被包括在任何相容类中的那些相容偶对，并列举出尚未被包含在任何相容类中的所有相容偶对。(4)重复步骤(3)，直到扫描过简化矩阵的所有列。最后，仅包含孤立元素的那些相容类，也是最大相容类。15/43关系矩阵法寻找最大相容类例：写出下图中的相容关系相对应的简化矩阵，并求出最大相容类。126345(a)213114111501006001011234516/43关系矩阵法寻找最大相容类解：这里没有孤立结点，故可忽略步骤(1)。根据步骤(2)和(3)可有(a)右起第一列上是l，故有相容偶对{5，6}。(b)第二列上全是0。第三列上有两个1。与它们相对应的相容偶对是{3，4}和{3，6}，于是可有{5，6}，{3，4}，{3，6}。(c)第四列上有三个1，故有{2，3}，{2，4}和{2，5}，于是可有{5，6}，{3，4}，{3，6}，{2，3}，{2，4}，{2，5}可以看出，相容偶对{2，3}和{2，4}中的元素2，与相容偶对{3，4}中的两个元素都有相容关系，故可把它们合并成一个相容类{2，3，4}。于是可有{2，3，4}，{5，6}，{3，6}，{2．5}。17/43关系矩阵法寻找最大相容类(d)第五列有三个1，故有{1，2}，{1，3}和{l，4}。于是可有{2，3，4}，{5，6}，{3，6}，{2，5}，{1，2}，{l，3}，{1，4}又可看出，相容偶对{1，2}，{1，3}和{1，4}中的元素1，与相容类{2，3，4}中的所有元素都有相容关系，故可以把它们合并成一个相容类{1，2，3，4}．于是可有{l，2，3，4}，{5，6}，{3，6}，{2，5}。这些都是最大相容类。18/43关系矩阵法寻找最大相容类例：写出下图中的相容关系相对应的简化矩阵，并求出最大相容类。126345(b)21311500161011123519/43关系矩阵法寻找最大相容类解：这里结点4是个孤立结点，故在矩阵中删除了相应的行和列。根据步骤(2)和(3)可有(1){4}(2){4}，{5,6}(3){4},{5,6},{3,5},{3,6}，合并后有{4},{3,5,6}(4){4},{3,5,6},{2,3}(5){4},{3,5,6},{2,3},{1,2},{1,3},{1,6}，合并后有{4},{3,5,6},{1,2,3},{1,3,6}，这里，相容偶对{1,3},{1,6}中的元素1，与相容类{3,5,6}中的部分元素有相容关系，故组成了相容类{1,3,6}。这些相容类都是最大相容类。20/43四、次序关系次序关系是集合中的可传递关系，它能提供一种比较集合各元素的手段。定义：设R是集合P中的二元关系．如果R是自反的、反对称的和可传递的，亦即有()()()()()()()()()()()()axxPxRxbxyxPyPxRyyRxxycxyzxPyPzPxRyyRzxRz则称R是集合P中的偏序关系，简称偏序。序偶P,≤称为偏序集合。21/43偏序关系通常用符号“≤”表示偏序。这样，符号≤就不单纯意味着实数中的“小于或等于”关系。事实上，这是从特定情况中，借用符号≤去表示更为普遍的偏序关系。对于偏序关系来说，如果有且x≤y，则按不同情况称它是“小于或等于”，“包含”，“在之前”等等。,xyP如果R是集合P中的偏序关系，则也是P中的偏序关系。如上所述，如果用≤表示R，则用≥表示。如果P,≤是一个偏序集合，则P,≥也是一个偏序集合，称P,≥是P,≤的对偶。RR22/43偏序关系例：设R是实数集合。“小于或等于”关系是R中的偏序关系；这个关系的逆关系“大于或等于”关系也是R中的偏序关系。例：设是A的幂集。X中的包含关系是个偏序关系；这个关系的逆关系也是个偏序关系。()AX设I+是正整数集合，且,当且仅当存在z，能使xz=y，才有“x整除y”(可写成x|y)，换言之，“y是x的整倍数”。“整除”和“整倍数”互为逆关系，它们都是I+中的偏序关系。,,xyzI23/43偏序关系例：设I+={2,3,6,8}，≤是I+中的“整除”关系。试表达出“整除”和“整倍数”关系。解：“整除”关系≤为{2,2,3,3,6,6,8,8,2,6,2,8,3,6}“整倍数”关系是≥{2,2,3,3,6,6,8,8,6,2,8,2,6,3}实数集合R中的“小于”关系和“大于”关系，都不是偏序关系，因为它们都不是自反的。但它们是实数集合中的另一种关系——拟序关系。24/43拟序关系定义：设R是集合X中的二元关系。如果R是反自反的和可传递的，亦即有()()(axxXxR)()()()()()xbxyzxXyYzZxRyyRzxRz则称R是拟序关系，并借用符号“”表示。注意：在上述定义中，没有明确列举反对称性的条件，事实上关系若是反自反的和可传递的．则一定是反对称的，否则会出现矛盾。这是因为，假定xy和yx，因为是可传递的，可得出xx，而R是反自反的，故总是反对称的。xRyyRxxy25/43拟序关系拟序关系和偏序关系的关系：定理：设R是集合中的二元关系。于是可有(a)如果R是个拟序关系,则是一个偏序关系。(b)如果R是个偏序关系，则R-Ix是个拟序关系。()xrRRI26/43全序关系定义：设是个偏序集合。如果对于每一个，或者x≤y或者y≤x，亦即,P,xyP()()()xyxPyPxyyx则称偏序关系≤是全序关系，简称全序，序偶称为全序集合。,P注意：P中具有全序关系的各元素，总能按线性次序x1,x2,…排列起来，这里当且仅当i≤j，才有xi≤xj,故全序也称为简单序或线性序，因此，序偶在这种情况下也被称为线性序集或链。,P27/43全序关系元素的可比性：设≤是集合P中的偏序关系。对于，如果有x≤y或y≤x,则P中的元素x和y称为可比的。在偏序集合中，并非任何两个元素x和y都存在有x≤y或y≤x的关系。事实上，对于某些x和y来说，和可能没有关系。在这种情况下，称x和y是不可比的。正是由于这种原因，才把称作“偏”序关系。在全序集合中，任何两个元素都是可比的。,xyP28/43全序关系例：设R是实数集合，a和b是R的元素。对于每一个实数a，设和S是集合并且。如果ab，则，因此是一个全序集合。{|0}aSxxa{|0}aSSaabSS,S如果A是个含有多于一个元素的集和，则不是一个全序集合。(),A例如，设A={a,b,c},(){,{},{},{},{,},{,},{,,}}Aabcacbcabc在上定义一个包含关系，可以看出{a}和{b,