离散数学教程课件

1、离散数学,数学与信息科学学院,1,第一部分 数理逻辑 第二部分 集合论 第三部分 图论 第四部分 抽象代数,离散数学,2,第一部分 数理逻辑,数理逻辑是用数学方法研究推理中前提和 结论之间的形式关系的学科。,推理是由一个或几个判断推出一个新判断的思维形式。,数学方法是指建立一套表意符号体系，对具体 事物进行抽象的形式研究的方法。,3,第一章 命题逻辑 第二章 一阶谓词逻辑,第一部分 数理逻辑,4,1.1 命题和命题联结词 1.2 命题公式及其赋值 1.3 等值演算与联结词完备集 1.4 析取范式与合取范式 1.5 推理的形式结构 1.6 自然推理系统P,第一章 命题逻辑,5,1. 命题：能判断

2、真假的陈述句。,包含两层意思：,（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

3、是素数，t：4是素数。,1.1 命题和命题联结词,10,4、命题联结词,1.1 命题和命题联结词,11,王化不但成绩好而且品德好。,pq：,1.1 命题和命题联结词,12,1.1 命题和命题联结词,开关坏了或灯泡坏了。,pq：,13,例：1.张晓婧爱唱歌或爱听音乐。 2.张晓婧是内蒙人或是陕西人。 3.张晓婧只能挑选202或203房间。,1.1 命题和命题联结词,注意：当排斥或两边的情况实际根本不可能同时发生的时候，排斥或也 可抽象为。但为了方便起见一般不这样抽象。,14,有位父亲对儿子说：“如果我 去书店，就一定给你买电脑 报“。问：在什么情况下， 父亲算失信呢？,1.1 命题和命题联结词,

4、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,1.1 命题和命题联结词,p q的逻辑关系为p与q互为充要条件,例：1.3是有理数当且仅当加拿大位于亚洲。 2.两圆的面积相等，则他们的半径相等， 反之亦然。,17,1.1 命题和命题联结词,例：今天第一节课上离散数学或数

5、据结构。,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）

6、不影响运算次序的括号也可以省去。,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 命题公式的等值式,甲

7、、已、丙3人根据口音对王教授是哪人进行了判断： 甲说：王教授不是苏州人，是上海人 已说：王教授不是上海人，是苏州人 丙说：王教授既不是上海人，也不是杭州人 结果3人中有一人全对，一人对一半，一人全错。问王教授是哪人？,33,联结词的完备集,n个命题变元可以形成22n个不同的真值函数,对于每个真值函数，都可以找到许多与之等值的命题公式， 而每个命题公式对应唯一的与之等值的真值函数。,定义.设S是一个联结词集合，如果任何n（n1）元真值 函数都可以由仅含S中的联结词构成的公式表示，则 称S是联结词完备集。,34,联结词的完备集,35,1.4 析取范式与合取范式,定义：命题变元及其否定统称为文字。

8、仅由有限个文字构成的析取式称为简单（质）析取式。 仅由有限个文字构成的合取式称为简单（质）合取式。,注意：单个文字既是简单析取式又是简单合取式。,讨论：设A为含n个文字的简单析取式 若A中同时含pi和pi，则？,若A为永真式，则？,36,若A为永真式，则A中必同时含有pi和pi，反之亦然。,同理有，若A为简单合取式， A为永假式的充要条件是A中同时含有pi和pi。,定理1. 一个简单析取式是重言式当且仅当它同时含有某 个命题变元及其他的否定。 一个简单合取式是矛盾式当且仅当它同时含有某 个命题变元及其他的否定。,1.4 析取范式与合取范式,37,定义：由有限个简单合取式构成的析取式称为析取范式

9、。 由有限个简单析取式构成的合取式称为合取范式。 析取范式与合取范式称为范式。,注意：单个文字、简单析取式、简单合取式都既是析取范 式又是合取范式。,1.4 析取范式与合取范式,定理2. 一个析取范式是矛盾式当且仅当它的每个简单合 取式为矛盾式。 一个合取范式是重言式当且仅当它的每个简单析 取式为重言式。,38,定理3.任一命题公式都存在与之等值的析取范式和合取范式。,范式的求法：消去公式中的蕴涵、等价和异或联结词 使用双重否定律和德摩根律，将公式中出现 的否定 词移到命题变元之前。 利用分配律、结合律将公式化为合（析）取 范式。,范式形式不唯一。,1.4 析取范式与合取范式,39,定义：在含

