应用离散数学（第4版）（微课版）习题及答案 周丽 习题3

应用离散数学集合与关系杭电－周丽、方景龙第三章PAGE7PAGE第3章：集合与关系§3.1集合及其运算习题3.11.判断下列命题成真还是成假（这里表示空集） （1） （2） （3） （4） （5） （6） （7） （8） （9） （10） （11） （12）解成真的有：（1）（3）（4）（5）（8）（9）（10）（11）成假的有：（2）（6）（7）（12）2.设，，，全集，求下列集合（1） （2）（3） （4）p(A)（5）p(A)-p(BC)解（1）={4}（2）={1，3，5，6}（3）={2，3，4，5，6}（4）p(A)={，{1}，{4}，{1，4}}（5）p(A)-p(BC)={{1}，{1，4}}3.某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有两人会打这三种球。已知6个会打网球的人中有4人会打排球。求不会打球的人数。解设A表示会打篮球的人的集合，B表示会打排球的人的集合，C表示会打网球的人的集合。据题意有：|A|=14,|B|=12,|AB|=6，|AC|=5，|ABC|=2，|C|=6，|BC|=4，据公式|ABC|=|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|=14+12+6-6-5-4+2=19所以不会打球的人数为25-19=6。所以有6个人不会打球。4.设是全集的任意子集，证明（1）分配律： （2）吸收律： ，（3）德·摩根律： ，（4）德·摩根律： （5）德·摩根律： 解用集合运算的定义方法证明：（1）A∩(B∪C)={x|xAxB∪C}={x|xA(xBxC)}={x|(xAxB)(xAxC)}=(A∩B)∪(A∩C)（2）A(AB)={x|xAxAB}={x|xA（xAxB）}={x|xA}=AA(AB)={x|xAxAB}={x|xA（xAxB）}={x|xA}=A（3）（AB）C={x|xE¬（xAxB）}={x|¬xA¬xB}=A（4）（AB）C={x|xE¬（xAxB）}={x|¬xA¬xB}=A（5）A−(B∩C)=(A−B)∪(A−C)设x∈A−(B∩C)

⇔(x∈A)∧(xB∩C)

⇔(x∈A)∧¬[(x∈B)(x∈C)]

⇔(x∈A)∧(¬(x∈B)¬(x∈C))

⇔((x∈A)∧(xB))((x∈A)∧(xC))

⇔[(x∈A)∧(xB)][(x∈A)∧(xC)]⇔(x∈A−B)(x∈A−C)

⇔x∈(A−B)∪(A−C)5.设是任意集合，证明（1）（2）（3）（4）（5）（6）解（1）左式=(A∩Bc)∪(B∩Ac)

=[(A∩Bc)∪B]∩[(A∩Bc)∪Ac]=(A∪B)∩(Bc∪B)∩(A∪Ac)∩(Bc∪Ac)=(A∪B)∩E∩E∩(Ac∪Bc)

=(A∪B)∩(A∩B)c

=(A∪B)−(A∩B)（2）因为所以。（3）右式=(A−C)−(B−C)=(A∩Cc)∩(B∩Cc)c=(A∩Cc)∩(Bc∪C)=(A∩Cc∩Bc)∪(A∩Cc∩C)=(A∩Cc∩Bc)∪=A∩Cc∩Bc

