《離散數(shù)學(xué)(劉任任版)第2章答案.ppt》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)(劉任任版)第2章答案.ppt（45頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

習(xí)題二,1.,(1).R={,,,},(2).R={,,,},2.,設(shè)R是定義在集合A上的二元關(guān)系。(1).設(shè)A=?，則R=?既是自反的又是反自反的.(2).令A(yù)={1，2}，R={}，于是R既不是自反又不是反自反的；(3).令A(yù)={1，2}，R={,},于是R既是對稱又是反對稱的；,(4).令A(yù)={1,2,3},R={,,},于是R既不是對稱又不是反對稱的。,3.,設(shè)A={X1,X2,…,Xn}，于是定義在A上的二元關(guān)系R中的元素來自于下列矩陣：……….…,,,(1)共有2n2種定義在A上的不同的二元關(guān)系；說明:∵|A|=n∴|AA|=n2∴|β(AA)|=2n2,(2)共有種定義在A上的不同的自反關(guān)系；說明:∵A上的自反關(guān)系必須滿足所有形如的序偶包含在關(guān)系中，而形如的序偶有n個(gè)。即|AA-{}|=n2-n∴在構(gòu)造A上的自反關(guān)系的時(shí)候可以先將所有的放到這些關(guān)系中再考慮其他序偶的組合。即|β(AA-{})|=2n2-n,(3)共有種定義在A上的不同的反自反關(guān)系；說明:∵A上的反自反關(guān)系必須滿足所有形如的序偶不能包含在關(guān)系中，∴在構(gòu)造A上的反自反關(guān)系的時(shí)候可以先將所有的拿出后再考慮其他序偶的組合。即β(AA-{})=2n2-n,(4)共有種定義在A上的不同的對稱關(guān)系;說明:∵A上的對稱關(guān)系必須滿足：如果在這個(gè)關(guān)系中，則也必須在這個(gè)關(guān)系中?！嘣跇?gòu)造A上的對稱關(guān)系的時(shí)候可以先將所有的和（其中x≠y）看成是一個(gè)整體?！嘁紤]的序偶的個(gè)數(shù)有：n+(n2-n)/2=n(n+1)/2∴β({}+(AA-{})/2)=2(n2+n)/2,(5)共有種定義在A上的不同的反對稱，其中，。,4.,(1)自反關(guān)系矩陣的主對角線上元素全為1；而關(guān)系圖中每個(gè)結(jié)點(diǎn)上都有圈（即若關(guān)系R是自反的，當(dāng)且僅當(dāng)在關(guān)系矩陣中，對角線上的所有元素都是1，在關(guān)系圖上每個(gè)結(jié)點(diǎn)都有自回路）。(2)反自反關(guān)系矩陣的主對角線上元素全為0;而關(guān)系圖中每個(gè)結(jié)點(diǎn)上均無圈（即若關(guān)系R是反自反的，當(dāng)且僅當(dāng)在關(guān)系矩陣中，對角線上的所有元素都是0，在關(guān)系圖上每個(gè)結(jié)點(diǎn)都沒有自回路）。,(3)對稱關(guān)系矩陣為對稱矩陣;而關(guān)系圖中任何兩個(gè)結(jié)點(diǎn)之間的有向弧是成對出現(xiàn)的,方向相反。（即若關(guān)系R是對稱的，當(dāng)且僅當(dāng)關(guān)系矩陣是對稱的，且在關(guān)系圖上任兩個(gè)結(jié)點(diǎn)若有定向弧線，則定向弧線必定是成對出現(xiàn)的）反對稱關(guān)系矩陣的元素滿足：當(dāng)i≠j時(shí)，。而關(guān)系圖中任何兩個(gè)結(jié)點(diǎn)之間的有向弧是單向的。（即若關(guān)系R是反對稱的，當(dāng)且僅當(dāng)關(guān)系矩陣中以對角線對稱的元素不能同時(shí)為1，在關(guān)系圖上任兩個(gè)結(jié)點(diǎn)的定向弧線不可能成對出現(xiàn)）,5.,RS={,},SR={};R2={,,};S2={,,}.,6.,設(shè)R={,},T={,},S={,},P={,},,7.,(1)正確。因?yàn)閷θ我鈞∈A，有xRx，xSx,所以x(RS)x。故RS是自反的。(2)錯(cuò)誤。例如，設(shè)x,y∈A，x≠y,且xRy，ySx，于是x(RS)x。故RS不是反自反的。,(3)錯(cuò)誤。例如，設(shè)對稱關(guān)系R={,},S={,}。則RS={},故RS不是對稱的。,(4)錯(cuò)誤。例如，設(shè)反對稱關(guān)系R={,},S={,},x≠y。于是，RS={,}。故RS不是反對稱的。(5)錯(cuò)誤。例如，設(shè)傳遞關(guān)系R={,},S={,},w≠v。于是，RS={,}，顯然，RS不是一個(gè)傳遞關(guān)系。,思考：假設(shè)R，S是定義在有限集合A上的滿足下表列標(biāo)題性質(zhì)的二元關(guān)系，試判斷下表行標(biāo)題所列二元關(guān)系是否具有相應(yīng)性質(zhì)。,思考：假設(shè)R，S是定義在有限集合A上的滿足下表列標(biāo)題性質(zhì)的二元關(guān)系，試判斷下表行標(biāo)題所列二元關(guān)系是否具有相應(yīng)性質(zhì)。,8.,(3)由定義，,于是存在z1,z2,zn-1,滿足：,∈R1?R1∪R2,舉例說明“”成立。設(shè),9.,設(shè)R1和R2是集合A上的二元關(guān)系。注意到,(3)由定義，,t(R1∩R2)=(R1∩R2)∪(R1∩R2)2∪∧于是t(R1)∩t(R2)=((R1∩R2)∪(R1∩R22)∪∧)∪((R12∩R22)∪(R12∩R2)∪∧)∪∧下證對任意的n≥1,有(R1∩R2)n?(R1n∩R2n)證明:任取∈(R1∩R2)n,則存在n-1個(gè)元素z1,z2…zn-1滿足∈R1∩R2,∈R1∩R2,…,∈R1∩R2。從而有∈R1,∈R1,…,∈R1并且∈R2,∈R2,…,∈R2。,所以有∈R1n并且∈R2n，即∈R1n∩R2n所以(R1∩R2)n?(R1n∩R2n)例如：設(shè)A={1，2，3}，R1={,},R2={}則t(R1)={,,{},t(R2)={},t(R1)∩t(R2)={},R1∩R2=?,t(R1∩R2)=?,,10.說法不正確.這是因?yàn)樽苑葱砸髮θ我獾膞和x都有關(guān)系R,x和y有沒有關(guān)系R,我們不考慮；但是,我們題目中得出的結(jié)論x和x具有關(guān)系R,是以對稱性為前提條件的,所以我們知道該論述不正確。,11.,設(shè)R是等價(jià)關(guān)系。若,∈R，則由R的對稱性知,∈R。再由R的傳遞性有∈R。反之,假設(shè)只要,∈R，就有∈R。(1)對稱性。設(shè)∈R，由自反性有∈R。于是∈R。(2)傳遞性。設(shè),∈R。由對稱性有∈R,再由假設(shè)有∈R。,12.,而由A/R1=A/R2,有對任意x∈A,因?yàn)閇x]R1∈A/R2并且x∈[x]R1∩[x]R2，所以[x]R1=[x]R2。產(chǎn)生矛盾。,13.,14.,故S是X的一個(gè)劃分,15.,設(shè)A={1,2,3,4},則A上的等價(jià)關(guān)系數(shù)目即A上的劃分的數(shù)目共有15個(gè)(1)最大劃分{{1},{2},{3},{4}}(2)最小劃分{{1,2,3,4}}(3)將A分成兩個(gè)集合S={A1，A2}，有兩種可能：,{{1,2},{3},{4}},{{1,3},{2},{4}},{{1,4},{2},{3}},{{2,3},{1},{4}},{{2,4},{1},{3}},{{3,4},{1},{2}}.設(shè)Ek表示k元集合A上的全部等價(jià)關(guān)系數(shù)目,則,因?yàn)镋n是將n個(gè)元素的集合進(jìn)行劃分的方法數(shù)，對任何一個(gè)劃分來說，b總是在劃分的某一個(gè)塊中，也就是某一個(gè)子集中。不妨設(shè)這個(gè)子集有k個(gè)元素(k=1,…,n),則在此子集中的另外k-1個(gè)元素將從n-1個(gè)元素中選取。然后對剩下的n-k個(gè)元素進(jìn)行劃分。故有,16.,,,,,15,3,5,,,,,,,,12,6,2,3,1,,,,54,27,9,3,,17.,(1)最(極)大元x1,無最小元;(2)上界下界上確界下確界{x2,x3,x4}x1x4x1x4{x3,x4,x5}x1,x3無x3無{x1,x2,x3}x1x4x1x4,18.,(2)題16中的,子集{3,5}無最大元;(3)題16中的,子集{2,3,6}有下確界但無最小元;(4)題16中的,子集{1}有上界2,3,6,12,但是無上確界。,19.,設(shè)為全序集,且|A|=n。,因此,B中必有最小元a.故為良序集,20.,設(shè)B是A的非空有限集。若B中不存在極大(小)元,則對任何x∈B,則存在y∈B,使得x≤y(y≤x),如此下去,得出B為無限集.矛盾.故結(jié)論成立。,21.,設(shè)B是A上的一個(gè)非空有限集,由上題知,B中至少有一個(gè)極大(小)元。又因?yàn)槿蚣?故B的極大(小)元均唯一,且就是最大(小)元。,