2.2析取范式与合取范式一、析取范式与合取范式定义2.2 命题变项及其否定统称作文字。
仅由有限个文字构成的析取式称为简单析取式。
仅由有限个文字构成的合取式称为简单合取式。
例如，文字：p,┐q,r,q.简单析取式: p,q,p∨q,p∨┐p∨r,┐p∨q∨┐r.简单合取式: p,┐r,┐p∧r,┐p∧q∧r,p∧q∧┐q.定理2.1（1）一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定。
（2）一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定。
定义2.3（1）由有限个简单合取式构成的析取式称为析取范式。
（2）由有限个简单析取式构成的合取式称为合取范式。
（3）析取范式与合取范式统称为范式。
例如，析取范式：（p┐∧q）∨r, ┐p∧q∧r, p∨┐q∨r.合取范式:(p∨q∨r)∧(┐q∨r), ┐p∧q∧r, p∨┐q∨r.定理2.2（1）一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。
（2）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。
范式的特点：（1）范式中不出现联结词→、↔，求范式时可消去：A→B⇔┐A∨BA↔B⇔(┐A∨B)∧(A∨┐B)（2）范式中不出现如下形式的公式：┐┐A, ┐(A∧B), ┐(A∨B)因为：┐┐A⇔A┐(A∧B)⇔┐A∨┐B┐(A∨B)⇔┐A∧┐B（3）在析取范式中不出现如下形式的公式：A∧(B∨C)在合取范式中不出现如下形式的公式：A∨(B∧C)因为：A∧(B∨C)⇔(A∧B)∨(A∧C)A∨(B∧C)⇔(A∨B)∧(A∨C)定理2.3 (范式存在定理)任一命题公式都存在着与之等值的析取范式与合取范式。
求范式的步骤：1．消去联结词→、↔；2．消去否定号┐；3．利用分配律。
命题公式的析取范式与合取范式都不是唯一的。
例2.7 求公式(p→q)↔r的析取范式与合取范式。
解: (1)合取范式：(p→q)↔r ⇔(┐p∨q)↔ r⇔((┐p∨q)→ r)∧(r→(┐p∨q))⇔(┐(┐p∨q)∨r)∧(┐r∨(┐p∨q))⇔ ((p∧┐q)∨r)∧(┐p∨q∨┐r)⇔ (p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)(2) 析取范式(p→q)↔r ⇔ ((p∧┐q)∨r)∧(┐p∨q∨┐r)⇔ (p∧┐q∧┐p)∨(p∧┐q∧q)∨(p∧┐q∧┐r)∨(r∧┐p)∨(r∧q)∨(r∧┐r)⇔ (p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)下面介绍命题公式的唯一规范化形式的范式：主析取范式与主合取范式。
二、主析取范式与主合取范式1．极小（大）项定义2.4极小项（极大项）：含n个命题变项的简单合取式（简单析取式），每个命题变项和它的否定式不同时出现，且二者之一必出现且仅出现一次。
由p, q两个命题变项形成的极小项与极大项由下表给出由p, q, r三个命题变项形成的极小项与极大项由下表给出.由上表可见:(1)n个命题变项可组成2n个不同的极小项和2n个不同的极大项。
(2)每个极小项都有且仅有一个成真赋值，其成真赋值对应的二进制数转化为十进制数为i，记该极小项为m i.(3)每个极大项都有且仅有一个成假赋值，其成假赋值对应的二进制数转化为十进制数为i，记该极大项为M i。
定理2.4 设m i和M i是p1，…，p n组成的极小项和极大项，则┐m i⇔M i, ┐M i⇔m i 。
2．主析(合)取范式定义2.5 主析取范式：全部由极小项组成的析取范式。
主合取范式：全部由极大项组成的合取范式。
如：（p∧q）∨(p∧┐q)⇔m2∨m3(p∨q)∧(┐p∨q)∧(p∨┐q)⇔M0∧M2∧M1定理2.5 任何命题公式都存在与之等值的主析取范式和主合取范式，且是唯一的。
用等值演算法求公式的主范式的步骤：（1）先求析取范式（合取范式）（2）将不是极小项（极大项）的简单合取式（简单析取式）化成与之等值的若干个极小项之析取（极大项之合取），利用的等值式为同一律（零律）、排中律（矛盾律）、分配律、幂等律等.（3）极小项（极大项）用名称mi（Mi）表示，并按角标从小到大顺序排序.例2.8 求公式(p→q)↔r的主析(合)取范式。
解: (1)主析取范式由例2.7 知，(p→q)↔r ⇔(p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)∵(┐p∧r)⇔┐p∧(┐q∨q)∧r⇔(┐p∧┐q∧r)∨(┐p∧q∧r)⇔m1∨m3(q∧r) ⇔(┐p∨p)∧q∧r⇔(┐p∧q∧r)∨(p∧q∧r)⇔m3∨m7（p∧┐q∧┐r) ⇔m4∴(p→q)↔r ⇔m1∨m3∨m4∨m7例求公式(p→⌝q)→r的主析取范式与主合取范式.（1）求主析取范式(p→⌝q)→r⇔ (p∧q)∨r （析取范式）①(p∧q)⇔ (p∧q)∧(⌝r∨r)⇔ (p∧q∧⌝r)∨(p∧q∧r)⇔ m6∨m7②r⇔ (⌝p∨p)∧(⌝q∨q)∧r⇔ (⌝p∧⌝q∧r)∨(⌝p∧q∧r)∨(p∧⌝q∧r)∨(p∧q∧r)⇔ m1∨m3∨m5∨m7③②, ③代入①并排序，得(p→⌝q)→r ⇔ m1∨m3∨m5∨ m6∨m7（主析取范式）（2）求A的主合取范式(p→⌝q)→r⇔ (p∨r)∧(q∨r) （合取范式）①p∨r⇔ p∨(q∧⌝q)∨r⇔ (p∨q∨r)∧(p∨⌝q∨r)⇔ M0∧M2②q∨r ⇔ (p∧⌝p)∨q∨r⇔ (p∨q∨r)∧(⌝p∨q∨r)⇔ M0∧M4③②,③代入①并排序，得(p→⌝q)→r ⇔ M0∧M2∧M4（主合取范式）例 2.9 求p→q 的主析取范式和主合取范式解: (1) 主合取范式p→q ⇔┐p∨q⇔M2(2) 主析取范式p→q ⇔(┐p∨q )⇔(┐p∧(┐q∨q ))∨((┐p∨p)∧q)⇔(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q)(┐p∧┐q)∨(┐p∧q)∨(p∧q)m0∨m1∨m3给出下面两个表：由表中看出，p→q有三个成真赋值，其主析取范式有三个极小项，极小项的下标分别为三个成真赋值的十进制数；p→q有一个成假赋值，其主合取范式有一个极大项，极大项的下标为成假赋值的十进制数。
由此，我们不难得到以下结论：含n个命题变项的公式，其主析取范式所含极小项的个数与其主合取范式所含极大项的个数之和为2n，并且极小项的下标分别为成真赋值的十进制数，极大项的下标分别为成假赋值的十进制数。
可见，已求出公式的一个主范式后，可立即得到公式的另一个主范式。
例2.13 由公式的主析取范式，求其主合取范式：(1)A⇔m1∨m2(A中含命题变项p,q)(2)B⇔m1∨m2∨m3(B中含命题变项p,q,r)解：(1)由题知，A的成真赋值为01,10,则其成假赋值为00，11，故A⇔M0∧M3(2)同理知，B的成真赋值为001，010，011，则其成假赋值为000，100，101，110，111，因此B⇔M0∧M4∧M5∧M6∧M7例, 求公式(p∧q)∨r的主析取范式及主合取范式。
主析取范式:(p∧q)∨r<==>(p∧q∧(r∨┐r))∨((p∨┐p)∧(q∨┐q)∧r)<==>(p∧q∧r)∨(p∧q∧┐r)∨(p∧q∧r)∨(p∧┐q∧r)∨(┐p∧q∧r)∨(┐p∧┐q ∧r)<==>(p∧q∧r)∨(p∧q∧┐r)∨(p∧┐q∧r)∨(┐p∧q∧r)∨(┐p∧┐q∧r)<==>∑(m1,m3,m5,m6,m7)主合取范式(p∧q)∨r<==>(p∨r)∧(q∨r) <==>(p∨(q∧┐q)∨r)∧((p∧┐p)∨q∨r)<==>(p∨q∨r)∧(p∨┐q∨r)∧(p∨q∨r)∧(┐p∨q∨r)<==>(p∨q∨r)∧(p∨┐q∨r)∧(┐p∨q∨r)<==>∏(M0,M2,M4)也就是:∑(m1,m3,m5,m6,m7)<==>∏(M0,M2,M4)说明:∑:表示连续的合取;∏:表示连续的析取例, 求公式(p∧q)∨r的主析取范式及主合取范式。
主析取范式:(p∧q)∨r<==>(p∧q∧(r∨┐r))∨((p∨┐p)∧(q∨┐q)∧r)<==>(p∧q∧r)∨(p∧q∧┐r)∨(p∧q∧r)∨(p∧┐q∧r)∨(┐p∧q∧r)∨(┐p∧┐q ∧r)<==>(p∧q∧r)∨(p∧q∧┐r)∨(p∧┐q∧r)∨(┐p∧q∧r)∨(┐p∧┐q∧r)<==>∑(m1,m3,m5,m6,m7)主合取范式(p∧q)∨r<==>(p∨r)∧(q∨r)<==>(p∨(q∧┐q)∨r)∧((p∧┐p)∨q∨r)<==>(p∨q∨r)∧(p∨┐q∨r)∧(p∨q∨r)∧(┐p∨q∨r)<==>(p∨q∨r)∧(p∨┐q∨r)∧(┐p∨q∨r)<==>∏(M0,M2,M4)也就是:∑(m1,m3,m5,m6,m7)<==>∏(M0,M2,M4)说明:∑:表示连续的合取;∏:表示连续的析取1.4.1范式1、简单析取式，简单合取式。
简单析取式：由有限个命题变项或其否定构成的析取式。
例如：，，，等都是简单析取式。
简单合取式：由有限个命题变项或其否定构成的合取式。
例如：，，，等都是简单合取式。
2、析取范式，合取范式。
定义：由有限个简单合取式构成的析取式称作析取范式。
由有限个简单析取式构成的合取式称作合取范式。
例如：为析取范式；为合取范式。
显然，为合取范式；为析取范式。
范式存在定理：任一命题公式都存在与之等值的析取范式和合取范式。
求范式步骤：(1) 消去联结词(即利用）。
(2) 否定消去或内移。
(3) 利用分配律。
例1、求公式的析取范式和合取范式。
解：原式消去内移消去分配律(对分配)上式即原式的析取范式，再利用第三步的结论，即：原式分配律(对分配)即原式的合取范式。
1.4.2主范例2、求公式的主析取范式解：由例1，的析取范式为(吸收律)例3、求公式的主合取范式。
解：由例1合取范式。