离散数学4.1-谓词基本概念
一、基本元件
| 元件 | 符号 | 说明 | 例子 |
|---|---|---|---|
| 个体词 | a, b, c... | 代表具体对象（常元） | a：小明 |
| 个体变元 | x, y, z... | 代表任意对象 | x 表示论域中任一元素 |
| 谓词 | P(x), Q(x,y)... | 表示性质或关系 | P(x)：x是学生； L(x,y)：x喜欢y |
| 量词 | ∀, ∃ | 修饰个体范围 | ∀x（所有x）； ∃x（存在x） |
| 连接词 | ¬, ∧, ∨, →, ↔ | 命题逻辑五件套 | 组合谓词形成复合公式 |
其中最重要的两个：
∀：全称量词，表示所有取值，如全部、所有等
∃：存在量词，表示部分取值，如有些、部分、一些等
二、论域（个体域）
定义： 量词所讨论的对象的全体集合。
符号化的第一步永远是确定论域。
论域不明确，公式无意义。
常见论域：所有人、所有自然数、全班同学等。
三、符号化核心法则
法则一：全称量词 ∀ 搭配蕴含 →
法则二：存在量词 ∃ 搭配合取 ∧
例题1：
句子： 所有的猫都怕老鼠。
推导过程：
定论域： 所有动物（或所有事物）
定谓词：
C(x)：x 是猫
P(x)：x 怕老鼠
判量词： “所有的” → 全称量词 ∀
套模板： 全称用 →
答案：∀x (C(x) → P(x))
例题2：
句子： 有些学生逃课了。
考点： ∃ 搭配 ∧
推导过程：
定论域： 所有人
定谓词：
S(x)：x 是学生
T(x)：x 逃课了
判量词： “有些” → 存在量词 ∃
套模板： 存在用 ∧
∃x (S(x) ∧ T(x))
四、特殊句式：“只有……才……”
这是最容易混淆的地方，要写成B→A
举例：只有年满 18 岁，才有选举权。
分析：
A：年满 18 岁
B：有选举权
逻辑关系：
“年满18岁”是“有选举权”的必要条件。
没满 18 岁 → 一定没选举权（¬A → ¬B）✅
有选举权 → 一定年满 18 岁（B → A）✅
但年满 18 岁 ⇏ 一定有选举权（可能有其他条件，如未被剥夺政治权利）
符号化：∀x (有选举权(x) → 年满18(x))
五、辖域、约束出现与自由出现
一、辖域
定义
辖域 是量词的作用范围。在一个公式中，量词后面的最短子公式就是该量词的辖域。
判断辖域的方法
量词 ∀x 或 ∃x 出现后，紧跟它的那个子公式（通常用括号界定）就是它的辖域。
例题 1：基本辖域判断
公式： ∀x P(x) → Q(x)
∀x后的P（x）就是辖域
例题 2：括号改变辖域
公式： ∀x (P(x) → Q(x))
∀x 后面紧跟的是括号 (P(x) → Q(x))，所以整个括号内的公式都是 ∀x 的辖域。
例题 3：嵌套量词的辖域
公式： ∀x (P(x) → ∃y L(x,y))
同理：∀x 的辖域：整个 (P(x) → ∃y L(x,y))
∃y的辖域：L(x,y)
二、约束出现与自由出现
定义
| 概念 | 定义 |
|---|---|
| 约束出现 | 变元 x 出现在量词 ∀x 或 ∃x 的辖域内，且被该量词约束 |
| 自由出现 | 变元 x 的出现没有被任何量词 ∀x 或 ∃x 所约束 |
| 指导变元 | 量词 ∀x 或 ∃x 中紧跟量词的那个变元（如 ∀x 中的 x） |
核心判断法则
一个变元的出现是否约束，看它是否在对应量词的辖域内。
例题
指出下列各公式中的指导变元、各量词的辖域、自由出现以及约束出现的个体变项。
（1）∀x(F(x,y)→G(x,z))
量词 ∀
指导变元：x
辖域：F(x,y)→G(x,z)
变元出现情况
约束出现：x（共 2 次）
自由出现：y、z（各 1 次）
（2）∀x(F(x)→G(y))→∃y(H(x)∧L(x,y,z))
① 全称量词 ∀
指导变元：x
辖域：F(x)→G(y)
辖域内变元：x 约束出现，y 自由出现
② 存在量词 ∃
指导变元：y
辖域：H(x)∧L(x,y,z)
辖域内变元：y 约束出现，x,z 自由出现
整体所有变元统计
x：约束出现 1 次，自由出现 2 次
y：自由出现 1 次，约束出现 1 次
z：自由出现 1 次
六、谓词公式分类定义
设 A 为一阶逻辑公式：
永真式（逻辑有效式）
若公式 A 在任意解释、任意赋值下取值均为真，则称 A 为永真式（逻辑有效式）。
矛盾式（永假式）
若公式 A 在任意解释、任意赋值下取值均为假，则称 A 为矛盾式（永假式）。
可满足式
至少存在一组解释与赋值，能使公式 A 的取值为真，则称 A 是可满足式。
七、补充注释
多个量词连用时，量词顺序一般不可随意调换。
例：∀x∃y和∃y∀x 含义不等价，不能互换。
例题：
设论域D={a,b}，与公式∃xA(x)等价的命题公式是（）
解题思路：
量词消去规则（有限论域）
∃x对应逻辑 “或”，所以∃xA(x)⟺A(a)∨A(b)
答案为A(a)∨A(b)
所以绑定关系：
∃x和∨
∀x和∧
