离散数学第二章-命题演算的推理理论-命题演算的公理系统.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,目录（,数理逻辑）,第一章 命题演算基础（,6,学时）,第二章 命题演算的推理理论（,4,学时,）,第三章 谓词演算基础（,5,学时）,第四章 谓词演算的推理理论（,5,学时）,第五章 递归函数论（,4,学时）,第二章 命题演算的推理理论,例 判断下面各推理是否正确,:,(1),如果天气凉快,小王就不去游泳。,天气凉快,所以小王没去游泳。,(2),如果天气凉快,小王就不去游泳。,天气不凉快,所以小王去游泳了。,推理是否正确：形式化,引入符号：,P,表示天气凉快，,Q,表示小王去游泳,(1),如果天气凉快,小王就不去游泳。天气凉快,所以小王没去游泳。,(,P,Q,),P,),Q,(2),如果天气凉快,小王就不去游泳。天气不凉快,所以小王去游泳了。,(,P,Q,),P,),Q,推理是否正确,?,考察主析取范式,(,P,Q),P,),Q,=,(,P,Q),P,),Q,=,(,P,Q),P,Q,=,(,P,Q),P,Q,=(P,Q),P,Q,=(P,Q)(,P,(,Q,Q,),(,Q,(,P,P,),=(P,Q)(,P,Q),(,P,Q),(,Q,P),=m,0,m,2,m,3,m,1,永真公式,推理是否正确,?,考察主析取范式,(P,Q),P),Q,=,(P,Q),P),Q,=,(,P,Q),P,Q,=,(,P,Q),P,Q,=(P,Q),P,Q,=(P,Q)(,P,(,Q,Q),(,Q,(,P,P),=(P,Q)(,P,Q),(,Q,P),=m,0,m,1,m,2,非永真公式,推理是否正确：真值表,P Q,(P,Q),P),Q,(P,Q),P),Q,T T T T,T F T T,F T T,F,F F T T,(P,Q),P),Q,为永真公式,而,(P,Q),P),Q,不是永真的。,三段论,三段论,可用三段论表示,(,P,Q,),P,),Q,如下：,P,Q,大前提,P,小前提,Q,结 论,例,如果今天下雨，则运动会将推迟举行；,今天下雨；,运动会将推迟举行。,逻辑推理,由前提推出结论,（,前提与结论都是命题，可真可假）,演绎推理,归纳推理,归纳推理,从真的前提出发，得到的结论只能够要求它与前提是,协调的,，但不一定是真的。,它基于对特殊的代表的有限观察，或基于对反复再现的现象的模式的有限观察，用公式表达规律。,所有观察到的乌鸦都是黑的。,所以所有乌鸦都是黑的。,演绎推理,可推导性,当前提的真蕴涵结论的真时，称前提和结论之间有可推导性关系，即前提和结论之间的推理是正确的。,演绎推理,前提和结论之间有可推导性关系的这种推理。,前提和结论间的形式关系,(,而,不考虑内容,),如果,1+1=3,，则雪是黑的。,1+1=3,。,雪是黑的。,该推理过程正确,但不意味着前提与结论正确,第二章 命题演算的推理理论,2.1,命题演算的公理系统,2.1.1,公理系统的组成部分,2.1.2,公理系统的推理过程,2.2,命题演算的假设推理系统,2.3,命题演算的归结推理法,2,1,命题演算的公理系统,给出若干条永真公式,(,称为公理,),，,再给出若干条由永真公式推出永真公式的推理规则，,由它们出发推出一切永真公式的系统。,了解公理系统的构成规则和推理形式，,培养读者构造公理系统及利用该公理系统进行推理的能力。,2,1,1,公理系统的组成部分,一、语法部分,基本符号,公理系统所允许出现的全体符号的集合,公理,规则,二、语义部分,基本符号,命题变元,P,，,Q,，,R,，,等字母表示命题变元,联结词,、,、,、,、,是联结词,括号,(,，,),是括号,合式公式,(1),任何命题变元均是公式；,(2),如果,P,为公式，则,P,为公式；,(3),如果为,P,，,Q,为公式，则,P,Q,，,P,Q,，,P,Q,，,P,Q,为公式；,(4),当且仅当经过有限次使用,(1),(2),(3),所组成的符号串才是公式。,推出符,表示其后的公式为永真公式,(,教材中遗漏,),公理,公理,1,P,P,公理,2 (,P,(,Q,R,),(,Q,(,P,R,),公理,3 (,P,Q,),(,Q,R,),(,P,R,),公理,4 (,P,(,P,Q,),(,P,Q,),公理,5 (,P,Q,),(,P,Q,),公理,6 (,P,Q,),(,Q,P,),公理,7 (,P,Q,),(,Q,P,),(,P,Q,),调头,传递,凝缩,与,有关,公理,公理,8 (P,Q),P,公理,9 (P,Q),Q,公理,10 P,(Q,(P,Q),公理,11 P,(P,Q),公理,12 Q,(P,Q),公理,13 (P,R),(Q,R),(,P,Q),R),公理,14 (P,Q),(Q,P),公理,15,P,P,与,有关,与,有关,与,有关,常用推理定律,(,详见耿素云,离散数学,),P,(PQ),附加,(PQ),P,化简,(P,Q)P),Q,假言推理,(P,Q),Q,),P,拒取式,(A,B),A)B,析取三段论,(AB),(B,C)(AC),假言三段论,(AB),(B,C)(AC),等价三段论,(AB),(C,D),(AC),(B,D),构造性二难,常用推理定律,(,详见方世昌的,离散数学,),P,(PQ),加法式,(PQ),P,简化式,(P,Q)P),Q,假言推理,(P,Q),Q,),P,拒取式,(A,B),A)B,析取三段论,(AB),(B,C)(AC),(,假言,),前提三段论,(AB),(C,D),(AC),(B,D),构造性二难,(AB),(C,D),(,B,D,),(A,C,),破坏性二难,规则,(1),代入规则：将公式,中出现的某一符号,B,每处均代以某一公式,C,，所到的公式,D,称为,C,对,的代入。,(2),分离规则：如果,A,B,且,A,，则,B,。,二、语义部分,(1),公理是永真公式。,(2),规则规定如何从永真公式推出永真公式。分离规则指明，如果,A,B,永真且,A,永真，则,B,也为永真公式。,(3),代入规则指明如果,为永真公式，则某一个公式正确代入公式,后所得的公式也为永真公式。,(4),定理为永真公式，它们是从公理出发利用分离规则和代入规则推出来的公式。,第二章 命题演算的推理理论,2.1,命题演算的公理系统,2.1.1,公理系统的组成部分,2.1.2,公理系统的推理过程,2.2,命题演算的假设推理系统,2.3,命题演算的归结推理法,定理,1(p18),P,P,证明：,(1)(P,Q,),(,Q,P,),公理,14,(2)(,P,P,),(,P,P,),P,用,P,，,Q,用,P,代入,(3)P,P,公理,1,(4),P,P,P,用,P,代入,(5)P,P,(2)(,4,),分离,P=P,例,(PP)P,证明：,(1),(PR)(QR)(PQ)R),公理,13,(2),(PP)(PP)(PP)P),(1),式中,Q,用,P,、,R,用,P,代入,P,P,公理,1,(PP)(PP)P),(2)(3),分离,(PP)P,(3)(4),分离,例,P,(,P,P,),证明,(1)(PR)(QR)(PQ)R),公理,13,(2)(PP)(PP)(PP)P),(1),式中,Q,用,P,、,R,用,P,代入,(3)P,P,公理,1,(4)(PP)(PP)P),(2)(3),分离,(5)(PP)P,(3)(4),分离,(6)P,(P,Q),公理,11,(7)P,(P,P),(6),式中,Q,用,P,代入,(8)(,P,Q,),(,Q,P,),(,P,Q,),公理,7,(9)(,P,(,P,P),(,P,P),P,),(,P,(P,P),(8),式中,Q,用,P,P,代入,(10)(,P,P),P,),(,P,(P,P),(7)(9),分离,(11),P,(P,P),(5)(10),分离,定理,2(p18),(P,Q),(R,P),(R,Q),分析：由传递公理,3,知道,(R,P,),(,P,Q,),(,R,Q,),与要求证的公式的联系是两个前件次序换一换，就可以用调头公理,2,：,(,P,(,Q,R,),(,Q,(,P,R,),加头公式,定理,2(p18),(P,Q),(R,P),(R,Q),证明：,(1)(P,Q,),(,Q,R,),(,P,R,),公理,3,(2)(R,P,),(,P,Q,),(,R,Q,),P,用,R,，,Q,用,P,，,R,用,Q,代入,(3)(P,(,Q,R,),(,Q,(,P,R,),公理,2,(4)(R,P),(,P,Q),(,R,Q,),(,P,Q,),(,R,P),(,R,Q,),P,用,R,P,，,Q,用,P,Q,，,R,用,R,Q,代入,(5)(P,Q,),(,R,P,),(,R,Q,),(4)(2),分离,定理,3(p18,拒取式,)(P,Q),(,Q,P),分析：由公理,14,，,(,P,Q,),(,Q,P,),，,可以得到,(,P,Q,),(,Q,P,),下面就是要建立,(,P,Q,),与,(,P,Q,),之间的联系。,如果,(,P,Q,),(,P,Q,),，,则由传递性知道结论成立。,下面先证明,(,P,Q,),(,P,Q,),。,证明：先证,(,P,Q,),(,P,Q,),(1),P,P,定理,1,(2),Q,Q,P,用,Q,代入,(3)(,P,Q,),(,Q,P,),公理,14,(4)(,P,Q,),(,Q,P,),Q,用,Q,代入,(5)(,P,Q,),(,R,P,),(,R,Q,),加头,定理,2,(6)(,Q,Q,),(,P,Q,),(,P,Q,),(5),式中,P,用,Q,代入，,Q,用,Q,代入，,R,用,P,代入,(7)(,P,Q,),(,P,Q,),(6)(2),分离,定理,3(p18,拒取式,)(,P,Q,),(,Q,P,),证明：,(1),P,P,定理,1,(2),Q,Q,P,用,Q,代入,(3)(,P,Q,),(,Q,P,),公理,14,(4)(,P,Q,),(,Q,P,),Q,用,Q,代入,(5)(,P,Q,),(,R,P,),(,R,Q,),定理,2,(6)(,Q,Q,),(,P,Q,),(,P,Q,),(5),式中,P,用,Q,代入，,Q,用,Q,代入，,R,用,P,代入,(7)(,P,Q,),(,P,Q,),(6)(2),分离,(8)(,P,Q,),(,Q,R,),(,P,R,),公理,3,(9)(,P,Q,),(,P,Q,),(,P,Q,)(,Q,P,)(,P,Q,),(,Q,P,),(8),式中,P,用,P,Q,，,Q,用,P,Q,，,R,用,Q,P,代入,(10)(,P,Q,),(,Q,P,),(,P,Q,),(,Q,P,),(9)(7),分离,(11)(,P,Q,),(,Q,P,),(10)(4),分离,例,（同定理,3,）,已知公理,A:P,P,B:(P,Q)(QP),C:(P,Q)(RP)(RQ),D:(P,Q)(QR)(PR),要证,(PQ)(QP),为本系统中的定理。,公理推理证明定理的方法,对于简单题，可以把待证明的公式变成永真蕴涵式的后件，再证明前件永真。,引理,P,(,P,Q),Q),证明：,(1)(,P,(,Q,R),(,Q,(,P,R),公理,2,(2)(,P,Q,)(,P,Q),(,P,(,P,Q,),Q),Q,用,P,代入,，,R,用,Q,代入,，,P,用,P,Q,代入,(3)P,P,公理,1,(4),(P,Q)(P,Q),代入,(5),P,(,P,Q,),Q),分离,(2)(4),例,1(p18),已知引理，试证明,(P,P),P,(1),P,(,P,Q,),Q,),定理,(2),P,(,P,P,),P,),Q,用,P,代入,(3)(,P,Q,),(,Q,P,),公理,14,(4)(,P,P,),P,),(,P,(,P,P,),P,用,P,P,代入，,Q,用,P,代入,(5)(,P,Q,),(,R,P,),(,R,Q,),定理,2,(6),(,P,P,),P,),(,P,(,P,P,),(,P,(,P,P,),P,),(,P,(,P,(,P,P,),P,用,(,P,P,),P,，,Q,用,P,(,P,P,),，,R,用,P,代入,(7)(,P,(,P,P,),P,),(,P,(,P,(,P,P,)(6)(4),分离,(8),P,(,P,(,P,P,)(7)(2),分离,(9)(,P,(,P,Q,),(,P,Q,),公理,4,(10)(,P,(,P,(,P,P,),(,P,(,P,P,),Q,用,(,P,P,),代入,(11)(,P,(,P,P,)(10)(8),分离,(12)(,P,(,P,P,),(,P,P,),P,)(3),式中,Q,用,P,P,代入,(13)(,P,P,),P,(12)(11),分离,例,2(p19),已知公理：,A,P,(,Q,P,),B,(,P,(,Q,R,),(,P,Q,),(,P,R,),C,(,P,(,Q,R,),(,Q,(,P,R,),D P,(,P,Q,),E,(,P,Q,),(,Q,P,),及分离规则和代入规则,证明公式,(,R,R,),(,P,P,),为定理。,P,P,？,例,2,的分析,先要证明,P,P,如果用公理,A,：,P,（,Q,P,），得到,P,（,P,P,），,难以继续。,证明,:,先证,P,P,P,(Q,P),公理,A,(2)(P,(Q,R),(P,Q),(P,R),公理,B,(3)(P,(Q,P),(P,Q),(P,P),R,用,P,代入,(2),(4)(P,Q),(P,P),(3)(1),分离,(5)(P,(Q,P),(P,P),Q,用,Q,P,代入,(4),(6)P,P,(5)(1),分离,例,2,的证明,(p19),(1),P,(,Q,P,),公理,A,(2),(,P,(,Q,R,),(,P,Q,),(,P,R,),公理,B,(3)(,P,(,Q,P,),(,P,Q,),(,P,P,),R,用,P,代入,(2),(4)(,P,Q,),(,P,P,)(3)(1),分离,(5)(,P,(,Q,P,),(,P,P,),Q,用,Q,P,代入,(4),(6),P,P,(5),(1),分离,(7),P,(,P,Q,),公理,D,(8)(,P,P,),(,P,P,),(,R,R,),P,用,P,P,，,Q,用,R,R,代入,(7),(9)(,P,P,),(,R,R,)(8)(6),分离,(10),(,P,Q,),(,Q,P,),公理,E,(11)(,P,P,),(,R,R,),(,R,R,),(,P,P,),P,用,P,P,，,Q,用,R,R,代入,(10),(12),(,R,R,),(,P,P,),(11)(9),分离,已知公理,A:(p,q)(qp)(pq),B:pp,q C:p,p D:(pr)(qr)(p,q),r)E:p,q,p,证明定理,:p(p,p),同前例,!,例,3,(1),pp,q,公理,B,(2),pp,p,代入,(3),(pr)(qr)(p,q),r),公理,D,(4)(pp)(pp)(p,p),p),代入,(5)p p,公理,C,(6)(pp)(p,p),p)(4)(5),分离,(7)(p,p),p (5)(6),分离,证明：先证,(p,p),p,(1),pp,q,公理,B,(2),pp,p,代入,(3),(pr)(qr)(p,q),r),公理,D,(4)(pp)(pp)(p,p),p),代入,(5)p p,公理,C,(6)(pp)(p,p),p)(4)(5),分离,(7)(p,p),p (5)(6),分离,(8)(p,q)(qp)(pq),公理,A,(9),(p,(p,p),)(p,p),p)(p(p,p),),代入,(10)(p,p),p)(p(p,p),),(2)(9),分离,(11)(p(p,p),),(7)(10),分离,例,3,的证明,例,4,已知公理,A,：,(Q,R)(PQ)(PR),B,：,(P,(QR)(Q(PR),C,：,(P,Q)(QR)(PR),D,：,P,P,及分离规则和代入规则,试证明下式为定理,(P,Q),R),(P,Q),R),例,4,的证明,(1),P,P,公理,4,(2),Q,Q,P,用,Q,代入,(3)(QR)(PQ)(PR),公理,1,(4)(,Q,Q)(P,Q),(PQ),Q,用,Q,代入,R,用,Q,代入,(5)(P,Q),(PQ),(4),、,(2),分离,(6)(PQ)(QR)(PR),公理,3,(7)(P,Q),(PQ),(PQ),R)(P,Q),R),P,用,P,Q,代入，,Q,用,P,Q,代入，,R,用,R,代入,(8)(P,Q),R),(P,Q),R),(7),、,(5),分离,例,5,已知公理：,A:,P,(,Q,P,),B:,(,Q,R,),(,P,Q,),(,P,R,),C:,(,P,P,),P,D:Q,(,P,Q,),E:,(,P,Q,),(,Q,P,),及分离规则和代入规则,试证明,P,P,为定理,例,5,的证明,(1)P,(,Q,P),公理,A,(2)(Q,R),(,P,Q,),(,P,R,),公理,B,(3)(P,P,),P,公理,C,(4)Q,(,P,Q,),公理,D,(5)(P,Q,),(,Q,P,),公理,E,(6)(P,P),P)(P(P,P),(PP),(2),式中,Q,用,P,P,、,R,用,P,代入,(7)(P(P,P),(PP)(3)(6),分离,(8)P(P,P),(4),式中,Q,用,P,代入,(9)P,P (7)(8),分离,第二章 命题演算的推理理论,2.1,命题演算的公理系统,2.1.1,公理系统的组成部分,2.1.2,公理系统的推理过程,2.2,命题演算的假设推理系统,2.3,命题演算的归结推理法,