离散第四章二元关系小结.ppt

《离散第四章二元关系小结.ppt》由会员分享，可在线阅读，更多相关《离散第四章二元关系小结.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章二元关系小结第四章二元关系 本章讨论的关系（主要是二元关系），它仍然是一种集合，但它是比前一章更为复杂的集合。关系是笛卡尔乘积的子集，它的元素是有序二元组的形式，这些有序二元组中的两个元素来自于两个不同或者相同的集合。因此，关系是建立在其它集合基础之上的集合。关系中的有序二元组反映了不同集合中元素与元素之间的关系，或者同一集合中元素之间的关系。本章首先讨论关系的基本表达形式，然后给 出关系的运算，最后讨论几种常用的关系。2/634.1关系的基本概念定义：设 且 为n个任意集合，(a)称R为 间的n元关系；(b)若n=2，则称R为A1到A2的二元关系；(c)若，则称R为空关系；若，则称R为

2、全关系；(d)若，则称R为A上的n元关系。一、关系的定义3/63二、关系的相等定义：设R1为A1,A2,An间的n元关系，R2为B1,B2,Bm间的m元关系，如果：（1）n=m（2）若，则（3）把R1和R2作为集合看，R1=R2。则称n元关系R1和m元关系R2相等，记作R1=R24/634.2关系的性质定义：设R为A上的二元关系(1)若对每个，皆有，则称R为自反的。用式子来表述即是：R是自反的(2)若对每个，皆有，则称R为反自反的。用式子来表述即是：R是反自反的 5/634.2关系的性质(3)对任意的，若，则，就称R为对称的。用式子来表述即是：R是对称的(4)对任意的，若 且，则x=y，就称R

3、为反对称的。用式子来表述即是：R是反对称的 6/634.2关系的性质(5)对任意的，若 且，则，就称R为可传递的。用式子来表述即是：R是可传递的(6)存在，并且 而，就称R为不可传递的。用式子来表述即是：R是不可传递的 7/63集合的压缩和开拓定义：设R为集合A上的二元关系且，则称S上的二元关系 为R在S上的压缩，记为，并称R为 在A上的开拓。定理：设R为A的二元关系且，那么：(1)若R是自反的，则 也是自反的；(2)若R是反自反的，则 也是反自反的；(3)若R是对称的，则 也是对称的；(4)若R是反对称的，则 也是反对称的；(5)若R是可传递的，则 也是可传递的；8/634.3关系的表示定义

4、：设A和B为任意的非空有限集，R为任意一个从A到B的二元关系。以 中的每个元素为结点对每个 皆画一条从x到y的有向边，这样得到的一个图称为关系R的关系图。一、关系图例：A=1,2,4;B=3,5,6;关系R=,A124B3569/63二、关系矩阵定义：给定两个有限集合X=x1,x2,xm和Y=y1,y2,yn，R是从X到Y的二元关系，如果有：则称 是R的关系矩阵，记作MR。例：设A=1,2,3,4,R为定义在A上的二元关系，R=,，写出关系矩阵。10/634.4关系的运算注意：由于关系也是特殊的集合，因此集合的运算也适用于关系中。设R1和R2是从A到B的二元关系，那么，也是从A到B的二元关系，

5、它们分别被称为二元关系R1和R2的交、并、差分和对称差分。11/634.4关系的运算定义：设R是从X到Y的关系，S是从Y到Z的关系，于是可用RS表示从X到Z的关系，通常称它是R和S的合成关系，用式子表示即是：一、关系的合成例：给定集合X=1,2,3,4，Y=2,3,4和Z=1,2,3。设R是从X到Y的关系，并且S是从Y到Z的关系，并且R和S给定成：试求R和S的合成关系，并画出合成关系图给出合成关系的关系矩阵。12/63一、关系的合成定理：给定集合X,Y,Z和W，设R1是从 X到Y的关系，R2和R3是Y到Z的关系，R4是从Z到W的关系，于是有：13/63一、关系的合成合成运算是对关系的二元运算，

