离散数学题型梳理-第7章

离散数学常考题型梳理

第7章 谓词逻辑

一、题型分析

本章主要介绍谓词逻辑的基本概念、基本定理与方法等．经常涉及到的题型有：

7-1谓词公式的翻译

7-2求辖域、约束变元、自由变元、变元换名

7-3在有限个体域下消去量词

7-4谓词推理演算

因此，在本章学习过程中希望大家要清楚地知道：

1．谓词

用以描述个体的性质或个体间关系的语法模式称为谓词．谓词命名式是谓词与个体和个体变元结合的表示形式．谓词命名式也简称为谓词．

谓词一般用大写字母P 、Q 、R 等表示，个体一般用小写字母a 、b 、c 等表示，个体变元就一般用小写字母x 、y 、z 等表示．

谓词可以写成P (x ，y ) 、H (x ，y ，z ) 、F (x ) 等形式．

2．量词

将表明个体取值量上的词“任意”、“所有的”、“全部”、“凡是”、“一切”等称为全称量词．全称量词用∀表示．

将表明个体取值量上的词“存在”、“有的”、“有些”、“至少有”等称为存在量词．存在量词用∃表示．

在书写谓词时，通常将个体变元的个体域定义为全总个体域，然后根据需要对各个不同的个体应用描述个体特性的谓词（称为特性谓词）来加以约束限制．

在谓词形式中，特性谓词的加入有两条规则：

(1) 对全称量词，特性谓词作为蕴含式（条件式）的前件加入．

(2) 对存在量词，特性谓词作为合取项加入．

即在命题符号化时要注意：使用全称量词∀，特性谓词后用→；使用存在量词∃，特性谓词后用∧．

设G (x ) 是一元谓词，个体域为D ．则

命题∀xG (x ) 的真值：

∀xG (x ) 取1值当且仅当对任意x ∈D ，G (x ) 都取1值．

∀xG (x ) 取0值当且仅当有一个x 0∈D ，使得G (x 0) 取0值．

命题∃xG (x ) 的真值：

∃xG (x ) 取1值当且仅当有一个x 0∈D ，使得G (x 0) 取1值．

∃xG (x ) 取0值当且仅当对任意x ∈D ，G (x ) 都取0值．

3．谓词公式

谓词公式可由下述各条规则组成：

(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)至(4)构成的公式为合式公式．

由上定义知，命题演算公式也是谓词合式公式．

4．变元的约束

对于 (∃x ) P (x ) 或 (∀x ) P (x ) 形式的公式，∃或∀后面所跟的个体变元x 称为相应量词的指导变元．

紧接于量词之后最小的子公式称为量词的辖域．

在量词的辖域内指导变元的一切出现均称为变元的约束出现．约束出现的变元称为约束变元．

在公式中，变元的非约束出现称为变元的自由出现．自由出现的变元称为自由变元．

约束变元的换名规则：对约束变元进行换名，即将量词辖域中出现的某个约束变元和相应的指导变元，换成另一个辖域中未曾出现过的变元符号，公式中的其余部分不变．

自由变元的代入规则：对自由变元进行代入，即对自由变元用与原公式中所有变元不同的符号去代替，并且处处代替．

5．在有限个体域下消去量词

当个体域为有限集合{a 1，a 2，…，a n }时，消去量词的规则为：

(∀x ) P (x ) ⇔P (a 1) ∧P (a 2) ∧…∧P (a n )

(∃x ) P (x ) ⇔P (a 1) ∨P (a 2) ∨…∨P (a n )

6．推理理论

谓词演算的推理是命题演算推理的推广和扩充，命题演算中的基本等价式，重言蕴含式以及P 规则、T 规则、CP 规则在谓词演算中仍然适用．

谓词逻辑中几个常用的等价式：

⌝(∀x ) P (x ) ⇔(∃x ) ⌝P (x )

