离散数学2.2-主析取/主合取范式

一、基础定义

1. 文字 单个命题变元，或单个变元带一个否定号。

是文字：p、¬q、r
不是文字：p ∧ q、¬(p ∨ q)

2. 简单合取式 若干个文字用 ∧ 连起来，内部只有 ∧。

例：p ∧ ¬q、¬p、p ∧ q ∧ r
若里面出现 A ∧ ¬A，整个式子恒等于 0。

3. 简单析取式 若干个文字用 ∨ 连起来，内部只有 ∨。

例：p ∨ ¬r、q、¬p ∨ q ∨ r
若里面出现 A ∨ ¬A，整个式子恒等于 1。

4. 析取范式 结构：多个简单合取式用 ∨ 连接。

形式：(合取坨1) ∨ (合取坨2) ∨ ...
例：(p ∧ q) ∨ (¬p ∧ r) ∨ ¬q
要求：无 →、↔，¬ 只贴在单个变元上。

5. 合取范式 结构：多个简单析取式用 ∧ 连接。

形式：(析取坨1) ∧ (析取坨2) ∧ ...
例：(p ∨ q) ∧ (¬p ∨ r) ∧ q
要求：同上。

6. 极小项（主析取的"坨"） n 个变元，每个变元恰好出现一次（原身或带否定）的简单合取式，记作 mᵢ。

2 变元 p, q 的全部极小项：

m₀ = ¬p ∧ ¬q
m₁ = ¬p ∧ q
m₂ = p ∧ ¬q
m₃ = p ∧ q

下标规则：变元取值 0 写 ¬，取值 1 写原字母，二进制转十进制即下标。性质：只有唯一一组赋值让该极小项为 1。

7. 主析取范式 所有"坨"都是极小项的析取范式，用 ∨ 连接。

例：m₀ ∨ m₁ ∨ m₃
单个极小项也合法：m₃

8. 极大项（主合取的"坨"） n 个变元，每个变元恰好出现一次（原身或带否定）的简单析取式，记作 Mᵢ。

2 变元 p, q 的全部极大项：

M₀ = p ∨ q
M₁ = p ∨ ¬q
M₂ = ¬p ∨ q
M₃ = ¬p ∨ ¬q

下标规则：变元取值 0 写原字母，取值 1 写 ¬，二进制转十进制即下标。性质：只有唯一一组赋值让该极大项为 0。

9. 主合取范式 所有"坨"都是极大项的合取范式，用 ∧ 连接。

例：M₀ ∧ M₂
单个极大项也合法：¬p ∨ q（即 M₂）

二、通用前置步骤

求任何范式，先做这三步：

消 →：A → B ⇔ ¬A ∨ B
消 ↔：A ↔ B ⇔ (A → B) ∧ (B → A)，再把 → 消掉
¬ 内移（德摩根律）：
- ¬(A ∨ B) ⇔ ¬A ∧ ¬B
- ¬(A ∧ B) ⇔ ¬A ∨ ¬B
- 处理完 ¬ 只贴单个字母

然后根据目标选分配律：

要析取范式：用 A ∧ (B ∨ C) ⇔ (A ∧ B) ∨ (A ∧ C)
要合取范式：用 A ∨ (B ∧ C) ⇔ (A ∨ B) ∧ (A ∨ C)

三、补变量方法

口诀：

求主析取（合取坨缺变量）：补 x ∨ ¬x
- 因为合取坨外面隐含 ∧ 1，而 1 = x ∨ ¬x
求主合取（析取坨缺变量）：补 x ∧ ¬x
- 因为析取坨外面隐含 ∨ 0，而 0 = x ∧ ¬x

四、例题

题型1：求主析取范式

题：求 p → (p ∧ q) 的主析取范式

解：

p → (p ∧ q)

⇔ ¬p ∨ (p ∧ q)（消 →）

⇔ (¬p ∧ (q ∨ ¬q)) ∨ (p ∧ q)（¬p 缺 q，补 q ∨ ¬q）

