1、11.5 对偶与范式 对偶式与对偶原理 析取范式与合取范式 主析取范式与主合取范式 2对偶式和对偶原理定义 在仅含有联结词 , , 的命题公式 A中，将 换成 , 换成 ，若 A中含有 0或 1，就将 0换成1， 1换成 0，所得命题公式称为 A的 对偶式 ，记为 A*.从定义不难看出， (A*)* 还原成 A定理 设 A和 A*互为对偶式， p1,p2, pn是出现在 A和A*中的全部命题变项，将 A和 A*写成 n元函数形式，则 (1) A(p1,p2, pn) A* ( p1, p2, pn)(2) A( p1, p2, pn) A* (p1,p2, pn) 定理（对偶原理） 设 A，
2、B为两个命题公式，若 A B，则 A* B*.3析取范式与合取范式 文字 :命题变项及其否定的总称简单析取式 :有限个文字构成的析取式如 p, q, pq, pqr, 简单合取式 :有限个文字构成的合取式如 p, q, pq, pqr, 析取范式 :由有限个简单合取式组成的析取式A1A2 Ar, 其中 A1,A2, ,Ar是 简单合取式合取范式 :由有限个简单析取式组成的合取式A1A2 Ar , 其中 A1,A2, ,Ar是 简单析取式4析取范式与合取范式 (续 )范式 :析取范式与合取范式的总称 公式 A的析取范式 : 与 A等值的析取范式公式 A的合取范式 : 与 A等值的合取范式说明：
3、单个文字既是简单析取式，又是简单合取式形如 pqr, pqr 的公式既是析取范式，又是合取范式 (为什么 ?) 5命题公式的范式 定理 任何命题公式都存在着与之等值的析取范式与合取范式 .求公 式 A的范式的步骤：(1) 消去 A中的 , （若存在）(2) 否定联结词 的内移或消去(3) 使用分配律对 分配（析取范式）对 分配（合取范式）公式的范式存在，但不惟一，这是它的局限性 6求公式的范式举例 例 求下列公式的析取范式与合取范式(1) A=(pq)r解 (pq)r (pq)r （消去 ） pqr （结合律）这既是 A的析取范式（由 3个简单合取式组成的析取式），又是 A的合取范式（由一个简
4、单析取式组成的合取式）7求公式的范式举例 (续 )(2) B=(pq)r解 (pq)r (pq)r （消去第一个 ） (pq)r （消去第二个 ） (pq)r （否定号内移 德摩根律）这一步已为析取范式（两个简单合取式构成）继续： (pq)r (pr)(qr) （ 对 分配律）这一步得到合取范式（由两个简单析取式构成） 8极小项与极大项 定义 在含有 n个命题变项的简单合取式 (简单析取式 )中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第 i（ 1in）个文字出现在左起第 i位上，称这样的简单合取式（简单析取式）为 极小项 （ 极大项 ） .说明： n个命题变项产生 2n个极小
5、项和 2n个极大项2n个极小项（极大项）均互不等值用 mi表示第 i个极小项，其中 i是该极小项成真赋值的十进制表示 . 用 Mi表示第 i个极大项，其中 i是该极大项成假赋值的十进制表示 , mi(Mi)称为极小项 (极大项 )的名称 . mi与 Mi的关系 : mi Mi , Mi mi 9极小项与极大项 (续 )由 p, q两个命题变项形成的极小项与极大项 公式 成真赋值 名称 公式 成假赋值 名称 p qp qp qp q0 00 11 01 1 m0m1m2m3 p q p qp qp q 0 00 11 01 1 M0M1M2M3 极小项 极大项 10由 p, q, r三个命题变项形成的极小项与极大项 极小项 极大项 公式 成真赋值 名称 公式 成假赋值 名称 p q rp q rp q rp q rp q rp q rp q rp q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1m0m1m2m3m4m5m6m7p q r p q r p q r p q r p q r p q r p q r p q r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1M0M1M2M3M4M5M6M7
