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

《离散数学第四章谓词演算的推理理论-假设推理系统.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章谓词演算的推理理论4.1谓词演算的永真推理系统4.2谓词演算的假设推理系统4.2.1假设推理系统的组成及证明方法4.2.2推理过程的推导过程4.3谓词演算的归结推理系统一、假设推理系统的组成(附加前提证明法)如果Γ，△A├△B，则Γ├△(AB)，也可表示为：如果△A1，△A2，…，△An，△A├△B，则△A1，△A2，…，△An├△(AB)。依次类推可得定理：├△(A1(A2(…(An(AB)))…)(2)存在推理定理如果有△A1，…，△An，△xP(x)，△P(e)├△Q，其中Q中不含有自由的e，且在推理过程

2、中不对假设中的自由变元和额外假设中的自由变元实施全规则和存在规则，则有：△A1，△A2，…，△An，△xP(x)├△Q去“存在量词”二、假设推理过程的证明方法(1)把待证公式的前件作为假设一一列出，假设中的全称量词可用全称量词消去规则消去，存在量词可引入额外假设删除，并在式子后注明它为额外假设。二、假设推理过程的证明方法(2)按永真的证明方法进行证明，但此时不能对假设实施代入。(3)待证公式的后件中若有全称量词，可用全0规则引入，存在量词可由公理21引入。全称量词消去规则规则成立的条件：（1）t是任意个体变项或常项。例考察∀x∃

3、yF（x，y）全称量词消去能不能得到下式:∃yF（y，y）✘存在量词消去规则规则成立的条件：（1）c是使A（c）为真的特定的个体常元。（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.2.1假设推理系统的组成

4、及证明方法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)由假设推理定理得：x(P(x)D(x))(P(a)D(a))例下面推理是否正确？设前提为∀x∃yF（x，y），（1）∀x∃yF（x，y）前提引入（2）∃yF（y，y）

5、全称量词消去解推理并不正确。如果给定解释I：个体域为实数集，F（x，y）：x＞y。则∀x∃yF（x，y）意为“对于每个实数x，均存在着比之更小的实数y”，这是一个真命题。而∃yF（y，y）意为“存在着比自己小的实数”，是假命题。之所以出现这样的错误,是因为∃yF（x，y）中有1个自由变元x,而∃yF（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）存在

6、量词引入解：推理并不正确。如果给定解释I：个体域为实数集，F(x,y)：x＞y。则x∃yF（x，y）为真，而∃yxF（x，y）意为“存在着最小实数”，是假命题，故知推理不正确。之所以出现这样的错误，是在第（3）步中，∃yF（t，y）非闭式（含有自由变元t)。例1(p44)求证：x(P(x)Q(x))(xP(x)xQ(x))解：(1)x(P(x)Q(x))假设(2)xP(x)假设(3)P(e)Q(e)额外假设(4)P(e)全称量词消去规则(5)Q(e)(3)(4)分离(6)Q(e)xQ(x)公理21+全称

7、量词消去规则(7)xQ(x)(6)(5)分离由存在推理定理得：x(P(x)Q(x))，xP(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(e)表示“e为庸医”；L(e1，e2)表示“e1喜欢e2”；则已知知识翻译为：(1)x(P(x)y(D(y)L(x，

8、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