最新5(等值式和前束范式以与推理理论)教学讲义ppt课件.ppt

《最新5(等值式和前束范式以与推理理论)教学讲义ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5(等值式和前束范式以与推理理论)二、基本等值式第一组命题逻辑中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)…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

2、)对于任意的解释Ｉ，设其个体域为Ｄ。若xA(x)在解释Ｉ下为真，由否定律可知，xA(x)为假，根据全称量词的定义，存在x0D,使A(x０)为假，从而A(x０)为真，所以解释Ｉ也使xA(x)为真。三、量词否定等值式4个公式的叙述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(x)和G(x)分别代入A(x)和B

3、(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))给出演算过程，并说明理由.七、前束范式例如，xy(F(x)

4、(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）求公式的前束范式的方法:利用重要等值式、置换规则、换名规则、代替规则进行等值演算.换名规则与代替规则换名规则:将量词辖域中出现的某个约束出现的

5、个体变项及对应的指导变项，改成另一个辖域中未曾出现过的个体变项符号，公式中其余部分不变，则所得公式与原来的公式等值.代替规则:对某自由出现的个体变项用与原公式中所有个体变项符号不同的符号去代替，则所得公式与原来的公式等值.换名规则与代替规则例子分别用换名规则和代替规则对下列公式改名: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(z,y))公式的前束范式(续)例求下列公

6、式的前束范式(1)x(M(x)F(x))解x(M(x)F(x))x(M(x)F(x))（量词否定等值式）x(M(x)F(x))两步结果都是前束范式，说明前束范式不惟一.例(续)(2)xF(x)xG(x)解xF(x)xG(x)xF(x)xG(x)（量词否定等值式）x(F(x)G(x))（量词分配等值式）另有一种形式xF(x)xG(x)xF(x)xG(x)xF(x)yG(y)(换名规则)xy(F(x)G(y))(量词辖域扩张)两种形式是等值的例(续)(3)xF(x)

7、xG(x)解xF(x)xG(x)xF(x)xG(x)x(F(x)G(x))（为什么？）或xy(F(x)G(y))（为什么？）(4)xF(x)y(G(x,y)H(y))解xF(x)y(G(x,y)H(y))zF(z)y(G(x,y)H(y))（换名规则）zy(F(z)(G(x,y)H(y)))（为什么？）例(续)或xF(x)y(G(z,y)H(y))（代替规则）xy(F(x)(G(z,y)H(y)))(5)x(F(x,y)y(G(x,y)H(x,z)

8、))解用换