谓词逻辑永真公式

《谓词逻辑永真公式》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、11.6谓词逻辑的永真公式在谓词逻辑中，公式是一个符号串，必须给以具体的解释后才能分辨其真假的可能。解释：给公式中的个体变元指定一个具体的个体域D一个公式经解释后才具有具体的意义。谓词公式的解释I包括：指定一个论域D(称I为D上的解释)对A中出现的每一个n元函数，指定一个D上的n元个体函数常量对A中出现的每一个n元谓词，指定一个D上的n元谓词常量对A中出现的每一个个体常量及自由变元，指定D中的一个个体常量对A中出现的每一个命题变元P，指派一个真值T或F由此得到一个命题AI，称AI的真值为公式A在解释I下的真值例取解

2、释I如下：D={1,2},定义D上的二元谓词P真值为P(1,1):T；P(1,2):F；P(2,1):F；P(2,2):T则xyP(x,y)和yxP(x,y)在解释I下的真值分别为?xyP(x,y)TTFFTTT212211xyP(x,y)yP(x,y)P(x,y)yx关于x的一元函数yxP(x,y)TFFFFFT212211yxP(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

3、；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)TT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

4、)是与论域无关的永真式谓词公式的永假式谓词公式的可满足式例：试说明以下公式的类型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)永真式可满足式可满足式永假式永真吗?永真式的判定命题逻辑的永真式问题是可判定的。至少可用真值表谓词逻辑的永真式问题是不可判定的。研究谓词逻辑永真式判定问题非常有意义：联词与量词的关系问题与否问题的关系构造证法的一种典型情形公式形

5、成规则、联词、量词、变元约束等知识点逐步推演思想完整地自顶向下逐步求精思想问题与否问题问题：所给公式是永真式吗？否问题：所给公式不是永真式吗？这两个问题有不同的难度是永真式：在任何论域的任何解释下皆为真不是永真式：存在一个使该公式为假的特定解释问题证明的一般方法直接证明法反证法数学归纳法递归或递推的形式给出算法问题描述方式决定Px(Q(x)→R(x))PxA(x)构造证法找出实例给出算法What代替How1.明确问题形式结构x：Q(x)R(x)2.转换形式结构Q1(x)R1(x)3.引用已知条件PP

6、(问题具体描述)(问题抽象描述)(两种方式)例：试判断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)为TA(1)∨B(1)为F或A(2)∨B(2)

7、为F不妨取FA(1)∨B(1)这样A(1)A(2)B(1)B(2)FFTxA(x)∨xB(x)x(A(x)∨B(x))F从而A(1)A(2)B(1)B(2)FFT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)FFFT在I下：FA(1)∨B(1)xB(x)T所以TxA(x)∨xB(x)x(A(x)∨

8、B(x))FFxA(x)∨xB(x)→x(A(x)∨B(x))此处取T亦可总结总的思路：试图在D={1,2}上找到一个使所给公式为假的解释。注意：以前进行运算都是根据形成过程由里往外逐次进行的，但这里的过程正好相反：自顶向下逐步推演。在推演过程中，首先考虑以下事实：若是上述五种情况之外的情况，则利用D中元素的对称性避免讨论。A→BFA→BABTFAA∨