离散数学-Week2

范式

析取范式与合取范式

文字 (Literal)

定义：命题变项及其否定的统称

• 示例：p, ¬q 等

简单析取式 (Simple Disjunction)

定义：有限个文字构成的析取式

• 示例：
• p
• ¬q
• p ∨ ¬q
• p ∨ q ∨ r

简单合取式 (Simple Conjunction)

定义：有限个文字构成的合取式

• 示例：
• p
• ¬q
• p ∧ ¬q
• p ∧ q ∧ r

定理2.3

• (1) 一个简单析取式是重言式当且仅当它同时含某个命题变项和它的否定

• 解释：只有当简单析取式中存在至少一对互补文字（如 p 和 ¬p）时，该析取式才必然为真

• (2) 一个简单合取式是矛盾式当且仅当它同时含某个命题变项和它的否定
• 解释：只有当简单合取式中存在至少一对互补文字（如 p 和 ¬p）时，该合取式才必然为假

析取范式 (Disjunctive Normal Form, DNF)

定义：由有限个简单合取式组成的析取式 一般形式：A₁ ∨ A₂ ∨ … ∨ Aᵣ 其中 A₁, A₂, …, Aᵣ 都是简单合取式

• 示例：
• (p ∧ q) ∨ (¬p ∧ r) ∨ (q ∧ ¬r)

合取范式 (Conjunctive Normal Form, CNF)

定义：由有限个简单析取式组成的合取式 一般形式：A₁ ∧ A₂ ∧ … ∧ Aᵣ 其中 A₁, A₂, …, Aᵣ 都是简单析取式

• 示例：
• (p ∨ q) ∧ (¬p ∨ r) ∧ (q ∨ ¬r)

范式 (Normal Form)

定义：析取范式与合取范式的统称

定理2.4

• (1) 一个析取范式是矛盾式当且仅当它的每一个简单合取式都是矛盾式

• 解释：由于析取范式是多个简单合取式的”或”运算，只有当每个简单合取式都为假时，整个析取范式才为假

• (2) 一个合取范式是重言式当且仅当它的每一个简单析取式都是重言式
• 解释：由于合取范式是多个简单析取式的”与”运算，只有当每个简单析取式都为真时，整个合取范式才为真

范式存在定理

定理2.5 任何命题公式都存在着与之等值的析取范式与合取范式。

求公式范式的步骤：

• (1) 消去任何公式中的联结词→和↔
• (2) 否定的消去(利用双重否定律)或内移(利用德摩根律)
• (3) 利用分配律：利用∧对∨的分配律求析取范式，利用∨对∧的分配律求合取范式

注意：为了清晰和无误，演算中利用交换律，使得每个简单析取式或合取式中命题变项的出现都是按字典顺序，这对下文中求主范式更为重要。

主析取范式与主合取范式

极小项与极大项

定义2.17 在含有n个命题变项的简单合取式（简单析取式）中，若满足以下条件：

1. 每个命题变项均以文字的形式（原变项或其否定）出现
2. 每个命题变项仅出现一次
3. 第i个文字（按下标或字母顺序排列）出现在左起第i位上

称这样的：

• 简单合取式为极小项
• 简单析取式为极大项

说明

• (1) 数量关系：n个命题变项产生 2ⁿ个极小项 和 2ⁿ个极大项
• (2) 互不等值性：2ⁿ个极小项（极大项）均互不等值
• (3) 命名规则：
• 用 mᵢ 表示第i个极小项
  • 其中 i 是该极小项成真赋值的十进制表示
• 用 Mᵢ 表示第i个极大项
  • 其中 i 是该极大项成假赋值的十进制表示
• mᵢ（Mᵢ）称为极小项（极大项）的名称

极小项与极大项（p, q 两个命题变项）

类型	公式	成真赋值	名称	公式	成假赋值	名称
极小项	¬p ∧ ¬q	0 0	m₀	p ∨ q	0 0	M₀
极小项	¬p ∧ q	0 1	m₁	p ∨ ¬q	0 1	M₁
极小项	p ∧ ¬q	1 0	m₂	¬p ∨ q	1 0	M₂
极小项	p ∧ q	1 1	m₃	¬p ∨ ¬q	1 1	M₃

