离散数学第二章命题演算的推理理论-假设推理系统.ppt
第二章 命题演算的推理理论,2.1 命题演算的公理系统 2.2 命题演算的假设推理系统 2.2.1 假设推理系统的组成 2.2.2 假设推理系统的推理过程2.3 命题演算的归结推理法,22 命题演算的假设推理系统,假设推理系统：由于它的推理形式类似于日常生活中的推理形式，也称为自然推理系统。,2.2.1 假设推理系统的组成,一、扩充的推理规则二、假设推理过程三、推理定理四、假设推理证明定理的方法,一、扩充的推理规则,分离规则的推广 A1，A2，AnA(2)肯定前提律 A1，A2，A3，An Ai,分离规则的推广,设有如下的推理规则 R：若A1，A2，An，可以推出A，即 R：A1，A2，An A，则称A是由 A1，A2，An实施规则R而得。设=A1，A2，An，则上述规则R可以记为 A 其中为形式前提，A为形式结论。,肯定前提律,A1，A2，A3，An Ai(i=1，2，n)，即前提中的任何命题均可作为结论。,二、假设推理过程,定义:如果能够作出一系列合式公式序列 A1，A2,A3,，An，它们(诸Ai)满足下列性质：(1)或为公理之一；(2)或为公式1,2,k之一，每个i称为假设；(3)或由前面的若干个Ag、Ah利用分离规则而得；(4)An=B。称这个公式序列A1，A2,，An为由公式 1，2，k证明B的证明过程.,1，2，k B,三、推理定理,(附加前提证明法)如果，AB，则 AB,要证(AB)，即要证，A B,附加前提证明法,如果 A1，A2，An-1，An，AB，则 A1，A2，An-1，An AB进而，有下面定理：A1，A2，An-1 An(AB)A1，A2，An-2 An-1(An(AB)依次类推可得定理：A1(A2(An(AB),(2)归谬法,如果，A B 且，A B，则 A。此定理称为反证律。这里B是一个公式。,其它公理、规则同前节。,四、假设推理证明定理的方法,(1)把待证公式的前件一一列出，作为假设(或把待证公式的后件的否定作为假设)，并在式子后注明为假设。(2)按上述介绍的推理方法进行推理，但此时不能对假设实施代入规则（因为假设不是永真公式）。(3)当推导出待证公式的后件时(或推导出矛盾时)就说证明了该定理。,第二章 命题演算的推理理论,2.1 命题演算的公理系统 2.2 命题演算的假设推理系统 2.2.1 假设推理系统的组成 2.2.2 假设推理系统的推理过程2.3 命题演算的归结推理法,例1：求证(P(Q R)(PQ)R),证明:(1)P(Q R)假设(2)P Q 假设(3)(PQ)P 公理8(4)(PQ)Q 公理9(5)P(3)(2)分离(6)Q(4)(2)分离(7)Q R(1)(5)分离(8)R(6)(7)分离 由假设推理过程的定义知：P(Q R)，P Q R 由推理定理得：(P(Q R)(PQ)R),(6)R 在(5)中用R代入P有错吗?不能对(5)实施代入规则!,例2(p21)求证：(PP)P,证明：(1)PP 假设(2)P 假设，结论的否定(3)P(1)(2)分离 显然，(2)与(3)表明推出矛盾(PP),P P(PP),P P 由反证法 得：(PP)P 由推理定理得：(PP)P,例(SQ)(PQ)S)P,解:(1)SQ 假设(2)PQ 假设(3)S 假设(4)P 假设,结论的否定(5)Q(1)(3)分离(6)Q(1)(3)分离 显然，(5)与(6)表明推出矛盾:SQ,PQ,S,P Q SQ,PQ,S,P Q 由反证法推理定理得：(SQ)(PQ)S)P,例(P(QR)(PQ)(PR),解:(1)P 假设(2)PQ 假设(3)P(QR)假设(4)Q(1)(2)分离(5)QR(1)(3)分离(7)R(4)(5)分离,即证得 P(QR),PQ,P R亦即证得命题：(P(QR)(PQ)(PR),例(PQ)R)(P(QR),解:(1)PQR 假设(2)P 假设(3)Q 假设(4)P(Q(PQ)公理10(5)Q(PQ)(2)(4)分离(6)PQ(3)(5)分离(7)R(1)(6)分离,即证得(PQ)R,P,Q R亦即证得(PQ)R)(P(QR),例(PQ)(PR)(QS)(SR),解:(1)(PQ)(PR)(QS)假设(2)PQ P 公理8(3)PQQ 公理9(4)(PQ)(PR)(QS)(PQ)代入(2)(5)(PQ)(PR)(QS)(PR)(QS)代入(3)(6)PQ(1)(4)分离(7)(PR)(QS)(1)(5)分离(8)(PR)(QS)(PR)代入(2)(9)(PR)(QS)(QS)代入(3)(10)PR(7)(8)分离(11)QS(7)(9)分离(12)P(2)(6)分离(13)Q(3)(6)分离(14)R(10)(12)分离(15)S(11)(13)分离(16)S(R(SR)公理10(17)R(SR)(15)(16)分离(18)SR(14)(17)分离,例 QQ心情谜语,现在是晚上十一点，天很暖。如果我考试通过了，那么我很快乐。如果我快乐，那么阳光灿烂。解：设 P：我考试通过了，Q：我很快乐，R：阳光灿烂，S：天很暖。前提：PQ，QR，RS,例(续)QQ心情谜语,(1)PQ 前提引入(2)QR 前提引入(3)(PQ)(QR)(PR)公理3(4)(QR)(PR)(1)(3)分离(5)PR(2)(4)分离(6)RS 前提引入(7)PQP 公理8(8)RSR(7)中,P用R,Q用S代入(9)R(7)(8)分离(10)(PQ)(QP)拒取式，定理3(p18)(11)(PR)(RP)(10)中Q用R代入(12)RP(5)(11)分离(13)P(9)(12)分离 所以有效结论是：我考试没通过。,例 甲是否盗窃了电脑？,公安人员审一件盗窃案。已知：(1)若甲盗窃了电脑，则作案时间不能发生在午夜前。(2)若乙证词正确，则在午夜时屋里灯光未灭。(3)若乙证词不正确，则作案时间发生在午夜前。(4)午夜时屋里灯光灭了。问：甲是否盗窃了电脑？,解 设 p：甲盗窃了电脑 r：作案时间发生在午夜前，s：乙证词正确，t：午夜时屋里灯光灭了。前提：pr，st，sr，t,例(续)甲是否盗窃了电脑？,(1)pr(2)st(3)sr(4)t(5)(PQ)(QP)公理14(6)(st)(ts)代入(6)(7)ts(3)(7)分离(8)s(5)(8)分离(9)r(4)(9)分离(10)(pr)(rp)代入(6)(11)rp(2)(11)分离(12)p(10)(12)分离,因此可得结论：甲不是盗窃犯。,例 谁是盗窃犯？,公安人员审一件盗窃案。已知：(1)若甲盗窃了电脑，则作案时间不能发生在午夜前。(2)若乙证词正确，则在午夜时屋里灯光未灭。(3)若乙证词不正确，则作案时间发生在午夜前。(4)午夜时屋里灯光灭了。问：谁是盗窃犯？,解 设 p：甲盗窃了电脑 r：作案时间发生在午夜前，s：乙证词正确，t：午夜时屋里灯光灭了。q：乙盗窃了电脑 前提：pr，st，sr，t，pq,例(续)谁是盗窃犯？,(1)pq(2)pr(3)st(4)sr(5)t,因此可得结论：乙是盗窃犯。,(PQ)(QP)公理14(st)(ts)代入(6)ts(3)(7)分离 s(5)(8)分离 r(4)(9)分离(pr)(rp)代入(6)rp(2)(11)分离 p(10)(12)分离(AB)(AB)析取三段论(pq)(pq)代入(14)p q(1)(15)分离 q(13)(16)分离,第二章 命题演算的推理理论,2.1 命题演算的公理系统 2.2 命题演算的假设推理系统 2.2.1 假设推理系统的组成 2.2.2 假设推理系统的推理过程 2.3 命题演算的归结推理法,
