离散数学-2-5谓词演算的等价式与蕴含式

《离散数学-2-5谓词演算的等价式与蕴含式》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章谓词逻辑2-5谓词演算的等价式与蕴含式授课人：李朔Email:chn.nj.ls@gmail.com1一、基本概念谓词公式中可包含有命题变元和客体变元，当命题变元用确定的命题取代，客体变元用确定的客体所取代时，就称作对公式赋值。一个谓词公式经过赋值后，就成为真值确定的命题（T或F）定义2-5.1给定任何两个谓词公式wffA和wffB，设它们有共同的个体域E。若对A和B的任意一组变元进行赋值，所得命题的真值相同，则称谓词公式A和B在E上是等价的。记为AB。2一、基本概念定义2-5.2任意给定谓词公式wffA，其个体域为E。若对A的任意变元

2、赋值，wffA都为真，则称该wffA在E上是有效的（或永真的）。定义2-5.3对于一个谓词公式wffA，如果在所有赋值下，该公式的真值都为假，则称该wffA为不可满足的。定义2-5.4对于一个谓词公式wffA，如果至少在一种赋值下为真，则称该wffA为可满足的。3二．命题公式的推广在命题逻辑中，重言式的同一分量出现的每一处都用同一合式公式置换，其结果仍是重言式类似于我们学习过的命题逻辑中的等价式与蕴含式，在谓词逻辑中有了等价和永真的概念，同样有谓词演算的一些等价式与蕴含式。命题演算中的等价公式表和蕴涵式表都可以推广到谓词演算中。当谓词演算中的公

3、式代替命题演算中永真公式的变元时，所得的谓词公式即为有效公式。故命题演算中的等价公式和蕴含式表都可推广到谓词演算中使用。4二．命题公式的推广例如：(x)(P(x)Q(x))(x)(P(x)Q(X))(x)P(x)(y)(R(x,y))((x)P(x)(y)(R(x,y)))(y)(x)(H(x,y)H(x,y))F5三．量词与联结词之间的关系例1设P(x)表示x喜欢梦八队，则P(x)表示x不喜欢梦八队。(个体域限定为人)（1）不是所有人都喜欢梦八队：(x)P(x)（2）存在一些人不喜欢梦八队：(

4、x)P(x)（3）不会有人喜欢梦八队：(x)P(x)（4）所有人都不喜欢梦八队：(x)P(x)可以看出命题(1)(2)意义完全相同，(3)(4)意义也完全相同。即有1.(x)P(x)(x)P(x)2.(x)P(x)(x)P(x)6三．量词与联结词之间的关系式1与式2反映了量词与联结词之间的关系，是我们可以得到的公式（量词的转化律）这里的约定：出现在量词之前的否定，不是否定该量词，而是否定被量化了的整个命题。上述公式在有限论域上的证明：设个体域中的客体变元为a1,a2,…,an，则1.(x)A(x)(A

5、(a1)A(a2)…A(an))A(a1)A(a2)…A(an))(x)A(x)2.(x)A(x)(A(a1)A(a2)…A(an))A(a1)A(a2)…A(an))(x)A(x)7三．量词与联结词之间的关系量词转化律也能推广到无穷个体域结论：当将量词前面的联结词移到量词的后面去时，存在量词改为全称量词，全称量词改为存在量词；反之，如果将量词后面的联结词移到量词的前面去时，也要做相应的改变。8四．量词作用域的扩张与收缩量词的作用域中常有合取项或析取项，如果其中一个为命题（即零元

6、谓词），则可将该命题移至量词作用域外。如1.(x)(A(x)B)(x)A(x)B2.(x)(A(x)B)(x)A(x)B3.(x)(A(x)B)(x)A(x)B4.(x)(A(x)B)(x)A(x)B因为B中不出现约束变元x,所以它属于或不属于量词作用域均有相同意义。9四．量词作用域的扩张与收缩从1-4式还可推得如下几个式子：5.((x)A(x)B))(x)(A(x)B)6.((x)A(x)B))(x)(A(x)B)7.(B(x)A(x))(x)(BA(x))8.(B(x

7、)A(x))(x)(BA(x))例2证明5式P68当谓词变元与量词的指导变元不同时，亦能有类似于上述的公式。10五、量词与命题联结词之间的一些等价关系量词与命题联结词存在不同的结合情况例学院里所有学生既懂理论也懂应用。(A(x),B(x))学院里所有学生懂理论且所有学生懂应用。上述语句意义相同。故有：（个体域为学院全体学生）(x)(A(x)B(x))(x)A(x)(x)B(x)由上式可以有：(x)(A(x)B(x))(x)(A(x))(x)(B(x))故有(x)(A(x)B(x))((x)A(x

8、)(x)B(x))即有(x)(A(x)B(x))(x)A(x)(x)B(x)11六、量词与命题联结词之间的一些蕴涵关系量词与命题与命题