=(A−B)−C=左式（4）(A−B)−C=(A−B)∩Cc=(A∩Bc)∩Cc=(A∩Cc)∩Bc=(A−C)–B（5）AB=(AB)(AB)=(AB)(ACBC)(AB)C=((AB)C)((AB)CCC)=((AB)(ACBC)))C)(((AB)(ACBC))CCC)=(ABC)(ACBCC)((ACBC)(AB))CC)=(ABC)(ACBCC)(ACBCC)(ABCCC)A(BC)=(BC)A用代替规则得=(BCA)(BCCCA)(BCCAC)(BCCAC)=左边（6）因为所以。6.设是任意集合，证明 （1） （2） （3）针对（2）举一反例，说明对某些集合是不成立的。解（1）设xp(A)∩P(B)⇔xP(A)∧xP(B)⇔xA∧xB⇔x∩A=x∧x∩B=x⇒x∩(A∩B)=x∩x=x⇔xA∩B⇔xp(A∩B)所以P(A)∩P(B)P(A∩B)另一方面，设xp(A∩B)⇔xA∩B⇒xA∧xB⇔xP(A)∧xP(B)⇔xp(A)∩P(B)所以P(A∩B)P(A)∩P(B)因此，结论成立。（2）设xp(A)∪P(B)⇔xP(A)∨xP(B)⇔xA∨xB⇒xA∪B⇔xA∪B⇔xp(A∪B)所以P(A)∪P(B)P(A∪B)因此，结论成立。（3）举例：A={1，2}，B={2，5}p(A)∪P(B)={，{1}，{2}，{5}，{1，2}，{2，5}}但是P(A∪B)={，{1}，{2}，{5}，{1，2}，{2，5}，{1，5}，{1，2，5}}7.设是任意集合，判断下列式子是否正确。如果正确请给出证明，否则请举一个反例。 （1） （2） （3） （4） （5） （6）解（1）错，如果A={1，2}，B={2，3}，C={1，2，3，4}（2）错，如果A={1，2}，B={2，3}，C= （3）正确，用反证法证明，若，可不妨设。（a）若，则根据集合对称差运算的定义，，，与矛盾。（b）若，则根据集合对称差运算的定义，，，也与矛盾。所以。 （4）正确，用反证法证明，若不成立，则存在。（a）若，则，从而，与矛盾。（b）若，则，从而，也与矛盾。所以。（5）正确。ABAB=BCDCD=D(AC)（BD）=（AB）（CD)=BD从而ACBD（6）不正确。举例：A={1，2}，B={1，2，3}，C={1，3}，D={1，2，3}但是AC=BD8.假定全集（1）用位串表示下列集合： （2）写出下列位串各自代表的集合 1111001111 0101111000 1000000001 解（1）=0011100000 =1010010001 =0111001110（2）1111001111={1，2，3，4，7，8，9，10} 0101111000 ={2，4，5，6，7}1000000001={1，10}9.说明怎样用位串的按位运算求下列集合，其中，，，。 （1） （2） （3） （4）解在全集中考虑问题，则集合A的位串是：11111000000000000000000000，集合B的位串是：01110010000000010001010000，集合C的位串是：00101000100000100000100111，集合D的位串是：00011001100001100001100110，集合的位串是11111010000000010001010000，集合的位串是01110000000000000000000000，集合的位串是01111010100000110001110111，集合的位串是01111010000000010001010000，集合的位串是00111001100001100001100111，集合的位串是11111011100001110001110111， 这些位串表示的集合为： §3.2二元关系及其运算习题3.2设，求。解ρ(A)={，{}，{{}}，{，{}}}Aρ(A)={<,>,<,{}>，<,{{}}>，<,{，{}}>，<{},>,<{},{}>，<{},{{}}>，<{},{，{}}>}2.设是任意集合，若，是否一定有成立？为什么？解当时，若，不一定成立；当时，若，则一定成立，反证如下：若不成立，则存在；又因为，所以存在，这样，序偶，与矛盾。3.列出集合上的恒等关系，全域关系，小于或等于关系，整除关系所包含的序偶。解，4.设，求出下列关系（列出其中的序偶）及其定义域和值域。（1）（2）（3）（4）解R1={<1，2>，<1，4>，<1，6>，<2，1>，<2，2>，<2，4>，<2，6>，<4，1>，<4，2>，<4，4>，<4，6>，<6，1>,<6，2>,<6，4>,<6，6>}，定义域和值域都是{1，2，4，6}。（2）R2={<1，2>，<2，1>}，定义域和值域都是{1，2}。（3）R3={<1，1>，<2，1>，<2，2>，<4，1>，<4，2>，<4，4>，<6，1>，<6，6>}，定义域和值域都是{1，2，4，6}。（4）R4={<1，1>，<1，2>，<2，1>，<2，2>，<4，1>，<4，2>，<6，1>，<6，2>}，定义域是{1，2，4，6}，值域是{1，2}。5.设集合A={0，1，2，3}，给出上的二元关系的关系矩阵和关系图。解MR=10..13..26.设，和是上的二元关系： 求下列关系及其关系矩阵和关系图。（1） （2） （3） （4）（5） （6）（7） （8）解（1）（2）={<b，d>}（3）（4）={<a，a>，<a，b>}（5）={<a，d>，<a，c>}（6）（7）={<a，a>，<a，b>，<a，d>}（8）={<a，a>，<b，a>，<d，b>}他们的关系矩阵分别如下：MRS=11000111MRC=00111110MR。S=00001100000MR2=110001000000 他们的关系图分别如下：aaabbabbdccddccdacabdacabdbbcdcdaabcabdbcabddcdcababdcdcaabbcdcd7.设是从集合到集合的关系，是从集合到集合的一个关系，是从集合到集合的一个关系，证明下列等式。（1）（2）（3）（4）解（1）设<x,y>R◦(S1∪S2)t(<x,t>∈R∧<t,y>∈S1∪S2)t(<x,t>∈R∧(<t,y>∈S1∨<t,y>∈S2))t((<x,t>∈R∧<t,y>∈S1)∨(<x,t>∈R∧<t,y>∈S2))t((<x,t>∈R∧<t,y>∈S1)∨t(<x,t>∈R∧<t,y>∈S2))<x,y>R◦S1∨<x,y>R◦S2<x,y>R◦S1∪R◦S2所以，。（2）所以，。（3）设<x,y>(S1∪S2)◦Tt(<x,t>∈S1∪S2∧<t,y>∈T)t((<x,t>∈S1∨<x,t>∈S2)∧<t,y>∈T)t((<x,t>∈S1∧<t,y>∈T)∨(<x,t>∈S2∧<t,y>∈T))t((<x,t>∈S1∧<t,y>∈T)∨t(<x,t>∈S2∧<t,y>∈T))<x,y>S1◦T∨<x,y>S2◦T<x,y>S1◦T∪S2◦T所以，。（4）<x,y>(S1S2)◦Tt(<x,t>∈S1S2∧<t,y>∈T)t((<x,t>∈S1∧<x,t>∈S2)∧<t,y>∈T)t((<x,t>∈S1∧<t,y>∈T)∧(<x,t>∈S2∧<t,y>∈T))⟹t((<x,t>∈S1∧<t,y>∈T)∧t(<x,t>∈S2∧<t,y>∈T))<x,y>S1◦T∧<x,y>S2◦T<x,y>S1◦TS2◦T所以，。8.设和都是从集合到集合的一个关系，证明下列等式。（1） （2）（3） （4）（5）解（1）设<x,y>(R∪S)-1<y,x>∈R∪S<y,x>∈R∨<y,x>∈S<x,y>∈R-1∨<x,y>∈S-1<x,y>∈R-1∪S-1所以，。（2）设<x,y>(R∩S)-1<y,x>∈R∩S<y,x>∈R∧<y,x>∈S<x,y>∈R-1∧<x,y>∈S-1<x,y>∈R-1∩S-1所以，。（3）设<x,y>(RC)-1<y,x>∈RC<y,x>R<x,y>R-1<x,y>∈(R-1)C所以，。（4）设<x,y>(R-S)-1<y,x>∈R-S<y,x>∈R∧<y,x>S<x,y>∈R-1∧<x,y>S-1<x,y>∈R-1-S-1所以，。（5）设<x,y>(R⊕S)-1<y,x>∈R⊕S<y,x>∈R-S∨<y,x>∈S-R（<y,x>∈R∧<y,x>S）∨（<y,x>∈S∧<y,x>R）（<x,y>∈R-1∧<x,y>S-1）∨（<x,y>∈S-1∧<x,y>R-1）<x,y>∈（R-1-S-1）∪（S-1-R-1）<x,y>∈R-1⊕S-1所以，。§3.3二元关系的性质与闭包习题3.3 1.确定下列整数集合上的关系是否是自反的、反自反的、对称的、反对称的和传递的，其中，当且仅当 （1） （2） （3） （4） （5） （6）（7）是的倍数 （8）与都是负的或都是非负的 解不是自反的，是反自反的，是对称的，不是反对称的，不是传递的。不是自反的，也不是反自反的，是对称的，不是反对称的，是传递的。不是自反的，是反自反的，是对称的，不是反对称的，不是传递的。是自反的，不是反自反的，是对称的，不是反对称的，是传递的。不是自反的，不是反自反的，不是对称的，是反对称的，不是传递的。不是自反的，也不是反自反的，不是对称的，是反对称的，不是传递的。是自反的，不是反自反的，不是对称的，是反对称的，是传递的。是自反的，不是反自反的，是对称的，不是反对称的，是传递的。2.设，（1）给出上的一个关系，要求既不是自反的又不是反自反的；（2）给出上的一个关系，要求既是对称的又是反对称的；（3）给出上的一个关系，要求既不是对称的又不是反对称的；（4）给出上的一个关系，要求是传递的但不是传递的。 解（1）R={⟨a,a⟩,⟨b,b⟩,⟨b,c⟩}（2）R={⟨a,a⟩,⟨b,b⟩,⟨c,c⟩}（3）R={⟨a,a⟩,⟨a,b⟩,⟨b,a⟩,⟨b,c⟩}（4）R={⟨a,a⟩,⟨b,c⟩} 3.根据下列关系的关系矩阵判断它们是否是自反的？反自反的？对称的？反对称的？传递的？并求出相应的关系，画出相应的关系图。 解假设A={a，b，c}R1是自反的，不是反自反的，不是对称的，也不是反对称的，不是传递的。R1={⟨a,a⟩,⟨a,b⟩,⟨b,a⟩,⟨b,b⟩,⟨b,c⟩,⟨c,a⟩,⟨c,c⟩}babaccR2不是自反的，不是反自反的，不是对称的，是反对称的，是传递的。R2={⟨a,a⟩,⟨a,b⟩,⟨c,a⟩,⟨c,b⟩}babaccR3是自反的，不是反自反的，是对称的，不是反对称的，是传递的。R3={⟨a,a⟩,⟨a,b⟩,⟨a,c⟩,⟨b,a⟩,⟨b,b⟩,⟨b,c⟩,⟨c,a⟩,⟨c,b⟩,⟨c,c⟩}babaccR4是自反的，不是反自反的，不是对称的，不是反对称的，是传递的。R4={⟨a,a⟩,⟨a,b⟩,⟨a,c⟩,⟨b,b⟩,⟨b,c⟩,⟨c,b⟩,⟨c,c⟩}babaccR5不是自反的，不是反自反的，不是对称的，不是反对称的，不是传递的。R5={⟨a,b⟩,⟨a,c⟩,⟨b,a⟩,⟨b,b⟩,⟨b,c⟩,⟨c,a⟩}ababccR6不是自反的，不是反自反的，是对称的，不是反对称的，不是传递的。R6={⟨a,a⟩,⟨a,b⟩,⟨a,c⟩,⟨b,a⟩,⟨c,a⟩}babaccR7是自反的，不是反自反的，不是对称的，是反对称的，不是传递的。R7={⟨a,a⟩,⟨a,c⟩,⟨b,a⟩,⟨b,b⟩,⟨c,b⟩,⟨c,c⟩}babaccR8是自反的，不是反自反的，是对称的，不是反对称的，不是传递的。R8={⟨a,a⟩,⟨a,b⟩,⟨b,a⟩,⟨b,b⟩,⟨b,c⟩,⟨c,b⟩,⟨c,c⟩}babaccR9不是自反的，不是反自反的，是对称的，不是反对称的，不是传递的。R9={⟨a,b⟩,⟨a,c⟩,⟨b,a⟩,⟨b,c⟩,⟨c,a⟩,⟨c,b⟩,⟨c,c⟩}ababcc4.设和是集合上的二元关系，试证表3.2的有关论断，即：（1）当和是自反的，则、、和也是自反的；而和则不一定。（2）当和是反自反的，则、、和也是反自反的；而和则不一定。（3）当和是对称的，则、、、和也是对称的；而则不一定。（4）当和是反对称的，则、和也是反对称的；而、和则不一定。（5）当和是传递的，则和也是传递的。而、、和则不一定。 解 （1）因为和是自反的，所以，都有，从而，都有、、和，所以他们也是自反的。而和则不一定是自反的，例如：取集合及其上的自反关系和，而和都不是自反的。（2）因为和是反自反的，所以，都有<a,a>R∧<a,a>S，从而，都有<a,a>、<a,a>、<a,a>R-S和<a,a>，所以他们也是反自反的。而和R。S则不一定是反自反的，例如：取集合及其上的反自反关系R={⟨a,b⟩，⟨a,c⟩，⟨b,a⟩}和S={⟨b,c⟩，⟨c,a⟩，⟨c,b⟩}，其RC={⟨a,a⟩，⟨b,b⟩，⟨b,c⟩，⟨c,a⟩，⟨c,b⟩，⟨c,c⟩}却是自反的，不是反自反的。R。S={⟨a,a⟩，⟨a,b⟩，⟨a,c⟩}也不是反自反的。 （3）因为和是对称的，所以，若则，若则，从而，若，则；若，则；若，则；若，则；若，则，所以他们也是对称的。而则不一定是对称的，例如：取集合及其上的对称关系和，而不是对称的。（4））因为和是反对称的，所以当a≠b时，若有<a,b>∈R则<b,a>R，若有<a,b>∈S则<b,a>S，从而当，都有<a,b>∈、<a,b>∈R-S和<a,b>∈，都有<b,a>，<b,a>R-S，<b,a>，所以他们也是反对称的。而、和R。S则不一定是反对称的，例如：取集合及其上的反对称关系R={⟨a,b⟩,⟨a,c⟩,⟨c,c⟩}和S={⟨b,c⟩,⟨c,a⟩,⟨a,b⟩}，其RC={⟨a,a⟩,⟨b,a⟩⟨b,b⟩,⟨b,c⟩,⟨c,a⟩,⟨c,b⟩}却不是反对称的。=R={⟨a,b⟩,⟨a,c⟩,⟨c,c⟩，⟨b,c⟩,⟨c,a⟩}不是反对称的。R。S={⟨a,a⟩，⟨a,c⟩,⟨c,a⟩}也不是反对称的。（5）因为当和是传递的，说明R2R，S2S，则（RS）2R2S2RS，所以RS是传递的。（R-1）2R-1，所以R-1也是传递的。但是、、和则不一定是传递的。例如：取集合及其上的传递关系R={⟨a,b⟩，⟨a,c⟩，⟨c,c⟩}和S={⟨b,c⟩，⟨c,a⟩，⟨b,a⟩}，但是={⟨a,b⟩，⟨a,c⟩，⟨c,c⟩，⟨b,c⟩，⟨c,a⟩，⟨b,a⟩}却不是传递的，同样，={⟨a,a⟩，⟨b,a⟩，⟨b,b⟩，⟨b,c⟩，⟨c,a⟩，⟨c,b⟩}不是传递的。={⟨a,a⟩，⟨a,c⟩，⟨c,a⟩}不是传递的。5.设及其上的关系，求自反闭包、对称闭包和传递闭包。 解自反闭包对称闭包传递闭包6.设关系，求包含的最小关系使得它是（1）自反的和传递的。 （2）对称的和传递的。（3）自反的、对称的和传递的。解（1）用公式rt(R)={⟨1,1⟩,⟨1,2⟩,⟨1,4⟩,⟨2,2⟩,⟨3,3⟩,⟨4,1⟩,⟨4,2⟩,⟨4,4⟩}（2）用公式ts(R)={⟨1,1⟩,⟨1,2⟩,⟨1,4⟩,⟨2,1⟩,⟨2,2⟩,⟨2,4⟩,⟨3,3⟩,⟨4,1⟩,⟨4,2⟩,⟨4,4⟩}（3）用公式rts(R)={⟨1,1⟩,⟨1,2⟩,⟨1,4⟩,⟨2,1⟩,⟨2,2⟩,⟨2,4⟩,⟨3,3⟩,⟨4,1⟩,⟨4,2⟩,⟨4,4⟩}7.根据下列关系的关系矩阵分别求出它们的自反闭包、对称闭包和传递闭包的关系矩阵。 解两个关系的闭包的关系矩阵分别如下：，，，，8.设的关系图如图3.5所示，试给出自反闭包、对称闭包和传递闭包的关系图。aabcde图3.5习题9的图 解：据上面的关系图得R={⟨a,b⟩，⟨b,c⟩，⟨b,e⟩，⟨c,d⟩，⟨d,c⟩，⟨e,e⟩}，从而得r(R)={⟨a,a⟩，⟨a,b⟩，⟨b,b⟩，⟨b,c⟩，⟨b,e⟩，⟨c,c⟩，⟨c,d⟩，⟨d,c⟩，⟨d,d⟩，⟨e,e⟩},其关系图如下abdabdceces(R)={⟨a,b⟩，⟨b,a⟩，⟨b,c⟩，⟨b,e⟩，⟨c,b⟩，⟨c,d⟩，⟨d,c⟩，⟨e,b⟩，⟨e,e⟩}，其关系图如下bacdebacdet(R)={⟨a,c⟩，⟨a,e⟩，⟨b,d⟩，⟨b,e⟩，⟨c,c⟩，⟨d,d⟩，⟨e,e⟩},其关系图如下bacdebacde9.设是集合上的关系， （1）若是自反的，证明和也是自反的。 （2）若是对称的，证明和也是对称的。 （3）若是传递的，证明也是传递的。 解若是自反的，则IA，则IA，IA，从而和也是自反的。若是对称的，则R-1=R，(R2)-1=(R-1)2=R2,…,(Rn)-1=(R-1)n=Rn,则-1=（R∪IA）-1=R-1∪IA-1=R∪IA，所以也是对称的。-1=（R∪R2∪R3∪…）-1=R-1∪(R2)-1∪(R3)-1∪…=，所以也是对称的。（3）若是传递的，则R2，从而2=（R∪IA）2=R2∪R∪IA=R∪IA，所以也是传递的。10.设和是集合上的关系，且，证明，， 解：以证明为例，另二个证明过程非常相似，只需要将其中的传递改为自反或对称即可。因为S，Rt(),得St()，t(R)是传递的，又因为t(S)是包含S的最小传递关系，所以。§3.4等价关系与划分习题3.41.对于给定的集合和其上的二元关系，判断是否为等价关系。 （1）为实数集，，。 （2），，。 （3），即正整数集，，。 （4），集合的基数，，。，集合和满足，，。 解不是等价关系的，因为x-x=0，不满足自反性。不是等价关系，不是传递的，例如<1,3>∈R,<3,2>∈R,但是<1,2>因为1+2=3却不属于R。（3）不是等价关系，不是自反的，如2*2=4是偶数。（4）1）因为x∈A,xxQUOTE⇒得xRx，所以R是自反的。2）对x,y∈A,若xRy得xyyx