定理2.6 设 mᵢ 与 Mᵢ 是由同一组命题变项形成的极小项和极大项，则：

• ¬mᵢ ⇔ Mᵢ
• ¬Mᵢ ⇔ mᵢ 解释 该定理表明：极小项与对应下标的极大项互为否定关系。即：
• 极小项的否定等价于对应的极大项
• 极大项的否定等价于对应的极小项

  主析取范式与主合取范式

  定义

• 主析取范式：由极小项构成的析取范式
• 主合取范式：由极大项构成的合取范式

示例 当 n=3，命题变项为 p, q, r 时：

• (¬p ∧ ¬q ∧ r) ∨ (¬p ∧ q ∧ r) ⇔ m₁ ∨ m₃ 是主析取范式
• (p ∨ q ∨ ¬r) ∧ (¬p ∨ q ∨ ¬r) ⇔ M₁ ∧ M₅ 是主合取范式

定理2.7 任何命题公式都存在着与之等值的主析取范式和主合取范式，并且是唯一的。

求主析取范式的步骤

设公式 A 含命题变项 p₁, p₂, …, pₙ

1. 求析取范式
   • 将公式 A 化为析取范式 A’ = B₁ ∨ B₂ ∨ … ∨ Bₛ
   • 其中每个 Bⱼ 是简单合取式 (j = 1, 2, …, s)
2. 扩展为极小项
   • 若某个 Bⱼ 既不包含 pᵢ，也不包含 ¬pᵢ
   • 则将 Bⱼ 展开为：
     • Bⱼ ⇔ Bⱼ ∧ (pᵢ ∨ ¬pᵢ) ⇔ (Bⱼ ∧ pᵢ) ∨ (Bⱼ ∧ ¬pᵢ)
   • 重复此过程，直到所有简单合取式都成为长度为 n 的极小项
3. 消去重复项
   • 消去重复出现的极小项
   • 即用 mᵢ 代替 mᵢ ∨ mᵢ
4. 排序
   • 将极小项按下标从小到大排列

求主合取范式的步骤

设公式 A 含命题变项 p₁, p₂, …, pₙ

1. 求合取范式
   • 将公式 A 化为合取范式 A’ = B₁ ∧ B₂ ∧ … ∧ Bₛ
   • 其中每个 Bⱼ 是简单析取式 (j = 1, 2, …, s)
2. 扩展为极大项
   • 若某个 Bⱼ 既不包含 pᵢ，也不包含 ¬pᵢ
   • 则将 Bⱼ 展开为：
     • Bⱼ ⇔ Bⱼ ∨ (pᵢ ∧ ¬pᵢ) ⇔ (Bⱼ ∨ pᵢ) ∧ (Bⱼ ∨ ¬pᵢ)
   • 重复此过程，直到所有简单析取式都成为长度为 n 的极大项
3. 消去重复项
   • 消去重复出现的极大项
   • 即用 Mᵢ 代替 Mᵢ ∧ Mᵢ
4. 排序
   • 将极大项按下标从小到大排列

快速求法

基本原理

设公式含有 n 个命题变项，则：

• 对于简单合取式

• 长度为 k 的简单合取式可展开成 2ⁿ⁻ᵏ 个极小项的析取

• 对于简单析取式
• 长度为 k 的简单析取式可展开成 2ⁿ⁻ᵏ 个极大项的合取

示例1：简单合取式展开为极小项

假设公式含命题变项 p, q, r（n=3）：
q
⇔ (¬p ∧ q ∧ ¬r) ∨ (¬p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r) ∨ (p ∧ q ∧ r)
⇔ m₂ ∨ m₃ ∨ m₆ ∨ m₇

解释：

• 简单合取式 q 长度为 1（k=1）
• 应展开为 2³⁻¹ = 4 个极小项
• 通过补全缺失的变项 p 和 r 的所有可能组合得到

示例2：简单析取式展开为极大项

假设公式含命题变项 p, q, r（n=3）：
p ∨ ¬r
//⇔ (p ∨ ¬r) ∨ (q ∧ ¬q)//或上1
⇔ (p ∨ q ∨ ¬r) ∧ (p ∨ ¬q ∨ ¬r)
⇔ M₁ ∧ M₃

解释：

