离散数学： 主范式-主析取范式与主合取范式求解公式汇总

主析取范式与主合取范式求解公式汇总

一、核心定义公式

（一）极小项与极大项定义

1. 极小项（记为 \( m_i \)）

• 定义：含 \( n \) 个命题变元的简单合取式，每个变元或其否定恰出现一次。
• 编码规则：命题变元对应“1”，变元的否定对应“0”，二进制编码转换为十进制数即为下标 \( i \)。
• 示例（\( n=3 \)，变元 \( P,Q,R \)）：
  • \( m_0 = \neg P \land \neg Q \land \neg R \)（编码000）
  • \( m_5 = P \land \neg Q \land R \)（编码101）

2. 极大项（记为 \( M_i \)）

• 定义：含 \( n \) 个命题变元的简单析取式，每个变元或其否定恰出现一次。
• 编码规则：命题变元对应“0”，变元的否定对应“1”，二进制编码转换为十进制数即为下标 \( i \)。
• 示例（\( n=3 \)，变元 \( P,Q,R \)）：
  • \( M_0 = P \lor Q \lor R \)（编码000）
  • \( M_5 = \neg P \lor Q \lor \neg R \)（编码101）

（二）主范式定义

1. 主析取范式：仅由极小项通过“∨”联结而成的范式，形式为 \( m_{i_1} \lor m_{i_2} \lor \dots \lor m_{i_k} \)（\( i_1,i_2,\dots,i_k \) 为成真指派下标）。
2. 主合取范式：仅由极大项通过“∧”联结而成的范式，形式为 \( M_{j_1} \land M_{j_2} \land \dots \land M_{j_m} \)（\( j_1,j_2,\dots,j_m \) 为成假指派下标）。

二、核心性质公式

（一）极小项与极大项关系

1. 互补关系：\( \neg m_i \equiv M_i \)，\( \neg M_i \equiv m_i \)
2. 互斥性：

• 极小项：\( m_i \land m_j \equiv F \)（\( i \neq j \)）
• 极大项：\( M_i \lor M_j \equiv T \)（\( i \neq j \)）

3. 完全性：

• 所有极小项析取：\( m_0 \lor m_1 \lor \dots \lor m_{2^n-1} \equiv T \)
• 所有极大项合取：\( M_0 \land M_1 \land \dots \land M_{2^n-1} \equiv F \)

（二）主范式转换关系

1. 主析取→主合取：若公式 \( G \) 的主析取范式为 \( \lor {m_i | i \in A} \)（\( A \) 为极小项下标集），则主合取范式为 \( \land {M_j | j \notin A} \)（\( j \) 为未出现的极小项下标）。
2. 主合取→主析取：若公式 \( G \) 的主合取范式为 \( \land {M_j | j \in B} \)（\( B \) 为极大项下标集），则主析取范式为 \( \lor {m_i | i \notin B} \)（\( i \) 为未出现的极大项下标）。
3. 特殊公式范式：

• 永真式：主析取范式含全部 \( 2^n \) 个极小项，主合取范式为空。
• 永假式：主合取范式含全部 \( 2^n \) 个极大项，主析取范式为空。

三、求解方法公式（两种核心方法）

（一）真值表法

1. 主析取范式求解步骤：

• 列出公式 \( G \) 的所有真值指派（共 \( 2^n \) 组）。
• 筛选出所有使 \( G \) 为真的指派，对应极小项 \( m_i \)。
• 所有对应极小项析取，即得主析取范式。

2. 主合取范式求解步骤：

• 列出公式 \( G \) 的所有真值指派（共 \( 2^n \) 组）。
• 筛选出所有使 \( G \) 为假的指派，对应极大项 \( M_j \)。
• 所有对应极大项合取，即得主合取范式。

（二）公式化归法（逻辑等价变换）

1. 通用预处理步骤：

• 消去蕴涵与等价联结词：
  • \( P \rightarrow Q \equiv \neg P \lor Q \)
  • \( P \leftrightarrow Q \equiv (P \rightarrow Q) \land (Q \rightarrow P) \equiv (\neg P \lor Q) \land (P \lor \neg Q) \)
• 否定联结词内移（德摩根律）：
  • \( \neg (P \lor Q) \equiv \neg P \land \neg Q \)
  • \( \neg (P \land Q) \equiv \neg P \lor \neg Q \)
  • \( \neg (\neg P) \equiv P \)
• 消除多余否定与重复变元：利用 \( P \land P \equiv P \)、\( P \lor P \equiv P \) 化简。

2. 主析取范式专用步骤：

• 化为析取范式：利用 \( P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R) \) 分配律展开。
• 补全缺省变元：对每个简单合取式，若缺变元 \( P \)，则用 \( P \equiv P \land (Q \lor \neg Q) \) 补全，再分配展开。
• 去重排序：删除重复极小项，按下标递增排序。

3. 主合取范式专用步骤：

• 化为合取范式：利用 \( P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R) \) 分配律展开。
• 补全缺省变元：对每个简单析取式，若缺变元 \( P \)，则用 \( P \equiv P \lor (Q \land \neg Q) \) 补全，再分配展开。
• 去重排序：删除重复极大项，按下标递增排序。

四、示例应用公式

（一）示例：求 \( G = (P \rightarrow \neg Q) \lor R \) 的主范式（\( n=3 \)，变元 \( P,Q,R \)）

1. 主析取范式（公式化归法）：

• 预处理：\( G \equiv (\neg P \lor \neg Q) \lor R \equiv \neg P \lor \neg Q \lor R \)
• 补全变元：
  • \( \neg P \equiv \neg P \land (Q \lor \neg Q) \land (R \lor \neg R) = m_0 \lor m_1 \lor m_4 \lor m_5 \)
  • \( \neg Q \equiv (P \lor \neg P) \land \neg Q \land (R \lor \neg R) = m_0 \lor m_2 \lor m_4 \lor m_6 \)
  • \( R \equiv (P \lor \neg P) \land (Q \lor \neg Q) \land R = m_1 \lor m_3 \lor m_5 \lor m_7 \)
• 析取去重：\( G \equiv m_0 \lor m_1 \lor m_2 \lor m_3 \lor m_4 \lor m_5 \lor m_6 \lor m_7 \)（永真式）

2. 主合取范式：因 \( G \) 为永真式，主合取范式为空。