⇔ (¬p ∧ q) ∨ (¬p ∧ ¬q) ∨ (p ∧ q)（分配律展开）

⇔ m₁ ∨ m₀ ∨ m₃ ⇔ m₀ ∨ m₁ ∨ m₃（下标从小到大排）

对应极小项：

¬p ∧ ¬q → m₀
¬p ∧ q → m₁
p ∧ q → m₃

题型2：同时求主析取与主合取范式

题：求 p → q 的主析取范式和主合取范式

解：

① 先求主合取

p → q ⇔ ¬p ∨ q（消 →）

¬p ∨ q 已包含 p、q 各一次，是极大项。 p=1, q=0 时 ¬p ∨ q = 0，故为 M₂。

主合取范式：M₂

② 再求主析取（两种方法任选）

方法一：补元法

p → q ⇔ ¬p ∨ q

现在是析取范式，但两个坨都缺变量，分别补：

¬p ⇔ ¬p ∧ (q ∨ ¬q)

⇔ (¬p ∧ q) ∨ (¬p ∧ ¬q) q

⇔ q ∧ (p ∨ ¬p)

⇔ (p ∧ q) ∨ (¬p ∧ q)

合并：

⇔ (¬p ∧ q) ∨ (¬p ∧ ¬q) ∨ (p ∧ q) ∨ (¬p ∧ q)

⇔ (¬p ∧ q) ∨ (¬p ∧ ¬q) ∨ (p ∧ q)（¬p ∧ q 重复，幂等律合并）

⇔ m₁ ∨ m₀ ∨ m₃ ⇔ m₀ ∨ m₁ ∨ m₃

方法二：下标互推法

已得主合取为 M₂。 2 变元全集下标 {0,1,2,3}，减掉 {2}，剩 {0,1,3}。主析取即 m₀ ∨ m₁ ∨ m₃。

最终答案：

主析取范式：m₀ ∨ m₁ ∨ m₃
主合取范式：M₂

五、主析取与主合取互推

总变元 n 个，全集下标为 {0, 1, 2, ..., 2ⁿ-1}。

已知主合取下标 → 求主析取：全集减掉极大项下标，剩下即极小项下标，用 ∨ 连接。
- 例：2 变元，主合取 M₂，全集 {0,1,2,3} 减 {2} 得 {0,1,3}，主析取 m₀ ∨ m₁ ∨ m₃
已知主析取下标 → 求主合取：同理，全集减极小项下标，剩下即极大项下标，用 ∧ 连接。

六、书写规范

极小项/极大项内部变量按 p, q, r 固定顺序写
最终答案下标必须从小到大排列：m₀ ∨ m₁ ∨ m₃，不写 m₃ ∨ m₀ ∨ m₁

七、用主范式判断公式类型

永真式：主析取包含全部 2ⁿ 个极小项（即主析取 = 1）
永假式：主合取包含全部 2ⁿ 个极大项（即主合取 = 0）
可满足式：未占满全部下标，同时存在主析取和主合取范式

八、求主析取范式的三种方法

等值补元法：先化到析取范式，缺变量补 x ∨ ¬x，展开得极小项
下标互推法：先求出主合取范式，用全集下标减法直接写出主析取
真值表法：列出所有赋值，挑出使原式为 1 的行，写出对应极小项用 ∨ 连接（变元多时不推荐）

离散数学2.2-主析取/主合取范式

Comments

离散数学

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

More from this blog

离散数学5.1-二元关系一

离散结构5-集合

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

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

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

一、基础定义

二、通用前置步骤

三、补变量方法

四、例题

五、主析取与主合取互推

六、书写规范

七、用主范式判断公式类型

八、求主析取范式的三种方法

Command Palette

Comments

离散数学

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

More from this blog

一、基础定义

二、通用前置步骤

三、补变量方法

四、例题

五、主析取与主合取互推

六、书写规范

七、用主范式判断公式类型

八、求主析取范式的三种方法