析取，数学术语。用符号“∨”表示。在离散数学中，命题是一个陈述句，它或真或假，但不能既真又假。联结词是逻辑联结词或命题联结词的简称，它是自然语言中连词的逻辑抽象。析取是最常用的逻辑联结词之一，表示“或”的意思。析取是逻辑和数学概念中的一个二元逻辑算符。其运算方法是：如果其两个变量中有一个真值为“真”，其结果为“真”，两个变量同时为假，其结果为“假”。

在离散数学中，命题是一个陈述句，它或真或假，但不能既真又假。联结词是逻辑联结词或命题联结词的简称，它是自然语言中连词的逻辑抽象。析取是最常用的逻辑联结词之一，表示“或”的意思。析取是逻辑和数学概念中的一个二元逻辑算符。其运算方法是：如果其两个变量中有一个真值为“真”，其结果为“真”，两个变量同时为假，其结果为“假”。析取在数据挖掘和数据库等很多领域都有广泛应用。

合取

基本符号：∧∧ 英文名：logicalconjunction 中文名：逻辑与，合取，交集，按位与，逻辑乘，与门，…命题逻辑中的二元连接词合取，是一个两元算子，集合论中的交集算子，二进制中的逻辑乘算子，按位与（Bitwise AND），逻辑门中的“与”门（AND gate），编程语言中的&或and运算符等等。

对于给定公式的判定问题，可用真值表方法加以解释，但当公式中命题变元的数目较大时，真值表就显得相当麻烦。每增加一个命题变元，真值表的行数就比原来增加一倍，从而使计算量增加一倍。另外，由于同一个命题公式可以有不同的表达形式，而不同的表达形式可以显示很不同的特征。某种特定类型的表达可以显示出从某一角度考虑极为重要的性质。但上述的不同表达形式却对我们研究命题演算带来了一定的困难。因此，从理论上讲，有必要对命题公式的标准形式问题进行一个深入的研究，使公式达到规范化。为此，引入范式这一概念，范式给各种千变万化的公式提供了一个统一的表达形式，同时，范式的研究对命题演算的发展起了极其重要的作用。如在逻辑理论中判断公式的一些性质，在论证命题的完整性时要用到范式。在工程技术的线路设计方面，自动机理论与人工智能方面等也有极其重要的作用。

子句

l1∨⋯∨lnl1∨⋯∨ln 在某些情况下，子句被写为文字的集合，所以上述子句将被写为 l1,…,lnl1,…,ln 。从上下文中得到提示把这个集合解释为它的元素的析取。子句可以为空；在这种情况下，它是文字的空集。空字句被指示为各种符号比如∅∅ 、⊥⊥ 或 □◻ 。空字句的真值求值总是 falsefalse。

文字 (数理逻辑)

在数理逻辑中，文字(literal)是一个原子公式(atom)或它的否定。文字可以分为两种类型:

肯定文字就是一个原子。 否定文字是一个原子的否定。 纯文字是其变量(在某个公式内)的所有出现都有相同符号的文字。

原子公式

在数理逻辑中， 原子公式或原子是没有子公式的公式。把什么公式当作原子依赖于所使用的逻辑。例如在命题逻辑中，唯一的原子公式是命题变量。

原子是在逻辑系统中”最小”的公式。在逻辑系统中的合式公式通常通过识别所有有效的原子公式，和给出从两个原子公式建立公式的规则而递归的定义。从原子公式制作的公式是复合公式。

例如，在命题逻辑中你有如下的公式构造规则:

任何命题变量 p 是合式原子公式。 给定任何公式 A，否定 ¬A (“非 A”) 是合式公式。 给定任何两个公式 A 和 B，合取 A ∧ B (“A 与 B”) 是合式公式。 给定任何两个公式 A 和 B，析取 A ∨ B (“A 或 B”) 是合式公式。 给定任何两个公式 A 和 B，蕴涵 A ⇒ B (“A 蕴涵 B “) 是合式公式。所以，我们可以建造任意的复杂的复合公式，比如，从简单的原子公式p、q 和 r 和我们的构造规则构造出 ((p ∧ ¬(q ⇒ r)) ∨ ¬p)。

（1）命题变元或命题变元的否定称为文字（Character）。

（2）有限个文字的析取式称为子句（Clouse）；有限个文字的合取式称为短语（Phrase）。

（3）有限个短语的析取式称为析取范式（Disjunctive Normal Form）；有限个子句的合取式称为合取范式(ConjunctiveNormal Form)。

例

（1）P、┐P是文字、子句、短语、析取范式、合取范式。

（2）P∨Q∨┐R是子句、析取范式、合取范式。

（3）┐P∧Q∧R是短语、析取范式、合取范式。

（4）(P∧Q)∨(┐P∧Q)是析取范式。

（5）(P∨Q)∧(┐P∨Q)是合取范式。

