析取范式

析取范式是离散数学中范式的一种，即由有限个简单合取式组成的析取式。由有限个简单析取式组成的合取式称为合取范式。例如（P∧Q）∨（P∧¬Q∧R）、P∧Q等是析取范式，（P∨Q）∧（P∨¬Q∨R）、P∨Q等是合取范式。^[1]

对于单独的一个命题变元P或其否定¬P，既可以看成是析取范式，又可以看成是合取范式；当然，其既可以看成是简单析取式，又可以看成是简单合取式，至于P∨Q，若把它看作简单合取式的析取，则它是析取范式；若把它看成是文字的析取，则它是合取范式，同理，P∧¬Q、P∧Q等既是析取范式，又是合取范式。^[1]

任何一个命题公式都存在着与之等价的析取范式和合取范式（范式存在定理）由析取范式和合取范式的定义可知，范式中不存在除了¬、∧、∨以外的逻辑联结词。^[1]

析取是最常用的逻辑联结词之一，表示“或”的意思。析取是逻辑和数学概念中的一个二元逻辑算符。其运算方法是：如果其两个变量中有一个真值为“真”，其结果为“真”，两个变量同时为假，其结果为“假”。析取在数据挖掘和数据库等很多领域都有广泛应用。

命题变项及其否定统称作文字，仅由有限个文字构成的析取式称为简单析取式；仅由有限个文字构成的合取式称为简单合取式。

例如，等为一个文字构成的简单析取式。一个文字既是简单析取式，又是简单合取式。

简单析取式：

简单合取式：

（1）一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定。

（2）一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定。

（1）由有限个简单合取式构成的析取式称为析取范式。

（2）由有限个简单析取式构成的合取式称为合取范式。

（3）析取范式与合取范式统称为范式。

设为简单的合取式，则 为析取范式。

例如，析取范式：

合取范式：

（1）一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。

（2）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。

范式存在定理：任一命题公式都存在着与之等值的析取范式与合取范式。

注意：命题公式的析取范式与合取范式都不是唯一的。

证明：

1、由蕴涵等值式和等价等值式可知，因而，在等值的条件下，可消去任何公式中的联结词和

2、用双重否定率和德摩根律，可得

3、利用分配律，可得

第一步：消去联结词和；

第二步：消去否定号；

第三步：利用分配律。

求公式的析取范式与合取范式。

解：

（1）合取范式：

（2）析取范式

设由n个命题变项构成的析取范式中所有简单合取项都是极小项，则称该析取范式为主析取范式。主析取范式存在且惟一。

例如，以下公式都是主析取范式：

A∨B

A

(A∧B)∨C

(A∧¬B∧¬C)∨(¬D∧E∧F)

但以下公式不是主析取范式：

¬(A∨B) - NOT是最外层的算子

A∨(B∧(C∨D)) - 一个OR嵌套在一个AND中

注意，把公式转换成主析取范式要使用逻辑等价，比如双重否定除去、德·摩根定律和分配律。所有逻辑公式都可以转换成主析取范式，但在某些情况下，转换可能导致公式的指数性增长。例如，以下逻辑公式在主析取范式下有2^n个项：

(X₁∨Y₁)∧(X₂∨Y₂)∧...∧(X_n∨Y_n)