1.7谓词演算的永真公式

1.7谓词演算的永真公式,1.7.1基本定义1.7.2基本永真公式1.7.3几个规则代入规则、置换规则、改名规则,2,1.7.1基本定义,定义1.7-1两个任意谓词公式A和B，E是它们共有的论述域，若（1）对公式A和B中的谓词变元（包括命题变元）指派以任一在E上有定义的确定的谓词。（2）对谓词命名式(如，P(x)中的个体变元，指派以E中的任一确定的个体。所得的命题具有同样的真值，则称公式A和B遍及E等价，记为在E上AB,3,例如：公式x(F(x)G(x),个体域：全总个体域，F(x)：x是人G(x)：x是黄种人，假命题个体域：实数集合F(x)：x10,G(x)：x0,真命题,4,定义1.7-2如果两个谓词公式A和B在任意论述域上都等价，则称A和B等价，记为AB,5,谓词公式的类型,定义1.7-3给定任一谓词公式A，如果在论述域E上，对公式A中的谓词和个体变元进行定义1.7-1中两种指派，所得命题（1）都真，则称A在E上有效，或在E上永真（2）至少一个是真，称A在E上可满足（3）都假，则称A在E上永假，或在E上不可满足,6,定义1.7-4给定任一谓词公式A，如果在任意论述域上，对上述两种指派，（1）A永真，称A永真或有效（2）A至少在一个域上可满足，称A可满足。（3）A永假，称A永假或不可满足。,7,例如：设P(x)仅可解释为（1）A(x)：x是质数（2）B(x)：x是合数论述域是3，4，判定谓词公式P(x)xP(x)是否永真。真值表如表所示，所以其是非永真式。,1.7.2基本永真式,第一组命题逻辑中基本等值式的代换实例,例如：xF(x)xF(x)xy(F(x,y)G(x,y)xy(F(x,y)G(x,y)xF(x)yG(y)xF(x)yG(y)x(F(x)G(y)zH(z)x(F(x)G(y)zH(z)(xF(x)yG(y)xF(x)yG(y),9,第二组含有量词的谓词演算的基本永真式（1）xAA，xAA，其中A是不含自由变元x的谓词公式。（2）xP(x)P(y)或xP(x)P(x)P(y)xP(x)或P(x)xP(x)xP(x)xP(x),基本等值式(续),10,(3)量词否定等值式设A(x)是含个体变项x自由出现的公式，则有（1）xA(x)xA(x)（2）xA(x)xA(x),基本永真式(续),注1.直观解释P(x):x今天来校上课.xP(x):不是所有的人今天都来校上课.xP(x):有人今天没有来校上课.注2.可以在有限个体域上证明思考题,（4）量词辖域收缩与扩张等值式设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),关于存在量词的:x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x)BxA(x),基本永真式(续),实例,例1证明xA(x)Bx(A(x)B),证明xA(x)BxA(x)BxA(x)Bx(A(x)B)x(A(x)B),注.x(P(x)Q(y)xP(x)Q(y)x(yP(x,y)Q(z)xyP(x,y)Q(z),（5）量词分配等值式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)xA(x)xB(x)x(A(x)B(x)注意：对无分配律，对无分配律,基本永真式(续),14,（6）量词对和的处理x(A(x)B(x)xA(x)xB(x)证明：x(A(x)B(x)x(A(x)B(x)xA(x)xB(x)xA(x)xB(x)xA(x)xB(x),基本永真式(续),15,（7）关于多个量词的永真式xyP(x,y)yxP(x,y)xyP(x,y)yxP(x,y)yxP(x,y)xyP(x,y)xyP(x,y)yxP(x,y)xyP(x,y)yxP(x,y),基本永真式(续),16,（8）消去量词等值式（有限个体域）设个体域D=a1,a2,an，则有（1）xA(x)A(a1)A(a2)A(an)（2）xA(x)A(a1)A(a2)A(an),基本永真式(续),1.7.3几个规则,置换规则换名规则代替规则,设(A)是含公式A的公式,(B)是用公式B取代(A)中的所有A得到的公式,若AB，则(A)(B),将公式A中某量词的指导变元及其在辖域内的所有约束出现改成该量词辖域内未曾出现的某个个体变项,其余部分不变,记所得公式为A,则AA,将公式A中某个自由出现的个体变项的所有自由出现改成A中未曾出现的某个个体变项,其余部分不变,记所得公式为A,则AA,实例,例1消去公式中既约束出现、又自由出现的个体变项(1)xF(x,y,z)yG(x,y,z),uF(u,y,z)yG(x,y,z)换名规则uF(u,y,z)vG(x,v,z)换名规则,或者xF(x,u,z)yG(x,y,z)代替规则xF(x,u,z)yG(v,y,z)代替规则,(2)x(F(x,y)yG(x,y,z),x(F(x,y)tG(x,t,z)换名规则,或者x(F(x,t)yG(x,y,z)代替规则,实例,例2设个体域D=a,b,c,消去下面公式中的量词:(1)x(F(x)G(x),(F(a)G(a)(F(b)G(b)(F(c)G(c),(2)x(F(x)yG(y),xF(x)yG(y)量词辖域收缩(F(a)F(b)F(c)(G(a)G(b)G(c),x(F(x,a)F(x,b)F(x,c),(3)xyF(x,y),(F(a,a)F(a,b)F(