离散数学考前复习.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,离散数学考前复习,第一部分,数理逻辑,第二部分,集合论,第三部分,图论,第四部分,抽象代数,2,第一部分 数理逻辑,数理逻辑是用数学方法研究推理中前提和,结论之间的形式关系的学科。,推理是由一个或几个判断推出一个新判断的思维形式。,数学方法是指建立一套表意符号体系，对具体,事物进行抽象的形式研究的方法。,3,第一章,命题逻辑,第二章,一阶谓词逻辑,第一部分 数理逻辑,4,1.1,命题和命题联结词,1.2,命题公式及其赋值,1.3,等值演算与联结词完备集,1.4,析取范式与合取范式,1.5,推理的形式结构,1.6,自然推理系统,P,第一章 命题逻辑,5,1.,命题,：,能判断真假的陈述句。,包含两层意思：,（,1,）必须是陈述句。,（,2,）能够确定（分辨）其真值。,1.1,命题和命题联结词,6,1.1,命题和命题联结词,7,2.,命题的真值：判断结果,注意：此处不纠缠具体命题的真假问题，只是将其作为数学概念来处理。,真值：真用,T,或,1,表示，假用,F,或,0,表示。,3.,命题和真值的符号化,1.1,命题和命题联结词,8,大家有疑问的，可以询问和交流,可以互相讨论下，但要小声点,9,1.1,命题和命题联结词,10,原子命题：不能被分解为更简单的陈述句,复合命题：原子命题通过联结词联结而成,例：,2,是有理数是不对的；,2,是偶素数；,2,或,4,是素数；如果,2,是素数，则,3,也,是素数；,2,是素数当且仅当,3,也是素数。,p,：,2,是有理数，,q,：,2,是偶数，,r,：,2,是素数，,s,：,3,是素数，,t,：,4,是素数。,1.1,命题和命题联结词,11,4,、命题联结词,1.1,命题和命题联结词,12,王化不但成绩好而且品德好。,pq,：,1.1,命题和命题联结词,13,1.1,命题和命题联结词,开关坏了或灯泡坏了。,pq,：,14,例：,1.,张晓婧爱唱歌或爱听音乐。,2.,张晓婧是内蒙人或是陕西人。,3.,张晓婧只能挑选,202,或,203,房间。,1.1,命题和命题联结词,注意：当排斥或两边的情况实际根本不可能同时发生的时候，排斥或也,可抽象为,。但为了方便起见一般不这样抽象。,15,有位父亲对儿子说：“如果我,去书店，就一定给你买电脑,报“。问：在什么情况下，,父亲算失信呢？,1.1,命题和命题联结词,16,注意：,“,只要,p,，就,q,，因为,p,，所以,q”,，“,p,仅当,q”,，,只有,q,，才,p“,，”除非,q,才,p“,，”除非,q,，否则非,p“,都可,抽象为,pq,。,p,，,q,可以没有任何内在联系。,例：,1.,如果,3,3,6,，那么雪是白的。,2.,除非我能工作完成了，我才去看电影。,3.,只要天下雨，我就回家。,4.,我回家仅当天下雨。,pq,的逻辑关系为,q,是,p,的必要条件或,p,是,q,的充分条件。,1.1,命题和命题联结词,17,1.1,命题和命题联结词,p q,的逻辑关系为,p,与,q,互为充要条件,例：,1.3,是有理数当且仅当加拿大位于亚洲。,2.,两圆的面积相等，则他们的半径相等，,反之亦然。,18,1.1,命题和命题联结词,例：今天第一节课上离散数学或数据结构。,19,例：,p,：北京比天津人口多,q,：,2,2,4 r,：乌鸦是黑色的,1.1,命题和命题联结词,20,5,、语句形式化,1.1,命题和命题联结词,例：,2,是有理数是不对的；,2,是偶素数；,2,或,4,是素数；如果,2,是素数，则,3,也,是素数；,2,是素数当且仅当,3,也是素数。,p,：,2,是有理数，,q,：,2,是偶数，,r,：,2,是素数，,s,：,3,是素数，,t,：,4,是素数。,p,不对；,q,且,r,；,r,或,t,；如果,r,，则,s,；,r,当且仅当,s,。,21,1.1,命题和命题联结词,22,命题常元：表示具体确定内容的命题。,命题变元：表示不确定具体内容的命题。,1.2,命题公式及其赋值,23,1.2,命题公式及其赋值,同时约定,：（,1,）最外层的括号可以省去。,（,2,）不影响运算次序的括号也可以省去。,24,1.2,命题公式及其赋值,25,1.2,命题公式及其赋值,26,1.2,命题公式及其赋值,27,1.2,命题公式及其赋值,28,1.2,命题公式及其赋值,29,1.3,命题公式的等值式,30,基本等值式（,A,，,B,，,C,为任意命题公式）,1.3,命题公式的等值式,31,1.3,命题公式的等值式,32,因,A,，,B,，,C,可以代入任意的命题公式，故以上等值式称为等值式模式。,由已知的等值式推演出另外一些等值式的过程为等值演算。,1.3,命题公式的等值式,33,等值演算的应用：,1.,验证等值式,2.,判定公式的类型,3.,解决工作生活中的判断问题,1.3,命题公式的等值式,甲、已、丙,3,人根据口音对王教授是哪人进行了判断：,甲说：王教授不是苏州人，是上海人,已说：王教授不是上海人，是苏州人,丙说：王教授既不是上海人，也不是杭州人,结果,3,人中有一人全对，一人对一半，一人全错。问王教授是哪人？,34,联结词的完备集,n,个命题变元可以形成,2,2n,个不同的真值函数,对于每个真值函数，都可以找到许多与之等值的命题公式，,而每个命题公式对应唯一的与之等值的真值函数。,定义,.,设,S,是一个联结词集合，如果任何,n,（,n1,）元真值,函数都可以由仅含,S,中的联结词构成的公式表示，则,称,S,是联结词完备集。,35,联结词的完备集,36,1.4,析取范式与合取范式,定义：命题变元及其否定统称为文字。,仅由有限个文字构成的析取式称为简单（质）析取式。,仅由有限个文字构成的合取式称为简单（质）合取式。,注意：单个文字既是简单析取式又是简单合取式。,讨论：设,A,为含,n,个文字的简单析取式,若,A,中同时含,p,i,和,p,i,，则？,若,A,为永真式，则？,37,若,A,为永真式，则,A,中必同时含有,p,i,和,p,i,，反之亦然。,同理有，若,A,为简单合取式，,A,为永假式的充要条件是,A,中同时含有,p,i,和,p,i,。,定理,1.,一个简单析取式是重言式当且仅当它同时含有某,个命题变元及其他的否定。,一个简单合取式是矛盾式当且仅当它同时含有某,个命题变元及其他的否定。,1.4,析取范式与合取范式,38,定义：,由有限个简单合取式构成的析取式称为析取范式。,由有限个简单析取式构成的合取式称为合取范式。,析取范式与合取范式称为范式。,注意：单个文字、简单析取式、简单合取式都既是析取范,式又是合取范式。,1.4,析取范式与合取范式,定理,2.,一个析取范式是矛盾式当且仅当它的每个简单合,取式为矛盾式。,一个合取范式是重言式当且仅当它的每个简单析,取式为重言式。,39,定理,3.,任一命题公式都存在与之等值的析取范式和合取范式。,范式的求法：,消去公式中的蕴涵、等价和异或联结词,使用双重否定律和德摩根律，将公式中出现,的否定 词移到命题变元之前。,利用分配律、结合律将公式化为合（析）取,范式。,范式形式不唯一。,1.4,析取范式与合取范式,40,定义：在含有,n,个命题变元的简单合（析）取式中，若每个,命题变元和 它的否定式不同时出现，而二者之一必,出现且仅出现一次，且第,i,个命题变元或它的否定是,出现在从左算起的第,i,位上（字典序），称这样的简,单合（析）取式为极小（大）项。,性质：,n,个变元可以形成,2,n,个极小（大）项；,每个极小（大）项有且仅有一个成真（假）赋值；,每组赋值下仅有一个极小（大）项为真（假）；,所有极小（大）项的析（合）取为真（假）；,1.4,析取范式与合取范式,41,将极小项的成真赋值对应的二进制数转化为十进制数为,i,，,将对应的极小项记为,m,i,。,将极大项的成假赋值对应的二进制数转化为十进制数为,i,，,将对应的极大项记为,M,i,。,定义：设由,n,个命题变元构成的析（合）取范式中所有的简,单合（析）取式都是极小（大）项，则称该析取范,式为主析（合）取范式。,1.4,析取范式与合取范式,定理,.,任何命题公式都存在与之等值的主析取范式和主合取范,式，并且是唯一的。,42,1.4,析取范式与合取范式,公式法：,求析取范式,用同一律补进未出现的命题变元,消去永假或重复出现的变元和极小项,将极小项按下标从小到大排列,真值表法：列出公式及各极小项的真值表，将每组赋值下,公式及极小项真值都为真的极小项进行析取。,主析取范式的求法：,1.,公式法,2.,真值表法,43,1.4,析取范式与合取范式,应用：,1.,求公式的成真、成假赋值,成真赋值为析取范式中所含极小项的编码的二进制数,成假赋值为合取范式中所含极大项的编码的二进制数,由主析取范式可以直接求主合取范式：,1,求出主析取范式中未包含的极小项,2,求出与,1,中求出的极小项下标相同的极大项,3,做,2,中极大项之合取,44,1.4,析取范式与合取范式,3.,判断两公式是否等值,若,A,，,B,共含有,n,个命题变元，按,n,个命题变元求出,A,与,B,的,主析取范式,A,、,B,，若,A,B,，则,A,B.,2.,判断公式的类型,设,A,含有,n,个命题变元,A,为重言式当且仅当,A,的主析取范式含全部,2,n,个极小项；,A,为矛盾式当且仅当,A,的主析取范式不含任何极小项，此,时记为,0,；,A,为可满足式当且仅当,A,的主析取范式中至少含一个极小项。,45,例：要在,A,，,B,，,C,中挑选,2,名出国进修，选派时满足下列条件：,若,A,去，则,C,同去,若,B,去，则,C,不能去,若,C,不去，则,A,或,B,可以去,问有几种选派方案，分别是什么？,4.,解决实际问题,1.4,析取范式与合取范式,46,1.5,推理的形式结构,注意：,推理正确实际是排除前提真结论假的情况,推理是否正确与前提的排列顺序无关,推理正确并不能保证,B,一定为真,47,1.5,推理的形式结构,推理的形式结构,48,1.5,推理的形式结构,49,例：若下午温度超过,30,度，则王晓燕必去游泳。若她去游,泳，她就不会去看电影。所以若王晓燕没去看电影，,下午温度必超过了,30,度。,p,：温度超过,30,度,q,：王晓燕去游泳,r,：王晓燕去看电影,1.5,推理的形式结构,50,1.5,推理的形式结构,51,注意：,以上都是蕴含式模式,若某推理的形式结构与某定律一致，则推理正确,成立的等值式可产生两条定律,推理定律可产生相应的推理规则,1.5,推理的形式结构,52,1.6,自然推理系统,P,定义,.,一个形式系统,I,由以下,4,部分组成：,非空的字母表，记作,A(I),A(I),中符号构成的合式公式集，记作,E(I),E(I),中特殊的公式组成的公理集，记作,Ax(I),推理规则集，记作,R(I),任给的前提，应用规则得到结论（可能真）,任给的公理，应用规则得到结论（永真）,53,1.6,自然推理系统,P,54,1.6,自然推理系统,P,55,例：若小王是理科生，则他的数学成绩一定很好。如果,小王不是理科生，他一定是文科生。小王的数学成绩,不好。所以小王是文科生。,p,：小王是理科生,q,：小王是文科生,r,：小王的数学成绩很好,1.6,自然推理系统,P,56,例：如果小张和小王去看电影，则小李也去看电影。小赵,不去看电影或小张去看电影。小王去看电影。所以，,当小赵去看电影时，小李也去。,p,：小张去看电影,q,：小王去看电影,r,：小李去看电影,s,：小赵去看电影,1.6,自然推理系统,P,57,2.,归谬法,将结论的否定作为前提引入，能推出矛盾来，则推理正确,例：如果马会飞或羊不吃草，则母鸡就会是飞鸟。如果母,鸡是飞鸟，那么烤熟的鸭子还会跑。烤熟的鸭子不会,跑。所以羊吃草。,p,：马会飞,q,：羊吃草,r,：母鸡是飞鸟,s,：烤熟的鸭子会跑,1.6,自然推理系统,P,58,所有的人总是要死的。,苏格拉底是人。,所以苏格拉底是要死的。,p:,q:,r:,第二章 谓词逻辑,59,第二章 谓词逻辑,2.1,一阶逻辑命题符号化,2.2,一阶逻辑公式及解释,2.3,一阶逻辑等值式与置换规则,2.4,一阶逻辑前束范式,2.5,一阶逻辑的推理理论,60,2.1,一阶逻辑命题符号化,1.,个体词,所研究对象中可以独立存在的具体的或抽象的客体（事物）,表示具体的或特定的客体,表示抽象或泛指的客体,个体变项的取值范围称为个体域，用,D,表示,宇宙间一切事物组成的称为全总个体域,61,2.,谓词,用来刻划个体词性质及个体词之间相互关系的词,2,是有理数,x,是无理数,小王与小李同岁,x,与,y,具有关系,L,是有理数,是无理数,与,同岁,与,具有关系,L,F,：,G,：,H,：,L,：,2.1,一阶逻辑命题符号化,62,3.,量词：个体词之间的数量关系,（,1,）全称量词,“一切的”，“所有的”，“每一个”，“任意的”，“凡”，“都”,记作,4.,符号化,确定个体域,确定个体词、量词和谓词,确定联结词,2.1,一阶逻辑命题符号化,63,例：所有的人都是要死的。,有的人用左手写字。,注意：,全称量词的特性谓词必须作为蕴涵式的前件引入,存在量词的特性谓词必须作为合取式的合取项引入,同一命题，不同的个体域符号化的形式可能不同,未指明个体域即为全总个体域,2.1,一阶逻辑命题符号化,64,例：在美国留学的学生未必都是亚洲人。,有的兔子比所有的乌龟跑的快。,对任意的整数,x,，都存在整数,y,使得,x,y,10,。,注意：,多个量词出现时，顺序一般不能随便换,有些命题符号化形式不唯一,2.1,一阶逻辑命题符号化,65,2.2,一阶逻辑公式及解释,66,2.2,一阶逻辑公式及解释,67,合式公式也称谓词公式，简称公式,2.2,一阶逻辑公式及解释,68,2.2,一阶逻辑公式及解释,69,2.2,一阶逻辑公式及解释,70,2.2,一阶逻辑公式及解释,71,定理,.,闭式在任何解释下都变成命题。,2.2,一阶逻辑公式及解释,72,2.2,一阶逻辑公式及解释,73,定理,.,重言式的代换实例都是永真式，矛盾式的代换,实例都是矛盾式。,2.2,一阶逻辑公式及解释,74,2.3,一阶逻辑等值式与置换规则,第一组,命题逻辑中等值式模式的代换实例都是一阶逻,辑的等值式模式,第二组,一阶逻辑中特殊的等值式,75,2.3,一阶逻辑等值式与置换规则,76,D=N,，,F(x),：,x,是奇数,G(x),：,x,是偶数,2.3,一阶逻辑等值式与置换规则,77,2.3,一阶逻辑等值式与置换规则,78,2.3,一阶逻辑等值式与置换规则,79,2.4,一阶逻辑前束范式,为了方便使用谓词公式进行定理证明和逻辑推理，需要,把谓词公式变换为便于使用的规范形式，就是范式。,80,定理,1,：任一谓词公式都可以化成为与之等值的前束范式。,2.4,一阶逻辑前束范式,81,2.4,一阶逻辑前束范式,82,2.5,一阶逻辑的推理理论,在一阶逻辑中，称永真的蕴涵式为推理定律。若一个推理,的形式结构正是某条推理定律，则该推理显然是正确的。,第一组,命题逻辑推理定律的代换实例,第二组,由基本等值式生成的推理定律,第三组,以下重要定律,83,第四组,消去量词和引入量词的推理规则,1,、全称量词消去规则（,UI,）,2.5,一阶逻辑的推理理论,84,UI,规则成立的条件：,（,1,）取代,x,的,y,应为任意不在,A(x),中约束出现的个体变项；,（,2,）用,y,取代,A(x),中自由出现的,x,时，必须将所有的自由出现,x,都取代；,（,3,）自由变元,y,也可替换为个体域中任意的个体常元,c,，,c,为任意不在,A(x),中出现过的个体常项。,2.5,一阶逻辑的推理理论,85,含义：如果个体域的所有个体都具有性质,A,，则个体域中,的任一个个体都具有性质,A,。,2,、存在量词消去规则（,EI,）,含义：如果个体域存在有性质,A,的个体，则个体域中必有,某一个个体具有性质,A,。,2.5,一阶逻辑的推理理论,86,ES,规则成立的条件：,（,1,）,c,是个体域中使,A,为真的特定的个体常项；,（,2,）,c,不曾在,A(x),或前面的推导公式中出现过；,（,3,）,A,（,x,）中除,x,外还有其他自由变元时，不能用此规则,2.5,一阶逻辑的推理理论,87,3,、全称量词引入规则（,UG,）,UG,规则成立的条件：,（,1,）,y,在,A,（,y,）中自由出现，且,y,取任何值时,A,均为真；,（,2,）,x,不在,A,（,y,）中约束出现。,含义：如果个体域的任意个体都具有性质,A,，则个体域中,的所有个体都具有性质,A,。,2.5,一阶逻辑的推理理论,88,4,、存在量词引入规则（,EG,）,EG,规则成立的条件：,（,1,）,c,是个体域中某个确定的个体；,（,2,）代替,c,的,x,不在,A,（,c,）中出现过。,含义：如果个体域有某一个个体,c,具有性质,A,，则个体域中,必存在具有性质,A,的个体。,2.5,一阶逻辑的推理理论,89,定义,.,一阶逻辑自然推理系统,F,的定义,1.,字母表：同一阶语言的字母表,2.,合式公式：同一阶语言合式公式的定义,3.,推理规则,a.,前提引入规则,b.,结论引入规则,c.,置换规则,d.,假言推理规则,e.,附加规则,f.,化简规则,g.,拒取式规则,h.,假言三段论规则,i.,析取三段论规则,j.,构造性二难规则,k.,合取引入规则,l.UI,，,EI,，,UG,，,EG,2.5,一阶逻辑的推理理论,90,例,7,：证明逻辑三段论,所有的人总是要死的。,苏格拉底是人。,所以苏格拉底是要死的。,2.5,一阶逻辑的推理理论,91,2.5,一阶逻辑的推理理论,例,10,：如果一个人怕困难就不会获得成功。每一个人或,者获得成功或者是失败的。有些人未曾失败过，所以有,些人不怕困难。（个体域是人的集合）判断这个推理是,否正确。,例,9,：根据前提集合：同事之间总是有工作矛盾的，,张平和李明没有工作矛盾，能得出什么结论？,92,第二部分 集合论,第三章,集合代数,第四章,二元关系,第五章,函数,93,第三章 集合代数,3.1,集合的基本概念,3.2,集合的运算,3.3,集合恒等式,94,一、集合的概念,集合（,set),的含义：一个集合是作为整体识别的、确定的、互相区别的一些事物的聚集（全体或总体等,),。,构成一个集合的每个事物，成为这个集合中的元素或成员。集合一般用,A,、,B,、,C,表示，集合中的元素用,a,、,b,、,c,表示。但这不是绝对的，因为一个集合可以作为另一个集合的元素。,如果,x,是集合,s,的一个元素,记作,;y,不是集合,s,的元素，记作,3.1,集合的基本概念,95,例,1,：,1.,偶素数集合。,2.,二进制的基数集合。,3.,英文字母的集合。,4.,全体实数的集合。,5.,自然数集合。,6.,整数集合。,7.,有理数集合。,8.,素数集合。,3.1,集合的基本概念,96,3.1,集合的基本概念,集合的表示方法,:,1.,列举法（枚举法、外延法）,把集合的所有元素（元素较少时）写在一个花括号内,;,列出足够多的元素（元素很多或无穷时）以反映集合中元素的特征。,如例,1,中的,1,、,2,、,3,、,5,可分别表示为：,2,0,，,1,a,，,b,，,cz,，,A,，,B,，,CZ,1,，,2,，,3,97,3.1,集合的基本概念,2.,描述法（概括法）,将集合中的元素的性质用一个谓词公式来描述，,S=X|P(X),意义为,:,集合,S,由且仅由满足为此公式,P(X),的对象组成，即 ，当且仅当,p(a),为真。,如例,1,中的,4,、,6,、,7,可表示为：,3.,文氏图,用图形图像直观的描述集合之间的相互关系和有关运算。,98,3.1,集合的基本概念,几个常见集合的表示符号：,N,：自然数集合，,N=0,，,1,，,2,，,3,；,I,：整数集合；,P,：素数或质数集合；,Q,：有理数集合；,R,：实数集合；,C,：复数集合；,99,3.1,集合的基本概念,集合的特性,:,A.,互异性：一个集合的个元素是可以区分开的，即每一 元素只出现一次。,B.,无序性：集合中元素排列顺序无关紧要，即集合表示 形式的不唯一性。,例,2,：,a,，,b,，,c=b,，,c,，,a=c,，,a,，,b=a,，,c,，,b=,b,，,a,，,c=c,，,b,，,a,100,3.1,集合的基本概念,C.,确定性：任一事物是否属于某一集合，回答是确定的。,例,3,：“好书”的全体，这不构成集合。,注意：一个集合是已知的，指的是对任一元素，利用某种方法可以判断它是否是这个集合的元素，而不是把集合的每一个元素都给出来。,101,3.1,集合的基本概念,集合的元素可以是任何具体或抽象的事物，包括别的集合，但不能是本集合自身。,例,4,：在一个住着一些人家的偏僻孤岛上，岛上只有一个理发师,a,，,a,给且只给岛上所有不能自己理发的人理发。问谁给,a,理发？,102,定义,1.,设,A,和,B,是两个集合，若,A,中的每一个元素都是,B,的元素，则称,A,是,B,的子集，也称,B,包含,A,记作,3.1,集合的基本概念,定义,2.,设,A,和,B,是任意两个集合，若,A,包含,B,且,B,包含,A,，则称,A,与,B,相等，记作,A=B.,即，,二、集合的关系,103,3.1,集合的基本概念,定义,3.,若,A,是,B,的子集且 ，则称,A,为,B,的真子集，或称,B,真包含,A,，记作，,B,称为,A,的超集。,104,集合的相等关系的性质：,设,A,B,C,为,3,个集合，,集合的包含关系的性质,:,3.1,集合的基本概念,105,定义,4.,不包含任何元素的集合称为空集，记作或,3.1,集合的基本概念,三、特殊集合,106,定义,4,：在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全集，记作,E,。,定义,5.,集合中元素的个数称为基数或势，用,|A|,表示。,基数是有限数的集合称为有限集，否则称为无限集。,全集是相对的，不同的问题有不同的全集，即使是同一个问题也可以取不同的全集。,3.1,集合的基本概念,107,3.1,集合的基本概念,含,n,个元素的集合简称,n,元集，其含有,k(kn),个元素的子集称为它的,k,元子集。,定义,6.,由集合,S,的所有子集组成的集合，称为集合,S,的幂 集，记作,P,（,S,）。,表示为：,有限集,S,，,|P,（,S,）,|=2,|S|,例：,A,a,，,b,，,c,，,d,，,c,108,3.2,集合的运算,一、集合的基本运算,109,3.2,集合的运算,定义,5.,设,A,为集合，,A,的元素的元素构成的集合称为,A,的广义并，记作,A,。,110,3.2,集合的运算,A,x|,z(z,A,xz),若,A,A,1,A,2,，,A,n,，则,A,A,1,A,2,A,n,定义,6.,设,A,为非空集合，,A,的所有元素的公共元素构成的集合称为,A,的广义交，记作,A,。,A,x|,z(z,A,xz),若,A,A,1,A,2,，,A,n,，则,A,A,1,A,2,A,n,例：,A,a,，,b,，,c,，,a,，,b,，,e,B=a,C=a,，,c,，,d,111,集合运算的优先级：,高级：广义并、广义交、绝对补、求幂集；同级按从右向左的顺 序进行,低级：并、交、相对补和对称差；同级按从左向右的顺序进行,3.2,集合的运算,112,3.2,集合的运算,文氏图可以用来描述集合间的关系及其运算,.,在文氏图中,全集用矩形表示,子集用圆形表示,阴影部分表示运算结果的集合,.,二、文氏图,A,B,B,A,B,A,B,A,113,3.2,集合的运算,A,114,3.3,集合恒等式,一、集合运算定律,以下列出集合性质中最主要的几条基本定律，对于全集,E,的任意子集,A,，,B,，,C,，有：,115,3.3,集合恒等式,116,1,、,基本定义法,根据集合相等的充要条件等式两边互为子集或由定义进行等价推理。,2,、,公式法,利用已证明过的恒等式去证明另外的恒等式。若表达式中出现形为,A-B,的差集时，用功能完备律先将运算“,-”,转化为运算“”和“,”,。,二、集合恒等式证明,3.3,集合恒等式,117,3.3,集合恒等式,118,3.3,集合恒等式,119,3.3,集合恒等式,120,小 结,集合的概念,集合的特性,集合的表示方法,:,列举法、描述法、文氏图,集合的运算：并、交、补、差、求幂,集合间的关系：包含、相等,集合恒等式的证明：定义法、公式法、成员表法,121,第四章二元关系,4.1,有序对与笛卡儿积,4.2,二元关系,4.3,关系的运算,4.4,关系的性质,4.5,关系的闭包,4.6,划分和等价关系,4.7,偏序关系,122,定义,1.,由两个具有固定次序的个体,a,，,b,组成的序列,称为序偶,记作,.,其中,a,b,称为序偶的分量,.,定义,2.,设,和,是两个序偶,若,a=c,且,b=d,则称这两个序偶相等,记作,=.,区别,:,集合,a,b=b,a,=(a=b),4.1,有序对与笛卡儿积,123,例,3:,设,A=a,b,c,B=1,0,则,4.1,有序对与笛卡儿积,定义,3.,设集合,A,，,B,，以,A,的元素作为第一元素，,B,的元算作为第二元素,的有序对构成的集合称为,A,与,B,的笛卡儿积，记作,AB,，符号化为,AB,=|x,A,y,B,性质,1.A,=,，,A=,124,例,4:,设,A=a,b,B=0,1,C=u,v,则,4.1,有序对与笛卡儿积,125,4.1,有序对与笛卡儿积,126,4.1,有序对与笛卡儿积,127,性质,5.,若,A,C,B,D,，,则,A B,C,D,。,4.1,有序对与笛卡儿积,其逆命题不成立。,A=B=,，,成立；,A,，,B,，,成立；,A=,且,B,，不成立；,A,且,B=,，不成立。,128,定义,4.,由,n,个具有给定次序的个体,a,1,，,a,2,，,，,a,n,组成的序列，称为有序,n,元组，记作,，其中,a,i,称为第,i,个分量。,=,当且仅当,a,i,=b,i,（,i=1,，,2,，,3,，,，,n,）。,有序,n,元组仍然是序偶，即,=,，,a,n,。,4.1,有序对与笛卡儿积,129,定义,5.,设,A,1,，,A,2,，,，,A,n,是任意的,n,个集合，所有有序,n,元组,组成的集合，称为集合,A,1,，,A,2,，,，,A,n,的笛卡儿积，并用 表示。其中 （,i=1,，,2,，,，,n,）,4.1,有序对与笛卡儿积,130,4.2,二元关系,定义,1.,若一个集合满足以下条件之一：,（,1,）集合非空，且它的元素都是有序对,（,2,）集合是空集,则称该集合为一个二元关系。,一、关系的定义,131,4.2,二元关系,例,2:,任意两个集合,A,B,若,|A|=n,|B|=m,求,A,到,B,共有多少不同的二元关系,?,132,4.2,二元关系,二、特殊关系,133,例,5.,设,A=2,3,4,B=2,3,4,5,6,定义,A,到,B,的二元关系,R:aRb,当且仅当,a,整除,b.,求,R,M,R,R=,，,，,，,，,，,4.2,二元关系,三、关系的表示方法,134,4.2,二元关系,一个有限集合,A,上的关系,R,还可以用一个称为,R,的关系图来表示。,135,4.2,二元关系,aaaa,d,a,b,c,d,e,例,6,：设,A=a,，,b,，,c,，,d,，,e,，,A,上关系,R=,，,，,，,，则,R,的关系图为：,136,例,3:,设,A=1,2,3,4,5,6,B=a,b,c,d,R=,求,domR,ranR.,解,:domR=2,3,4,6,ranR=a,b,d,4.3,关系的运算,137,例,:1.Z,上的关系,.,3.,空关系的逆是空关系,.,例,3,中,R,的逆关系,R,-1,=,4.3,关系的运算,138,4.3,关系的运算,例：,1.R1=,是,的兄弟,，,R2=,是,的父亲,2.A=1,，,2,，,3,，,4,，,5,，,R,，,S,是,A,上的二元关系,R=,，,，,S=,，,，,，,139,4.3,关系的运算,关系是以序偶为元素的集合，故可对关系进行集合的运算以产生新的关系。作为关系，绝对补运算是对全关系而言的,。,140,4.3,关系的运算,2.A=1,，,2,，,3,，,4,，,5,，,R,，,S,是,A,上的二元关系,R=,，,，,S=,，,，,，,由此可知，合成关系不满足交换律，满足结合律。,141,4.3,关系的运算,142,定理,8.,关系矩阵的乘法满足结合律，即,M,R,1,（,M,R,2,M,R,3,）,=,（,M,R,1,M,R,2,）,M,R,3,4.3,关系的运算,定理,9.,设,R,1,是一个由,A,1,到,A,2,的关系，,R,2,是一个由,A,2,到,A,3,的关系，,，,R,n,是一个由,A,n,到,A,n+1,的关系（,A,i,都是有限集）。它们的关系矩阵分别是,M,R,1,，,M,R,2,，,，,M,R,n,，则合成关系,R,1,R,2,R,n,的关系矩阵,M,R,1,R,2,R,n,=M,R,1,M,R,2,M,R,n,。,143,定义,5.,设,R,为,A,上的关系，,n,为自然数，则,R,的,n,次幂定义为：,R,0,=|x,A=I,A,R,n+1,=R,n,R,4.3,关系的运算,幂运算的求解：,若,R,是列举法表示，可进行多次右复合；,例：,A=a,，,b,，,c,，,d,，,R=,，,，,，,144,例：设,A=a,，,b,，,c,，,d,，,R=,，,，,，,，则,R,0,，,R,2,，,R,3,，,R,4,。,R,0,=,，,，,，,R,2,=,，,，,，,R,3,=,，,，,，,，,R,4,=,，,，,，,4.3,关系的运算,145,若,R,用关系矩阵,M,表示，则,R,n,的关系矩阵是,M,n,；,若,R,是用关系图,G,表示的，则可由,G,得,R,n,的关系图,G,。,G,与,G,的顶点集合相同，考察,G,中每个顶点,x,，若在,G,中,从,x,出发经过,n,步长的路径到达顶点,y,，则在,G,中加一条,从,x,到,y,的边。当把所有顶点都考察完后，就得到,G,。,4.3,关系的运算,146,4.3,关系的运算,定理,10.,幂运算满足指数定律：,R,n,R,m,=R,n+m,（,R,n,）,m,=R,mn,幂运算的性质：,定理,11.,设,A,为,n,元集，,R,是,A,上的关系，则存在,s,、,t,N,，使得,R,s,=R,t,。,147,4.4,关系的性质,定义,1.,设,R,A,A,，,若,x(x,A,R),，则称,R,是自反的；,若,x(x,A,R),，则称,R,是反自反的；,若,x(x,A,R),y(y,A,R),，,则称,R,是非自反的。,定义,2.,设,R,A,A,，,若,x,y,(x,y,A,R,R),，,则称,R,是,A,上的对称关系；,若,x,y,(x,y,A,R,R,x=y),，,则称,R,是,A,上的反对称关系；,否则，则称,R,是,A,上的非对称关系。,148,空关系既是对称的又是反对称的,.,非空集合上的空关系是反自反的、对称的、反对称的、可传递的。,空集合上的空关系则是自反的、反自反的、对称的、反对称的和可传递的。,4.4,关系的性质,149,非空集合上的全关系是自反的、对称的、和可传递的。,例,2.S=a,，,b,，,c,，,S,上的关系,R,1,=,，,，,，,，,R,2,=,，,，,R,3,=,，,例,3.,在集合,S=a,，,b,，,c,，,d,上的关系,R,：,，,，,，判断,R,的性质。,4.4,关系的性质,定理,.,设,R,是,A,上的二元关系，那么,R,是传递的当且仅当,RR,R,。,150,4.4,关系的性质,根据定义可证明下面几个定理是成立的。,151,4.4,关系的性质,152,4.4,关系的性质,153,可能有某种关系，既是对称的，又是反对称的,。,例,4.S=a,，,b,，,c,，,S,上的关系,R=,，,，,某种关系，既不是对称的，也不是反对称的。,例,5.S,上的关系,Q=,，,，,定理,5.,设,R,在,A,上是反自反的和可传递的，则,R,必是反对称的。,4.4,关系的性质,154,例,6.,设,A=1,，,2,，,3,，,A,上的关系,R=,和,S=,都是,A,上的传递关系。,传递性对并运算不一定保持。,4.4,关系的性质,155,关系的闭包运算是关系上的一元运算，他把给出的关系,R,扩充成一新关系,R,c,，使,R,c,具有一定的性质，且进行的扩充又是最小的。,4.5,关系的闭包,156,该定义表明，,r,（,R,）（,s,（,R,），,t,（,R,）是包含,R,的,最小自反（对称，传递）关系。,必要性：,R=r,（,R,），由定义,1,（,1,）知，,r,（,R,）是自反的，故,R,是自反的。,4.5,关系的闭包,157,4.5,关系的闭包,158,4.5,关系的闭包,159,4.5,关系的闭包,160,4.5,关系的闭包,161,4.5,关系的闭包,162,4.5,关系的闭包,3.I,A,的自反、对称和传递闭包是什么,？,4.,空关系的自反、对称和传递闭包是什么？,例：,A=a,，,b,，,c,，,d,，,R=,，,，,，,163,设,R,、,r(R),、,s(R),、,t(R),的关系矩阵分别为,M,、,M,r,、,M,s,、,M,t,，则,M,r,=M+E,M,s,=M+M,M,t,=M+M,2,+M,3,+,设,R,、,r(R),、,s(R),、,t(R),的关系矩阵分别为,G,、,G,r,、,G,s,、,G,t,，则,考察,G,中的每个顶点，若没有环就加上一个，得到,G,r,；,考察,G,中每条边，若有,x,i,到,x,j,的单向边（,i,j,），则加,x,j,到,x,i,的反向边，得,G,s,；,考察,G,中每个顶点,x,i,，找出从,x,i,出发的所有,2,步、,3,步,n,步,长的路径（,n,为,G,中的顶点数）。设路径的终点为,x,j1,、,x,j2,、,、,x,jk,，若没有从,x,i,到,x,jl,（,l=1,，,2,，,k),的边，就加上这条,边。考察完所有的顶点后，得到,G,t,。,4.5,关系的闭包,164,4.5,关系的闭包,165,4.5,关系的闭包,166,4.5,关系的闭包,167,4.6,等价关系与划分,例：,A=1,2,3,4,5,6,7,8,，,R=|x,y,Axy(mod3),168,4.6,等价关系与划分,169,4.6,等价关系与划分,170,一个集合的划分往往不是唯一的。,4.6,等价关系与划分,171,4.6,等价关系与划分,等价关系与划分一一对应。,172,4.7,偏序关系,173,4.7,偏序关系,由以上定义可知，在具有偏序关系的集合中任取,x,、,y,，有,xy,、,x,y,、,x,与,y,不可比,例：,A=1,2,3,，,是,A,上的整除关系。,174,盖住关系的关系图称哈斯图,.,求法,:1.,省略关系图中每个结点处的自环,.,2.,若,xy,且,y,盖住,x,将代表,y,的结点放在代表,x,的结点之上,并在,x,与,y,之间连线,省去有向边的箭头,.,4.7,偏序关系,若,xy,但,y,不盖住,x,，则省去,x,与,y,之间的连线。,175,4.7,偏序关系,176,4.7,偏序关系,177,4.7,偏序关系,B,的最小元一定是,B,的下界，同时也是,B,的最大下界。,B,的最大元一