离散数学教程ppt.ppt
《离散数学教程ppt.ppt》由会员分享,可在线阅读,更多相关《离散数学教程ppt.ppt(292页珍藏版)》请在课桌文档上搜索。
1、离散数学,数学与信息科学学院,第一部分 数理逻辑第二部分 集合论第三部分 图论第四部分 抽象代数,离散数学,第一部分 数理逻辑,数理逻辑是用数学方法研究推理中前提和结论之间的形式关系的学科。,推理是由一个或几个判断推出一个新判断的思维形式。,数学方法是指建立一套表意符号体系,对具体事物进行抽象的形式研究的方法。,第一章 命题逻辑第二章 一阶谓词逻辑,第一部分 数理逻辑,1.1 命题和命题联结词1.2 命题公式及其赋值1.3 等值演算与联结词完备集1.4 析取范式与合取范式1.5 推理的形式结构1.6 自然推理系统P,第一章 命题逻辑,1.命题:能判断真假的陈述句。,包含两层意思:,(1)必须是
2、陈述句。,(2)能够确定(分辨)其真值。,1.1 命题和命题联结词,1.1 命题和命题联结词,2.命题的真值:判断结果,注意:此处不纠缠具体命题的真假问题,只是将其作为数学概念来处理。,真值:真用T或1表示,假用F或0表示。,3.命题和真值的符号化,1.1 命题和命题联结词,1.1 命题和命题联结词,原子命题:不能被分解为更简单的陈述句复合命题:原子命题通过联结词联结而成,例:2是有理数是不对的;2是偶素数;2或4是素数;如果2是素数,则3也是素数;2是素数当且仅当3也是素数。,p:2是有理数,q:2是偶数,r:2是素数,s:3是素数,t:4是素数。,1.1 命题和命题联结词,4、命题联结词,
3、1.1 命题和命题联结词,王化不但成绩好而且品德好。,pq:,1.1 命题和命题联结词,1.1 命题和命题联结词,开关坏了或灯泡坏了。,pq:,例:1.张晓婧爱唱歌或爱听音乐。2.张晓婧是内蒙人或是陕西人。3.张晓婧只能挑选202或203房间。,1.1 命题和命题联结词,注意:当排斥或两边的情况实际根本不可能同时发生的时候,排斥或也可抽象为。但为了方便起见一般不这样抽象。,有位父亲对儿子说:“如果我去书店,就一定给你买电脑报“。问:在什么情况下,父亲算失信呢?,1.1 命题和命题联结词,注意:“只要p,就q,因为p,所以q”,“p仅当q”,只有q,才p“,”除非q才p“,”除非q,否则非p“都
4、可抽象为pq。p,q可以没有任何内在联系。,例:1.如果336,那么雪是白的。2.除非我能工作完成了,我才去看电影。3.只要天下雨,我就回家。4.我回家仅当天下雨。,pq的逻辑关系为q是p的必要条件或p是q的充分条件。,1.1 命题和命题联结词,1.1 命题和命题联结词,p q的逻辑关系为p与q互为充要条件,例:1.3是有理数当且仅当加拿大位于亚洲。2.两圆的面积相等,则他们的半径相等,反之亦然。,1.1 命题和命题联结词,例:今天第一节课上离散数学或数据结构。,例:p:北京比天津人口多 q:224 r:乌鸦是黑色的,1.1 命题和命题联结词,5、语句形式化,1.1 命题和命题联结词,例:2是
5、有理数是不对的;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。,1.1 命题和命题联结词,命题常元:表示具体确定内容的命题。命题变元:表示不确定具体内容的命题。,1.2 命题公式及其赋值,1.2 命题公式及其赋值,同时约定:(1)最外层的括号可以省去。(2)不影响运算次序的括号也可以省去。,1.2 命题公式及其赋值,1.2 命题公式及其赋值,1.2 命题公式及其赋值,1.2 命题公式及其赋值,1.2 命题公式及其赋值,1.3 命题公
6、式的等值式,基本等值式(A,B,C为任意命题公式),1.3 命题公式的等值式,1.3 命题公式的等值式,因A,B,C可以代入任意的命题公式,故以上等值式称为等值式模式。,由已知的等值式推演出另外一些等值式的过程为等值演算。,1.3 命题公式的等值式,等值演算的应用:1.验证等值式 2.判定公式的类型 3.解决工作生活中的判断问题,1.3 命题公式的等值式,甲、已、丙3人根据口音对王教授是哪人进行了判断:甲说:王教授不是苏州人,是上海人 已说:王教授不是上海人,是苏州人 丙说:王教授既不是上海人,也不是杭州人结果3人中有一人全对,一人对一半,一人全错。问王教授是哪人?,联结词的完备集,n个命题变
7、元可以形成22n个不同的真值函数,对于每个真值函数,都可以找到许多与之等值的命题公式,而每个命题公式对应唯一的与之等值的真值函数。,定义.设S是一个联结词集合,如果任何n(n1)元真值 函数都可以由仅含S中的联结词构成的公式表示,则 称S是联结词完备集。,联结词的完备集,1.4 析取范式与合取范式,定义:命题变元及其否定统称为文字。仅由有限个文字构成的析取式称为简单(质)析取式。仅由有限个文字构成的合取式称为简单(质)合取式。,注意:单个文字既是简单析取式又是简单合取式。,讨论:设A为含n个文字的简单析取式 若A中同时含pi和pi,则?,若A为永真式,则?,若A为永真式,则A中必同时含有pi和
8、pi,反之亦然。,同理有,若A为简单合取式,A为永假式的充要条件是A中同时含有pi和pi。,定理1.一个简单析取式是重言式当且仅当它同时含有某 个命题变元及其他的否定。一个简单合取式是矛盾式当且仅当它同时含有某 个命题变元及其他的否定。,1.4 析取范式与合取范式,定义:由有限个简单合取式构成的析取式称为析取范式。由有限个简单析取式构成的合取式称为合取范式。析取范式与合取范式称为范式。,注意:单个文字、简单析取式、简单合取式都既是析取范 式又是合取范式。,1.4 析取范式与合取范式,定理2.一个析取范式是矛盾式当且仅当它的每个简单合 取式为矛盾式。一个合取范式是重言式当且仅当它的每个简单析 取
9、式为重言式。,定理3.任一命题公式都存在与之等值的析取范式和合取范式。,范式的求法:消去公式中的蕴涵、等价和异或联结词 使用双重否定律和德摩根律,将公式中出现 的否定 词移到命题变元之前。利用分配律、结合律将公式化为合(析)取 范式。,范式形式不唯一。,1.4 析取范式与合取范式,定义:在含有n个命题变元的简单合(析)取式中,若每个 命题变元和 它的否定式不同时出现,而二者之一必 出现且仅出现一次,且第 i个命题变元或它的否定是 出现在从左算起的第i位上(字典序),称这样的简 单合(析)取式为极小(大)项。,性质:n个变元可以形成2n个极小(大)项;每个极小(大)项有且仅有一个成真(假)赋值;
10、每组赋值下仅有一个极小(大)项为真(假);所有极小(大)项的析(合)取为真(假);,1.4 析取范式与合取范式,将极小项的成真赋值对应的二进制数转化为十进制数为i,将对应的极小项记为mi。将极大项的成假赋值对应的二进制数转化为十进制数为i,将对应的极大项记为Mi。,定义:设由n个命题变元构成的析(合)取范式中所有的简 单合(析)取式都是极小(大)项,则称该析取范 式为主析(合)取范式。,1.4 析取范式与合取范式,定理.任何命题公式都存在与之等值的主析取范式和主合取范 式,并且是唯一的。,1.4 析取范式与合取范式,公式法:求析取范式 用同一律补进未出现的命题变元 消去永假或重复出现的变元和极
11、小项 将极小项按下标从小到大排列,真值表法:列出公式及各极小项的真值表,将每组赋值下 公式及极小项真值都为真的极小项进行析取。,主析取范式的求法:,1.公式法2.真值表法,1.4 析取范式与合取范式,应用:1.求公式的成真、成假赋值 成真赋值为析取范式中所含极小项的编码的二进制数 成假赋值为合取范式中所含极大项的编码的二进制数,由主析取范式可以直接求主合取范式:1求出主析取范式中未包含的极小项 2求出与1中求出的极小项下标相同的极大项 3做2中极大项之合取,1.4 析取范式与合取范式,3.判断两公式是否等值 若A,B共含有n个命题变元,按n个命题变元求出A与B的主析取范式A、B,若AB,则AB
12、.,2.判断公式的类型 设A含有n个命题变元A为重言式当且仅当A的主析取范式含全部2n个极小项;A为矛盾式当且仅当A的主析取范式不含任何极小项,此 时记为0;A为可满足式当且仅当A的主析取范式中至少含一个极小项。,例:要在A,B,C中挑选2名出国进修,选派时满足下列条件:若A去,则C同去 若B去,则C不能去 若C不去,则A或B可以去问有几种选派方案,分别是什么?,4.解决实际问题,1.4 析取范式与合取范式,1.5推理的形式结构,注意:推理正确实际是排除前提真结论假的情况推理是否正确与前提的排列顺序无关推理正确并不能保证B一定为真,1.5推理的形式结构,推理的形式结构,1.5推理的形式结构,例
13、:若下午温度超过30度,则王晓燕必去游泳。若她去游 泳,她就不会去看电影。所以若王晓燕没去看电影,下午温度必超过了30度。,p:温度超过30度q:王晓燕去游泳r:王晓燕去看电影,1.5推理的形式结构,1.5推理的形式结构,注意:以上都是蕴含式模式若某推理的形式结构与某定律一致,则推理正确成立的等值式可产生两条定律推理定律可产生相应的推理规则,1.5推理的形式结构,1.6自然推理系统P,定义.一个形式系统I由以下4部分组成:非空的字母表,记作A(I)A(I)中符号构成的合式公式集,记作E(I)E(I)中特殊的公式组成的公理集,记作Ax(I)推理规则集,记作R(I),任给的前提,应用规则得到结论(
14、可能真),任给的公理,应用规则得到结论(永真),1.6自然推理系统P,1.6自然推理系统P,例:若小王是理科生,则他的数学成绩一定很好。如果 小王不是理科生,他一定是文科生。小王的数学成绩 不好。所以小王是文科生。,p:小王是理科生q:小王是文科生r:小王的数学成绩很好,1.6自然推理系统P,例:如果小张和小王去看电影,则小李也去看电影。小赵 不去看电影或小张去看电影。小王去看电影。所以,当小赵去看电影时,小李也去。,p:小张去看电影q:小王去看电影r:小李去看电影s:小赵去看电影,1.6自然推理系统P,2.归谬法将结论的否定作为前提引入,能推出矛盾来,则推理正确,例:如果马会飞或羊不吃草,则
15、母鸡就会是飞鸟。如果母 鸡是飞鸟,那么烤熟的鸭子还会跑。烤熟的鸭子不会 跑。所以羊吃草。,p:马会飞q:羊吃草r:母鸡是飞鸟s:烤熟的鸭子会跑,1.6自然推理系统P,所有的人总是要死的。苏格拉底是人。所以苏格拉底是要死的。,p:q:r:,第二章 谓词逻辑,第二章 谓词逻辑,2.1一阶逻辑命题符号化2.2一阶逻辑公式及解释2.3一阶逻辑等值式与置换规则2.4一阶逻辑前束范式2.5一阶逻辑的推理理论,2.1一阶逻辑命题符号化,1.个体词,所研究对象中可以独立存在的具体的或抽象的客体(事物),表示具体的或特定的客体,表示抽象或泛指的客体,个体变项的取值范围称为个体域,用D表示,宇宙间一切事物组成的称
16、为全总个体域,2.谓词,用来刻划个体词性质及个体词之间相互关系的词,2是有理数x是无理数小王与小李同岁x与y具有关系L,是有理数是无理数与同岁与具有关系L,F:G:H:L:,2.1一阶逻辑命题符号化,3.量词:个体词之间的数量关系,(1)全称量词“一切的”,“所有的”,“每一个”,“任意的”,“凡”,“都”记作,4.符号化,确定个体域确定个体词、量词和谓词确定联结词,2.1一阶逻辑命题符号化,例:所有的人都是要死的。有的人用左手写字。,注意:全称量词的特性谓词必须作为蕴涵式的前件引入存在量词的特性谓词必须作为合取式的合取项引入同一命题,不同的个体域符号化的形式可能不同未指明个体域即为全总个体域
17、,2.1一阶逻辑命题符号化,例:在美国留学的学生未必都是亚洲人。有的兔子比所有的乌龟跑的快。对任意的整数x,都存在整数y使得xy10。,注意:多个量词出现时,顺序一般不能随便换有些命题符号化形式不唯一,2.1一阶逻辑命题符号化,2.2一阶逻辑公式及解释,2.2一阶逻辑公式及解释,合式公式也称谓词公式,简称公式,2.2一阶逻辑公式及解释,2.2一阶逻辑公式及解释,2.2一阶逻辑公式及解释,2.2一阶逻辑公式及解释,定理.闭式在任何解释下都变成命题。,2.2一阶逻辑公式及解释,2.2一阶逻辑公式及解释,定理.重言式的代换实例都是永真式,矛盾式的代换 实例都是矛盾式。,2.2一阶逻辑公式及解释,2.
18、3一阶逻辑等值式与置换规则,第一组 命题逻辑中等值式模式的代换实例都是一阶逻 辑的等值式模式,第二组 一阶逻辑中特殊的等值式,2.3一阶逻辑等值式与置换规则,D=N,F(x):x是奇数 G(x):x是偶数,2.3一阶逻辑等值式与置换规则,2.3一阶逻辑等值式与置换规则,2.3一阶逻辑等值式与置换规则,2.4一阶逻辑前束范式,为了方便使用谓词公式进行定理证明和逻辑推理,需要把谓词公式变换为便于使用的规范形式,就是范式。,定理1:任一谓词公式都可以化成为与之等值的前束范式。,2.4一阶逻辑前束范式,2.4一阶逻辑前束范式,2.5一阶逻辑的推理理论,在一阶逻辑中,称永真的蕴涵式为推理定律。若一个推理
19、的形式结构正是某条推理定律,则该推理显然是正确的。,第一组 命题逻辑推理定律的代换实例,第二组 由基本等值式生成的推理定律,第三组 以下重要定律,第四组 消去量词和引入量词的推理规则,1、全称量词消去规则(UI),2.5一阶逻辑的推理理论,UI规则成立的条件:(1)取代x的y应为任意不在A(x)中约束出现的个体变项;(2)用y取代A(x)中自由出现的x时,必须将所有的自由出现x都取代;(3)自由变元y也可替换为个体域中任意的个体常元c,c为任意不在A(x)中出现过的个体常项。,2.5一阶逻辑的推理理论,含义:如果个体域的所有个体都具有性质A,则个体域中的任一个个体都具有性质A。,2、存在量词消
20、去规则(EI),含义:如果个体域存在有性质A的个体,则个体域中必有某一个个体具有性质A。,2.5一阶逻辑的推理理论,ES规则成立的条件:(1)c是个体域中使A为真的特定的个体常项;(2)c不曾在A(x)或前面的推导公式中出现过;(3)A(x)中除x外还有其他自由变元时,不能用此规则,2.5一阶逻辑的推理理论,3、全称量词引入规则(UG),UG规则成立的条件:(1)y在A(y)中自由出现,且y取任何值时A均为真;(2)x不在A(y)中约束出现。,含义:如果个体域的任意个体都具有性质A,则个体域中的所有个体都具有性质A。,2.5一阶逻辑的推理理论,4、存在量词引入规则(EG),EG规则成立的条件:
21、(1)c是个体域中某个确定的个体;(2)代替c的x不在A(c)中出现过。,含义:如果个体域有某一个个体c具有性质A,则个体域中必存在具有性质A的个体。,2.5一阶逻辑的推理理论,定义.一阶逻辑自然推理系统F的定义 1.字母表:同一阶语言的字母表 2.合式公式:同一阶语言合式公式的定义 3.推理规则 a.前提引入规则 b.结论引入规则 c.置换规则 d.假言推理规则 e.附加规则 f.化简规则 g.拒取式规则 h.假言三段论规则 i.析取三段论规则 j.构造性二难规则 k.合取引入规则 l.UI,EI,UG,EG,2.5一阶逻辑的推理理论,例7:证明逻辑三段论 所有的人总是要死的。苏格拉底是人。
22、所以苏格拉底是要死的。,2.5一阶逻辑的推理理论,2.5一阶逻辑的推理理论,例10:如果一个人怕困难就不会获得成功。每一个人或者获得成功或者是失败的。有些人未曾失败过,所以有些人不怕困难。(个体域是人的集合)判断这个推理是否正确。,例9:根据前提集合:同事之间总是有工作矛盾的,张平和李明没有工作矛盾,能得出什么结论?,第二部分 集合论,第三章 集合代数第四章 二元关系第五章 函数,第三章 集合代数,3.1 集合的基本概念3.2 集合的运算3.3 集合恒等式,一、集合的概念集合(set)的含义:一个集合是作为整体识别的、确定的、互相区别的一些事物的聚集(全体或总体等)。构成一个集合的每个事物,成
23、为这个集合中的元素或成员。集合一般用A、B、C表示,集合中的元素用a、b、c表示。但这不是绝对的,因为一个集合可以作为另一个集合的元素。如果x是集合s的一个元素,记作;y不是集合s的元素,记作,3.1集合的基本概念,例1:1.偶素数集合。2.二进制的基数集合。3.英文字母的集合。4.全体实数的集合。5.自然数集合。6.整数集合。7.有理数集合。8.素数集合。,3.1集合的基本概念,3.1集合的基本概念,集合的表示方法:1.列举法(枚举法、外延法)把集合的所有元素(元素较少时)写在一个花括号内;列出足够多的元素(元素很多或无穷时)以反映集合中元素的特征。如例1中的1、2、3、5可分别表示为:20
24、,1a,b,cz,A,B,CZ1,2,3,3.1集合的基本概念,2.描述法(概括法)将集合中的元素的性质用一个谓词公式来描述,S=X|P(X),意义为:集合S由且仅由满足为此公式P(X)的对象组成,即,当且仅当p(a)为真。如例1中的4、6、7可表示为:,3.文氏图用图形图像直观的描述集合之间的相互关系和有关运算。,3.1集合的基本概念,几个常见集合的表示符号:N:自然数集合,N=0,1,2,3;I:整数集合;P:素数或质数集合;Q:有理数集合;R:实数集合;C:复数集合;,3.1集合的基本概念,集合的特性:A.互异性:一个集合的个元素是可以区分开的,即每一 元素只出现一次。B.无序性:集合中
25、元素排列顺序无关紧要,即集合表示 形式的不唯一性。例2:a,b,c=b,c,a=c,a,b=a,c,b=b,a,c=c,b,a,3.1集合的基本概念,C.确定性:任一事物是否属于某一集合,回答是确定的。,例3:“好书”的全体,这不构成集合。,注意:一个集合是已知的,指的是对任一元素,利用某种方法可以判断它是否是这个集合的元素,而不是把集合的每一个元素都给出来。,3.1集合的基本概念,集合的元素可以是任何具体或抽象的事物,包括别的集合,但不能是本集合自身。,例4:在一个住着一些人家的偏僻孤岛上,岛上只有一个理发师a,a给且只给岛上所有不能自己理发的人理发。问谁给a理发?,定义1.设A和B是两个集
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 教程 ppt
链接地址:https://www.desk33.com/p-233572.html