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

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、用描述法 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示下列集合(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∈且aC∈，即有aA∈或aBC∈∪，因此()aABC∈∩∪，因此右边⊆左边。2吸收律()AABA∩∪=证明：()AABA∩∪⊆显然成立，对aA∀∈，则显然有aAB∈∪，因此有()aAAB∈∩∪，因此有()AAAB⊆∩∪成立。22、设,,ABC是任意集合，运用集合运算定律证明：(1)(())BABAU′′∪∪∩=10证明：()()(()())(())()BABABABABAAABBUABBABU′′′=∪∪∪′′′′=∪∩∪=∪∪∩∪′′=∪∩∪=∪∪==左边右边(2)()()()()()()ABBCCAABBCCA∪∩∪∩∪=∩∪∩∪∩证明：(())()(())(()())()()(()()()()()()BACCACABCAACCBBAACAACCCBBAACAC=∪∩∩∪=∪∩∪∪∩∩=∩∪∩∪∩∩∪∩∩=∩∪∩∪∩∪∩=左边右边(3)()()()()()()ABBCACABABCABC′′∪∩∪∩∪=∩∪∩∩∪∩∩证明：((()))()(()())()(())()()()()()((()))()(()())()(())()()()BACAABCBAAACABCBACABCBABCABCBCABCBBCABBBCBCABCBCABAC′′=∩∩∪∪∩∩′′=∩∪∩∪∪∩∩′=∩∪∪∩∩′=∩∪∩∪∩∩′=∩∪∩∩∪′=∩∪∩∪∩∪=∩∪∩∪=∩∪∩∪∩右边由上 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的证明可知左边=右边，得证。23、用得摩根定律证明()(())ABABC′′′∩∪∩∪补集是()()()ABABAC′′∪∩∪∩∪。证明：(()(()))(())(())()(())()(())()()()ABABCABABCABABCABABCABABAC′′′′∩∪∩∪′′′′′=∩∩∩∪′′′=∪∩∪∪′′=∪∩∪∩′′=∪∩∪∩∪24、设iA为某些实数的集合，定义为0{|1}1{|1}(1,2,)iAaaAaaii=<=≤−=试证明：01iiAA∞==11证明：设1iiaA∞=∈，则比存在整数k，使得kaA∈，因此有11ak≤−，于是1a<,因此0aA∈。另一方面，设0aA∈，则有1a<，若0a≤，则有1aA∈，因此1iiaA∞=∈。若01a<<，则令1ba=−，1111abb=−=−，令11kb=+，其中表示1b的整数部分，则有111kb>，因此11111akb=−<−，即kaA∈，于是1iiaA∞=∈，因此得证。25、设12{,,,}rAAA是集合A的一个分划，试证明12,,,rABABAB∩∩∩中所有非空集合构成AB∩的一个分划。证明：因为12{,,,}rAAA是集合A的一个分划，因此由分划的定义，可得1riiAA==，且,ijAAijφ∩=≠，而()(),ijABABijφ∩∩∩=≠，且11()()(rriiiiABABAB==∩=∩=∩分配律)，因此12,,,rABABAB∩∩∩中所有非空集合构成AB∩的一个分划。26、n个元素的集合，有多少中不同的方法可以分划成两块？答：当n奇数时有12112nnnnCCC+−+++种不同的方法，当n为偶数时有12/2nnnnCCC+++种不同的方法。12第2章关系1、若{0,1}A=,{1,2}B=，确定集合：(1){1}AB××(2)2AB×(3)2()BA×解：{1}{(0,1,1),(0,1,2),(1,1,1),(1,1,2)}AB××=2{((0,0),1),((0,1),1),((1,0),1),((1,1),1),((0,0),2),((0,1),2),((1,0),2),((1,1),2)}AB×=2、在通常的具有X轴和Y轴的笛卡尔坐标系中，若有试给出笛卡尔积XY×的几何解释解：表示横坐标x的范围在32x−≤≤，纵坐标y的范围在20y−≤≤的二维点集所构成的集合。3、设A，B，C和D是任意的集合，证明(1)()()()ABCABAC×∩=×∩×(2)()()()ABCABAC×−=×−×(3)()()()()ABCDACBD∩×∩=×∩∩证明：(3)首先，因为ABA∩⊆，CDC∩⊆，所以()()ABCDAC∩×∩⊆×类似地，()()ABCDBD∩×∩⊆×，所以有：()()()()ABCDACBD∩×∩⊆×∩×反之，若(,)()()xyACBD∈×∩×，则(,)()xyAC∈×，(,)()xyBD∈×则,xAyC∈∈，且,xByD∈∈，即xAB∈∩，yCD∈∩所以，(,)()()xyABCD∈∩∩×所以()()()()ACBDABCD×∩×⊆∩∩×所以()()()()ABCDACBD∩×∩=×∩∩4、对下列每种情形，列出由A到B的关系ρ的元素，确定ρ的定义域和值域，构造ρ的关系矩阵：(1){0,1,2},{0,2,4},{(,)|}ABababABρ===∈∩解：{0,2}AB∩=，{(0,0),(0,2),(0,4),(1,0),(2,0),(1,2)}ρ=2(){((0,1),(0,1)),((0,1),(0,2),((0,1),(1,1)),((0,1),(1,2))((0,2),(0,1)),((0,2),(0,2),((0,2),(1,1)),((0,2),(1,2))((1,1),(0,1)),((1,1),(0,2),((1,1),(1,1)),((1,1),(1,2))((1,2),(0,1)),((1,2),(0,2),((1BA×=,2),(1,1)),((1,2),(1,2))}{|,32}{|,20}XxxRxYyyRy=∈−≤≤=∈−≤≤13关系矩阵(2)2{1,2,3,4,5},{1,2,3},{(,)|}ABababρ====解：{(1,1),(4,2)}ρ=关系矩阵Mρ=5、设{1,2,3,4,5,6}A=，对下列每一种情形，构造A上的关系图，并确定ρ的定义域和值域(1){(,)|}ijijρ==解：图略{(1,1),(2,2),(3,3),(4,4),(5,5),(6,6)}ρ=定义域DAρ=，RAρ=(2){(,)|}ijijρ=整除解：{(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5),(6,6)}ρ=定义域DAρ=，RAρ=(3){(,)|}ijijρ=是的倍数解：定义域DAρ=，RAρ=(4){(,)|}ijijρ=>解：定义域{6,5,4,3,2}Dρ=，{5,4,3,2,1}Rρ=(5){(,)|}ijijρ=<{(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(2,1),(3,1)(4,1),(5,1),(6,1),(4,2),(6,2),(6,3)}ρ={(6,5),(6,4),(6,3),(6,2),(6,1)(5,4),(5,3),(5,2),(5,1)(4,3),(4,2),(4,1)(3,2),(3,1)(2,1)}ρ=100000000010000111110100Mρ=14解：定义域{5,4,3,2,1}Dρ=，{6,5,4,3,2}Rρ=(6){(,)|,10}ijijijρ=≠<解：定义域{6,5,4,3,2,1}Dρ=，{6,5,4,3,2,1}Rρ=(7)2{(,)|,()}ijijijAρ=≠−∈解：定义域DAρ=，RAρ=(8){(,)|/}ijijρ=是素数解：{(2,1),(3,1),(5,1),(4,2),(6,3),(6,2)}ρ=定义域{2,3,4,5,6}Dρ=，{1,2,3}Rρ=6、设1{(1,2),(2,4),(3,3)}ρ=和2{(1,3),(2,4),(4,2)}ρ=，试求出1212,ρρρρ∪∩，1Dρ，，，和，并证明：12()Dρρ∪=12DDρρ∪1212()RRRρρρρ∩⊆∩解：12{(1,2),(2,4),(3,3),(1,3),(4,2)}ρρ∪=12{(2,4)}ρρ∩=1{1,2,3}Dρ=，2{1,2,4}Dρ=，1{2,4,3}Rρ=，2{3,4,2}Rρ=12(){1,2,3,4}Dρρ∪=12(){4}Rρρ∩=证明：12()Dρρ∪=12DDρρ∪设12()xDρρ∪∈，则必存在y，使得12(,)xyρρ∈∪，所以1(,)xyρ∈或者2(,)xyρ∈，因此，1xDρ∈或者2xDρ∈，即12xDDρρ∈∪，所以12()Dρρ∪⊆12DDρρ∪；反之，设x∈12DDρρ∪，则x1Dρ∈或者2xDρ∈，所以存在1y，使得1(,)xy{(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(2,1),(2,2),(2,3)(2,4),(3,1),(3,2),(3,3),(4,1),(4,2),(5,1),(6,1)}ρ={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(2,4),(3,1)(3,2),(3,3),(3,4),(3,5),(4,2),(4,3),(4,4),(4,5)(4,6)(5,3),(5,4),(5,5),(5,6),(6,4),(6,5),(6,6)}ρ=，{(1,2),(1,3),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6)(3,4),(3,5),(3,6),(4,5),(4,6),(5,6)}ρ=12()Dρρ∪2Dρ1Rρ2Rρ12()Rρρ∩151ρ∈，或者存在2y，使得2(,)xy2ρ∈，由并集的定义知，1(,)xy12ρρ∈∪，或者2(,)xy12ρρ∈∪，总之有12xDρρ∪∈，故12DDρρ∪⊆12()Dρρ∪。证明：1212()RRRρρρρ∩⊆∩设12yRρρ∩∈，则必存在x，使得(,)xy1ρ∈，(,)xy2ρ∈，因此1bRρ∈且2bRρ∈，由交集的定义11bRRρρ∈∩，故1212()RRRρρρρ∩⊆∩。7、1A和2A是分别具有基数1n和2n的有限集，试问有多少个1A到2A的不同关系？答：21AA×的所有子集都是1A到2A的一个关系，所以共有)21(#2AA×个不同的关系。8、找出集合},,,{21naaaA=上普遍关系和恒等关系的关系矩阵和关系图的特征。答：A上的普遍关系2A=ρ的关系矩阵是全1矩阵，而恒等关系的关系矩阵是单位矩阵。9、下列是集合}3,2,1,0{=A上的关系：}2/1|),{(1ijijji=+==或者ρ，}2|),{(2+==jijiρ，试确定如下的复合关系：（1）21ρρ⋅（2）12ρρ⋅（3）121ρρρ⋅⋅（4）31ρ解：（1）)}1,2(),0,0(),3,2(),2,1(),1,0{(1=ρ，)}1,3(),0,2{(2=ρ)}1,2(),0,1{(21=⋅ρρ（2）)}1,3(),0,2(),1,2{(12=⋅ρρ（3）)}2,2(),0,1(),1,1{(121=⋅⋅ρρρ（4）)}2,2(),0,0(),1,0(),1,1(),3,1(),2,0{(21=ρ)}1,2(),3,2(),1,0(),0,0(),2,0(),2,1(),1,0(),3,0{(31=ρ10、设321,,ρρρ是集合A上的关系，试证明：如果21ρρ⊆，则有：（1）3231ρρρρ⋅⊆⋅（2）2313ρρρρ⋅⊆⋅（3）~2~1ρρ⊆证明：（1）对31),(ρρ⋅∈∀yx，由复合关系的定义，∃Az∈，使得，1),(ρ∈zx，3),(ρ∈yz，因为21ρρ⊆，所以2),(ρ∈zx，所以32),(ρρ⋅∈yx，所以3231ρρρρ⋅⊆⋅（2）对13),(ρρ⋅∈∀yx，由复合关系的定义，∃Az∈，使得，3),(ρ∈zx，1),(ρ∈yz，因为21ρρ⊆，所以2),(ρ∈yz，所以23),(ρρ⋅∈yx，所以2313ρρρρ⋅⊆⋅。（3）对~1),(ρ∈∀yx，有1),(ρ∈xy，因为21ρρ⊆，所以2),(ρ∈xy，所以~2),(ρ∈yx，16也即~2~1ρρ⊆。11、给定)}4,3(),2,1(),1,0{(1=ρ，)}3,3(),4,1(),3,1{(21=⋅ρρ求一个基数最小的关系，使满足2ρ的条件。一般地说，若给定1ρ和21ρρ⋅，2ρ能被唯一的确定吗？基数最小的2ρ能被唯一确定吗？答：)}3,4(),4,2(),3,2{(2=ρ。一般地说，若给定1ρ和21ρρ⋅，2ρ不能被唯一的确定。基数最小的2ρ也不能被唯一确定。12、给定集合321,,AAA，设1ρ是由21AA到得关系，2ρ和3ρ是由32AA到得关系，试证明：（1）)(321ρρρ∪⋅=)()(3121ρρρρ⋅∪⋅证明：根据并集和复合关系的定义，)(321ρρρ∪⋅和)()(3121ρρρρ⋅∪⋅都是31AA到上的关系，下只需要证明它们由完全相同的序偶组成。设)(),(321ρρρ∪⋅∈ca，必存在2Ab∈，使得1),(ρ∈ba，32),(ρρ∪∈cb，所以有2),(ρ∈cb或者3),(ρ∈cb，所以有21),(ρρ⋅∈ca或者31),(ρρ⋅∈ca，也即)()(),(3121ρρρρ⋅∪⋅∈ca，也即⊆∪⋅)(321ρρρ)()(3121ρρρρ⋅∪⋅；反之，若∈),(ca)()(3121ρρρρ⋅∪⋅，也即∈),(ca)(21ρρ⋅或者∈),(ca)(31ρρ⋅，若∈),(ca)(21ρρ⋅，则存在2Ab∈，使得1),(ρ∈ba，2),(ρ∈cb，则1),(ρ∈ba，32),(ρρ∪∈cb，则)(),(321ρρρ∪⋅∈ca，若∈),(ca)(31ρρ⋅同理可得，因此有⊆⋅∪⋅)()(3121ρρρρ)(321ρρρ∪⋅。则)(321ρρρ∪⋅=)()(3121ρρρρ⋅∪⋅。（2）)()()(3121321ρρρρρρρ∩∩⋅⊆∩⋅证明：设)(),(321ρρρ∩⋅∈ca，则存在2Ab∈，使得，1),(ρ∈ba，32),(ρρ∩∈cb，则2),(ρ∈cb，且3),(ρ∈cb，所以21),(ρρ⋅∈ca，且31),(ρρ⋅∈ca，即)()(),(3121ρρρρ⋅∩⋅∈ca，所以)()()(3121321ρρρρρρρ∩∩⋅⊆∩⋅。13、给定nijIjijiρρ},1,,|),{(=−∈=是什么？答：},3,2,1,0,1,2,3,{−−−=I，}),4,3(),3,2(),2,1(),1,0(),0,1(),1,2(,{−−−=ρ}),5,3(),4,2(),3,1(),2,0(),0,2(),1,3(,{2−−−=ρ，则},,|),{(nijIjijin=−∈=ρ14、对第9题中的关系，构造关系矩阵（1）1ρM（2）1ρM解：)}1,2(),0,0(),3,2(),2,1(),1,0{(1=ρ)}1,3(),0,2{(2=ρ11100001001010000Mρ=20000000010000100Mρ=17(3)12ρρ⋅M解：)}1,3(),0,2(),1,2{(12=⋅ρρ15、设A是有n个元素的有限集，ρ是A上的关系，试证明必存在两个正整数tk,，使得tkρρ=。证明：因为ρ是A上的关系，所以对于任意正整数r，rρ也是A上的关系，另一方面，因为nA=)(#，所以2)(#nAA=×，222)2(#)(#nAAAA==××，也即A上只有22n个不同的关系，因此在关系1223222,,,,,+nnρρρρρ中必有两个是相同的，也即存在两个正整数tk,，使得tkρρ=，其中1212+≤<≤ntk。16、设1ρ是由A到B的关系，2ρ是由B到C的关系，试证明~1~2~21ρρρρ⋅=⋅。证明：由题设知道~21ρρ⋅和~1~2ρρ⋅都是由C到A的关系，因此只要证明它们由完全相同的序偶组成。设~21),(ρρ⋅∈ac，则21),(ρρ⋅∈ca，因此必存在元素Bb∈，使得1),(ρ∈ba，2),(ρ∈cb，所以~1),(ρ∈ab，~2),(ρ∈bc，所以~1~2),(ρρ⋅∈ac。反之，设~1~2),(ρρ⋅∈ac，则必存在元素Bb∈′，使得~2),(ρ∈′bc，~1),(ρ∈′ab，所以1),(ρ∈′ba，2),(ρ∈′cb，所以21),(ρρ⋅∈ca，所以∈),(ac~21ρρ⋅，所以~1~2~21ρρρρ⋅=⋅。17、（1）设1ρ和2ρ是由A到B的关系，问~2~1~21ρρρρ∪=∪成立吗？答：成立（2）设ρ是集合A上的关系，如果ρ是自反的，则ρ~一定是自反的吗？答：是的。证明：若ρ是自反的，则对所有的Aa∈，有ρ∈),(aa，则一定有ρ~),(∈aa，则ρ~也是自反的。（3）若ρ是对称的，则ρ~也是对称的吗？答：是的。（4）若ρ是可传递的，则ρ~也是可传递的吗？答：是的证明：若ρ是可传递的，由定义可知，若ρ∈),(yx，ρ∈),(zy，则一定有ρ∈),(zx，由逆关系的定义，也即，若ρ~),(∈xy，ρ~),(∈yz，一定有ρ~),(∈xz，，则ρ~也是可传递的。18、图2-9给出了集合}6,5,4,3,2,1{上的关系ρ的关系图，试画出关系5ρ和8ρ的图，并利用关系图求出关系ρ的传递闭包。解：210000000011000100Mρρ⋅=18图2-9关系)}6,6(),3,6(),4,5(),5,4(),5,2(),5,1(),3,1{(=ρ)}6,6(),3,6(),5,5(),4,4(),4,2(),4,1{(2=ρ)}6,6(),3,6(),4,5(),5,4(),5,2(),5,1{(3=ρ)}6,6(),3,6(),5,5(),4,4(),4,2(),4,1{(4=ρ因为24ρρ=，所以35ρρ=，28ρρ=传递闭包。19、试证明：若ρ是基数为n的集合A上的一个关系，则ρ的传递闭包为iniρρ1=+∪=证明：由定义iiρρ∞=+∪=1，要证明iniiiρρ11=∞=∪=∪，因为iniρ1=∪iiρ∞=∪⊆1，所以只要证明⊆∪∞=iiρ1iniρ1=∪即可。设∈),(baiiρ∞=∪1，则必存在正整数k，使得kbaρ∈),(，若nk≤，则∈),(bainiρ1=∪，若nk>，则在A中必存在1−k个元素121,,,−kiiiaaa，使得：baaaaakiiiiρρρ1211,,,−因为nk>，所以在baaaakiii,,,,,121−这1+k个元素中必有两个元素triiaa=（ktr≤<≤0，记a为0ia，记b为kia），因此下述关系baaaaaaaktrrriiiiiiρρρρ1111,,,,,−+−成立，这表明bakρ，kkrtkk<−−=11),(。若nk>1，用类似的方法又可找到12kk<，使,2bakρ，最后必可找到一正整h，使bahρ且nh≤，因此∈),(ba，故。20、下