《《假设推理系统》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《假设推理系统》PPT课件.ppt（37页珍藏版）》请在三一办公上搜索。
1、2.2 假设推理系统,自然推理系统,一、扩充的推理规则二、假设推理过程三、推理定理四、假设推理证明定理的方法,2.2.1 假设推理系统的组成,一、扩充的推理规则,P Q 大前提 P 小前提 Q 结 论,推理的有效性由永真公式：(P Q)P)Q所保证。,分离规则(回顾):P Q,P Q,一、扩充的推理规则,称B是由 A1，A2，An实施规则R而得,其中R为：R：A1，A2，An B,设有重言式：(A1 A2 An)B,拒取式,P Q 大前提 Q 小前提 P 结 论,推理的有效性由永真公式：(P Q)Q)P所保证。,析取三段论,P Q 大前提 P 小前提 Q 结 论,推理的有效性由永真公式：(P
2、Q)P)Q所保证。,假言三段论,P Q 前提 Q R 前提 P R 结论,推理的有效性由永真公式：(P Q)(Q R)(P R)所保证。,合取,P 前提 Q 前提 P Q 结论,推理的有效性由永真公式：P(Q(P Q)所保证。,肯定前提律（化简）,P Q 前提 P 结论,推理的有效性由永真公式：(P Q)Q所保证。,一般地，A1，A2，A3，An Ai(i=1，2，n)，即前提中的任何命题均可作为结论。,置换(替换),任何命题公式都可以用与之等价的命题公式置换。,如果A=B，则 A B,例 P Q P Q,二、假设推理过程,定义:如果能够作出一系列合式公式序列 A1，A2,A3,，An，它们满
3、足下列性质：(1)诸Ai或为公理/定理之一；(2)或为公式1,2,k之一，每个i称为假设；(3)或由前面的若干个Ag、Ah利用分离规则而得；(4)An=B。称这个公式序列A1，A2,，An为由公式 1，2，k证明B的证明过程.,1，2，k B,三、推理定理,附加前提推理定理（CP规则）如果，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 且，
4、A B这里B是一个公式。则有:A。,四、假设推理证明定理的方法,把待证公式的前件一一列出，注明为假设或前提。按推理规则进行推理，但此时不能对假设以及演绎公式实施代入规则。(3)当推导出待证公式的后件时，就完成了该定理的证明。,附加前提推理证明方法,四、假设推理证明定理的方法,(1)把待证公式的前件一一列出，把待证公式的后件的否定列出，注明为假设或前提。(2)按推理规则进行推理，但此时不能对假设以及演绎公式实施代入规则。(3)当推导出两个矛盾的结论时，就完成了该定理的证明。,反证法,定理(PR)(QR)(PQ),证明:PR 假设 QR 假设(3)P 假设(4)R(1)(3)分离(5)Q(2)(4
5、)拒取规则,即证得:PR,QR,P Q由推理定理,原公式得证,定理(PR)(QR)(PQ),另证(只使用两个前提假设):PR 假设 QR 假设(3)(PR)(RQ)(PQ)公理3(4)(RQ)(PQ)(1)(3)分离(5)(QR)(RQ)公理14(6)RQ(2)(5)分离(7)PQ(4)(6)分离,例1：求证(P(Q R)(PQ)R),证明:(1)P(Q R)假设(2)P Q 假设(3)P(2)化简(4)Q(2)化简(5)Q R(1)(3)分离(6)R(4)(5)分离,(4)R 在(3)中用R代入P有错吗?不能对(5)实施代入规则!,例1：求证(P(Q R)(PQ)R),证明(若不使用化简规则
6、)(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)分离,例2(p21)求证：(PP)P,证明：(1)PP 假设(2)P 假设，结论的否定(3)P(1)(2)分离 显然，(2)与(3)矛盾。由反证法，结论得证。,例(SQ)(PQ)S)P,解:(1)(SQ)(PQ)S 假设(2)SQ(1)化简(3)PQ(1)化简(4)S(1)化简(5)P 假设,结论的否定(置换)(6)Q(2)(4)分离(7)Q(3)(5)分离 显然，(6)与(7)矛盾。由反证法，公式得证。,例(
7、SQ)(PQ)S)P,解:(1)(SQ)(PQ)S 假设(2)SQ(1)化简(3)PQ(1)化简(4)S(1)化简(5)Q(2)(4)分离(7)P(3)(5)拒取规则,例(PQ)R)(P(QR),解:(1)(PQ)R 假设(2)P 假设(3)Q 假设(4)P(Q(PQ)公理10(5)Q(PQ)(2)(4)分离(6)PQ(3)(5)分离(7)R(1)(6)分离,例(PQ)(PR)(QS)(SR),解:(1)P 假设(2)Q 假设(3)PR 假设(4)QS 假设(5)R(1)(3)分离(6)S(2)(4)分离(7)SR(5)(6)合取,例 QQ心情谜语,现在是晚上十一点，天很暖。如果我考试通过了，
8、那么我很快乐。如果我快乐，那么阳光灿烂。解：设 P：我考试通过了，Q：我很快乐，R：阳光灿烂，S：天很暖。前提：PQ，QR，RS,例(续)QQ心情谜语,(1)PQ 前提 QR 前提 RS 前提 PR(1)(2)假言三段论(5)R(3)化简 P(4)(5)拒取式 所以有效结论是：我考试没通过。,例 甲是否盗窃了电脑？,公安人员审一件盗窃案。已知：(1)若甲盗窃了电脑，则作案时间不能发生在午夜前。(2)若乙证词正确，则在午夜时屋里灯光未灭。(3)若乙证词不正确，则作案时间发生在午夜前。(4)午夜时屋里灯光灭了。问：甲是否盗窃了电脑？,解 设 p：甲盗窃了电脑 r：作案时间发生在午夜前，s：乙证词正
9、确，t：午夜时屋里灯光灭了。前提：pr，st，sr，t,例(续)甲是否盗窃了电脑？,(1)pr(2)st sr t(5)s(2)(4)拒取式(6)r(3)(5)分离(7)p(1)(6)拒取式,因此可得结论：甲不是盗窃犯。,例 构造下面的假设推理证明,前提：pq,rq,rs 结论：ps pq 假设 rq 假设(3)rs 假设 p 附加假设 q(1)(4)析取三段论 r(2)(5)析取三段论 s(3)(6)分离,例 构造下面的假设推理证明,前提：pq,rq,rs 结论：pspq 假设 rq 假设(3)rs 假设p q(1)等值置换q r(2)等值置换p r(4)(5)传递三段论Ps(3)(6)传递
10、三段论,穷举法,若 A1，A2，Ak,B,A1，A2，Ak,B,则 A1，A2，Ak,B,例 写出对应下面推理的证明,解：记 p：今天是星期一 q：考英语 r：考数学 s：英语老师开会 前提：p(qr)(qr),sq,p,s 结论：r,如果今天是星期一,则要考英语或考数学。如果英语老师开会,则不考英语。今天是星期一，英语老师开会，所以考数学。,p(q r)(qr)假设sq 假设 p 假设 s 假设 r 额外假设(q r)(qr),(1)(3)分离(7)q(2)(4)分离(8)q r(6)穷举q(8)化简 qr(6)穷举 r(10)化简,显然，(7)(9)矛盾，并且(5)(11)矛盾。,p(qr
11、)假设sr 假设 p 假设 s 假设(5)r(2)(4)分离(6)qr(1)(3)分离(7)q(5)(6)析取三段论,如果将考英语或考数学翻译成 qr，则证明如下:,讨论,如果将“如果今天是星期一,则要考英语或考数学”翻译如下：p(qr)(qr)=p(qr)(qr)=p(qr)(qr)=(pqr)(pqr)=(p(qr)(p(qr)则有2个前提假设：p(qr)p(qr)前面的证明只用到第1个前提，所以证明仍然有效。,已知公理 A:(P Q)P B:(P Q)Q C:P(Q(P Q)及分离规则和代入规则，试用假设推理证明下面公式为本系统的定理:(PR)(QS)(PQ)(S R),例(10级期末试题,6分),证：（1）PR 假设（2）(QS)(PQ)假设（3）(QS)(PQ)(QS)公理（A）代入（4）(QS)(PQ)(PQ)公理（B）代入（5）QS（2）（3）分离（6）PQ（2）（4）分离（7）(PQ)P 公理（A）（8）(PQ)Q 公理（B）（9）P（6）（7）分离（10）Q（6）（8）分离（11）S（5）（10）分离（12）S(R(S R)公理（C）代入（13）R(S R)（11）（12）分离（14）R（1）（9）分离（15）S R（13）（14）分离,
