第2章二元关系

1、 相关相关 :按照某种规则，确定二个对象或多个对象之间有关系，称这二个对象或多个对象是相关的。注意:相关性与指定的规则有关。 (1)扑克牌中的方块与梅花 同花关系：不相关； 同点关系：相关 (2)父子二人 同辈关系：不相关； 父子关系：相关注： 二元关系：二个对象之间的关系 多元关系：多个对象之间的关系 多元关系常化成二元关系来研究无序的二元关系：方块与梅花，谁在前，谁在后都还是同点的。有序的二元关系：父子关系，不能交换父与子的次序又如: （1） 偶数，与是无序的 用，表示无序对 （2），与是有序的二元关系，叫作相关 于，记成，用（，）表示有序对 （3）无序的二元关系可用有序的二元关系表示 即

2、（，）与（，）都属于这种二元关系 有序对的集合（，），b称为对的直交积，记为，又称叉积，又称叉积，笛笛卡儿卡儿（DescartesDescartes）乘积乘积。注：，不满足交换律，也不存在结合律！笛卡儿积满足分配律：（对， ）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）的证明：对（，）（） 且 ， （，），（，） （，）（）（） 即得（）（）（） 其次，对（，）（）（） （，）而（，）（） ，而 ， （，）（） 即得（）（）（） 因此，（）（）（）的几何意义： 设，均为实闭区间则有序对（，），是平面上一个点（1）表示矩形区域，（2）应为矩形区域， 注： （1）当且仅当时

3、，是正方形区域 （2）由于也是集合，它应满足集合的一切性质 按照某种规定，定义了一个有序对（，）的集合，其中，称为到的一个二元关系。(显然 R AB，即：即：AB的任意一个子集合都是的任意一个子集合都是A到到B的一的一个二元关系！个二元关系！)注意: 二元关系是指满足某规律的有序对的全体。例：（,）,R, 其中R读作相关于。*二元关系的表示：（1 ）集合法集合法 (穷举法、描述法穷举法、描述法 )（张三，铅球），（张三，足球），（李四，米），（李四，跳高），（王五，跨栏），（赵六，米）是运动会的报名表，（2）表格法用表格表示一目了然（3）图示法 用字母数字来代替这些元素 a，b，c，d，1，2

4、，3，4，5关系图，直观！(a, 3), (a, 4), (b, ), (b, 2),（c, 5),（d, 1）（4）矩阵法： 把，集合内元素排好序: 若（，），称为恒等关系，常用 IA表示。说明：对于一个给定的有限集合，其上的恒等关系 IA是唯一确定的。而且，恒等关系一定是A上的上的。例：A=1，2，3，4上的恒等关系为： IA =(1,1), (2,2), (3,3), (4,4) 设是上的二元关系， （1） 若对任意aA，(a,a)，则称为A上的自反关系。 自反的二元关系的关系矩阵对角元均为，即ii （，）。 （2）若对任意aA,(a,a) ，则称为A上的反自反关系。 的关系矩阵对角元素

5、均为，即ii （i=1，2，3，n）2.2.1 二元关系的基本类型自反关系任意(a,a) R反自反关系任意(a,a) R既不是自反的，也不是既不是自反的，也不是反自反的二元关系！反自反的二元关系！注意注意：不是自反的不一定是反自反的，不是反自反的也不一定是自反的。自反性与反自及性是互斥的，但不互补。 如下图： 对称关系与反对称关系对称关系与反对称关系 若（，），则有（，），则称这样的二元关系为对称关系。此时的相关矩阵是对称矩阵，即ijji 若（a,b） ,，则有（，） ，则称这样的二元关系为反对称关系。此时的关系矩阵满足ijji0（）对称关系若(a,b) R则(b, a) R（ab）反对称关系

6、若(a,b) R则(b, a) R（ab）既不是对称的，也不是既不是对称的，也不是反对称的二元关系！反对称的二元关系！注意注意：对称与反对称,既不互斥，又不互补。即:不是对称的，不一定是反对称的；反之依然。 如下图： （5）传递关系 设R是A上的二元关系，若满足当(a，b)R 且 (b，c)时，有(a，c)，则称这样的为A上传递关系。 例: 若A=1,2,3,4,下面哪个是A上的传递关系? R1=(1,2); R2=(1,2),(2,3),(1,3) R3=(1,1),(2,2); R4=(1,2),(2,3),(3,4),(3,1) R5=AA二元关系的性质二元关系的性质：对应于关系图，有：