⇒yx则yxxy得yR3）但是R不是传递的。举个例子，若xy且zy，虽然满足xRyQUOTE且yRz⇒且yRz，但是不一定满足xz且zx,也就是得不到xRz。因为R是自反的，对称的，不是传递的，所以R不是等价关系。（5）1）因为x∈A,xx=∅CQUOTE⇒得xRx，所以R是自反的。2）对x,y∈A,若xRy得xyC

⇒yx则yx=xyC得yR3）x,y，z∈A,若xRyQUOTE且yRz⇒且yRz则xyC且yzC⇒从而xz=(xz)Ø=(xz)(yy)=(xy)(yz)(xy)(yz)C，得xRz,所以R是传递的。因为R是自反的，对称的，传递的，所以R是等价关系。2.设，对于上的等价关系画出的关系图，并求出中各元素关于的等价类。 解的关系图如下：ccabd中各元素关于的等价类分别为：，3.给出模6同余关系，并求出所有的模6同余类。 解模6同余关系所有的模6同余类为：即4.设，判断下列关系是否等价关系，若是等价关系，试给出它的等价类。（1）（2） 解（1）1）因为<x1，x2>∈A,满足x1+x2=x2+x1得<<x1，x2>，<x1，x2>>R，所以R是自反的。2）对<x1，x2>,<y1，y2>∈A,若<<x1，x2>，<y1，y2>>R，则满足x1+y2=x2+y1,从而得y1+x2=y2+x1,也就是<<y1，y2>，<x1，x2>>R，所以R是对称的。3）对<x1，x2>,<y1，y2>，<z1，z2>∈A,若<<x1，x2>，<y1，y2>>R且<<y1，y2>，<z1，z2>>R，则满足x1+y2=x2+y1,y1+z2=y2+z1,从而得x1+z2=x2+z1,也就是<<x1，x2>，<x1，x2>>R，所以R是传递的。因为R是自反的，对称的，传递的，所以R是等价关系。共有二个等价类。{<0，2>，<2，4>，<4，6>，….}和{<1，2>，<3，4>，<5，6>，….}（2）因为<x1，x2>∈A,满足x1+x1≠x2+x2所以<<x1，x2>，<x1，x2>>R，所以R不是自反的。所以R不是等价关系。5.假如和是集合上的等价关系，问下面的关系是否一定是等价关系，是的给予证明，不是的举出反例。（1） （2） （3） （4） （5） （6） 解（1）依据书中表3.2知，若R和S是等价关系，即R和S是自反的，对称的，传递的。则是自反的，对称的，但不一定是传递的。所以不一定是等价关系。（2）依据书中表3.2知，若R和S是等价关系，即R和S是自反的，对称的，传递的。则是自反的，对称的，传递的。所以是等价关系。（3）依据书中表3.2知，若R和S是等价关系，即R和S是自反的，对称的，传递的。则不是自反的，是对称的，不是传递的。所以不是等价关系。（4）依据书中表3.2知，若R和S是等价关系，即R和S是自反的，对称的，传递的。则不是自反的，对称的，不是传递的。所以不是等价关系。（5）不一定是等价关系，例如：取集合及其上的等价关系有，它不是对称的，从而不是等价关系。 （6）一定是等价关系，证明如下：，因为是自反的，所以，从而，即是自反的；，有，因为是对称的，所以，从而，即是对称的；，有，因为是传递的，所以，从而，即是传递的；综上所述，若是集合上的等价关系，则一定是等价关系。6.当我们构造一个关系的自反闭包的对称闭包的传递闭包时，一定得到一个等价关系吗？是的请证明，不是的请举出反例。 解一定能得到等价关系。对于tsr(R)来说，r(R)是自反的，则sr(R)是对称的，自反的。tsr(R)是传递的，对称的，自反的，所以就是等价关系。7.假如和是集合上的等价关系，和分别是对应于和的划分。证明当且仅当是的加细。（如果在划分中的每个集合都是划分中某个集合的子集，则叫做的加细）证明（1）由推出是的加细，这就是要证明对于中的任何集合，在中都存在集合，使得。 因为中的任何集合是中的某个元素关于等价关系的等价类，即 现构造它是中元素关于等价关系的等价类，从而是中的一个集合。又由于，所以有。（2）由是的加细推出，这就是要证明如果对于中的任何集合，在中都存在集合，使得，那么。 ，有，所以在中存在集合，使得。 根据条件，在中存在集合使得，从而。由于是中某个元素关于等价关系的等价类，根据等价类的定义，有。所以。§3.5偏序关素与拓扑排序习题3.51．确定由下面的关系图3.12表示的3个关系是否为偏序？并列出这些关系中的所有序偶来进行验证。图3.12习题1的图解：（a）是偏序关系。R={<a,a>，<a,b>，<a,c>，<a,d>，<b,b>，<c,c>，<d,b>，<d,d>}是自反的、反对称的，传递的。（b）不是偏序关系。R={<a,a>，<a,b>，<a,c>，<a,d>，<b,b>，<c,c>，<c,d>，<d,b>，<d,d>}是自反的、反对称的，但不是传递的。（c）是偏序关系。R={<a,a>，<a,b>，<b,b>，<c,c>，<c,d>，<d,d>}是自反的、反对称的，传递的。2．确定由下面的关系矩阵表示的关系是否为偏序？并列出这些关系中的所有序偶来进行验证。（1） （2） （3）解：（1）不是偏序。R={<a,a>，<a,c>，<b,a>，<b,b>，<c,c>}是自反的，反对称的，不是传递的。（2）是偏序。R={<a,a>，<c,a>，<b,b>，<c,c>}是自反的，反对称的，传递的。（3）不是偏序。R={<a,a>，<a,c>，<b,c>，<b,b>，<c,c>，<c,d>，<d,a>，<d,b>，<d,d>}是自反的，反对称的，不是传递的。3．画出在下述集合上的整除关系的哈斯图。（1） （2）（3） （4）解哈斯图如下：117117325131548326714．在下面偏序集中找出两个不可比的元素。（1） （2）解：（1）{1，2}和{0，2}不可比。（2）6和8不可比。5．是偏序集。（1）求极大元素和极小元素。（2）存在最大元素吗？存在最小元素吗？如果存在，请求出。（3）找出子集的所有上界。如果它的上确界存在的话，求出上确界。（4）找出子集的所有下界。如果它的下确界存在的话，求出下确界。解：（1）极大元素为24和45，极小元素为3和5。（2）不存在最大元素，也不存在最小元素。（3）子集的上界有15和45，上确界是15。（4）子集的下界有3，5和15，下确界是15。6．是偏序集。（1）求极大元素和极小元素。（2）存在最大元素吗？存在最小元素吗？如果存在，请求出。（3）找出子集的所有上界。如果它的上确界存在的话，求出上确界。（4）找出子集的所有下界。如果它的下确界存在的话，求出下确界。解：极大元素：{1，2}，{1，3，4}，{2，3，4}极小元素：{1}，{2}，{4}不存在最大元素，也不存在最小元素。子集的所有上界为{2，4}，{2，3，4}，上确界是{2，4}。子集的所有下界是{2}，下确界也是{2}。7．求一个与集合上的整除关系相容的全序。解：全序为1R2R3R6R12R8R24R368．如果表示建筑一座房子所需任务的哈斯图如图3.13所示，通过制定这些任务的顺序来安排他们。解：安排的任务如下：打地基，建框架，盖顶，建外墙，装管道，配线，铺地板，建墙板，内部装修，内部设施，铺地毯，外部装修，外部设施，完成。9．对一个软件项目的任务进行排序，关于这个项目任务的哈斯图如图3.14所示。解对一个软件项目的任务排序如下：确定用户需求，编写功能需求，开发系统需求，建立测试点，开发模块A，开发模块B，开发模块C，模块集成，写文档，测试，测试，完成。AA图3.13习题8的图图3.14习题9的图§3.6函数习题3.61.设函数如下：求，，，，，，。 解=0={0}=1={1}={0，1，2，3，….}={1}={2,3,4}2.设函数，，证明（1） （2） 解（1）设y∈f(A∪B)⇔QUOTE∃x∃x(x∈A∪B∧y=f(x))

