资源描述：
《离散数学第2章(7-8)(新教材)课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第七节谓词公式的前束范式在命题演算中有时需将命题公式化成与之等价的规范形式,在谓词演算中也需将谓词公式化成与之等价的规范形式。 定义7.1(前束范式) 用某种方式将一个谓词公式中所有的量词都移到公式的开头,而它们的作用域延伸至整个公式的末尾,这样得到的与原公式等价的公式称为所给公式的前束范式。根据上面的定义，前束范式的一般形式是:(Δ1x1)(Δ2x2)…(Δnxn)P,其中Δi是量词或;xi是个体变量(i=1,2,…,n),P是不含任何量词的谓词公式,其中的谓词公式P常称为该前束范式的母式.例1. (1)(x)(y)(z)(P(x,y)Q(y,u)R(x,v,z)) 是一
2、个析取范式, (2)(x)(P(x)(y)Q(x,y)) 不是前束范式.定理7.1任意一个谓词公式都有一个与之等价的前束范式存在。证明:首先利用量词的转化公式,把否定联结词移 到各个命题公式以及谓词公式的前面,再利用形如 (x)(AB(x))A(x)B(x) 以及(x)(AB(x))A(x)B(x) 的等价式通过扩大量词的作用范围,把量词逐步移到公式最前面,这样就得到与之等价的前束范式了。定义7.2(前束合取范式)如果一个前束范式的母式是若干项的一个合取式，且每个单独的合取项中只含有原子谓词公式以及否定联结词和析取联结词，也即其母式有如下形状:则称所给前束范式是
3、一个前束合取范式.定义7.3(前束析取范式)如果一个前束范式的母式是若干项的一个析取式,且每个单独的析取项中只含有原子谓词公式以及否定联结词和合取联结词,也即其母式有如下形状:则称所给前束范式是一个前束析取范式.下面的定理保证了前束合取范式以及前束析取范式的存在:定理7.2任何一个谓词公式都有与它等价的前束合取范式存在;也都有与它等价的前束析取范式存在.下面给出几个求前束范式的例子.例2.求出下列公式的前束范式: (1)(x)P(x)(y)Q(x,y)(2)(x)(P(x)Q(x))((x)P(x)(x)Q(x))解: (1)(x)P(x)(y)Q(x,y)
4、(x)P(x)(y)Q(x,y)(x)P(x)(y)Q(z,y)(x)(y)(P(x)Q(z,y))((x)(y)(P(x)Q(z,y)))(2)(x)(P(x)Q(x))((x)P(x)(x)Q(x))(x)(P(x)Q(x))((x)P(x)(x)Q(x))(x)(P(x)Q(x))((x)P(x)(x)Q(x))((x)(P(x)Q(x))(x)Q(x))(x)P(x)(交换律)((x)((P(x)Q(x))Q(x)))(x)P(x)(结合律)((x)(
5、(P(x)Q(x))(Q(x)Q(x)))(x)P(x)(分配律)((x)((P(x)Q(x))T)(x)P(x)((x)(P(x)Q(x)))(y)P(y)(x)(y)(P(x)Q(x)P(y)).例3.求下述谓词公式的前束合取范式和前束析取 范式:(x)P(x)(x)((z)Q(x,z)(z)R(x,y,z)).解:原式(x)P(x)(x)((z)Q(x,z)(z)R(x,y,z))(x)P(x)(x)((z)Q(x,z)(z)R(x,y,z))(x)(P(x)((z)Q(x
6、,z)(z)R(x,y,z)))(分配律)(x)(P(x)((z)Q(x,z)(u)R(x,y,u)))(x)(z)(u)(P(x)Q(x,z)R(x,y,u))第8节谓词演算的推理理论谓词演算的推理理论中，经常遇到等价式以及蕴含式的证明问题，而等价式可以改为证明两个蕴含式。所以蕴含式的证明是这一部分的重点。其证明方法与命题逻辑中的证明方法本质上是相同的。可以分为直接证法、间接证法以及特殊情况下的CP规则证法等。因而谓词逻辑的推理方法可以看作是命题演算推理方法的扩张。 但在谓词演算推理中，有些前提和结论可能受到量词的限制，此时不能将命题演算中的推理规则直接拿
7、来应用，而应该首先利用消去量词的规则化为可以应用命题逻辑中推理规则的情形再行处理，以下是两组消去和恢复量词的规则。第一组(消去和恢复全称量词的规则):(1)全称指定规则,用符号US来表示(x)P(x)P(c)这里P是谓词,c是论域中某个任意的个体.(2)全称推广规则,用符号UG来表示P(x)(x)P(x)此规则是说如果能够证明对论域中的每个个体c,都有P(c)成立,那么根据此规则可得到结论(x)P(x)成立.第