⌝(∃x ) P (x ) ⇔(∀x ) ⌝P (x )

(∀x )(A (x ) ∨B ) ⇔(∀x ) A (x ) ∨B

(∀x )(A (x ) ∧B ) ⇔(∀x ) A (x ) ∧B

(∃x )(A (x ) ∨B ) ⇔(∃x ) A (x ) ∨B

(∃x )(A (x ) ∧B ) ⇔(∃x ) A (x ) ∧B

（注：子公式B 中不出现约束变元x ）

(∀x )(A (x ) ∧B (x )) ⇔(∀x ) A (x ) ∧(∀x ) B (x )

(∃x )(A (x ) ∨B (x )) ⇔(∃x ) A (x ) ∨(∃x ) B (x )

谓词逻辑的推理演算新增加了添加与消去量词的四条规则：

(1) 全称指定规则（全称量词消去规则），表示为US ，即：

P (c )

此规则是对量词约束的变元任意指定一个个体，其逻辑含义是，如果(∀x ) P (x ) 成立，则可以任取个体域中某个任意的个体c ，而P (c ) 也是成立的．

(2) 全称推广规则（全称量词附加规则），表示为UG ，即：

(∀x ) P (x )

此规则是对使得谓词P 成立的个体c 进行推广，其逻辑含义是，如果对于个体域中任意的个体c ，有P (c ) 成立，则(∀x ) P (x ) 也成立．

(3) 存在指定规则（存在量词消去规则），表示为ES ，即：

P (c )

此规则是对量词约束的变元指定一个个体，其逻辑含义是，如果(∃x ) P (x ) 成立，则个体域中有某个个体c 使得P (c ) 成立．

(4) 存在推广规则（存在量词附加规则），表示为EG ，即：

(∃x ) P (x )

此规则是对使得谓词P 成立的个体c 进行推广，其逻辑含义是，如果对于个体域中存在某个个体c ，使P (c ) 成立，则(∃x ) P (x ) 也成立．

二、常考知识点分析

常考知识点1：命题公式的翻译（历年考核次数：5次，本课程共考过6次；重要程度：★★★★★）

（2008年7月试卷第13题）将语句“有人去上课．”翻译成谓词公式．

[解题过程] 设P (x ) ：x 是人，Q (x ) ：x 去上课．则语句“有人去上课．”翻译成谓词公式为

(∃x )(P (x ) ∧Q (x )) ．

易错点：有同学会误表示为(∃x )(P (x ) →Q (x )) ．

提示：用存在量词“∃”来表明个体的取值量，对各个不同的个体应用描述个体特性的特性谓词P (x ) 来加以约束限制时，特性谓词作为合取项加入．

（2009年1月试卷第13题）将语句“所有的人都学习努力．”翻译成谓词公式．

[解题过程] 设P (x ) ：x 是人，Q (x ) ：x 学习努力．则语句“所有的人都学习努力．”翻译成谓词公式为

(∀x )(P (x ) →Q (x )) ．

易错点：有同学会误表示为(∀x )(P (x ) ∧Q (x )) ．

提示：用全你量词“∀”来表明个体的取值量，对各个不同的个体应用描述个体特性的特性谓词P (x ) 来加以约束限制时，特性谓词作为条件式的前件加入．

常考知识点2：量词辖域、约束变元、自由变元（历年考核次数：3次，本课程共考过6次；重要程度：★★★）

（2008年9月试卷第16题）

设谓词公式∃x (P (x , y ) →∀zQ (y , x , z )) ∧∀yR (y , z ) F (y ) ，试

（1）写出量词的辖域；（2）指出该公式的自由变元和约束变元．

[解题过程] （1）量词∃的辖域为(P (x , y )

第1个量词∀的辖域为Q (y , x , z ) ，

第2个量词∀的辖域为R (y , z ) ．

（2）(P (x , y ) →∀zQ (y , x , z )) →∀zQ (y , x , z )) ， 与F (y ) 中的y ，以及R (y , z ) 中的z 为自由变元． (P (x , y ) →∀zQ (y , x , z )) 中的x ，Q (y , x , z ) 中的z ，以及R (y , z ) 中的y 为约束变元．

