离散数学第二版邓辉文编著第一章第六节习题答案 VIP免费

离散数学第二版邓辉文编著第一章第六节习题答案第一篇：离散数学第二版邓辉文编著第一章第六节习题答案1.6集合对等习题1.61.证明:任意无限集合均存在可数子集.证设A是无限集合，取a0A，则A{a0}是无限集合.取a1A，则A{a0,a1}是无限集合.一直下去，即可得到无限集合A的可数子集{a0,a1,...an,...}.2.证明:(0,1)~[0,1].证由于(0,1)是无限集合，而任意无限集合均存在可数子集，设{a0,a1,...an,...}是(0,1)开区间的一个可数子集合，令f:(0,1)[0,1]，满足下面的条件f(a0)0,f(a1)1,f(ai)ai2,i2;f(x)x,x{a0,a1,...,an,...}.显然，f是(0,1)到[0,1]的一个双射.故(0,1)~[0,1].3.证明:[0,1]~[a,b],ab.证令f:[0,1][a,b]，f(x)a(ba)x，容易证明f是一个双射，进而[0,1]~[a,b].4.有理数集合Q是可数集合.证由于正有理数集合Q+=nm,nN,m0,m与n互素，令mf:QNN，nf(m,n)，m则f是单射，所以|Q+||NN|.由于N~NN，于是|Q+||N|0.而Q+是无限集合，所以|Q+||N|0.于是|Q+|=0.所以正有理数集合Q+是可数集合.显然Q+与所有负有理数集合Q-对等，而Q=Q+Q-{0}，所有Q是可数集合.5.证明:全体无理数组成的集合R–Q与R有相同的基数.证在全体无理数集合R–Q中选取可数子集{a0,a1,...an,...}，因为Q可数，设Q={b0,b1,...bn,...}.构造映射f:RQR如下f(a2i)ai,f(a2i1)bi,i0,1,2,...；f(x)x,x{a0,a1,...,an,...}.则f:RQR是双射，所以R–Q与R有相同的基数.6.对于任意集合A，P(A)是A的幂集，证明:|A||P(A)|.证令g:AP(A),g(x){x}，则g是A到P(A)的单射，所以|A||P(A)|.假设|A||P(A)|，则存在A到P(A)的双射f.令S{x|xf(x)}，则SA.因为f是A到P(A)的双射，必存在yA是得f(y)S.考虑是否yS.由于ySy{x|xf(x)}yf(y)yS，这是一个矛盾.于是|A||P(A)|不成立，因此有|A||P(A)|.第二篇：离散数学习题及答案离散数学考试试题（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∧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分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。解：论域：所有人的集合。S(x)：x是专家；W(x)：x是工人；Y(x)：x是青年人；则推理化形式为：x(S(x)∧W(x))，xY(x)x(S(x)∧Y(x))下面给出证明：(1)xY(x)P(2)Y(c)T(1)，ES(3)x(S(x)∧W(x))P(4)S(c)∧W(c)T(3)，US(5)S(c)T(4)，I(6)S(c)∧Y(c)T(2)(5)，I(7)x(S(x)∧Y(x))T(6)，EG三、（10分）设A、B和C是三个集合，则AB(BA)。证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA)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...