离散数学（上）：谓词演算推理理论

（1）前束范式

在命题演算中，常常要将公式化成规范形式，对于谓词演算，也有类似情况，一个谓词演算公式，可以化为与它等价的范式。

定义1 一个公式，如果量词均在全式的开头，它们的作用域，延伸到整个公式的末尾，则该公式叫作前束范式。

前束范式可记为下述形式：

（□v1）（□v2）…（□vn）A，其中□可能是量词∀或量词∃，vi（i=1，2，…，n）是客体变元，A是没有量词的谓词公式。

例如（∀x）（∀y）（∃z）（Q（x，y）→R（z）），（∀y）（∀x）（」P（x，y）→Q（y））等都是前束范式。

定理1 任意一个谓词公式，均和一个前束范式等价。

证明 首先利用量词转化公式，把否定深入到命题变元和谓词填式的前面，其次利用（∀x）（A∨B（x））⇔A∨（∀x）B（x）和（∃x）（A∧B（x））⇔A∧（∃x）B（x）把量词移到全式的最前面，这样便得到前束范式。

例1 把公式（∀x）P（x）→（∃x）Q（x）转化为前束范式。

解（∀x）P（x）→（∃x）Q（x）⇔（∃x）」P（x）∨（∃x）Q（x）⇔（∃x）（」P（x）∨Q（x））。

例2 化公式（∀x）（∀y）（（∃z）（P（x，z）∧P（y，z））→（∃u）Q（x，y，u））为前束范式。

解 原式⇔（∀x）（∀y）（」（∃z）（P（x，z）∧P（y，z））∨（∃u）Q（x，y，u））

⇔(∀x)(∀y)((∀z)(」P(x,z)∨」P(y,z)∨(∃u)Q(x,y,u))

⇔(∀x)(∀y)(∀z)(∃u)(」P(x,z)∨」P(y,z)∨Q(x,y,u))

例3 把公式」（∀x）{（∃y）A（x，y）→（∃x）（∀y）[B（x，y）∧（∀y）（A（y，x）→B（x，y））]}化为前束范式。

解 第一步否定深入。

原式⇔（∃x）」{」（∃y）A（x，y）∨（∃x）（∀y）[B（x，y）∧（∀y）（A（x，y）→B（x，y）]}(www.xing528.com)

⇔(∃x){(∃y)A(x,y)∧(∀x)(∃y)[」B(x,y)∨(∃y)」(A(y,x)→B(x,y)]}。

第二步改名，以便把量词提到前面。

⇔(∃x){(∃y)A(x,y)∧(∀u)(∃r)[」B(u,r)∨(∃z)」(A(z,u)→B(u,s))]}

⇔(∃x)(∃y)(∀u)(∃r)(∃z){A(x,y)∧[」B(u,r)∨」(A(z,u)→B(u,z))]}。

（2）推理理论

谓词演算的推理方法，可以看作是命题演算推理方法的扩张。因为谓词演算的很多等价式和蕴涵式，是命题演算有关公式的推广，所以命题演算中的推理规则，如P、T和CP规则等亦可在谓词的推理理论中应用，但是在谓词推理中，某些前提与结论可能是受量词限制的，为了使用这些等价式和蕴涵式，必须在推理过程中有消去和添加量词的规则，以便使谓词演算公式的推理过程可类似于命题演算中推理理论那样进行。现介绍如下规则。

1）全称指定规则，它表示为US

这里P是谓词，而c是论域中任意的客体。例如设论域为全人类。P（x）表示“x总是要死的”，如果我们有（∀x）P（x）即是“所有人总是要死的”，那么全称指定规则可有结论“苏格拉底总是要死的”。

2）全称推广规则，它表示为UG

这个规则是要对命题量化，如果能够证明对论域中每一个客体x断言P（x）都成立，则全称推广规则可得到结论（∀x）P（x）成立。在应用本规则时，必须能够证明前提P（x）对论域中每一可能的x是真。

（3）存在指定规则，它可表示为ES

这里c是论域中的某些客体，必须注意，应用存在指定规则，其指定的客体c不是任意的。例如（∃x）P（x）和（∃x）Q（x）都真，则对于某些c和d，可以断定P（c）∧Q（d）必定为真，但不能断定P（c）∧Q（c）是真。

（4）存在推广规则，它表示为EG

这里c是论域中的一个客体，这个规则比较明显，对于某些客体c，若P（c）为真，则在论域中必有（∃x）P（x）为真。

例4 证明（∀x）（H（x）→M（x））∧H（s）⇒M（s），这是著名的苏格拉底论证。