谓词逻辑永真公式

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,11.6 谓词逻辑的永真公式,在谓词逻辑中，公式是一个符号串，必须给以具体的解释后才能分辨其真假的可能。,解释：给公式中的个体变元指定一个具体的个体域D,一个公式经解释后才具有具体的意义。,谓词公式的解释I包括：,指定一个论域,D,(,称,I,为,D,上的解释,),对,A,中出现的每一个,n,元函数，指定一个,D,上的,n,元个体函数常量,对,A,中出现的每一个,n,元谓词，指定一个,D,上的,n,元谓词常量,对,A,中,出现的每一个个体常量及自由变元，指定,D,中的一个个体常量,对,A,中出现的每一个命题变元,P,，,指派一个真值,T,或,F,由此得到一个命题,A,I,，称,A,I,的真值为公式,A,在解释,I,下,的真值,例,取解释,I如下：,D=1,2,定义,D上的二元谓词P真值为,P(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),T,T,F,F,T,T,T,2,1,2,2,1,1,xyP(x,y),yP(x,y),P(x,y),y,x,关于x的一元函数,yxP(x,y),T,F,F,F,F,F,T,2,1,2,2,1,1,yx P(x,y),xP(x,y),P(x,y),x,y,关于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),1),P,(2),Q,(,f,(2),1),T,T,x,(,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,)是与论域无关的永真式,谓词公式的永假式,谓词公式的可满足式,例：试说明以下公式的类型,xA,(,x,),A,(,y,),xA,(,x,),A,(,y,),A,(,x,)(,A,(,x,),：,x,+6=5),x,(,A,(,x,),A,(,x,),x,(,A,(,x,),B,(,x,),),xA,(,x,),xB,(,x,),x,(,A,(,x,),B,(,x,),),xA,(,x,),xB,(,x,),永真式,可满足式,可满足式,永假式,永真吗?,永真式的判定,命题逻辑的永真式问题是可判定的。,至少可用真值表,谓词逻辑的永真式问题是不可判定的。,研究谓词逻辑永真式判定问题非常有意义：,联词与量词的关系,问题与否问题的关系,构造证法的一种典型情形,公式形成规则、联词、量词、变元约束等知识点,逐步推演思想,完整地自顶向下逐步求精思想,问题与否问题,问题：所给公式是永真式吗？,否问题：所给公式不是永真式吗？,这两个问题有不同的难度,是永真式：,在任何论域的任何解释下皆为真,不是永真式：,存在一个使该公式为假的特定解释,问题证明的一般方法,直接证明法,反证法,数学归纳法,递归或递推的,形式给出算法,问题描述方式决定,P,x(Q(x)R(x),P,xA(x),构造证法,找出实例,给出算法,What代替How,1.明确问题形式结构,x：Q(x),R(x,),2.转换形式结构,Q,1,(x),R,1,(x),3.引用已知条件P,P,(问题具体描述),(问题抽象描述),(两种方式),例：试判断,xA,(,x,),xB,(,x,),x(A,(,x,),B,(,x,)是否是永真式，并说明理由,。,分析：试图找到一个使该公式为假的解释，首先考虑论域。,论域大了，过程会复杂，论域小了，无法区分全称与存在，所以,取D,=1,2。,A,(1),A,(2),B,(1),B,(2),?,现在要确定,目的(约束条件)是,F,xA,(,x,),xB,(,x,),x(A,(,x,),B,(,x,),所以,T,xA,(,x,),xB,(,x,),x(A,(,x,),B,(,x,),F,xA,(,x,),为T,或,xB,(,x,),为T,A,(,1,)B(1),为F,或,A,(,2,)B(2),为F,不妨,取,F,A,(1),B,(1),这样,A,(1),A,(2),B,(1),B,(2),F F,T,xA,(,x,),xB,(,x,),x(A,(,x,),B,(,x,),F,从而,A,(1),A,(2),B,(1),B,(2),F F T,xB,(,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下：,F,A,(1),B,(1),xB,(,x,),T,所以,T,xA,(,x,),xB,(,x,),x(A,(,x,),B,(,x,),F,F,xA,(,x,),xB,(,x,),x(A,(,x,),B,(,x,),此处取T亦可,总结,总的思路：试图在D=1,2上找到一个使所给公式为假的解释。,注意：以前进行运算都是根据形成过程由里往外逐次进行的，但这里的过程正好相反：自顶向下逐步推演。,在推演过程中，首先考虑以下事实：,若是上述五种情况之外的情况，则利用D中元素的对称性避免讨论。,AB,F,AB,A B,T F,A,AB,F,A B,F F,AB,T,A B,T T,T,xA(x),A(1)A(2),T T,F,xA(x),A(1)A(2),F F,谓词公式的等价,定义,两个任意谓词公式,A,和,B,E,是它们共有的论域,若,在任何解释下，,A,与,B,作的真值都相同(或者说,A,B,是永真式)，则称公式,A,与,B,在论域,E,上是等价的。如果不论对什么论域,E,，都使得公式,A,与,B,等价，则称,A,与,B,等价，记作,A,B,。,例：,I,(x)：,x,是整数，,N,(,x,)：,x,是自然数，论域,E,是自然数集合,I,(,x,)与,N,(,x,)在,E,上是等价的,N,(,x,),I,(,x,),N,(,x,),I,(,x,),谓词公式的蕴含,定义,两个任意谓词公式,A,和,B,，,E,是它们的论域，,若,在任何解释下，都使得公式,A,B,为永真式，则称在论域,E,上公式,A,永真蕴含,B,。如果不论对什么论域,E,，,A,B,是永真式，则称,A,永真蕴含,B,，记作,A,B,。,例：,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）,量词的否定,xP,(,x,),x,P,(,x,)（1）,xP,(,x,),x,P,(,x,),（2）,量词转换公式,共轭,例,x,y,z,(,x,+,z,=,y,),x,y,z,(,x+z=y,),x,y,z,(,x,+,z,=,y,),x,y,z,(,x,+,z,=,y,),x,y,z,(,x,+,z,y,),(2),量词辖域的扩张和收缩,xP,(,x,),Q,x,(,P,(,x,),Q,),(3),xP,(,x,),Q,x,(,P,(,x,),Q,),(4),xP,(,x,),Q,x,(,P,(,x,),Q,),(5),xP,(,x,),Q,x,(,P,(,x,),Q,),(6),证明式,(3),：,一方面，当,Q,为,F,时，,xP,(,x,),Q,xP,(,x,)F,xP,(,x,),x,(,P,(,x,),Q,),x,(,P,(,x,),F,),xP,(,x,),另一方面，当,Q,为,T,时，,xP,(,x,),Q,xP,(,x,)T,T,x,(,P,(,x,),Q,),x,(,P,(,x,),T,),T,(5),量词辖域的扩张和收缩,xA,(,x,),P,x,(,A,(,x,),P,),(12),xA,(,x,),P,x,(,A,(,x,),P,),(13),P,xA,(,x,),x,(,P,A,(,x,),(14),P,xA,(,x,),x,(,P,A,(,x,),(15),P,是,不含个体变元x的谓词公式,(3)关于多个量词的永真式,x,yA,(,x,y,),y,xA,(,x,y,),(7),x,yA,(,x,y,),y,xA,(,x,y,),(8),x,yA,(,x,y,),y,xA,(,x,y,),(9),x,yA,(,x,y,),y,xA,(,x,y,),y,xA,(,x,y,),x,yA,(,x,y,),x,yA,(,x,y,),x,yA,(,x,y,),y,xA,(,x,y,),x,yA,(,x,y,),y,xA,(,x,y,),x,yA,(,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,),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,),x,A,(,x,),x,B,(,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,)为假,所以,xA,(,x,),xB,(,x,),不蕴含,x,(,A,(,x,),B,(,x,),或,D,=1,2,A,(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得,