《假设推理系统.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 结 论
2、,推理的有效性由永真公式： (P 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,二、假设推理过程,定义: 如果
3、能够作出一系列合式公式序列 A1，A2, A3, ，An， 它们满足下列性质： (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
4、 (AB) A1，A2，An-2 An-1 (An (AB) 依次类推可得定理： A1(A2(An(AB),(2) 反证律,如果 ，A B 且 ，A B 这里B是一个公式。 则有: A。,四、假设推理证明定理的方法,把待证公式的前件一一列出，注明为假设或前提。 按推理规则进行推理，但此时不能对假设以及演绎公式实施代入规则。 (3) 当推导出待证公式的后件时，就完成了该定理的证明。,附加前提推理证明方法,四、假设推理证明定理的方法,(1) 把待证公式的前件一一列出，把待证公式的后件的否定列出，注明为假设或前提。 (2) 按推理规则进行推理，但此时不能对假设以及演绎公式实施代入规则。 (3) 当推
5、导出两个矛盾的结论时，就完成了该定理的证明。,反证法,定理 (PR)(QR)(PQ),证明: PR 假设 QR 假设 (3) P 假设 (4) R (1)(3)分离 (5) Q (2)(4)拒取规则,即证得: 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)
6、 假设 (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),证明(若不使用化简规则) (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 假设，结论的
7、否定 (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)矛盾。由反证法，公式得证。,例 (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
8、)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心情谜语,现在是晚上十一点，天很暖。如果我考试通过了， 那么我很快乐。 如果我快乐， 那么阳光灿烂。 解： 设 P： 我考试通过了， Q： 我很快乐， R：
9、阳光灿烂， 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： 乙证词正确， t： 午夜时屋里
10、灯光灭了。 前提： 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 结论：ps pq 假设 rq 假设 (3) rs 假设 p q (1)等值置换 q r (2
11、)等值置换 p r (4)(5)传递三段论 Ps (3)(6)传递三段论,穷举法,若 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
12、r (6)穷举 q (8) 化简 qr (6)穷举 r (10)化简,显然，(7)(9) 矛盾，并且(5)(11)矛盾。,p (qr) 假设 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个前提，所以证明仍然有效。,已知
13、公理 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）分离,