1.
设A与B均为含n个命题变项的公式, 判断下列命题是否为真？
（1）A
B 当且仅当 AB是可满足式. 该命题为假
该命题为真
（2）A
B 当且仅当 A与B有相同的主析取范式.
该命题为真
该命题为假
n
（3）若A为重言式, 则A的主析取范式中含有2个极小项.
该命题为真
该命题为假
（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)∧┐p
3.
用主析取范式法判断题2中3个公式的类型, 并求公式的成真赋值.
题2中三个公式如下： （1）(p→q)→(┐q→┐p) （2）┐(p→q)∧r∧q （3）(p→q)∧┐p
4.
求题2中3个公式的主合取范式, 并求公式的成假赋值.
题2中三个公式如下：
（1）(p→q)→(┐q→┐p) （2）┐(p→q)∧r∧q （3）(p→q)∧┐p
5.
已知命题公式A中含3个命题变项p, q, r, 并知道它的成真赋值分别为001, 010, 111, 求A的主析取范式和主合取范式.
6.
（1）(┐p∨q)∧(p→r)p→(q∧r)
（2）(p∧q)∨┐(┐p∨q)
用等值演算法证明下面等值式.
p
7.
求公式(p→┐q)∧r在以下各联结词完备集中与之等值的一个公式：
（1）{┐,∧, ∨} （2）{┐,∧} （3）{┐,∨} （4）{┐, →} （5）{↑}
8.
用等值演算法求解下面问题.
某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习. 选派必须满足以下条件：
（1）若赵去, 则钱也去 （2）李、周中至少去一人 （3）钱、孙中去且仅去一人 （4）孙、李两人都去或都不去 （5）若周去, 则赵、钱也同去 问该公司应选派哪些人出国？
例题分析
题1分析：
（1）A（2）A式,
B 当且仅当 AB为重言式, 而不是可满足式.
B说明A与B有相同的成真赋值, 因而有相同的主析取范式；反之若A与B有相同的主析取范
说明它们有相同的成真赋值,当然也有相同的成假赋值. 因而A
n
B为重言式,故A
n
B.
（3）若A为重言式, 说明2个赋值都是成真赋值, 因而主析取范式中含有2个极小项.
（4）若A为矛盾式, 则A无成真赋值, 因而A的主析取范式不含任何极小项, 规定A的主析取范式为0, 而 不是1. 若是1, 则A
1, 这与A为矛盾式不是矛盾了吗？
n
n
（5）若A为矛盾式, 则A的2个赋值都是成假赋值, 因而主合取范式应含有2个极大项, 而不是1. 若为1,
则A
1, A不就成了重言式了吗？
（6）{∧、∨}不是联结词完备集. 因而, 有的公式不能等值地化为它中的公式. 例如： p
q
┐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
q
(┐p∨p)∧q (┐p∧q)∨(p∧q)
2
┐p∧(┐q∨q)
(┐p∧┐q)∨(┐p∧q)
熟练之后, 以上过程可不写在演算过程中. 该公式中含n=2个命题变项, 它的主析取范式中含了2=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∧q) m0∨m1
(┐p∨q)∧┐p (消去→)
┐p∨(┐p∧q) (分配律、幂等律) 已为析取
主析取范式中含2个极小项, 成真赋值为00和01.
相关推荐：
loading