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