《谓词逻辑永真公式.ppt》由会员分享，可在线阅读，更多相关《谓词逻辑永真公式.ppt（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、11.6 谓词逻辑的永真公式在谓词逻辑中，公式是一个符号串，必须给以具体的解释后才能分辨其真假的可能。解释：给公式中的个体变元指定一个具体的个体域D一个公式经解释后才具有具体的意义。谓词公式的解释I包括：1.指定一个论域D(称I为D上的解释)2.对A中出现的每一个n元函数，指定一个D上的 n元个体函数常量3.对A中出现的每一个n元谓词，指定一个D上的n元谓词常量4.对A中出现的每一个个体常量及自由变元，指定D中的一个个体常量5.对A中出现的每一个命题变元P，指派一个真值T或F 由此得到一个命题AI，称AI的真值为公式A在解释I 下的真值例取解释I如下：D=1,2,定义D上的二元谓词P真值为P(
2、1,1):T；P(1,2):F；P(2,1):F；P(2,2):T 则xyP(x,y)和yxP(x,y)在解释I下的真值分别为?xyP(x,y)TTFFTTT212211xyP(x,y)yP(x,y)P(x,y)yx关于x的一元函数yxP(x,y)TFFFFFT212211yx P(x,y)xP(x,y)P(x,y)xy关于y的一元函数例取解释I如下：D=1,2,令 a:1,f(1)=2,f(2)=1定义D上的谓词P和Q为P(1):F；P(2):T；Q(1,1):T；Q(1,2):T；Q(2,1):F；Q(2,2):F求谓词公式x(P(x)Q(f(x),a)在解释I下的真值P(1)Q(f(1)
3、,1)P(2)Q(f(2),1)TTx(P(x)Q(f(x),a)在解释I下的真值为T谓词公式的永真式定义定义 给定谓词公式A，E是其论域，如果在任何解释下公式A的真值都为真，则称公式A在论域E上是永真式。如果不论对什么论域E，都使得公式A为永真式，则称A为永真式。例：I(x)：x是整数，论域E为自然数集合I(x)在E上是永真式I(x)I(x)是与论域无关的永真式谓词公式的永假式谓词公式的可满足式例：试说明以下公式的类型1.xA(x)A(y)2.xA(x)A(y)3.A(x)(A(x)：x+6=5)4.x(A(x)A(x)5.x(A(x)B(x)xA(x)xB(x)6.x(A(x)B(x)xA
4、(x)xB(x)永真式 可满足式 可满足式永假式永真吗?永真式的判定命题逻辑的永真式问题是可判定的。至少可用真值表谓词逻辑的永真式问题是不可判定的。研究谓词逻辑永真式判定问题非常有意义：联词与量词的关系问题与否问题的关系构造证法的一种典型情形公式形成规则、联词、量词、变元约束等知识点逐步推演思想完整地自顶向下逐步求精思想问题与否问题问题：所给公式是永真式吗？否问题：所给公式不是永真式吗？这两个问题有不同的难度是永真式：在任何论域的任何解释下皆为真不是永真式：存在一个使该公式为假的特定解释问题证明的一般方法直接证明法反证法数学归纳法递归或递推的形式给出算法问题描述方式决定Px(Q(x)R(x)P
5、xA(x)构造证法找出实例给出算法What代替How1.明确问题形式结构x：Q(x)R(x)2.转换形式结构 Q1(x)R1(x)3.引用已知条件PP(问题具体描述)(问题抽象描述)(两种方式)例：试判断xA(x)xB(x)x(A(x)B(x)是否是永真式，并说明理由。分析：试图找到一个使该公式为假的解释，首先考虑论域。论域大了，过程会复杂，论域小了，无法区分全称与存在，所以取D=1,2。A(1)A(2)B(1)B(2)?现在要确定目的(约束条件)是FxA(x)xB(x)x(A(x)B(x)所以TxA(x)xB(x)x(A(x)B(x)FxA(x)为T或或xB(x)为TA(1)B(1)为F或或
6、A(2)B(2)为F不妨不妨取FA(1)B(1)这样A(1)A(2)B(1)B(2)F F TxA(x)xB(x)x(A(x)B(x)F从而A(1)A(2)B(1)B(2)F F TxB(x)T所以xA(x)F因此结论：所给公式不是永真式例(续前)：试判断xA(x)xB(x)x(A(x)B(x)是否是永真式，并说明理由。解：所给公式不是永真式，理由如下。考虑D=1,2上的解释I：A(1)A(2)B(1)B(2)F F F T在I下：FA(1)B(1)xB(x)T所以TxA(x)xB(x)x(A(x)B(x)FFxA(x)xB(x)x(A(x)B(x)此处取T亦可总结总的思路：试图在D=1,2上
7、找到一个使所给公式为假的解释。注意：以前进行运算都是根据形成过程由里往外逐次进行的，但这里的过程正好相反：自顶向下逐步推演。在推演过程中，首先考虑以下事实：若是上述五种情况之外的情况，则利用D中元素的对称性避免讨论。ABFABA BT FA ABFA BF FABTA BT TTxA(x)A(1)A(2)T TF xA(x)A(1)A(2)F F谓词公式的等价定义两个任意谓词公式A和B,E是它们共有的论域,若在任何解释下，A与B作的真值都相同(或者说AB是永真式)，则称公式A与B在论域E上是等价的。如果不论对什么论域E，都使得公式A与B等价，则称A与B等价，记作AB。例：I(x)：x是整数，N
8、(x)：x是自然数，论域E是自然数集合I(x)与N(x)在E上是等价的N(x)I(x)N(x)I(x)谓词公式的蕴含定义两个任意谓词公式A和B，E是它们的论域，若在任何解释下，都使得公式AB为永真式，则称在论域E上公式A永真蕴含B。如果不论对什么论域E，AB是永真式，则称A永真蕴含B，记作AB。例：G(x)：x大于5，N(x)：表示x是自然数，论域E=-1,-2,6,7,8,9,.在E上公式G(x)N(x)是永真式(G(x)N(x)N(x)是与论域无关的永真式，所以(G(x)N(x)N(x)谓词演算的基本永真公式命题演算的永真公式也是谓词演算的永真公式含有量词的谓词演算的基本永真公式（1）量词
9、的否定 xP(x)xP(x)（1）xP(x)xP(x)（2）量词转换公式共轭共轭例 xyz(x+z=y)xyz(x+z=y)xyz(x+z=y)xy z(x+z=y)xy z(x+zy)(2)量词辖域的扩张和收缩xP(x)Qx(P(x)Q)(3)xP(x)Qx(P(x)Q)(4)xP(x)Qx(P(x)Q)(5)xP(x)Qx(P(x)Q)(6)证明式(3)：一方面，当Q为F时，xP(x)QxP(x)FxP(x)x(P(x)Q)x(P(x)F)xP(x)另一方面，当Q为T时，xP(x)QxP(x)TTx(P(x)Q)x(P(x)T)T(5)量词辖域的扩张和收缩xA(x)Px(A(x)P)(12
10、)xA(x)Px(A(x)P)(13)PxA(x)x(PA(x)(14)PxA(x)x(PA(x)(15)P是不含个体变元x的谓词公式(3)关于多个量词的永真式1.xyA(x,y)yxA(x,y)(7)2.xyA(x,y)yxA(x,y)(8)3.xyA(x,y)yxA(x,y)(9)4.xyA(x,y)yxA(x,y)5.yxA(x,y)xyA(x,y)6.xyA(x,y)xyA(x,y)7.yxA(x,y)xyA(x,y)8.yxA(x,y)xyA(x,y)(4)xP(x)P(y)或 xP(x)P(x)(10)P(y)xP(x)或 P(x)xP(x)(11)(6)量词的分配形式x(A(x)
11、B(x)xA(x)xB(x)(16)x(A(x)B(x)xA(x)xB(x)(17)xA(x)xB(x)x(A(x)B(x)(18)x(A(x)B(x)xA(x)xB(x)(19)证明式16：个体域中每一个体x，使得 A(x)B(x)为真,等价于对一切x,A(x)是真并且对一切x,B(x)是真证明式17：由1得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)注意注意：式18和式19不是等价公式，而是永真蕴含式例：给定如下解释A(x)：x是奇数B(x)：x是偶数则 xA(x)xB(x)为真 x(A(x)B(x)为假
12、所以xA(x)xB(x)不蕴含不蕴含x(A(x)B(x)或D=1,2A(1):T A(2):F B(1):F B(2):T证明式19 x(A(x)B(x)xA(x)xB(x)证明：假设前件x(A(x)B(x)为真，则论域中至少有一个个体a，使得 A(a)B(a)为真，即A(a)和B(a)都为真，所以有xA(x)以及xB(x)为真，得xA(x)xB(x)为真 所以 x(A(x)B(x)xA(x)xB(x)证明式18 xA(x)xB(x)x(A(x)B(x)证明：由3得 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
13、(x)xB(x)x(A(x)B(x)公式4得证。特别要注意蕴含式的方向，不要搞错(7)量词对及的处理x(A(x)B(x)xA(x)xB(x)xA(x)xB(x)x(A(x)B(x)证明1.xA(x)xB(x)xA(x)xB(x)xA(x)xB(x)x(A(x)B(x)x(A(x)B(x)证明2.xA(x)xB(x)xA(x)xB(x)xA(x)xB(x)x(A(x)B(x)x(A(x)B(x)几条规则(命题演算的推广)代入规则设A是命题逻辑中的永真式，则用谓词逻辑的合适公式代替A中的某些命题变元得到的代入实例也是永真式；如果A是永假式，则上述代入实例也是永假式例A(x)A(x)B(x)PPQx(A(x)B(x)x(A(x)B(x)PQPQ(xA(x)xB(x)xA(x)xB(x)摩根律替换规则设A(x1,x2,xn)B(x1,x2,xn),而A是公式C中的子公式,将B替换C中之A不必每一处得D,则CD。对偶原理在公式A B或A B中,A,B仅含运算符,和,将上式中的全称量词与存在量词互换,与互换,T和F互换,则 A*B*,B*A*