离散数学第四章谓词演算的推理理论-假设推理系统.ppt

《离散数学第四章谓词演算的推理理论-假设推理系统.ppt》由会员分享，可在线阅读，更多相关《离散数学第四章谓词演算的推理理论-假设推理系统.ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章 谓词演算的推理理论4.1 谓词演算的永真推理系统谓词演算的永真推理系统 4.2谓词演算的假设推理系统谓词演算的假设推理系统 4.2.1 假设推理系统的组成及证明方法假设推理系统的组成及证明方法 4.2.2 推理过程的推导过程推理过程的推导过程4.3谓词演算的归结推理系统谓词演算的归结推理系统一、假设推理系统的组成一、假设推理系统的组成(1)(附加前提证明法附加前提证明法)如果如果，A B，则则(AB)，也可表示为：也可表示为：如果如果A1，A2，An，A B，则则A1，A2，An(AB)。依次类推可得定理：依次类推可得定理：(A1(A2(An(AB)(2)存在推理定理存在推理定理如果有

2、如果有 A1，An，xP(x)，P(e)Q，其中其中Q中不含有自由的中不含有自由的e，且在推理过程中不对假设中的自由，且在推理过程中不对假设中的自由变元和额外假设中的自由变元实施全规则和存在规则，则有：变元和额外假设中的自由变元实施全规则和存在规则，则有：A1，A2，An，xP(x)Q去“存在量词”二、假设推理过程的证明方法(1)把待证公式的前件作为假设一一列出，假把待证公式的前件作为假设一一列出，假设中的全称量词设中的全称量词 可用全称量词消去规则可用全称量词消去规则消去，存在量词可引入额外假设删除，并消去，存在量词可引入额外假设删除，并在式子后注明它为额外假设。在式子后注明它为额外假设。二

3、、假设推理过程的证明方法(2)按永真的证明方法进行证明，但此时不能对按永真的证明方法进行证明，但此时不能对假设实施代入。假设实施代入。(3)待证公式的后件中若有全称量词，可用全待证公式的后件中若有全称量词，可用全0规则引入，存在量词可由公理规则引入，存在量词可由公理21引入。引入。全称量词消去规则规则成立的条件：规则成立的条件：（1）t是任意个体变项或常项。是任意个体变项或常项。例例 考察考察 x yF（x，y）全称量词消去能不能得）全称量词消去能不能得到下式到下式:y F（y，y）存在量词消去规则规则成立的条件：规则成立的条件：（1）c是使是使A（c）为真的特定的个体常元。）为真的特定的个体

4、常元。（2）xA（x）是）是闭式闭式。例例 考察考察 yF（x，y）存在量词消去能不能得到下）存在量词消去能不能得到下式式:F（x，c）全称量词引入规则 规则成立的条件：规则成立的条件：（1）A（t）在在任任何何解解释释I及及I中中对对t的的任任何何赋赋值下均为真。值下均为真。（2）x不在不在A（t）中约束出现。）中约束出现。存在量词引入规则 规则成立的条件：规则成立的条件：（1）c是特定的个体常元。是特定的个体常元。（2）x不在不在A（c）中出现。）中出现。第四章 谓词演算的推理理论4.1 谓词演算的永真推理系统谓词演算的永真推理系统 4.2谓词演算的假设推理系统谓词演算的假设推理系统 4.

5、2.1 假设推理系统的组成及证明方法假设推理系统的组成及证明方法 4.2.2 推理过程的推导过程推理过程的推导过程4.3谓词演算的归结推理系统谓词演算的归结推理系统例例 求证苏格拉底三段论求证苏格拉底三段论凡人要死，苏格拉底是人，所以苏格拉底要死凡人要死，苏格拉底是人，所以苏格拉底要死。解：解：P(e):e是人是人 D(e):e要死要死a:苏格拉底苏格拉底(1)x(P(x)D(x)假设假设(2)P(a)假设假设(3)P(a)D(a)全称量词消去规则全称量词消去规则(4)D(a)(2)(3)分离分离由存在推理定理得：由存在推理定理得：x(P(x)Q(x)，P(a)Q(a)由假设推理定理得：由假设

6、推理定理得：x(P(x)D(x)(P(a)D(a)例例 下面推理是否正确？下面推理是否正确？设前提为设前提为 x yF（x，y），），（1）x yF（x，y）前提引入前提引入 （2）y F（y，y）全称量词消去全称量词消去解解 推理并不正确。推理并不正确。如果给定解释如果给定解释I：个体域为实数集，：个体域为实数集，F（x，y）：）：xy。则则 x yF（x，y）意为）意为“对于每个实数对于每个实数x，均存在着，均存在着比之更小的实数比之更小的实数y”，这是一个真命题。，这是一个真命题。而而 yF（y，y）意为）意为“存在着比自己小的实数存在着比自己小的实数”，是，是假命题。假命题。之所以出现

7、这样的错误之所以出现这样的错误,是因为是因为 yF（x，y）中有中有1个自个自由变元由变元x,而而 y F（y，y）中无自由变元。）中无自由变元。例例 下面推理是否正确？面推理是否正确？设前提为设前提为x yF（x，y），），（1）x yF（x，y）前提引入前提引入 （2）yF（t，y）全称量词消去全称量词消去 （3）F（t，c）存在量词消去存在量词消去 （4）xF（x，c）全称量词引入全称量词引入 （5）y xF（x，y）存在量词引入存在量词引入 解：解：推理并不正确。推理并不正确。如果给定解释如果给定解释I：个体域为实数集，：个体域为实数集，F(x,y)：xy。则则 x yF（x，y）为真

8、，）为真，而而 y xF（x，y）意为）意为“存在着最小实数存在着最小实数”，是假命题，是假命题，故知推理不正确。故知推理不正确。之所以出现这样的错误，是在第（之所以出现这样的错误，是在第（3）步中，）步中，yF（t，y）非闭式（含有自由变元）非闭式（含有自由变元t)。例例1(p44)求证：求证：x(P(x)x(P(x)Q(x)Q(x)(xP(x)xP(x)xQ(x)xQ(x)解：解：(1)x(P(x)Q(x)假设假设(2)x P(x)假设假设(3)P(e)Q(e)额外假设额外假设(4)P(e)全称量词消去规则全称量词消去规则(5)Q(e)(3)(4)分离分离(6)Q(e)x Q(x)公理公理

9、21+全称量词消去规则全称量词消去规则(7)x Q(x)(6)(5)分离分离由存在推理定理得：由存在推理定理得：x(P(x)Q(x)，x P(x)xQ(x)由假设推理定理得：由假设推理定理得：x(P(x)Q(x)(xP(x)xQ(x)例例2(p44)已知知识：已知知识：(1)有些病人喜欢所有的医生；有些病人喜欢所有的医生；(2)所有的病人均不喜欢庸医；所有的病人均不喜欢庸医；试证明结论：所有的医生均不是庸医。试证明结论：所有的医生均不是庸医。例例2(p44)证明：先把知识翻译为符号公式证明：先把知识翻译为符号公式,令令P(e)表示表示“e为病人为病人”；D(e)表示表示“e为医生为医生”；Q(

10、e)表示表示“e为庸医为庸医”；L(e1，e2)表示表示“e1喜欢喜欢e2”；则已知知识翻译为：则已知知识翻译为：(1)x(P(x)y(D(y)L(x，y)(2)x(P(x)y(Q(y)L(x，y)结论翻译为：结论翻译为：x(D(x)Q(x)(1)x(P(x)y(D(y)L(x，y)假设假设(2)x(P(x)y(Q(y)L(x，y)假设假设(3)P(a)y(D(y)L(a，y)额外假设额外假设(4)(P(a)y(D(y)L(a，y)P(a)公理公理8(5)(P(a)y(D(y)L(a，y)y(D(y)L(a,y)公理公理9(6)P(a)(4)(3)分离分离(7)y(D(y)L(a，y)(5)(

11、3)分离分离(8)P(a)y(Q(y)L(a，y)全称量词消去规则全称量词消去规则(2)(9)y(Q(y)L(a，y)(8)(6)分离分离先将（1）、（2）化简去掉（7）、（9）中全称量词(10)D(b)L(a，b)全称量词消去规则全称量词消去规则(7)(11)Q(b)L(a，b)全称量词消去规则全称量词消去规则(9)(12)(Q(b)L(a，b)(L(a，b)Q(b)公理公理14(13)L(a，b)Q(b)(12)(11)分离分离(14)(D(b)L(a,b)(L(a,b)Q(b)(D(b)Q(b)公理公理3(15)(L(a，b)Q(b)(D(b)Q(b)(14)(10)分离分离(16)D(

12、b)Q(b)(15)(13)分离分离(17)x(D(x)Q(x)全全0规则规则(16)最后，把公式翻译为日常语句得结论：所有的医生均不是庸医。最后，把公式翻译为日常语句得结论：所有的医生均不是庸医。例 所有羊都吃草所有羊都吃草,所有死羊都不吃草所有死羊都不吃草.所以所以,所有死羊都不是羊所有死羊都不是羊.解解:推理如下推理如下:(1)x(羊羊(x)吃草吃草(x)(2)x(死羊死羊(x)吃草吃草(x)(3)羊羊(x)吃草吃草(x)(4)死羊死羊(x)吃草吃草(x)(5)(羊羊(x)吃草吃草(x)(吃草吃草(x)羊羊(x)定理定理 (6)吃草吃草(x)羊羊(x)(7)(死羊死羊(x)吃草吃草(x)传递公理传递公理 (吃草吃草(x)羊羊(x)(死羊死羊(x)羊羊(x)(8)(吃草吃草(x)羊羊(x)(死羊死羊(x)羊羊(x)(9)死羊死羊(x)羊羊(x)(10)x(死羊死羊(x)羊羊(x)第四章 谓词演算的推理理论4.1 谓词演算的永真推理系统谓词演算的永真推理系统 4.2谓词演算的假设推理系统谓词演算的假设推理系统 4.2.1 假设推理系统的组成及证明方法假设推理系统的组成及证明方法 4.2.2 推理过程的推导过程推理过程的推导过程4.3谓词演算的归结推理系统谓词演算的归结推理系统