离散数学第7讲

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,离散数学 第,7,讲,回顾上节课重要知识点：,理解命题逻辑推理的基本概念；,掌握推理常用的三种方法：,真值表法,等价值演算法,主析取范式,掌握九条重要的推理定律；,1,离散数学 第,7,讲,本节课基本知识点：,自然推理系统的定义,自然推理系统中的常用的推理规则；,自然推理系统中的构造证明法。,2,第三章 命题逻辑的推理理论,3.2,自然推理系统,在推理过程中，如果命题变元较多或前提较多，以上三种方法都不方便，因而引入,构造证明方法,。,证明,是一个描述推理过程的,命题公式序列,，其中的每个命题公式，或者是已知的前提，或者是由某些前提应用推理规则得到的结论（中间结论或推理中的结论）。,而要构造出严谨的证明就必须在形式系统中进行，因而首先给出形式系统的定义。,3,第三章 命题逻辑的推理理论,定义,3.2,形式系统,一个形式系统,I,由下列四个部分组成：,（,1,）非空的字母表集，记作,A,（,I,）。,（,2,）由,A,（,I,）,中符号构造的合式公式集，记作,E,（,I,）。,（,3,）,E,（,I,）,中一些特殊的公式组成的公理集,记作,A,X,（,I,）。,（,4,）,推理规则集，记作,r,（,I,）,。,可以将,I,记作为,4,元组,其中,是,I,的,形式语言系统,为,I,的,形式演算系统,4,第三章 命题逻辑的推理理论,形式系统一般分为两类：,自然推理系统,（本书介绍）,特点：从任意给定的前提出发，应用系统中的推理规则进行推理演算，得到的最后命题公式是推理的结论，此结论可能是重言式，也可能不是。,公理推理系统,特点：只能从若干条给定的公理出发，应用系统中的推理规则进行推理演算，得到的结论是系统中的重言式，称为系统中的定理。,5,第三章 命题逻辑的推理理论,定义,3.3,自然推理系统,（不含有公理部分）,自然推理系统,p,定义如下：,1,、字母表,（,1,）命题变项符号：,p,q,r,（,2,）,联结词符号：,，,（,3,）,括号与逗号,：,(),2,、合式公式 定义同,1.6,3,、推理规则,6,第三章 命题逻辑的推理理论,构造证明法祥解：,构造证明法,也是自然推理中的一种常用方法，,适用于命题变项较多时,，且必须在给定的规则下进行。,构造证明法,是,一个描述推理过程的命题公式序列,，,其中的每个命题公式或者是已知的前提,，或者是,某些前提应用推理规则得到的结论,。,7,第三章 命题逻辑的推理理论,证明中常用的推理规则：,1,、前提引入规则,P,：,在证明的任何一步上都可引入前提。,2,、结论引入规则,T,：,在证明的任何一步上，所证明的结论都可作为后续证明的前提。,3,、置换规则,：在证明的任何一步上，命题公式中任何子命题公式都可用与之等值的命题公式置换。（等值公式参考课本,P21,）,8,第三章 命题逻辑的推理理论,4,、代入规则：,在证明的任何一步上，永真式中某一变元的所有出现都可代入同一公式。,5,、假言推理规则,(,分离规则,),：,A,B,A=B,6,、,附加规则,：,A=AB,7,、,化简规则,：,AB=A,8,、,拒取式规则,：,A,B,B,=,A,9,、,假言三段论规则,：,A,B,B,C=A,C,9,第三章 命题逻辑的推理理论,10,、析取三段论规则,:,A B,A=B,11,、,构造性两难规则：,A,B,C,D,AC=B D,12,、,合取引入规则：,A,，,B=AB,13,、,假设引消规则,CP,规则,：可在任何步骤引入假设,A,，,此后推出,B,后，即可消去假设,A,，,而得到结论,A,B(,附加前提,),。,10,第三章 命题逻辑的推理理论,例：前提：,P,R,，,Q S,，,P,Q,结论：,R S,证明：,P,R,前提引入,Q S,前提引入,P,Q,前提引入,R S,构造性两难规则,11,第三章 命题逻辑的推理理论,例,3.3,：在自然推理系统中构造下列推理的证明。,(1),前提：,p,q,q,r,p,s,s,结论：,r(q p),（,前提、结论已明确给出）,证明：,p,s,前提引入,s,前提引入,p ,拒取式,p,q,前提引入,q ,析取三段论,q,r,前提引入,r ,假言推理,r(q p),合取规则,12,第三章 命题逻辑的推理理论,(2),前提：,p,q,r,q,r,s,结论：,p,s,（,前提、结论已明确给出）,解：,p,q,前提引入,p,q,置换规则,r,q,前提引入,q,r,置换规则,p,r,假言三段论,r,s,前提引入,p,s,假言三段论,13,第三章 命题逻辑的推理理论,注：,1,、推理过程不是唯一的。,只要严格按照推理规则从而得到有效结论的推理就是正确的。,2,、证明过程中不要跳步。（跳步在等价公式或蕴含式的证明中可以使用，但这里不可以）,14,第三章 命题逻辑的推理理论,例,3.4,：在自然推理系统中构造下列推理的证明。,若,a,是实数，则它不是有理数就是无理数。若,a,不能表示成分数，则它不是有理数。,a,是实数且它不能表示成分数，所以,a,是无理数。,（,前提、结论未明确给出,需要自己构造。,),解：首先将简单命题符号化,p:a,是实数,q:a,是有理数,r:a,是无理数,s:a,能表示成分数,15,第三章 命题逻辑的推理理论,前提：,p,(q,r),s,q,，,p,s,结论：,r,证明,:,p,s,前提引入,p,化简规则,s ,化简规则,p,(q,r),前提引入,q,r ,假言推理,s,q,前提引入,q ,假言推理,r ,析取三段论,16,第三章 命题逻辑的推理理论,两种特殊的证明方法,1,附加前提证明法（,CP,规则）,适用于此类蕴涵式的证明,(,A,1,A,2,A,k,),(A B)(*),欲,证明,(*),式为,重言式,，,只需证明,(,A,1,A,2,A,k,A)B,为重言式，因为,17,第三章 命题逻辑的推理理论,(*),式,(,A,1,A,2,A,k,),(A B),(,A,1,A,2,A,k,),(,A,B),(,A,1,A,2,A,k,),(,A,B),A,1,A,2,A,k,A,B,(,A,1,A,2,A,k,A),B,(,A,1,A,2,A,k,A),B,(,A,1,A,2,A,k,A),B,18,第三章 命题逻辑的推理理论,例,：,前提：,p,(q,r,),s,p,q,结论：,s,r,证明：,s,p,前提引入,s,附加,前提引入,CP,规则,p ,假言推理,p,(q,r,),前提引入,q,r ,假言推理,q,前提引入,r ,假言推理,s,r,CP,规则,19,第三章 命题逻辑的推理理论,两种特殊的证明方法,2,归谬法,适用于此类蕴涵式的证明,(,A,1,A,2,A,k,),B (*),欲,证明,(*),式，只需将,B,作为前提能推出矛盾来即可。因为：,(*),(,A,1,A,2,A,k,),B,(,A,1,A,2,A,k,B,）,若,(,A,1,A,2,A,k,B,）为,矛盾式，则,(,A,1,A,2,A,k,),B,为,重言式 ，即,(,A,1,A,2,A,k,),=B,20,第三章 命题逻辑的推理理论,例,：前提：,p,q ,r,q,r,s,结论：,p,证明：,p,结论否定,引入,p,q,前提引入,q,假言推理,r,q,前提引入,r ,析取三段论,r,s,前提引入,r ,化简规则,r,r ,合取，矛盾,21,第三章 命题逻辑的推理理论,练习,：用归谬法证明,前提：,p,q,，,p,r,q,s,结论：,r s,证明：,(r s),结论否定,引入,r,s ,置换规则,r,化简规则,p,r,前提引入,p,拒取,s,化简规则,q,s,前提引入,22,第三章 命题逻辑的推理理论,q ,拒取,p,q ,合取,(,p,q),置换规则,(11)p,q,前提引入,(12),(,p,q),(p,q)(11),合取,矛盾,23,第三章 命题逻辑的推理理论,本讲小结,掌握自然推理系统中的常用的推理规则；,能够应用这些推理规则在自然推理系统对推理进行构造证明。,作业,P55,第,11,、,12,、,14,、,15,、,16,、,18,题,24,第三章 命题逻辑的推理理论,本章小结,一、本章重要知识点：,理解命题逻辑推理的基本概念；,掌握推理常用的三种方法：,掌握九条重要的推理定律；,掌握自然推理系统中的常用的推理规则；,能够应用这些推理规则在自然推理系统对推理进行构造证明。,25,第三章 命题逻辑的推理理论,二、典型例题,1,、,R(,P,S),Q,S=P(QR),2,、,RQ,，,RS,，,SQ,，,PQ,=,P,3,、试证明,（），,，,=,。,26,