離散數(shù)學(xué)(胡海濤)第3章答案

1、離散數(shù)學(xué)第三章(胡海濤版)1。下列集合分別用描述和枚舉表示：(1)非負(fù)偶集合；(2)整數(shù)24的所有正因子的集合；(3)一組不超過9且以9為素數(shù)的正整數(shù)(這組中的元素數(shù)稱為歐拉函數(shù)(9)。解答：說明(1)x|x是一個非負(fù)偶數(shù)(2)x|x是一個24 (3)x| x的正因子，x是一個不超過9的正整數(shù)，并且與9 (1) 0，2，4，(2) 1，2，3，4，6，8，12，24()是素數(shù)。如果是這樣，請給出一個例子。解決方案：存在。A=1，B=1，1，那么AB和AB都有效。3.找出下列集合的冪集：(1)；(2)；(3)a，a；(4)1，2 .解答：解答：(1) p ()=(2) p ()=，(3) p (

2、a，a)=，a，a，a (4) p (1，2)=，1，24。設(shè)S=0，1，求集合SP(S)解：解：p (s)=，0，1，0，1 sp (s)=，5。證明對于任何集合A和B，都有P(A)P(B)P(AB)，P(A)P(B)P(AB)并證明：對于任何集合C，如果CP(A)P(B)CP(A)CP(B)CACBCAB，那么P(A)P(B)P(AB)成立。在任意集合c中，如果CP(A)P(B)CP(A)CP(B)CACBCAB，那么P(A)P(B)P(AB)成立。例如：A=1，2，B=2，3，P(A)=，1，2，1，2，P(B)=，2，3，2，3，P(A)P(B)=，1，2，1，2，3，2因此，P(A)

3、P(B)P(AB)。6.設(shè)甲、乙、丙為任意集合，并證明：(1)丙(乙)=(甲)(乙)；(2)如果ABBC是已知的，并且有A-BB-C，那么AB。證明：(1)C(AB)=C(AB)(BA)=(C(AB)(C(BA)=(CA)(CB)(CB)=(CA)(CB)(2)證明定律如果結(jié)論不正確，那么就有xA和xB，然后是xA-B和xB-C，也就是xB。與xB的矛盾。7.下列關(guān)系的屬性是什么？(1)有mRn當(dāng)且僅當(dāng)|i-k|8(m，Nn)；(3)當(dāng)且僅當(dāng)ik(i，kN)時，存在iRk。解答：解答：(1)自反，對稱(2)對稱(3)自反，對稱，傳遞8。請在滿足下列條件的集合Aa，b，c上構(gòu)造二元關(guān)系：(1)對

4、稱和反對稱；(2)既不反身也不反身；(3)對稱性和自反性；(4)反身性、對稱性和傳遞性；(5)作為子集，是可傳遞的。解決方案：(1)、(2)、(3)、(4)、(5)、(9)。設(shè)Rj代表Z上模J的等價關(guān)系，Rk代表Z上模K的等價關(guān)系，證明了當(dāng)且僅當(dāng)K是J的整數(shù)倍時，Z/Rk細(xì)分Z/Rj。證明：充分性：如果K是J的整數(shù)倍，即lZ，設(shè)k=lj，Z/Rk=aRk| aZ，Z/Rj=aRj| aZ，ark=x | xzarxx，arj=x | xzarxx，顯然對于任何xaRk，ax(mod k)，即必要性證明如果關(guān)系r是對稱的，那么Rk(k1，kN)也是對稱的。證明：設(shè)R是A上的二元關(guān)系，并且X，yA

5、，如果xRky成立，那么根據(jù)關(guān)系式的定義，存在x0=x，x1，x2，xk- 1，xk=y，這使得X0RX1，X1RX2，XK-1RXK成立，并且R是對稱的，所以xKx0-1，11.設(shè)集合A=a，b，c，d上的關(guān)系R=，用矩陣運算求R的自反性，對稱性和傳遞閉包。解：0100 1010 0001 0000 R M，1000 0100 0010 0001 A I，1 0100 1000 0100 0010 r m，0100 1010 00001 0000 1000 0100 00100 0010 000010因此，r (r)=，0100 1010 0001 0000 0100 1000 0010=0

6、100 1010 0101 0010 so s(R)=，2 01000100100101010010000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000設(shè)R和S是a和RS上的二元關(guān)系，證明：(1)r(R)r(S) (2) S (R)S (S)(3)T(R)T(S)證明：(1)r(R)定義的R(R)有RIA，如果R是RS定義的，R(S)(2)S (R)，S(R)定義的，有RR1，如果R是RS定義的，s(S)，如果R1有R，所以S，所以S1是S(S)，所以S (R)

7、 S (S)。(3)由t(R)定義的t(R)具有Rk(k1，kN)，即x0=x，x1，x2，xk-1，xk=y，這使得x0rx1，x1rx2，xk-1rxk保持不變，并由RS定義，因此x0sx1，x1sx2，13.設(shè)R和S是a上的二元關(guān)系，并證明：(1)R(RS)=R(R)R(S)(2)S(RS)=S(R)S(S)(3)t(R)t(S)t(RS)證明：(1)(2)S(RS)=(RS)(RS)1=(RS)(R1S1)=(RR1)(SS1)=S(R)S(S).(3) t (r) t (s)=I I r 1 I s 1，t(t(RS)=I I S)R(1=I I R 1 I S 1 Ji SR，1

8、1，顯式t(R)t(S)t(RS)。14.找出集合a，b，c和D的所有劃分和等價關(guān)系.解決方案：集合A、B、C、D共有四個元素，可分為如下四類：1) 41111類型劃分，只有一個，即A、B、C、D，對應(yīng)的等價關(guān)系為：2)4211有2 4個C6類型，即A、B、C、D、A、C、B、D、A、D、B、B、C、A、D、B、D、A、C、D、A、B。對應(yīng)的等價關(guān)系如下5)440型分為1，即甲、乙、丙、丁，對應(yīng)的等價關(guān)系為：綜上所述，集合a、b、c和D有15個劃分和等價關(guān)系.15.設(shè)R是非空集A上的二元關(guān)系，如果A、B和CA滿足aRb和bRccRa，那么R稱為A上的循環(huán)關(guān)系，證明了當(dāng)且僅當(dāng)R是等價的，R是自反

9、循環(huán)的。證明：證明：必要性：如果R是自反的和循環(huán)的，它適用于a，b，cA，aRa如果aRc成立，R和cRa是循環(huán)的，所以R是對稱的；如果aRb和bRc與cRa是循環(huán)的，那么R與aRc是對稱的，所以R是傳遞的，所以R是等價的。充分性：如果R是等價的，很明顯R是自反的，并且只需要證明R是循環(huán)的。對于a，b，cA，如果aRb和bRc，從R的傳遞性來看，有aRc，然后從R的對稱性來看，有cRa，所以R是循環(huán)的。16.假設(shè)a和B是非空集合，f是從a到B的映射.將A上的二元關(guān)系R定義為：x，yA，xRy當(dāng)且僅當(dāng)f(x)=f(y)，證明R是A上的等價關(guān)系，并描述由R生成的A的除。證明：證明：顯然f(x)=f

10、(x)，所以xRx是自反的。如果xRy有f(x)=f(y)，那么f(y)=f(x)，那么yRx，也就是r，是對稱的。如果xRy和yRz有f(x)=f(y)，f(y)=f(z)，那么f(x)=f(z)，xRz，也就是說，r是可傳遞的。因此，r是a上的等價關(guān)系.在由R生成的A的除法中，所有具有相同對應(yīng)值的獨立變量都屬于同一個塊。17.給出一個二元關(guān)系，它既是等價關(guān)系又是偏序關(guān)系。解決方案：R=，在aa，b，c上。18.假設(shè)A1、A2和A3是完備集u的子集，那么形式為3 1i Ai(Ai是Ai或Ai)的集合稱為由A1、A2和A3產(chǎn)生的次項。證明了A1、A2、A3產(chǎn)生的所有非空項的集合構(gòu)成了完整集合U

11、的一個劃分，證明：(1)3 1 ai(2)3 1 ai 3 1 AIJ=(3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)=(A1 A2)(a1a 2 19)。設(shè)R和S是a上的相容關(guān)系，并問：(1)復(fù)合關(guān)系R和S是a上的相容關(guān)系嗎？(2)2)RS是A上的相容關(guān)系嗎？(3)3)RS是A上的相容關(guān)系嗎？解決方案：(1)讓A=1，2，3，R=，S=，R=，不兼容。(2)RS顯然是自反的，所以RS是R和S，所以R和S是RS，所以RS是a上的相容關(guān)系。在偏序關(guān)系“可分”下畫出集合S=1，2，3，4，5，6的哈斯圖，(1)寫出1，2，3，4，5，6的最大(小)元素和最大(小)元素；(2)分別寫出2，3，6和2，3，5的上(下)界和上(下)界。解決方案：哈斯圖如下：5 4 6