《1.7谓词演算的永真公式.ppt》由会员分享，可在线阅读，更多相关《1.7谓词演算的永真公式.ppt（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1.7 谓词演算的永真公式谓词演算的永真公式1.7.1 基本定义基本定义1.7.2 基本永真公式基本永真公式1.7.3 几个规则几个规则 代入规则、置换规则、改名规则代入规则、置换规则、改名规则 11.7.1 基本定义基本定义定义定义1.7-1 两个任意谓词公式两个任意谓词公式A和和B，E是它是它们共有的论述域，若们共有的论述域，若（1）对公式）对公式A和和B中的中的谓词变元谓词变元（包括命题（包括命题变元）指派以任一在变元）指派以任一在E上有定义的确定的谓上有定义的确定的谓词。词。（2）对谓词命名式）对谓词命名式(如，如，P(x)中的中的个体变元个体变元，指派以指派以E中的任一确定的个体。中
2、的任一确定的个体。所得的命题具有同样的真值，则称公式所得的命题具有同样的真值，则称公式A和和B遍及遍及E等价，记为等价，记为在在E上上AB2例如：例如：公式公式 x(F(x)G(x),个体域：全总个体域，个体域：全总个体域，F(x)：x是人是人 G(x)：x是黄种人，假命题是黄种人，假命题个体域：实数集合个体域：实数集合F(x)：x 10,G(x)：x0,真命题真命题3定义定义1.7-2 如果两个谓词公式如果两个谓词公式A和和B 在在任意任意论述域论述域上都等价，则称上都等价，则称A和和B等价，记为等价，记为AB4谓词公式的类型谓词公式的类型定义定义1.7-3 给定任一谓词公式给定任一谓词公式
3、A，如果在论，如果在论述域述域E上，对公式上，对公式A中的谓词和个体变元进中的谓词和个体变元进行行定义定义1.7-1中两种指派，所得命题中两种指派，所得命题（1）都真都真，则称，则称A在在E上有效上有效，或在，或在E上永上永真真（2）至少一个是真至少一个是真，称，称A在在E上可满足上可满足（3）都假都假，则称，则称A在在E上永假上永假，或在，或在E上不上不可满足可满足5定义定义1.7-4 给定任一谓词公式给定任一谓词公式A，如果在，如果在任任意论述域意论述域上，对上述两种指派，上，对上述两种指派，（1）A永真永真，称，称A永真或有效永真或有效（2）A至少在一个域上可满足至少在一个域上可满足，称
4、，称A可满足。可满足。（3）A永假永假，称，称A永假或不可满足永假或不可满足。6例如：设例如：设P(x)仅可解释为仅可解释为（1）A(x)：x是质数是质数（2）B(x)：x是合数是合数论述域是论述域是3，4，判定谓词公式判定谓词公式P(x)x P(x)是否永真。是否永真。真值表如表所示，所以其真值表如表所示，所以其是非永真式。是非永真式。P(x)xP(x)x P(x)A(x)3A(x)4B(x)3B(x)4 1 1 1 0 1 0 0 1 0 1 1 171.7.2 基本永真式第一组第一组 命题逻辑中基本等值式的代换实例命题逻辑中基本等值式的代换实例例如：例如：xF(x)xF(x)x y(F(
5、x,y)G(x,y)x y(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)8第二组第二组 含有量词的谓词演算的基本永真式含有量词的谓词演算的基本永真式（1）xA A，xAA，其中，其中A是不含自由变元是不含自由变元x的谓词公式。的谓词公式。（2）xP(x)P(y)或或 xP(x)P(x)P(y)xP(x)或或P(x)xP(x)xP(x)xP(x)基本等值式(续)9(3)量词否定等值式量词否定等值式 设设A(x)是含个体变项是含个体变项x自由出现的公式，则有自由出现的公式，则有
6、 （1）xA(x)x A(x)（2）xA(x)x A(x)基本永真式(续)注注1.直观解释直观解释P(x):x今天来校上课今天来校上课.xP(x):不是所有的人今天都来校上课不是所有的人今天都来校上课.x P(x):有人今天没有来校上课有人今天没有来校上课.注注2.可以在有限个体域上证明可以在有限个体域上证明思考题思考题10（4）量词辖域收缩与扩张等值式）量词辖域收缩与扩张等值式 设设A(x)是含是含x自由出现的公式，自由出现的公式，B中自由变元中自由变元x的谓词的谓词关于全称量词的：关于全称量词的：x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(
7、BA(x)BxA(x)关于存在量词的关于存在量词的:x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x)BxA(x)基本永真式(续)11实例例例1 证明证明 xA(x)B x(A(x)B)证明证明 xA(x)B x A(x)B x A(x)B x(A(x)B)x(A(x)B)注注.x(P(x)Q(y)xP(x)Q(y)x(yP(x,y)Q(z)x yP(x,y)Q(z)12（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
8、(x)x(A(x)B(x)注意：注意：对对 无分配律，无分配律，对对 无分配律无分配律 基本永真式(续)13（6）量词对）量词对 和和的处理的处理 x(A(x)B(x)xA(x)xB(x)证明：证明：x(A(x)B(x)x(A(x)B(x)x A(x)x B(x)xA(x)x B(x)xA(x)xB(x)基本永真式(续)14（7）关于多个量词的永真式）关于多个量词的永真式 x yP(x,y)y x P(x,y)x yP(x,y)y x P(x,y)y x P(x,y)x y P(x,y)x y P(x,y)y x P(x,y)x y P(x,y)y x P(x,y)基本永真式(续)15（8）消
9、去量词等值式（有限个体域）消去量词等值式（有限个体域）设个体域设个体域 D=a1,a2,an，则有则有 （1）xA(x)A(a1)A(a2)A(an)（2）xA(x)A(a1)A(a2)A(an)基本永真式(续)161.7.3 几个规则置换规则置换规则换名规则换名规则代替规则代替规则 设设(A)是含公式是含公式A的公式的公式,(B)是用公式是用公式B取取代代(A)中的所有中的所有A得到的公式得到的公式,若若AB，则则(A)(B)将公式将公式A中某量词的指导变元及其在辖域内的中某量词的指导变元及其在辖域内的所有约束出现改成该量词辖域内未曾出现的某个个体变所有约束出现改成该量词辖域内未曾出现的某个
10、个体变项项,其余部分不变其余部分不变,记所得公式为记所得公式为A,则则A A 将公式将公式A中某个自由出现的个体变项的所有自中某个自由出现的个体变项的所有自由出现改成由出现改成A中未曾出现的某个个体变项中未曾出现的某个个体变项,其余部分不变其余部分不变,记所得公式为记所得公式为A,则则A A17实例例例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)代替规则代替
11、规则 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)代替规则代替规则18实例例例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)x yF(x,y)(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)19实例例例3 证明下列各等值式证明下列各等值式:x(M(x)F(x)x(M(x)F(x)证证 左边左边 x (M(x)F(x)量词否定等值式量词否定等值式 x(M(x)F(x)x(M(x)F(x)20