7、（1）自反关系：每个顶点都有自回路，（2）反自反关系：每个顶点都没有自回路；（3）对称关系：任意两个顶点间或没有边，或有两条相向边；（4）反对称关系：任二顶点至多只有一条有向边；（5）传递关系：若到有边，到有边， 则到必有边。 思考思考 那么，它们的那么，它们的关系矩阵又有什么特点关系矩阵又有什么特点？例：1（，）， ， 是自反的，rii=1; 不是对称的，(1,2) R1,而(2,1) R1 是反对称的，是传递的。 注：将改为，则无自反性，且是反自反的。例：2（，）整除， 是自反的，不是对称的，是反对称的，是可传递的。例：3（1，2）12，1，2(). 其中()是的幂集。 3是自反的，不是对

8、称的，是反对称的，是传递的。 注：若改为，则无自反性。例：4( a, b ) | a+b=偶数，a, 4是自反的，对称的，传递的， 因偶，偶， 则（）（）偶数。 所以, 4是传递的! 例：5(a,), b 互素，b 5 是 对称的，但不是自反的，也无传递性。 ）（kjiknkijaab1例见教材P30 (例2.6，2.7，2.8）1000000010000000110000011000000011100001110000111例如1、等价关系的表格及图形表示（p34，p35) 2.3.3 等价类和商集1 1、等价类、等价类:若R是A上的等价关系，aA，由中的所有与a等价的元素构成的集合，称为a

9、的等价类。a的等价类记为aR， 即 aR=x| xA且aRx注：注：等价关系把的元素分为若干类，各类之间没有公共元素。 把集合分为若干非空子集1,2,An满足：（1）当时, ij（2）A，使i（=1，2，n）, 即:niiAA1则集合Pr()1,2,n称为的一个划分划分。 2.3.4 2.3.4 集合的划分集合的划分定理定理1：上的等价关系确定了A的一种划分; 反之,给定了集合的任一种划分，也总可以找到上的一个等价关系。注：（）Pr（）（）当且仅当 Pr(） ， （）非空时Pr（）P（）P（）（的幂集）时， P（） 例：例： 张扑克 1（，）扑克与同花 2（，）扑克与同点 则: 1把分为四类同

10、花类， 2把分为类同点类。例：设例：设，（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，）则是等价关系是等价关系，但不直观，用关系图表示。 三个不连通的图三个不连通的图 二元关系R是自反的，对称的，传递的，且把分成了三个等价类，A/R， 商集的元素个数（即在下的等价类个数）称为的秩.2、等价关系R将A分成若干等价类，每个类选个代表组成新的集合称为A关于R的商集，表示为A/R。 即: 以集合A上的等价关系R确定的所有互不相同的等价类作为元素而构成的集合, 称为A关于等价关系R的商集.例：在上例中 A/RR ，R ，R 例例: : 设Aa

11、,b,c,d，给定1,2,3,4,5,6,如下：1=a,b,c,d 2=a,b,c,d 3=a,a,b,c,d 4=a,b,c 5= ,a,b,c,d 6=a,a,b,c,d 则1和2是A的划分，其它都不是A的划分。因为3中的子集a和a,b,c,d有交，4A，5中含有空集，而6根本不是A的子集族。 例例4 4： （，） （mod ），是整数集合上模同余的二元关系. 证明R是等价关系。证明：由于当（）时,（）(1)因 （）， 自反性(2)若（），则（）对称性(3)若（），（），则 （）（）（） 满足传递性,故是等价关系商集： I/R R，R ，R 其中 R ， R ， R ，小结： 给定集合A上

12、的一个等价关系总可以通过寻求互不相同的等价类找到集合A的一个划分； 反之反之，若给定了集合A的一个划分，若指定位于同一个子集中的两个元素是相关的，则这个关系一定是等价关系。 简言之，等价关系与划分可以相互确定。 上的二元关系，若是自反的，对称的，称为A上的相容关系。注注：等价关系必然是相容关系。*2.3.5 相容关系 定理：设C是集合A的一个覆盖，设R为A上的二元关系，其定义为Rba),(当且仅当元素ba,属于同一覆盖快，则R是A上的相容关系。我们可记上述定理中的由C确定的相容关系为R=R(C)。 若R是非空集合上的相容关系，B是相容类，在差集A-B中没有一个元素能和B中所有元素都是相关的，称

13、B是由相容关系R产生的一个最大相容类。例：课本P40 最大相容类求法：课本P40-41 （1）画出（简化的）相容关系图。 （2）找出所有互不相同的最大完全多边形。 最大完全多边形：孤立点、悬挂边、三边形、完全四边形、完全五边形. 由所有最大相容类所构成的集合称为集合A上的相容关系R所确定的完全覆盖，记为CR(A).例、已知集合A=129，134，345，275，347，348，当a，bA，且a，b至少有一个数码相同时（a，b）R，求R的所有最大相容类。 解：易知该二元关系为相容关系。其次，画出（简化的）关系图。最后，在图中找出所有最大的完全多边形，分别以这些最大的完全多边形的顶点作为元素构成的

14、集合即为所求。R的所有最大相容类为（4个）：129，134，129，275，345，275，347，134，345，347，348小结： 给定集合A上的一个相容关系总可以通过寻求最大相容类找到集合A的一个完全覆盖；反之，若给定了集合A的一个完全覆盖，若指定位于同一个子集中的两个元素是相关的，则这个关系一定是相容关系。 简言之简言之，相容关系与完全覆盖可以相互确定。 2.3.8 偏序关系 设是上的二元关系，如果满足：(1) 自反的； (2）反对称的；(3) 传递的,则称是上的偏序关系（半序关系）。例：， ， 1（，）， 2（，）|， 3（1，2）|12，1，2P()注：（1）用矩阵表示偏序关系，

15、不能明显看到二元关系的特征。（2）用简化的关系图表示较适合。 简化的关系图： (1)自反性：每个顶点都有自回路，省去。 (2)反对称性：两个顶点间只可能有一个箭头 从左右，或从下上的方向 从小到大安置顶点，可省略箭头。 (3)传递性：由于有（a,b),(b,c)R,则(a,c)R 故只画（a,b),(b,c)对应的边,省略边(a,c)。HasseHasse图图（哈斯图） 设是上的一个偏序关系，如果，则将画在下面，且不，使，(此时此时也称也称b b是是a a的盖住元素的盖住元素, , 或称或称a a被被b b盖盖住住)，则，间用直线连接。符合简化的关系图的绘制，称这样得到的关系图为哈斯图。例中:

