引言
在逻辑学中，析取范式（Disjunctive Normal Form，DNF）和合取范式（Conjunctive Normal Form，CNF）是两种基本的逻辑公式形式。它们在逻辑推理、计算机科学和数学证明中有着广泛的应用。本文将为你详细介绍这两种范式的要点，帮助你快速掌握它们。
析取范式（DNF）
概念
析取范式是由多个子句构成的逻辑公式，每个子句是合取（AND）多个命题变元的析取（OR）。
表示形式
DNF 可以表示为： $\( \phi = \bigvee_{i=1}^{n} \bigwedge_{j=1}^{m} p_{ij} \)\( 其中，\)n\( 是子句的数量，\)m$ 是每个子句中命题变元的数量。
要点
- 子句：DNF 中的每个子句都是一个合取表达式，表示为 \(\bigwedge_{j=1}^{m} p_{ij}\)。
- 析取：所有子句之间用析取运算符 \(\bigvee\) 连接。
- 命题变元：每个子句中的命题变元可以是命题变元的否定，但不能同时出现。
- 真值表：DNF 的真值表具有以下特点：
- 如果所有子句都为假，则整个公式为假。
- 如果至少有一个子句为真，则整个公式为真。
例子
假设有一个 DNF 公式： $\( \phi = (p \wedge q) \vee (\neg p \wedge r) \)\( 这个公式包含两个子句：\)(p \wedge q)\( 和 \)(\neg p \wedge r)$。
合取范式（CNF）
概念
合取范式是由多个子句构成的逻辑公式，每个子句是析取（OR）多个命题变元的合取（AND）。
表示形式
CNF 可以表示为： $\( \psi = \bigwedge_{i=1}^{n} \bigvee_{j=1}^{m} p_{ij} \)\( 其中，\)n\( 是子句的数量，\)m$ 是每个子句中命题变元的数量。
要点
- 子句：CNF 中的每个子句都是一个析取表达式，表示为 \(\bigvee_{j=1}^{m} p_{ij}\)。
- 合取：所有子句之间用合取运算符 \(\bigwedge\) 连接。
- 命题变元：每个子句中的命题变元不能同时出现。
- 真值表：CNF 的真值表具有以下特点：
- 如果所有子句都为假，则整个公式为假。
- 如果至少有一个子句为真，则整个公式为真。
例子
假设有一个 CNF 公式： $\( \psi = (p \vee q) \wedge (\neg p \vee r) \)\( 这个公式包含两个子句：\)(p \vee q)\( 和 \)(\neg p \vee r)$。
总结
掌握析取范式和合取范式对于逻辑推理和数学证明具有重要意义。本文简要介绍了这两种范式的概念、表示形式和要点，希望能帮助你快速掌握它们。在实际应用中，请根据具体问题灵活运用。