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

第四章 二元关系小结,第四章 二元关系,本章讨论的关系（主要是二元关系），它仍然是一种集合，但它是比前一章更为复杂的集合。关系是笛卡尔乘积的子集，它的元素是有序二元组的形式，这些有序二元组中的两个元素来自于两个不同或者相同的集合。因此，关系是建立在其它集合基础之上的集合。关系中的有序二元组反映了不同集合中元素与元素之间的关系，或者同一集合中元素之间的关系。本章首先讨论关系的基本表达形式，然后给 出关系的运算，最后讨论几种常用的关系。,2/63,4.1关系的基本概念,定义：设 且 为n个任意集合，,(a)称R为 间的n元关系；,(b)若n=2，则称R为A1到A2的二元关系；,(c)若，则称R为空关系；若，则称R为全关系；,(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=R2,4/63,4.2关系的性质,定义：设R为A上的二元关系,(1)若对每个，皆有，则称R为自反的。用式子来表述即是：R是自反的,(2)若对每个，皆有，则称R为反自反的。用式子来表述即是：R是反自反的,5/63,4.2关系的性质,(3)对任意的，若，则，就称R为对称的。用式子来表述即是：R是对称的,(4)对任意的，若 且，则x=y，就称R为反对称的。用式子来表述即是：R是反对称的,6/63,4.2关系的性质,7/63,集合的压缩和开拓,定义：设R为集合A上的二元关系且，则称S上的二元关系 为R在S上的压缩，记为，并称R为 在A上的开拓。,定理：设R为A的二元关系且，那么：,(1)若R是自反的，则 也是自反的；,(2)若R是反自反的，则 也是反自反的；,(3)若R是对称的，则 也是对称的；,(4)若R是反对称的，则 也是反对称的；,(5)若R是可传递的，则 也是可传递的；,8/63,4.3关系的表示,定义：设A和B为任意的非空有限集，R为任意一个从A到B的二元关系。以 中的每个元素为结点对每个 皆画一条从x到y的有向边，这样得到的一个图称为关系R的关系图。,一、关系图,例：A=1,2,4;B=3,5,6;关系R=,9/63,二、关系矩阵,。,例：设A=1,2,3,4,R为定义在A上的二元关系，R=,，写出关系矩阵。,10/63,4.4关系的运算,注意：由于关系也是特殊的集合，因此集合的运算也适用于关系中。设R1和R2是从A到B的二元关系，那么，也是从A到B的二元关系，它们分别被称为二元关系R1和R2的交、并、差分和对称差分。,11/63,4.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,一、关系的合成,合成运算是对关系的二元运算，使用这种运算，能够由两个关系生成一个新的关系，对于这个新的关系又可进行合成运算，从而生成其它关系。,定理：设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，并称作关系R的幂。,定义：给定集合X，R是X中的二元关系。设，于是R的n次幂Rn可定义成,15/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,y2,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的关系。于是有,证明：对于任何，和 来说，如果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)当且仅当，R才是对称的。(c)当且仅当，R才是传递的。,证明：仅给出（a）的证明过程 如果是R自反的，则R具有定义给出的应具备 的全部性质。因此有。反之，如果，则由定义的(1)得R是自反的。,22/63,四、关系的闭包运算,定理：设X是任意集合，R是X中的二元关系，IX是X中的恒等关系。于是可有,在整数集合中，小于关系“”的自反闭包是“”；恒等关系IX的自反闭包是IX。不等关系“”的自反闭包是全域关系；空关系的自反闭包是恒等关系。,23/63,四、关系的闭包运算,定理：给定集合X，R是X中的二元关系。于是可有,在整数集合中，小于关系“”的对称闭包是不等关系“”；小于或等于关系“”的对称闭包是全域关系；恒等关系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)也是可传递的。,26/63,四、关系的闭包运算,定理：设X是集合，R是集合中的二元关系，于是有,证明：,27/63,这一部分介绍了关系的一般概念，即关系是笛卡尔的子集，那关系就是集合，于是集合上理论可以推广到关系上来，注意集合的相等和关系的相等有一点区别，关系的相等还要求定义域要相等我们还介绍了关系的表示方法：集合表示法，关系图表示法，关系矩阵表示法集合上的运算可以平移到关系上来，除此之外关系还有它独特的运算：复合运算，求逆运算和闭包运算,28/63,我们学习了关系性质的形式化定义法：设是定义在X上的二元关系自反的x(xR)R是反自反的x(xR)R是不自反的x(xXR)y(yX R)R是对称的xy(x,yXR R)R是反对称的xy(x,yXRR xy),29/63,R是不对称的=xy(xXyXRR)zw(zXwXR R)R是传递的xyz(x,y,z XR R R)R是不可传递的xyz(x,y,zXRR 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称为划分的类。划分的类的数目叫划分的秩。划分是覆盖的特定情况，即覆盖中元素互不相交的特定情况。,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所生成的全部极小项集合，能够构成全集E的一个划分。,证明：证明这个定理，只需证明全集E中的每一个元素，都仅属于一个完全交集就够了。如果，则，或，或；或。由此可见，定有,这里 或是Ai或是 Ai。试考察两个不同的完全交集T。因为两个完全交集是不同的，就是说存在这样一个i，使得 和，因此可有，即；因而任何一个 都不能同时属于两个不同的完全交集。,35/63,二、等价关系,定义：设X是任意集合,R是集合中的二元关系。如果R是自反的、对称的和可传递的，则称R是等价关系。即满足以下几点：,如果R是集合X中的等价关系，则R的域是集合X自身，所以，称R是定义于集合X中的关系。,例如 数的相等关系是任何数集上的等价关系。,又例如一群人的集合中姓氏相同的关系也是等价关系。,但朋友关系不是等价关系，因为它不可传递。,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相等关系是自反的。,(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去划分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,等价关系与集合的划分,证明：要证明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是自反的和对称的，因此是一相容关系。,44/63,最大相容类,定义：设是集合中的相容关系。假定。如果任何一个，都与其它所有的元素有相容关系，而X-A中没有能与A中所有元素都有相容关系的元素，则子集 称为最大相容类。,寻找最大相容类的方法：关系图法关系矩阵法,45/63,四、次序关系,次序关系是集合中的可传递关系，它能提供一种比较集合各元素的手段。,定义：设R是集合P中的二元关系如果R是自反的、反对称的和可传递的，亦即有,则称R是集合P中的偏序关系，简称偏序。序偶称为偏序集合。,46/63,偏序关系,通常用符号“”表示偏序。这样，符号就不单纯意味着实数中的“小于或等于”关系。事实上，这是从特定情况中，借用符号去表示更为普遍的偏序关系。对于偏序关系来说，如果有 且xy，则按不同情况称它是“小于或等于”，“包含”，“在之前”等等。,如果R是集合P中的偏序关系，则 也是P中的偏序关系。如上所述，如果用表示R，则用表示。如果是一个偏序集合，则也是一个偏序集合，称是的对偶。,47/63,偏序关系,例：设I+=2,3,6,8，是I+中的“整除”关系。试表达出“整除”和“整倍数”关系。,解：“整除”关系为,“整倍数”关系是,实数集合R中的“小于”关系，都不是偏序关系，因为它们都不是自反的。但它们是实数集合中的另一种关系拟序关系。,48/63,拟序关系,定义：设R是集合X中的二元关系。如果R是反自反的和可传递的，亦即有,则称R是拟序关系，并借用符号“”表示。,注意：在上述定义中，没有明确列举反对称性的条件，事实上关系若是反自反的和可传递的则一定是反对称的，否则会出现矛盾。这是因为，假定xy和yx，因为是可传递的，可得出xx，而R是反自反的，故总是反对称的。,49/63,拟序关系,拟序关系和偏序关系的关系：,定理：设R是集合中的二元关系。于是可有,(a)如果R是个拟序关系,则 是一个偏序关系。(b)如果R是个偏序关系，则R-Ix是个拟序关系。,50/63,全序关系,定义：设 是个偏序集合。如果对于每一个，或者xy或者yx，亦即,则称偏序关系是全序关系，简称全序，序偶 称为全序集合。,注意：P中具有全序关系的各元素，总能按线性次序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，并称它是字母次序关系。为此,设和是集合中的任何两个元素，且有pq。为了满足P中的次序关系首先对两个元素串进行比较。如果需要的话，把两个元素串加以交换，使得qp。,53/63,字母次序关系,如果要使，就必须满足下列条件之一：,如果上述条件中一个也没有得到满足，则应有,54/63,五、偏序集合与哈斯图,像表达相容关系时用简化关系图一样，通常使用较为简便的偏序集合图哈斯(Hass)图来表达偏序关系。,定义：设 是一个偏序集，如果对任何，xy和xy，而且不存在任何其它元素 能使xz和zy，即 成立，则称元素y盖覆x。,55/63,偏序集合与哈斯图,在哈斯图中，用小圈表示每个元素。如果有，且xy和xy，则把表示x的小圈画在表示y的小圈之下。如果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都是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,偏序集合与哈斯图,定义：设 是一个偏序集合，并有。,如果 是Q的一个上界，且对于Q的每一个上界q都有qq，则称q是Q的最小上界，通常记作LUB。如果 是Q的一个下界，且对于Q的每一个下界q都有qq，则称q是Q的最大下界，通常记作GLB。,如果存在最小上界的话，它是唯一的；如果存在最大下界的话，它也是唯一的。,61/63,良序关系,定义：给定集合X，R是X中的二元关系。如果R是个全序关系，且X的每一个非空子集都有一个最小成员，则称R是个良序关系。与此对应，序偶称为良序集合。,每一个良序集合必定是全序集台,因为对于任何子集来说，其本身必定有一个元素是它的最小成员。但是每一个全序集合不一定都是良序的，有限全序集合必定是良序的。,62/63,这一部分介绍了特殊关系的运算：满足某些性质就是特种关系：等价关系（划分）相容关系（覆盖）偏序关系（哈斯图）,63/63,