析取范式和合取范式.ppt

实例 例2 (1) 求 A ? (?p?q)?(?p??q?r)?r的主析取范式 解 用快速求法 (1) ?p?q ? (?p?q??r)?(?p?q?r) ? m2? m3 ?p??q?r ? m1 r ?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?q?r) ? m1? m3? m5? m7 得 A? m1? m2? m3? m5? m7 ? ?(1,2,3,5,7) * 实例(续) (2) 求 B? ?p?(p?q??r)的主合取范式 解 ?p ? (?p?q?r)?(?p?q??r)?(?p??q?r)?(?p??q??r) ? M4?M5?M6?M7 p?q??r ? M1 得 B? M1?M4?M5?M6?M7 ? ?(1,4,5,6,7) * 主析取范式的用途 (1) 求公式的成真赋值和成假赋值 设公式A含n个命题变项, A的主析取范式有s个极小项, 则A 有s个成真赋值, 它们是极小项下标的二进制表示, 其余2n-s 个赋值都是成假赋值 例如 ?(p?q)??r ? m0? m2? m4 ?m5 ? m6 成真赋值: 000,010,100,101,110; 成假赋值: 001,011,111 * 主析取范式的用途(续) (2) 判断公式的类型 设A含n个命题变项，则 A为重言式当且仅当A的主析取范式含2n个极小项 A为矛盾式当且仅当 A的主析取范式不含任何极小项,记作0 A为可满足式当且仅当A的主析取范式中至少含一个极小项 * 实例 例3 用主析取范式判断公式的类型: (1) A? ?(p?q)?q (2) B? p?(p?q) (3) C? (p?q)?r 解 (1) A ? ?(? p?q)?q ? ( p??q)?q ? 0 矛盾式 (2) B ? ? p?(p?q) ? 1 ? m0?m1?m2?m3 重言式 (3) C ? ?(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?m1?m3? m5?m7 非重言式的可满足式 * 主析取范式的用途(续) (3) 判断两个公式是否等值 例4 用主析取范式判断下面2组公式是否等值: (1) p与(?p?q)?(p?q) 解 p ? p?(?q?q) ? (p??q)?(p?q) ? m2?m3 (?p?q)?(p?q) ? ?(?p?q)?(p?q) ? (p??q)?(p?q) ? m2?m3 故 p ? (?p?q)?(p?q) * 实例(续) * (2) (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?q)?(p? r) ?(p?q??r)?(p?q?r)?(p??q?r)?(p?q?r) ? m5? m6?m7 故 (p?q)?r p?(q?r) 实例 例5 某单位要从A,B,C三人中选派若干人出国考察, 需满 足下述条件: (1) 若A去, 则C必须去; (2) 若B去, 则C不能去; (3) A和B必须去一人且只能去一人. 问有几种可能的选派方案? 解 记p:派A去, q:派B去, r:派C去 (1) p?r, (2) q??r, (3) (p??q)?(?p?q) 求下式的成真赋值 A=(p?r)?(q??r)?((p??q)?(?p?q)) * 实例(续) 求A的主析取范式 A=(p?r)?(q??r)?((p??q)?(?p?q)) ? (?p?r)?(?q??r)?((p??q)?(?p?q)) ? ((?p??q)?(?p??r)?(r??q)?(r??r)) ?((p??q)?(?p?q)) ? ((?p??q)?(p??q))?((?p??r)?(p??q)) ?((r??q)?(p??q))?((?p??q)?(?p?q))