• 简单析取式 p ∨ ¬r 长度为 2（k=2）
• 应展开为 2³⁻² = 2 个极大项
• 通过补全缺失的变项 q 的所有可能组合得到

主析取范式的用途

1. 求公式的成真赋值和成假赋值

设公式 A 含 n 个命题变项，A 的主析取范式有 s 个极小项，则：

• A 有 s 个成真赋值，它们是极小项下标的二进制表示
• 其余 2ⁿ - s 个赋值都是成假赋值

2. 判断公式的类型

设 A 含 n 个命题变项，则：

• A 为重言式 ⇔ A 的主析取范式含 2ⁿ 个极小项
• A 为矛盾式 ⇔ A 的主析取范式不含任何极小项，记作 0
• A 为可满足式 ⇔ A 的主析取范式中至少含 一个极小项

3. 判断两个公式是否等值

两个公式等值的充分必要条件是它们的主析取范式相同。

应用原理

• 由于主析取范式是唯一的，比较两个公式的主析取范式即可判断它们是否逻辑等价
• 避免了构建复杂真值表的繁琐过程
• 特别适用于证明逻辑等价关系

推理

有效推理

定义2.20若对于每组赋值，A₁∧A₂∧…∧Aₖ 为假，或者当 A₁∧A₂∧…∧Aₖ 为真时，B 也为真，则称由前提 A₁,A₂,…,Aₖ 推出 B 的推理有效或推理正确，并称 B 是有效的结论。

定理2.8 由前提 A₁, A₂, …, Aₖ 推出 B 的推理正确当且仅当 A₁∧A₂∧…∧Aₖ → B 为重言式。

推理的形式结构

形式(1)：A₁ ∧ A₂ ∧ … ∧ Aₖ → B

形式(2)：

• 前提：A₁, A₂, … , Aₖ
• 结论：B 当推理正确时，记作：A₁ ∧ A₂ ∧ … ∧ Aₖ ⇒ B （符号”⇒”表示 A₁ ∧ A₂ ∧ … ∧ Aₖ → B 是重言式）

判断推理是否正确的四种方法：

1. 真值表法：通过构建真值表验证蕴含式是否在所有赋值下都为真
2. 等值演算法：通过逻辑等值变换将蕴含式化简，判断是否为重言式
3. 主析取范式法：通过求主析取范式，检查是否包含所有可能的极小项
4. 构造证明法：使用已知的推理规则和等值式，从前提逐步推导出结论

一阶逻辑基本概念

个体词与个体域

个体词: 所研究对象中可以独立存在的具体或抽象的客体 个体常项: 表示具体事物的个体词, 用a, b, c等表示 个体变项: 表示抽象事物的个体词, 用x, y, z等表示 个体域: 个体变项的取值范围（或称论域） 全总个体域: 宇宙间一切事物组成的个体域

例如 “若x是偶数, 则x能被2整除.” x、偶数和2是个体词, 偶数和2是个体常项, x是个体变项个体域可以是自然数集N, 整数集Z,…, 也可以是全总个体域

谓词:

表示个体词性质或相互之间关系的词      谓词常项: 表示具体性质或相互之间关系的谓词      谓词变项: 表示抽象性质或相互之间关系的谓词 谓词用F,G,H,P等表示

一般的：

• 用F(a)表示个体常项a具有性质F(F是谓词常项或谓词变项);
• 用 F(x) 表示个体变项x具有性质F;
• 用F(a,b) 表示个体常项a,b具有关系F;
• 用 F(x,y)表示个体变项x,y具有关系F

n元谓词 P(x₁, x₂, …, xₙ)：包含n个个体变项的谓词，是定义在个体域上，值域为{0,1}的n元函数。

分类：

1. 一元谓词：表示事物的性质
2. 多元谓词 (n≥2)：表示事物之间的关系
3. 0元谓词：不含个体变项的谓词，即命题常项或命题变项

示例： F(a), G(a,b), P(a₁,a₂,…,aₙ) 等都是0元谓词。 当F, G, P为谓词常项时，0元谓词就是命题。

命题逻辑中的命题都可以表示为0元谓词，因此可以将命题看作是特殊的谓词。

量词

全称量词 ∀

• 表示：任意的、所有的、一切的
• 示例：∀x 表示对个体域中所有的x
• 示例：∀x F(x) 表示所有的x都具有性质F