6、使用这种运算，能够由两个关系生成一个新的关系，对于这个新的关系又可进行合成运算，从而生成其它关系。定理：设R1是从X到Y的关系，R2是从Y到Z的关系，R3是从Z到W的关系，于是有14/63关系的幂定义：如果R1是从X1到X2的关系，R2是从X2到的X3关系，Rn是从Xn到Xn+1的关系，则无括号表达式 表达了从X1到Xn+1的关系。当X1=X2=Xn+1和R1=R2=Rn时，也就是说当集合X中的所有Ri都是同样的关系时，X中的合成关系 可表达成Rn，并称作关系关系RR的幂的幂。定义：给定集合X，R是X中的二元关系。设，于是R的n次幂Rn可定义成(a)R0是集合X中的恒等关系IX，亦即(b)15

7、/63关系的幂定理：给定集合X，R是X中的二元关系。设，于是可有 例：给定集合X=a,b,c，R1,R2,R3,R4是X中的关系，并给定给出这些关系的各次幂16/63关系的幂定理：设X是含有n个元素的有限集合，R是X中的二元关系。于是存在这样的s和t，能使，证明：集合X中的每一个二元关系都是 的子集，X有n个元素，有n2个元素，有 个元素，每一个元素都是 的一个子集，也是一种二元关系，因而，在X中有 个不同的二元关系。所以，不同的二元关系R的幂不会多于个。但是序列 中有 项，因此这些的方幂中至少有两个是相等的。证毕。17/63二、合成关系的矩阵表达和图解设集合X=x1,x2,xm,Y=y1,y

8、2,yn,Z=z1,z2,zp,R是从X到Y的关系，S是从Y到Z的关系，MR和MS第i行第j列的元素分别是aij和bij，它们是0或者1。则合成关系 关系矩阵上的元素为定义布尔运算：0+0=0，1+0=0+1=1+1=111=1，01=10=00=0对两个关系矩阵求其合成时，其运算法则与一般矩阵的乘法是相同的，但其中的加法运算和乘法运算应改为布尔加和布尔乘。18/63三、关系的求逆运算关系R的逆关系 定义如下：对于所有的 和 逆关系的关系矩阵：原关系矩阵转置逆关系的关系图：原关系图中颠倒弧线上箭头的方向。19/63三、合成关系的求逆运算定理：设R是从集合X到Y的关系。S是从集合Y到Z的关系。于

9、是有 证明：对于任何，和 来说，如果xRy和ySz，则会有 和，因为还有 和，所以又有。因此可有。利用关系矩阵也可以理解，的转置和 是一样的。20/63四、关系的闭包运算闭包的定义：给定集合X，R是X中的二元关系。如果有另一个关系 满足（1）是自反的(对称的、可传递的)；（2）（3）对于任何自反的(对称的、可传递的)关系，如果，则则称关系 为R的自反的自反的(对称的，可传递的对称的，可传递的)闭闭包。包。并用r(R)表示的R自反闭包，用s(R)表示R的对称闭包，用t(R)表示R的可传递闭包。21/63四、关系的闭包运算定理：给定集合X，R是X中的关系。于是可有(a)当且仅当，R才是自反的。(b

10、)当且仅当，R才是对称的。(c)当且仅当，R才是传递的。证明：仅给出（a）的证明过程 如果是R自反的，则R具有定义给出的应具备 的全部性质。因此有。反之，如果，则由定义的(1)得R是自反的。22/63四、关系的闭包运算定理：设X是任意集合，R是X中的二元关系，IX是X中的恒等关系。于是可有 在整数集合中，小于关系“”的自反闭包是“”；恒等关系IX的自反闭包是IX。不等关系“”的自反闭包是全域关系；空关系的自反闭包是恒等关系。23/63四、关系的闭包运算定理：给定集合X，R是X中的二元关系。于是可有 在整数集合中，小于关系“”的对称闭包是不等关系“”；小于或等于关系“”的对称闭包是全域关系；恒等

11、关系IX的对称闭包是IX；不等关系“”的对称闭包是不等关系“”。24/63四、关系的闭包运算定理：给定集合X，R是X中的二元关系。于是可有 当A是有限集时，A上只有有限个不同的关系，因此，存在某个正整数m，使得 事实上，可以证明，若，则25/63四、关系的闭包运算定理：设X是集合，R是X中的二元关系，于是有（1）如果R是自反的，那么s(R),t(R)也是自反的；（2）如果R是对称的，那么r(R),t(R)也是对称的；（3）如果R是可传递的，那么r(R)也是可传递的。证明（1）：若R是自反的，则对于所有的 都有 即s(R),t(R)是自反的26/63四、关系的闭包运算定理：设X是集合，R是集合中

