谓词演算推理理论-离散数学

全称量词消去规则（US）：

∀xA（x）├A（y）

∀xA（x）├A（c）

两式成立的条件是：①x是A（x）中自由出现的个体变元；②y为任意的不在A（x）中约束出现的个体变元；③c为任意的个体常元.

全称量词引入规则（UG）：

A（y）├∀xA（x）

上式成立的条件是：①y是A（y）中自由出现的个体变元，且y取任何值A（y）均为真；②取代y的x不能在A（y）中约束出现.

存在量词引入规则（EG）：

A（c）├∃xA（x）

上式成立的条件是：①c是特定的个体常元；②取代c的x不能在A（c）中出现.

存在量词消去规则（ES）：

∃xA（x）├A（c）

上式成立的条件是：①c是使A（c）为真的特定的个体常元；②c不曾在A（x）中出现；③A（x）中除x外还有其他自由出现的个体变元时，不能用此规则.

谓词演算中推理的一般过程：先把带量词前提中的量词去掉，变为命题逻辑的推理，推出结果后，再把量词附加上去，得出谓词逻辑的结论.

重点

1.谓词，个体，全称量词，存在量词，个体域，命题符号化.

2.原子公式，谓词公式，指导变元，自由变元，约束变元，辖域.

3.自由变元的代入，约束变元的换名.

4.赋值，等价，蕴涵.

5.逻辑推理，US规则，UG规则，ES规则，EG规则.

难点

1.正确地进行命题符号化，谓词和个体的引入.

2.计算给定赋值下公式的真值.

3.如何有效地利用US规则，UG规则，ES规则，EG规则并结合命题逻辑中的推理定理、推理规则和证明方法进行谓词逻辑中的逻辑推理.

US、UG、ES、EG四个规则仅对谓词公式最外层的量词适用（即该量词的辖域是去除该量词后的整个公式）.要弄清去掉量词后，个体c是特定的还是任意的.因为如果同时有全称量词的前提和存在量词的前提，最好先引入存在量词的前提.

例题解析

例2.1　试将下列命题符号化：

（1）所有的人都是要死的.

（2）每个自然数都是实数.

（3）一些大学生有远大的理想.

（4）有的学生选修了C++.

（5）不存在最大的自然数.

【分析】对一个命题进行符号化，其关键在于对自然语言中语句之间的逻辑关系以及命题联结词的含义要有正确的理解，确定原子命题并使用适当的联结词.然后分解每个原子命题，找出个体、谓词和量词，选定个体域（或者全总个体域）.在选定全总个体域时，还要引入特性谓词来限制对应个体变元的取值范围.

如（1）中人要死是一个原子命题，个体涉及所有的人.（2）中自然数是实数是一个原子命题，个体涉及所有的自然数.（3）中大学生有远大理想是一个原子命题，个体涉及部分大学生.（4）中学生选修C++是一个原子命题，个体涉及一些学生.（5）的含义也可以理解为“对每一个自然数x，都存在比它大的自然数”，涉及两个自然数的大小关系，自然数x比自然数y大是一个原子命题，个体涉及全体和一些自然数.

解：

如果个体域选定全总个体域，则各个命题可分别符号化为：

（1）（∀x）（S（x）→L（x）），其中特性谓词S（x）：x是人，L（x）：x是要死的.

（2）（∀x）（N（x）→R（x）），其中特性谓词N（x）：x是自然数，R（x）：x是实数.

（3）（∃x）（P（x）∧Q（x）），其中特性谓词P（x）：x是大学生，Q（x）：x有远大理想.

（4）（∃x）（F（x）∧T（x）），其中特性谓词F（x）：x是学生，T（x）：x选修了C++.

（5）（∀x）（N（x）→（∃y）（N（y）∧G（y，x）），其中特性谓词N（x）：x是自然数，G（x，y）：x大于y.

在命题符号化时，如果个体域是全总个体域，则一定要正确地使用特性谓词.当引入特性谓词时，全称量词后跟的是条件式，（∀x）（S（x）→L（x））.存在量词后跟的是合取式，如（∃x）（P（x）∧Q（x））.

