析取范式、合取范式
| 析取范式 | |
|---|---|
| 术语名称 | 析取范式 |
| 英语名称 | disjunctive normal form |
| 别名 | DNF, OR of ANDs, sum of products |
| 合取范式 | |
|---|---|
| 术语名称 | 合取范式 |
| 英语名称 | conjunctive normal form |
| 别名 | CNF, AND of ORs, product of sums |
命题公式可以表示为等值的标准形式。 合取的析取称为析取范式(disjunctive normal form, DNF)，析取的合取称为合取范式(conjunctive normal form, CNF)。 析取范式和合取范式是命题公式的两种重要的标准形式。
定义
定义范式前，需要明确一些文法概念进行构造。
文字
| 原子公式 | |
|---|---|
| 术语名称 | 原子公式 |
| 英语名称 | atomic formula |
| 别名 | 原子, atom, prime formula |
| 文字 | |
|---|---|
| 术语名称 | 文字 |
| 英语名称 | literal |
| 肯定文字 | |
|---|---|
| 术语名称 | 肯定文字 |
| 英语名称 | positive literal |
| 否定文字 | |
|---|---|
| 术语名称 | 否定文字 |
| 英语名称 | negative literal |
| 极性 | |
|---|---|
| 术语名称 | 极性 |
| 英语名称 | polarity |
| 互补文字 | |
|---|---|
| 术语名称 | 互补文字 |
| 英语名称 | complementary literal |
| 别名 | 互补对, complementary pair |
- 不含逻辑联结词的命题公式，即原子命题，称为原子公式(atomic formula)或原子(atom)，在命题逻辑范围内通常是命题变元；
- 原子公式称为肯定文字(positive literal)、原子公式的否定称为否定文字(negative literal)，合称文字(literal)。其中的肯定否定称为其极性(polarity)。
- 一组互为否定的文字称为一对互补文字(complementary literals)或互补对(complementary pair)。
注：
- 可以认为原子命题的定义就是不含逻辑联结词。在命题逻辑中是命题变元，但命题逻辑以外可以有其他情况。
- 文字指包含原子公式及其否定。需要注意，尽管 [math]\displaystyle{ P }[/math] （原子公式）和 [math]\displaystyle{ \lnot P }[/math] （原子公式的否定）都是文字，但是如 [math]\displaystyle{ \lnot \lnot P }[/math] 的形式则不是一个文字。
析取式、合取式
| 析取式 | |
|---|---|
| 术语名称 | 析取式 |
| 英语名称 | disjunctive clause |
| 别名 | 子句, clause |
| 合取式 | |
|---|---|
| 术语名称 | 合取式 |
| 英语名称 | conjunctive clause |
| 别名 | 短语 |
- 有限个文字的析取称为析取式或子句(disjunctive clause)。
- 有限个文字的合取称为合取式或短语(conjunctive clause)。
注：
- 单个文字既是析取式也是合取式。
- 空析取式定义为假，空合取式定义为真。
“子句”(clause)和“短语”(phrase)的叫法来自《离散代数（第四版）》， 但英语一般叫做 (disjunctive) clause 和 conjunctive clause 。[1][2]
析取范式
有限个合取式的析取称为析取范式(disjuntive normal form, DNF)， 形如 [math]\displaystyle{ (L_{11} \land \cdots \land L_{1m_1}) \lor \cdots \lor (L_{n1} \land \cdots \land L_{nm_n}) }[/math] ，其中每个 [math]\displaystyle{ L_{ij} }[/math] 都是文字。
注：
- 析取范式可以是单个合取式。
- 析取范式可以是零个合取式，空析取范式定义为假。
BNF 定义
析取范式构成的集合是命题语言的子集，也符合上下文无关文法，可以通过 Backus–Naur 范式定义。
<dnf> ::= ( <c_clause> ) | <dnf> ∨ ( <c_clause> )
<c_clause> ::= <literal> | <c_clause> ∧ <literal>
<literal> ::= <atomic> | ¬ <atomic>
<atomic> ::= "p" | "p₀" | "p₁" | "p₂" | ...
合取范式
有限个析取式的合取称为合取范式(conjuntive normal form, CNF)， 形如 [math]\displaystyle{ (L_{11} \lor \cdots \lor L_{1m_1}) \land \cdots \land (L_{n1} \lor \cdots \lor L_{nm_n}) }[/math] ，其中每个 [math]\displaystyle{ L_{ij} }[/math] 都是文字。
注：
- 合取范式可以是单个析取式。
- 合取范式可以是零个析取式，空合取范式定义为真。
BNF 定义
合取范式也符合上下文无关文法，可以通过 Backus–Naur 范式定义。
<cnf> ::= ( <d_clause> ) | <cnf> ∨ ( <d_clause> )
<d_clause> ::= <literal> | <d_clause> ∧ <literal>
<literal> ::= <atomic> | ¬ <atomic>
<atomic> ::= "p" | "p₀" | "p₁" | "p₂" | ...
性质
- 析取范式和合取范式的集合都分别覆盖所有可能的真值函数，任意可能的真值函数都能通过它们表达。
- 析取范式存在定理(disjunctive normal form theorem)：对任意命题公式，都存在与其等价的析取范式。
- 合取范式存在定理：对任意命题公式，都存在与其等价的合取范式。
- 与同一公式等价的析取范式和合取范式通常不唯一。可以存在各项之间的合并拆分关系，且析取范式和合取范式均没有限制文字重复、互补对同时出现、析取项和合取项重复的情况。
转换算法
任意命题公式都能通过以下步骤转换为析取范式或合取范式。
- 消除非基本逻辑联结词（主要指蕴涵 [math]\displaystyle{ \rightarrow }[/math] 和等价 [math]\displaystyle{ \leftrightarrow }[/math] ）：将其他逻辑联结词替换为仅含 [math]\displaystyle{ \lnot,\land,\lor }[/math] 的表达方式。
- 消除文字外的否定 [math]\displaystyle{ \lnot }[/math] ：使用德・摩根律将限定对象不是原子公式的否定符号移到原子公式前。
- 分配律：在合取和析取的层数及嵌套顺序与所需范式不同的地方，使用分配律得到目标范式形式。其间可以通过分配率消去构成矛盾式的项（互补对合取）、合并构成重言式的项（互补对析取）。
例子
析取范式例子
- [math]\displaystyle{ (P \land Q) \lor (P \land \lnot R) \lor (\lnot Q \land R) }[/math]
- [math]\displaystyle{ P \lor Q }[/math] （两个合取式，分别含一个文字）
- [math]\displaystyle{ P \land Q }[/math] （单个合取式，内含两个文字）
合取范式例子
- [math]\displaystyle{ (P \lor Q) \land (P \lor \lnot R) \land (\lnot Q \lor R) }[/math]
- [math]\displaystyle{ P \land Q }[/math] （两个析取式，分别含一个文字）
- [math]\displaystyle{ P \lor Q }[/math] （单个析取式，内含两个文字）