12、的二元关系，于是有证明：27/63 这一部分介绍了关系的一般概念，即关系是笛卡尔的子集，那关系就是集合，于是集合上理论可以推广到关系上来，注意集合的相等和关系的相等有一点区别，关系的相等还要求定义域要相等 我们还介绍了关系的表示方法：集合表示法，关系图表示法，关系矩阵表示法 集合上的运算可以平移到关系上来，除此之外关系还有它独特的运算：复合运算，求逆运算和闭包运算28/63 我们学习了关系性质的形式化定义法：设是定义在X上的二元关系 自反的x(x R)R是反自反的 x(x R)R是不自反的 x(x X R)y(y X R)R是对称的 xy(x,y X R R)R是反对称的 xy(x,y X R

13、 R xy)29/63 R是不对称的=xy(x X yX R R)zw(z X w X R R)R是传递的 xyz(x,y,z X R R R)R是不可传递的 xyz(x,y,z X R R R)30/63第二部分是关于特殊关系的4.5特殊关系一、集合的划分和覆盖定义：给定非空集合S，设非空集合A=A1,A2,An，如果有则称集合A是集合S的覆盖。注意：集合的覆盖不唯一。例如：S=a,b,c，A=a,b,b,c，B=a,b,c，A和B都是集合S的覆盖。31/63定义：给定非空集合S，设非空集合A=A1,A2,An，如果有则称集合A是集合S的一个划分。划分中的元素Ai称为划分的类 类。划分的类的

14、数目叫划分的秩 秩。划分是覆盖的特定情况，即覆盖中元素互不相交的特定情况。32/63一、集合的划分和覆盖定义：设A和A是非空集合S的两种划分，并可以表示成如果A的每一个类Aj，都是A的某一个类Ai的子集，那么称划分A是划分A的加细，并称A加细了A。如果A是A的加细并且AA，则称A是A的真加细。33/63极小项、完全交集定义：划分全集E的过程，可看成是在表达全集的文氏图上划出分界线的过程。设A，B，C是全集E的三个子集。由A，B和C生成的E的划分的类，称为极小极小项或完全交集项或完全交集。n个子集生成2n个极小项，用 表示。34/63一、集合的划分和覆盖定理：由全集E的n个子集A1,A2,An所

15、生成的全部极小项集合，能够构成全集E的一个划分。证明：证明这个定理，只需证明全集E中的每一个元素，都仅属于一个完全交集就够了。如果，则，或，或；或。由此可见，定有这里 或是Ai或是 Ai。试考察两个不同的完全交集T。因为两个完全交集是不同的，就是说存在这样一个i，使得 和，因此可有，即；因而任何一个 都不能同时属于两个不同的完全交集。35/63二、等价关系定义：设X是任意集合,R是集合中的二元关系。如果R是自反的、对称的和可传递的，则称R是等价关系。即满足以下几点：如果R是集合X中的等价关系，则R的域是集合X自身，所以，称R是定义于集合X中的关系。例如 数的相等关系是任何数集上的等价关系。又例

16、如一群人的集合中姓氏相同的关系也是等价关系。但朋友关系不是等价关系，因为它不可传递。36/63元素的等价 设R是集合A上的等价关系，若元素aRb，则称a与b等价，或称b与a等价。定义：设m是个正整数，。如果对于某一个整数n，有x-y=nm,则称x模m等价于y，并记作 整数m称为等价的模数等价的模数。“”表示模m等价关系R。37/63二、等价关系定理：任何集合 中的模m相等关系，是一个等价关系。证明：设R是任何集合 中的模m相等价关系。如果X=，则R是个空关系，显然有是自反的、对称的和可传递的。如果X，则需考察下列三条：(1)对于任何 来说，因为x-x=0m，所以有。因此，模m相等关系是自反的。