如果个体域不是全总个体域，则各个命题可分别符号化为：

（1）（∀x）L（x），其中个体域D：所有的人，L（x）：x是要死的.

（2）（∀x）R（x），其中个体域D：所有的自然数，R（x）：x是实数.(www.xing528.com)

（3）（∃x）Q（x），其中个体域D：所有的大学生，Q（x）：x有远大理想.

（4）（∃x）T（x），其中个体域D：所有的学生，T（x）：：x选修了C++.

（5）（∀x）（∃y）G（y，x），其中个体域D：所有的自然数，G（x，y）：x大于y.

例2.2　求下列各式的真值：

（1）∀x（P（x）∨Q（x）），其中P（x）：x=1，Q（x）：x=2，个体域｛1，2｝.

（2）∀x（P→Q（x））∨R（a），其中P：3＞-2，Q（x）：x≤3，R（x）：x＞5，a：3，个体域｛-2，3，5，6｝.

【分析】对一个约束变元而言，当个体域的元素是有限时，可以将量词去掉：若个体域D=｛a1，a2，…，an｝，则有下式成立：

（1）∀xA（x）⇔A（a1）∧A（a2）∧…∧A（an）.

（2）∃xA（x）⇔A（a1）∨A（a2）∨…∨A（an）.

解：

（1）∀x（P（x）∨Q（x））⇔（P（1）∨Q（1））∧（P（2）∨Q（2））⇔（T∨F）∧（F∨T）⇔T

（2）∀x（P→Q（x））∨R（a）⇔（（P→Q（-2））∧（P→Q（3））∧（P→Q（5））∧（P→Q（6）））∨R（a）

⇔（T∧T∧F∧F）∨F⇔F

例2.3　证明∀x（H（x）→M（x）），∃xH（x）├∃xM（x）.

【分析】由于结论是∃xM（x），因此只需证明存在一些个体c使M（x）成立，然后利用EG规则就可得到.但前提∀x（H（x）→M（x）），∃xH（x）一个有全称量词，另一个有存在量词.所以等先要引入与存在量词有关的前提，利用ES规则.然后再引入与全称量词有关的前提，使用US规则.然后利用命题逻辑中的相关推理定理和推理规则进行推理.

证明：

（1）∃xH（x）　前提引入

（2）H（c）　ES，（1）

（3）∀x（H（x）→M（x））　前提引入

（4）H（c）→M（c）　US，（3）

（5）M（c）　假言推理，（2），（4）

（6）∃xM（x）　EG，（5）

注意（1）（2）和（3）（4）的顺序绝对不能交换.

例2.4　每个学生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有学生都将有所作为，所以，一定有些学生是聪明的.

【分析】对于这种类型的题目，先要进行命题符号化.一般情形下所有的前提都要进行变换，使得能够应用命题逻辑中的推理规则和推理定理.因此一般在引入前提后，都要先用US规则或ES规则去掉量词.最后要用UG规则或EG规则引入量词.

解：

设S（e）：e是学生，A（e）：e将有所作为，D（e）：e是勤奋的，C（e）：e是聪明的，个体域：人的集合，则命题可符号化为：

∀x（S（x）→（D（x）∨C（x））），∀x（D（x）→A（x）），¬∀x（S（x）→A（x））├∃x（S（x）∧C（x））

（1）¬∀x（S（x）→A（x））　前提引入

（2）¬∀x（¬S（x）∨A（x））　置换，（1）

（3）∃x（S（x）∧¬A（x））　置换，（2）

（4）S（a）∧¬A（a）　US，（3）

（5）S（a）　化简，（4）

（6）¬A（a）　化简，（4）

（7）∀x（S（x）→（D（x）∨C（x））　前提引入

（8）S（a）→（D（a）∨C（a））　US，（7）

（9）D（a）∨C（a）　假言推理，（5），（8）

（10）∀x（D（x）→A（x））　前提引入

（11）D（a）→A（a）　US，（10）

（12）¬D（a）　拒取式，（6），（11）

（13）C（a）　析取三段论，（9），（12）

（14）S（a）∧C（a）　合取引入，（5），（13）

（15）∃x（S（x）∧C（x））　EG，（14）