面向对象程序设计1.5.ppt

1.5 对偶与范式 对偶式与对偶原理 析取范式与合取范式 主析取范式与主合取范式 对偶式和对偶原理 定义 在仅含有联结词?, ∧,∨的命题公式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，B为两个命题公式， 若A ? B，则A* ? B*. 析取范式与合取范式 文字:命题变项及其否定的总称 简单析取式:有限个文字构成的析取式 如 p, ?q, p??q, p?q?r, … 简单合取式:有限个文字构成的合取式 如 p, ?q, p??q, p?q?r, … 析取范式:由有限个简单合取式组成的析取式 A1?A2???Ar, 其中A1,A2,?,Ar是简单合取式 合取范式:由有限个简单析取式组成的合取式 A1?A2???Ar , 其中A1,A2,?,Ar是简单析取式 析取范式与合取范式 析取范式:由有限个简单合取式组成的析取式 A1?A2???Ar, 其中A1,A2,?,Ar是简单合取式 例如: (p??q)?(p?q?r) 合取范式:由有限个简单析取式组成的合取式 A1?A2???Ar , 其中A1,A2,?,Ar是简单析取式 例如: (p??q)?(p?q?r) 析取范式与合取范式(续) 范式:析取范式与合取范式的总称? 公式A的析取范式: 与A等值的析取范式 公式A的合取范式: 与A等值的合取范式 说明： 单个文字既是简单析取式，又是简单合取式 p??q?r, ?p?q??r既是析取范式，又是合取范式 (为什么?) 命题公式的范式 定理 任何命题公式都存在着与之等值的析取范式 与合取范式. 求公式A的范式的步骤： (1) 消去A中的?, ?（若存在） (2) 否定联结词?的内移或消去 (3) 使用分配律 ?对?分配（析取范式） ?对?分配（合取范式） 公式的范式存在，但不惟一 范式存在定理 定理任何命题公式都存在着与之等值的析取范式与合取范式. 证 求公式A的范式的步骤： (1) 消去A中的?, ? A?B??A?B A?B ?(A?B)?(B?A) ?(?A?B)?(A??B) 范式存在定理 (2) 否定联结词?的内移或消去 ?(A?B)??A??B ?(A?B)??A??B ??A? A (3) 使用分配律 A?(B?C)?(A?B)?(A?C) 求合取范式 A?(B?C)?(A?B)?(A?C) 求析取范式 范式存在定理(续) 例1 求?(p?q)??r 的析取范式与合取范式 范式存在定理(续) 例1 求?(p?q)??r 的析取范式与合取范式 解 ?(p?q)??r ? ?(?p?q)??r (蕴涵等值式) ? (??p??q)??r (德模根律) ? (p??q)??r (双重否定律) 析取范式 范式存在定理(续) 注意: 公式的析取范式与合取范式不惟一. ?(p?q)??r ? (p??q)??r ? (p??q)?(?r?1) (同一律) ?(p??q)?(?r?(p??p)) (排中律) ? (p??q)?(?r?p)?(?r??p)) (分配律) 极小项与极大项 定义 在含有n个命题变项的简单合取式(简单析取式)中， 若每个命题变项均以文字的形式在其中出现且仅出现一 次，而且第i（1?i?n）个文字出现在左起第i位上，称这样 的简单合取式（简单析取式）为极小项（极大项）. 说明：n个命题变项产生2n个极小项和2n个极大项 2n个极小项（极大项）均互不等值 用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示. 用Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示, mi(Mi)称为极小项(极大项)的名称. mi与Mi的关系: ?mi ? Mi , ?Mi ? mi 极小