离散数学试题(a卷答案)

《离散数学试题(a卷答案)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学试题（A卷答案）一、（10分）某项工作需要派A、B、C和D4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？(1)若A去，则C和D中要去1个人；(2)B和C不能都去；(3)若C去，则D留下。解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：A®CÅD，Ø(B∧C)，C®ØD必须同时成立。因此(A®CÅD)∧Ø(B∧C)∧(C®ØD)Û(ØA∨(C∧ØD)∨(ØC∧D))∧(ØB∨ØC)∧(ØC∨ØD)Û(ØA∨(C∧ØD)∨(ØC∧D))∧((ØB∧ØC)∨(ØB∧ØD)∨ØC∨(ØC∧ØD))Û(ØA∧

2、ØB∧ØC)∨(ØA∧ØB∧ØD)∨(ØA∧ØC)∨(ØA∧ØC∧ØD)∨(C∧ØD∧ØB∧ØC)∨(C∧ØD∧ØB∧ØD)∨(C∧ØD∧ØC)∨(C∧ØD∧ØC∧ØD)∨(ØC∧D∧ØB∧ØC)∨(ØC∧D∧ØB∧ØD)∨(ØC∧D∧ØC)∨(ØC∧D∧ØC∧ØD)ÛF∨F∨(ØA∧ØC)∨F∨F∨(C∧ØD∧ØB)∨F∨F∨(ØC∧D∧ØB)∨F∨(ØC∧D)∨FÛ(ØA∧ØC)∨(ØB∧C∧ØD)∨(ØC∧D∧ØB)∨(ØC∧D)Û(ØA∧ØC)∨(ØB∧C∧ØD)∨(ØC∧D)ÛT故有三种派法：B∧D，A∧C，A∧D。二、（15分）在谓词逻

3、辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。解：论域：所有人的集合。()：是专家；()：是工人；()：是青年人；则推理化形式为：(()∧())，()(()∧())下面给出证明：(1)()P(2)(c)T(1)，ES(3)(()∧())P(4)(c)∧(c)T(3)，US(5)(c)T(4)，I(6)(c)∧(c)T(2)(5)，I(7)(()∧())T(6)，EG三、（10分）设A、B和C是三个集合，则AÌBÞØ(BÌA)。证明：AÌBÛ"x(x∈A→x∈B)∧$x(x∈B∧xÏA)Û

4、"x(xÏA∨x∈B)∧$x(x∈B∧xÏA)6ÛØ$x(x∈A∧xÏB)∧Ø"x(xÏB∨x∈A)ÞØ$x(x∈A∧xÏB)∨Ø"x(x∈A∨xÏB)ÛØ($x(x∈A∧xÏB)∧"x(x∈A∨xÏB))ÛØ($x(x∈A∧xÏB)∧"x(x∈B→x∈A))ÛØ(BÌA)。四、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。解r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1

5、，1>，<2，2>，<3，3>，<4，4>，<5，5>}s(R)＝R∪R－1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>}R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>}R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2t(R)＝Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，

6、2>，<2，2>，<5，1>，<5，4>，<5，5>}。五、（10分）R是非空集合A上的二元关系，若R是对称的，则r(R)和t(R)是对称的。证明对任意的x、y∈A，若xr(R)y，则由r(R)＝R∪IA得，xRy或xIAy。因R与IA对称，所以有yRx或yIAx，于是yr(R)x。所以r(R)是对称的。下证对任意正整数n，Rn对称。因R对称，则有xR2yÛ$z(xRz∧zRy)Û$z(zRx∧yRz)ÛyR2x，所以R2对称。若对称，则xyÛ$z(xz∧zRy)Û$z(zx∧yRz)Ûyx，所以对称。因此，对任意正整数n，对称。对任意的x、y∈A

7、，若xt(R)y，则存在m使得xRmy，于是有yRmx，即有yt(R)x。因此，t(R)是对称的。六、（10分）若f：A→B是双射，则f－1：B→A是双射。证明因为f：A→B是双射，则f－1是B到A的函数。下证f－1是双射。对任意x∈A，必存在y∈B使f(x)＝y，从而f－1(y)＝x，所以f－1是满射。对任意的y1、y2∈B，若f－1(y1)＝f－1(y2)＝x，则f(x)＝y1，f(x)＝y2。因为f：A→B是函数，则y1＝y2。所以f－1是单射。综上可得，f－1：B→A是双射。七、（10分）设是一个半群，如果S是有限集，则必存在a∈

8、S，使得a*a＝a。证明因为是一个半群，对任意的b∈S，由*的封闭性可知，b2＝b*b∈S，b3＝b2*b∈S，