注意：句子(P∨Q∨┐R)仅是子句、合取范式，句子(┐P∧Q∧R)仅是短语、析取范式；而对句子P∨(Q∨┐R)、┐(Q∨R)等即不是析取范式也不是合取范式，但通过将句子P∨(Q∨┐R)转换为P∨Q∨┐R以及将句子┐(Q∨R)转换为┐Q∧┐R后，即是析取范式和合取范式。

从上述定义和例子可以得出如下关系：

单个的文字是子句、短语、析取范式，合取范式。

析取范式、合取范式仅含联结词集{┐,∧,∨}。

对于任意命题公式，可以通过逻辑等价公式求出等价于它的析取范式和合取范式，其步骤如下：

（1）利用等价公式中的等价式和蕴涵式将公式中的→、«用联结词┐、∧、∨来取代。

（2）利用德·摩根定律将否定号┐移到各个命题变元的前端。

（3）利用结合律、分配律、吸收律、等幂律、交换律等将公式化成其等价的析取范式和合取范式。

例求公式：(P∧┐Q)«(P→R)的析取范式和合取范式。

解 (P∧┐Q)«(P→R)

= ((P∧┐Q)→(P→R))∧((P→R)→(P∧┐Q))

= (┐(P∧┐Q)∨(P→R))∧(┐(P→R)∨(P∧┐Q))

= ((┐P∨Q)∨(┐P∨R))∧(┐(┐P∨R)∨(P∧┐Q))

= (┐P∨Q∨┐P∨R)∧((P∧┐R)∨(P∧┐Q))

= (┐P∨Q∨R)∧P∧(┐R∨┐Q) 合取范式

= ((┐P∧P)∨(Q∧P)∨(R∧P))∧(┐R∨┐Q)

= (Q∧P∧┐R)∨(R∧P∧┐R)∨(Q∧P∧┐Q)∨(R∧P∧┐Q)

= (Q∧P∧┐R)∨（R∧P∧┐Q）

显然，范式为命题公式提供了一种统一的表达形式，但这种表达形式并不惟一。

如公式：(P∨Q)∧(P∨R)

与之等价的公式：P∨(Q∧R),(P∧P)∨(Q∧R)，P∨(Q∧┐Q)∨(Q∧R),P∨(P∧R)∨(Q∧R)

等都是析取范式。这种不惟一的表达形式也给研究问题带来了不便，下面引进更为标准的范式。

定理1：任意一个命题公式都存在与之等价的合取范式和析取范式。

定理的证明思路

1、化成限定性公式；

2、将否定联结词移到命题变量的前面；

3、消除多余的否定联结词；

4、化成合取范式和析取范式。

定理1局限

1、标准化但仅仅是初步的

# 标准化的形式

# 不唯一性

2、能够判定是否为永真或永假公式但不方便

定理2：一个命题公式是永真公式当且仅当与它等价的合取范式的每一个大项中包含了一个命题变量和它的否定；一个命题公式是永假公式当且仅当与它等价的析取范式的每一个小项中包含了一个命题变量和它的否定。

（1）设P1、P2、P3、…、Pn是n 个命题变元，一个短语或子句如果恰好包含所有这n个命题变元或命题变元的否定，且排列顺序与P1、P2、P3、…、Pn的顺序一致，则称此短语或子句为关于P1、P2、P3、…、Pn的一个极小项（Minterm）或极大项（Maxterm）。

（2）由有限个极小项组成的析取范式称为主析取范式（Principal Disjunctive Normal Form）。

（3）由有限个极大项组成的合取范式称为主合取范式（Principal Disjunctive Normal Form）。

如果一个主析取范式不包含任何极小项，则称该主析取范式为“空”；如果一个主合取范式不包含任何极大项，则称该主合取范式为“空”。

定理:任何一个公式都有与之等价的主析取范式和主合取范式。

证明该定理的方法与过程，实际也就是求一个公式的主析取范式和主合取范式的方法，主要有两种不同的方法，一是真值表技术，一是公式转换法。

任何一个公式的主析取范式和主合取范式不仅要取决于该公式，而且取决于该公式所包含的命题变元。如公式：G1=(P→Q)∧Q G2(P,Q,R) = (P→Q)∧Q

尽管G1和G2(P,Q,R)右端的公式是一样的，但它们求出的相应的主析取范式和主合取范式却是不同的，前者是依赖于两个命题变元的，后者应依赖于三个命题变元。

对于两个命题变元P，Q来说，由于每个P、Q可以取命题变元自身和其否定，所以其对应的不同的极小项和极大项分别有如下四项：

P∧Q、┐P∧Q、P∧┐Q、┐P∧┐Q；

P∨Q、┐P∨Q、P∨┐Q、┐P∨┐Q；

