析取范式、合取范式
| 析取范式 | |
|---|---|
| 术语名称 | 析取范式 |
| 英语名称 | disjunctive normal form |
| 别名 | DNF, OR of ANDs, sum of products |
| 合取范式 | |
|---|---|
| 术语名称 | 合取范式 |
| 英语名称 | conjunctive normal form |
| 别名 | CNF, AND of ORs, sum of products |
命题公式可以表示为与其等值的标准形式。 合取的析取称为析取范式(disjunctive normal form)，析取的合取称为合取范式(conjunctive normal form)。
定义
文字
| 原子公式 | |
|---|---|
| 术语名称 | 原子公式 |
| 英语名称 | atomic formula |
| 别名 | 原子, atom, prime formula |
| 文字 | |
|---|---|
| 术语名称 | 文字 |
| 英语名称 | literal |
- 不含逻辑联结词的命题公式（原子命题）称为原子公式(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)。
注：不限制文字的出现情况。由于是有限个，一个甚至0个也可以。
“子句”(clause)和“短语”(phrase)的叫法来自《离散代数（第四版）》， 但英语一般叫做 (disjunctive) clause 和 conjunctive cluase 。[1][2]
析取范式、合取范式
对任意命题公式，都分别存在至少一个具有以下的形式的公式与其等值：
- 有限个合取式的析取称为析取范式(disjuntive normal form, DNF)。
- 有限个析取式的合取称为合取范式(conjuntive normal form, CNF)。
注：其中有限个包含一个甚至0个的情况。
性质
对任意命题公式，都存在与其等价的析取范式和合取范式。
由于不限制文字的出现情况，等价的析取范式和合取范式不唯一。可以存在各项之间的合并拆分，以及同时在一项中存在相同或互补的文字。由于幂等性，含有相同文字的子句或短语相当于仅出现一次，互补文字的子句或短语相当于这个子句或短语未出现在范式中。