10、有n个命题变元的简单合（析）取式中，若每个 命题变元和 它的否定式不同时出现，而二者之一必 出现且仅出现一次，且第 i个命题变元或它的否定是 出现在从左算起的第i位上（字典序），称这样的简 单合（析）取式为极小（大）项。,性质：n个变元可以形成2n个极小（大）项； 每个极小（大）项有且仅有一个成真（假）赋值； 每组赋值下仅有一个极小（大）项为真（假）； 所有极小（大）项的析（合）取为真（假）；,1.4 析取范式与合取范式,40,将极小项的成真赋值对应的二进制数转化为十进制数为i， 将对应的极小项记为mi。 将极大项的成假赋值对应的二进制数转化为十进制数为i， 将对应的极大项记为Mi。,定义：设

11、由n个命题变元构成的析（合）取范式中所有的简 单合（析）取式都是极小（大）项，则称该析取范 式为主析（合）取范式。,1.4 析取范式与合取范式,定理.任何命题公式都存在与之等值的主析取范式和主合取范 式，并且是唯一的。,41,1.4 析取范式与合取范式,公式法：求析取范式 用同一律补进未出现的命题变元 消去永假或重复出现的变元和极小项 将极小项按下标从小到大排列,真值表法：列出公式及各极小项的真值表，将每组赋值下 公式及极小项真值都为真的极小项进行析取。,主析取范式的求法：,1.公式法 2.真值表法,42,1.4 析取范式与合取范式,应用：1.求公式的成真、成假赋值 成真赋值为析取范式中所含极

12、小项的编码的二进制数 成假赋值为合取范式中所含极大项的编码的二进制数,由主析取范式可以直接求主合取范式： 1求出主析取范式中未包含的极小项 2求出与1中求出的极小项下标相同的极大项 3做2中极大项之合取,43,1.4 析取范式与合取范式,3.判断两公式是否等值 若A，B共含有n个命题变元，按n个命题变元求出A与B的 主析取范式A、B，若AB，则AB.,2.判断公式的类型 设A含有n个命题变元 A为重言式当且仅当A的主析取范式含全部2n个极小项； A为矛盾式当且仅当A的主析取范式不含任何极小项，此 时记为0； A为可满足式当且仅当A的主析取范式中至少含一个极小项。,44,例：要在A，B，C中挑选

13、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推理的形式结构

14、,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,例：若小王是理科生，则他的数学成绩一定很好。如果 小王

15、不是理科生，他一定是文科生。小王的数学成绩 不好。所以小王是文科生。,p：小王是理科生 q：小王是文科生 r：小王的数学成绩很好,1.6自然推理系统P,55,例：如果小张和小王去看电影，则小李也去看电影。小赵 不去看电影或小张去看电影。小王去看电影。所以， 当小赵去看电影时，小李也去。,p：小张去看电影 q：小王去看电影 r：小李去看电影 s：小赵去看电影,1.6自然推理系统P,56,2.归谬法 将结论的否定作为前提引入，能推出矛盾来，则推理正确,例：如果马会飞或羊不吃草，则母鸡就会是飞鸟。如果母 鸡是飞鸟，那么烤熟的鸭子还会跑。烤熟的鸭子不会 跑。所以羊吃草。,p：马会飞 q：羊吃草 r：母

16、鸡是飞鸟 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是有

17、理数 x是无理数 小王与小李同岁 x与y具有关系L,是有理数 是无理数 与同岁 与具有关系L,F： G： H： L：,2.1一阶逻辑命题符号化,61,3.量词：个体词之间的数量关系,（1）全称量词 “一切的”，“所有的”，“每一个”，“任意的”，“凡”，“都” 记作,4.符号化,确定个体域 确定个体词、量词和谓词 确定联结词,2.1一阶逻辑命题符号化,62,例：所有的人都是要死的。 有的人用左手写字。,注意： 全称量词的特性谓词必须作为蕴涵式的前件引入 存在量词的特性谓词必须作为合取式的合取项引入 同一命题，不同的个体域符号化的形式可能不同 未指明个体域即为全总个体域,2.1一阶逻辑命题符号化

18、,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,定理.重言式的代换实例都是永真式，矛盾式的代换 实例都

19、是矛盾式。,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一

