离散数学导论

离散数学导论(第三版)徐洁磬,制作单位:咸宁职业技术学院电子系,第一篇绪言,一、介绍离散数学产生的背景。二、教学内容：1.计算机科学与离散数学由于计算技术的日益发展，计算机应用的日益拓广，计算机软件的日益丰富，计算机理论研究的日趋完善，从而产生了计算科学。在计算科学的研究中需要借助一些工具与方法，而离散数学正是研究计算机科学的有力工具。离散数学作为有力的数学工具，对计算机的发展，计算科学的研究起着重大的作用。远在计算机产生之前，图灵在研究可计算性问题时就建立了著名的图灵机。图灵机的基本结果思想为1946年机算计的问世，在理论上奠定了基础。在计算机发展的初期，利用布尔代数理论研究开关电路，从而建立了一套完整的数学逻辑理论，对计算机的逻辑设计起了很大作用。在近期，利用自动理论机理论研究形式语言；利用渭词演算研究程序正确性问题；利用代数结构研究编码理论；利用能行性理论研究计算机中的可计算性问题等，这些也是离散数学在计算科学研究中的应用。目前，离散数学在人工智能，数据库结构，软件工程，程序理论中等计算机研究领域中的作用越来越大。计算机科学普遍地采用离散数学的一些基本概念，基本思想，基本方法，使得计算机科学越趋完善与成熟。所有这些，使得离散数学成为了了解和学习计算机科学，掌握和研究计算机科学的必需的理论基础。在现代计算机科学中，如果不了解离散数学的基本内容，则在计算机科学研究中就会寸步难行。,2.离散数学之特怔,离散数学是数学的一个分之，它以离散数学作为其主要研究对象，如自然数，真假值，字母表等。这使它与数学分析（研究对象是连续量）在研究对象上形成了鲜明的差别。由于这两种数学在研究对象上的本质区别，使数学分为连续数学与离散数学两大类。在离散数学中非常重视“能行性”问题的研究。要解决个问题，首先要证明此问题解的存在性。但是，仅解决存在性还不够，还需要找出此问题解的步骤来，而且其步骤必须是有限的，有规则的。这就是所谓“能行性”问题的研究。离散数学的上述特征使得它成为研究计算机科学的基本数学工具。由于计算机是一个离散的结构，故计算机科学的研究对象大都是离散形式。在计算机科学的研究对象中任何一个问题不仅需要解的存在性，而且更需要解的能行性。因此，离散数学成了研究计算机科学的最合适的工具。,3离散数学的内容,由于离散数学是以离散量作为其研究对象，故一切以离散现象作为其研究对象或作为其研究对象之一的数学均可属于离散数学，如集合论，代数结构，数理逻辑，图论等。它还包括诸如组合数学，数论，离散概率等方面，但是其主要内容为前述的4个部分，因此在本教程中主要介绍集合论，代数结构，图论及数理逻辑这4部分内容。离散数学各分支间虽然其研究对象一致，但其研究方法各异，研究的侧重点也有所不同，故各具特色，它们互相补充，互相促进，互相渗透，逐渐形成了一门具有一定共性的学科。,第二篇集合论,本篇由集合论初步关系有限集与无限集等部分与集合论相关的内容组成，它们以集合概念为基础并进一步扩充与延伸组成一个内容关联的整体,离散数学导论,第一章集合论初步,集合的概念是一般数学及离散数学中的基本概念，亦是计算机科学中经常应用的基本概念集合论还能直接应用到计算机科学的各个部分中去,集合的基本概念,1.1.1集合及其元素首先，对集合及其元素的概念作一个说明。一些不同的确定对象的全体称为集合，而这些对象称为集合的元素。由此可见，集合是由元素组成的，元素可以理解为存在于世上的客观物体。当然，这些物体可以是具体的，也可以是抽象的，如人，书，桌子，花，太阳，地球，原子，自然数，实数，字母，点，三角形等。对于集合可以举一些例子。,例.地球上全体人构成一个集合，而每个人则是此集合的元素。例.计算机内存的全体存储单元构成一个集合，而每个存储单元为此集合之元素。例.全体自然数构成一个集合，而每个自然数是这个集合的元素。一般用带标号或不带标号的大写字母表示集合，如A，M，X1，Bi等，一般用带标号或不带标号的小写字母表示集合的元素，如a1，b2，x，y等。为了表示一个集合由那些元素组成，一般将集合的元素全部列出（元素间以逗号隔开）并左右用花括号括起，以表示由这些元素组成的集合。例如，元素A由元素a,b，c，d组成，则可以写成A=a,b,c,d,对于集合必须注意几点：集合中的元素是确定的，也就是说，对于集合A，任一元素a或属于此集合，或属于此集合，或不属于此集合，两者必居其一。若一元素a属于集合A，则用a属于A，若不属于A，则用a不属于A表示；集合中的每个元素均不相同，亦即集合a，b，c，d与集合a，b，c，d是一样的。除此之外，对集合不做任何其他限制，使它具有最广泛的含义。,对集合的元素也不做任何限制，甚至某一集合可以作为另一集合的元素，如A=1，2，a，b，其中集合a，b是集合A的元素。对于应用哪些构成一集合，从理论上讲也不做任何限制，当然，在实际应用时，它往往具有明确的范围。即事说，一集合的元素往往具有一共同的性质。对于集合元素的个数也不做任何限制，它可以是有限个，也可以是无限个。一集合若有有限个元素组成，则称为有限集；一集合若无限个元素组成，则称无限集。如自然数集即为无限集，地球上人的集合则是有限集，特别是，对元素个数为零的集合称做空集，记为空集。如“缺席今天会议的人”构成集合A，则今天全体出席会议表示A=空集。,与空集相对应的是全集，一个集合，如果它能包括人们所考虑的目标之内的所有元素，则此集合叫做全集，记为E。如讨论存储器时，则存储器的全体存储单元构成一个全集E。如讨论人的问题，则全体人类构成了一个全集E。前面已经提到集合的表示法，即集合A由元素a,b,c,d组成，可写为A=a，b，c，d，这种表示法称为“枚举法”，也就是将集合所有元素a，b,c,d组成，可写为A=a，b，c，d，这种表示方法称为“枚举法”，也就是将集合所有元素一一列出，但有时也只列出一部分元素，而其余部分可从前后关系中很显然地推出，如：A=1，2，3，4，。,表示全体自然数的集合，又如：A=1，2，3，4，。，100表示从1到100的100各自然数所构成的集合。前面所讨论的集合表示法称为显式表示法，集合还可用另一种方法表示即隐式表示法，这个方法是用一集合元素所具有的共同性质来刻画这个集合。如正偶数组成的集合A可写成A=x|x是正偶数对一般情况可用下面方式表示：A=x|P（x）其中p表示某性质，这个集合A表示由满足性质P的元素x所组成。,1.1.2集合间的关系,集合间一般有两种关系：相等关系与包容关系。定义1.1如果集合A与集合B的元素相同，则称这两个集合是相等的，记以A=B；否则，称这两个集合不相等，记以AB.定义1.2集合A.B,如果当aA必有aB,则称B包含A,或称A是B的子集,记以BA或AB.如果BA且存在于b,使得bB但bA,则称A是B的真子集,记以BA或AB.若集合A,B间不满足AB,则称B不包含A,记以AB.,例.设N=0,1,2,100,则有AN,并且有AN.例.设A=1,2,3,3,B=1,2,3,则有A=B.例.设A=i|i为正整数,B=j|j为正偶数,则有BA,且BA.对于集合的相等与包含关系,可以用一种文氏图（VennDiagram）表示.文氏图在表示集合间的关系时较为直观,形象,故目前被广泛应用.在文氏图中用一个平面图中的区域表示一个全集,而对包含于全集内的集合用平面区域内的圈表示之.这样,全集内的集合间关系就可用平面区域内圆之间的关系.对于相等,包含等关系可以很形象地用文氏图表示,如图1.1所示.,由定义可知，并、交运算满足结合律，即ABC=ABC1-3ABC=ABC1-4由定义还可知，并、交运算满足分配律，即AAB=ABAC1-5ABC=ABAC1-6由定义还可知得到有关空集、全集及补集的几个公式.它包括同一律:A=AAE=A互补律:AA=EAA=零一律:AE=EA=,对式1-11,可以证明:AE=(AE)E=E(AE)=(AA)(AE)=A(AE)=(AA)=E对式1-12,可以证明:A=(A)=(A)=(AA)(A)=AA=,还可以证明等幂律:AA=AAA=A对于式1-13,有A=A=A(AA)=(AA)(AA)=(AA)E=AA,对于式1-14,有A=AE=A(AA)=(AA)(AA)=(AA)=AA此外,还有两个吸收律:A(AB)=AA(AB)=A对于式1-15,有A(AB)=(AE)(AB)=A(EB)=AE=A,类似地,对于式1-16,A(AB)=(A)(AB)=A(B)=A=A可以证明,只有及E才能分别满足式1-7及式1-8此叫做及E的惟一性,即假设除外尚有X满足式1-7,则此时有AX=A.将X及分别代入上面第一式、第二式之A内,得到X=XX=,由类似的方法可证得只有E满足式1-9和式1-10此叫做A的惟一性，即假设除A外尚有A满足式1-9和式1-10.则有=(AA)=（A）（A）=（A）（A）=E（A）,=（A）（A）=（A）（A）=E（A）=（A）E=A同理可得A=A故A=A=A=由此证得A=,利用E、及A的惟一性可以证明双补律:（A）=A以及以下两个公式:E=E由于AA=E，AA=，这表示A是A的补集,由于补集的惟一性,因此可得到（A）=A。同法可得与E互补,因此由式1-111-12之A中分别代以及E:,E=E，E=由E及与惟一性即得=E，从而有=（E）=E最后,有德根定律（DeMorgansLaw）(AB)=AB(AB)=AB对于式(1-20),有(AB)(AB)=(ABA)(ABB)=（AA）BA(BB)=(EB)(AE)=EE=E而对式(1-21),有(AB)（AB）=（ABA）（ABB）,=（AA）ABA（BB）=（B）（A）=由补集的惟一性,可得(AB)=AB同理可得(AB)=AB到此为止,得到了有关集合代数的21个公式,下面举例说明这些公式的应用.例1.12某力图书管有藏书100万册,有一读者前往查阅,他希望能了解所有19世纪法国的发描写农民为题材的长篇小说,以及1999年我国出版的不是描写改革一放的长篇小说的书名.请将此读者要了解的书名用集合论方法描述之.解在此问题中,全集E为所有该图书馆藏书的书名所组成的集合,并合令:,F：所有问题的法国的书所组成的书名集;G:所有19世纪的书所组成的书名集;H:所有描写农民生活题材的书名所组成的书名集;R:所有长篇小说所组成的书名集;S:所有1999年出生版的书所组成的书名集;C:所有中国的书所组成的书名集;K:所有描写改革开放的书所组成的书名集;这样,此读者所要了解的书名可用集合的论方法描述.R（GFH）（SCK）例1.13设A、B、C为任意3个集合,已知AB,AB=AC,试证B=C解(ABC)(AB)(A(AC)=(AB)(A(AC)=A,1.2幂集、n元有序组及笛卡儿乘积,1.幂集定义1.9由集合的所有子集包括空集及A本身所组成的集合称为A的幂集,记以或。例1.15A=a,b，则=，a，b，A例116A=1，2，3,则=，1，2，3，1，2，1，3，2，3，A定理1.5若集合A为由n个元素所组成的有限集,则为有限且由个元素组成.证将中的每一个元素即为A的子集与一二制数建立一一对应关系.设A=,则建立一个n位的二进制数：，当A的某一子集中的出现有则对应的为1,当不出现有时,则对应的为0,这样,任一个A的子集就与一二进制数建立一一对应关系;给一个二进制数,可得到一个A的子集,反之,给出一个A的子集,可得到一个二进制.已知n位的二进制数共有个数,由此可知的元素共为个.2n元有序组定义1.10两个按一次序排列的客体a、b组成一个有序序列,称为有序偶,并记以a,b由定义可知,有序偶刻画了两个客体间的和次序,它并不表示由两个元素所组成的集合.在很多情况下客体间的次序是很重要的,如在一个平面直角坐标系中,点一般并不与相等,如;在一个表示月、日的有序偶中,表示3月8日,而8,3则表达8月3日,故（3，8）（，）有序偶（a,b）中的a,b分别称为（a,b）的第一客体与第二客体定义有序偶（a,b）与（c,d）,如果有a=c,b=d,则说（a,b）与(c,d)是相等的由有序偶的相等性可以看出，两个有序偶只有当其两个客体相同而且次序也相同时才相等,将有序偶推广到n元有序组。定义1.12n个(n1)按一定次序排列的客体组成一个有序序列,称为n元有序组,并记以定义1.13n元有序组与如果有=,(i=1,2,n)则说与是相等的.同样,n元有序组中的称为此n元有序组的第i个客体(i=1,2,n).例1.17表示时间的a年b月c日d时e分f秒可用一六元有序组(a,b,c,d,e,f)表示之.例1.18一个身份证号码是由所在省、市、区及出生年、月、日以及相应序列号等七元有序组组成（省、市、区、年、月、日、序列号）。,3笛卡儿乘积,在此节中利用n元有序组而引入笛卡儿乘积的的概念.设有两个集合A与B,用A与B的元素组成有序偶,以A的元素作为有序偶的第一个客体,以B的元素作为有序偶的第二个客体,用这种办法所组成的所有有序偶的全体构成一个集合,此集合称为A与B的卡笛儿乘积,可记为AB.由此可见,两个集合A、B的卡笛儿乘积是以一些有序偶为元素所组成的集合，这些有序偶的第一个客体取自集合A，第二个客体取自集合B，这样，可以对卡笛儿乘积下一个形式化的定义。,定义1.14集合A、B的卡笛儿乘积可表示为AB=（a，b）|aA，bB例1.19平面上直角坐标中的所有点可用一笛卡儿乘积表示:RR=x,y|aR,yR其中R表示实数集.例1.20一天之内的时间可用某时某分表示,它们的全体可用笛卡儿乘积表示:AB=a,b|aA,bB其中,A=0,1,2,23,B=0,1,2,59.类似地,可以定义n个集合A1、A2、An的笛卡儿乘积.定义1.15集合、的笛卡儿乘积可表示为,例1.21设A=1,2,B=a,b,C=,，则AB=（1,a）,(2,a),(1,b),(2,b)ABC=(1,a,),(1,a,),(2,a,),(2,a,),(1,b,),(1,b,),(2,b,),(2,b,)AA=(1,1),(1,2),(2,1),(2,2)一般可以用表示:AAA,亦即=AAA例1.22在计算机内的字是由固定的个有序二进制位所组成,它的全体可以表示如下形式:=AAA=|A，i=1，2，n,其中A=0,1.,=(，)|，,第二章节关系,在第一章中讨论了集合及它的元素,本章将研究集合内元素之间的关联以及集合之间元素的关联这就是“关系”.“关系”是很重要的基本数学概念,它在各数学领域(不仅在离散数学领域而且在其他数学领域)中均有很大的作用,并且对研究计算机科学中的许多问题都是很好的数学工具.,2.1关系的基本概念,2.1.1关系及其定义世界上存在着各种各样的关系,人与人之间有“同志”关系、“上下级”关系；两个数之间有“大于”关系、“等于”关系及“小于”关系；两个变量有一定的“函数”关系；计算机内两电路间有导线“连接”关系；程序间有“调用”关系。所以，对关系进行深刻的研究，对数学与计算机科学都有很大的用处。为了讨论关系，先从一个简单的例子着手。设一旅馆有N个房间，每个房间可住两个旅客，所以一共可以住2N个旅客。在旅馆内，旅客与房间有一定关系，讨论关系：“某旅客住在某房间”，有R表示这种关系，为讨论方便起见，设N=3，此时表示旅馆共有3间房间，分别记以1、2、3，而此时旅馆共住6个旅客，分别记以a、b、c、d、e、f,这些旅客住房的示意图如图2。1所示。,a1bc2de3f,图2.1旅客住房的示意图,由图2。1可以很清楚地看出，a与1间存在关系R，记以aR1；同样可以看出a与2间不存在关系R，记以aR2。可以将满足R的所有关系列出如下：（1）满足R的关系PRQ可看成是一个有序偶；（P，Q），如上面AR1可写成有序偶：（A，1）。（2）满足R的所有关系可看成是一个有序偶的集合，这个集合即可叫R，上例中R即为R=(a,1),(b,1),(c,2),(d,2),(e,3),(f,3)(3)上面这种关系称为二元关系，因为它仅牵涉到两个客体间的关系。当然，还可以有三元关系、四元关系及多元关系存在。但这里主要讨论二元关系，因为二元关系是最基本的关系，二元关系搞清楚了，多元关系也就清楚了。故书中除非特别说明，一般所指的关系均为二元关系。,这样，可以用有序偶的集合定义一个关系亦即是说关系是一些有序偶的集合，下面对此做进一步说明。（4）在上面的例子中若令A=（a,b,c,d,e,f）,B=1,2,3,则此例中关系的每一元素均属于AB,亦即R是AB的子集,或可写为R包含于AB.此时称此关系为从A到B的关系R,这样,可以给出关系的正式定义:定义2.1从集合A到集合B的一个关系R是AB的一个子集.关系R中有序偶第一个客体所允许先取对象的集合称为关系R的定义域,记以D(R),第二个客体所允许选取对象的集合称为关系R的值域,记以C(R).在特殊情况下,当D(R)=C(R)时,并且此时设D(R)=C(R)=M,为一集合,此时此关系为集合M上的关系.,例2.2实数集R上的“”关系可定义如下：=（x,y）|xR,yR且XY从此例可以看出:(35,24),但(24,35)不,此关系中有序偶的第一、第二客体均取自相同的集合R，故此关系称为集合R上的关系。在计算机领域内，关系的概念到处存在，在数据结构中，若是表格，则一张表格反映了此表格内容间的几种关系。如在虚拟存储器的页表中，它反映了虚页号与实质号间的关系（如表2。1所示）,表2.1,虚实页号对照表,在表2。1中所表示出来的关系可写成R=（0，13），（1，18），（2，15），（3，11）在一个大型的计算机结构中或一个大型软件结构中常说它们内部逻辑关系复杂，这是所指的“逻辑关系”即是此处所谓“关系”，只要将这些结构内的关系搞清，则任何结构的“正确性”、“可靠性”都会迎刃而解。与集合论中情况类似，如果从X到Y不存在某种关系R，则称此种关系为空关系，如果X的第个元素到Y的每个元素间均具有某种关系，则称此关系为全关系。从X到Y的全关系即为XY。还可以用类似的方法定义多元关系。,定义2。2由集合、所确定的n元关系是的一个子集。由此定义可以看出，n元关系是一些n元有序组的集合。2.1.2关系的图的表示法通常可以用图来刻画关系。一个集合X=上的关系R可用一关系图表示之。集合X中元素可用图中结点表示；关系R的有序偶可用图中从结点到结点的有向边表示。这样，即可将关系用图表示。,例2。3设有6个程序、，P它们间有一的调用关系R:R、R、R、R、R、R，这个关系是集合P=、上的关系,并且有R=(，)、(，)、(，)、(，)、(，)、(，)对于这样的一个关系可用一个图表示之，这个图如图2。2所示。由于一个图可用一个矩阵表示，故关系还可以用矩阵表示，在上例中可用下面的矩阵表示:,由于图的表示法较为直观，并且通过矩阵表示又可直接使用计算机计算，故关系的图形表示法对分析、研究关系起很大的作用。2。2关系的运算2。2。1关系的交、补、差由于关系是一些有序偶的集合，这样，有关集合的运算如集合的交、补、差等在关系中也是适用的。例如设X=a,b,c，Y=1，2，且有从X到Y的关系R=(a,1),(b,2),(c,1)，S=(a,1),(b,1),(c,1)，此时则有RS=(a,1),(b,1),b,2,(c,1)RS建立了一个新的关系，这也是一个从X到Y的关系，同理，还可以有RS=(a,1),(c,1)R=(a,2),(b,1),(c,2)R-S=（b,2）,上面这些关系的运算结果都建立了新的关系,而且也都是从X到Y的关系.以前这些关集合运算的一些公式在关系中也同样适用.除了上述的几种运算以外,在关系中尚有两种新的运算,它们是复合运算与逆运算,其结果所组成的关系称复合关系与逆关系,现分别介绍于下.2.2.2复合关系为说明复合关系,先以一例说明.设某人A与某人B有“兄妹”关系R，又设有某人C，而B与C有“母子”关系S，可以知道，A与C得到一个新的关系T“舅甥”关系，这个关系T乃是由关系R与S复合而得的，故关系T称为关系R与S的复合关系，下面用集合论的方法给出复合关系的定义。定义2。3设R是一个从X到Y的关系，S是一个从Y到Z的关系，则R与S的复合关系：RS可定义为RS=（x,z）|xX，zZ，至少存在一个yY有（x,y）R且（y,z）S这个复合关系是一个从X到Z的关系是一个从X到Z关系.,例2.4设R=1,2,3,4,2,2S=4,2,2,5,3,1到此时有RS=1,53,22,5SR=4,23,2SS=4,5RR=1,22,2复合关系也可用图形表示.现以一例说明.例2.5设X=,Y=,Z=从X到Y的关系R=从Y到Z的关系S=,由此可得到从X到Z的关系RS：它可以用图表示.如图示2.3所示,由R、S可很容易得到RS,即将与中通过有边相连接组成RS.,两个关系的复合亦可用矩阵运算来表示。设X=，Y=,Z=,从X到Y的关系，S是从Y到Z的关系,这样,关系R所表示的矩阵是一个m行n列的矩阵,关系S所表示的矩阵是一个n行p列的矩阵.因此有=在例2.5中:=故=注意:是的布尔矩阵,关系的复合是一种运算.称为关系的复合运算,这种运算满足结合律,下面的定理即证明这一点.定理2.1设R,S,T分别表示从X到Y，Y到Z，Z到U的关系，则有（RS）T=R（ST）证先证明（RS）TR（ST），其次证明R（ST）(RS)T。设（x,u）(RS)T，这样必存在某些zZ，有（x,z）RS，（z,u）T；进一步，必存在某些yY，有（x,y）R，（y,z）S，因为（y,z）S，（z,u）T，故必有y,z）ST；进一步，（x,y）R，（y,z）ST，故必有（x,u）R（ST）。由此证明了（RS）TR（ST），其次证明R（ST）(RS)T。定理得证。,定义2.4设有一个集合X上的关系，则可定义如下:由定义.很容易就能知道=2.2.3逆关系再介绍一种关系中的运算称为关系的逆运算,它是一种一元运算,其结果所组成的关系,由于关系的复合运算满足结合律,故可以将复合运算中的括号除去,亦即对于某个关系R自己与自己的复合运算是RR,可以表示.同理RRR可用表示,因此可以用的方式来定义关系的幂.,称关系的逆关系,先以一例说明,设有某程序a与另一程b而程序a可以调用程序b,因此a与b有调用的关系,反之程序b可被程序a所调用.因此a与b有被调用的关系,这样说被调用的关系是“调用关系的逆关系”,下面对一个关系的逆关系定义如下.定义2.5设R是一个从X到Y的关系,即R=x,yxX,yY,则从Y到x的关系:则有从Y到X的逆关系一个关系的逆关系可用图形及矩阵方法表示,一个关系P的逆关系R的图形是将表示R的图形中的有向边的方向改变后即得.例2.7XyYX,关系R的逆关系其矩阵是的转置矩阵,对于例2.7有=关系的逆关系满足下面的定理定理2.2设R,S分别是从X到Y及Y到Z的关系,则有=R此定理证明很容易请读者自己验证.,2.3关系的重要性质,关系的某些特质在研究关系中起很大的作用,在这一节中将给予介绍,关系的这些特殊性质即是关系的自反性、反自反性,关系的对称性、反对称以及关系的传递性.首先讨论关系的自反性及反自性.定义2.6在集合X上的关系R,如对任意xX,有x,xR,则称为自反性的,定义2.7在集合X上的关系R,如对任意xX,有x,xR,则称为R是反自反的,例2.8在整数集Z上的关系“”是自反的,不是反看的.例2.9在整数集Z上的关系“”是反自反的,不是自反的.例2.10在集合X=1,2,3,4上的关系R:R=1,11,23,42,24,2此关系既不是自反的也不是反自的,由此可知,一个关系的自反性与反自性可以都不存在.,一个关系的自反性在图形表示法中相当于一个关系图中的每个结点均有环出现,而一个关系自反性相当于一个关系图中的每个结均无环出现.下面讨论关系的对称性与反对称性.定义2.8在集合X上的关系R,如果有x,yR,必有y,x)R,则称P是对称的.定义2.9在集合X上的关系R,如果有x,y且xy,必有y,xR，则称R是反对称的。例2.11在一些人的集合中“同志”关系是对称的,“父子”关系则是反对称的.例2.12在整数集Z上的关系“”及“”均是反对称的.例2.13在集合X=1,2,3,4上的关系R:R=1,22,13,44,2此关系既不是对称的也不是反对称的.,关系的对称性在图形表示中相当于关系图中两个结点间如有有向边相连,则一定有主方向相反的两条有向边连接;一个关系的反对称性相当于关系图中的两个结点间如有有向边相连则一定只有一条边.最后,关于关系的传递性,有下面的定义:定义2.10在集合X上的关系R,如果有x,y且y,zR,则必有x,zR,则称R是传递的.例2.14在一些人的集合上,“同志”关系是传递的,但“父子”并不是传递的.例2,15整数集Z上的“”、“”关系均是传递的.例2.16在一些城市所组成的集合上.“线路的连通”关系是传递的.一些集合X上的关系可能具有上述5个性质中若干性质.例2.17整数集Z上的“”关系是反自反的、反对称的,然而是传递的.例2.18整数集Z上的“相等”关系是自反的、对称的,同时又是传递的.例2.19一些人所组成的集合上的“父子”关系是反自反、反对称的,亦是非传递的.如果将关系用图形表示,则关系的上述性质从图形中可以很容易看出.,例2.20用图示2.5所表示出来的集合X=1,2,3上的关系的5个图形,从图形中可以清楚地看出:,(1)是自反的、对称的,又是传递的(它是一个全关系).(2)是反自反的、反对称的,不是传递的.(3)不是自反的、对称的、传递的.(4)是反自反的、反对称的、传递的.(5)是反自反的、对称的、传递的且又不是对称的(它是一个空,112323具有某些特定性质的关系特别有用,如等价关系,偏序关系等,关于这些,将在后面讨论.2.4关系上的闭包运算本节讨论关系的一种新的运算闭包运算,由于这种运算比较特殊,也比较有用,故专列一节讨论.什么叫一个关系上的闭包运算呢?为了说明此问题现以一例表示.设有4个程序所组成的集合P=上的“调用”关系R：,这个关系可用图2.6表示已经知道,调用关系是传递的,如能调用,能调用,则亦有调用,现希望在R的基础上建立一个满足传递性的新关系,譬如说,下面的关系R即是这样的一个关系.,R=当然,满足这个条件的关系不仅仅R一个,如下面的关系R亦是:R=我们选用满足这个条件的最小者,在这个例子中即为R,这个R就称为上的传递闭包,R是一个新关系,它是在集合P上的一个新的调用关系.对于关系的自反性,对称性,传递性均可建立闭包,下面对闭包的概念给予明确的定义.定义2.11设R是集合X上的一个关系,则R的自反(对称,传递)闭包是一个满足下列条件的关系R:(1)R是自反的(对称的,传递的);(2)R,(3)设R是自反的(对称的,传递的)且R则必有RR通常用r(R)表示R的看反闭包;s(R)表示R的对称闭包;用t(R)表示R的传递闭包.可以举几个关于闭包的例子.例2.21整数集Z上的“”关系的自反闭包是“”关系;它是对称闭包是“”关系;它的传递闭包即是自身.例2.22集合X上的“=”关系：Q=它的自反闭包、对称闭包及传递闭包都是它自己。给出一个关系后总可以得到一个关系的闭包,对此有下面的一些定理.定理2.3设R是集合X上的关系,则r(R)=RQ,其中Q=（x,x）xX证令R=RQ,显然,R是自反的,其次R,如果设R是一个在X上的具有自反性的关系,且R,需求求证R.,.设(a,b)R,因为R=RQ,而对于a、b或a=b或ab,若a=b,则(a,b)Q,因为R是自反的,此时必有(a,b)R,若ab,则(a,b)R,此时必有(a,b)R,因为R,由此如(a,b)R则必有(a,b)R,由此证得R。由自反闭包的定义可如：例2。23上面提到过的程序集P=上的“调用”关系：R=如果程序还都能自己直接调用自己（即递归调用），亦即有Q=则RQ即构成一个自反闭包，它是一个“具递归调用”的关系：定理2.4设R集合X上的关系,则证:令，显然，,且R是对称的,如果设R是一个在X上具有对称性的关系且，需要求证设,则必有(a,b)R,因为.设(a,b)，这样必有()由此（)因为R是对称的,所以有,因此,如果则必有,由此证得，由此证得，由对称闭包的定义可知例2.24设程序集P=上的“调用”关系R=如果此“调用”关系尚有“双向调用”的功能,亦即还具有关系.=则是一个R的对称闭包,它是一个“具有双向调用”的关系.,定理2.5设R是集合X上的关系,则=证可以分两部分证明.先证对任一0有,用数字归纳法证明.由传递闭包的定义可知。假设,，令；因为，这表示必至少存在一个,并且有,，由归纳假设知，故有，因为是传递的,故，由此证得.,由于对每个均有，故有证明先证明是传递的，令是中的任意两个元素,这样必存在有，这样必有，因为由此可见是传递的由闭包定义可知:由此定理得证.当X为有限时,还有下面的理.定理2.6设R是有有限集合X上的关系,并设X有n个元素,此时有,证对任一0，有，因为当时,显然,当k时，设有，此时必存在序列：中且对,由于,故在至中必存在一些元素相等,譬如设，则此时，故可在序列中除去、,接这种办法,最后所得到的序列其个数为+1,，且，故有，亦即有由此定理得证例2.25程序集P=上的“调用”关系：,的传递闭包是t(R)=关于这个前面已有叙述，这是由于,2.5次序关系,研究具有某些性质的关系是比较重要的.在这一节时研究次序关系,它是一个满足反对称性及传递的关系,下面将研究各种类型的次序关系.,定义2.12集合X上的关系R如果是自反的,反对称的,传递的,则称R在X上是偏序的或称R是集合X上的偏序关系,而称集合X为R的偏序集用(X,R)表示.一般地用符号“”表示偏序(注意,此符号在这里并不表示为小于或等于).例2.26由集合A所组成的幂集上的关系“”是自反的,反对称的又是传递的,故它是偏序的.例2.27整数集上的“”(不是偏序的符号)是偏序关系.例2.28集合上的“整除”关系是偏序的定义2.13集合X上的关系R如果是反自反的，传递的，则称R在X上是拟序的或称R是集合X上的拟序关系。一般地用符号“”表示拟序（同样，在此该符号并不表示是小于）。例2.29由集合A组成的幂集P（A）上的关系“”是拟序关系,例2.30整数集Z上的“”（不是拟序符号）是拟序关系。对于拟序有下面的定理。定理2.7集合X上的关系R是拟序的，则其必是反对称的。证用反证法。设R不是反对称的则必至少存在两个元素，xX，yX它们有（x，y）R且（y，x）R。由于R是拟序的，故它是传递的，由此必有（x，x）R，但R又是反自反，故矛盾，由此定理得证。由此定理可知，拟序关系实际上是满足反自反，反对称且传递的关系。并且可以看出拟序关系与偏序关系之间有一定的联系偏序是拟序的扩充而拟序是偏序缩减。由拟序关系，偏序关系以及闭包的定义可知，拟序关系的自反闭包是一个偏序关系，由此可以很容易得到下面的定理（其证明从略）定理2.8设R是集合X上的关系，则如果R是一个拟序关系，则r（R）=RQ是一个偏序关系如果R是一个偏序序关系，则R-Q是一个拟序关系。,这个定理建立了集合X上的拟序与偏序间的联系，已经知道整数集Z上的“”关系是拟序的，她的自反闭包是“”，故“”是偏序的。集合上的“”关系是拟序的，它的自反闭包是“”，故“”是偏序的。集合X=2，3，6，8上的“整除”关系R=（2，2），（3，3），（6，6），（8，8），（2，6），（2，8），（3，6）是偏序的，则关系R=R-Q=（2，6），（2，8），（3，6）是拟序的。仔细分析偏序关系可以发现有两种不同的偏序关系。如例2.26中的Z上的“”关系。他能将Z中的所有数按关系“”进行比较，并按一定的次序排成一个序列，但也有另一种情况，如例2.27中集合X中的元素不能按“整除”关系进行比较，从而也不是按一定次序排成一个序列。又如，2与3即不能进行比较；3与8亦不能进行比较，故2，3，6，8，4个元素无法按传递关系排序由于存在上述两种不同的情况，有必要对偏序关系作更进一步的区分。定义2.14设R是集合X上的偏序，如果对每个x,yX必有xy或yx，则称x是线性次序的（也可叫全序的）或称R是集合X上的线性次序关系。例2.31集合X=a,b,c上的关系R=（a，b），（b，c），（a，c），（a，a），（b,b），（c,c）是线性次序的,例2.32集合A=a,b的幂集=,上的“”关系不是线性次序的应用上面的概念可以引入一个在计算机科学中常用的字典次序概念。设有一些抽象字母所组成的集合，这个集合是有限的，它可叫做字母表。在此集合上可建立一个线性次序关系“”，由内的字母所组成的字母串叫上的字，所有这些字（包括空字）组成一个集合，需要在上建立一个字典次序。,定义.设是一有限字母表，上的偏序关系是一个线性次序集，建立上的字典次序关系：设x，y，其中x,y；,且如，则说xy；如，则说yx如存在一个最大的k且kmin（n,m），使得，而，如果，则说xy；如，则说yx；如存在一个最大的kmin（n,m），使得，此时如，则说xy；如，则说yx,根据此定义可以明显地看出字典次序是一个线性次序。,例.目前一般外语字典都是按字典次序排列。如一英语字典则字母表为a,b,c，x,y,z，中的字母按a,b,c，x,y,z的顺序排列构成一线性次序。在上的任两个字均能区别其先后次序，如arc在and之后，bed在be之后。,例2。34计算机中定点二进制数的大小可认为是建立在字母表=0，1上的且有“”关系的字典次序。,定义2。16设集合X上有一个偏序关系“”且设Y是X的一个子集，则（1）如果存在一个元素yY对每个yy,则称y是Y的最元素;如果均有yy,则称y是Y的最小元素.(2)如果存在一个元素yY且在Y中不存在元素y有yy，且yy,则称y是Y的极大元素；如果Y中不存在元素y有yy且yy，则称y是Y的极小元素。（3）如果存在一个元素xX,对每个yy均有yx，则称x是Y的上界；如果均有xy,则称x是Y的下界。（4）如果xX是Y的上界且对每一个Y的上界x均有xx,则称x是y的上确界；如果x是Y的下界且对每一个Y的下界x均有xx，则x是Y的下确界。,这个定义所确定的最大元素，极大元素、上界、上确界（相应地：最小元素、极小元素、下界、下确界）等4个概念是有明确区别的，不能混淆。当然，有时它们所代表的元素有些是相同的，但这并不影响它们之间概念的不同，下面举一个例子来说明。,例2.35集合A=a,b,c的幂集，a,b,c,a,b,a,c,b,c,a,b,c上的“”关系是一个偏序关系。（1）设B=a,b，b,c，b，c,，则它没有最大元素，但它有极大元素：a,b，b,c；它的上界与上确界是相同的即是a,b,c，它的最小元素、极小元素、下界及下确界均相同即为（2）设B=a，c，则它的最大元素没有，极大元素是a和c，上界是a,c和a,b，上确界是a,c，它的最小元素没有，极小元素是a和c，下界是，下确界也。,虽然最大元素、极大元素、上界、上确界（相应地：最小元素、极小元素、下界、下确界）这4个概念间有着很大的区别，但是它们间也有一定的联系，下面的定理即叙述了这一点。,定理2。9设集合X上有一个偏序关系“”且设Y是X的一个子集，则（1）如果y是Y的最大（小）元素，则它亦必是Y的极大（小）元素（2）如果y是Y的最大（小）元素，则它亦必是Y的上（下）确界；（3）如果x是Y的上（下）确界，且xY，则x必是Y的最大（小）元素。证（1）用反证法。如果y不是Y的极大元素，则必存在一个yY，有yy且yy，这就表示y并非是Y的最大元素，而这个与假设矛盾，由此得证；（2）因为YX，由最大元素的定义立即可知y是Y的上界，设y也是Y的一个上界且yy，则必有yy，因为yY，yX-Y故y是Y的上确界；（3）如果yY是Y的一个上确界，则对任一yY必有yy，由此，y必是Y的最大元素。关于最小元素、极小元素、下确界间的联系其证明与此类似。由此定理得证。,为了说明与研究偏序关系，用一种图形的方法协助分析与研究是有益的，此种图称为哈斯（Hasse）图，哈斯图的画法可描述如下：对一个X上的偏序关系,对其X中的每个元素可用结点表示.如x,yX,且xy,则在图中将结点X画于结点y的下面,如x与y间不存在另一个z有:xz,zy则在x与y间用一线连接,由此所得到的图即为哈斯图.,例2.36整数集Z上的“”关系是偏序的，它可用哈斯图描述（如图2。7所示）。同时它还是一个线性次序关系，由此图可以很明显地看出“线性次序”的含义来。,例2。37集合X=2，3，6，12，24，36上的“整除”关系R是偏序的，它可用哈斯图表示（如图2。8所示）。,例2。38A=a,b，则（A）上的包含关系是偏序关系，它的哈其图如图2。9所示.,从上面3个例子可以看出，哈斯图比较形象地表示了集合上的偏序关系。当然，哈斯图的作用远不止于此，哈斯图对寻找最大（小）元素、极大（小）元素、上（下）界、上（下）确界等有很明显的作用。如例2。37中的图2。8，可以很明显地看出集合X没有最大元素，极大元素为24，36，同样地也没有上界与上确界。它的极小元素是2，3，但其余元素均没有。又如在例2。36中的图2。7可看出：自然数集N没有最大元素、极大元素以及上界、上确界，而它的最小元素、极小元素以及下界、下确界均为0。,2。6相容关系,定义2。17一个在X上的关系R，如果它是扑克反的、对称的，则称此关系为相容关系。,例2。39设有字母串集合：X=ab,bcd,ce,fe在X上的关系R是：字母串间有相同的字母，在此情况下，有R=（ab,bcd），（bcd,ce）,（ce,fe）,（bcd,ab）,（ce,bcd）,（fe,ce）,（ab,ab）,（bcd,bcd）,（ce,ce）,（fe,fe）它是扑克反的、对称的，故R是相容关系。,例2。40设X=2166,243,375,648,455，关系R为元素间有相同的数字。在此情况下R满足自反性与对称性，故R是相容关系。相容关系一般可以用“”表示。,一般来说，相容关系并不满足传递性，如2166243，243375，但21664375。,可以将相容关系用图表示。例2。39中的相容关系R可用图2。10（a）表示（为方便起见，用x1、x2、x3、x4分别表示4个X中的元素），考虑到表示相容关系的图中的边均是双向的且均有环出现，因此可以用图2。10（b）加以简化。,相容关系的关系矩阵是对称的，且对角线上诸元素均为1，在此情况下，公给出矩阵下部三角形部分就足够了。对例2。40的相容关系有如下的矩阵：,定义2。18设有集合X上的相容关系，设A是X的子集，如A中任何元素都互为相容，且X-A中的任何元素没有一个与A中的所有元素相容，则称A是X中的极大相容性分块。,例2。41前面例2。39中ab,bcd,bcd,ce,ce,fe均为极大相容性分块。,例2。42前面例2。40中x1,x2,x4,x2,x4,x5均为极大相容性分块。,从图的观点看，如果在图中各结点构成一个最大完全多边形，则这些结点构成了一个极大相容性分块。所谓“最大完全多边形”指的是这样的多边形，它的任一顶点与其他顶点相连（如三角形是，有对角线存在的四边形亦是）且这种多边形不能再行扩充。,例2。43图2。11（a）所示的集合X：1,2,3,4,5上的相容关系有两个极大相容性分块，它们是：1,3,4与2,3,4,5,相容性这个概念在现实生活中广泛存在，它相当于，“相似”、“有某些共同点”等，下面举一个实际例子。,例2。44同室4人每人都有一些爱好如下：A爱好游泳（a）、跳舞（b）、下棋（c）；B爱好跳舞（b）、游泳（a）；C爱好跳舞（b）、打球（d）；D爱好下棋（c）、游泳（a）。有相同爱好者必能谈得来，试给