离散数学 第二章 一阶逻辑等值式.ppt

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

1、2.3一阶逻辑等值式等值式基本等值式量词否定等值式量词辖域收缩与扩张等值式量词分配等值式前束范式1等值式与基本等值式基本等值式:命题逻辑中16组基本等值式的代换实例如，xF(x)yG(y)xF(x)yG(y)(xF(x)yG(y))xF(x)yG(y)等消去量词等值式设D={a1,a2,…,an}xA(x)A(a1)A(a2)…A(an)xA(x)A(a1)A(a2)…A(an)定义若AB为逻辑有效式，则称A与B是等值的，记作AB，并称AB为等值式.2基本等值式(续)量词辖域收缩与扩张等值式设A(x)是含x自由出现的公式，B中不含x

2、的出现关于全称量词的：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)关于存在量词的: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基本的等值式(续)量词否定等值式设A(x)是含x自由出现的公式xA(x)xA(x)xA(x)xA(x)量词分配等值式x(A(x)B(x))xA(x)xB(x)x(A(x)B(x))xA(x)xB(x)注意：对

3、无分配律，对无分配律4基本的等值式(续)例将下面命题用两种形式符号化(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(F(x)G(x))x(F(x)G(x))给出演算过程，并说明理由.5前束范式例如，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为一个一阶

4、逻辑公式,若A具有如下形式Q1x1Q2x2…QkxkB,则称A为前束范式,其中Qi(1ik)为或，B为不含量词的公式.6公式的前束范式定理（前束范式存在定理）一阶逻辑中的任何公式都存在与之等值的前束范式注意:公式的前束范式不惟一求公式的前束范式的方法:利用重要等值式、置换规则、换名规则、代替规则进行等值演算.7换名规则与代替规则换名规则:将量词辖域中出现的某个约束出现的个体变项及对应的指导变项，改成其他辖域中未曾出现过的个体变项符号，公式中其余部分不变，则所得公式与原来的公式等值.代替规则:对某自由出现的个体变项用与原公式中所有个体变项符号不同的符号去代替，则所得公式与原来的公式等值.

5、8公式的前束范式(续)例求下列公式的前束范式(1)x(M(x)F(x))解x(M(x)F(x))x(M(x)F(x))（量词否定等值式）x(M(x)F(x))两步结果都是前束范式，说明前束范式不惟一.9例(续)(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))(量词辖域扩张)两种形式是等值的10例(续)(3)x

6、F(x)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)))（为什么？）11例(续)或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)))解用换名规则,

7、也可用代替规则,这里用代替规则x(F(x,y)y(G(x,y)H(x,z)))x(F(x,u)y(G(x,y)H(x,z)))xy(F(x,u)G(x,y)H(x,z)))注意：x与y不能颠倒12