⇔QUOTE∃x∃x((x∈Ax∈B)∧y=f(x))⇔QUOTE∃x∃x((x∈A∧y=f(x))(x∈B∧y=f(x)))

⇔QUOTE∃x∃x((x∈A∧y=f(x))(x∈B∧y=f(x)))

⇔y∈f(A)y∈f(B)⇔y∈f(A)∪f(B)因此，。（2）设y∈f(A∩B)⇔QUOTE∃x∃x(x∈A∩B∧y=f(x))

⇔QUOTE∃x∃x(x∈A∧x∈B∧y=f(x))⇔QUOTE∃x∃x((x∈A∧y=f(x))∧(x∈B∧y=f(x)))

QUOTE∃x∃x((x∈A∧y=f(x))∧∃x(x∈B∧y=f(x)))

⇔y∈f(A)∧y∈f(B)⇔y∈f(A)∩f(B)因此，。3.设可逆函数，，证明（1） （2） 解因为f是可逆函数，则f是双射函数，既是满射函数又是单射函数，也就是x和y一一对应。（1）设x∈f-1(A∪B)⇔存在唯一的y，使得(x∈A∪B∧y=f(x))

⇔((x∈Ax∈B)∧y=f(x))⇔((x∈A∧y=f(x))(x∈B∧y=f(x)))

⇔((x∈A∧x=f-1(y))(x∈B∧x=f-1(y)))

⇔x∈f-1(A)x∈f-1(B)⇔x∈f-1(A)∪f-1(B)因此，。（2）设x∈f-1(A∩B)⇔存在唯一的y，使得(x∈A∩B∧y=f(x))

⇔((x∈Ax∈B)∧y=f(x))⇔((x∈A∧y=f(x))∧(x∈B∧y=f(x)))

⇔((x∈A∧x=f-1(y))∧(x∈B∧x=f-1(y)))

⇔x∈f-1(A)∧x∈f-1(B)⇔x∈f-1(A)∩f-1(B)因此，。4.给定函数和集合如下：（1）（2）（3）（4）（5）（6）（7）（8）对以上每一组函数和集合，分别回答以下问题：（1）f是满射、单射还是双射？（2）如果f是双射，求f的逆函数。（3）求f(A)和f-1(B)。 解（1）={8}，={4}，f是双射函数，其逆函数就是它自已。（2）={2}，={0，1}，f是双射函数，f-1(y)=log2y。（3）={<5,6>}，={2}，f是单射函数，但不是满射函数。（4），，不是满射