16、 偏序关系R1的哈斯图如右：R1哈斯图的画法：哈斯图的画法：1）确定最底层元素（均为极小元！即不是盖住元素的元素不是盖住元素的元素）2）第i层是第i-1层元的盖住元素，层层向上。3）相邻层的顶点根据盖住关系进行连线。4）检查有无错漏连线。画哈斯图时的注意事项：画哈斯图时的注意事项：1）图中不应该出现三角形。2）图中不应该出现水平线。3）应尽量减少线的交叉，使图清晰。例题: 哈斯图的画法已知A=1,2,3,4,5,6,8,10,12,16,24, R是A上的整除关系. 第五层第四层第三层第二层第一层 上偏序关系，如果，都有，或，则称为上的全序关系。注：（1）全序的含义：中每两个元素均能比大小，即

17、任何两个元素都相关。（2）偏序则是部分有序。（3）“小于或等于”关系1是全序，“整除”关系 2和“包含于”关系3都是偏序。在整除关系2中，,，,，都排成了序，但与，与，与等在整除的意义上来说无法排出大小来。 集合及上的一个偏序关系组成的二元组（，）称为偏序集，也记之为（，）。注： 同一集合上的两个不同的偏序关系，可构成多个偏序集， 如前例1和2都定义在 ，上，其中1是小于或等于关系，2是整除关系，但（,1）与(,2）是不一样的偏序集。 若偏序集（，）的偏序关系是上的全序关系，则称（，）为全序集。 （，1）是全序集。显然，全序集是偏序集的特例。又如：（，）实数全体，在下是全序集。平面上点集，也可

18、以规定一种，模长大的大，模长相等的情况下，以幅角的大小来比大小，因此，平面上点集也是全序集。（，）当然也是全序集。注:实数全体，平面点集是无法用哈斯图表示的。一般来说，对有限集用哈斯图比较好，对可列集只能示意一下，对不可列无限集是没法表示的，因为任二个数之间一定还有别的数。 设（，）是偏序集，是的子集合，若（，）是全序集，则称为（，）中的链。 当是有限集时，的基数称为链长。例： 在上例哈斯图（，2）中，取11，2，4，8，2|（整除），则 （1，2）是全序关系，1是偏序集（，|）中链长为的链。 2，3， 4，5，也都是（，|）中的链。 设（，）为偏序集，是的子集合，且对，（）,都有（，）且（，

19、），则称为（，）中的反链。 当为有限集时，为反链的长度。注： 反链中的元素都互不相关。反链中的元素都互不相关。例如：，2是整除关系，在（，2）中，1， 12， 23，3都是反链。 设（A，）是偏序集，若，且在中找不到一个元素（），使（），则称为中的极大元（极小元）。例：（，|）是偏序集，|是整除关系， ，则 中极大元：， 中极小元：，注注1 1：极大元，极小元必须是子集中的元素。注注2 2：极大元，极小元并不要求唯一，且同一元素，可以既是极大元，又是极小元，如，。 设（A，）是偏序集，若存在某个，对都有(或），则称为的最大元（最小元）。例：例：上例，其哈斯图如下： 子集中是不存在最大元（最小元

20、）的。注： 最大元（最小元）本身应属于子集，且与中任一元素都有关系。 设（A，）是偏序集，BA，若A，对 B都有（或）称为B的上界（下界）。注：（1）上例中，无最大元，但存在的上界。（2）无最小元，1是的下界（3）最大（小）若存在，则是的一个上（下）界（4）上（下）界可以不唯一，也可以不存在 设（A，）是偏序集，BA，若是B的一个上界（下界），而对任意B的上界（下界）b，都有ab（或ba），称是B的上确界（下确界）。注注： 上确界：最小上界 下确界：最大下界 如果存在上/下确界，则上/下确界一定是唯一的。 存在上/下界，但不一定存在上/下确界。例：试求出上面两个哈斯图中的最大例：试求出上面两个

21、哈斯图中的最大/小、极大小、极大/小元素，以小元素，以及左图中子集及左图中子集2，3，4的上的上/下界以及上下界以及上/下确界。下确界。2.4.2.4.1 1 复合关系复合关系复合关系复合关系：若R是A到B的二元关系，S是B到C的二元关系，复合关系的求法复合关系的求法：（1） 关系图法：RS是由从A到C的所有通路两端点元素构成的有序对作为元素的集合。（2）矩阵法：设R、S的关系矩阵分别为MR、MS， 则： MRS=MR*MS例：课本P48-50易见RS为A到C的二元关系。),( ,),( ,B| ),(ScbRbabcaSRR与S复合记为RS，其定义为显然： 若1和2是到的二元关系，则（1）1

22、2(,b)|(a,b)1或 (,)2（2）12(,b)|(a,b)1且(,)2 （3）1-2(,b)|(a,b)1 但 (a,b) 2 （5）12(a,b)|(a,b)12 但(a,b)12逆关系逆关系 ：若R是A到B的二元关系，则称 =（b，a）|（a，b）R 是R的逆关系，即B到A的二元关系。例：设A=1，2，3，4，B=x，y，z R=（1，x），（1，y），（2，z）则R的逆关系为： =（x，1），（y，1），（z，2） 显然，它是一个B到A的二元关系。2.4.2.4.2 2 逆关系逆关系R的逆关系也常常记为1-R逆关系的求法：（1）集合法：有序对元素前后调换位置。（2）矩阵法：矩阵转

23、置。（3）关系图：每条有向边取反向。2.4.2.4.3 3 关系的闭包运算关系的闭包运算 设R是A上的关系，我们希望R具有某些有用的性质，比如说自反性。如果R不具有自反性，我们通过在R中添加一部分有序对来改造R，得到新的关系R ，使得R具有自反性。但又不希望R与R相差太多，换句话说，添加的有序对要尽可能的少。满足这些要求的R就称为R的自反闭包自反闭包。通过添加有序对来构造的闭包除自反闭包外还有对称闭包对称闭包和传递闭包传递闭包。 设R是非空集合A上的关系，若存在A上的二元关系R同时满足下面两个条件：（1）R是自反的（对称的或传递的）（2）R R（3）对A上任何包含R的自反（对称或传递）关系R有

24、R R。 则称R是R在A上的自反闭包自反闭包（对称闭包或传递闭包) 一般将R的自反闭包记作r(R)，对称闭包记作s(R)，传递闭包记作t(R)。1iiRniiR1 如果关系R是自反的和对称的，那么经过求闭包的运算以后所得到的关系仍就是自反的和对称的。但是对于传递的关系则不然。它的自反闭包仍旧保持传递性，而对称闭包就有可能失去传递性。 例如A=1，2，3，R=(2, 3)是A上的传递关系， R的对称闭包 s(R)=s(t(R)=(2, 3), (3, 2), 而 t(s(R)= (2, 3), (3,2), (2,2), (3,3) , 显然s(R)不再是A上的传递关系。从这里可以看出，如果计算关系R的自反、对称、传递的闭包，为了不失去传递性，传递闭包运算应该放在对称闭包运算的后边，若令tsr(R)表示R的自反、对称、传递闭包，我们能证明 tsr(R)=t(s(r(R) 例：例：若R是对称的，则Rn也是对称的，其中n是任何正整数。证明：证明：用归纳法用归纳法。 (1)当n=1，R1=R,显然是对称的。 当n=2时，若(x, y) R2, 由复合关系的定义知: 必存在zA,使得(x, z)R且(z