20、阶逻辑前束范式,81,2.5一阶逻辑的推理理论,在一阶逻辑中，称永真的蕴涵式为推理定律。若一个推理 的形式结构正是某条推理定律，则该推理显然是正确的。,第一组 命题逻辑推理定律的代换实例,第二组 由基本等值式生成的推理定律,第三组 以下重要定律,82,第四组 消去量词和引入量词的推理规则,1、全称量词消去规则（UI）,2.5一阶逻辑的推理理论,83,UI规则成立的条件： （1）取代x的y应为任意不在A(x)中约束出现的个体变项； （2）用y取代A(x)中自由出现的x时，必须将所有的自由出现x都取代； （3）自由变元y也可替换为个体域中任意的个体常元c，c为任意不在A(x)中出现过的个体常项。,

21、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）中约束出现。,含

22、义：如果个体域的任意个体都具有性质A，则个体域中 的所有个体都具有性质A。,2.5一阶逻辑的推理理论,87,4、存在量词引入规则（EG）,EG规则成立的条件： （1）c是个体域中某个确定的个体； （2）代替c的x不在A（c）中出现过。,含义：如果个体域有某一个个体c具有性质A，则个体域中 必存在具有性质A的个体。,2.5一阶逻辑的推理理论,88,定义.一阶逻辑自然推理系统F的定义 1.字母表：同一阶语言的字母表 2.合式公式：同一阶语言合式公式的定义 3.推理规则 a.前提引入规则 b.结论引入规则 c.置换规则 d.假言推理规则 e.附加规则 f.化简规则 g.拒取式规则 h.假言三段论规则

23、 i.析取三段论规则 j.构造性二难规则 k.合取引入规则 l. UI，EI，UG，EG,2.5一阶逻辑的推理理论,89,例7：证明逻辑三段论 所有的人总是要死的。 苏格拉底是人。 所以苏格拉底是要死的。,2.5一阶逻辑的推理理论,90,2.5一阶逻辑的推理理论,例10：如果一个人怕困难就不会获得成功。每一个人或 者获得成功或者是失败的。有些人未曾失败过，所以有 些人不怕困难。（个体域是人的集合）判断这个推理是 否正确。,例9：根据前提集合：同事之间总是有工作矛盾的， 张平和李明没有工作矛盾，能得出什么结论？,91,第二部分 集合论,第三章 集合代数 第四章 二元关系 第五章 函数,92,第三

24、章 集合代数,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.有理数集合。

25、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.文氏图 用图形图像直观的描述集合之间的相互关系和有关运

26、算。,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：“好书”的全体，这不构成集合。,注意：一个集合是已知的，指的是对

27、任一元素，利用某种方法可以判断它是否是这个集合的元素，而不是把集合的每一个元素都给出来。,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的子集且

28、，则称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

29、元集，其含有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 (zA xz),若A A1,A2,，An，则A A1A2 An,定义6.设A 为非空集合， A 的所有元素的公共元素构成的集合称为A的广义交，记作A 。,A x|z (zA xz),若A A1,A2,，An，则A

30、A1 A2 An,例：Aa，b，c，a，b，e B=a C=a，c，d,110,集合运算的优先级： 高级：广义并、广义交、绝对补、求幂集；同级按从右向左的顺 序进行 低级：并、交、相对补和对称差；同级按从左向右的顺序进行,3.2集合的运算,111,3.2集合的运算,文氏图可以用来描述集合间的关系及其运算.在文氏图中,全集用矩形表示,子集用圆形表示,阴影部分表示运算结果的集合.,二、文氏图,112,3.2集合的运算,113,3.3集合恒等式,一、集合运算定律,以下列出集合性质中最主要的几条基本定律，对于全集E的任意子集A，B，C，有：,114,3.3集合恒等式,115,1、基本定义法,根据集合相

31、等的充要条件等式两边互为子集或由定义进行等价推理。,2、公式法,利用已证明过的恒等式去证明另外的恒等式。若表达式中出现形为 A-B的差集时，用功能完备律先将运算“-”转化为运算“ ”和“”。,二、集合恒等式证明,3.3集合恒等式,116,3.3集合恒等式,117,3.3集合恒等式,118,3.3集合恒等式,119,小 结,集合的概念 集合的特性 集合的表示方法:列举法、描述法、文氏图 集合的运算：并、交、补、差、求幂 集合间的关系：包含、相等 集合恒等式的证明：定义法、公式法、成员表法,120,第四章二元关系,4.1 有序对与笛卡儿积 4.2 二元关系 4.3 关系的运算 4.4 关系的性质