易错点：求辖域容易出错，要注意式中括号的配对．

提示：紧跟量词后面的个体变元为该量词的指导变元，在该量词的辖域中与指导变元相同的变元为约束变元，与指导变元不同的或不在任何量词的辖域中的变元为自由变元。

常考知识点3：变元换名（历年考核次数：2次，本课程共考过6次；重要程度：★★）

（2009年7月试卷第13题）下面的推理是否正确，试予以说明．

(1) (∀x ) F (x ) →G (x ) 前提引入

(2) F (y ) →G (y ) US （1）．

[解题过程] 错误．

第2步应为：F (y ) ∧G (x )

因为F (x ) 中的x 是约束变元，而G (x ) 中的x 是自由变元，换名时，约束变元与自由变元不能混淆．

易错点：约束变元与自由变元容易混淆．

提示：详细过程应为：

(1) ∀xF (x ) ∧G (x ) 前提引入

(2) ∀uF (u ) ∧G (x ) T (1)换名规则

(3) ∀u (F (u ) ∧G (x )) T (2)

(4) F (y ) ∧G (x ) U S(3)

常考知识点4：在有限个体域下消去量词（历年考核次数：5次，本课程共考过6次；重要程度：★★★★★）

（2008年7月试卷第10题）设个体域

(∀x ) A (x ) ∧D ={a , b }，则谓词公式∃(x ) B (消去量词后的等值式为x ．

答 (A (a ) ∧A (b )) ∧(B (a ) ∨B (b ))

[解题过程] (∀x ) A (x ) ⇔A (a ) ∧A (b ) ，(∃x ) B (x ) ⇔B (a ) ∨B (b ) ，所以

(∀x ) A (x ) ∧(∃x ) B (x ) ⇔(A (a ) ∧A (b )) ∧(B (a ) ∨B (b ))

易错点：容易用错合取、析取符号．

提示：当个体域为有限集合{a 1，a 2，…，a n }时，消去量词的规则为：

(∀x ) P (x ) ⇔P (a 1) ∧P (a 2) ∧…∧P (a n )

(∃x ) P (x ) ⇔P (a 1) ∨P (a 2) ∨…∨P (a n )

常考知识点5：谓词推理演算（历年考核次数：1次，本课程共考过6次；重要程度：★★）

（2008年7月试卷第19题）试证明(∃x )(P (x ) ∧

[证明过程]

（1）(∃x )(P (x ) ∧

（2）P (a ) ∧R (a ) R (x )) ⇒(∃x ) P (x ) ∧(∃x ) R (x ) ． R (x )) P ES （1）

（3）P (a ) T （2）I (化简规则)

（4）(∃x ) P (x ) EG （3）

（5）R (a ) T （2）I (化简规则)

（6）(∃x ) R (x ) EG （5）

（7）(∃x ) P (x ) ∧(∃x ) R (x ) T （4）（6）I

易错点：推理规则不易理解和掌握．

提示：（1）式引入前提后，根据存在指定规则提到（2）式，根据化简规则得到（3）式、（5）式，再根据存在推广规则分别得到（4）式、（6）式，最后根据合取引入规则要证明的结果（7）式．

三、模拟练习

练习1：（2008年9月试卷第13题）将语句“所有人都去工作．”翻译成谓词公式．

练习2：（2009年7月试卷第5题）设A (x ) ：x 是人，B (x ) ：x 是学生，则命题“不是所有人都是学生”可符号化为（ ）．

A ．(∀x )(A (x ) ∧B (x )) B ．⌝(∃x )(A (x ) ∧B (x ))

C ．⌝(∀x )(A (x ) →B (x )) D ．⌝(∃x )(A (x ) ∧⌝B (x ))

练习3：（2009年10月试卷第5题）设A (x ) ：x 是人，B (x ) ：x 是工人，则命题“有人是工人”可符号化为（ ）．

A ．(∃x )(A (x ) ∧B (x )) B ．(∀x )(A (x ) ∧B (x ))

C ．⌝(∀x )(A (x ) →B (x )) D ．⌝(∃x )(A (x ) ∧⌝B (x ))

练习4：（2009年1月试卷第10题）(∀x )(P (x ) →Q (x ) ∨R (x ，y )) 中的自由变元为 ．

练习5：（2010年1月试卷第17题）

设谓词公式(∃x )(A (x , y ) →

（1）写出量词的辖域；

（2）指出该公式的自由变元和约束变元．

练习6：将下列表达式中的变元换名，使得约束变元不是自由的，自由变元不是约束的：

∀xP (x , y ) ∨Q (z ) ∨∃y (R (x , y ) ∨∀zS (z )) ．

练习7：（2008年9月试卷第10题）设个体域D ＝{1,2}，则谓词公式∃xA (x ) 消去量词后的等值式为 ．

练习8：（2009年7月试卷第10题）设个体域D ＝{a , b , c }，则谓词公式(∀x ) A (x ) 消去量词后的等值式为 ．

练习9：（2009年10月试卷第10题）设个体域D ＝{1, 2, 3}，P (x ) 为“x 小于2”，则谓词公式(∀x ) P (x ) 的真值为 ．

练习10：（2010年1月试卷第10题）设个体域D = {1，2}，A (x ) 为“x 大于1”，则谓词公式(∃x ) A (x ) 的真值为

练习11：试证明∀xA (x ) ∨∀xB (x ) ⇒∀x (A (x ) ∨B (x )) (∀z ) B (y , x , z )) ，试

四、模拟练习解答

1．解 设P (x ) ：x 是人，Q (x ) ：x 去工作．

则语句翻译成谓词公式为：(∀x )(P (x ) →Q (x )) ．

解析 这里“所有”用全称量词表示．带全称量词的公式，特性谓词P (x ) 应作为蕴含式（条件式）的前件加入，所以P (x ) 后面使用符号“→”．

2．答 C

解析 选项A ，错了．

带全称量词的公式，特性谓词A (x ) 应作为蕴含式（条件式）的前件加入，A (x ) 后面应使用符号“→”．

选项B ，错了．

其逻辑含义是“没有人是学生”．

选项C ，正确．

这里“所有”用全称量词表示．带全称量词的公式，特性谓词A (x ) 应作为蕴含式（条件式）的前件加入，所以A (x ) 后面使用符号“→”．(∀x )(A (x ) →B (x )) 的逻辑含义是“所有人都是学生”，原命题是它的否定．

选项D ，错了．

其逻辑含义是“没有人不是学生”．

3．答 A

解析 选项A ，正确．

这里“有”用存在量词表示．带存在量词的公式，特性谓词A (x ) 应作为合取项加入，所以此处A (x ) 后面使用符号“∧”．

选项B ，错了．

带全称量词的公式，特性谓词A (x ) 应作为蕴含式（条件式）的前件加入，A (x ) 后面应使用符号“→”．

选项C ，错了．

其逻辑含义是“不是所有人都是工人”．

选项D ，错了．

其逻辑含义是“没有人不是工人”．

4．答 y

解析 在量词∀的辖域P (x ) →Q (x ) ∨R (x ，y ) 中，变元y 不受该量词的指导变元

x 的约束，所以y 是自由就元．

5．解 （1）量词∃的辖域为A (x , y ) →

量词∀的辖域为B (y , x , z ) ．

（2）A (x , y ) →(∀z ) B (y , x , z ) 中的(∀z ) B (y , x , z ) ， y 为自由变元．

A (x , y ) →(∀z ) B (y , x , z ) 中的x 和B (y , x , z ) 中的z 为约束变元．

(∀z ) B (y , x , z ) ，它即解析 （1）紧接于量词∃之后最小的子公式为A (x , y ) →

为量词∃的辖域．紧接于量词∀之后最小的子公式为B (y , x , z ) ，它即为量词∀的辖域．

（2）在量词∃的辖域A (x , y ) →

元x 的约束，所以y 是自由变元．

在量词∃的辖域A (x , y ) →(∀z ) B (y , x , z ) 中，变元(∀z ) B (y , x , z ) 中，变元y 不受该量词的指导变x 是指导变元的约束出现，因而是约束变元．在量词∀的辖域B (y , x , z ) 中，变元z 是指导变元的约束出现，因而是约束变元．

6．解 ∀xP (x , y ) ∨Q (z ) ∨∃y (R (x , y ) ∨∀zS (z ))

⇔∀uP (u , y ) ∨Q (z ) ∨∃v (R (x , v ) ∨∀wS (w ))

（或⇔∀xP (x , v ) ∨Q (w ) ∨∃y (R (u , y ) ∨∀zS (z )) ）

解析 P (x , y ) 中的x 、R (x , y ) ∨∀zS (z ) 中的y 、S (z ) 中的z 为约束变元， 而R (x , y ) ∨∀zS (z ) 中的x 、P (x , y ) 中的y 、Q (z ) 中的z 为自由变元．

变元换名可对公式中的约束变元x 、y 、z 分别换名为u 、v 、w （或对公式中的自由变元x 、y 、z 分别换名为u 、v 、w ）．

7．答 A (1)∨A (2)

解析 当个体域为有限集合{a 1，a 2，…，a n }时，消去存在量词∃的规则为：

(∃x ) P (x ) ⇔P (a 1) ∨P (a 2) ∨…∨P (a n )

8．答 A (a ) ∧A (b ) ∧A (c )

解析 当个体域为有限集合{a 1，a 2，…，a n }时，消去全称量词∀的规则为：

(∀x ) P (x ) ⇔P (a 1) ∧P (a 2) ∧…∧P (a n )

9．答 0（或F ，或假）

解析 (∀x ) P (x ) ⇔P (1)∧P (2)∧P (3)⇔1∧0∧0⇔0

10．答 1

解析 (∃x ) A (x ) ⇔A (1)∨A (2)⇔0∨1⇔1

11．证明 (1) ∀xA (x ) ∨∀xB (x ) P

(2) ∀xA (x ) ∨∀yB (y ) T (1)（换名规则）

(3) ∀x ∀y (A (x ) ∨B (y )) T (2)（量词辖域扩张）

(4) ∀y (A (a ) ∨B (y )) US (3)

(5) A (a ) ∨B (a ) US (4)

(6) ∀x (A (x ) ∨B (x )) UG (5)

解析 不能从(1)式直接得出A (a ) ∨∀xB (x ) 或∀xA (x ) ∨B (a ) ，因为没有相关规则．

证明二（反证法）

(1) ⌝(∀x (A (x ) ∨B (x ))) P （附加前提）

(2) ∃x (⌝A (x ) ∧⌝B (x )) T (1)

(3) ⌝A (a ) ∧⌝B (a ) ES (2)

(4) ⌝A (a ) T (3)

(5) ∃x ⌝A (x ) EG (4)

(6) ⌝∀xA (x ) T (5)

(7) ∀xA (x ) ∨∀xB (x ) P

(8) ∀xB (x ) T (6)(7)（析取三段论）

(9) ⌝B (a ) T (3)

(10) ∃x ⌝B (x ) EG (9)

(11) ⌝∀xB (x ) T (10)

(12) ∀xB (x ) ∧⌝∀xB (x ) T (8)(11)（合取引入）

(13) ∀x (A (x ) ∨B (x )) 反证法