集合論與二元關(guān)系題庫2012-03-19

PAGEPAGE10《離散數(shù)學(xué)》題庫答案集合論與二元關(guān)系一、選擇或填空1.設(shè)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的基數(shù)|S|=5，則S的冪集的基數(shù)|P(S)|=（）。答：324.設(shè)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=Ф，則下列哪個結(jié)論不可能正確？（）（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},}答：（2）（4）9.判斷下列命題哪幾個正確？（）（1）所有空集都不相等（2）{Ф}Ф（3）若A為非空集，則AA成立。答：（2）10.設(shè)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.設(shè)A={1,2,3,4,5,6}，B={1,2,3}，從A到B的關(guān)系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上的既是等價關(guān)系又是偏序關(guān)系的一個例子。（）答：A上的恒等關(guān)系15.集合A上的等價關(guān)系的三個性質(zhì)是什么？（）答：自反性、對稱性和傳遞性16.集合A上的偏序關(guān)系的三個性質(zhì)是什么？（）答：自反性、反對稱性和傳遞性17.設(shè)S={1,2,3,4}，A上的關(guān)系Ｒ={<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.設(shè)A=｛1，2，3，4，5，6｝，R是A上的整除關(guān)系，求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.設(shè)A={1,2,3,4,5,6}，B={1,2,3}，從A到B的關(guān)系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.設(shè)A={1,2,3,4,5,6}，B={1,2,3}，從A到B的關(guān)系R={<x,y>：x=y2}，求R和R-1的關(guān)系矩陣。答：R的關(guān)系矩陣=；R的關(guān)系矩陣=。21.集合A={1,2,…,10}上的關(guān)系R={<x,y>：x+y=10,x,yA}，則R的性質(zhì)為（）。（1）自反的（2）對稱的（3）傳遞的，對稱的（4）傳遞的答：（2）22.設(shè)，則（）。答：{0,1,2,3,4,6}ABC23.A，B，C表示三個集合，文圖中陰影部分的集合表達(dá)式為（）ABC答：24.設(shè)A={1,2,3,4}，A上關(guān)系圖為則R2=（）。答：{<1,1>,<1,3>,<2,2>,<2,4>}25.設(shè)A={a,b,c,d}，其上偏序關(guān)系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.設(shè)A={1,2,3}，則A上的二元關(guān)系有（）個。（1）23（2）32（3）（4）答：（3）28.設(shè)A={1,2,3,4}，P(A)（A的冪集）上規(guī)定二關(guān)元系如下則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.設(shè)A={Ф,{1},{1,3},{1,2,3}}，則A上包含關(guān)系“”的哈斯圖為（）。（1）（2）（3）（4）答：（3）30.下列函數(shù)是雙射的為（）。（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—整數(shù)集，E—偶數(shù)集，N—自然數(shù)集，R—實數(shù)集）答：（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=Ф。證明：設(shè)A=B，則AB=(A-B)(B-A)=ФФ=Ф。設(shè)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當(dāng)且僅當(dāng)B=Ф。證明： 當(dāng)B=Ф時，因為（A-B）B=(A-Ф)Ф=A，(AB)-B=(AФ)-Ф=A，所以(A-B)B=(AB)-B。 用反證法證明。假設(shè)B≠Ф，則存在bB。因為bB且bAB，所以b(A-B)B。而顯然b(AB)-B。故這與已知(A-B)B=(AB)-B矛盾。18.列出下列二元關(guān)系的所有元素：（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.設(shè)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>,<,a>,<,b>,<a,a>,<a,b>}。22.設(shè)全集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)={qimv40h,{a,d}}；（5）(A-B)(B-C)={d,c,a}；（6）(AB)C={b,d}。23.設(shè)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上的任一良序關(guān)系一定是A上的全序關(guān)系。證明：a，b∈A，則{a,b}是A的一個非空子集?！苁茿上的良序關(guān)系，{a,b}有最小元。若最小元為a，則a≤b；否則b≤a。從而≤為A上的的全序關(guān)系。25.若R和S都是非空集A上的等價關(guān)系，則RS是A上的等價關(guān)系。證明：a∈A，因為R和S都是A上的等價關(guān)系，所以aRa且aSa。故aRSa。從而RS是自反的。a,b∈A，aRSb，即aRb且aSb。因為R和S都是A上的等價關(guān)系，所以bRa且bSa。故bRSa。從而RS是對稱的。a,b,c∈A，aRSb且bRSc，即aRb，aSb，bRc且bSc。因為R和S都是A上的等價關(guān)系，所以aRc且aSc。故aRSc。從而RS是傳遞的。故RS是A上的等價關(guān)系。26.設(shè)RA×A，則R自反IAR。證明：xA，R是自反的，xRx。即<x,x>R，故IAR。xA，IAR，<x,x>R即xR，故R是自反的。27.設(shè)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.設(shè)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)，則由合成關(guān)系的定義知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)，則由合成關(guān)系的定義知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.設(shè)(A,≤)為偏序集，Ф≠BA，若B有最大（?。┰?、上（下）確界，則它們是惟一的。證明：設(shè)a,b都是B的最大元，則由最大元的定義ab，ba。是A上的偏序關(guān)系，a=b。即B如果有最大元則它是惟一的。30.設(shè)A={1,2,3}，寫出下列圖示關(guān)系的關(guān)系矩陣，并討論它們的性質(zhì)：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.設(shè)A={1,2,…,10}。下列哪個是A的劃分？若是劃分，則它們誘導(dǎo)的等價關(guān)系是什么？（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的劃分。其誘導(dǎo)的等價關(guān)系是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}上的等價關(guān)系，R=I{<1,5>,<5,1>,<2,4>,<4,2>,<3,6>,<6,3>}求R誘導(dǎo)的劃分。解：R誘導(dǎo)的劃分為{{1,5},{2,4},{3,6}}。33.A上的偏序關(guān)系的Hasse圖如下。（1）下列哪些關(guān)系式成立：ab，ba，ce，ef，df，cf；（2）分別求出下列集合關(guān)于的極大（?。┰?、最大（?。┰?、上（下）界及上（下）確界（若存在的話）：（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.設(shè)集合A={a,b,c,d,e}上的二元關(guān)系為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上的偏序關(guān)系，<A,R>是偏序集。對應(yīng)哈斯圖如下：ecdba35.證明：A到B的映射決定A的一個劃分，A的一個劃分也決定A到B的一個映射。解：設(shè)f是A到B的一個映射，定義A上的關(guān)系R：aRbf(a)=f(b)。易證R上A上的一個等價關(guān)系，因此誘導(dǎo)出A的一個劃分。反過來，設(shè)是一個A的劃分，則定義A到B的一個對應(yīng)關(guān)系f：對在同一個劃分塊中的所有A的元素，讓它們在f下對應(yīng)于B的同一個元素。則顯然f是A到B的一個映射。36.設(shè)全集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的對稱差或環(huán)和)，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.設(shè)全集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的對稱差或環(huán)和），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.設(shè)全集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的對稱差或環(huán)和），ABC，（AC的補(bǔ)集）。解：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.設(shè)集合A={a,b,c,d}上的關(guān)系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的函數(shù)，定義一個函數(shù)對任意有，證明：若f是A到B的滿射，則g是從B到的單射。證明：。41.設(shè)S是A上一個二元關(guān)系，R={<a,b>|（a,bA）（存在某cA有<a,c>S且<c,b>S）}。證明：若S是A上一個等價關(guān)系，則R也是A上的一個等價關(guān)系。證明：，由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。根據(jù)R的定義有<b,a>R,故R對稱。,若<a,b>R且<b,c>R，則存在d,eA使得<a,d>S,<d,b>S,