32、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的笛卡儿积，记作AB，符号化为 AB =|xAyB,性质1. A=， A=,123,例4:设A=a,b,B=0,1,C=u,v

33、则,4.1 有序对与笛卡儿积,124,4.1 有序对与笛卡儿积,125,4.1 有序对与笛卡儿积,126,性质5.若AC BD，则A B CD。,4.1 有序对与笛卡儿积,其逆命题不成立。 A=B=，成立； A ，B ，成立； A= 且 B ，不成立； A 且B= ，不成立。,127,定义4.由n个具有给定次序的个体a1，a2，an组成的序列，称为有序n元组，记作，其中ai称为第i个分量。 =当且仅当ai=bi（i=1，2，3，n）。 有序n元组仍然是序偶，即=，an。,4.1 有序对与笛卡儿积,128,定义5. 设A1，A2，An是任意的n个集合，所有有序n元组组成的集合，称为集合A1，A2

34、，An的笛卡儿积，并用 表示。其中 （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,MR,R=，,4.2 二元关系,三、关系的表示方法,133,4.2 二元关系,一个有限集合A

35、上的关系R还可以用一个称为R的关系图来表示。,134,4.2 二元关系,例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 关系的运算,关系是以序偶为元素的集合，

36、故可对关系进行集合的运算以产生新的关系。作为关系，绝对补运算是对全关系而言的。,139,4.3 关系的运算,2. A=1，2，3，4，5，R，S是A上的二元关系 R=， S=，,由此可知，合成关系不满足交换律，满足结合律。,140,4.3 关系的运算,141,定理8.关系矩阵的乘法满足结合律，即MR1（MR2MR3）=（MR1MR2）MR3,4.3 关系的运算,定理9.设R1是一个由A1到A2的关系，R2是一个由A2到A3的关系，Rn是一个由An到An+1的关系（Ai都是有限集）。它们的关系矩阵分别是MR1，MR2，MRn，则合成关系R1R2Rn的关系矩阵MR1R2Rn=MR1MR2MRn。,

37、142,定义5.设R为A上的关系，n为自然数，则R的n次幂定义为： R0=|xA=IA Rn+1=RnR,4.3 关系的运算,幂运算的求解：,若R是列举法表示，可进行多次右复合；,例：A=a，b，c，d，R=，,143,例：设A=a，b，c，d，R=，则R0， R2 ，R3，R4。,R0=，,R2=，,R3=，,R4=，,4.3 关系的运算,144,若R用关系矩阵M表示，则Rn的关系矩阵是Mn；,若R是用关系图G表示的，则可由G得Rn的关系图G。 G与G的顶点集合相同，考察G中每个顶点x，若在G中 从x出发经过n步长的路径到达顶点y，则在G中加一条 从x到y的边。当把所有顶点都考察完后，就得到

38、G。,4.3 关系的运算,145,4.3 关系的运算,定理10.幂运算满足指数定律：Rn Rm=Rn+m （Rn）m=Rmn,幂运算的性质：,定理11.设A为n元集，R是A上的关系，则存在s、tN，使得Rs=Rt。,146,4.4 关系的性质,定义1.设RAA， 若x(xAR)，则称R是自反的； 若x(xA R)，则称R是反自反的； 若x(xAR) y (yA R)， 则称R是非自反的。,定义2.设RAA， 若xy (x,yA RR)， 则称R是A上的对称关系； 若xy (x,yA R R x=y)， 则称R是A上的反对称关系； 否则，则称R是A上的非对称关系。,147,空关系既是对称的又是反

39、对称的.,非空集合上的空关系是反自反的、对称的、反对称的、可传递的。,空集合上的空关系则是自反的、反自反的、对称的、反对称的和可传递的。,4.4 关系的性质,148,非空集合上的全关系是自反的、对称的、和可传递的。,例2.S=a，b，c，S上的关系R1=，R2=，R3=，,例3.在集合S=a，b，c，d上的关系R：， ,，判断R的性质。,4.4 关系的性质,定理.设R是A上的二元关系，那么R是传递的当且仅当RRR。,149,4.4 关系的性质,根据定义可证明下面几个定理是成立的。,150,4.4 关系的性质,151,4.4 关系的性质,152,可能有某种关系，既是对称的，又是反对称的。,例4.

