国防科大版离散数学习题答案

第二章二元关系-1-第一章集合习题1.11.a){0,1,2,3,4}b){11,13,17,19}c){12,24,36,48,64}2.a){x|xN且x100}b)Ev={x|xN且2整除x}Od={x|xN且2不能整除x}c){y|存在xI使得y=10x}或{x|x/10I}3.极小化步骤省略a)①{0,1,2,3,4,5,6,7,8,9}A；②若,A，则A。或①{0,1,2,3,4,5,6,7,8,9}A；②若A且a{0,1,2,3,4,5,6,7,8,9}，则aA。或①{0,1,2,3,4,5,6,7,8,9}A；②若A且a{0,1,2,3,4,5,6,7,8,9}，则aA。b)①{0,1,2,3,4,5,6,7,8,9}A；②若,A且0，则A。c)①若a{0,1,2,3,4,5,6,7,8,9}，则a.A；②若A且a{0,1,2,3,4,5,6,7,8,9}，则aA；若A且a{0,1,2,3,4,5,6,7,8,9}，则aA。或①{0.,1.,2.,3.,4.,5.,6.,7.,8.,9.}A；②若A且a{0,1,2,3,4,5,6,7,8,9}，则aA；若A且a{0,1,2,3,4,5,6,7,8,9}，则aA。d)①{0,10}A；②若A，则1A；若,A且0，则A。e)Ev定义如下：①{0}Ev或0Ev；②若Ev，则+2Ev。第二章二元关系-2-Od定义如下：①{1}Od或1Od；②若Od，则+2Od。f)①{0}A或0A；②若A，则2)1(A。4.A=G；C=F；B=E。5.题号是否正确a)b)（空集不含任何元素）c)d)e)f)g)h)6.题号是否正确a)（反例：A={a}；B=；C={{a}}）b)（反例：A=；B={}；C={}）c)（反例：A=；B={a}；C={}）d)（反例：A=；B={}；C={{}}）7.能。例如：B=A{A}。8.a)；{1}；{2}；{3}；{1,2}；{1,3}；{2,3}；{1,2,3}；b)；{1}；{{2,3}}；{1,{2,3}}；c)；{{1,{2,3}}}；d)；{}；e)；{}；{{}}；{,{}}；f)；{{1,2}}；g)；{{,2}}；{{2}}；{{,2},{2}}；9.a){，{a}，{{b}}，{a,{b}}}；b){，{1}，{}，{1,}}；c){，{x}，{y}，{z}，{x,y}，{x,z}，{y,z}，{x,y,z}}；d){，{}，{a}，{{a}}，{,a}，{,{a}}，{a,{a}}，{,a,{a}}}。习题1.2第二章二元关系-3-1.a)A~B={4}；b)(AB)~C={1,3,5}；c)~(AB)={2,3,4,5}；d)~A~B={2,3,4,5}；e)(A–B)–C=；f)A–(B–C)={4}；g)(AB)C={5}；h)(AB)(BC)={1,2}。2.a)BC或B–E；b)AD；c)(A–B)C；d)C–B或C–A；e)(AC)(E–B)或(A–E)(E–B)；3.a)证明：对于任意xAC，因为xAC，所以xA或xC。若xA，则由于AB，因此xB；若xC，则由于CD，因此xD。所以，xB或xD，即xBD。所以，ACBD。类似可证ACBD。d)A–(BC)=A~(BC)=A(~B~C)=(AA)(~B~C)=(A~B)(A~C)=(A–B)(A–C)f)A–(A–B)=A~(A–B)=A~(A~B)=A(~AB)=(A~A)(AB)=(AB)=AB4.a))若A=B，则AB=A且AB=A。因此，AB=(AB)–(AB)=A–A=。)若AB=，则AB=AB。又因为ABAAB且ABBAB，所以AB=A=B=AB。所以A=B。5.证明略。a)b)c)（反例：A={a,b}，B={a}，C={b}）d)（反例：A={a}，B={a,b}，C={a,c}）e)第二章二元关系-4-f)（反例：A={a,b}，B={a}，C={b}）g)（反例：A={a}，B={a,b}，C={a,c}）6.a)BC~A；b)ABC；c)A~(BC)，即BC~A；d)ABC；e)(A–B)(A–C)=(A~B)(A~C)=((A~B)(A~C))–((A~B)(A~C))=((A~B)(A~C))~((A~B)(A~C))=((A~B)(A~C))(~(A~B)~(A~C))=((A~B)(A~C))((~AB)(~AC))=(A(~B~C))(~A(BC))=(A(~B~C))(BC)=A((BC)~(BC))=A(BC)因此，若(A–B)(A–C)=A，则A(BC)=A。所以，A(BC)。f)由上题，(A–B)(A–C)=A(BC)因此，若(A–B)(A–C)=，则A(BC)=。g)A=B；h)A=B=；i)A=B；j)B=；k)BA或AB。7.a)对于任意x(A)(B)，则x(A)或x(B)。若x(A)，则xA。因为AAB，所以，xAB。因此，x(AB)。若x(B)，则xB。因为BAB，所以，xAB。因此，x(AB)。所以，总有x(AB)。因此，(A)(B)(AB)。b)对于任意x(A)(B)，则x(A)且x(B)。x(A)，因此xA。x(B)，因此xB。所以，xAB。因此，x(AB)。所以，(A)(B)(AB)。8.a){{}}={}，{{}}={}；b){,{}}={}，{,{}}=；第二章二元关系-5-c){{a},{b},{a,b}}={a,b}，{{a},{b},{a,b}}=。9.证明：i)若xR0，则xR且x1。所以对于任意iI+均有x1+1/i。即对于任意iI+均有xRi。所以，x1iiR。ii)若x1iiR，则对于任意iI+均有xRi。所以对于任意iI+均有x1+1/i。所以，x1，故x1iiR。10.因为An+1An，所以00AAnn，0nnA。11.}0|{1yRyyAxRxx且，}10|{1yRyyAxRxx且。12.a)nmiiAxmn0mAx0m使得总有iffiffAx；b)nAxmn0mx0m有使得有iffAiffAxmii。第二章二元关系-6-习题1.31.a)证明：用第一归纳法i)当n=1时，左边=1/2=右边；ii)对任意的k1，假设当n=k时命题为真，即1)1(1321211kkkk因为)2()1(1)1(1321211kkkk)2()1(1)1(kkkk)2()1()2()1()1()2()1(1)2(2kkkkkkkkk即当n=k+1时命题也为真。由i)ii)可知，对于任意n1均有1)1(1321211nnnn。b)证明：用第一归纳法i)当n=1时，左边=2=右边；ii)对任意的k1，假设当n=k时命题为真，即2+22+23++2k=2k+1-2因为2+22+23++2k+2k+1=2k+1-2+2k+1=2k+2-2即当n=k+1时命题也为真。由i)ii)可知，对于任意n1均有2+22+23++2n=2n+1-2。c)证明：用第一归纳法i)当n=0时，左边=10=右边；当n=1时，左边=22=右边；ii)对任意的k1，假设当n=k时命题为真，即2k2k因为2k+1=22k22k2k+2=2(k+1)（因为k1）即当n=k+1时命题也为真。由i)ii)可知，对于任意n1均有2n=2n。第二章二元关系-7-d)证明：用第一归纳法i)当n=1时，左边=3，右边=3，3|3，所以n=1时命题为真；ii)对任意的k1，假设当n=k时命题为真，即3|k3+2k因为(k+1)3+2(k+1)=k3+3k2+3k+1+2k+2=(k3+2k)+3(k2+k+1)由于3|k3+2k且3|3(k2+k+1)，因此，3|(k+1)3+2(k+1)即当n=k+1时命题也为真。由i)ii)可知，对于任意n1均有3|n3+2n。e)证明：用第一归纳法i)当n=1时，左边=6=右边=3，所以n=1时命题为真；ii)对任意的k1，假设当n=k时命题为真，即123+234++k(k+1)(k+2)=k(k+1)(k+2)(k+3)/4因为123+234++k(k+1)(k+2)+(k+1)(k+2)(k+3)=k(k+1)(k+2)(k+3)/4+(k+1)(k+2)(k+3)=(k+1)(k+2)(k+3)(k+4)/4即当n=k+1时命题也为真。由i)ii)可知，对于任意n1均有123+234++n(n+1)(n+2)=n(n+1)(n+2)(n+3)/4。f)证明：证明分三部分①三个相邻整数中最小者0；②三个相邻整数中最小者=-1；③三个相邻整数中最小者-2。对①用第一归纳法，即证9|n3+(n+1)3+(n+2)3i)当n=0时，9|9，所以n=0时命题为真；ii)对任意的k0，假设当n=k时命题为真，即9|k3+(k+1)3+(k+2)3因为(k+1)3+(k+2)3+(k+3)3=k3+3k2+3k+1+(k+1)3+3(k+1)2+3(k+1)+1+(k+2)3+3(k+2)2+3(k+2)+1=k3+(k+1)3+(k+2)3+3k2+3k+1+3(k+1)2+3(k+1)+1+3(k+2)2+3(k+2)+1=k3+(k+1)3+(k+2)3+9k2+27k+27=k3+(k+1)3+(k+2)3+9(k2+3k+3)由于9|k3+(k+1)3+(k+2)3且9|9(k2+3k+3)所以，9|(k+1)3+(k+2)3+(k+3)3，即当n=k+1时命题也为真。由i)ii)可知，对于任意n0均有9|n3+(n+1)3+(n+2)3对③由于9|n3+(n+1)3+(n+2)3，所以，9|(-n)3+(-(n+1))3+(-(n+2))3。对②因为9|0，所以此时命题也为真。根据以上证明可知，任意三个相邻整数的立方和能被9整除。第二章二元关系-8-g)证明：用第一归纳法i)当n=0时，112+121=133，133|133，所以n=0时命题为真；ii)对任意的k0，假设当n=k时命题为真，即133|11k+2+122k+1因为11k+3+122(k+1)+1=1111k+2+122122k+1=11(11k+2+122k+1)+133122k+1由于133|11k+2+122k+1且133|133122k+1因此，133|11(11k+2+122k+1)+133122k+1。即当n=k+1时命题也为真。由i)ii)可知，对于任意n1均有133|11n+2+122n+13.证明：用第二归纳法i)当n=1时，011)251()251(F，所以n=1时命题为真；当n=2时，1012)251(11FFF，所以n=2时命题为真；ii)对任意的k2，假设当2nk时命题均为真