离散数学命题逻辑等值演算.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 练习7:消解法 7. 用消解法判断下述公式是否是可满足的: (p??q)?(q??r)?(?q??r) 解 S=(p??q)?(q??r)?(?q??r) 第1次循环 S0=?,S1={p??q, q??r, ?q??r}, S2=? p??q, q??r 消解得到p??r q??r, ?q??r消解得到?r S2={p??r,?r} 第2次循环 S0={p??q, q??r, ?q??r},S1={p??r,?r}, S2=? S2=? 输出“Yes”,计算结束. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 3. 判断两个公式是否等值 例8 用主析取范式判以下每一组公式是否等值 ⑴ p?(q?r) 与 (p?q)?r ⑵ p?(q?r) 与 (p?q)?r 解 p?(q?r) = m0?m1?m2?m3? m4?m5? m7 (p?q)?r = m0?m1?m2?m3? m4?m5? m7 (p?q)?r = m1?m3? m4?m5? m7 显见，⑴中的两公式等值，而⑵的不等值. 主范式的应用 * 4. 解实际问题 例9 某单位要从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)) ?((?p??r)?(?p?q))?((r??q)?(?p?q)) ? (p??q?r)?(?p?q??r) 成真赋值:101,010 结论: 方案1 派A与C去, 方案2 派B去 主范式的应用 * 由主析取范式确定主合取范式 例10 设A有3个命题变项, 且已知A= m1?m3?m7, 求A的主合取 范式. 解 A的成真赋值是1,3,7的二进制表示, 成假赋值是在主析取 范式中没有出现的极小项的下角标0,2,4,5,6的二进制表示, 它 们恰好是A的主合取范式的极大项的下角标, 故 A ? M0?M2?M4?M5?M6 用成真赋值和成假赋值确定主范式 由主合取范式确定主析取范式 用真值表确定主范式 * 3 联结词的完备集 定义6 称F:{0,1}n? {0,1} 为n元真值函数. {0,1}n={00…0, 00…1, …, 11…1}，包含 个长为n的0,1符号串. 共有 个n元真值函数. 1元真值函数 p 0 0 0 1 1 1 0 1 0 1 * 真值函数 p q 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 p