命题逻辑等值演算.doc

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）(pq)(qp)（2）(pq)rq（3）(pq)p3.用主析取范式法判断题2中3个公式的类型, 并求公式的成真赋值. 题2中三个公式如下：（1）(pq)(qp)（2）(pq)rq（3）(pq)p4.求题2中3个公式的主合取范式, 并求公式的成假赋值. 题2中三个公式如下：（1）(pq)(qp)（2）(pq)rq（3）(pq)p5.已知命题公式A中含3个命题变项p, q, r, 并知道它的成真赋值分别为001, 010, 111, 求A的主析取范式和主合取范式. 6.用等值演算法证明下面等值式. （1）(pq)(pr)p(qr)（2）(pq)(pq)p7.求公式(pq)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 pq (pq) . 但无论如何不能只含联结词和. （7）、是联结词完备集, 在它中再加一个联结词, 所得集合、也为完备集, 因而任何公式A都能等值地化为联结词集、中的公式.题2分析：（1） (pq)(qp) (pq)(qp) (蕴涵等值式) (pq)(pq) (德摩根律、交换律) (pq)p)q (结合律) (pp)(qp)q (分配律) (1(pq)q (排中律、交换律) p(qq) (同一律、结合律) p1 (排中律) 1 (零律) 由于该公式与1等值, 故它为重言式. （2） (pq)rq (pq)qr (蕴含等值式、交换律) p(qq)r (德摩根律、结合律) p0r (矛盾律) 0 (零律) 由于公式与0等值, 故它为矛盾式. （3） (pq)p (pq)p (蕴含等值式) p (吸收律) 由最后一步可知, 该公式既有成真赋值00和01, 又有成假赋值10和11, 故它为可满足式. 注意：等项演算的过程不是唯一的, 但重言式一定与1等值, 矛盾式一定与0等值. 而可满足式化简到能观察出成真和成假赋值都存在即可. 题3分析：求主析取范式可用真值表法, 也可以用等值演算法, 这里用等值演算法. （1） (pq)(qp) (pq)(qp) (消去) (pq)pq (内移) (已为析取范式) (pq)(pq)(pq)(pq)(pq) （*） m2m0m1m1m3 m0m1m2m3 (幂等律、排序)(*)由p及q派生的极小项的过程如下： pp(qq) (pq)(pq) q(pp)q (pq)(pq)熟练之后, 以上过程可不写在演算过程中. 该公式中含n=2个命题变项, 它的主析取范式中含了22=4个极小项, 故它为重言式, 00, 01, 10, 11全为成真赋值.（2） (pq)rq (pq)rq (消去) pqqr (内移) 0 (矛盾律和零律) 该公式的主析取范式为0, 故它为矛盾式, 00, 01, 10, 11全为成假赋值, 无成真赋值. （3） (pq)p (pq)p (消去) p(pq) (分配律、幂等律) 已为析取范式 (pq)(pq) m0m1 主析取范式中含2个极小项, 成真赋值为00和01. 题4分析：求公式的主合取范式一般可有三种方法： （i） 真值表法； （ii） 等值演算法； （iii）用主析取范式求主合取范式. 这里用方法（iii）, 其余两种方法留给读者. （1）由题3可知, 主析取范式为： (pq)(qp)m0m1m2m3因而该公式为重言式, 它的主合取范式为1, 无成假赋值. （2）由题3可知, 它为矛盾式, 即它的主析取范式为0, 因而无成真赋值, 于是主合取范式含8个极大项, 即： (pq)rqM0M1M2M3M4M5M6M7（3）该公式的主析取范式中含2个极小项m0和m1, 故主合取范式中含22-2=2个极大项M2和M3, 即 (pq)pM2M3成假赋值为10和11. 题5分析：由于公式含3个命题变项, 并且已知有3个成真赋值001, 010, 111, 因而有5个成假赋值000, 011, 100, 101, 110.成真赋值对应的极小项分别为m1, m2, m7, 故主析取范式为 Am1m2m7 成假赋值对应的极大项分别为M0, M3, M4, M5, M6, 故主合取范式为 AM0M3M4M5M6注意：公式的真值表与主析取范式(主合取范式)可以相互唯一确定. 题6分析：用等值演算法证明AB, 可以有3种方式. 从A出发, 证到B；从B出发证到A；或证明AC和BC,由于等值关系有传递性和对称性, 故AB. 题7分析：（1） (pq)r (pq)r (已满足要求)（2） (pq)r (pq)r (pq)r (已满足要求)（3） (pq)r (pq)r (pq)r) (pq)r) (已满足要求)（4） (pq)r (pq)r) (pq)r) ( (pq)r) (已满足要求)（5） (pq)r (pq)r (pq)r (pq)r (pq)r) (pq)r) (pq)r)(pq)r)注意：以上各式的推导和最后形式不唯一. 题8分析：解此类问题的步骤应为： 将简单命题符号化 写出各复合命题 写出由各复合命题组成的合取式 将写出的公式化成析取范式, 给出其成真赋值, 即可得到答案. 具体解法如下： 令 p：派赵去 q：派钱去 r：派孙去 s：派李去 u：派周去 (1) pq (2) su (3) (qr)(qr) (4) (rs)(rs) (5) u(pq) 设A=(pq)(su)(qr)(qr)(rs)(rs) (u(pq) 求A的析取范式(用等值演算法), 简要过程如下： A(pq)(su)(qr)( qr) (rs)(rs)(u(pq) (pq)(qr)(qr)(rs)(rs) (su)(u(pq) (pqr)(qr)(pqr)(rs)(rs) (su)(u(pq) (qr)(pqr)(rs)(rs)(su) (u(pq) （用了吸收律） (pqrs)(qrs)(su)(u(pq) (pqrs)(pqrsu)(qrsu)(u(pq) (pqrsu)(pqrsu) 最后一步得到一个主析取范式, 含有两个极小项. 当p, q, r, s, u取值分别为0, 0, 1, 1, 0 或 1, 1, 0, 0, 1 时, A为真, 故公司应派孙、李去, 而赵、钱、周不去, 或赵、钱、周去, 而孙、李不去. 注意, 在演算中, 多次用了矛盾律和同一律. 返回 例题答案题1答案：（1）为假；（2）为真；（3）为真；（4）为假；（5）为假；（6）为假；（7）为真. 题2答案：（1）为重言式；（2）为矛盾式；（3）为可满足式.题3答案：（1）为重言式, 00, 01, 10, 11为成真赋值.（2）为矛盾式, 无成真赋值. （3）为可满足式, 成真赋值为00和01.题4答案：（1）该公式的主合取范式为1, 无成假赋值.（2）它的主合取范式为：M0M1M2M3M4M5M6M7, 8个赋值全是成假赋值.（3）该公式的主析取范式为M2和M3, 成假赋值为10和11. 题5答案：A的主析取范式为 m1m2m7；A的主合取范式为 M0M3M4M5M6. 题6答案：（1）