1. 命题逻辑的局限性
为了研究简单命题句子内部的逻辑关系，我们需要对简单命题进行分解，利用个体词，谓
词和量词来描述它们，并研究个体与总体的内在联系和数量关系，这就是谓词逻辑或一阶逻辑
2. 个体词和谓词
在原子命题中，可以独立存在的客体（句子中的主语、宾语等），称为个体词。而用以
刻划客体的性质或客体之间的关系即是谓词。
个体词可分为两种，个体常量和个体变量，均在个体域内取值。
- 表示具体或特定的个体词称为个体常量。一般用带或不带下标的小写英文字母
a, b, c, · · · , a1, b1, c1, · · · 等表示。 - 表示抽象的或泛指的个体词称为个体变量。一般用带或不带下标的小写英文字母
x, y, z, · · · , x1, y1, z1, · · · 等表示。 - 个体词的取值范围称为个体域 (或论域)，常用 D 表示；
- 宇宙间的所有个体域聚集在一起所构成的个体域称为全总个体域。若无特别说明，
均使用全总个体域
设 D 为非空的个体域，定义
(表示 n 个个体都在个体域 D 上取值) 上取值于{0, 1}上的 n 元
函数，称为 n 元命题函数或 n 元谓词，记为P(x1, x2, · · · , xn)。其中，个体变量x1, x2, · · · , xn ∈ D。
1 表示具体性质或关系的谓词称为谓词常量。
2 表示抽象的或泛指的性质或关系的谓词称为谓词变量。
复合命题的谓词符号化
如果王童是一个三好学生，那么她的学习成绩一定很好。
设 S(x):x 是一个三好学生，H(x)：x 学习成绩好，a：王童,
则该命题符号化为：S(a) → H(a)
李新华是李兰的父亲并且李兰和张三是同班同学。
设 F(x, y):x 是 y 的父亲，M(x, y)：x 与 y 是同班同学，b: 李新华，c: 李兰，d: 张三，
则该命题符号化为：F(b, c) ∧ M(c, d)
3. 量词
全称量词 (∀x): 所有的 x；任意的 x；一切的 x；每一个 x；· · ·
存在量词 (∃x): 有些 x；至少有一个 x；某一些 x；存在 x；· · ·
其中的 x 称为作用变量。一般将其量词加在其谓词之前，记为 (∀x)F(x)，(∃x)F(x)。此时，F(x)称为全称量词和存在量词的辖域。
所有的老虎都要吃人；P(x):x 要吃人。(∀x)P(x),x ∈{老虎}
每一个大学生都会说英语；Q(x):x 会说英语。(∀x)Q(x),x ∈{大学生}
有一些人登上过月球； R(x):x 登上过月球。(∃x)R(x),x ∈{人}
存在自然数是素数。S(x):x 是素数。(∃x)S(x),x ∈{自然数}
更准确的表达
所有的老虎都要吃人；
T(x):x 是老虎，P(x):x 要吃人。(∀x)(T(x) → P(x))
每一个大学生都会说英语；
C(x):x 是大学生，Q(x):x 会说英语。(∀x)(C(x) → Q(x))
有一些人登上过月球；
H(x):x 是人，R(x):x 登上过月球。(∃x)(H(x) ∧ R(x))
存在自然数是素数。
N(x):x 是自然数，S(x):x 是素数。(∃x)(N(x) ∧ S(x)
谓词翻译和真值
设 P(x)：x 是素数；I(x)：x 是整数；Q(x, y)：x+y=0。用语句描述下述句子，并判断其真假值。
(∀x)(I(x) → P(x)); “所有整数都是素数”, 真值为假
(∃x)(I(x) ∧ P(x)) “有一些整数是素数”, 真值为真
(∀x)(∀y)(I(x) ∧ I(y) → Q(x, y))
“对任意整数 x,y 都有 x+y=0”, 真值为假
(∀x)(I(x) → (∃y)(I(y) ∧ Q(x, y)))
“对任意整数 x, 都存在整数 y，使得 x+y=0”, 真值为真
(∃x)(∀y)(I(x) ∧ (I(y) → Q(x, y)))
“存在整数 x, 对任意的整数 y，都有 x+y=0”, 真值为假
谓词逻辑符号化的两条规则
统一个体域为全总个体域，而对每一个句子中个体变量的变化范围用一元特性谓词刻划之。这种特性谓词在加入到命题函数中时必定遵循如下原则：
对于全称量词 (∀x)，刻划其对应个体域的特性谓词作为蕴涵式之前件加入。
对于存在量词 (∃x)，刻划其对应个体域的特性谓词作为合取式之合取项加入。
个体域有限的情况下
特别的，当个体域 D = {x0, x1, · · · , xn} 是有限集合时，(∀x)G(x) 和 (∃x)G(x) 的
真值可以用与之等价的命题公式来进行表示。
(∀x)G(x) = G(x0) ∧ G(x1) ∧ · · · ∧ G(xn)
(∃x)G(x) = G(x0) ∨ G(x1) ∨ · · · ∨ G(xn)
4. 谓词合式公式
若 P(x1, x2, · · · , xn) 是 n 元谓词，t1,t2, · · · ,tn 是项，则称 P(t1,t2, · · · ,tn) 为原子谓词公式，简称原子公式。
满足下列条件的表达式，称为合式公式(well-formed formulae/wff)，简称公式。
- 原子公式是合式公式；
- 若 G，H 是合式公式，则(¬G)，(¬H)，(G ∨ H)，(G ∧ H)，(G → H)，(G ↔ H) 也
是合式公式； - 若 G 是合式公式，x 是个体变量，则(∀x)G、(∃x)G也是合式公式；
- 由有限次使用以上三个规则产生的表达式才是合式公式。
5. 自由变元与约束变元
给定一个合式公式 G，若变元 x 出现在使用变元的量词的辖域之内，则称变元 x 的出现为约束出现，此时的变元 x 称为约束变元。若 x 的出现不是约束出现，则称它为自由出现，此时的变元 x 称为自由变元。
若量词后有括号，则括号内的子公式就是该量词的辖域；(∀x)(· · ·)
若量词后无括号，则与量词邻接的子公式为该量词的辖域。(∀x)F(x)
闭式
设 G 是任意一个公式，若 G 中无自由出现的个体变元，则称 G 为封闭的合式公式，简称闭式。
(∀x)(P(x) → (∃y)R(x, y)) 是闭式；
(∃x)P(x) ∧ Q(x, y) 不是闭式。
6. 公式的解释和真值
设有解释 I 为：
1 个体域为 D = {α, β}；
2 a 指定为：α；
3 f(α) = β, f(β) = α；
4 P(α) = 1, P(β) = 0，Q(α, α) = 0，Q(α, β) = 1，Q(β, α) = 1，Q(β, β) = 1。
判断公式 (∃x)(P(f(x)) ∧ Q(x, f(a))) 在解释 I 下的真值结果。
解:
当x = α时，P(f(x)) ∧ Q(x, f(a)) = P(f(α) ∧ Q(α, f(α))) = P(β) ∧ Q(α, β) = 0 ∧ 1 = 0
当x = β时，P(f(x)) ∧ Q(x, f(a)) = P(f(β) ∧ Q(β, f(α))) = P(α) ∧ Q(β, β) = 1 ∧ 1 = 1
可见原公式真值为真。
7. 前束范式
在命题逻辑里，每一公式都有与之等值的范式，范式是一种统一的表达形式，当研究一个公式的特点 (如永真、永假) 时，范式起着重要作用。对谓词逻辑的公式来说，也有范式，其中前束范式与原公式是等值的，而其它范式与原公式只有较弱的关系。
称公式 G 是一个前束范式，如果 G 中的一切量词都位于该公式的最前端 (不含否定词) 且这些量
词的辖域都延伸到公式的末端。其标准形式如下：
(Q1x1)(Q2x2)· · ·(Qnxn)M(x1, x2, · · · , xn)
其中 Qi 为量词 ∀ 或 ∃(i = 1, · · · n)，M 称作公式 G 的母式 (基式)，M 中不再有量词。
前束范式的求解步骤
1 消去公式中的联结词“→”,“↔”(如果有的话)；
2 反复运用量词转换律，德摩根律和双重否定律，直到将所有的“¬”都内移到原子谓词公式的
前端；
¬(∃x)G(x) = (∀x)¬G(x); ¬(∀x)G(x) = (∃x)¬G(x). (量词转换律)
3 使用谓词的等价公式将所有量词提到公式的最前端并保证其辖域直到公式的末端。
(∃x)G(x) = (∃y)G(y); (∀x)G(x) = (∀y)G(y); (改名规则)
(∀x)(G(x) ∧ H(x)) = (∀x)G(x) ∧ (∀x)H(x); (量词分配律)
(∃x)(G(x) ∨ H(x)) = (∃x)G(x) ∨ (∃x)H(x).
(∀x)G(x) ∨ (∀x)H(x) = (∀x)(∀y)(G(x) ∨ H(y));
(∃x)G(x) ∧ (∃x)H(x) = (∃x)(∃y)(G(x) ∧ H(y)).
(∀x)(G(x) ∨ S) = (∀x)G(x) ∨ S; (∀x)(G(x) ∧ S) = (∀x)G(x) ∧ S; (量词辖域的扩张与收缩律)
(∃x)(G(x) ∨ S) = (∃x)G(x) ∨ S; (∃x)(G(x) ∧ S) = (∃x)G(x) ∧ S
