本文属于「离散数学」系列文章之一。这一系列着重于离散数学的学习和应用。由于内容随时可能发生更新变动，欢迎关注和收藏离散数学系列文章汇总目录一文以作备忘。此外，在本系列学习文章中，为了透彻理解数学知识，本人参考了诸多博客、教程、文档、书籍等资料。以下是本文的不完全参考目录，在后续学习中还会逐渐补充：

一个简单的推理示例，大前提：所有自然数都有大于它的素数；小前提： 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 之间的关系：

用于表示具体或特定个体的符号称为个体常元，常用 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 元谓词，如下所示：

因此，“ 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 既是学习委员也是数学课代表。

设有谓词 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之间。

仅仅使用谓词，还不能很好地表达日常生活中的所有命题，如“所有的人都要呼吸”、“有些有理数是自然数”等。为了刻画这类表示全称判断或特称判断的命题，需要引入量词 quantifier 。

∀ x \forall x ∀x 表示“对于所有的 x x x”、“对于任一 x x x”、“对于每一个 x x x” 。符号 ∀ \forall ∀ 称为全称量词 universal quantifier ， x x x 是量词 ∀ \forall ∀ 的作用变元或指导变元。例如：

∃ x \exist x ∃x 表示“存在某个 x x x”或“至少有一个 x x x ”。符号 ∃ \exist ∃ 称为存在量词 existential quantifier ， x x x 是量词 ∃ \exist ∃ 的作用变元或指导变元。例如：

在谓词 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 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 ∃ ，作为合取式的合取项。