离散数学第二章命题演算的推理理论-假设推理系统.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)