离散数学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和∧

离散数学4.1-谓词基本概念

Comments

离散数学

离散结构5-集合

More from this blog

离散数学5.1-二元关系一

离散结构5-集合

离散数学3-命题逻辑推理理论

离散数学2.3-联结词的完备集

一、基本元件

二、论域（个体域）

三、符号化核心法则

法则一：全称量词 ∀ 搭配蕴含 →

法则二：存在量词 ∃ 搭配合取 ∧

四、特殊句式：“只有……才……”

五、辖域、约束出现与自由出现

一、辖域

定义

判断辖域的方法

二、约束出现与自由出现

定义

核心判断法则

六、谓词公式分类定义

七、补充注释

Command Palette

Comments

离散数学

离散结构5-集合

More from this blog

一、基本元件

二、论域（个体域）

三、符号化核心法则

法则一：全称量词 ∀ 搭配蕴含 →

法则二：存在量词 ∃ 搭配合取 ∧

四、特殊句式：“只有……才……”

五、辖域、约束出现与自由出现

一、辖域

定义

判断辖域的方法

二、约束出现与自由出现

定义

核心判断法则

六、谓词公式分类定义

七、补充注释