命题逻辑等值演算.docx

《命题逻辑等值演算.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、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用等值演算法来判断下列公式

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)

3、∧(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有相同的成真赋

4、值,因而有相同的主析取范式；反之若A与B有相同的主析取范式,说明它们有相同的成真赋值,当然也有相同的成假赋值.因而AB为重言式,故AB.（3）若A为重言式,说明2n个赋值都是成真赋值,因而主析取范式中含有（4）若A为矛盾式,则A无成真赋值,因而A的主析取范式不含任何极小项不是1.若是1,则A1,这与A为矛盾式不是矛盾了吗？2n个极小项.,规定A的主析取范式为0,而（5）若A为矛盾式,则A的2n个赋值都是成假赋值,因而主合取范式应含有2n个极大项,而不是1.若为1,则A1,A不就成了重言式了吗？（6）{∧、∨}不是联结词完备集.因而

5、,有的公式不能等值地化为它中的公式.例如：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(排中

6、律)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分析：求主析取范式

7、可用真值表法,也可以用等值演算法,这里用等值演算法.（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∨m3m0∨m1∨m2∨m3(幂等律、排序)(*)由┐p及q派生的极小项的过程如下：┐p┐p∧(┐q∨q)(┐p∧┐q)∨(┐p∧q)q(┐p∨p)∧q(┐p∧q)∨(p∧q)熟练之后,以上过程可不写在演算过程中.该