离散数学命题演算的推理理论假设推理系统公开课一等奖优质课大赛微课获奖课件.pptx

第二章第二章 命题演算推理理论命题演算推理理论2.12.1 命题演算公理系统命题演算公理系统 2.2 2.2 命题演算假设推理系统命题演算假设推理系统 2.2.1 2.2.1 假设推理系统构成假设推理系统构成 2.2.2 2.2.2 假设推理系统推理过程假设推理系统推理过程2.3 2.3 命题演算归结推理法命题演算归结推理法第1页第1页22 命题演算假设推理系统命题演算假设推理系统 假设推理系统：假设推理系统：由于它推理形式类似于日常生活由于它推理形式类似于日常生活中推理形式，中推理形式，也称为也称为自然推理系统自然推理系统。第2页第2页2.2.1 假设推理系统构成假设推理系统构成一、扩充推理规则一、扩充推理规则二、假设推理过程二、假设推理过程三、推理定理三、推理定理四、假设推理证实定理办法四、假设推理证实定理办法第3页第3页一、扩充推理规则一、扩充推理规则(1)分离规则推广分离规则推广 A1，A2，AnA(2)必定前提律必定前提律 A1，A2，A3，An Ai 第4页第4页分离规则推广分离规则推广设有下列推理规则设有下列推理规则 R：若：若A1，A2，An，能够推出能够推出A，即即 R：A1，A2，An A，则称则称A是由是由 A1，A2，An实行规则实行规则R而得。而得。设设=A1，A2，An，则上述规则，则上述规则R能够记为能够记为 A 其中其中为形式前提，为形式前提，A为形式结论。为形式结论。第5页第5页必定前提律必定前提律 A1，A2，A3，An Ai (i=1，2，n)，即前提中任何命题均可作为结论。即前提中任何命题均可作为结论。第6页第6页二、假设推理过程定义定义:假如能够作出一系列合式公式序列假如能够作出一系列合式公式序列 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第7页第7页三、推理定理(1)(附加前提证实法附加前提证实法)假如假如，AB，则，则 AB 要证要证 (AB)，即要证即要证，A B第8页第8页附加前提证实法附加前提证实法 假如假如 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)第9页第9页(2)归谬法归谬法假如假如 ，A B 且且 ，A B，则则 A。此定理称为此定理称为反证律反证律。这里。这里B是一个公式。是一个公式。其它公理、规则同前节。其它公理、规则同前节。第10页第10页四、假设推理证实定理办法(1)把待证公式前件一一列出，作为假设把待证公式前件一一列出，作为假设(或把或把待证公式后件否认作为假设待证公式后件否认作为假设)，并在式子后，并在式子后注明为假设。注明为假设。(2)按上述简介推理办法进行推理，但此时按上述简介推理办法进行推理，但此时不能不能对假设实行代入规则对假设实行代入规则（由于假设不是永真（由于假设不是永真公式）。公式）。(3)当推导出待证公式后件时当推导出待证公式后件时(或推导出矛盾时或推导出矛盾时)就说证实了该定理。就说证实了该定理。第11页第11页第二章第二章 命题演算推理理论命题演算推理理论2.12.1 命题演算公理系统命题演算公理系统 2.2 2.2 命题演算假设推理系统命题演算假设推理系统 2.2.1 2.2.1 假设推理系统构成假设推理系统构成 2.2.2 2.2.2 假设推理系统推理过程假设推理系统推理过程2.3 2.3 命题演算归结推理法命题演算归结推理法第12页第12页例例1：求证：求证(P(Q R)(P Q)R)证实证实:(1)P(Q R)假设假设 (2)P Q 假设假设 (3)(P Q)P 公理公理8 (4)(P Q)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)(P Q)R)(6)R 在(5)中用R代入P有错吗?不能对(5)实行代入规则!第13页第13页例2(p21)求证：求证：(PP)P证实：证实：(1)PP 假设假设 (2)P 假设，结论否认假设，结论否认 (3)P (1)(2)分离分离 显然，显然，(2)与与(3)表明推出矛盾表明推出矛盾 (PP),P P (PP),P P 由反证法由反证法 得：得：(PP)P 由推理定理得：由推理定理得：(PP)P第14页第14页例 (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第15页第15页例例 (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)第16页第16页例例 (P Q)R)(P(QR)解解:(1)P QR 假设假设 (2)P 假设假设 (3)Q 假设假设(4)P(Q(P Q)公理公理10(5)Q(P Q)(2)(4)分离分离(6)P Q (3)(5)分离分离 (7)R (1)(6)分离分离即证得即证得 (P Q)R,P,Q R亦即证得亦即证得 (P Q)R)(P(QR)第17页第17页例例 (P Q)(PR)(QS)(S R)解解:(1)(P Q)(PR)(QS)假设假设 (2)P Q P 公理公理8 (3)P QQ 公理公理9 (4)(P Q)(PR)(QS)(P Q)代入代入(2)(5)(P Q)(PR)(QS)(PR)(QS)代入代入(3)(6)P Q (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(S R)公理公理10 (17)R(S R)(15)(16)分离分离 (18)S R (14)(17)分离分离第18页第18页例例 QQ心情谜语心情谜语 现现在在是是晚晚上上十十一一点点，天天很很暖暖。假假如如我我考考试试通通过过了了，那那么么我我很很高高兴兴。假假如如我我高高兴兴，那那么么阳阳光灿烂。光灿烂。解解：设设 P：我考试通过了，我考试通过了，Q：我很高兴，我很高兴，R：阳光灿烂，阳光灿烂，S：天很暖。天很暖。前提：前提：PQ，QR，R S第19页第19页例例(续续)QQ心情谜语心情谜语(1)PQ 前提引入前提引入(2)QR 前提引入前提引入(3)(PQ)(QR)(PR)公理公理3(4)(QR)(PR)(1)(3)分离分离(5)PR (2)(4)分离分离(6)R S 前提引入前提引入(7)P QP 公理公理8(8)R SR (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)分离分离 因此有效结论是：因此有效结论是：我考试没通过我考试没通过。第20页第20页例例 甲是否盗窃了电脑？甲是否盗窃了电脑？公安人员审一件盗窃案。公安人员审一件盗窃案。已知：已知：(1)若甲盗窃了电脑，若甲盗窃了电脑，则作案时间不能发生在半夜前。则作案时间不能发生在半夜前。(2)若乙证词正确，若乙证词正确，则在半夜时屋里灯光未灭。则在半夜时屋里灯光未灭。(3)若乙证词不正确，若乙证词不正确，则作案时间发生在半夜前。则作案时间发生在半夜前。(4)半夜时屋里灯光灭了。半夜时屋里灯光灭了。问：甲是否盗窃了电脑？问：甲是否盗窃了电脑？解解 设设 p：甲盗窃了电脑甲盗窃了电脑 r：作案时间发生在半夜前，作案时间发生在半夜前，s：乙证词正确，乙证词正确，t：半夜时屋里灯光灭了。半夜时屋里灯光灭了。前提：前提：p r，s t，sr，t第21页第21页例(续)甲是否盗窃了电脑？甲是否盗窃了电脑？(1)p r(2)s t(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)分离分离因此可得结论：因此可得结论：甲不是盗窃犯。甲不是盗窃犯。第22页第22页例例 谁是盗窃犯？谁是盗窃犯？公安人员审一件盗窃案。公安人员审一件盗窃案。已知：已知：(1)若甲盗窃了电脑，若甲盗窃了电脑，则作案时间不能发生在半夜前。则作案时间不能发生在半夜前。(2)若乙证词正确，若乙证词正确，则在半夜时屋里灯光未灭。则在半夜时屋里灯光未灭。(3)若乙证词不正确，若乙证词不正确，则作案时间发生在半夜前。则作案时间发生在半夜前。(4)半夜时屋里灯光灭了。半夜时屋里灯光灭了。问：谁是盗窃犯？问：谁是盗窃犯？解解 设设 p：甲盗窃了电脑甲盗窃了电脑 r：作案时间发生在半夜前，作案时间发生在半夜前，s：乙证词正确，乙证词正确，t：半夜时屋里灯光灭了。半夜时屋里灯光灭了。q：乙盗窃了电脑乙盗窃了电脑 前提：前提：p r，s t，sr，t，p q第23页第23页例(续)谁是盗窃犯？谁是盗窃犯？(1)p q(2)p r(3)s t(4)sr(5)t因此可得结论：因此可得结论：乙是盗窃犯。乙是盗窃犯。(6)(PQ)(QP)公理公理14(7)(st)(ts)代入代入(6)(8)ts (3)(7)分离分离(9)s (5)(8)分离分离(10)r (4)(9)分离分离(11)(pr)(rp)代入代入(6)(12)rp (2)(11)分离分离(13)p (10)(12)分离分离(14)(A B)(AB)析取三段论析取三段论(15)(p q)(pq)代入代入(14)(16)p q (1)(15)分离分离(17)q (13)(16)分离分离第24页第24页第二章第二章 命题演算推理理论命题演算推理理论2.12.1 命题演算公理系统命题演算公理系统 2.2 2.2 命题演算假设推理系统命题演算假设推理系统 2.2.1 2.2.1 假设推理系统构成假设推理系统构成 2.2.2 2.2.2 假设推理系统推理过程假设推理系统推理过程 2.3 2.3 命题演算归结推理法命题演算归结推理法第25页第25页