集合论与二元关系题库2012-03-19

PAGEPAGE10《离散数学》题库答案集合论与二元关系一、选择或填空1.设A={a,{a}}，下列命题错误的是（）。（1）{a}P(A)（2）{a}P(A)（3）{{a}}P(A)（4）{{a}}P(A)答：（2）2.在0（）Ф之间写上正确的符号。（1）=（2）（3）（4）答：（4）3.若集合S的基数|S|=5，则S的幂集的基数|P(S)|=（）。答：324.设P={x：(x+1)4且xR}，Q={x：5x+16且xR}，则下列命题哪个正确（）？（1）QP（2）QP（3）PQ（4）P=Q答：（3）5.下列各集合中，哪几个分别相等？（）（1）A1={a,b}（2）A2={b,a}（3）A3={a,b,a}（4）A4={a,b,c}（5）A5={x：(x-a)(x-b)(x-c)=0}（6）A6={x：x2-(a+b)x+ab=0}答：A1=A2=A3=A6，A4=A56.若A-B=Ф，则下列哪个结论不可能正确？（）（1）A=Ф（2）B=Ф（3）AB（4）BA答：（4）7.判断下列命题哪个为真?（）（1）空集只是非空集合的子集（2）空集是任何集合的真子集（3）A-B=B-AA=B（4）若A的一个元素属于B，则A=B答：（3）8.判断下列命题哪几个为正确？（）（1）{Ф}∈{Ф,{{Ф}}}（2）{Ф}{Ф,{{Ф}}}（3）Ф∈{{Ф}}（4）Ф{Ф}（5）{a,b}∈{a,b,{a},{b}}答：（2）（4）9.判断下列命题哪几个正确？（）（1）所有空集都不相等（2）{Ф}Ф（3）若A为非空集，则AA成立。答：（2）10.设A∩B=A∩C，∩B=∩C，则B（）C。答：=（等于）11.判断下列命题哪几个正确？（）（1）若A∪B＝A∪C，则B＝C（2）{a,b}={b,a}（3）P(A∩B)P(A)∩P(B)（P(S)表示S的幂集）（4）若A为非空集，则AA∪A成立答：（2）12.Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理正确？（）（1）AB，BCAC（2）AB，BCA∈B（3）A∈B，B∈CA∈C答：（1）13.设A={1,2,3,4,5,6}，B={1,2,3}，从A到B的关系R={(x,y)：x=y2}，求（1）R（2）R-1。答：（1）R={<1,1>,<4,2>}（2）R-1={<1,1>,<2,4>}。14.举出集合A上的既是等价关系又是偏序关系的一个例子。（）答：A上的恒等关系15.集合A上的等价关系的三个性质是什么？（）答：自反性、对称性和传递性16.集合A上的偏序关系的三个性质是什么？（）答：自反性、反对称性和传递性17.设S={1,2,3,4}，A上的关系Ｒ={<1,2>，<2,1>，<2,3>，<3,4>}。求（1）RR（2）R-1。答：RR={<1,1>，<1,3>，<2,2>，<2,4>}R-1={<2,1>，<1,2>，<3,2>，<4,3>}。18.设A=｛1，2，3，4，5，6｝，R是A上的整除关系，求R={（）}。答：R={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,4>,<2,6>,<3,6>}。19.设A={1,2,3,4,5,6}，B={1,2,3}，从A到B的关系R={<x,y>：x=2y}，求（1）R；（2）R-1。答：（1）R={<1,1>,<4,2>,<6,3>}；（2）R={<1,1>,<2,4>,<3,6>}。20.设A={1,2,3,4,5,6}，B={1,2,3}，从A到B的关系R={<x,y>：x=y2}，求R和R-1的关系矩阵。答：R的关系矩阵=；R的关系矩阵=。21.集合A={1,2,…,10}上的关系R={<x,y>：x+y=10,x,yA}，则R的性质为（）。（1）自反的（2）对称的（3）传递的，对称的（4）传递的答：（2）22.设，则（）。答：{0,1,2,3,4,6}ABC23.A，B，C表示三个集合，文图中阴影部分的集合表达式为（）ABC答：24.设A={1,2,3,4}，A上关系图为则R2=（）。答：{<1,1>,<1,3>,<2,2>,<2,4>}25.设A={a,b,c,d}，其上偏序关系R的哈斯图为则R=（）。答：{<a,b>,<a,c>,<a,d>,<b,d>,<c,d>}∪IA26.下列集合中相等的有（）。（1）{4,3}∪Ф（2）{Ф,3,4}（3）{4,Ф,3,3}（4）{3,4}答：（2）（3）27.设A={1,2,3}，则A上的二元关系有（）个。（1）23（2）32（3）（4）答：（3）28.设A={1,2,3,4}，P(A)（A的幂集）上规定二关元系如下则P(A)/R=（）。（1）A（2）P(A)（3）{{{1}},{{1,2}},{{1,2,3}},{{1,2,3,4}}}（4）{{Ф},{{1},{2},{3},{4}},{{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}},{{1,2,3},{1,2,4},{1,3,4},{2,3,4}},{A}}答：（4）29.设A={Ф,{1},{1,3},{1,2,3}}，则A上包含关系“”的哈斯图为（）。（1）（2）（3）（4）答：（3）30.下列函数是双射的为（）。（1）f:ZE,f(x)=2x（2）f:NNN,f(n)=<n（3）f:RZ,f(x)=[x]（4）f:ZN,f(x)=|x|（注：Z—整数集，E—偶数集，N—自然数集，R—实数集）答：（1）二、解答题或证明题：1.A(B-C)＝(AB)-(AC)。证明：(AB)-(AC)=(AB)=(AB)()=(AB)(AB)=AB=AB=A(B-C)2.(A-B)(A-C)=A-(BC)。证明：(A-B)(A-C)=(A)(A)=A()=A=A-(BC)3.AB=AC，B=C，则C=B。证明：B=B(A)=(B)(BA)=(C)(CA)=C(A)=C。4.AB=A(B-A)。证明：A(B-A)=A(B)=(AB)(A)=(AB)U=AB。5.A=BAB=Ф。证明：设A=B，则AB=(A-B)(B-A)=ФФ=Ф。设AB=Ф，则AB=(A-B)(B-A)=Ф。故A-B=Ф，B-A=Ф，从而AB，BA，故A=B。6.AB=AC，AB=AC，则C=B。证明：B=B(AB)=B(AC)=(BA)(BC)=(AC)(BC)=C(AB)=C(AC)=C7.AB=AC，B=C，则C=B。证明：B=B(A)=(BA)(B)=(CA)(C)=C(A)=C8.A-(BC)＝(A-B)-C。证明：A-(BC)=A=A()=(A)=(A-B)=(A-B)-C9.(A-B)(A-C)=A-(BC)。证明：(A-B)(A-C)=(A)(A)=(AA)()=A=A-(BC)10.A-B=B，则A=B=Ф。证明：因为B=A-B，所以BB=(A-B)B=Ф。从而A=A-B=B=Ф。11.A=(A-B)(A-C)ABC=Ф。证明：因为(A-B)(A-C)=(A)(A)=A()=A=A-(BC)，且A=(A-B)(A-C)，所以A=A-(BC)，故ABC=Ф。因为ABC=Ф，所以A-(BC)=A。而A-(BC)=(A-B)(A-C)，所以A=(A-B)(A-C)。12.(A-B)(A-C)=ФABC。证明：因为(A-B)(A-C)=(A)(A)=A()=A=A-(BC)，且(A-B)(A-C)=Ф，所以Ф=A-(BC)，故ABC。因为ABC，所以A-(BC)=A。而A-(BC)=(A-B)(A-C)，所以A=(A-B)(A-C)。13.(A-B)(B-A)=AB=Ф。证明：因为(A-B)(B-A)=A，所以B-AA。但(B-A)A=Ф，故B-A=Ф。即BA，从而B=Ф（否则A-BA，从而与(A-B)(B-A)=A矛盾）。因为B=Ф，所以A-B=A且B-A=Ф。从而(A-B)(B-A)=A。14.(A-B)-CA-(B-C)。证明：x(A-B)-C，有A-B且xC，即A，xB且xC。从而A，xB-C，故xA-(B-C)。从而(A-B)-CA-(B-C)。15.P(A)P(B)P(AB)（P(S)表示S的幂集）。证明：CP(A)p(B)，有CP(A)或CP(B)，所以CA或CB。从而CAB，故CP(AB)。即P(A)P(B)P(AB)。16.P(A)P(B)=P(AB)（P(S)表示S的幂集）。证明：CP(A)P(B)，有CP(A)且CP(B)，所以CA且CB。从而CAB，故CP(AB)。即P(A)P(B)P(AB)。CP(AB)，有CAB，所以CA且CB。从而CP(A)且CP(B)，故CP(A)P(B)。即P(AB)P(A)P(B)。故P(AB)=P(A)P(B)。17.(A-B)B=(AB)-B当且仅当B=Ф。证明： 当B=Ф时，因为（A-B）B=(A-Ф)Ф=A，(AB)-B=(AФ)-Ф=A，所以(A-B)B=(AB)-B。 用反证法证明。假设B≠Ф，则存在bB。因为bB且bAB，所以b(A-B)B。而显然b(AB)-B。故这与已知(A-B)B=(AB)-B矛盾。18.列出下列二元关系的所有元素：（1）A={0,1,2}，B={0,2,4}，R={<x,y>:x,y};（2）A={1,2,3,4,5},B={1,2}，R={<x,y>:2x+y4且x且yb};（3）A={1,2,3}，B={-3,-2,-1,0,1}，R={<x,y>:|x|=|y|且x且yb};解：（1）R={<0,0>,<0,2>,<2,0>,<2,2>}；（2）R={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>}；（3）R={<1,1>,<1,-1>,<2,-2>,<3,-3>}。19.对任意集合A,B，证明：若AA=BB，则A=B。证明：若B=Ф，则BB=Ф。从而AA=Ф。故A=Ф。从而B=A。若B≠Ф，则BB≠Ф。从而AA≠Ф。对,<x,x>BB。因为AA=BB，则<x,x>A。从而xA。故BA。同理可证，AB。故B=A。20.对任意集合A,B，证明：若A≠Ф，AB=AC，则B=C。证明：若B=Ф，则AB=Ф。从而AC=。因为A≠Ф，所以C=Ф。即B=C。若B≠Ф，则AB≠Ф。从而AC≠Ф。对，因为A≠Ф，所以存在yA，使<y,x>B。因为AB=AC，则<y,x>C。从而xC。故BC。同理可证，CB。故B=C。21.设A={a,b}，B={c}。求下列集合：（1）A{0,1}B；（2）B2A；（3）(AB)2；（4）P(A)A。解：（1）A{0,1}B={<a,0,c>,<a,1,c>,<b,0,c>,<b,1,c>}；（2）B2A={<c,c,a>,<c,c,b>}（3）(AB)2={<a,c,a,c>,<a,c,b,c>,<b,c,a,c>,<b,c,b,c>}；（4）P(A)A={<Ф,a>,<Ф,b>,<{a},a>,<{a},b>,<{b},a>,<{b},b>,<a,a>,<a,b>}。22.设全集U={a,b,c,d,e},A={a,d},B={a,b,c},C={b,d}。求下列各集合：（1）AB；（2）；（3）(A)C；（4）P(A)-P(B)；（5）(A-B)(B-C)；（6）(AB)C。解：（1）AB={a}；（2）={a,b,c,d,e}；（3）(A)C={b,d}；（4）P(A)-P(B)={{d},{a,d}}；（5）(A-B)(B-C)={d,c,a}；（6）(AB)C={b,d}。23.设A,B,C是任意集合，证明或否定下列断言：（1）若AB，且BC，则AC；（2）若AB，且BC，则AC；（3）若AB，且BC，则AC；（4）若AB，且BC，则AC。证明：（1）成立。对xA，因为AB，所以xB。又因为BC，所以xC。即AC。（2）不成立。反例如下：A={a}，B={a,b}，C={a,b,c}。虽然AB，且BC，但AC。（3）不成立。反例如下：A={a}，B={{a},b}，C={{{a},b},c}。虽然AB，且BC，但AC。（4）成立。因为AB，且BC，所以AC。24.A上的任一良序关系一定是A上的全序关系。证明：a，b∈A，则{a,b}是A的一个非空子集。≤是A上的良序关系，{a,b}有最小元。若最小元为a，则a≤b；否则b≤a。从而≤为A上的的全序关系。25.若R和S都是非空集A上的等价关系，则RS是A上的等价关系。证明：a∈A，因为R和S都是A上的等价关系，所以aRa且aSa。故aRSa。从而RS是自反的。a,b∈A，aRSb，即aRb且aSb。因为R和S都是A上的等价关系，所以bRa且bSa。故bRSa。从而RS是对称的。a,b,c∈A，aRSb且bRSc，即aRb，aSb，bRc且bSc。因为R和S都是A上的等价关系，所以aRc且aSc。故aRSc。从而RS是传递的。故RS是A上的等价关系。26.设RA×A，则R自反IAR。证明：xA，R是自反的，xRx。即<x,x>R，故IAR。xA，IAR，<x,x>R即xR，故R是自反的。27.设A是集合，RA×A，则R是对称的R=R-1。证明：<x,y>R，R是对称的，yRx。即<y,x>R，故<x,y>R-1。从而RR-1。反之<y,x>R-1，即<x,y>R。R是对称的，yRx。即<y,x>R，R-1R。故R=R-1。x，yA，若<x,y>R，即<y,x>R-1。R=R-1，<y,x>R。即yRx，故R是对称的。28.设A,B,C和D均是集合，RA×B，SB×C，TC×D，则（1）R(ST)=(RS)(RT)；（2）R(ST)(RS)(RT)。证明：（1）<x,z>R(ST)，则由合成关系的定义知yB，使得<x,y>R且<y,z>ST。从而<x,y>R且<y,z>S或<x,y>R且<y,z>T，即<x,z>RS或<x,z>RT。故<x,z>(RS)(RT)。从而R(ST)(RS)(RT)。同理可证(RS)(RT)R(ST)。故R(ST)=(RS)(RT)。（2）<x,z>R(ST)，则由合成关系的定义知yB，使得<x,y>R且<y,z>ST。从而<x,y>R且<y,z>S且<y,z>T，即<x,z>RS且<x,z>RT。故<x,z>(RS)(RT)。从而R(ST)(RS)(RT)。29.设(A,≤)为偏序集，Ф≠BA，若B有最大（小）元、上（下）确界，则它们是惟一的。证明：设a,b都是B的最大元，则由最大元的定义ab，ba。是A上的偏序关系，a=b。即B如果有最大元则它是惟一的。30.设A={1,2,3}，写出下列图示关系的关系矩阵，并讨论它们的性质：111232323解：（1）R={(2,1>,<3,1>,<2,3>}；Mr=；它是反自反的、反对称的、传递的；（2）R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>}；Mr=；它是反自反的、对称的；（3）R={<1,2>,<2,1>,<1,3>,<3,3>}；Mr=；它既不是自反的、反自反的，也不是对称的、反对称的、传递的。31.设A={1,2,…,10}。下列哪个是A的划分？若是划分，则它们诱导的等价关系是什么？（1）B={{1,3,6},{2,8,10},{4,5,7}}；（2）C={{1,5,7},{2,4,8,9},{3,5,6,10}}；（3）D={{1,2,7},{3,5,10},{4,6,8},{9}}。解：（1）和（2）都不是A的划分。（3）是A的划分。其诱导的等价关系是I{<1,2>,<2,1>,<1,7>,<7,1>,<2,7>,<7,2>,<3,5>,<5,3>,<3,10>,<10,3>,<10,5>,<5,10>,<4,6>,<6,4>,<4,8>,<8,4>,<6,8>,<8,6>}。32.R是A={1,2,3,4,5,6}上的等价关系，R=I{<1,5>,<5,1>,<2,4>,<4,2>,<3,6>,<6,3>}求R诱导的划分。解：R诱导的划分为{{1,5},{2,4},{3,6}}。33.A上的偏序关系的Hasse图如下。（1）下列哪些关系式成立：ab，ba，ce，ef，df，cf；（2）分别求出下列集合关于的极大（小）元、最大（小）元、上（下）界及上（下）确界（若存在的话）：（a）A；（b）{b,d}；（c）{b,e}；（d）{b,d,e}。aefbdc解：（1）ba，ce，df，cf成立；（2）（a）的极大元为a,e,f，极小元为c；无最大元，c是最小元；无上界，下界是c；无上确界，下确界是c。（b）的极大元为b,d，极小元为b,d；无最大元和最小元；上界是e，下界是c；上确界是e，下确界是c。（c）的极大元为e，极小元为b；最大元是e，b是最小元；上界是e，下界是b；上确界是e，下确界是b。（d）的极大元为e，极小元为b,d；最大元是e，无最小元；上界是e，下界是c；上确界是e，下确界是c。34.设集合A={a,b,c,d,e}上的二元关系为R={<a,a>,<a,b>,<a,c>,<a,d>,<a,e>,<b,b>,<b,c>,<b,e>,<c,c>,<c,e>,<d,d>,<d,e>,<e,e>}验证<A,R>是偏序集，并画出哈斯图。解：因为<a,a>,<b,b>,<c,c>,<d,d>,<e,e>R，所以R是自反的；因为<a,b>R但<b,a>R，<a,c>R但<c,a>R，<a,d>R但<d,a>R，<a,e>R但<e,a>R，<b,c>R但<c,b>R，<b,e>R但<e,b>R，<c,e>R但<e,c>R，<d,e>R但<e,d>R，<b,d>,<d,b>,<c,d>,<d,c>R，所以R是反对称的；因为R2={<a,a>,<a,b>,<a,c>,<a,d>,<a,e>,<b,b>,<b,c>,<b,e>,<c,c>,<c,e>,<d,d>,<d,e>,<e,e>}=R，所以R是传递的。故R是A上的偏序关系，<A,R>是偏序集。对应哈斯图如下：ecdba35.证明：A到B的映射决定A的一个划分，A的一个划分也决定A到B的一个映射。解：设f是A到B的一个映射，定义A上的关系R：aRbf(a)=f(b)。易证R上A上的一个等价关系，因此诱导出A的一个划分。反过来，设是一个A的划分，则定义A到B的一个对应关系f：对在同一个划分块中的所有A的元素，让它们在f下对应于B的同一个元素。则显然f是A到B的一个映射。36.设全集U={1,2,3,4,5,6,7,8,9,10}，A={1,3,4,5,6,7,8}，B={2,4,5,6,9,10}，C={1,3,5,7,9}。计算A-B，AC，BC(B与C的对称差或环和)，A(BC)，，A。解：A-B={1,3,7,8}；AC={4,5,6}；BC={1,2,3,4,5,6,7,10}；A(BC)={1,3,4,5,6,7,8,9}；={}；A∩={1,3,7,8}。37.设全集U={1,2,3,4,5,6,7,8,9,10}，A={1,2,3,4,5,6,7}，B={4,5,6,7,8,9,10}，C={2,4,6,8,10}。计算A-B，A∩C，BC（B与C的对称差或环和），A∪B∪C，，A∪。解：A-B={1,2,3}；A∩C={2,4,6}；BC={2,5,7,9}；A∪B∪C={1,2,3,4,5,6,7,8,9,10}；={1,3,5,7,8,9,10}；A∪={1,2,3,4,5,6,7,8,9,10}。38.设全集U={1,2,3,4,5,6,7,8,9,10}，A={4,5,6,7,8,9,10}，B={1,2,3,4,5,6,7}，C={2,4,6,8,10}。计算A-B，AC，BC（B与C的对称差或环和），ABC，（AC的补集）。解：A-B={8,9,10}；AC={2,4,5,6,7,8,9,10}；BC={1,3,5,7,8,10}；ABC={4,6}；={1,2,3,5,7,9}。39.设集合A={a,b,c,d}上的关系R={<a,b>,<b,a>,<b,c>,<c,d>}用矩阵运算求出R的传递闭包t(R)。解：，，t(R)={<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c>,<b,d>,<c,d>}。40.若是从A到B的函数，定义一个函数对任意有，证明：若f是A到B的满射，则g是从B到的单射。证明：。41.设S是A上一个二元关系，R={<a,b>|（a,bA）（存在某cA有<a,c>S且<c,b>S）}。证明：若S是A上一个等价关系，则R也是A上的一个等价关系。证明：，由S自反，所以<a,a>S且<a,a>S，从而<a,a>R。故R自反。,若<a,b>R，则存在cA使得<a,c>S且<c,b>S。因为S对称，所以有<b,c>S且<c,a>S。根据R的定义有<b,a>R,故R对称。,若<a,b>R且<b,c>R，则存在d,eA使得<a,d>S,<d,b>S,