命题逻辑等值演算.doc
9页
1.设A与B均为含n个命题变项的公式, 判断下列命题与否为真？ （1）AB 当且仅当 AB是可满足式. 该命题为真 该命题为假 （2）AB 当且仅当 A与B有相似的主析取范式. 该命题为真 该命题为假 （3）若A为重言式, 则A的主析取范式中具有2n个极小项. 该命题为真 该命题为假 （4）若A为矛盾式, 则A的主析取范式为1. 该命题为真 该命题为假 （5）若A为矛盾式, 则A的主合取范式为1. 该命题为真 该命题为假 （6）任何公式A都能等值地化为联结词集{∧、∨} 中的公式. 该命题为真 该命题为假 （7）任何公式A都能等值地化为联结词集{┐、→、∧}中的公式. 该命题为真 该命题为假 2.用等值演算法来判断下列公式的类型. （1）(p→q)→(┐q→┐p) （2）┐(p→q)∧r∧q （3）(p→q)∧┐p3.用主析取范式法判断题2中3个公式的类型, 并求公式的成真赋值. 题2中三个公式如下： （1）(p→q)→(┐q→┐p) （2）┐(p→q)∧r∧q （3）(p→q)∧┐p4.求题2中3个公式的主合取范式, 并求公式的成假赋值. 题2中三个公式如下： （1）(p→q)→(┐q→┐p) （2）┐(p→q)∧r∧q （3）(p→q)∧┐p5.已知命题公式A中含3个命题变项p, q, r, 并懂得它的成真赋值分别为001, 010, 111, 求A的主析取范式和主合取范式. 6.用等值演算法证明下面等值式. （1）(┐p∨q)∧(p→r)p→(q∧r) （2）(p∧q)∨┐(┐p∨q)p7.求公式(p→┐q)∧r在如下各联结词完备集中与之等值的一种公式： （1）{┐,∧, ∨} （2）{┐,∧} （3）{┐,∨} （4）{┐, →} （5）{↑}8.用等值演算法求解下面问题. 某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派某些人出国学习. 选派必须满足如下条件： （1）若赵去, 则钱也去 （2）李、周中至少去一人 （3）钱、孙中去且仅去一人 （4）孙、李两人都去或都不去 （5）若周去, 则赵、钱也同去 问该公司应选派哪些人出国？ 例题分析 题1分析：（1）AB 当且仅当 AB为重言式, 而不是可满足式.（2）AB阐明A与B有相似的成真赋值, 因而有相似的主析取范式；反之若A与B有相似的主析取范式, 阐明它们有相似的成真赋值,固然也有相似的成假赋值. 因而AB为重言式,故AB. （3）若A为重言式, 阐明2n个赋值都是成真赋值, 因而主析取范式中具有2n个极小项. （4）若A为矛盾式, 则A无成真赋值, 因而A的主析取范式不含任何极小项, 规定A的主析取范式为0, 而不是1. 若是1, 则A1, 这与A为矛盾式不是矛盾了吗？（5）若A为矛盾式, 则A的2n个赋值都是成假赋值, 因而主合取范式应具有2n个极大项, 而不是1. 若为1, 则A1, A不就成了重言式了吗？（6）{∧、∨}不是联结词完备集. 因而, 有的公式不能等值地化为它中的公式. 例如： pq ┐p∨q ┐(p∧┐q) ... 但无论如何不能只含联结词∧和∨. （7）{┐、→}是联结词完备集, 在它中再加一种联结词∧, 所得集合{┐、→、∧}也为完备集, 因而任何公式A都能等值地化为联结词集{┐、→、∧}中的公式.题2分析：（1） (p→q)→(┐q→┐p) ┐(┐p∨q)∨(q∨┐p) (蕴涵等值式) (p∧┐q)∨(┐p∨q) (德·摩根律、互换律) ((p∧┐q)∨┐p)∨q (结合律) ((p∨┐p)∧(┐q∨┐p))∨q (分派律) (1∧(┐p∨┐q))∨q (排中律、互换律) ┐p∨(┐q∨q) (同一律、结合律) ┐p∨1 (排中律) 1 (零律) 由于该公式与1等值, 故它为重言式. （2） ┐(p→q)∧r∧q ┐(┐p∨q)∧q∧r (蕴含等值式、互换律) p∧(┐q∧q)∧r (德·摩根律、结合律) p∧0∧r (矛盾律) 0 (零律) 由于公式与0等值, 故它为矛盾式. （3） (p→q)∧┐p (┐p∨q)∧┐p (蕴含等值式) ┐p (吸取律) 由最后一步可知, 该公式既有成真赋值00和01, 又有成假赋值10和11, 故它为可满足式. 注意：等项演算的过程不是唯一的, 但重言式一定与1等值, 矛盾式一定与0等值. 而可满足式化简到能观测出成真和成假赋值都存在即可. 题3分析：求主析取范式可用真值表法, 也可以用等值演算法, 这里用等值演算法. （1） (p→q)→(┐q→┐p) ┐(┐p∨q)∨(q∨┐p) (消去→) (p∧┐q)∨┐p∨q (┐内移) (已为析取范式) (p∧┐q)∨(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q) （*） m2∨m0∨m1∨m1∨m3 m0∨m1∨m2∨m3 (幂等律、排序)(*)由┐p及q派生的极小项的过程如下： ┐p┐p∧(┐q∨q) (┐p∧┐q)∨(┐p∧q) q(┐p∨p)∧q (┐p∧q)∨(p∧q)纯熟之后, 以上过程可不写在演算过程中. 该公式中含n=2个命题变项, 它的主析取范式中含了22=4个极小项, 故它为重言式, 00, 01, 10, 11全为成真赋值.（2） ┐(p→q)∧r∧q ┐(┐p∨q)∧r∧q (消去→) p∧┐q∧q∧r (┐内移) 0 (矛盾律和零律) 该公式的主析取范式为0, 故它为矛盾式, 00, 01, 10, 11全为成假赋值, 无成真赋值. （3） (p→q)∧┐p (┐p∨q)∧┐p (消去→) ┐p∨(┐p∧q) (分派律、幂等律) 已为析取范式 (┐p∧┐q)∨(┐p∧q) m0∨m1 主析取范式中含2个极小项, 成真赋值为00和01. 题4分析：求公式的主合取范式一般可有三种措施： （i） 真值表法； （ii） 等值演算法； （iii）用主析取范式求主合取范式. 这里用措施（iii）, 其他两种措施留给读者. （1）由题3可知, 主析取范式为： (p→q)→(┐q→┐p)m0∨m1∨m2∨m3因而该公式为重言式, 它的主合取范式为1, 无成假赋值. （2）由题3可知, 它为矛盾式, 即它的主析取范式为0, 因而无成真赋值, 于是主合取范式含8个极大项, 即： ┐(p→q)∧r∧qM0∧M1∧M2∧M3∧M4∧M5∧M6∧M7（3）该公式的主析取范式中含2个极小项m0和m1, 故主合取范式中含22-2=2个极大项M2和M3, 即 (p→q)∧┐pM2∧M3成假赋值为10和11. 题5分析： 由于公式含3个命题变项, 并且已知有3个成真赋值001, 010, 111, 因而有5个成假赋值000, 011, 100, 101, 110.成真赋值相应的极小项分别为m1, m2, m7, 故主析取范式为 Am1∨m2∨m7 成假赋值相应的极大项分别为M0, M3, M4, M5, M6, 故主合取范式为 AM0∧M3∧M4∧M5∧M6注意：公式的真值表与主析取范式(主合取范式)可以互相唯一拟定. 题6分析： 用等值演算法证明AB, 可以有3种方式. 从A出发, 证到B；从B出发证到A；或证明AC和BC,由于等值关系有传递性和对称性, 故AB. 题7分析： （1） (p→┐q)∧r (┐p∨┐q)∧r (已满足规定) （2） (p→┐q)∧r (┐p∨┐q)∧r ┐(p∧q)∧r (已满足规定) （3） (p→┐q)∧r (┐p∨┐q)∧r ┐┐((┐p∨┐q)∧r) ┐(┐(┐p∨┐q)∨┐r) (已满足规定) （4） (p→┐q)∧r ┐┐((p→┐q)∧r) ┐(┐(p→┐q)∨┐r) ┐( (p→┐q)→┐r) (已满足规定) （5） (p→┐q)∧r (┐p∨┐q)∧r ┐(p∧q)∧r (p↑q)∧r ┐┐((p↑q)∧r) ┐((p↑q)↑r) ((p↑q)↑r)↑((p↑q)↑r) 注意：以上各式的推导和最后形式不唯一. 题8分析：解此类问题的环节应为： ① 将简朴命题符号化 ② 写出各复合命题 ③ 写出由各复合命题构成的合取式 ④ 将写出的公式化成析取范式, 给出其成真赋值, 即可得到答案. 具体解法如下： ① 令 p：派赵去 q：派钱去 r：派孙去 s：派李去 u：派周去 ② (1) p→q (2) s∨u (3) ((q∧┐r)∨(┐q∧r)) (4) ((r∧s)∨(┐r∧┐s)) (5) u→(p∧q) ③ 设A=(p→q)∧(s∨u)∧((q∧┐r)∨(┐q∧r))∧((r∧s)∨(┐r∧┐s)) ∧(u→(p∧q)) ④ 求A的析取范式(用等值演算法), 简要过程如下： A(┐p∨。
