哈工大離散數(shù)學(xué)教科書習(xí)題答案(文件)
【正文】 當(dāng)時。假設(shè)存在和：，因為，于是，使得。假設(shè)不是單射，則，但。解：（1）但，故f是滿射，但f不是單射。（1）若存在唯一的一個映射，使得，則是可逆的嗎？（2）若存在唯一的一個映射，使得，則是可逆的嗎？答案：（1）不一定可逆。證：由，得是單射。為對換即可。證：假設(shè)與的奇偶性不同，不妨設(shè)為奇置換，為偶置換。 －循環(huán)置換（123），（124）…（12n）中若干之乘積。5. 設(shè)，A上的代數(shù)運算“”如表所示。7. 設(shè)“”是X上的代數(shù)運算，則應(yīng)該怎樣定義“”的逆運算？回憶一下，逆運算通常比原運算“難算”，這是為什么？例如，積分比微分難，減法比加法難，除法比乘法難，開方比冪方運算難。設(shè)，R是X上的二元關(guān)系。、S是X上的二元關(guān)系。于是或，即，因而。故（3），則。證2：，則或，即或。于是由xRy和yRx以及R的傳遞性即得xRx。此人只是說明了X中的部分元素滿足了xRx，因而是錯誤的。 b）若R,S都是對稱的，則也是對稱的。 答案：真假假假假，R2和R3是B到C的二元關(guān)系，則一般情況下。同理可證相反的包含關(guān)系成立，故等式成立，這個證明錯在什么地方？解：由且，只能得到。證1，故R對稱。當(dāng)n=1時，Rn=R顯然是對稱的。因為Rk，R均是對稱的，所以，于是。因為Ri0對稱，所以有，故。其次，設(shè)，因為是一切包含的傳遞關(guān)系的交，而且是傳遞的，故，即。（3）（4）先證再證因為是包含的一切傳遞關(guān)系的交，又因為且是傳遞的，所以。證：（1）因為所以因此（2）因為所以因此 〔證畢〕。？為什么？解：不可以。解：存在。因為若R是對稱的，所以也是對稱的，因此。由自反閉包的定義可知：又，故，因此。于是，故，但。證明（1）是S上的等價關(guān)系，（2）求等價類的集合。故等價類集合為。故3. （1）是等價關(guān)系顯然。證；，i與i必在的循環(huán)分解式中的同一個循環(huán)置換中，即，則是自反的。因而是傳遞性的。，試求：（1）X上自反二元關(guān)系的個數(shù)；（2）X上反自反二元關(guān)系的個數(shù)；（3）X上對稱二元關(guān)系的個數(shù)；（4）X上自反或?qū)ΨQ關(guān)系的個數(shù)；解：（1）X上自反二元關(guān)系的個數(shù)為（2）X上反自反二元關(guān)系的個數(shù)為（3）X上對稱二元關(guān)系的個數(shù)為（4）X上自反或?qū)ΨQ關(guān)系的個數(shù)為習(xí)題。證：的每個分點也是的分點，故，因此是自反的；，若且，則的每個分點也是的分點且的每個分點也是的分點，故。從而是自反的；(2)，若且，則且。由是偏序集可知：與是傳遞的，所以且。因為不滿足反對稱性。解：存在。證明：是上的等價關(guān)系。下面看傳遞性因為若；由是傳遞的，有。而，所以是自反的；，若，則與在一個等類中，故，因此是反對稱的；，若，則由的傳遞性有，即。證：，由于是上的全序關(guān)系，故或必有一個成立。 第四章 無窮集合及其基數(shù)習(xí)題的所有項組成的集合，則是否市可數(shù)的？為什么？解：因為序列是可以重復(fù)的，故若是由有限個數(shù)組成的集合，則是有限的集合；若是由無限個數(shù)組成的集合，則是可數(shù)的。：單調(diào)函數(shù)的不連續(xù)點的集合至多可數(shù)。令，設(shè)，則是Ａ的子集的特征函數(shù)。于是，可數(shù)集的所有有限子集對應(yīng)著有理數(shù)的一個子集。7．設(shè)Ａ是有限集，Ｂ是可數(shù)集，證明：是可數(shù)的。于是由４題即可證明）（。Ａ1＝{長度為1的字符串}Ａ2＝{長度為2的字符串} Ａn＝{長度為n的字符串} 因為Ａi 中每個長度都是有限的，而＝，故是至多可數(shù)的。習(xí)題，使得它是到實數(shù)的一一對應(yīng)。令即為所求。假設(shè)可數(shù)，則的子集（即的元素）是可數(shù)的，故中元素可排成一個無重復(fù)項的無窮序列：而，于是特征函可數(shù)，即可寫成下列無窮序列形式： 其中或。5．令，利用康托對角線法證明S是不可數(shù)集。該序列對應(yīng)的函數(shù)，不為任一個，矛盾。每個函數(shù)確定了一個0,1序列。令則,但確實是到的一個映射，即是的子集的特征函數(shù)，矛盾。（用對角線方法）。證：中包含一個可數(shù)子集可數(shù)。證2：不妨假設(shè)（令＝也是可以），則可按字典序排序為：。8. 設(shè)為一個有限字母表，上所有字（包括空字）之集記為。設(shè)。而可數(shù)集Ａ的所有有限子集是無窮的，故是可數(shù)的。于是就對應(yīng)著一個由0，1組成的有限序列0，1，1，0，…，0，1。：直線上互不相交的開區(qū)間的全體所構(gòu)成的集合至多可數(shù)。因此。綜上可知：是上的偏序關(guān)系。因此是上的等價關(guān)系。證明：是上的偏序關(guān)系。在上定義的小于或等于關(guān)系“”，則就是一個沒有最大元素，但卻有唯一極大元的偏序集。故不滿足反對稱性，因此不是偏序關(guān)系。綜上可知：是上的一個偏序關(guān)系。因此“”是對稱的。證明：（1）是上的偏序關(guān)系；（2）若或，則是上的偏序關(guān)系嗎？證：1.(1)，則。因此是傳遞的。在上定義二元關(guān)系如下：的每個分點也是的分點。＝{1,2,3,4}上兩個等價關(guān)系R與S，使得不是等價關(guān)系。因而是對稱性的。故等價類集合為。(2)如圖4所示。（2），共有8個，如圖4所示。習(xí)題。（3）因為，故，因此。，證明：（1）（2）（3）證：（1）因為都是A上的自反關(guān)系，所以也A上的自反關(guān)系。：若R是對稱的，則R＋也是對稱的。因此不定義二元關(guān)系的反自反閉包和反對稱閉包?！叭P(guān)系”。＝（a,b,c,d,e），R＝｛（a,b），（b,c），（c,d），（d,e）｝試求和。（2）因為顯然成立。習(xí)題，試證（1）。綜上，Rn對都是對稱關(guān)系。當(dāng)n=k+1時。因為R對稱，所以，因此，故R對稱。例如時，故這步推理錯誤，S是X上的滿足的對稱關(guān)系，證明.證1：設(shè)，則使得且。于是且。
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1