洪帆《离散数学基础》(第三版)课后习题答案

1第1章集合1、列举下列集合的元素(1)小于20的素数的集合(2)小于5的非负整数的集合(3)2{|,10240515}iiIiii∈−−≤≤且答：(1){1,3,5,7,11,13,17,19}(2){0,1,2,3,4}(3){5,6,7,8,9,10,11}2、用描述法表示下列集合(1)12345{,,,,}aaaaa答：{|,15}iaiIi∈≤≤(2){2,4,8,}答：{2|}iiN∈(3){0,2,4,100}答：{2|,050}iiZi∈≤≤3、下面哪些式子是错误的？(1){}{{}}aa∈答：正确(2){}{{}}aa⊆答：错误(3){}{{},}aaa∈答：正确(4){}{{},}aaa⊆答：正确4、已给{2,,{3},4}Sa=和{{},3,4,1}Ra=，指出下面哪些论断是正确的？哪些是错误的？(1){}aS∈错误2(2){}aR∈正确(3){,4,{3}}aS⊆正确(4){{},1,3,4}aR⊆正确(5)RS=错误(6){}aS⊆正确(7){}aR⊆错误(8)Rφ⊆正确(9){{}}aRφ⊆⊆正确(10){}Sφ⊆错误(11)Rφ∈错误(12){{3},4}φ⊆正确5、列举出集合,,ABC的例子，使其满足AB∈，BC∈且AC∉答：{}Aa=，{{}}Ba=，显然AB∈，{{{}}}Ca=，显然BC∈，但是AC∉。6、给出下列集合的幂集(1){,{}}ab答：幂集{,{},{{}},{,{}}ababφ(2){,,{}}aaφ答：幂集{,{},{},{{}},{,},{,{}},{,{}},{,,{}}}aaaaaaaaφφφφφ7、设{}Aa=，给出A和2A的幂集答：2{,{}}Aaφ=22{,{{}},{{}},{,{}}}Aaaφφφ=8、设128{,,,}Aaaa=由17B和31B所表示的A的子集各是什么？应如何表示子集2,67{,}aaa和13{,}aa答：170001000148{,}BBaa==3310001111145678{,,,,}BBaaaaa==2,670100011070{,}aaaBB==，1310100000160{,}aaBB==9、设{1,2,3,4,5}U=，{1,4}A=，{1,2,5}B=，{2,4}C=，确定集合：(1)AB′∩(2)()ABC′∩∪(3)()ABC∪∩(4)()()ABAC∪∩∪(5)()AB′∩(6)AB′′∪(7)()BC′∪(8)BC′′∩(9)22AC−(10)22AC∩答：(1){3,4}B′=，{4}AB′∩=(2){1}AB∩=，{1,3,5}C′=，(){1,3,5}ABC′∩∪=(3){2}BC∩=，(){1,2,4}ABC∪∩=(4){1,2,4,5}AB∪=，{1,2,4}AC∪=，()(){1,2,4}ABAC∪∩∪=(5)(){2,3,4,5}AB′∩=(6){2,3,5}A′=，{2,3,4,5}AB′′∪=(7){1,2,4,5}BC∪=，(){3}BC′∪=(8){3,4}B′=，{1,3,5}C′=，{3}BC′′∩=(9)2{,{1},{4},{1,4}}Aφ=，2{,{2},{4}{24}}Cφ=，，，22{{1},{1,4}}AC−=(10)22{,{4}}ACφ∩=10、给定自然数集N的下列子集：{1,2,7,8}A=，2{|50}Bii=，{|330}Ciii=≤≤可被整数，0{|2,,06}kDiikZk==∈≤≤求下列集合：(1)(())ABCD∪∪∪答：{1,2,3,4,5,6,7}B=，{0,3,6,9,12,15,18,21,24,27,30}C=，{1,2,4,8,16,32,64}D=(()){0,1,2,3,4,5,6,7,8,9,12,15,16,18,21,24,27,30,32,64}ABCD∪∪∪=(2)(())ABCDφ∩∩∩=4(3)()BAC−∪解：{0,1,2,3,6,7,8,9,12,15,18,21,24,27,30}AC∪=，(){4,5}BAC−∪=(4)()ABD′∩∪解：{3,4,5,6}ABBA′∩=−=，(){1,2,3,4,5,6,8,16,32,64}ABD′∩∪=11、给定自然数集N的下列子集{|12}Ann=，{|8}Bnn=≤，{|2,}CnnkkN==∈，{|3,}DnnkkN==∈{|21,}EnnkkN==−∈将下列集合表示为由,,,,ABCDE产生的集合：(1){2,4,6,8}(2){3,6,9}(3){10}(4){|369}nnnn==≥或或(5){|109}nnnnn≤是偶数且或是奇数且(6){|6}nn是的倍数答：{1,2,3,4,5,6,7,8,9,10,11}A=，{1,2,3,4,5,6,7,8}B={2,4,6,8,}C=，{3,6,9,12,}D=，{1,3,5,7,}E={2,4,6,8}BC=∩{3,6,9}=AD∩{10}=(())ABDE−−−(4){|369}nnnn==≥=或或{3}{6}{9,10,11,12,}∪∪{3,6,9,10,11,12,}()ADB′==∩∪(5){2,4,6,8,10,11,13,15,}(()())(())AEEBADB=−∪−−∩−(6){|6}{6,12,18,24,30}nn==是的倍数CD∩12、判断以下哪些论断是正确的，哪些论断是错误的，并说明理由。(1)若aA∈，则aAB∈∪5答：正确，根据集合并的定义(2)若aA∈，则aAB∈∩答：显然不正确，因为根据集合交运算的定义，必须a同时属于A和B(3)若aAB∈∩，则aB∈答：正确(4)若AB⊆，则ABB∩=答：错误(5)若AB⊆，则ABA∩=答：正确(6)若aA∉，则aAB∉∪答：错误(7)若aA∉，则aAB∉∩答：正确13、设,,ABC是任意的集合，下述论断哪些是正确的？哪些是错误的？说明理由(1)若ABAC∩=∩，则BC=答：不正确，反例，设Aφ=，则不论,BC是什么集合，都有ABACφ∩=∩=，但显然,BC不一定相等。(2)当且仅当ABB∪=，有AB⊆；答：正确，证明如下：若ABB∪=，则对aA∀∈，有aABB∈∪=，则有aB∈，因此有AB⊆。反之，若AB⊆，则ABB∪=显然成立。(3)当且仅当ABA∩=，有AB⊆答：正确，证明如下：若ABA∩=，则对aA∀∈，因此aAB∈∩，则aB∈，则有AB⊆。若AB⊆，则aA∀∈，有aB∈，因此由aA∈，可以得出aAB∈∩，因此AAB⊆∩，又ABA∩⊆，有ABA∩=。6(4)当且仅当AC⊆，有()ABCφ∩−=答：不正确，因为()ABCABC′∩−=∩∩，因此不一定需要满足AC⊆，而若ABφ∩=也可以满足。例如：{,,}Aabc=，{,}Bde=，{,}Cab=，()ABCφ∩−=成立，而AC⊆不成立。(5)当且仅当BC⊆，有()ABCA−∪=答：不正确，因为若BC⊆，有()ABCA−∪=成立，但是反之不成立，反例如下:{1,2,3,4,5}A=，{1,6}B=，{1,2}C=，而{2,3,4,5}AB−=，(){1,2,3,4,5}ABC−∪=，但是BC⊆不成立。14、设,,,ABCD是集合，下述哪些论断是正确的？哪些是错误的？说明理由。(1)若,ABCD⊆⊆，则()ACBD∪⊆∪答：正确，证明：对aAC∀∈∪，则aA∈或aC∈，因为,ABCD⊆⊆，因此aB∈或aD∈，因此aBD∈∪，即()ACBD∪⊆∪成立。(2)若,ABCD⊆⊆，则()ACBD∩⊆∩答：正确(3)若AB⊂，CD⊂，则()ACBD∪⊂∪答：正确(4)若,ABCD⊂⊂，则()ACBD∩⊂∩答：不正确。例如若,ABCD⊂⊂，但是ACφ∩=，BDφ∩=，则()ACBDφφ=∩⊆∩=。15、设,AB是两个集合，问：(1)如果ABB−=，那么A和B有什么关系？答：因为ABB−=，而ABABB′−=∩=，即对aB∀∈有,aAaB′∈∈，因此7ABφ==。(2)如果ABBA−=−，那么A和B有什么关系？答：充要条件是AB=。证明：因为ABBA−=−的()()ABABAA−∪=−∪，从而有AAB=∪，即AB⊆，同理可证明BA⊆，因此AB=。16、设,AB是任意集合，下述论断哪些是正确的？哪些是错误的？说明理由。(1)222ABAB∪=∪答：不正确。例如{,}Aab=，{,}Bbc=，则{,,}ABabc∪=2{,{},{},{},{,},{,},{,},{,,}}ABabcabacbcabcφ∪=2{,{},{},{,}}Aababφ=，2{,{},{},{,}}Bbcbcφ=显然222ABAB∪=∪不成立。(2)222ABAB∩=∩答：成立。证明：对22ABC∀∈∩，则2AC∈且2BC∈，则,CACB⊆⊆，则CAB⊆∩，因此2ABC∩∈。反之，若2ABC∩∀∈，则CAB⊆∩，则CA⊆且CB⊆，因此2AC∈，且2BC∈，因此22ABC∈∩，即222ABAB∩=∩。(3)2(2)AA′′=答：显然不成立，因为左边集合肯定含有φ，而右边不含有。17、在一个班级的50个学生中，有26人在离散数学的考试中取得了优秀的成绩；21人在程序设计的考试中取得了优秀的成绩。假如有17人在两次考试中都没有取得优秀成绩，问有多少人在两次考试中都取得了优秀成绩?答：分别用,AB表示在离散和程序设计的考试中取得优秀成绩的学生集合，U表示全体学生集合：则#()26A=，#()21B=，#()501733AB∪=−=，则两次考试中都取得了优秀成绩的学生人数为26+21-33=14人。18、设,,ABC是任意集合，运用成员表证明：(1)()()()()ABACACAB′′∪∩∪=∩∪∩证明：8ABCA′AC′∪AB∪AC∩AB′∩左边右边00011000000011100000010111011101111101111000010000101011101111000100001110111011(3)()()()ABCABAC−∪=−∩−证明：ABCAB−AC−()()ABAC−∩−BC∪()ABC−∪0000000000100010010000100110001010011101101100101100101011100010由上得证左右两边相等。19、由S和T的成员表如何判断ST⊆？应用成员表证明或否定()()ABBCAB′′∪∩∪⊆∩答：先分别给出集合()()ABBC′∪∩∪和AB′∩的成员表如下：ABCAB∪BC∪()BC′∪()()ABBC′∪∩∪B′AB′∩000001010001010010010110000011110000100101111101110011110110000111110000观察上述表格，我们发现()()ABBC′∪∩∪所标记的列中，仅在第五列为1，这9意味着当元素,uAuB∈∉且uC∉时，()()uABBC′∈∪∩∪，而在其他情形下，元素()()uABBC′∉∪∩∪。而集合AB′∩所标记的列中，第五和第六行均为1，这意味着,uAuB∈∉且uC∉时，uAB′∈∩，当,uAuB∈∉，且uC∈时，也有uAB′∈∩。所以当元素()()uABBC′∈∪∩∪时也有uAB′∈∩，反之不然，因此()()ABBCAB′′∪∩∪⊆∩成立。20、12,,,rAAA为U的子集，12,,,rAAA至多能产生多少不同的子集？答：构造由12,,,rAAA所产生的集合的成员表，显然该成员表由2r个行所组成。在该成员表中不同的列可由2r为的二进制数0000~11111分别表示，而不同的列所标记的集合不相同的，因此由12,,,rAAA至多可以产生22r个不同的集合。21、证明分配律、等幂律和吸收律9′1分配律()()()ABCABAC∩∪=∩∪∩证明：对()aABC∀∈∩∪，则有aA∈且aBC∈∪，即有aA∈，且aB∈或aC∈，也即有aAB∈∩或aAC∈∩，即()()aABAC∈∩∪∩，因此左边⊆右边。对()()aABAC∀∈∩∪∩，则aAB∈∩或aAC∈∩，即aA∈且aB∈，或aA