40、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扩充成一新关系Rc，使Rc具有一定的性质，且进行的扩充又是最小的。,4.5 关系的闭包,155,该定义表明，r（R）（s（R），t（R）是包含R的 最小自反（对称，传递）关系。,必要性：R=r（R），由定义1（1）知，r（R）是自反的，故R

41、是自反的。,4.5 关系的闭包,156,4.5 关系的闭包,157,4.5 关系的闭包,158,4.5 关系的闭包,159,4.5 关系的闭包,160,4.5 关系的闭包,161,4.5 关系的闭包,3.IA的自反、对称和传递闭包是什么？,4.空关系的自反、对称和传递闭包是什么？,例：A=a，b，c，d，R=，,162,设R、r(R)、s(R)、t(R)的关系矩阵分别为M、Mr、Ms、Mt，则 Mr=M+E Ms=M+M Mt=M+M2+M3+,设R、r(R)、s(R)、t(R)的关系矩阵分别为G、Gr、Gs、Gt，则 考察G中的每个顶点，若没有环就加上一个，得到Gr； 考察G中每条边，若有x

42、i到xj的单向边（ij），则加xj到xi 的反向边，得Gs； 考察G中每个顶点xi，找出从xi出发的所有2步、3步n步 长的路径（n为G中的顶点数）。设路径的终点为xj1、xj2、 、xjk，若没有从xi到xjl（l=1，2，k)的边，就加上这条 边。考察完所有的顶点后，得到Gt。,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,yAxy(mod3),167,4.6 等价关系与划分,168,4.6 等价关系与划分,169,一个集合的划分往往不是唯一的。,4.

43、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的下界，同时也

44、是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

45、|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=GFGGF. 即满足条件：domF=domG xdomF，都F(x)=G(x).,181,5.1 函数的定义与性质,182,5.1 函数的定义与性质,183,5.1 函数的定义与性质,184,5.1 函数的定义与性质,185,5.1 函数的定义与性质,定义7,186,单调函数可以定义于一般的偏序集上。 每个子集对应一个特征函数，不

46、同的子集则对应不同的特征函数。 故而可用特征函数来标记不同的子集。 给定集合A和A上的等价关系R，就可以确定一个自然映射，不同的 等价关系将确定不同的自然映射。,5.1 函数的定义与性质,187,算法的评价标准：时间复杂度、空间复杂度 估计复杂度的方法是：选择一个基本运算，对于给定规模为n的输入， 计算算法所做基本运算的次数，将这个次数表示为输入规模的函数。 最坏情况下的复杂度w（n） 平均情况下的复杂度A（n） 算法分析的主要工作就是估计复杂度函数的阶。阶越高，增长越快， 算法复杂度越高，效率越低。,5.1 函数的定义与性质,188,5.1 函数的定义与性质,189,5.2 函数的复合与反函

47、数,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|aAbB为A与B 的无序积，记作A&B。为方便，将a，b记为（a，b）,6.1 图,19

48、6,定义2.图G=是有序二元组，其中V(G)是有限非空 集；V中元素称为G的顶点或结点，V称为G的顶点集。E(G) 是V(G)中诸顶点之间边或弧的集合，E称为G的边集。,图G的边可以是无方向的，用vi，vj表示，称为无向边， 只由无向边构成的图G称为无向图。,图G的边可以是有方向的，用表示，称为有向边， 只由有向边构成的图D称为有向图。,6.1 图,197,如果图G中既有有向边，又有无向边，则称图G为混合图。,6.1 图,198,D=,ek=E,称vi为ek的起点， vj为ek的终点， 并称vi邻接到vj或vj邻接于vi。 若ek的终点是el的起点，则ek、el相邻。,6.1 图,定义4.在无

49、向图中，关联一对顶点的无向边若多于1条，则称这些边 为平行边，平行边的条数为重数。 在D中，关联一对顶点的有向边若多于1条，且始点、终点相同，则 称这些边为平行边。 含平行边的图为多重图，不含平行边、环的图为简单图。,199,6.1 图,200,6.1 图,201,6.1 图,必要条件：阶数相同 边数相同 度数相同的顶点数相同,202,6.1 图,203,6.1 图,204,6.1 图,205,6.2 通路与回路,206,定理1.在n阶图G中，若从顶点vi到vj（vivj）存在通路，则 从vi到vj存在长度小于或等于（n-1）的通路。,推论：在n阶图G中，若从顶点vi到vj（vivj）存在通路

