跳转到内容

Advertising:

析取范式、合取范式：修订间差异

来自GSXAB的知识库
Gsxab​（留言 | 贡献）
6,437次编辑
无编辑摘要
 
Gsxab​（留言 | 贡献）
6,437次编辑
无编辑摘要
 
（未显示同一用户的11个中间版本）
第1行： 第1行：
[[分类:命题逻辑]]
[[分类:命题逻辑]]{{DEFAULTSORT:xi1qu3fan4shi4he2qu3fan4shi4}}
{{#seo:
|keywords=析取范式, 合取范式, 范式, DNF, CNF
|description=本文介绍析取范式（DNF）和合取范式（CNF）的定义、性质与转换方法，包括这两种范式作为命题公式标准形式的概念，其结构特点及其在逻辑化简和计算机科学中的重要性。
|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
|published_time=2023-09-08
}}
{{InfoBox
{{InfoBox
|name=析取范式
|name=析取范式
第8行： 第14行：
|name=合取范式
|name=合取范式
|eng_name=conjunctive normal form
|eng_name=conjunctive normal form
|aliases=CNF,AND of ORs,sum of products
|aliases=CNF,AND of ORs,product of sums
}}
}}
[[命题公式]]可以表示为与其[[等值（逻辑）|等值]]的标准形式。
[[命题公式]]可以表示为[[等值（逻辑）|等值]]的标准形式。
[[合取]]的[[析取]]称为'''析取范式'''('''disjunctive normal form''')，析取的合取称为'''合取范式'''('''conjunctive normal form''')。
[[合取]]的[[析取]]称为'''析取范式'''('''disjunctive normal form''', '''DNF''')，析取的合取称为'''合取范式'''('''conjunctive normal form''', '''CNF''')。
析取范式和合取范式是命题公式的两种重要的标准形式。


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


=== 文字 ===
=== 文字 ===
第26行： 第35行：
|eng_name=literal
|eng_name=literal
}}
}}
* 不含逻辑联结词的命题公式（[[原子命题]]）称为'''原子公式'''('''atomic formula''')或'''原子'''('''atom''')，在命题逻辑范围内通常与命题变元相同；
{{InfoBox
* 原子公式称为'''肯定文字'''('''positive literal''')、原子公式的否定称为'''否定文字'''('''negative literal''')，合称'''文字'''('''literal''')。其中肯定否定称为其'''极性'''('''polarity''')。
|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''')。
* 一组互为否定的文字称为一对'''互补文字'''('''complementary literal'''s)或'''互补对'''('''complementary pair''')。


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


=== 析取式、合取式 ===
=== 析取式、合取式 ===
第47行： 第75行：
* 有限个文字的合取称为'''合取式'''或'''短语'''('''conjunctive clause''')。
* 有限个文字的合取称为'''合取式'''或'''短语'''('''conjunctive clause''')。


注：不限制文字的出现情况。由于是有限个，一个甚至0个也可以。
注：
* 单个文字既是析取式也是合取式。
* 空析取式定义为假，空合取式定义为真。


<blockquote>
<blockquote>
第54行： 第84行：
</blockquote>
</blockquote>


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


对任意命题公式，都分别存在至少一个具有以下的形式的公式与其等值：
有限个合取式的析取称为'''析取范式'''('''disjuntive normal form''', '''DNF''')，
* 有限个合取式的析取称为'''析取范式'''('''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> 都是文字。
* 有限个析取式的合取称为'''合取范式'''('''conjuntive normal form''', '''CNF''')。


注：其中有限个包含 1 个甚至 0 个的情况。换句话说， <math>P\land Q</math> 也是一个析取范式，其中只含有一个合取式， <math>\mathrm{F}</math> 也是一个析取范式，这是 0 个合取式产生的空运算结果。类似地也有 <math>P\lor Q</math> 和 <math>\mathrm{T}</math> 是合取范式。
注：
* 析取范式可以是单个合取式。
* 析取范式可以是零个合取式，空析取范式定义为假。
 
==== BNF 定义 ====
 
析取范式构成的集合是[[命题语言]]的子集，也符合[[上下文无关文法]]，可以通过 [[Backus–Naur 范式]]定义。
 
<syntaxhighlight lang="bnf">
<dnf>      ::= ( <c_clause> ) | <dnf> ∨ ( <c_clause> )
<c_clause> ::= <literal> | <c_clause> ∧ <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>      ::= ( <d_clause> ) | <cnf> ∨ ( <d_clause> )
<d_clause> ::= <literal> | <d_clause> ∧ <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> ：使用[[de Morgan 律（逻辑）|德·摩根律]]将限定对象不是原子公式的否定符号移到原子公式前。
# [[分配律]]：在合取和析取的层数及嵌套顺序与所需范式不同的地方，使用分配律得到目标范式形式。其间可以通过分配率消去构成矛盾式的项（互补对合取）、合并构成重言式的项（互补对析取）。
 
== 例子 ==
 
=== 析取范式例子 ===
* <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> （单个析取式，内含两个文字）




{{命题逻辑}}
{{命题逻辑}}

2026年1月3日 (六) 12:49的最新版本

析取范式
术语名称 析取范式
英语名称 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)：对任意命题公式，都存在与其等价的析取范式。
    • 合取范式存在定理：对任意命题公式，都存在与其等价的合取范式。
  • 与同一公式等价的析取范式和合取范式通常不唯一。可以存在各项之间的合并拆分关系，且析取范式和合取范式均没有限制文字重复、互补对同时出现、析取项和合取项重复的情况。

转换算法

任意命题公式都能通过以下步骤转换为析取范式或合取范式。

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

例子

析取范式例子

  • [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] （单个析取式，内含两个文字）


命题逻辑/零阶逻辑
基本概念 命题 命题、命题变元、命题常量
真值 真 [math]\displaystyle{ \mathrm{T} }[/math]/[math]\displaystyle{ 1 }[/math]/[math]\displaystyle{ \top }[/math] 、假 [math]\displaystyle{ \mathrm{F} }[/math]/[math]\displaystyle{ 0 }[/math]/[math]\displaystyle{ \bot }[/math]
命题结构 命题结构 原子命题、复合命题
逻辑联结词 否定（非） [math]\displaystyle{ \lnot }[/math] 、合取（且/与） [math]\displaystyle{ \land }[/math] 、析取（或） [math]\displaystyle{ \lor }[/math]
蕴涵（推出） [math]\displaystyle{ \rightarrow }[/math] 、等价（当且仅当） [math]\displaystyle{ \leftrightarrow }[/math]
命题公式 形式定义 命题语言 [math]\displaystyle{ \mathcal{L}_0 }[/math] 、命题公式
逻辑语义 指派、 Tarski 真理定义、解释、真值表、满足
语义分类 重言式/永真式、偶然式/仅可满足式/可真可假式、矛盾式/永假式/不可满足式
语义关系 重言等价/等值/等价 [math]\displaystyle{ = }[/math]/[math]\displaystyle{ \Leftrightarrow }[/math] 、重言蕴涵 [math]\displaystyle{ \Rightarrow }[/math]
范式 析取范式、合取范式（主析取范式、主合取范式）
  1. ↑ Clause (Logic) - Wikipedia
  2. ↑ 数理逻辑（2）——命题逻辑的等值、范式和推理演算 - tetradecane的文章 - 知乎
检索自“https://knowledge.gsxab.top/index.php?title=析取范式、合取范式&oldid=6379”

Advertising: