【离散数学】数理逻辑 第二章 谓词逻辑(1) 谓词、量词（全称和存在量词、全总个体域和特性谓词）
本文属于「离散数学」系列文章之一。这一系列着重于离散数学的学习和应用。由于内容随时可能发生更新变动，欢迎关注和收藏离散数学系列文章汇总目录一文以作备忘。此外，在本系列学习文章中，为了透彻理解数学知识，本人参考了诸多博客、教程、文档、书籍等资料。以下是本文的不完全参考目录，在后续学习中还会逐渐补充：
离散数学及其应用 第七版 Discrete Mathematics and Its Applications 7th ，作者是 Kenneth H.Rosen离散数学 第二版，武波等编著，西安电子科技大学出版社
文章目录
1. 谓词、量词1.1 谓词1.1.1 谓词定义、意义1.1.2 谓词与函数、谓词与命题
1.2 量词1.2.1 全称量词
∀
\forall
∀1.2.2 存在量词
∃
\exist
∃1.2.3 全称量化、存在量化1.2.4 全总个体域、特性谓词及其代入规则
1. 谓词、量词
1.1 谓词
1.1.1 谓词定义、意义
一个简单的推理示例，大前提：所有自然数都有大于它的素数；小前提：
2
100
2^{100}
2100 是自然数；结论：
2
100
2^{100}
2100 有大于它的素数。这一推理显然正确，但由于两个前提和结论都是简单命题，它在命题逻辑中得不到证明。同样的还有，大前提：所有人都会死；小前提：苏格拉底是人；结论：苏格拉底会死。另外，给定三个简单命题：甲是老师，乙是老师，丙是老师，命题符号化时要使用三个不同符号，不能反映“是老师”这一共同特征。
为了解决命题逻辑存在的这些问题，引入了谓词的概念。谓词对简单命题进一步分析，找出所描述的对象以及对象间的关系，抽象出同类命题描述的一般模式。如下所示，命题中出现的“2”、“5”、“7”等是具体的个体对象，“…是偶数”刻画对象
x
x
x 的性质，“…小于…”刻画对象
x
x
x 和
y
y
y 之间的关系，“…在…和…之间”刻画对象
x
,
y
,
z
x, y, z
x,y,z 之间的关系：
示例模式2是偶数
x
x
x 是偶数5小于7
x
x
x 小于
y
y
y点a在b和c之间
x
x
x 在
y
y
y 和
z
z
z 之间
用于表示具体或特定个体的符号称为个体常元，常用 a, b, c 等表示。用于表示任意个体的变元称为个体变元，常用 x, y, z 等表示，个体变元的取值范围称为该变元的论域 domain of discourse 或个体域，是一个集合，通常使用大写字母表示。
定义1.1.1 刻画单个个体的特性或多个个体间关系的模式称为谓词 predicate 。
谓词可以简单描述为，由一个谓词符和若干具有固定次序的个体常元或变元组成的表达式。带有
n
(
n
≥
0
)
n\ (n \ge 0)
n (n≥0) 个个体的谓词称为
n
n
n 元谓词，如下所示：
零元谓词，即
n
=
0
n = 0
n=0 时，谓词就是一个命题；一元谓词用于刻画个体的特性，由一个表示个体特性的大写字母（称为特性谓词符、一元谓词符、一元关系符）和一个个体常元或变元组成的表达式表示，如
P
(
a
)
,
Q
(
x
)
P(a),\ Q(x)
P(a), Q(x) 等；
n
n
n 元谓词用于刻画
n
n
n 个个体之间的关系（
n
≥
2
n \ge 2
n≥2 时），由一个表示
n
n
n 个个体关系的大写字母（称为
n
n
n 元谓词符、
n
n
n 元关系符）和
n
n
n 个个体常元或变元组成的表达式表示，如
R
(
a
1
,
a
2
,
…
,
a
n
)
R(a_1, a_2, \dots, a_n)
R(a1,a2,…,an)、
Q
(
x
1
,
x
2
,
…
,
x
n
)
Q(x_1, x_2, \dots, x_n)
Q(x1,x2,…,xn) 等；
因此，“
x
x
x 是偶数”可以用谓词
P
(
x
)
P(x)
P(x) 表示，
P
(
2
)
P(2)
P(2)、
P
(
3
)
P(3)
P(3) 分别表示 “2是偶数”、“3是偶数”；“
x
x
x 小于
y
y
y”可以用谓词
Q
(
x
,
y
)
Q(x, y)
Q(x,y) 表示，
Q
(
5
,
7
)
Q(5, 7)
Q(5,7)、
Q
(
6
,
5
)
Q(6, 5)
Q(6,5) 分别表示“5小于7”、“6小于5”；“
x
x
x 在
y
y
y 和
z
z
z 之间”可以用谓词
R
(
x
,
y
,
z
)
R(x, y, z)
R(x,y,z) 表示。
特别地，某些谓词符/关系符直接使用特殊的习惯符号，如
=
,
≠
,
<
,
>
,
≤
,
≥
=, \ne, \lt, \gt, \le, \ge
=,=,<,>,≤,≥ 等，表达方式可采用中缀表示法，如
x
≠
y
,
x
≤
y
x \ne y, x \le y
x=y,x≤y 等。
谓词也可以使用联结词进行组合，此处的意义与命题逻辑完全相同，如
S
(
x
)
S(x)
S(x) 表示
x
x
x 是学习委员，
W
(
x
)
W(x)
W(x) 表示
x
x
x 是数学课代表，则
S
(
x
)
∧
W
(
x
)
S(x) \land W(x)
S(x)∧W(x) 表示
x
x
x 既是学习委员也是数学课代表。
1.1.2 谓词与函数、谓词与命题
设有谓词
P
(
x
1
,
x
2
,
…
,
x
n
)
P(x_1, x_2, \dots, x_n)
P(x1,x2,…,xn) ，
D
1
,
D
2
,
…
,
D
n
D_1, D_2, \dots, D_n
D1,D2,…,Dn 是个体域集合，其中
x
i
∈
D
i
x_i \in D_i
xi∈Di 。显而易见，
n
n
n 元谓词
P
(
x
1
,
x
2
,
…
,
x
n
)
P(x_1, x_2, \dots, x_n)
P(x1,x2,…,xn) 是从
D
1
×
D
2
×
⋯
×
D
n
D_1\times D_2\times \dots \times D_n
D1×D2×⋯×Dn 到集合
{
T
,
F
}
\{T, F\}
{T,F} 上的一个
n
n
n 元函数。因此，有时也把
P
(
x
1
,
x
2
,
…
,
x
n
)
P(x_1, x_2, \dots, x_n)
P(x1,x2,…,xn) 称为
n
n
n 元命题函数。当
n
=
0
n = 0
n=0 时，谓词
P
P
P 退化为命题。
由于谓词
P
(
x
1
,
x
2
,
…
,
x
n
)
P(x_1, x_2, \dots, x_n)
P(x1,x2,…,xn) 仅是一个函数，它没有真假值。只有将谓词符
P
P
P 指定为一个确定的
n
n
n 元函数，将每个个体变元均代入相应个体域中确定的个体常元，才能得到一个具有确定真假值的命题。
例1 用谓词表示以下命题： （1）小王是大学生。 （2）老张是小张的父亲。 （3）0.7介于0和1之间。 解答： （1）设一元谓词
A
(
x
)
A(x)
A(x) 表示
x
x
x 是大学生，个体常元
c
c
c 表示小王，则
A
(
c
)
A(c)
A(c) 表示小王是大学生。 （2）设二元谓词
B
(
x
,
y
)
B(x,y)
B(x,y) 表示
x
x
x 是
y
y
y 的父亲，个体常元
a
a
a 表示老张，
b
b
b 表示小张，则
B
(
a
,
b
)
B(a, b)
B(a,b) 表示老张是小张的父亲。 （3）设三元谓词
G
(
x
,
y
,
z
)
G(x, y, z)
G(x,y,z) 表示
x
x
x 介于
y
y
y 和
z
z
z 之间，个体常元
a
a
a 表示0.7，
b
b
b 表示0，
c
c
c 表示1，则
G
(
a
,
b
,
c
)
G(a, b, c)
G(a,b,c) 表示0.7介于0和1之间。
1.2 量词
仅仅使用谓词，还不能很好地表达日常生活中的所有命题，如“所有的人都要呼吸”、“有些有理数是自然数”等。为了刻画这类表示全称判断或特称判断的命题，需要引入量词 quantifier 。
1.2.1 全称量词
∀
\forall
∀
∀
x
\forall x
∀x 表示“对于所有的
x
x
x”、“对于任一
x
x
x”、“对于每一个
x
x
x” 。符号
∀
\forall
∀ 称为全称量词 universal quantifier ，
x
x
x 是量词
∀
\forall
∀ 的作用变元或指导变元。例如：
∀
x
P
(
x
)
\forall xP(x)
∀xP(x) 表示“对于所有的
x
x
x 均有
P
(
x
)
P(x)
P(x)”
∀
x
¬
P
(
x
)
\forall x\lnot P(x)
∀x¬P(x) 表示“对于所有的
x
x
x 均有
¬
P
(
x
)
\lnot P(x)
¬P(x)”
¬
∀
x
P
(
x
)
\lnot \forall x P(x)
¬∀xP(x) 表示“并非对于所有的
x
x
x 均有
P
(
x
)
P(x)
P(x)”
¬
∀
x
¬
P
(
x
)
\lnot \forall x \lnot P(x)
¬∀x¬P(x) 表示“并非对于所有的
x
x
x 均有
¬
P
(
x
)
\lnot P(x)
¬P(x)”
1.2.2 存在量词
∃
\exist
∃
∃
x
\exist x
∃x 表示“存在某个
x
x
x”或“至少有一个
x
x
x ”。符号
∃
\exist
∃ 称为存在量词 existential quantifier ，
x
x
x 是量词
∃
\exist
∃ 的作用变元或指导变元。例如：
∃
x
P
(
x
)
\exist xP(x)
∃xP(x) 表示“存在
x
x
x 满足
P
(
x
)
P(x)
P(x)”
∃
x
¬
P
(
x
)
\exist x\lnot P(x)
∃x¬P(x) 表示“存在
x
x
x 满足
¬
P
(
x
)
\lnot P(x)
¬P(x)”
¬
∃
x
P
(
x
)
\lnot \exist x P(x)
¬∃xP(x) 表示“不存在
x
x
x 满足
P
(
x
)
P(x)
P(x)”
¬
∃
x
¬
P
(
x
)
\lnot \exist x \lnot P(x)
¬∃x¬P(x) 表示“不存在
x
x
x 满足
¬
P
(
x
)
\lnot P(x)
¬P(x)”
1.2.3 全称量化、存在量化
在谓词
P
(
x
)
P(x)
P(x) 或
Q
(
x
,
y
)
Q(x, y)
Q(x,y) 等前面加上全称量词
∀
x
\forall x
∀x 或存在量词
∃
x
\exist x
∃x ，则称个体变元
x
x
x 被全称量化或存在量化。要指出的是，如果论域是有限集合，则对某个个体变元的量化可以用命题形式表示（翻译到命题逻辑？）。设论域
D
=
{
a
1
,
a
2
,
…
,
a
n
}
D = \{ a_1, a_2, \dots, a_n\}
D={a1,a2,…,an} ，则有：
∀
x
P
(
x
)
⇔
P
(
a
1
)
∧
P
(
a
2
)
∧
⋯
∧
P
(
a
n
)
∃
x
P
(
x
)
⇔
P
(
a
1
)
∨
P
(
a
2
)
∨
⋯
∨
P
(
a
n
)
\begin{aligned} \forall xP(x) \Leftrightarrow P(a_1) \land P(a_2) \land \dots \land P(a_n)\\ \exist xP(x) \Leftrightarrow P(a_1) \lor P(a_2) \lor \dots \lor P(a_n) \end{aligned}
∀xP(x)⇔P(a1)∧P(a2)∧⋯∧P(an)∃xP(x)⇔P(a1)∨P(a2)∨⋯∨P(an)
对于一个谓词，如果为谓词符指定具体含义，为每个个体变元指定论域，则谓词中的所有变元都会被量词量化，则该命题成为一个具有真假值的命题。
例2 如果论域是整数，指出下列命题的真假值。 （a）
∀
x
(
x
<
x
+
1
)
\forall x ( x \lt x + 1)
∀x(x ∃ x ( x < x + 1 ) \exist x(x \lt x + 1) ∃x(x ∃ x ( x = 3 ) \exist x (x = 3) ∃x(x=3) （d） ∀ x ( x = 3 ) \forall x(x = 3) ∀x(x=3) 解答：如果论域是整数，则 (a), (b), (c) 是真，(d) 是假。这里 x x x 被全称量化或存在量化。 1.2.4 全总个体域、特性谓词及其代入规则 由例2可知，量化后所得命题的真值与个体变元的论域相关。事实上，不同个体变元可以采用完全不同的论域，但不同变元一起讨论时用不同的论域会带来不便，于是引入一个统一的个体论域——全总个体域，它包括所有个体变元所能代表的所有可能的个体。除非特别说明，否则论域默认为全总个体域。此时，对个体变元的变化范围，要用特性谓词来加以限制。 例3 符号化下列命题。 （a）所有的人都是要死的。 （b）有些人不怕死。 解答：设 D ( x ) D(x) D(x) 表示 x x x 是要死的， H ( x ) H(x) H(x) 表示 x x x 是人， F ( x ) F(x) F(x) 表示 x x x 不怕死。 如果论域是人类，则(a)符号化为 ∀ x D ( x ) \forall x D(x) ∀xD(x) ，(b)符号化为 ∃ x F ( x ) \exist x F(x) ∃xF(x) ；如果论域是全总个体域，则大不相同，需要用特性谓词来加以限制： (a)实际上等价于“对于一切 x x x ，如果 x x x 是人，那么 x x x 是要死的”，应表示为 ∀ x ( H ( x ) → D ( x ) ) \forall x(H(x) \to D(x)) ∀x(H(x)→D(x)) ，而非 ∀ x ( H ( x ) ∧ D ( x ) ) \forall x(H(x) \land D(x)) ∀x(H(x)∧D(x)) ；(b)实际上等价于“存在一些 x x x ， x x x 是人，并且 x x x 不怕死”，应表示为 ∃ x ( H ( x ) ∧ F ( x ) ) \exist x(H(x) \land F(x)) ∃x(H(x)∧F(x)) ，而非 ∃ x ( H ( x ) → F ( x ) ) \exist x (H(x) \to F(x)) ∃x(H(x)→F(x)) 。 例3中的 H ( x ) H(x) H(x) 就是特性谓词（即一元谓词），用以刻画个体是“人”这一特性。特性谓词的作用是，限定论域为 （全总个体域中）满足该谓词的所有个体构成的一个特定的论域。例3中特性谓词 H ( x ) H(x) H(x) 的作用如下图所示： 把特性谓词加入到公式时，有以下两条规则： 规则1：对于全称量词，特性谓词作为条件式的前件加入；规则2：对于存在量词，特性谓词作为合取式的合取项加入； 例4 在全总个体域上，使用谓词和量词表示下列命题公式。 （a）所有的有理数都是实数； （b）虽然存在一些大于0的有理数，但是并不是大于0的实数都是有理数。 （c）对于任何一个有理数，都存在大于该有理数的实数。 解答：设 R ( x ) R(x) R(x)： x x x 是实数， Q ( x ) Q(x) Q(x)： x x x 是有理数， G ( x , y ) G(x, y) G(x,y)： x > y x > y x>y ，则： （a） ∀ x ( Q ( x ) → R ( x ) ) \forall x(Q(x) \to R(x)) ∀x(Q(x)→R(x)) ——特性谓词 Q ( x ) Q(x) Q(x) 对于 ∀ \forall ∀，作为条件式的前件 （b） ∃ x ( Q ( x ) ∧ G ( x , 0 ) ) ∧ ¬ ∀ x ( ( R ( x ) ∧ G ( x , 0 ) ) → Q ( x ) ) \exist x (Q(x) \land G(x, 0)) \land \lnot \forall x \big((R(x) \land G(x, 0)) \to Q(x) \big) ∃x(Q(x)∧G(x,0))∧¬∀x((R(x)∧G(x,0))→Q(x)) ——特性谓词 R ( x ) R(x) R(x) 对于 ∀ \forall ∀，作为条件式的前件；特性谓词 Q ( x ) Q(x) Q(x) 对于 ∃ \exist ∃ ，作为合取式的合取项。 （c） ∀ x ( Q ( x ) → ∃ y ( R ( y ) ∧ G ( y , x ) ) ) \forall x(Q(x) \to \exist y(R(y) \land G(y, x))) ∀x(Q(x)→∃y(R(y)∧G(y,x))) ——特性谓词 Q ( x ) Q(x) Q(x) 对于 ∀ \forall ∀，作为条件式的前件；特性谓词 R ( y ) R(y) R(y) 对于 ∃ \exist ∃ ，作为合取式的合取项。