离散数学习题解答(耿素云屈婉玲)北京大学出版社 下载本文

去找 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