50、，则 从vi到vj一定存在长度小于或等于（n-1）的初级通路。,定理2.在n阶图G中，若存在从顶点vi到自身的回路，则一定 存在长度小于或等于n的回路。,推论：在n阶图G中，若存在从顶点vi到自身的简单回路，则 一定存在长度小于或等于n的初级回路。,6.2 通路与回路,207,无向图顶点间的连通关系是V上的一个等价关系，他的所 有等价类构成V的一个划分。任意两个顶点vi,vj属于同一个 等价类当且仅当他们有路连接。,6.3 图的连通性,208,6.3 图的连通性,209,6.3 图的连通性,210,当v是G的点割集，则称v是G的割点。,若v是连通图G的一个割点，那么G-v就是不连通或平凡图。,

51、6.3 图的连通性,211,6.3 图的连通性,212,6.3 图的连通性,213,6.3 图的连通性,214,定理3.一个有向图D是强连通图的充要条件是D中存在至少 经过每个顶点一次的回路。,6.3 图的连通性,定理4.设D是n阶有向图，D是单向连通图当且仅当D中存在 经过每个顶点至少一次的通路。,215,6.3 图的连通性,极大路径法：,设G=为n阶无向图，E。设l为G中一条路 径。若此路径的始点或终点与通路外的顶点相邻，就将它 们扩充到通路中来，继续这一过程，直到最后得到的通路 的两个端点不与通路外的顶点相邻为止。设最后得到的路 径为l+k，称其为极大路径。称使用此种方法证明问题 的方法

52、为极大路径法。,216,邻接矩阵A的阶就是G的顶点数n。,6.4 图的矩阵表示,图的表示方法： （1）用边的集合和边的集合表示，如G= （2）用图形表示，顶点用小圆圈表示，边用线段或弧表示 （3）用矩阵表示,217,邻接矩阵依赖于V中个元素的给定次序，对于V中各元素 的不同给定次序，可以得到同一个图G的不同邻接矩阵。 这些矩阵可以通过交换另一个矩阵的某些行或对应的列而 得到。如果两个图有这样的邻接矩阵，则这两个图是同构 的。,6.4 图的矩阵表示,若主对角线某元素不为0，则表示该对应顶点上有自环。 零矩阵对应的图为零图。,218,6.4 图的矩阵表示,219,6.4 图的矩阵表示,220,6.

53、4 图的矩阵表示,221,6.4 图的矩阵表示,222,6.4 图的矩阵表示,223,6.4 图的矩阵表示,224,6.5 图的运算,225,6.5 图的运算,226,第七章 欧拉图与哈密顿图,7.1 欧拉图 7.2 哈密顿图 7.3二部图 7.4平面图 7.5树,227,定义1.通过图G的每条边一次且仅一次行遍图中所有顶点的 通路称为欧拉通路。通过图G的每条边一次且仅一次行遍图 中所有顶点的回路称为欧拉回路。具有欧拉回路的图称为 欧拉图。具有欧拉通路而无欧拉回路的图为半欧拉图。,定理1.无向图G为欧拉图当且仅当G是连通图，且G中所有 顶点的度数都是偶数。,定理2.如果G是欧拉图，那么G可分成

54、若干个边不重的回路。,7.1 欧拉图,228,定理3.具有一条连接顶点vi和vj的欧拉通路的充要条件是 Vi和vj是G中仅有的具有奇数度的顶点。,定理4.设连通图G=有k个度为奇数的顶点，则E(G) 可划分为k/2条简单通路。,定理5.有向连通图D为欧拉图的充要条件是每个顶点的入 度等于出度 。,7.1 欧拉图,229,定理6.有向连通图D存在一条欧拉通路的充要条件是恰有 两个奇度数顶点，其中的一个入度比出度大1，另一个的 出度比入度大1，而其余顶点的入度等于出度。,7.1 欧拉图,230,7.1 欧拉图,231,定义1.通过图G的每个顶点一次且仅一次的回路称为 哈密顿回路. 哈密顿通路是通过

