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