查看“︁析取范式、合取范式”︁的源代码

[[分类:命题逻辑]]{{DEFAULTSORT:xi1qu3fan4shi4he2qu3fan4shi4}}
{{#seo:
|keywords=析取范式, 合取范式, 范式, DNF, CNF
|description=本文介绍析取范式（DNF）和合取范式（CNF）的定义、性质与转换方法，包括这两种范式作为命题公式标准形式的概念，其结构特点及其在逻辑化简和计算机科学中的重要性。
|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
|published_time=2023-09-08
}}
{{InfoBox
|name=析取范式
|eng_name=disjunctive normal form
|aliases=DNF,OR of ANDs,sum of products
}}
{{InfoBox
|name=合取范式
|eng_name=conjunctive normal form
|aliases=CNF,AND of ORs,product of sums
}}
[[命题公式]]可以表示为[[等值（逻辑）|等值]]的标准形式。
[[合取]]的[[析取]]称为'''析取范式'''('''disjunctive normal form''', '''DNF''')，析取的合取称为'''合取范式'''('''conjunctive normal form''', '''CNF''')。
析取范式和合取范式是命题公式的两种重要的标准形式。

== 定义 ==

定义范式前，需要明确一些文法概念进行构造。

=== 文字 ===

{{InfoBox
|name=原子公式
|eng_name=atomic formula
|aliases=原子,atom,prime formula
}}
{{InfoBox
|name=文字
|eng_name=literal
}}
{{InfoBox
|name=肯定文字
|eng_name=positive literal
}}
{{InfoBox
|name=否定文字
|eng_name=negative literal
}}
{{InfoBox
|name=极性
|eng_name=polarity
}}
{{InfoBox
|name=互补文字
|eng_name=complementary literal
|aliases=互补对,complementary pair
}}
* 不含逻辑联结词的命题公式，即[[原子命题]]，称为'''原子公式'''('''atomic formula''')或'''原子'''('''atom''')，在命题逻辑范围内通常是命题变元；
* 原子公式称为'''肯定文字'''('''positive literal''')、原子公式的[[否定]]称为'''否定文字'''('''negative literal''')，合称'''文字'''('''literal''')。其中的肯定否定称为其'''极性'''('''polarity''')。
* 一组互为否定的文字称为一对'''互补文字'''('''complementary literal'''s)或'''互补对'''('''complementary pair''')。

注：
* 可以认为原子命题的定义就是不含逻辑联结词。在命题逻辑中是命题变元，但命题逻辑以外可以有其他情况。
* 文字指包含原子公式及其否定。需要注意，尽管 <math>P</math> （原子公式）和 <math>\lnot P</math> （原子公式的否定）都是文字，但是如 <math>\lnot \lnot P</math> 的形式则不是一个文字。

=== 析取式、合取式 ===

{{InfoBox
|name=析取式
|eng_name=disjunctive clause
|aliases=子句,clause
}}
{{InfoBox
|name=合取式
|eng_name=conjunctive clause
|aliases=短语
}}
* 有限个文字的析取称为'''析取式'''或'''子句'''('''disjunctive clause''')。
* 有限个文字的合取称为'''合取式'''或'''短语'''('''conjunctive clause''')。

注：
* 单个文字既是析取式也是合取式。
* 空析取式定义为假，空合取式定义为真。

<blockquote>
“子句”(clause)和“短语”(phrase)的叫法来自《离散代数（第四版）》，
但英语一般叫做 (disjunctive) clause 和 conjunctive clause 。<ref>[https://en.wikipedia.org/wiki/Clause_(logic) Clause (Logic) - Wikipedia]</ref><ref>[https://zhuanlan.zhihu.com/p/83001673 数理逻辑（2）——命题逻辑的等值、范式和推理演算 - tetradecane的文章 - 知乎]</ref>
</blockquote>

=== 析取范式 ===

有限个合取式的析取称为'''析取范式'''('''disjuntive normal form''', '''DNF''')，
形如 <math>(L_{11} \land \cdots \land L_{1m_1}) \lor \cdots \lor (L_{n1} \land \cdots \land L_{nm_n})</math> ，其中每个 <math>L_{ij}</math> 都是文字。

注：
* 析取范式可以是单个合取式。
* 析取范式可以是零个合取式，空析取范式定义为假。

==== BNF 定义 ====

析取范式构成的集合是[[命题语言]]的子集，也符合[[上下文无关文法]]，可以通过 [[Backus–Naur 范式]]定义。

<syntaxhighlight lang="bnf">
<dnf>      ::= ( <conjunct> ) | <dnf> ∨ ( <conjunct> )
<conjunct> ::= <literal> | <term> ∧ <literal>
<literal>  ::= <atomic> | ¬ <atomic>
<atomic>   ::= "p" | "p₀" | "p₁" | "p₂" | ...
</syntaxhighlight>

=== 合取范式 ===

有限个析取式的合取称为'''合取范式'''('''conjuntive normal form''', '''CNF''')，
形如 <math>(L_{11} \lor \cdots \lor L_{1m_1}) \land \cdots \land (L_{n1} \lor \cdots \lor L_{nm_n})</math> ，其中每个 <math>L_{ij}</math> 都是文字。

注：
* 合取范式可以是单个析取式。
* 合取范式可以是零个析取式，空合取范式定义为真。

==== BNF 定义 ====

合取范式也符合上下文无关文法，可以通过 Backus–Naur 范式定义。

<syntaxhighlight lang="bnf">
<cnf>      ::= ( <disjunct> ) | <cnf> ∨ ( <disjunct> )
<disjunct> ::= <literal> | <term> ∧ <literal>
<literal>  ::= <atomic> | ¬ <atomic>
<atomic>   ::= "p" | "p₀" | "p₁" | "p₂" | ...
</syntaxhighlight>

== 性质 ==

* 析取范式和合取范式的集合都分别覆盖所有可能的真值函数，任意可能的真值函数都能通过它们表达。
* '''析取范式定理'''('''disjunctive normal form theorem''')：对任意命题公式，都存在与其等价的析取范式。同理也存在合取范式。
* 与同一公式等价的析取范式和合取范式通常不唯一。可以存在各项之间的合并拆分关系，且析取范式和合取范式均没有限制文字重复、互补对同时出现、析取项和合取项重复的情况。

== 转换算法 ==

任意命题公式都能通过以下步骤转换为析取范式或合取范式。
# 消除非基本逻辑联结词（主要指[[蕴含]] <math>\rightarrow</math> 和[[等价（逻辑）|等价]] <math>\leftrightarrow</math> ）：将其他逻辑联结词替换为仅含 <math>\lnot,\land,\lor</math> 的表达方式。
# 消除文字外的否定 <math>\lnot</math> ：使用[[德・摩根律]]将限定对象不是原子公式的否定符号移到原子公式前。
# [[分配律]]：在合取和析取的层数及嵌套顺序与所需范式不同的地方，使用分配律得到目标范式形式。其间可以通过分配率消去构成矛盾式的项（互补对合取）、合并构成重言式的项（互补对析取）。

== 例子 ==

=== 析取范式例子 ===
* <math>(P \land Q) \lor (P \land \lnot R) \lor (\lnot Q \land R)</math>
* <math>P \lor Q</math> （两个合取式，分别含一个文字）
* <math>P \land Q</math> （单个合取式，内含两个文字）

=== 合取范式例子 ===
* <math>(P \lor Q) \land (P \lor \lnot R) \land (\lnot Q \lor R)</math>
* <math>P \land Q</math> （两个析取式，分别含一个文字）
* <math>P \lor Q</math> （单个析取式，内含两个文字）


{{命题逻辑}}