55、图G的每个顶点一次 且仅一次的通路.具有哈密顿回路的图称为哈密顿图. 具有哈密顿通路而不具有哈密顿回路的图称为哈密顿 图. 平凡图是哈密顿图。,性质:,1.连通,度大于等于2 2.哈密顿通路是度为n-1的基本通路,其回路长为n,7.2 哈密顿图,232,7.2 哈密顿图,233,7.2 哈密顿图,例：在某次国际会议的预备会中，共有8人参加，他们来 自不同的国家。已知他们中任何两个无共同语言的人中的 每一个，与其余有共同语言的人数之和大于或等于8。问 能否将这8人排在圆桌旁，使任何人都能与两边的人交谈。,定理4.若D为n（n2）阶竞赛图，则D中具有哈密顿通路。,234,带权图与货郎担问题,货郎担

56、问题：,设有n个城市，城市之间均有道路，道路的长度均大于或 等于0。一个旅行商从某个城市出发，要经过每个城市一 次且仅一次，最后回到出发的城市。问他如何走，才能使 路线最短？,235,7.5 树,7.5.1 无向树及其性质 7.5.2 生成树 7.5.3 根树及其应用,236,定义1.连通无回路的无向图称为无向树，简称树，用T 表示 。若无向图F至少有两个连通分图都是树，称F为 森林。仅有一个顶点的树称为平凡树。悬挂点称为树叶。,定理1.设G=是n阶m条边的无向图，下列各命题等价； （1）G是树； （2）G的任意两个顶点之间有唯一路径；,7.5.1 无向树及其性质,237,（3）G中无回路且m

57、=n-1； （4）G是连通且m=n-1； （5）G是连通的，且G中任何边均是割边； （6）G中无回路，但若在G的任意两个不同的顶点间加 一条边，则所得的图中恰有唯一的一个含有新边的圈。,定理2.设T是n阶非平凡的无向树，则T中至少有两片树叶。,7.5.1 无向树及其性质,238,定义1.设T是无向图G的子图并且为树，则称T为G的树。 若T是G的树且为生成子图，则称T是G的生成树，T中的 边称为树枝。图G中不在T中的边称作相应生成树T的弦。 并称导出子图GE(G)-E(T)为T的余树，记作 。,定理1.无向图G具有生成树当且仅当G是连通图。,推论1： 设G为n阶m条边的无向连通图，则mn-1。,

58、7.5.2 生成树,239,7.5.2 生成树,240,7.5.2 生成树,241,定义4.设G=是无向连通带权图，T是G的 一棵生成树。T中各条边带权之和称为T的权，记作 W(T)。若生成树T0在所有生成树中有最小的权，则称 T0是G的最小生成树。,7.5.2 生成树,242,7.5.2 生成树,243,7.5.3 根树及其应用,在根树中，由于有向边的方向一致，故在画的时候可以省去边的方向。,244,设T为根树，若将T中层数相同的顶点都标定次序，可以将 根树分成以下各类：, 若T的每个分支点至多有r个儿子，则称T为r叉树； 又若r叉树是有序的，则称其为r叉有序树。, 若T的每个分支点恰好有r

59、个儿子，则称T为r叉正则树； 又若T是有序的，则称其为r叉正则有序树。, 若T为r叉正则树，且每个树叶的层数均为树高，则称T为r叉 完全正则树；又若T是有序的，则称其为r叉完全正则有序树。,7.5.3 根树及其应用,245,2叉正则有序树的每个分支点的两个儿子导出的根子树分别 称为左子树和右子树。,在所有的r叉树中，2叉树最重要。,7.5.3 根树及其应用,246,在通信中，常用二进制编码表示符号。如：A，B，C，D就可 用00，01，10，11分别来表示，这叫做等长码表示方法。适用 于出现的频率基本相同的情况，当出现的频率相差较大时，就需 要非等长的编码。,7.5.3 根树及其应用,247,

60、可用2叉树产生二元前缀码。,设T是具有t片树叶的2叉树，则T的每个分支点有12个儿子。设 V为T的分支点，若v有两个儿子，在由v引出的两条边上，左边标 上0，右边标上1。若v只有一个儿子，由它引出的边上可以标0也 可以标1。,7.5.3 根树及其应用,248,设v是T的任意一片树叶，从树根到v的通路上各边的标号（0或1） 按通路上边的顺序放在v处，则t片树叶处t个符号串组成的集合为 一个二元前缀码。,定理1.由一棵给定的2叉正则树，可以产生惟一的一个二元前缀码。,由产生的任一个前缀码都可以传输符号。但这些符号出现频率不同 时，就要用各符号出现的频率为权，利用Huffman算法求最优2叉树， 由