一阶逻辑推理--离散数学.ppt

《一阶逻辑推理--离散数学.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、3.3、谓词演算的推理理论在谓词演算中，推理的形式结构仍为若是永真式，则称由前提逻辑的推出结论C，在此,C均为谓词公式。一、推理规则命题演算中的推理规则，可在谓词推理理论中应用。谓词逻辑中的基本重言蕴含式)()())()(()6()()())()(()5()()())()(()4())()(()()()3(xxBxxAxBxAxxxBxxAxBxAxxxBxxAxBxAxxBxAxxxBxxA"«"Þ«"$®$Þ®""®"Þ®"®"Þ"®$二、与量词有关的推理规则1.US(全称特定化规则)使用此规则时要注意：（1）y为任意不在A(x)中约束出现的个

2、体变元；（2）c为任意的个体常元。关于（1）的反例：对于，x,y的个体域为实数集R，是一真命题.若应用US得，则是错误的。正确的做法是换成使用此规则时应注意：（1）c是使A为真的特定个体常元；c不在A(x)或其前的推导中出现。（2）如果A(x)中有其他自由变元出现，且x是随其他自由变元变化的，那么不能使用此规则。2.ES（存在特定化规则）例如：对于，个体域为实数集。若使用ES规则，得到c=y,即在实数集中有一实数c等于任意实数y.结论显然不成立。关于（2）的反例：证明（1）前提（2）（1）；化简例指出下面推理的错误.（3）（1）；化简（4）（2）；

3、ES（5）（3）；ES（6）（4）（5）；合取引入（7）（6）；EG因此3.UG（全称一般化规则）使用此规则时注意:(1)y在A(y)中自由出现，且y取任何值时A均为真。（即y不能是某些特定的个体）见下例(2)x不在A(y)中约束出现例指出下面推理的错误.设D(x,y)表示“x可被y整除”,个体域为{5,7,10,11}.因为D(5，5)和D(10,5)为真，所以xD(x,5)为真.因为D(7，5)和D(11,5)为假，所以xD(x,5)为假.但有下面的推理过程：(1)xD(x,5)前提(2)D(z,5)(1);ES(3)xD(x,5)(2);UG

4、因此，xD(x,5)xD(x,5).4、EG（存在一般化规则）使用此规则时注意:(1)c是个体域中某个确定的个体。(2)代替c的x不能已在A(c)中出现。三、推理规则的应用例1证明苏格拉底的三段论。“凡人都是要死的，苏格拉底是人，所以苏格拉底是要死的。”解令M(x):x是人;D(x):x是要死的;c:苏格拉底。于是苏格拉底三段论可表示为：证明（1）M(c)前提（2）前提（3）（1）；US（4）D(c)(1),(3);假言推理例2证明（3）C(a)∧Q(a)（2）；ES证明（1）前提（2）前提（4）（1）；US（5）C(a)（3）；化简（6）W(a)

5、∧R(a)（4）,（5）；假言推理（7）Q(a)（3）；化简（8）R(a)（6）；化简（9）Q(a)∧R(a)（7）,（8）；合取引入（10）（9）；EG例3证明证明（1）附加前提（2）（1）；量词否定等值式（6）Q(c)（3）,（5）；析取三段论（7）（6）；EG（3）（2）；ES（4）前提(5)（4）；US例4证明（1）附加前提（2）（1）；德摩根证法一:(间接证明法)（3）（2）；化简（4）（2）；化简（5）（4）；量词否定等值式（6）（3）；量词否定等值式（7）（6）；ES（8）（5）；US（9）（7）（8）；合取（10）（9）；德摩根（1

6、1）前提（12）（11）；US（13）（10）（12）;合取证法二（1）附加前提（2）（1）；量词否定等值式（3）前提（4）（2）；ES（5）（3）；US（6）（4）（5）；析取三段论（7）（6）；EG（8）（1）（7）；CP（9）（8）；蕴含等值式，德摩根原题可转化为证明例5用构造推理过程的方法证明证明证明例6符号化下述命题,并推证其结论。“所有有理数是实数，某些有理数是整数，因此某些实数是整数。”解先将命题符号化令Q(x):x是有理数；R(x):x是实数;I(x);x是整数.证明