汪展鹏 兰笛 周洁

【摘要】本文主要对离散数学中的一些只含一个个体变元的谓词逻辑等值式在个体变元多于两个时的简单形式的推广，并加以证明和举例说明，从而可以简化多元谓词问题.

【关键词】离散数学;多元谓词;等值式;形式推广

引 言

由于命题逻辑的局限性，有些命题在命题逻辑中不能判断其正确性.例如，著名的“苏格拉底（Socrates，古希腊哲学家，公元前470—前399）论证”就是如此[1].由此，人们引入了谓词逻辑，将简单命题进一步分解为个体词、谓词和量词.谓词逻辑就是研究它们的形式结构、逻辑性质、谓词关系及从中导出的规律.谓词逻辑在数据库（如用谓词逻辑将关系数据库中的数据子语言表示出来并优化）、教育（如智能答疑系统）、人工智能科学等方面都有很广泛的应用，它既是程序设计理论、语义形式化及程序逻辑研究的重要基础，又是程序验证、程序分析、综合及自动生成、定理证明和知识表示的有力工具，显示了谓词逻辑在计算机科学中的重要性.

而随着谓词逻辑基本等值式的应用，过程过于烦琐复杂的谓词逻辑演算也变得简单.本文主要对离散数学中的一些主要的、只含一个个体变元的谓词逻辑等值式在个体变元多于两个时的简单形式的推广，从而可以简化多元谓词问题，并加以证明和举例说明，对于本文未给出的谓词逻辑等值式，其在个体变元多于两个时的简单形式推广可以参考本文证明过程.

1 基本知识

对于谓词逻辑的基本理论知识，我们建议读者参看参考文献[1].

定义1.1 令A，B为一阶语言的合式公式，若AB为逻辑有效式，则称A和B等值，记为AB.称AB是等值式.

定理1.1 设Q不含自由变项x，则下列等值式成立.

（1）xPxxPx

（2）x（P（x）∨Q）xP（x）∨Q

（3）x（P（x）→Q（x））x（P（x））→x（Q（x））

（4）x（P（x）∧Q（x））x（P（x））∧x（Q（x））

（5）xyP（x，y）yxP（x，y）

在对一元或二元谓词逻辑问题的求解过程中，通过以上等值式的替换，往往可以使问题简单化.但是，以上的等值式，由于其中谓词所含个体变元数目的限制，故对于多元或更加一般的谓词逻辑问题就没有应用价值.

例1 设T（x，y）：x被y认可，再令x是“学生”集合中的元素，y是“老师”集合中的元素，判断命题（xyT（x，y））与命题xy（T（x，y））是否等值.

由于上述等值式不适用，只能单纯地从其语义来判断或者将“学生”和“老师”集合中的元素代入之后再判断，下面选择用语义角度解决该问题.

（xyT（x，y））表示：不是每名學生都有老师认可.而命题xy（T（x，y））表示：有的同学，所有老师都不认可.两者意思一致，因此，两者等值.

虽然从语义判断也是可行的，但是在多元谓词演算过程中，如果每一步都这样来判断，那么工作量会很大.因此，以下给出上述等值式在n（n≥2）元谓词逻辑的简单形式的推广，并加以严格的理论证明.

2 记 号

我们作如下符号注记：

（1）∏ni=1Qixi表示Q1x1Q2x2…Qnxn，其中Qi是量词，即Qi∈{，}.

（2）P（n）表示P（x1，x2，…，xn）.

（3）P（k，y1，y2，…，yi）表示P（x1，x2，…，xk，y1，y2，…，yi），其中xi为自由变项，yi为个体常项.

3 主要结论

结论3.1  ∏ni=1QixiP（n）∏ni=1Rixi（P（n）），其中Qi和Ri表示不同的量词，即若Qi取，那么Ri取;反之亦然.

证明 我们对变元个数运用第一数学归纳法：

（1）当n=1时即为结论（1），显然成立.

