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