17、(2)对于任何 来说，如果，则存在某一个，能使x-y=nm。于是可有y-x=(-n)m，因此有，即模m相等关系是对称的。(3)设，和。于是存在，能使 和。而，从而可有，即模m相等关系是可传递的。38/63等价类 定义 设 是集合A上的等价关系，则A 中等价于元素 的所有元素组成的集合称为 生成的等价类，用 表示，即 说明：简单起见，有时候把aR简单写作a。39/63等价类例：设X=a,b,c,d，R是X中的等价关系，并把R给定成 则：40/63二、等价关系定理：设R是非空集合X中的等价关系。R的等价类的集合，是X的一个划分。定义：设R是非空集合X中的等价关系。R的各元素生成的等价类集合 称按R

18、去划分X的商集商集，记作X/R，也可以写成X(mod R)。由定义可知，按R对集合X的划分X/R是一个集合，并且X/R的基数是X的不同的R等价类的数目，因此X/R的基数又称为等价关系R的秩秩。41/63特殊的等价关系全域关系：令等价关系R1=X X，这里X的每一个元素与X的所有元素都有R1的关系。按R1划分X的商集乃是集合X。等价关系R1是全域关系。全域关系会造成集合X的最小划分。恒等关系R：X的每一个元素仅关系到它自身，而不关系到其它元素。显然，R是个恒等关系。按R划分X的商集，仅由单元素集合组成。恒等关系R会造成集合X的最大划分。最大划分和最小划分均称为X的平凡划分。42/63等价关系与集

19、合的划分定理：设C是非空集合X的一个划分，则由这个划分所确定的下述关系R必定是个等价关系，并称R为由划分C导出的X中的等价关系。证明：要证明R是个等价关系，就必须证明R是自反的、对称的和可传递的。(a)由于C是X的划分，C必定覆盖X。对任意的，必有x属于C的某一个元素S。所以对于每一个，都有xRx，即R是自反的。43/63三、相容关系定义：给定集合X中的二元关系R，如果R是自反的，对称的，则称R是相容关系，记作。也就是说，可以把R规定成：显然，所有的等价关系都是相容关系，但相容关系并不一定是等价关系。例如，设集合X=2166,243,375,648,455，X中的关系，可以看出R是自反的和对称

20、的，因此是一相容关系。44/63最大相容类定义：设是集合中的相容关系。假定。如果任何一个，都与其它所有的元素有相容关系，而X-A中没有能与A中所有元素都有相容关系的元素，则子集 称为最大相容类最大相容类。寻找最大相容类的方法：关系图法关系矩阵法45/63四、次序关系次序关系是集合中的可传递关系，它能提供一种比较集合各元素的手段。定义：设R是集合P中的二元关系如果R是自反的、反对称的和可传递的，亦即有 则称R是集合P中的偏序关系偏序关系，简称偏序偏序。序偶称为偏序集合偏序集合。46/63偏序关系通常用符号“”表示偏序。这样，符号就不单纯意味着实数中的“小于或等于”关系。事实上，这是从特定情况中，

21、借用符号去表示更为普遍的偏序关系。对于偏序关系来说，如果有 且xy，则按不同情况称它是“小于或等于”，“包含”，“在之前”等等。如果R是集合P中的偏序关系，则 也是P中的偏序关系。如上所述，如果用表示R，则用表示。如果是一个偏序集合，则也是一个偏序集合，称是的对偶。47/63偏序关系例：设I+=2,3,6,8，是I+中的“整除”关系。试表达出“整除”和“整倍数”关系。解：“整除”关系为“整倍数”关系是 实数集合R中的“小于”关系，都不是偏序关系，因为它们都不是自反的。但它们是实数集合中的另一种关系拟序关系。48/63拟序关系定义：设R是集合X中的二元关系。如果R是反自反的和可传递的，亦即有 则

22、称R是拟序关系，并借用符号“”表示。注意：在上述定义中，没有明确列举反对称性的条件，事实上关系若是反自反的和可传递的则一定是反对称的，否则会出现矛盾。这是因为，假定xy和yx，因为是可传递的，可得出xx，而R是反自反的，故总是反对称的。49/63拟序关系拟序关系和偏序关系的关系：定理：设R是集合中的二元关系。于是可有(a)如果R是个拟序关系,则 是一个偏序关系。(b)如果R是个偏序关系，则R-Ix是个拟序关系。50/63全序关系定义：设 是个偏序集合。如果对于每一个，或者xy或者yx，亦即 则称偏序关系是全序关系全序关系，简称全序全序，序偶 称为全序集合全序集合。注意：P中具有全序关系的各元素

