离散数学第五版第一章(耿素云、屈婉玲、张立昂编著)省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,An Introduction to Database Systenm,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。谢谢,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,An Introduction to Database Systenm,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。谢谢,离散数学,第1页,教材及参考书,(1),教材,耿素云，屈婉玲，张立昂：离散数学,(,第三版,),，清华大学出版社,第2页,教材及参考书,(2),参考书,耿素云：离散数学,(,修订版,),，,高等教育出版社,屈婉玲，耿素云，张立昂：离散数学题解（修订版），清华大学出版社,李盘林，李丽双，李洋，王春立：离散数学，高等教育出版社,第3页,学习目标,初步掌握当代数学观点和方法；,初步掌握处理离散结构和方法，提升计算机系统设计和程序设计逻辑数字能力；,初步掌握计算机在进行数处理时方法和计算；,培养学习抽象思维和缜密思索能力；,第4页,首都师范大学教育技术系,离散数学,第一章 命题逻辑,第5页,第一章,命题逻辑,一、命题与联结词,二、命题公式及其赋值,三、等值式,四、析取范式与合取范式,五、联结词完备集,六、推理形式结构七、自然推理系统,P,第6页,命题与联结词,一、命题,定义：能判断真假陈说句，被称为命题。,说明：,命题真值：作为命题所表示判断只有两个结果：正确和错误，此结果称为命题真值。,命题是正确，称此命题真值为,真,；命题是错误，称此命题真值为,假,。,真值为真命题称为,真命题,；真值为假命题称为,假命题,。,任何命题真值都是唯一。,其它类型句子，如疑问句、祈使句、感叹句均没有真假意义，因为均不是命,题。,在数理逻辑中，命题真值真和假，有时分别用,1,和,0,来表示，也有时分别用,T,和,F,来表示。,第7页,命题与联结词,怎样判断命题：,首先判断其是否为,陈说句,其次判断其是否有,唯一真值,例,1判断以下句子是否为命题，真值怎样？,（,1,）,10,是整数。,（,2,）,北京是我们祖国首都。,真命题,真命题,（,3,）,雪是黑。,（,4,）,x,大于,y,。,（,5,）,向右看齐！,（,6,）,你吃饭了吗？,疑问句 非命题,祈使句 非命题,真值不唯一 非命题,假命题,第8页,命题与联结词,例,1,：判断以下句子是否为命题，真值怎样？,（,7,）,本命题是假。,（,8,）,我正在说谎。,悖论 非命题,悖论 非命题,（,9,）,年元旦是晴天。,是命题 真假未定,第9页,命题与联结词,三、原子命题（简单命题）,定义：不能被分解为更简单命题命题，称为原子命题。,四、复合命题,定义：由若干个原子命题用命题联结词联结而成命题，称为复合命题。,二、命题符号化,本书中用小写字母,p,，,q,，,r,来表示命题。,例,2:,p,:,10,是整数。,q,：,北京是我们祖国首都。,r,:,雪是黑。,第10页,命题与联结词,例,3,：判断以下命题是否为复合命题。,（,1,）,5,能被,2,整除。,（,2,）,2,是素数当且仅当三角形有三条边。,原子命题,复合命题,（,3,）,4,是,2,倍数或是,3,倍数。,复合命题,（,4,）,李明与王华是同学。,原子命题,（,5,）,蓝色和黄色能够调配成绿色。,原子命题,（,6,）,2,不是合数。,复合命题,第11页,1.1,命题与联结词,五、命题联结词,否定,符号：,p,p,0,1,1,0,真值表：,定义,1.1,：设,p,为命题，复合命题,“,非,p,”,（或,“,p,否定,”,）称为,p,否定式，记作,p,，符号,称为否定联结词。要求,p,为真当且仅当,p,为假。,说明：,是一元联结词,念作,“,等值,”,，表示该符号两边两个命题在任何情况下真值相同。,性质：,p,p,第12页,命题与联结词,合取,符号：,定义,1.2,：设,p,，,q,为二命题，复合命题,“,p,而且,q,”,（或,“,p,与,q,”,）称为,p,与,q,合取式，记作,p,q,，符号,称为合取联结词。并要求,p,q,为真当且仅当,p,与,q,同时为真时为真。,真值表：,P Q,P,Q,0 0,0,0 1,0,1 0,0,1 1,1,注意,：,自然语言中,“,既,，又,”,，,“,不但,，而且,”,，,“,即使,，不过,”,，,“,一面,，一面,”,等联结次可符号化为,。,不要见到,“,与,”,或,“,和,”,就使用联结词,。,第13页,命题与联结词,例,4,：将以下命题符号化。,（,1,）,吴颖既用功又聪明。,（,2,）,吴颖不但用功而且聪明。,（,3,）,吴颖即使聪明，但不用功。,（,4,）,张辉与王丽都是三好学生。,（,5,）,张辉与王丽是同学。,p,:,吴颖用功。,q,:,吴颖聪明。,r,:,张辉是三好学生。,s,:,王丽是三好学生。,t,:,张辉与王丽是同学。,p,q,p,q,p,q,p,q,s,第14页,命题与联结词,真值表：,析取,符号：,定义,1.3,：设,p,，,q,为二命题，复合命题,“,p,或,q,”,称为,p,与,q,析取式，记作,p,q,，符号,称为析取联结词。并要求,p,q,为假当且仅当,p,与,q,同事为假。,P Q,P,Q,0 0,0,0 1,1,1 0,1,1 1,1,注意,：,自然语言中,“,或,”,含有二义性，用它做联结命题有时含有相容性，有时含有排斥性，对应联结词分别称为,相容或,和,排斥或,第15页,命题与联结词,例,5,：将以下命题符号化。,（,1,）,张明正在睡觉或游泳。,（,2,）,李强是位排球队员或是足球队员。,（,3,）,他昨晚做了二十或三十道题。,（,4,）,张静只能挑选,202,或,203,房间。,或表示约数，不能用析取,p,:,张明正在睡觉。,q,:,张明正在游泳,p,q,排斥或,p,:,李强是位排球队员。,q,:,李强是位足球队员,p,q,相容或,p,:,张静挑选,202,房间。,q,:,张静挑选,203,房间（,p,q,）,（,p,q,）,p,q,不正确,第16页,命题与联结词,蕴含,符号：,定义,1.4,：设,p,，,q,为二命题，复合命题,“,假如,p,，则,q,”,称为,p,与,q,蕴含式，记作,p,q,，并称,p,是蕴含式前件，,q,为蕴含式后件，符号,称为蕴含联结词并要求,p,q,为假当且仅当,p,为真,q,为假。,真值表：,P Q,P,Q,0 0,1,0 1,1,1 0,0,1 1,1,p,q,逻辑关系为,q,是,p,必要条件,p,是,q,充分条件。,第17页,命题与联结词,注意,：,蕴含,符号：,在自然语言和数学中，有很多方式来描述蕴含，比如：,“,只要,p,，就,q,”,，,”,因为,p,，所以,q,”,，,”,p,仅当,q,”,，,”,只有,q,才,p,”,，,”,除非,q,才,p,”,，,”,除非,q,，不然非,p,”,，,q,是,p,必要条件，因而所用联结词应符号化为,，各种描述方式都应该符号化为,p,q,。,在自然语言中，,“,假如,p,则,q,”,中前件,p,与后件,q,往往含有某种内在联络，而在数理逻辑中，,p,与,q,能够无任何内在联络。,在数学或其它自然科学中，,“,假如,p,，则,q,”,往往表示是前件,p,为真，后件,q,也为真推理。但在数理逻辑中，作为一个要求，当,p,为假时，不论,q,是真还是假，,p,q,均为真，也就是说，只有,p,为真,q,为假这一个情况，使得复合命题,p,q,为假。,第18页,命题与联结词,例,6,：将以下命题符号化。,（,1,）,只要不下雨，我就骑自行车上班。,（,2,）,只有不下雨，我才骑自行车上班。,（,3,）,若,2+2=4,，则太阳从东方升起。,p,:,天下雨。,q,:,我骑自行车上班。,s,:2+2=4,。,t,:,太阳从东方升起,r,:,太阳从西方升起。,（,4,）,若,2+2 4,，则太阳从东方升起。,（,5,）,若,2+2=4,，则太阳从西方升起。,（,6,）,若,2+2 4,，则太阳从西方升起。,p,q,q,p,s,t,s,r,s,r,s,t,第19页,命题与联结词,等价,符号：,定义,1.5,：设,p,，,q,为二命题，复合命题,“,p,当且仅当,q,”,称为,p,与,q,等价式，记作,p,q,，符号,称为等价联结词。并要求,p,q,为真当且仅当,p,与,q,同时为真或同时为假。,真值表：,P Q,P Q,0 0,1,0 1,0,1 0,0,1 1,1,p,q,逻辑关系为,q,与,p,互为充分必要条件。,第20页,命题与联结词,例,7,：将以下命题符号化。,（,1,）,2+2=4,当且仅当,3,是奇数。,（,2,）,2+2=4,当且仅当,3,不是奇数。,p,:,2+2=4,。,q,:,3,是奇数,。,（,3,）,2+2 4,当且仅当,3,是奇数。,（,4,）,2+2 4,当且仅当,3,不是奇数。,p,q,p,q,p,q,p,q,第21页,命题与联结词,说明,由联结词集 中一个联结词联结一个或两个原子命题组成复合命题是简单复合命题，能够称他们为基本复合命题。,屡次使用联结词集中联结词，能够组成更为复杂复合命题。求复杂复合命题真值时，还要要求联结词先后次序。将括号也算在内，这个次序为 ，对同一优先级联结词，先出现者先运算。,我们只关心复合命题中命题之间真值关系，而不关心命题内容。,比如,:(,(,P,Q,),R,)(,R,P,),Q,),可写成,:,(,P,Q,R,),R,P,Q,但有时为了看起来清楚醒目,也能够保留一些原可省去括号。,第22页,例,8,将以下命题符号化,设,P,表示,“,他有理论知识,”,Q,表示,“,他有实践经验,”,则,“,他现有理论知识又有实践经验,”,可译为,:,。,设,P,:,明天下雨,Q,:,明天下雪,R,:,我去学校。则,(i),“,假如明天不是雨夹雪则我去学校,”,可写成,;,(ii),“,假如明天不下雨而且不下雪则我去学校,”,可写成,;,(iii),“,假如明天下雨或下雪则我不去学校,”,可写成,;,(iv)“,当且仅当明天不下雪而且不下雨时我才去学校,;,命题与联结词,第23页,命题与联结词,例,9,：求式子真值。,p:0 q:0 r:0,p:1 q:0 r:1,p:0 q:1 r:0,第24页,第一章,命题逻辑,一、命题与联结词,二、命题公式及其赋值,三、等值式,四、析取范式与合取范式,五、联结词完备集,六、推理形式结构,七、自然推理系统,P,第25页,等值式,一、,等值,定义,2.1,注意,设,A,、,B,是两个命题公式，若,A,，,B,组成等价式,A,B,为重言式，则称,A,与B,是等值，记作,A,B,。,不是联结符，它是用来说明,A,与,B,等值，要与,区分清楚。,怎样判断两个命题公式是否等值？,方法一：经过真值表比较在各相同赋值情况下，真值是否相同。,方法二：将,A,，,B,组成,A,B,等价式，判断其是否为重言式。,第26页,等值式,例,1,：判断下面两个公式是否等值：,(,p,q),P Q,0 0,0,0 1,0,1 0,0,1 1,1,0,1,0,1,0,1,1,1,pq,(,p,q),(pq)(pq),pq,第27页,等值式,例,2,：判断下面公式是否等值：,(p,q)(p q),q,p q,0 0,0,0 1,0,1 0,0,1 1,1,0,0,0,0,1,1,0,1,(p,q),(pq),(pq)(pq),第28页,等值式,p q r,0 0 0,1,1,1,0 0 1,1,1,1,0 1 0,1,1,1,0 1 1,1,1,1,1 0 0,0,0,1,1 0 1,0,0,1,1 1 0,0,0,1,1 1 1,1,1,1,(p,q),(p,r),(p,(q,r),(p,q),(p,r),(p,(q,r),(p,q),(p,r),(p,(q,r),第29页,等值式,二、,16,组主要等值式,双重否定,A,A,等幂律,A,A,A,A,A,A,交换率,A,B B AAB B A,分配律,(A,B)C (AC)(BC),(AB)C (AC)(BC),结合律,(A,B)C A(BC),(AB)C A(BC),第30页,等值式,吸收律,A,(AB)A,A(AB)A,德摩根律,(AB)AB,(AB)AB,零律,A,11A00,同一律,A,0AA1A,排中律,A,A1,第31页,等值式,矛盾律,A,0,蕴涵等值式,A,A B,等价等值式,A,B(AB)(BA),假言易位,A,B B A,等价否定等值式,A,B,A,B,归谬论,(A,B)(AB)A,第32页,等值式,注意：,以上,16,组等值式都是用元语言符号书写，称这么等值式为等值式模式。能够将这些元语言符号用详细命题公式代替，则这些详细命题公式被称为等值式模式代入实例。,第33页,等值式,三、,等值演算,定义,等值演算规则,由已知等值式推演出另外一些等值式过程为,等值演算,。,置换规则,设,(A),是含公式,A,命题公式，,(B),是用公式,B,置换了,(A),中全部,A,后得到命题公式，若,A,B,，则,(A),(B),第34页,等值式,等值演算用途,（,1,）证实等值式,例,3,：用等值演算法验证等值式：,(p,q),r,(p,r),(q,r),(p,q),(p,q),(p,q),第35页,等值式,(p,q),r,(p,r),(q,r),方法一：,（,p,q),r,(p,q),r,(,p,q),r,(,p,r),(,q,r),(p,r),(q,r),方法二：,(p,r)q,r),(,p,r),(,q,r),(,p,q),r,(p,q),r,(p,q),r,第36页,等值式,(pq)(pq)(pq),(pq),(p,q),(q,p),(,p,q),(,q,p),(,p,q),(,q,p),(p,q),(q,p),(p,q),(,q,q),(p,p),(,q,p),(p,q),(,q,p),(p,q),(p,q),第37页,等值式,（,2,）判断命题公式类型,例,4,：判断以下公式类型：,(p,q),p),(p,q),(q,p),(p,q),(,p,q),(q,p),第38页,等值式,(p,q),p),(p,q),p),(,(p,q),p),(p,q),p,p,q),q,0,q,0,永假式,(,矛盾式,),第39页,等值式,(p,q),(q,p),(p,q),(p,q),(q,p),(p,q),(p,q),(p,q),1,永真式,(,重言式,),第40页,等值式,(,p,q),(q,p),(,p,q),(q,p),(p,q),(,q,p),(p,q),(,p,q),(,p,q),(,p,q),(,p,p,q),(,q,p,q),p,q,可满足式,第41页,等值式,（,3,）等值演算方法还能够帮助人们处理现实生活中一些判断问题,第42页,等值式,例,5,：用等值演算法处理下面问题。,A,、,B,、,C,、,D 4,人做百米竞赛，观众甲、乙、丙预报比赛名次为：,甲：,C,第一，,B,第二；,乙：,C,第二，,D,第三；,丙：,A,第二，,D,第四。,比赛结束后发觉甲、乙、丙每人汇报情况都是各对二分之一，试问实际名次怎样（假设并无并列者）？,第43页,等值式,甲：,C,第一，,B,第二；,乙：,C,第二，,D,第三；,丙：,A,第二，,D,第四。,1)(r,1,q,2,)(r,1,q,2,)1,p,i,:A,第,iq,i,:B,第,i r,i,:C,第,i s,i,:D,第,i,2)(r,2,s,3,)(r,2,s,3,)1,3)(p,2,s,4,)(p,2,s,4,)1,第44页,等值式,其中：,r,1,q,2,r,2,s,3,中,C,不可能既得第一名，又得第二名；,r,1,q,2,r,2,s,3,中,B,、,C,不能同时为第二名；,1)2)1,(r,1,q,2,)(r,1,q,2,)(r,2,s,3,)(r,2,s,3,),(r,1,q,2,r,2,s,3,)(r,1,q,2,r,2,s,3,),(r,1,q,2,r,2,s,3,)(r,1,q,2,r,2,s,3,),4):,1)2),(r,1,q,2,r,2,s,3,)(r,1,q,2,r,2,s,3,),1,第45页,等值式,第三名,第一名、,第四名、,第二名、,所以：,D,C,B,A,1,),(,),(,),(,),(,),(,),(,),(,),(,),(,),4),3,1,3,2,2,1,4,2,3,2,2,1,4,2,3,2,2,1,4,2,3,2,2,1,4,2,3,2,2,1,4,2,3,2,2,1,3,2,2,1,4,2,4,2,s,r,q,r,s,p,s,r,q,r,s,p,s,r,q,r,s,p,s,r,q,r,s,p,s,r,q,r,s,p,s,r,q,r,s,r,q,r,s,p,s,p,第46页,第一章,命题逻辑,一、命题与联结词,二、命题公式及其赋值,三、等值式,四、析取范式与合取范式,五、联结词完备集,六、推理形式结构,七、自然推理系统,P,第47页,析取范式与合取范式,一、,简单析取式、简单合取式,定义,1.18,注意,命题变项及其否定统称作,文字,。仅由有限个文字组成析取式称作,简单析取式,。仅由有限个文字组成合取式称作,简单合取式,。,一个文字既是简单析取式，又是简单合取式。,定理,（,1,）一个简单析取式是重言式当且仅当它同时含某个命题变项及它否定式。,（,2,）一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它否定式。,第48页,例,1,：判断下面公式哪些是简单析取式，哪些是简单合取式：,析取范式与合取范式,(pq),ppr,pq,ppr,pqr,pqr,p,第49页,二、,析取范式、合取范式,定义,1.19,（,1,）由有限个,简单合取式,组成,析取式,被称为,析取范式,。,（,2,）由有限个,简单析取式,组成,合取式,被称为,合取范式,。,（,3,）析取范式与合取范式统称为,范式,。,析取范式与合取范式,第50页,例,2,：判断下面公式哪些是析取式范式，哪些是合取范式：,注意：,（,1,）简单析取式既是析取范式，也是合取范式；,（,2,）简单合取式既是合取范式，也是析取范式；,析取范式与合取范式,(pq)(pq),(pq)(pr),prpq,pqr,p,第51页,二、,析取范式、合取范式,定理,（,1,）一个析取范式是矛盾式当且仅当它每个简单合取式都是矛盾式。,（,2,）一个合取范式是重言式当且仅当它每个简单析取式都是重言式。,怎样将一个命题公式转换成析取范式或合取范式,（,1,）首先消去公式中,和,联结词。,（,2,）其次，范式中不允许出现,p,、,(p,q),、,(p,q),。,（,3,）最终，析取范式中不允许出现,A,(BC),合取范式中不允许出现,A,(BC),析取范式与合取范式,第52页,二、,析取范式、合取范式,定理,1.4,（范式存在定理）,任一命题公式都存在着与之等值析取范式与合取范式。,析取范式与合取范式,第53页,例,3,：求下面公式析取范式与合取范式,析取范式与合取范式,注意：,命题公式析取范式与合取范式不唯一；,p,r,q,r,p,p,r,q,p,p,r,q,p,p,r,q,p,p,r,q,p,),(,),(,),),(,),),(,(,),),(),),(,),(,求析取范式,2,(pq)r)p,(1),求合取范式,(pq)r)p,(pq)r)p,(pq)r)p,(pq)r)p,(pq)(rp),第54页,三、,极大项、极小项,定义,1.20,在含有,n,个命题变项,简单合取式,（简单析取式）中，若每个命题变项和它否定式,不一样时出现,，而,二者之一必须出现且仅出现一次,，且第,i,个命题变项或它否定式出现在从左算起第,i,位上（若命题变项无角标，就按字典次序排列），称这么,简单合取式,（简单析取式）为,极小项,（极大项）。,析取范式与合取范式,第55页,析取范式与合取范式,例,4,：公式中出现,P,，,Q,，,R,三个命题变项以下公式哪些是极小项，极大项？,P,Q,P,Q,P,不是极小项，,P,，,P,同时出现,不是极小项，其中没出现,R,P,Q,R,是极小项,P,Q,R,P,Q,P,Q,P,是极大项,不是极大项，,P,，,P,同时出现,不是极大项，其中没出现,R,注意：,n,个命题变项共可产生,2,n,个不一样极小项，也可产生,2,n,个不一样极大项。,第56页,三、,极大项、极小项,极小项与极大项记法,析取范式与合取范式,极小项,极大项,公式,成真赋值,名称,公式,成假赋值,名称,P,Q,R,000,m,0,P,Q,R,000,M,0,P,Q,R,001,m,1,P,Q,R,001,M,1,P,Q,R,010m,2,P,Q,R,010,M,2,P,Q,R,011,m,3,P,Q,R,011,M,3,P,Q,R,100,m,4,P,Q,R,100,M,4,P,Q,R,101,m,5,P,Q,R,101,M,5,P,Q,R,110,m,6,P,Q,R,110,M,6,P,Q,R,111,m,7,P,Q,R,111,M,7,第57页,三、,极大项、极小项,定理,设,m,i,与,M,i,是命题变项,p,1,，,p,2,，,p,3,，,，,p,n,形成极小项和极大项，则,m,i,M,i,，,M,i,m,i,。,析取范式与合取范式,四、,主析取范式、主合取范式,定义,1.21,设由,n,个命题变项组成,析取范式,（合取范式）中全部,简单合取范式,（简单析取范式）都是,极小项,（极大项），则称该,析取范式,（合取范式）,为主析取范式,（主合取范式）。,第58页,析取范式与合取范式,四、,主析取范式、主合取范式,定理,2.5,任何命题公式都存在着与之等值主析取范式和主析取范式，而且是唯一。,第59页,例,5,：求主析取范式和主合取范式,析取范式与合取范式,(pq)r)p,(1),求主合取范式,(pq)r)p,(pq)r)p,(pq)r)p,(pq)r)p,(pq)(rp),(pq)(rr)(p(qq)r),(pqr)(pqr)(pqr),第60页,析取范式与合取范式,(2),求主析取范式,(pq)r)p,(pq)r)p,(pq)r)p,(pq)r)p,(pr)(qr)p,(p(qq)r)(pp)qr)(p(qq)(rr),(pqr)(pqr)(pqr)(pqr)(pqr),第61页,析取范式与合取范式,四、,主析取范式、主合取范式,主析取范式、主合取范式用途,（,1,）求公式成真与成假赋值,（,2,）判断公式类型,A,为重言式当且仅当,A,主析取范式包含,2,n,个极小项。,A,为矛盾式当且仅当,A,主析取范式不含任何极小项。,A,为可满足式当且仅当,A,主析取范式最少含有一个极小项。,第62页,例,6,：用公式主析取范式判断公式类型,2.2,析取范式与合取范式,(pq)q,p(pq),pq)q,(pq)q,(pq)q,0,p(pq),p(pq),(pq)(pq)(pq)(pq),1,第63页,析取范式与合取范式,（,3,）判断两个公式是否等值。,例,7,：判断以下公式是否等值,p,(pq)(pq),p,p,(q,q),(p,q),(p,q),所以两个公式等值,第64页,析取范式与合取范式,（,4,）应用主析取范式分析和处理实际问题。,例,8,：,某科研所要从,3,名科研骨干,A,，,B,，,C,中挑选,1,2,名出国进修。因为工作需要，选派时要满足以下条件：,若,A,去，则,C,同去；,若,B,去，则,C,不能去；,若,C,不去，则,A,或,B,能够去。,问所里应怎样选派他们？,第65页,2.2,析取范式与合取范式,四、,主析取范式、主合取范式,说明,（,1,）由公式主析取范式求主合取范式,（,2,）重言式与矛盾式主合取范式,A,为重言式当且仅当,A,主合取范式不包含,任何,极大项。,A,为矛盾式当且仅当,A,主合取范式包含,2,n,个极大项。,A,为可满足式当且仅当,A,主合取范式包含极大项少于,2,n,个。,第66页,第一章,数理逻辑,一、命题与联结词,二、命题公式及其赋值,三、等值式,四、析取范式与合取范式,五、联结词完备集,六、推理形式结构,七、自然推理系统,P,第67页,联结词完备集,一、,n,元真值函数,定义,注意,称,F:,0,，,1,n,0,，1,为,n,元真值函数,。,n,个命题变项可组成,(2,n,个,2,相乘,),个不一样,n,元真值函数,。,二、,联结词完备集,定义,设,S,是一个联结词集合，假如任何,n,（,n=1,）元真值函数都能够,由仅含,S,中联结词组成公式表示，则称,S,是,联结词完备集,。,第68页,联结词完备集,二、,联结词完备集,定理,S=,、,、,是联结词完备集。,推论,以下联结词集都是完备集：,（,1,）,S1,、,、,、,（,2,）,S2,、,、,、,、,（,3,）,S3,、,（,4,）,S4,、,（,5,）,S5,、,第69页,联结词完备集,二、,联结词完备集,定义,1.12 1.13,定理,设,pq,为两个命题，复合命题,“,p,与,q,否定式,”,（,“,p,或,q,否定式,”,）称作,p,，,q,与非式（或非式），记作,p,q(p,q),。符号,(),称作与非联结词或非联结词）。,p,q,为真当且仅当,p,与,q,不一样时为真（,p,q,为真当且仅当,p,与,q,同时为假）。,都是联结词完备集：,第70页,例：,给定命题公式,(PQ)R,，该公式在联结词完备集,中形式为,，在,中形式为,，在,中形式为,，在,中形式为,。,2.2,析取范式与合取范式,第71页,第一章,命题逻辑,一、命题与联结词,二、命题公式及其赋值,三、等值式,四、析取范式与合取范式,五、联结词完备集,六、推理形式结构,七、自然推理系统,P,第72页,推理形式结构,一、,推理,推理定义,推理有效性定义（定义,1.24,）,推理,是指从,前提,出发推出,结论,思维过程，而前提是已知命题,公式集合，结论是从前提出发应用推理规则推出命题公式。,设,A,1,，,A,2,，,A,k,，,B,都是命题公式，若对于,A,1,，,A,2,，,A,k,，,B,中出现命题变项,任意一组赋值，或者,A,1,A,2,A,k,为,假，或者当,A,1,A,2,A,k,为真时，,B,也为真，,则称由前提,A,1,，,A,2,，,A,k,推出,B,推理是有效或正确，并称,B,是有效结论。,第73页,3.1,推理形式结构,说明,（1,）推理,正确性与前提排列次序无关,，因而前提中公式,不一定是序列，而是一个,有限公式集合,，若这个集合极为,，可,将推,B,推理记为,B,。若推理是正确记为,B,，,不然记为,B,。这里能够成,B,和,A,1,，,A,2,，,A,k,B,为推理形式结构。,第74页,3.1,推理形式结构,（,2,）设,A,1,，,A,2,，,A,k,，,B,中共出现,n,个命题变项，对于任一组赋,值 ，前提和结论取值情况有以下,四种：,A,1,A,2,A,k,为,0,，,B,为,0,；,A,1,A,2,A,k,为,0,，,B,为,1,；,A,1,A,2,A,k,为,1,，,B,为,0,；,A,1,A,2,A,k,为,1,，,B,为,1,只要不出现,3),中情况，推理就是正确，所以判断方法是判,断是否会出现,3),中情况。,第75页,3.1,推理形式结构,（,3,）推理正确，并不能确保结论,B,一定为真，这与数学,中推理不一样。,例,1,：判断以下推理是否正确：,（,1,）,p,pq,q,（,2,）,p,qp,q,方法一：真值表法，分别计算出前提合取式以及结论真值情况，查看,是否出现情况,3),，假如不出现，则有效推理。,方法二：简单推理法，首先判断结论为,0,时，各命题变项取值情况，然,后，更据个变项取值求出前提合取式真值，假如真值能够为,1,，,则，推理不正确。,第76页,3.1,推理形式结构,定理,命题公式,A,1,，,A,2,，,A,k,推,B,推理正确当且仅当,(A,1,A,2,A,k,),B,为,重言式,。,怎样证实该定理？,判断推理是否正确三种方法,判断,(A,1,A,2,A,k,),B,是否为,重言式,。,第77页,3.1,推理形式结构,例,2:,判断以下推理是否正确,（,1,）若,a,能被,4,整除，则,a,能被,2,整除。,a,能被,4,整除，,所以,a,能被,2,整除,。,（,2,）若,a,能被,4,整除，则,a,能被,2,整除。,a,能被,2,整除，,所以,a,能被,4,整除,。,（,3,）若下午气温超出,30,摄氏度，则王小燕必去游泳。,若她去游泳，她就不去看电影了。所以，若王,小燕没去看电影，下午气温必超出了,30,摄氏度,。,第78页,3.1,推理形式结构,例,2:,判断以下推理是否正确,（,4,）假如他是理科学生，他必学好数学。假如他不是,文科学生，他必是理科学生。他没学好数学。所,以他是文科学生,。,步骤：,首先，将简单命题符号化，然后分别写出前提、结论。,然后，依据判断推理是否正确方法，判断推理。,真值表法,、,等值演算法,或,主析取范式法,第79页,3.1,推理形式结构,定义,九条主要推理定律,人们在研究过程中，发觉一些主要重言蕴含式，,这些主要,重言蕴含式,被称为,推理定律,。,二、,推理定律,A,（,A,B,）,附加律,（,A,BA,化简律,（,A,B,）,A,B,假言推理,（,A,B,）,B,A,拒取式,第80页,3.1,推理形式结构,（,A,B,）,B,A,析取三段论,（,A,B,）,（,B,C,）,A,C,假言三段论,（,A,B,）,（,B,C,）,A,C,等价三段论,（,A,B,）,（,C,D,）,(A,C),(B,D),（,A,B,）,（,A,B,）,(A,A),B,结构性二难,（,A,B,）,（,C,D,）,(,B,D),(,A,C),破坏性二难,第81页,3.1,推理形式结构,注意,（,1,）出现,A,、,B,、,C,等依然是元语言符号,，它们代表,是任意命题公式，因而九条推理定律全是以模式,形式出现。,（,2,）若一个推理形式结构与某条推理定律对应蕴含,式一致，则不用证实就可断定这个推理是正确，,只需说明用了某条推理定律即可,。,（,3,）,24,个等值式中每一个都派生出两条推理定律。,第82页,第一章,数理逻辑,一、命题与联结词,二、命题公式及其赋值,三、等值式,四、析取范式与合取范式,五、联结词完备集,六、推理形式结构,七、自然推理系统,P,第83页,3.2,自然推理系统,P,定义,3.2,一个形式系统,I,由下面四个部分组成：,一、形式语言系统，,形式演算系统,（,1,）非空字母表，记作,A(I),。,（,2,）,A(I),中符号结构合式公式集，记作,E(I),。,（,3,）,EI),中一些特殊公式组成公理集，记作,Ax(I),。,（,4,）推理规则集，记作,R(I),。,能够将,I,记为,4,元组,。其中,是,I,形式语言系统,，而,为,I,形式演算系统,。,第84页,3.2,自然推理系统,P,形式系统分类,（,1,）自然推理系统,二、自然推理系统,P,（,2,）公理推理系统,从,任意给定前提,出发，应用系统中推理规则进行推理演算，,得到最终命题公式是推理结论（有时称为有效结论，它可,是重言式，也可能不是）。,只能从,若干条给定公理,出发，应用系统中推理规则进行推理,演算，,得到结论是系统中重言式,，称为系统中定理。,我们介绍,是自然推理,系统,P,第85页,3.2,自然推理系统,P,定义,(1),字母表,二、自然推理系统,P,命题变项符号：,p,q,r,。,联结词符号：,。,括号与逗号,：（）,，,。,（,2,）合式公式,同定义,1.6,第86页,3.2,自然推理系统,P,（,3,）推理规则,前提引入规则：在证实任何步骤上都能够引入前提。,结论引入规则：在证实任何步骤上所得到结论都,能够做为后继证实前提。,置换规则：在证实任何步骤上，命题公式中子公,式都能够用与之等值公式置换，得到公式序列中又,一个公式。,假言推理规则（或称分离规则）：,A,B,A,B,第87页,3.2,自然推理系统,P,附加规则：,A,AB,化简规则：,A,B,A,拒取式规则：,AB,B,A,假言三段论规则：,A,B,BC,AC,第88页,3.2,自然推理系统,P,析取三段论规则：,A,B,B,A,结构性二难推理规则：,A,B,C D,A C,B D,结构性二难推理规则：,A,B,C D,B D,A C,第89页,3.2,自然推理系统,P,合取引入规则：,A,B,A B,第90页,3.2,自然推理系统,P,例,3:,在自然推理系统,P,中结构下面推理证实：,（,1,）前提：,p,q,q,r,p,s,s,结论：,r,(p,q),（,2,）前提：,p,r,q,s,p,q,结论：,r,s,（,3,）前提：,p,r,s,t,s,r,p,q,t,结论：,q,第91页,3.2,自然推理系统,P,证实两种方法,二、自然推理系统,P,（,1,）附加前提证实法,前提：,A1,、,A2,、,、,Ak,。,结论：,A,B,转成,前提：,A1,、,A2,、,、,Ak,、,A,结论：,B,第92页,3.2,自然推理系统,P,例,4:,用附加前提证实法证实以下推理：,（,1,）前提：,p,(q,r),s,p,q,结论：,s,r,（,2,）假如小张和小王去看电影，则小李也去看电影，,小赵不去看电影或小张去看电影。小王去看电,影。所以，当小赵去看电影时，小李也去。,第93页,3.2,自然推理系统,P,证实两种方法,二、自然推理系统,P,（,2,）归谬法,前提：,A1,、,A2,、,、,Ak,。,结论：,B,转成,前提：,A1,、,A2,、,、,Ak,、,B,结论：矛盾,第94页,3.2,自然推理系统,P,例,5:,用归谬证实法证实以下推理：,前提：,p,(,(r,s),q),s,p,结论：,q,第95页,