離散數(shù)學(劉任任版)第2章答案.ppt

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

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