（2）假设当n=k（k≥1，k∈N）时结论亦成立，下面证明n=k+1时结论成立，对Qk+1分以下两种情况进行讨论：

①Qk+1取时：

不妨令xk+1是集合{y1，y2，…，ym}中的元素，所以∏ki=1Qixixk+1P（k+1）

∏ki=1QixiP（k，y1）∧…∧∏ki=1QixiP（k，ym）

∏ki=1QixiPk，y1∨…∨∏ki=1QixiP（k，ym）.

而此时yi（i=1，2，…，m）都是个体常项，上式中各项都从k+1元谓词变为k元谓词，所以上式等价于：

∏ki=1Rixi（P（k，y1））∨…∨∏ki=1Rixi（P（k，ym））

∏ki=1Rixixk+1P（k+1）.

②Qk+1取时：同理可证.

∏ki=1Qixixk+1P（k+1）∏ki=1Rixixk+1P（k+1）.

所以，该结论对n=k+1成立.

综合（1）（2），对一切自然数n≥1，上述结论成立.

有了这个结论，再来看上述例题：当n=2时，很显然有xyT（x，y）xyT（x，y）成立.体现出多元推广后等值式的实用性.

结论3.2 设W不含自由变项xi（i=1，2，…，n），则下列等值式成立.

∏ni=1xiP（n）∨W∏ni=1xiP（n）∨W.

证明 类似于结论3.1的证明过程，同样对变元个数用第一数学归纳法即可.（归纳步骤需要用到“∨”对“∧”的分配律）

当n=2时，下面通过一个实例来论证该结论.

例2 设P（x，y）：x在y，再令x是“学生”集合中的元素，y是“教室”集合中的元素，Q：外面下雨.判断命题xy（P（x，y）∨Q）与命题xyP（x，y）∨Q是否等值.

下面从其语义来判断两个命题是否等值.首先将“学生”和“教室”集合中的元素代入之后再判断.命题xy（P（x，y）∨Q）表示：任意学生在外面下雨时都在自己的教室，而命题xyP（x，y）∨Q表示：外面下雨时任意一个学生都在自己的教室.两者意思一致，因此，两者等值.

结论3.3 ∏ni=1xiP（n）→W（n）∏ni=1xiP（n）→∏ni=1xiW（n）.

证明 只证n=2时的结论，其他情况类似可证.

假设论域有限，设xi∈{yi，1，yi，2，…，yi，mi}，则：

∏2i=1xi（P（2）→W（2））∏2i=1xi（P（2）∨W（2））

x1（（P（1，y2，1）∨W（1，y2，1））∨…∨（P（1，y2，m2）∨W（1，y2，m2））

…P（y1，1，y2，1）∨W（y1，1，y2，1）∨…∨P（y1，m1，y2，m2）∨W（y1，m1，y2，m2） .

根据“∨”的交换律和结合律，上式可化为：

（P（y1，1，y2，1）∨…∨P（y1，m1，y2，m2））∨（W（y1，1，y2，1）∨…∨W（y1，m1，y2，m2））

∏2i=1xi（P（2））∨∏2i=1xiW（2）.

根据利用结论3.1，即证.

当n=2时，下面通过一个实例来论证该结论.

例3 设P（x，y）：x≥y，W（x，y）：x>y，再令x是实数集合中的元素，y是实数集合中的元素，判断命题xy（P（x，y）→W（x，y））与命题xyP（x，y）→xyW（x，y）是否等值.

下面从其语义来判断两个命题是否等值.首先将实数集合中的元素代入之后再判断.命题xy（P（x，y）→W（x，y））表示：存在实数x，y，有当x≥y时，x>y.而命题xyP（x，y）→xyW（x，y）表示：对所有的实数x≥y，存在实数x，y，满足x>y.两者意思一致，因此，两者等值.

结论3.4

（1）∏ni=1xiP（n）∧W（n）∏ni=1xiP（n）∧∏ni=1xiW（n）.

（2）∏ni=1xiP（n）∨W（n）∏ni=1xiP（n）∨∏ni=1xiW（n）.

