5(等值式和前束范式以及推理理论).ppt

《5(等值式和前束范式以及推理理论).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、等值式定义1若AB为逻辑有效式，则称A与B是等值的，记作AB，并称AB为等值式.定义2若谓词公式A和B对任意一个解释都取相同的真值，则称A与B是等值的，记作AB，并称AB为等值式.5.1一阶逻辑等值式与置换规则二、基本等值式第一组命题逻辑中16组基本等值式的代换实例由代换实例可知,命题逻辑中的等值式可以得到一类谓词逻辑中的等值式.例如xF(x)yG(y)xF(x)yG(y)(xF(x)yG(y))xF(x)yG(y)等第二组1、消去量词等值式设D={a1,a2,…,an}xA(x)A(a1)A(a2)…

2、A(an)xA(x)A(a1)A(a2)…A(an)2、量词否定等值式设A(x)是含x自由出现的公式，(1)xA(x)xA(x)(2)xA(x)xA(x)证:(1)对于任意的解释Ｉ，设其个体域为Ｄ。若xA(x)在解释Ｉ下为真，由否定律可知，xA(x)为假，根据全称量词的定义，存在x0D,使A(x０)为假，从而A(x０)为真，所以解释Ｉ也使xA(x)为真。三、量词否定等值式4个公式的叙述若xA(x)在解释Ｉ下为假，由否定律可知，xA(x)为真，根据全称量词的定义，对任意xD,使A(x)为真，亦即对任意xD，A

3、(x)为假，所以解释Ｉ也使xA(x)为假。(2)可类似于(1)证明之，也可以利用(1)的结果证明。（练习题）设A(x)是含x自由出现的公式，(1)xA(x)xA(x)(2)xA(x)xA(x)令D是全班所有同学组成的集合,A(x):x今天来上课,则“并非每位同学今天都来上课”逻辑等价于“有同学今天没有来上课”,“并非有同学今天来上课”逻辑等价于“每位同学今天都没有来上课”。量词否定等值式之举例说明：设A(x)是含x自由出现的公式，B中不含x的出现关于全称量词的：x(A(x)B)xA(x)Bx(A(x)B)xA(x)B

4、x(A(x)B)xA(x)Bx(BA(x))BxA(x)关于存在量词的:x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x))BxA(x)3、量词辖域收缩与扩张等值式.4、量词分配等值式x(A(x)B(x))xA(x)xB(x)x(A(x)B(x))xA(x)xB(x)注意：对无分配律，对无分配律例如x(A(x)B(x))xA(x)xB(x)x(A(x)B(x))xA(x)xB(x)证:取具体谓词公式F(

5、x)和G(x)分别代入A(x)和B(x)使得x(A(x)B(x))↔xA(x)xB(x)不是逻辑有效式即可.5、量词交换等值式xyA(x,y)yxA(x,y);xyA(x,y)yxA(x,y).例将下面命题用两种形式符号化(1)没有不犯错误的人(2)不是所有的人都爱看电影解(1)令F(x)：x是人，G(x)：x犯错误.x(F(x)G(x))x(F(x)G(x))请给出演算过程，并说明理由.(2)令F(x)：x是人，G(x)：x爱看电影.x(F(x)G(x))x(F(x)G(x))给出演算过程，并说明理由.

6、七、前束范式例如，xy(F(x)(G(y)H(x,y)))x(F(x)G(x))是前束范式,而x(F(x)y(G(y)H(x,y)))x(F(x)G(x))不是前束范式，定义设A为一个谓词公式,若A具有如下形式Q1x1Q2x2…QkxkB,则称A为前束范式,其中Qi(1ik)为或，B为不含量词的公式.公式的前束范式定理（前束范式存在定理）：谓词逻辑中的任何公式都存在与之等值的前束范式。注意:（1）公式的前束范式不惟一.（2）求公式的前束范式的方法:利用重要等值式、置换规则、换名规则、代替规则进行等值演算.换名规则与代替规则换名

7、规则:将量词辖域中出现的某个约束出现的个体变项及对应的指导变项，改成另一个辖域中未曾出现过的个体变项符号，公式中其余部分不变，则所得公式与原来的公式等值.代替规则:对某自由出现的个体变项用与原公式中所有个体变项符号不同的符号去代替，则所得公式与原来的公式等值.换名规则与代替规则例子分别用换名规则和代替规则对下列公式改名:x(F(x)G(x))H(x,y))解:(1)用换名规则:由于x既是约束变项,又是自由变项,故将约束变项x改为z,得z(F(z)G(z))H(x,y))(2)用代替规则:将公式中的自由变项x用z代替,得x(F(x)G(x))H(

8、z,y))公式的前束范式