发布时间 : 星期六 文章离散数学习题解答（耿素云屈婉玲）北京大学出版社更新完毕开始阅读037b805e83c4bb4cf6ecd146
去找 QQ头像 http://www.7zhao.net
??(?(?p?r)??(p??r)) （c）F??p??q?r
28.一个排队线路，输入为A、B、C，其输出分别为FA、FB、FC.本线路中，在同一时间只能有一个信号通过，若同时有两个或两个以上信号申请输出时，则按A、B、C的顺序输出，写出FA、FB、FC在联结词完备集{?，?}中的表达式.
答：p：A输入，q：B输入，r：C输入.有题意可得：
FA?(p??q??r)?(p??q?r)?(p?q??r)?(p?q?r)
?(p??q)?(p?q)?p
FB?(?p?q??r)?(?p?q?r)??p?q FC??p?q?r
29.在某班班委成员的选举中，已知王小红、李强、丁金生3位同学被选进了班委会.该班的甲、乙、丙三名学生预言：
甲说：王小红为班长，李强为生活委员. 乙说：丁金生为班长，王小红为生活委员. 丙说：李强为班长，王小红为学习委员.
班委会分工名单公布后发现，甲、乙、丙三人都恰好猜对了一半.问王小红、李强、丁金生各任何职（用等值等演求解）？
答：设p：王小红为班长，q：李强为生活委员
r：丁金生为班长，s：王小红为生活委员 t：李强为班长，w：王小红为学习委员
由题意得，p、q有且只有一个为真，r、s有且只有一个为真，t、w有且只有一个为真.
若p为真，则q为假，那么r为假，则s为真，这样p与s矛盾，因此这种假设行不通. 若p为假，则q为真，那么t为假，则w为真，则s为假，所以r为真，因此王小红、李强、丁金生的职位分别是：学习委员、生活委员、班长.
30.某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习.选派必须满足以下条件：
（1）若赵去，钱也去.
（2）李、周两人中必有一人去. （3）钱、孙两人中去且仅去一人. （4）孙、李两人同去或同不去. （5）若周去，则赵、钱也同去.
用等值演算法分析该公司如何选派他们出国？
答：设p：派赵去，q：派钱去，r：派李去，s：派孙去，t：派周去
首先以条件（2）为基础，有三种情况： ① 若周去，李不去，由条件（5）得则赵、钱同去，由条件（3）得那么孙不去，符合
文章来源：http://www.7zhao.net
去找 QQ头像 http://www.7zhao.net
5个条件，即p?q??r??s?t.
② 若李去，周不去，由条件（4）得则孙去，从而由条件（3）得钱不去，而由条件（1）
得赵也不去，即?p??q?r?s??t. ③ 若周、李都去，那么由条件（4）得则孙去，由条件（5）得赵、钱都去，这样孙和
钱都去，与条件（3）矛盾，因此这种情况不存在. 习题三
1.从日常生活或数学中的各种推理中，构造两个满足附加律的推理定律，并将它们符号化。例如：“若2是偶数，则2是偶数或3是奇数”。令p:2是偶数，q:3是奇数，则该附加律符号为p?p?q。
解：（1）“若3是素数，则3是素数或5是奇数”。令p：3是素数，q：5是奇数，则该附加律符号化为p?p?q
（2）“若明天不下雨，则明天不下雨或明天下雪”。令p：明天下雨，q：明天下雪，则该附加律符号化为?p??p?q。
2.从日常生活或数学的各种推理中，构造两个满足化简律的推理定律，并将它们符号化。例如：“我去过海南岛和新疆，所以我去过海南岛”。令p：我去过海南岛，q:我去过新疆，则该化简律符号化为p?q?p。
解：（1）“6能被2和3整除，所以6能被2整除”。令p：6能被2整除，p：6能被2整除，q：6能被3整除，则该化简律符号化为p?q?p。
（2）“小明会弹琴和跳舞，所以小明会弹琴”。令p：小明会弹琴，q：小明会跳舞，则该化简律符号化为p?q?p。
3.随意构造三个满足假言推理定律的推理，并将它们符号化。例如：“如果2是素数，则雪是黑色的，2是素数，所以雪是黑色的”。令p:2是素数，q：雪是黑色的，该假言推理定律符号化为(p?q)?p?q。
解：（1）“如果小明会跳舞，则他会弹琴，小明会跳舞，所以他会弹琴”。 令p：小明会弹琴，q：小明会跳舞，该假言推理定律符号化为(p?q)?p?q。
（2）“如果3是奇数，则明天下雨，3是奇数，所以明天下雨”。令p：3是奇数，q：
明天下雨，该假言推理定律符号化为(p?q)?p?q。
（3）“如果明天晴天，则小明去游泳，明天晴天，所以小明去游泳”。令p：明天晴天，
q：小明去游泳，该假言推理定律符号化为(p?q)?p?q。
4.参照1,2,3题，请构造满足拒取式、析取三段论、假言三段论、等价三段论、构造性二难等推理定律的实例各一个，并将它们符号化。 解：（1）拒取式：“明天是周末，小明就休息，小明没有休息，所以明天不是周末”。令p：明天周末，q：小明休息。该拒取式定律符号化为?p?q???q??p。
文章来源：http://www.7zhao.net
去找 QQ头像 http://www.7zhao.net
（2）析取三段论：“小明会弹琴或跳舞，小明不会跳舞，所以小明会弹琴”。令p：小
明会弹琴，q：小明会跳舞，该析取三段式定律符号化为?p?q???q?p。
（3）假言三段论：“明天要是周末，小明明天休息，小明要是明天休息，他就会去游泳，所以，明天要是周末，小明就去游泳”。令p：明天是周末，q：小明明天休息，t：小明去游泳，该假言三段论定律符号化为?p?q???q?t??p?t。
（4）等价三段论：“2是素数当且仅当3是奇数，3是奇数当且仅当4是偶数，所以2是素数当且仅当4是偶数”。令p：2是素数，q：3是奇数，t：4是偶数，该等价三段论定律符号化为?p?q???q?t??p?t。
（5）构造性二难：“明天是周一，小明就要上学，明天是周末，小明就要去游泳，明天是周末或者周一，所以小明去上学或者去游泳”。令p：明天是周一，q小明要上学，s：明天是周末，t：小明要去游泳，该构造性二难定律符号化为
?p?q???s?t???p?s???q?t?。
（6）破坏性二难：“明天是周一，小明就要上学，明天是周末，小明就要去游泳，小明没有去上学或者小明没有去游泳，所以明天不是周一或者明天不是周末”。令p：明天是周一，q小明要上学，s：明天是周末，t：小明要去游泳，该构造性二难定律符号化为
?p?q???s?t????q??t????p??s?。
5.分别写出德摩定律、吸收律所产生的推理定律（每个等值式产生两条推理定律）。 解：的摩定律1：??A?B???A??B
产生的推理定律：（1）??A?B???A??B （2）?A??B???A?B? 的摩定律2：??A?B???A??B
产生的推理定律：（1）??A?B???A??B （2）?A??B???A?B? 吸收律1：A??A?B??A
产生的推理定律：（1）A??A?B??A （2）A?A??A?B? 吸收律2：A??A?B??A
产生的推理定律：（1）A??A?B??A （2）A?A??A?B?
6.判断下列推理是否正确。先将简单命题符号化，再写出前提、结论、推理的形式结构（以蕴涵式的形式给出）和判断过程（至少给出两种判断方法）：
（1）若今天是星期一，则明天是星期三。今天是星期一，所以明天是星期三。 （2）若今天是星期一，则明天是星期二。明天是星期二，所以今天是星期一。
文章来源：http://www.7zhao.net
去找 QQ头像 http://www.7zhao.net
（3）若今天是星期一，则明天是星期三。明天不是星期三，所以今天不是星期一。 （4）若今天是星期一，则明天是星期二。今天不是星期一，所以明天不是星期二。 （5）若今天是星期一，则明天是星期二或星期三。
（6）今天是星期一当且仅当明天是星期三。今天不是星期一，所以明天不是星期三。
解：（1）设p：今天是星期一，q：明天是星期三，推理的形式结构为?p?q??p?q，判断该推理是否正确，即判断?p?q??p?q是否为重言式，不难看出，该式满足假言推理定律，所以推理正确。
（2）设p：今天是星期一，q：明天是星期二，推理的形式结构为?p?q??q?p。
等值演算法：
?p?q??q?p???p?q??q?p?q?p?p??q ，可见该式不是重言式，所以推理不正确。
?p?q??q?p???p?q??q?p主析取范式法：?q?p，从而可知不是重言式，故推理不正确。
?p??q?M1?m0?m2?m3
（3）设p：今天是星期一，q：明天是星期三，推理的形式结构为?p?q???q??p，判断该推理是否正确，即判断?p?q???q??p是否为重言式，不难看出，该式满足拒取式定律，所以推理正确。
（4）设p：今天是星期一，q：明天是星期二，推理的形式结构为?p?q???p??q。
?p?q???p??q???p?q???p??q等值演算法：?(??p??p???q??p?)??q ，可见该式不是重言式，所以推理不
??p??q?p??q正确。
文章来源：http://www.7zhao.net