没有两个不同的极小项是等价的，且每个极小项只有一组真值指派，使该极小项的真值为真，因此可给极小项编码，使极小项为“T”的那组真值指派为对应的极小项的编码；如极小项┐P∧┐Q∧┐R只有在P、Q、R分别取真值0、0、0时才为真，所以有时又可用m000(m0)来表示，同理，如┐P∧Q∧┐R也可用m010(m2)来表示。

没有两个不同的极大项是等价的，且每个极大项只有一组真值指派，使该极大项的真值为假，因此可给极大项编码，使极大项为“F”的那组真值指派为对应的极小项的编码；如极小项┐P∨┐Q∨┐R只有在P、Q、R分别取真值1、1、1时才为假，所以有时又可用M111（M7）来表示，同理，如┐P∨Q∨┐R也可用M101(M5)来表示。

根据上述真值结果可知：任意两个极小项的合取必为假，任意两个极大项的析取必为真。

极大项的否定是极小项，极小项的否定是极大项，即

Mi∨Mj=T；mi∧mj=F（当i≠j时，i,j∈{0,1,2,3,…2n1}）

mi= ┐Mi；Mi= ┐mi(i=0,1,2,3,…2n1)

所有极小项的析取为永真公式；所有极大项的合取是永假公式。

根据上述对极小项的分析可知，任何一个极小项的真值解释中仅有一种解释使得其真值为真，而主析取范式是由一些极小项的析取组成，为此，在真值表技术中，可利用将公式的真值进行分解的方式，分解成一些子公式，该子公式仅有一种解释使其真值为真，此时，每一个子公式都对应了一个极小项，将这些极小项的析取所得到的结果为原公式，此时原公式已表示成了一个主析取范式。

除了利用真值表技术求主范式的方法以外，还可利用公式之间的等价关系来求主范式。对于任意命题公式，可以通过逻辑等价公式求出等价于它的析取范式和合取范式，其步骤如下：

（1）利用等价公式中的等价式和蕴涵式将公式中的→、«用联结词┐、∧、∨来取代。

（2）利用德·摩根定律将否定号┐移到各个命题变元的前端。

（3）利用结合律、分配律、吸收律、等幂律、交换律等将公式化成其等价的析取范式和合取范式。

（4）在析取范式的短语和合取范式的子句中，如同一命题变元出现多次，则将其化成只出现一次。

（5）去掉析取范式中所有永假式的短语和合取范式中所有永真式的子句，即去掉短语中含有形如P∧┐P的子公式和子句中含有形如P∨┐P的子公式。

（6）若析取范式的某一个短语中缺少该命题公式中所规定的命题变元，如缺少命题变元P，则可用公式：

(┐P∨P)∧Q=Q

将命题变元P补进去，并利用分配律展开，然后合并相同的短语，此时得到的短语将是标准的极小项；若合取范式的某一个子句中缺少该命题公式中所规定的命题变元，如缺少命题变元P，则可用公式：

(┐P∧P)∨Q=Q

将命题变元P补进去，并利用分配律展开，然后合并相同的子句，此时得到的子句将是标准的极大项。

（7）利用等幂律将相同的极小项和极大项合并，同时利用交换律进行顺序调整，由此可转换成标准的主析取范式和主合取范式。

1. 对于命题公式G，都存在等价于它的主析取范式。

2. 设公式G，H是关于原子P1，…，Pn的两个主析取范式。 如果G，H不完全相同，则G，H不等价。

3. 对于任意公式G，存在唯一一个与G等价的主析取范式。

4. 设命题公式G中所有不同原子为P1，…，Pn，如果G的某个析取范式G’中的每一个短语，都是关于P1，…，Pn的一个极小项，则称G’为G的主析取范式。 恒假公式的主析取范式用0表示。

5. 对于命题公式G，都存在等价于它的主析取范式。

6. 设公式G，H是关于原子P1，…，Pn的两个主析取范式。 如果G，H不完全相同，则G，H不等价。

7. 对于任意公式G，存在唯一一个与G等价的主析取范式。

8. 令A（a1、a2、……、an）包含有n个变量的公式，则有：

1、如果A存在与之等价的主析取范式，则必唯一；

2、如果A存在与之等价的主合取范式，则必唯一；

3、A是永真公式当且仅当与A等价的主析取范式恰有2n个极小项或没有主合取范式；

4、A是永假公式当且仅当与A等价的主合取范式恰有2n个极大项或没有主析取范式；

5、两个命题公式等价当且仅当它们有相同的主合取范式或相同的主析取范式。

示例

例6 张先生手中有代号为A、B、C、D、E的五种股票，根据当前股市情况及张先生本人的经济需求，需要

要求

（1）若A抛出，则B也抛出；

（2）B和C要留一种股票且只能留一种；

（3）C和D要么全抛，要么都不抛；

（4）D和E两种股票中必然有一种或两种要抛出；

（5）若E抛出，则A、B也抛出。上述五种条件全部满足，问有几种合理的方案供张先生选择。