离散数学第2章(7-8)(新教材)

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(前束合取范式)如果一个前束范式的母式是若干项的一个合取式，且每个单独的合取项中只含有原子谓词公式以及否定联结词和析取联结词，也即其母式有如下形状:则称所给前束范式是一个前束合取范式.定义7.3(前束析取范

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) (x)P(x)(y)Q(x,y) (x)P(x)(y)Q(z,y)

4、(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)(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. 求下述谓词公式的前束合

5、取范式和前束析取 范式: (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, 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节 谓词演算的推理理论 谓词演算的推理理论中，经常遇到等价式以及蕴含式的证明问题，而等价式可以改为证明两个蕴含式。所以蕴含式的证明是这一部分的重点。其证明方法与

6、命题逻辑中的证明方法本质上是相同的。可以分为直接证法、间接证法以及特殊情况下的CP规则证法等。因而谓词逻辑的推理方法可以看作是命题演算推理方法的扩张。 但在谓词演算推理中，有些前提和结论可能受到量词的限制，此时不能将命题演算中的推理规则直接拿来应用，而应该首先利用消去量词的规则化为可以应用命题逻辑中推理规则的情形再行处理，以下是两组消去和恢复量词的规则。第一组(消去和恢复全称量词的规则):(1)全称指定规则, 用符号US来表示 (x)P(x) P(c) 这里P是谓词, c是论域中某个任意的个体. (2)全称推广规则, 用符号UG来表示 P(x) (x)P(x) 此规则是说如果能够证明对论域中的

7、每个个体c, 都有P(c)成立, 那么根据此规则可得到结论(x)P(x)成立.第二组(消去和恢复存在量词的规则):(3)存在指定规则, 用符号ES来表示 (x)P(x) P(c) 这里c是论域中某个个体, 但不是任意的个体. 例如, 如果(x)P(x)和(x)Q(x)都为真, 则可断定, 存在个体c和d, 使P(c)和Q(d)都为真, 但不能断定P(c)和Q(c)都为真, 也不能断定P(d)和Q(d)都为真,因为个体c和d不一定相同. (4)存在推广规则, 用符号EG来表示 P(c) (x)P(x) 此规则比较显然, 即当对某个个体c, P(c)为真时, 在论域中必有(x)P(x)为真.例1.

8、 证明苏格拉底三段论:“所有的人都是要死的,苏格拉底是人,所以苏格拉底是要死的.”证明: 设H(x): x是一个人, D(x): x是要死的, s: 苏格拉底。 即需证明: (x)(H(x)M(x)H(s)M(s); (1) (x)(H(x)D(x) 前提 (2) H(s)D(s) (1), US (3) H(s) 前提 (4) D(s) T(2),(3)例2. 证明下列蕴含式的有效性: (x)(P(x)Q(x) (x)Q(x)(x)P(x)证法一: 用如下的直接证法 (1) (x)Q(x)(x)P(x) P(设右方为假) (2) (x)Q(x)(x)P(x) T(1) (3) (x)Q(x)

9、(x)P(x) T(2) (4) (x)Q(x) T(3) (5) (x)P(x) T(3) (6) Q(c) T(4)ES (7) P(c) T(5)US (8) P(c)Q(c) T(6)(7) (9) (P(c)Q(c) T(8) (10) (x)(P(x)Q(x) T(9) EG (11) (x)(P(x)Q(x) T(10) 证法二:用CP规则加以证明(1)(x)Q(x) 附加前提(2)Q(c) (c是某个特殊的个体)T(1)ES(3)(x)(P(x)Q(x) P(4)P(c)Q(c) T(3)US (5)P(c) T(4) (6)(x)P(x) T(5)EG例3.(一个应用问题)

10、自从改革开放以来,银行业发生了很大的变化.中国国内目前有三类银行在从事各种外币以及人民币的金融业务:一批国家以及地方资金控股的国有银行,若干家民营资本控股的私有银行以及外国资本控股的外资银行.有的银行专做资金大的大客户的业务(如外资银行),有的银行兼做大客户和小客户的业务(如国有银行和私有银行).已知b银行不是国有银行,但它兼做大客户和小客户的业务.证明它是一家私有银行.证明:定义如下谓词 G(x):x是国有银行, S(x):x是私有银行, W(x):x是外资银行, D(x):x做大客户业务,X(x):x做小客户业务. 则问题可化为证明一个蕴含式,它的前提是:(1)(x)(G(x)S(x)W(x) (2)(x)(W(x)D(x)X(x) (3)(x)(G(x)S(x)D(x)X(x) (4)G(b),D(b),X(b) 要证的结论是:S(b).用间接证法:(1)S(b) 附加前提 (2)(x)(G(x)S(x)W(x) P (3)G(b)S(b)W(b) T(2)US(4)