证明 同结论3.3的证明过程类似，依次将谓词展开再利用“∧”的交换律和结合律即可.

当n=2时，下面通过一个实例来论证该结论（1）式.

例4 设P（x，y）：x>y，W（x，y）：x≠y，再令x是实数集合中的元素，y是实数集合中的元素，判断命题xy（P（x，y）∧W（x，y））与命题xyP（x，y）∧xyW（x，y）是否等值.

下面从其语义来判断两个命题是否等值.首先将实数集合中的元素代入之后再判断.命题xy（P（x，y）∧W（x，y））表示：对所有的实数x，y，都有x>y且x≠y.而命题xyP（x，y）∧xyW（x，y）表示：对所有的实数x>y，都有x≠y.两者意思一致，因此，两者等值.

当n=2时，下面通过一个实例来论证该结论（2）式.

例5 设P（x，y）：x>y，W（x，y）：x=y，再令x是实数集合中的元素，y是实数集合中的元素，判断命题xy（P（x，y）∨W（x，y））与命题xyP（x，y）∨xyW（x，y）是否等值.

下面从其语义来判断两个命题是否等值.首先将实数集合中的元素代入之后再判断.命题xy（P（x，y）∨W（x，y））表示：存在实数x，y，有x>y或者x=y.而命题xyP（x，y）∨xyW（x，y）表示：存在实数x>y，或者存在实数x=y.两者意思一致，因此，两者等值.

结论3.5 ∏ni=1xiP（n）∏ni=1xtiP（n），

∏ni=1

xiP（n）∏ni=1xtiP（n），其中t1，t2，…，tn为1，2，…，n的任一排列.

证明 同结论3.3的证明过程类似，依次将谓词展开，再分别利用“∧”和“∨”的交换律和结合律即可.

还可以将结论3.5一般化，得到一个适用范围更广的推论3.5.1.

推论3.5.1 对于nn≥2元谓词命题∏ni=1QixiP（n）：

若Q1=Q2=…=Qn，则为结论2.5中的情形.

若Qi≠Qi+1=…=Qn，其中i=1，2，…，n-1，则Qi+1xi+1，…，Qn-1xn-1，Qnxn可以任意交换位置，即：

Q1x1Q2x2…QnxnP（x1，x2，…，xn）Q1x1…QixiQti+1xti+1…，

Qtn-1xtn-1QtnxtnP（x1，x2，…，xn）.

其中ti+1，…，tn-1，tn是i+1，…，n-1，n的任意排列.

由于证明过程与结论3.5类似，所以不再赘述.

※注意：

（1）本文仅仅是从谓词逻辑的所有等值式中选出几个比较基本的加以推广，引理未提及的等值式推广形式的证明均可仿照本文相应部分或者利用本文结论.

如，要证明Q→xP（x）x（Q→P（x））在n（n≥2）时的推广形式：

Q→∏ni=1xiP（n）∏ni=1xiQ→P（n）.

证明过程如下：

Q→∏ni=1xiP（n）Q∨∏ni=1xiP（n）.

再由結论3.2，上式可化为：

∏ni=1xiQ∨P（n）∏ni=1xiQ→P（n）.

（2）对于推论3.5.1，只有Qi+1xi+1，…，Qn-1xn-1，Qnxn可以交换位置，其他的量词及其所限制变元的位置一定保持不变，否则可能是错误的，下面举例说明.

例6 设P（x，y）表示x+y=a（a为一固定常数），因此，xyP（x，y）在实数R上的含义就是对任意实数x存在实数y满足x+y=a，其真值为1;而xyP（x，y）在实数域R上的含义就是存在实数y对任意的实数x都满足x+y=a，其真值为0.因此，两者不等值，即：

xyP（x，y）≠xyP（x，y）.

【参考文献】

[1]李世群，马千里.离散数学[M].天津：天津大学出版社，2010.

[2]祝深有，张会凌.带有多重量词的谓词公式的否定[J].甘肃广播电视大学学报，2008（03），36-37.