离散数学：谓词公式翻译技巧

我们知道，简单命题函数与逻辑联结词可以组合成一些谓词表达式。有了谓词与量词的概念，谓词表达式所能刻画的日常命题就能广泛而深入得多了。但是，怎样的谓词表达式才能成为谓词公式并能进行谓词演算呢？下面先介绍谓词的合式公式。

我们把A（x1，x2，…，xn）称作谓词演算的原子公式，其中x1，x2，…，xn是客体变元，因此原子谓词公式包括下述形式的各种特例。如Q，A（x），A（x，y），A（f（x），y），A（x，y，z），A（a，y）等。

定义1 谓词演算的合式公式可由下述各条组成：

（1）原子谓词公式是合式公式。

（2）若A是合式公式，则」A是一个合式公式。

（3）若A和B是合式公式，则A∧B，A∨B，A→B和A⇆B都是合式公式。

（4）如果A是合式公式，x是A中出现的任何变元，则（∀x）A和（∃x）A都是合式公式。

（5）只有经过有限次的应用规则（1）、（2）、（3）、（4）所得到的公式是合式公式。

在讨论命题公式时，曾用了关于圆括号的某些约定，即最外层的括号可以省略，在谓词合式公式中亦将遵守同样的约定，但需注意，量词后面若有括号则不能省略。

谓词合式公式，今后简称谓词公式。

下面举例说明如何用谓词公式表达自然语言中一些有关命题。

例1 并非每个实数都是有理数。

解 设R（x）：x是实数，Q（x）：x是有理数，则有：」∀x（R（x）→Q（x））。

例2 没有不犯错误的人。

解 设F（x）：x犯错误，M（x）：x是人，

则有：」（∃x（M（x）∧」F（x）））。

例3 尽管有人聪明，但未必一切人都聪明。

解 设P（x）：x聪明，M（x）：x是人，

则有：∃x（M（x）∧P（x））∧」（∀x（M（x）→P（x）））。(www.xing528.com)

例4 每一个人都爱他自己的孩子。

解 设P（x）：x是人，C（x）：x是孩子，I（x，y）：x属于y，L（x，y）：x爱y，

则有：∀x∀y（P（y）∧C（x）∧I（x，y）→L（y，x））。

例5 科学家都教育自己的孩子成为科学家，有一个人教育他的孩子去做官，证明：这个人一定不是科学家。

解 设S（x）：x是科学家，E（x）：x教育他的孩子成为科学家。

前提的描写：

P1:∀x(S(x)→E(x)),

P2:∃x(」E(x))。

结论的描写：

C:∃x(」S(x))。

于是，要去证明：（P1∧P2）→C是恒真公式。

例6 每一个人的外祖父都是他母亲的父亲。

解 设P（x）：x是人，Q（x，y）：x是y的外祖父，F（x，y）：x是y的父亲，M（x，y）：x是y的母亲，则命题可表示为：

∀x∀y∀z(P(x)∧P(y)∧P(z)∧O(x,y)∧M(z,y)→F(x,z))

例7 不管黑猫白猫，抓住老鼠就是好猫。

解 设C（x）：x是猫，B（x）：x是黑的，W（x）：x是白的，G（x）：x是好的，M（x）：x是老鼠，K（x，y）：x抓住y。于是命题可表示为：

∀x∀y(C(x)∧M(y)∧(B(x)∨W(x))∧(K(x,y)→G(x))