离散数学习题答案文档格式.docx
《离散数学习题答案文档格式.docx》由会员分享，可在线阅读，更多相关《离散数学习题答案文档格式.docx（73页珍藏版）》请在冰点文库上搜索。
p
q
（¬
p→q）
q
q∨p）
0
1
1
存在主析取范式=成真赋值对应的小项的析取
=m00∨m10∨m11=（¬
q）∨（p∧¬
q）∨（p∧q）
主析取范式=成假赋值对应的大项的合取
=M01=p∨¬
等值演算：
⇔¬
（¬
p∨q）∨（p∨¬
q）
（p∨q）∨（p∨¬
⇔（¬
q）∨（p∨¬
p∨（p∨¬
q））∧（¬
q∨（p∨¬
q））
p∨p∨¬
q）∧（¬
q∨p∨¬
⇔（1∨¬
q）∧（p∨¬
⇔（p∨¬
这是大项，故为大项的合取，称为主合取范式
⇔（p）∨（¬
⇔（p∧1）∨（1∧¬
⇔（p∧（q∨¬
q））∨（（p∨¬
⇔（p∧q）∨（p∧¬
q）∨（¬
q）
因为一个公式的值不是真，就是假，因此当我们得到一个公的取值为真的情况时，剩下的组合是取值为假，因此当得到小项的析取组成的主析取范式后，可以针对剩下的组合写出主合取范式。
如当我们得到（¬
q∨p）的大项之合取（p∨¬
q）后，使（p∨¬
q）为假时（p,q）的值为（0,1），故其标记为M01，剩余的取值为（0,0）,（1,0）,（1,1），故小项之析取为m00∨m10∨m11。
反之，若先得到其小项的析取，也可得到其大项的合取。
反正这两者将其所有组合瓜分完毕。
p→q）→（q∧r）
r
p→q
（q∧r）
结果
主析取范式=m000∨m001∨m011∨m111=（¬
q∧¬
r）∨（¬
q∧r）∨（¬
p∧q∧r）∨（p∧q∧r）
主合取范式=M010∧M100∧M101∧M110=（p∨¬
q∨r）∧（¬
p∨q∨r）∧（¬
p∨q∨¬
r）∧（¬
p∨¬
q∨r）
（3）（p∨（q∧r））→（p∨q∨r）
（p∨（q∧r））
（p∨q∨r）
→（p∨q∨r）
永真式，所有小项的析取得到其主析取范式
=（¬
p∧q∧¬
p∧q∧r）∨（p∧¬
r）∨（p∧¬
q∧r）∨（p∧q∧¬
r）∨（p∧q∧r）
由于没为假的指派，所以没有为假赋值，所对应的大项合取构成的合取，即没有主合取范式。
（p∨（q∧r））∨（p∨q∨r）=（¬
（q∧r））∨（p∨q∨r）=（（¬
q）∨（¬
r））∨（p∨q∨r）=
r）∨p∨q∨r=¬
（p∨q）∨（¬
r）∨p∨q∨r=1永真
p）
没有成真的赋值，从而没有对应的小项，因此没有小项构成的主析取范式
永假式即矛盾式，为假指派对应的大项合取=（p∨q）∧（p∨¬
p∨q）∧（¬
原式=¬
q∨¬
p=（q∧p）∧¬
p=0
（5）（p∧q）∨（¬
p∨r）
（p∧q）
（p∧q）∨（¬
主析取范式
r）∨（¬
q∧r）∨（¬
主合取范式
M100=¬
p∨q∨r
原式=（（p∧q）∨¬
p）∨r=（（p∨¬
p）∧（¬
p∨q））∨r=（1∧（¬
p∨q））∨r=¬
p∨q∨r这就是大项也
剩下的赋值对应的就是小项
（6）（p→（p∨q））∨r
（p∨q）
（p→（p∨q））
（p→（p∨q））∨r
永真式，只有小项组成的主析取范式。
没有为假的赋值，所以没有成假赋值对应的大项的合取，即没有主合取范式。
原式=（¬
p∨（p∨q））∨r=（1∨q）∨r=1
（7）（p∧q）∨r
（p∧q）∨r
主析取范式=m001∨m011∨m101∨m110∨m111=
p∧q∧r）∨（p∧¬
主合取范式=M000∧M010∧M100=（p∨q∨r）∧（p∨¬
q∨r）∧（¬
p∨q∨r）
（p∧q）∨r
=（p∧q∧1）∨（1∧1∧r）
=（p∧q∧（¬
r∨r））∨（（¬
p∨p）∧（¬
q∨q）∧r）
=（p∧q∧¬
r）∨（p∧q∧r）∨（¬
p∧q∧r）∨（p∧¬
q∧r）
=（p∨r）∧（q∨r）
=（p∨0∨r）∧（0∨q∨r）
=（p∨（¬
q∧q）∨r）∧（（¬
p∧p）∨q∨r）
=（p∨¬
q∨r）∧（p∨q∨r）∧（¬
p∨q∨r）∧（p∨q∨r）
p∨q∨r）
（8）（p→q）∧（q→r）
（p→q）
（q→r）
（p→q）∧（q→r）
主析取范式=m000∨m001∨m011∨m111
主合取范式=M010∧M100∧M101∧M110=
q∨r）
（p→q）∧（q→r）=（¬
p∨q∨0）∧（0∨¬
p∨q∨（¬
r∧r））∧（（¬
p∧p）∨¬
r）∧（¬
p∨q∨r）∧（¬
q∨r）∧（p∨¬
p∧r）∨（q∧¬
q）∨（q∧r）
q∧1）∨（¬
p∧1∧r）∨（1∧q∧r）
q∧（¬
r∨r））∨（¬
p∧（¬
q∨q）∧r）∨（（¬
p∨p）∧q∧r）
r）∨（¬
q∧r）∨（¬
p∧q∧r）∨（¬
p∧q∧r）∨（p∧q∧r）
p∧q∧r）∨（p∧q∧r）
（9）（p∧q）→q
（p∧q）→q
永真式，只有小项的析取构成的主析取范式=（¬
q）∨（¬
p∧q）∨（p∧¬
没有为假的指派，所以没有由大项的合取构成的主合取范式
（p∧q）→q
=¬
（p∧q）∨q
q）∨q
q∨q
=1
r↔p
（r↔p）
主析取范式=m110=p∧q∧¬
r
主合取范式=M000∧M001∧M010∧M011∧M100∧M101∧M111
=（p∨q∨r）∧（p∨q∨¬
r）∧（p∨¬
q∨r）∧（p∨¬
r）∧（¬
p∨q∨r）∧（¬
r）
（r↔p）∧p∧q
（（¬
p∨r）∧（p∨¬
r））∧p∧q
=（（p∧¬
r）∨（¬
p∧r））∧p∧q
=（p∧¬
r∧p∧q）∨（¬
p∧r∧p∧q）
=（p∧q∧¬
（（p∧r）∨（¬
=（（¬
r）∧（p∨r））∧p∧q
=（¬
r）∧（p∨r）∧p∧q
r）∧（（p∨r）∧p）∧q
r）∧p∧q
p∨（¬
q∧q）∨¬
r）∧（p∨（¬
q∧q）∨（¬
p∧p）∨q∨（¬
r∧r））
r）∧
（p∨¬
q∨r）∧（p∨q∨¬
r）∧（p∨q∨r）∧
∧（¬
r）∧（¬
p∨q∨r）∧（p∨q∨¬
r）∧（p∨q∨r）
=（p∨q∨r）∧（p∨q∨¬
r）∧（p∨¬
q∨r）∧（p∨¬
r）∧（¬
p∨q∨r）∧（¬
=M000∧M001∧M010∧M011∧M100∧M101∧M111
二、应用题
1、某次课间休息时，1位同学作为主持人与另外3位同学进行猜数游戏，主持人说这个数是30、50、70中的某一个，你们三位同学各猜一次，然后主持人分析每人猜数的结果，从而最终确定是哪个数。
同学1说：
这个数是30，不是50
同学2说：
这个数是50，不是70
同学3说：
这个数既不是30，也不是50
主持人听后说道：
你们3人中，有一人全对，有二人对了一半，请问到底是哪个数。
令S表示“这个数是30”，W表示“这个数是50”，Q表示“这个数是70”
同学1的话：
S∧¬
W
同学2的话：
W∧¬
Q
同学3的话：
对于每个人来说，只有二个选择：
全对、对一半，对一半又分成：
第一句对第二句错、第一句错第二句对，因此每个同学的对错情况为：
√√、√×
、×
√，因此3个人共有3*3*3=27种可能的情况，其中有些情况不符合“有一人全对，有二人对了一半”而剔除。
我们按“√√、√×
√”顺序，构造“类真值表”来分析其组合情况
同学1
同学2
同学3
命题公式
分析
√√
不必写
不可能全对
√×
不可能有2个对
W∧W∧Q∧¬
S∧W=0
真值为0不对
W∧W∧Q∧S∧¬
W=0
W∧Q∧¬
Q∧S∧¬
W=S∧¬
Q
可能对的，是30
不是50，不是70
S∧W∧W∧¬
Q∧¬
S∧W=0
不可能
Q∧S∧¬
S∧W∧W∧Q∧¬
S∧W∧¬
×
S,¬
W,W,¬
Q,S,W=0
√
S,¬
Q,S,¬
W,W,Q,¬
S，¬
W，¬
Q，¬
W=
3个数都不是，不可能
答案是：
是30，不是50，不是70
这个数是30，不是50全对
这个数是50，不是70第一句错第二句对
这个数既不是30，也不是50第一句错第二句对
2、设计一个如下的电路图：
它有三个输入p1、p2、p3，当其中有2个及以上的值为1时输出的结果为1，其他情况下输出0。
请给出其真值表，同时针对此真值表给出主析取范式、主合取范式，并给出其最简单的表达式。
答：
与课堂例题一样
在真实的教材将其换成了如下习题
它有三个输入p1、p2、p3，当其中任意二个的值为0时输出的结果为1，其他情况下输出0。
p1
p2
p3
表达式的值
其主析取范式=m000∨m001∨m010∨m100
p1∧¬
p2∧¬
p3）∨（¬
p2∧p3）∨（¬
p1∧p2∧¬
p3）∨（p1∧¬
p3）
=（（¬
p2）∧（¬
p3∨∧p3））∨（（（¬
p1∧p2）∨（p1∧¬
p2））∧¬
p2）∨（（（¬
其主合取范式=M011∧M101∧M110∧M111
=（p1∨¬
p2∨¬
p3）∧（¬
p∨p2∨¬
p1∨¬
p2∨p3）∧（¬
pq∨¬
=（（（p1∨¬
p1∨p2））∨¬
p3）∧（¬
p2）
3、某年级要从1班、2班、3班、4班、5班中选出一名才子主持元旦晚会，每班最多一人，也可能没有，这些人满足如下条件，请确定最终选择哪些班级的学生：
（1）如果1班有人选中，则2班有人选中。
（2）若5班有人选上则1班与2班均有人选上。
（3）5班与4班必有一班有被选中。
（4）3班与4班同时有人选上或同时没人选上。
用One表示1班选了人，Two表示2班选了人，Three表示3班选了人，Four表示4班选了人，Five表示5班选了人。
则这4个条件依次为
One→Two，Five→（One∧Two），Four∨Five，Three↔Four
满足这4个条件，即这4个条件的值均为真即为1，所以其合取为1
（One→Two）∧（Five→（One∧Two））∧（Four∨Five）∧（Three↔Four）=1，
将以上合取范式转换为主析取范式，因此双条件应转换为析取式的合取式
原式=
One∨Two）∧（¬
Five∨（One∧Two））∧（Four∨Five）∧（（¬
Three∨Four）∧（Three∨¬
Four））
=[（¬
Five∨（One∧Two））]∧（Four∨Five）∧（¬
Four）
One∧¬
Five）∨（¬
One∧（One∧Two）∨（Two∧¬
Five）∨（Two∧（One∧Two）]∧（Four∨Five）∧（¬
={[（¬
Five）∨（Two∧¬
Five）∨（Two∧One）]∧（Four∨Five）}
∧（¬
Five∧Four）∨（Two∧¬
Five∧Four）∨（Two∧One∧Four）∨（Two∧One∧Five）]
Three∨Four）}∧（Three∨¬
={（¬
Five∧Four∧¬
Three）∨
Five∧Four）∨
（Two∧¬
Five∧Four∧¬
（Two∧One∧Four∧¬
（Two∧One∧Four）∨
（Two∧One∧Five∧¬
（Two∧One∧Five∧Four）}∧（Three∨¬
Five∧Four∧Three）∨
（Two∧¬
Five∧Four∧Three）∨
（Two∧One∧Four∧Three）∨
Three∧¬
Four）∨
（Two∧One∧Five∧Four∧Three）
One∧Three∧Four∧¬
Five）∨
（Two∧Three∧Four∧¬
（One∧Two∧Three∧Four）∨
（One∧Two∧¬
Three∧¬
Four∧Five）∨
（One∧Two∧Three∧Four∧Five）
一班
二班
三班
四班
五班
条件1
条件2
条件3
条件4
方案一
无
不限
有
满足
方案二
方案三
方案四
方案五
按照某位帅哥的质疑，经仔细思考，应该将其转换为主析取范式，所以最终结果为：
One∧1∧Three∧Four∧¬
（1∧Two∧Three∧Four∧¬
（One∧Two∧Three∧Four∧1）∨
（One∧Two∧Three∧Four∧Five）
Two∧Three∧Four∧¬
Five）∨（¬
One∧Two∧Three∧Four∧¬
One∧Two∧Three∧Four∧¬
Five）∨（One∧Two∧Three∧Four∧¬
（One∧Two∧Three∧Four∧¬
Five）∨（One∧Two∧Three∧Four∧Five）∨
Four∧Five）∨（One∧Two∧Three∧Four∧Five）
（One∧Two∧Three∧Four∧¬
Four∧Five）
满
升级会员 