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

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