离散数学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₂）

---

二、通用前置步骤

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

1. 消 →：A → B ⇔ ¬A ∨ B

2. 消 ↔：A ↔ B ⇔ (A → B) ∧ (B → A)，再把 → 消掉

3. ¬ 内移（德摩根律）：

   • ¬(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）

• 可满足式：未占满全部下标，同时存在主析取和主合取范式

---

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

1. 等值补元法：先化到析取范式，缺变量补 x ∨ ¬x，展开得极小项

2. 下标互推法：先求出主合取范式，用全集下标减法直接写出主析取

3. 真值表法：列出所有赋值，挑出使原式为 1 的行，写出对应极小项用 ∨ 连接（变元多时不推荐）