23、，总能按线性次序x1,x2,排列起来，这里当且仅当ij，才有xixj,故全序也称为简单序或线性序，因此，序偶 在这种情况下也被称为线性序集线性序集或链链。51/63字母次序关系定义：设R是实数集合且P=RR。假定R中的关系是一般的“大于或等于”关系。对于P中的任何两个序偶 和，可以定义一个关系S 如果，则有,因此S是P中的全序关系。并称它是字母次序关系字母次序关系或字母序字母序。例如，52/63字母次序关系设R是X中的全序关系，并设 这个方程式说明，P是由长度小于或等于n的元素串组成的。假定n取某个固定值，可把长度为P 的元素串看成是P重序元。这样就可以定义P中的全序关系S，并称它是字母次序关

24、系。为此,设和是集合中的任何两个元素，且有pq。为了满足P中的次序关系首先对两个元素串进行比较。如果需要的话，把两个元素串加以交换，使得qp。53/63字母次序关系如果要使，就必须满足下列条件之一：如果上述条件中一个也没有得到满足，则应有 54/63五、偏序集合与哈斯图像表达相容关系时用简化关系图一样，通常使用较为简便的偏序集合图哈斯(Hass)图来表达偏序关系。定义：设 是一个偏序集，如果对任何，xy和xy，而且不存在任何其它元素 能使xz和zy，即 成立，则称元素y盖覆x。55/63偏序集合与哈斯图在哈斯图中，用小圈表示每个元素。如果有，且xy和xy，则把表示x的小圈画在表示y的小圈之下。

25、如果y盖覆x，则在x和y之间画上一条直线。如果xy和xy，但是y不盖覆x，则不能把x和y直接用直线连结起来，而是要经过P的一个或多个元素把它们连结起来。这样，所有的边的方向都是自下朝上，故可略去边上的全部箭头表示。56/63偏序集合与哈斯图定义：设 是一个偏序集合，并有。(a)如果对于每一个元素 有，则元素 称为Q的最小成员最小成员，通常记作0。(b)如果对于每一个元素 有，则元素 称为Q的最大成员最大成员，通常记作1。如果能画出哈斯图，就可以看出是否存在最大成员和最小成员。57/63偏序集合与哈斯图定理：设X是一个偏序集合，且有。如果x和y都是Q的最小(最大)成员,则x=y。证：假定x和y都

26、是Q的最小成员。于是可有xy和yx。根据偏序关系的反对称性，可以得出x=y。当x和y都是Q的最大成员时，定理的证明类似于上述的证明。58/63偏序集合与哈斯图定义：设 是一个偏序集合，并有。极大成员和极小成员都不是唯一的。不同的极大成员(或不同的极小成员)是不可比的。(a)如果，且不存在元素 能使qq和qq，则称q是Q的极小成员。(b)如果，且不存在元素 能使qq和qq，则称q是Q的极大成员。59/63偏序集合与哈斯图定义：设 是一个偏序集合，并有。(a)如果对于每一个元素 有，则元素 称为Q的上界上界。(b)如果对于每一个元素 有，则元素 称为Q的下界下界。60/63偏序集合与哈斯图定义：设

27、 是一个偏序集合，并有。(1)如果 是Q的一个上界，且对于Q的每一个上界q都有qq，则称q是Q的最小上界最小上界，通常记作LUB。(2)如果 是Q的一个下界，且对于Q的每一个下界q都有qq，则称q是Q的最大下界最大下界，通常记作GLB。如果存在最小上界的话，它是唯一的；如果存在最大下界的话，它也是唯一的。61/63良序关系定义：给定集合X，R是X中的二元关系。如果R是个全序关系，且X的每一个非空子集都有一个最小成员，则称R是个良序关系良序关系。与此对应，序偶称为良良序集合序集合。每一个良序集合必定是全序集台,因为对于任何子集来说，其本身必定有一个元素是它的最小成员。但是每一个全序集合不一定都是良序的，有限全序集合必定是良序的。62/63 这一部分介绍了特殊关系的运算：满足某些性质就是特种关系：等价关系（划分）相容关系（覆盖）偏序关系（哈斯图）63/63