离散数学习题解答耿素云屈婉玲北京大学出版社(供参考)

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

19.将下列公式化成与之等值且仅含??,??中联结词的公式. （1）(?p??q)?r

答：(?p??q)?r??(?(?p??q)??r) （2）(p?(q??p))?q?r

答：(p?(q??p))?q?r??(?(?p??(?q?p))??q??r)

（3）p?q??r

答：p?q??r??(?p??q?r)

?}中联结词的公式： 20．将下列公式化成与之等值且仅含{?，（1）(p?q)?r（2）(p??q)?r（3）(p?q)?r

答：(p?q)?r??(?p??q)?r??(p??q)?r?(p??q)?r (2)(p??q)?r

答：(p??q)?r??(?(p??q)??r)??((p??q)??r) (3)(p?q)?r

答：(p?q)?r?(?(?p??q)?r)?(r??(?p??q)) 21．证明：

(p?q)?(q?p). （1）(p?q)?(q?p)，(p?(q?r))?((p?q)?r). （2）(p?(q?r))?((p?q)?r)，证明：(1)p?q??(p?q)??(q?p)?q?p；

(2)令p?0,q?0,r?1则

p?(q?r)?1,(p?q)?r?0，p?(q?r)?1,(p?q)?r?0.，可知(p?(q?r))?((p?q)?r)，(p?(q?r))?((p?q)?r).

22.从表2.6中，找出与下列公式等值的真值函数： （1）p?q

（2）p?q

（3）(p??q)?(?p?q) （4）?(p?q)

(2)(2)(2)(2)答：(1)F14;(2)F8;(3)F6;(4)F2

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

23．设A、B、C为任意的命题公式，证明： （1）等值关系有自反性：A?A

（2）等值关系有对称性：若A?B,则B?A

（3）等值关系有传递性：若A?B且B?C，则A?C

答：(1)A?A?(A?A)?(A?A)?A?A??A?A?1

(2)B?A?(?B?A)?(?A?B)?(?A?B)?(?B?A)?A?B (3)

24．设A、B为任意的命题公式，证明：?A??B当且仅当A?B 答：?A??B?(A??B)?(B??A)?(A?B)?(B?A)?A?B. 因此?A??B当且仅当A?B。

25．设A、B、C为任意的命题公式，（1）若A?C?B?C，举例说明A?B不一定成立。（2）若A?C?B?C，举例说明A?B不一定成立。由（1）、（2）可知，联结词

?与?不满足消去率。

答：(1)设A?p?1,B?q?0,C?r?1，则A?C?1?B?C?1

，但

A?1,B?0，二者不等价。

（2）设A?p?1,B?q?0,C?r?0，则A?C?0?B?C?0，但

A?1,B?0，二者不等价。

26．在上题（25）中，若已知A?C?B?C，在什么条件下，A?B一定成立？又若已知A?C?B?C，在什么条件下，A?B一定成立？ 解：若C?0;则A?C?B?C，A?B一定成立。 若C?1；则A?C?B?C，A?B一定成立。

27．某电路中有一个灯泡和三个开关A、B、C。已知在且仅在下述四种情况下灯亮： （1）C的扳键向上，A、B的扳键向下。（2）A的扳键向上，B、C的扳键向下。（3）B、C的扳键向上，A的扳键向下。（4）A、B的扳键向上，C的扳键向下。 设F为1表示灯亮，p、q、r分别表示A、B、C的扳键向上。 （a）求F的主析取范式。

（b）在联结词完备集{?，?}上构造F。

?，?}上构造F。 （c）在联结词完备集{?，文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

答：（a）由题意知，灯亮的情况如下：

（b）F?(p??q??r)?(?p??q?r)?(?p?q?r)?(p?q??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输入.有题意可得：

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）得那么孙不去，符合

5个条件，即p?q??r??s?t. ② 若李去，周不去，由条件（4）得则孙去，从而由条件（3）得钱不去，而由条件（1）

得赵也不去，即?p??q?r?s??t. ③ 若周、李都去，那么由条件（4）得则孙去，由条件（5）得赵、钱都去，这样孙和

钱都去，与条件（3）矛盾，因此这种情况不存在.

习题三

1.从日常生活或数学中的各种推理中，构造两个满足附加律的推理定律，并将它们符号化。

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.

例如：“若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。

（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：明