存在量词 ∃

• 表示：存在、有的、至少有一个
• 示例：∃x 表示在个体域中存在x
• 示例：∃x F(x) 表示存在x具有性质F

一阶逻辑命题符号化

例：在一阶逻辑中将下面命题符号化：
(1) 人都爱美；
(2) 有人用左手写字。
个体域分别取(a) 人类集合和(b) 全总个体域。 解：
(a) 个体域为人类集合：

• (1) 设F(x): x爱美，符号化为 ∀x F(x)。
• (2) 设G(x): x用左手写字，符号化为 ∃x G(x)。 (b) 个体域为全总个体域：
• 设M(x): x为人，F(x)和G(x)同(a)中
• (1) 符号化为 ∀x (M(x) → F(x))。
• (2) 符号化为 ∃x (M(x) ∧ G(x))。 说明：在使用全总个体域时，需要引入特性谓词M(x)来将人与其他事物区分开来。

注意：

• (1) 一元谓词和多元谓词的使用
• (2) 全称量词和存在量词的区别
• (3) 多个量词出现时, 不能随意交换顺序
• (4) 命题的符号化不惟一

一阶语言 L 的字母表定义

定义

定义3.1 一阶语言 L 的字母表包含以下符号：

• (1) 个体常项：a, b, c, …, aᵢ, bᵢ, cᵢ, … (i ≥ 1)
• (2) 个体变项：x, y, z, …, xᵢ, yᵢ, zᵢ, … (i ≥ 1)
• (3) 函数符号：f, g, h, …, fᵢ, gᵢ, hᵢ, … (i ≥ 1)
• (4) 谓词符号：F, G, H, …, Fᵢ, Gᵢ, Hᵢ, … (i ≥ 1)
• (5) 量词符号：∀, ∃
• (6) 联结词符号：¬, ∧, ∨, →, ↔
• (7) 括号与逗号：( , ) , ,

定义3.2 L的项的定义

1. 基本项：个体常项和个体变项是项
2. 复合项：若 φ(x₁, x₂, …, xₙ) 是任意的 n 元函数，t₁, t₂, …, tₙ 是任意的 n 个项，则 φ(t₁, t₂, …, tₙ) 是项
3. 生成规则：所有的项都是有限次使用 (1) 和 (2) 得到的

定义3.3 原子公式 设 R(x₁, x₂, …, xₙ) 是 L 的任意 n 元谓词，t₁, t₂, …, tₙ 是 L 的任意 n 个项，则称 R(t₁, t₂, …, tₙ) 是原子公式

定义3.4：合式公式（谓词公式） L 的合式公式定义如下：

1. 基础：原子公式是合式公式
2. 否定：若 A 是合式公式，则 (¬A) 也是合式公式
3. 联结词：若 A, B 是合式公式，则 (A∧B), (A∨B), (A→B), (A↔B) 也是合式公式
4. 量词：若 A 是合式公式，则 ∀xA, ∃xA 也是合式公式
5. 有限性：只有有限次地应用 (1)~(4) 形成的符号串才是合式公式 合式公式又称谓词公式，简称公式

定义3.5 量词的辖域与变元的出现 在公式 ∀xA 和 ∃xA 中：

• 称 x 为指导变元
• 称 A 为相应量词的辖域
• 在 ∀x 和 ∃x 的辖域中，x 的所有出现称为约束出现
• A 中不是约束出现的其他变项称为自由出现

示例分析

例：公式 ∀x(F(x,y) → ∃yG(x,y,z))

• ∀x 的辖域：(F(x,y) → ∃yG(x,y,z))，指导变元为 x
• ∃y 的辖域：G(x,y,z)，指导变元为 y
• x 的出现：两次出现均为约束出现
• y 的出现：第一次出现为自由出现，第二次出现为约束出现
• z 的出现：自由出现

例：公式 ∀x(F(x) → ∃xG(x))

• ∀x 的辖域：(F(x) → ∃xG(x))，指导变元为 x
• ∃x 的辖域：G(x)，指导变元为 x
• x 的出现：两次出现均为约束出现
• note：第一次出现的 x 是 ∀x 中的 x，第二次出现的 x 是 ∃x 中的 x

重要概念：闭式

闭式：不含自由出现的个体变项的公式