离散数学屈婉玲第五章PPT课件

.,1,主要内容一阶逻辑等值式与基本的等值式置换规则、换名规则、代替规则前束范式,第五章一阶逻辑等值演算,.,2,5.1一阶逻辑等值式与置换规则,定义5.1设A,B是两个谓词公式,如果AB是永真式,则称A与B等值,记作AB,并称AB是等值式基本等值式第一组命题逻辑中16组基本等值式的代换实例例如，xF(x)xF(x),xF(x)yG(y)xF(x)yG(y)等第二组(1)消去量词等值式设D=a1,a2,anxA(x)A(a1)A(a2)A(an)xA(x)A(a1)A(a2)A(an),.,3,基本等值式,(2)量词否定等值式xA(x)xA(x)xA(x)xA(x)(3)量词辖域收缩与扩张等值式.A(x)是含x自由出现的公式，B中不含x的自由出现关于全称量词的：x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x)BxA(x),.,4,基本等值式,关于存在量词的：x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x)BxA(x)(4)量词分配等值式x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)注意：对，对无分配律,.,5,置换规则、换名规则、代替规则,1.置换规则设(A)是含A的公式,那么,若AB,则(A)(B).2.换名规则设A为一公式，将A中某量词辖域中个体变项的所有约束出现及相应的指导变元换成该量词辖域中未曾出现过的个体变项符号，其余部分不变，设所得公式为A，则AA.3.代替规则设A为一公式，将A中某个个体变项的所有自由出现用A中未曾出现过的个体变项符号代替，其余部分不变，设所得公式为A，则AA.,.,6,实例,例1将下面命题用两种形式符号化,并证明两者等值:(1)没有不犯错误的人,解令F(x)：x是人，G(x)：x犯错误.x(F(x)G(x)或x(F(x)G(x),x(F(x)G(x)x(F(x)G(x)量词否定等值式x(F(x)G(x)置换x(F(x)G(x)置换,.,7,实例,(2)不是所有的人都爱看电影,解令F(x)：x是人，G(x)：爱看电影.x(F(x)G(x)或x(F(x)G(x),x(F(x)G(x)x(F(x)G(x)量词否定等值式x(F(x)G(x)置换x(F(x)G(x)置换,.,8,实例,例2将公式化成等值的不含既有约束出现、又有自由出现的个体变项:x(F(x,y,z)yG(x,y,z),解x(F(x,y,z)yG(x,y,z)x(F(x,y,z)tG(x,t,z)换名规则xt(F(x,y,z)G(x,t,z)辖域扩张等值式,或者x(F(x,y,z)yG(x,y,z)x(F(x,u,z)yG(x,y,z)代替规则xy(F(x,u,z)G(x,y,z)辖域扩张等值式,.,9,实例,例3设个体域D=a,b,c,消去下述公式中的量词:(1)xy(F(x)G(y),解xy(F(x)G(y)(y(F(a)G(y)(y(F(b)G(y)(y(F(c)G(y)(F(a)G(a)(F(a)G(b)(F(a)G(c)(F(b)G(a)(F(b)G(b)(F(b)G(c)(F(c)G(a)(F(c)G(b)(F(c)G(c),.,10,实例,解法二xy(F(x)G(y)x(F(x)yG(y)辖域收缩等值式x(F(x)G(a)G(b)G(c)(F(a)G(a)G(b)G(c)(F(b)G(a)G(b)G(c)(F(c)G(a)G(b)G(c),.,11,实例,(2)xyF(x,y),xyF(x,y)x(F(x,a)F(x,b)F(x,c)(F(a,a)F(a,b)F(a,c)(F(b,a)F(b,b)F(b,c)(F(c,a)F(c,b)F(c,c),.,12,5.2一阶逻辑前束范式,定义5.2设A为一阶逻辑公式，若A具有如下形式Q1x1Q2x2QkxkB则称A为前束范式，其中Qi(1ik)为或，B为不含量词的公式.例如，x(F(x)G(x)xy(F(x)(G(y)H(x,y)是前束范式而x(F(x)G(x)x(F(x)y(G(y)H(x,y)不是前束范式,.,13,前束范式存在定理,定理5.1（前束范式存在定理）一阶逻辑中的任何公式都存在与之等值的前束范式,例4求下列公式的前束范式(1)x(M(x)F(x),解x(M(x)F(x)x(M(x)F(x)（量词否定等值式）x(M(x)F(x)后两步结果都是前束范式，说明公式的前束范式不惟一.,.,14,求前束范式的实例,(2)xF(x)xG(x),解xF(x)xG(x)xF(x)xG(x)（量词否定等值式）x(F(x)G(x)（量词分配等值式）,或xF(x)xG(x)xF(x)xG(x)量词否定等值式xF(x)yG(y)换名规则xy(F(x)G(y)辖域收缩扩张规则,.,15,求前束范式的实例,(3)xF(x)y(G(x,y)H(y),或xF(x)y(G(z,y)H(y)代替规则xy(F(x)(G(z,y)H(y),解xF(x)y(G(x,y)H(y)zF(z)y(G(x,y)H(y)换名规则zy(F(z)(G(x,y)H(y)辖域收缩扩张规则,.,16,第五章习题课,主要内容一阶逻辑等值式基本等值式，置换规则、换名规则、代替规则前束范式,基本要求深刻理解并牢记一阶逻辑中的重要等值式,并能准确而熟练地应用它们熟练正确地使用置换规则、换名规则、代替规则熟练地求出给定公式的前束范式,.,17,练习1,1.给定解释I如下:(1)个体域D=2,3(2)(3)(4)求下述公式在I下的解释及其真值:xy(F(f(x)G(y,f(a),解xF(f(x)yG(y,f(a)F(f(2)F(f(3)(G(2,f(2)G(3,f(2)10(10)0,.,18,练习2,2.求下述公式的前束范式:xF(x)y(G(x,y)H(x,y),解使用换名规则,xF(x)y(G(x,y)H(x,y)zF(z)y(G(x,y)H(