離散數(shù)學(xué)習(xí)題集(十五套)

1、離散數(shù)學(xué)試題與答案試卷一3、設(shè)A=1，2，3，則A上的二元關(guān)系有（ c ）個(gè)。 A 23 ； B 32 ； C ； D 。5、設(shè)A=1，2，3，4，P（A）（A的冪集）上規(guī)定二元系如下則P（A）/ R=（ d ）AA ；BP(A) ；C1，1，2，1，2，3，1，2，3，4；D，2，2，3，2，3，4，A試卷二試題與答案1、 設(shè)S=a1 ，a2 ，a8，Bi是S的子集，則由B31所表達(dá)的子集是6、設(shè) 為普通加法和乘法，則（ a ）是域。A BC D= N 。1、 設(shè)R是A上一個(gè)二元關(guān)系，試證明若R是A上一個(gè)等價(jià)關(guān)系，則S也是A上的一個(gè)等價(jià)關(guān)系。（9分）一、 證明 46%1、（9分）（1） S自

2、反的，由R自反，（2） S對(duì)稱(chēng)的（3） S傳遞的由（1）、（2）、（3）得；S是等價(jià)關(guān)系。試卷三試題與答案一、 選擇 20% （每小題 2分）1、 設(shè)R和S是P上的關(guān)系，P是所有人的集合，則表示關(guān)系 （ a ）。A、；B、；C、 ； D、。試卷四試題與答案一、 選擇 25% （每小題 2.5分）1、 公式的解釋I為：個(gè)體域D=2，P(x)：x>3, Q(x)：x=4則A的真值為（ a ）。A、1； B、0； C、可滿足式； D、無(wú)法判定。2、 下列等價(jià)關(guān)系正確的是（ b ）。A、；B、；C、；D、。3、 下列推理步驟錯(cuò)在（ d ）。PUSPESTIEGA、；B、；C、；D、1、 五、謂詞

3、邏輯推理 15%符號(hào)化語(yǔ)句：“有些人喜歡所有的花，但是人們不喜歡雜草，那么花不是雜草”。并推證其結(jié)論。五、謂詞邏輯推理 15%解： 證明：PESTITIPUSTITEUSUSTIUG試卷五試題與答案試卷六試題與答案一、 填空 15% （每小題 3分）1、 設(shè)n階圖G中有m條邊，每個(gè)結(jié)點(diǎn)的度數(shù)不是k的是k+1，若G中有Nk個(gè)k度頂點(diǎn)，Nk+1個(gè)k+1度頂點(diǎn)，則N k = n(k+1)-2m 。試卷七試題與答案一、 填空 15% （每小題 3分）1. 已知一棵無(wú)向樹(shù)T有三個(gè)3頂點(diǎn),一個(gè)2度頂點(diǎn),其余的都是1度頂點(diǎn),則T中有 5 個(gè)1度頂點(diǎn)。試卷八試題與答案試卷九試題與答案一、 選擇 20% （每小

4、題 2分）1、 設(shè)S=N，Q，R，下列命題正確的是（ c ）。A、； B、；C、； D、。2、 下列語(yǔ)句不是命題的有（ ae ）。A、 x=13； B、離散數(shù)學(xué)是計(jì)算機(jī)系的一門(mén)必修課； C、雞有三只腳；D、太陽(yáng)系以外的星球上有生物； E、你打算考碩士研究生嗎？3、 下列關(guān)系中能構(gòu)成函數(shù)的是（ b ）。A、；B、；C、； D、。10、N是自然數(shù)集，定義（即x除以3的余數(shù)），則f是（ d ）。A、滿射不是單射；B、單射不是滿射；C、雙射；D、不是單射也不是滿射。試卷十試題與答案一、 填空 10% （每小題 2分）1、 若P，Q為二命題，真值為1，當(dāng)且僅當(dāng) 。2、 對(duì)公式中自由變?cè)M(jìn)行代入的公式為

5、。3、 的前束范式為 。4、 設(shè)x是謂詞合式公式A的一個(gè)客體變?cè)珹的論域?yàn)镈，A（x）關(guān)于y的自由的，則 被稱(chēng)為全稱(chēng)量詞消去規(guī)則，記為US。5、 與非門(mén)的邏輯網(wǎng)絡(luò)為 。二、 選擇 30% （每小題 3分）1、 下列各符號(hào)串，不是合式公式的有（ ）。A、； B、；C、； D、。2、 下列語(yǔ)句是命題的有（ ）。A、2是素?cái)?shù)；B、x+5 > 6；C、地球外的星球上也有人；D、這朵花多好看呀！。3、 下列公式是重言式的有（ ）。A、；B、；C、；D、4、 下列問(wèn)題成立的有（ ）。A、 若，則； B、若，則；C、若，則； D、若，則。5、 命題邏輯演繹的CP規(guī)則為（ ）。A、 在推演過(guò)程中可隨便

6、使用前提；B、在推演過(guò)程中可隨便使用前面演繹出的某些公式的邏輯結(jié)果；C、如果要演繹出的公式為形式，那么將B作為前提，設(shè)法演繹出C；D、設(shè)是含公式A的命題公式，則可用B替換中的A。6、 命題“有的人喜歡所有的花”的邏輯符號(hào)化為（ ）。設(shè)D：全總個(gè)體域，F(xiàn)（x）：x是花，M(x) ：x是人，H(x,y)：x喜歡y A、；B、；C、；D、。7、 公式換名（ ）。A、；B、；C、；D、。8、 給定公式，當(dāng)D=a,b時(shí)，解釋?zhuān)?）使該公式真值為0。A、P(a)=0、P(b)=0；B、P(a)=0、P(b)=1；C、P(a)=1、P(b)=0；D、P(a)=1、P(b)=19、 下面蘊(yùn)涵關(guān)系成立的是（ ）

7、。A、；B、；C、；D、。10、下列推理步驟錯(cuò)在（ ）。PUSESUGEGA、；B、；C、；D、。三、 邏輯判斷 28%1、（8分）下列命題相容嗎？2、（10分）用范式方法判斷公式 是否等價(jià)。3、（10分）下列前提下結(jié)論是否有效？今天或者天晴或者下雨。如果天晴，我去看電影；若我去看電影，我就不看書(shū)。故我在看書(shū)時(shí)，說(shuō)明今天下雨。四、 計(jì)算 12%1、（5分）給定3個(gè)命題：P：北京比天津人口多；Q：2大于1；R：15是素?cái)?shù)。 求復(fù)合命題：的真值。2、（7分）給定解釋I：D=2，3，L（x,y）為L(zhǎng)( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) = L (3 ,

8、2 )=0 ,求謂詞合式公式的真值。五、 邏輯推理20%1、（10分）所有有理數(shù)是實(shí)數(shù)，某些有理數(shù)是整數(shù)，因此某些實(shí)數(shù)是整數(shù)。2、（10分）符號(hào)化語(yǔ)句：“有些病人相信所有的醫(yī)生，但是病人都不相信騙子，所以醫(yī)生都不是騙子”。并推證其結(jié)論。答案二、 填空 15%（每小題3分）1、P，Q的真值相同；2、；3、；4、；5、。三、 選擇 30%（每小題 3分）題目12345678910答案B、CA、CBC、DCDAB、CB、DC四、 邏輯判斷 28%1、（8分）PAPBTIPTETIFTI所以不相容。2、（10分）所以?xún)墒降葍r(jià)。3、設(shè)P：今天天晴，Q：今天下雨，R：我不看書(shū)，S：我看電影符號(hào)化為：PPT

9、ITIPTETI結(jié)論有效。五、 計(jì)算 12%1、（5分）解：P，Q是真命題，R是假命題。2、（7分）六、 邏輯推理 20%1、（10分）解：設(shè)R(x)：x是實(shí)數(shù)，Q(x)：x是有理數(shù)，I(x)：x是整數(shù)符號(hào)化：前提：，結(jié)論：PESPUSTITITITIEG2、解：F(x)：x是病人，G(x)：x是醫(yī)生，H(x)：x是騙子，L(x,y)：x相信y符號(hào)化：前提：結(jié)論：PESTITIPUSTITEUSUSTIUG卷十一試題與答案一、 填空 20% （每小題 2分）1、 稱(chēng)為命題。2、命題PQ的真值為0，當(dāng)且僅當(dāng) 。3、一個(gè)命題含有4個(gè)原子命題，則對(duì)其所有可能賦值有 種。4、所有小項(xiàng)的析取式為 。5、

10、令P（x）：x是質(zhì)數(shù)，E（x）：x是偶數(shù)，Q（x）：x是奇數(shù)，D（x，y）：x除盡y. 則的漢語(yǔ)翻譯為 。6、設(shè)S=a，b, c 則S6的集合表示為 。7、P（P()）= 。8、= 。9、設(shè)R為集合A上的關(guān)系，則t（R）= 。10、若R 是集合A上的偏序關(guān)系，則R滿足 。二、 選擇 20% （每小題 2分）1、 下列命題正確的有（ ）。A、 若是滿射，則是滿射； B、若是滿射，則都是滿射；C、若是單射，則都是單射；D、若單射，則是單射。2、 設(shè)f，g是函數(shù)，當(dāng)（ ）時(shí)，f=g 。A、； B、；C、； D、。3、 下列關(guān)系，（ ）能構(gòu)成函數(shù)。A、；B、；C、； D、。4、 下列函數(shù)（ ）滿射；（

11、 ）單射；（ ）雙射（ ）；一般函數(shù)（ ）。A、； B、（除以3的余數(shù)）；C、；D、。5、 集合A=1，2，3，4上的偏序關(guān)系為，則它的Hass圖為（ ）。6、 設(shè)集合A=1，2，3，4，5上偏序關(guān)系的Hass圖為則子集B=2，3，4的最大元（ ）；最小元（ ）；極大元（ ）；極小元（ ）；上界（ ）；上確界（ ）；下界（ ）；下確界（ ）。A、 無(wú)，4，2、3，4，1，1，4，4； B、無(wú)，4、5，2、3，4、5，1，1，4，4；C、無(wú)，4，2、3，4、5，1，1，4，4； D、無(wú)，4，2、3，4，1，1，4，無(wú)。7、 設(shè)R，S是集合A上的關(guān)系，則下列（ ）斷言是正確的。A、 自反的，則是自

12、反的；B、若對(duì)稱(chēng)的，則是對(duì)稱(chēng)的；C、若傳遞的，則是傳遞的；D、若反對(duì)稱(chēng)的，則是反對(duì)稱(chēng)的8、 設(shè)X為集合，|X|=n，在X上有（ ）種不同的關(guān)系。A、n2； B、2n； C、； D、。9、 下列推導(dǎo)錯(cuò)在（ ）。PUSESUGA、； B、； C、； D、無(wú)。10、“沒(méi)有不犯錯(cuò)誤的人”的邏輯符號(hào)化為（ ）。設(shè)H（x）：x是人， P（x）：x犯錯(cuò)誤。A、； B、；C、； D、。三、 命題演繹28% 1、（10分）用反證法證明。2、（8分）用CP規(guī)則證明。3、（10分）演繹推理：所有的有理數(shù)都是實(shí)數(shù)，所有的無(wú)理數(shù)也是實(shí)數(shù)，虛數(shù)不是實(shí)數(shù)。因此，虛數(shù)既不是有理數(shù)，也不是無(wú)理數(shù)。四、 8% 將化為與其等價(jià)的前

13、束范式。五、8%A=a,b,c,d，R=<a,b>,<b,c>,<b,d>,<c,b>為A上的關(guān)系，利用矩陣乘法求R的傳遞閉包，并畫(huà)出t（R）的關(guān)系圖。六、證明16%1、 （8分）設(shè)A=1，2，3，4，在 P（A）上規(guī)定二元關(guān)系如下： P（A）證明R是P（A）上的等價(jià)關(guān)系并寫(xiě)出商集P（A）/R。2、 （8分）設(shè)f是A到A的滿射，且，證明f=IA 。答案一、 填空 20%（每小題2分）1、 能夠斷真假的陣述句；2、P的真值為1，Q的真值為0；3、24=16；4、永真式；5、任意兩數(shù)x、y,如果x是偶數(shù)且能除盡y，則y一定是偶數(shù)；6、S110=a,b

14、；7、；8、；9、；10、自反性、反對(duì)稱(chēng)性、傳遞性二、選擇 20%（每小題 2分）題目12345678910答案A、DBC、DC、D；A、D；D；BCAADCB、D三、命題演繹 28%1、（10分）證明：P（附加前提）TEPTEPTETETITIPTETETI2、（8分）P（附加前提）PTIPTITECP3、證明：設(shè)Q（x）：x是有理數(shù)，R(x)：x是實(shí)數(shù)，N(x)：x是無(wú)理數(shù)， C(x)：x是虛數(shù)。前提： 結(jié)論：PUSPUSPUSTETITITITEUG四、 8%解：五、8%解：所以t（R）=<a,b>,<a,c>,<a,d>,<b,b>,&l

15、t;b,c>,<b,d>,<c,b>,<c,c>,<c,d>關(guān)系圖為六、證明16%1、（8分）證明：P（A），由于，所以，即R自反的。P（A），若，則，R是對(duì)稱(chēng)的。P（A），若：，即： 所以R是傳遞的。由知，R是等價(jià)關(guān)系。P（A）/R = R，1R，1，2R，1，2，3R，1，2，3，4R2、（8分）證明：因?yàn)閒是滿射，所以，存在使得，又因?yàn)閒是函數(shù)，所以 即 由 所以，又，所以 由a的任意性知：f=IA 。卷十二試題與答案五、 填空 20% （每空 2分）1、 設(shè)集合A=1，2，3，4，5，6，7，8，9，10，定義A上的二元關(guān)系“”為x

16、 y = x|y , 則= 。2、 設(shè)，定義A上的二元運(yùn)算為普通乘法、除法和加法，則代數(shù)系統(tǒng)<A,*>中運(yùn)算*關(guān)于 運(yùn)算具有封閉性。3、 設(shè)集合S=，S上的運(yùn)算*定義為*則代數(shù)系統(tǒng)<S，*>中幺元是 ，左逆元是 ，無(wú)左逆元的元素是 。4、 在群坯、半群、獨(dú)異點(diǎn)、群中 滿足消去律。5、 設(shè)<G,*>是由元素生成的循環(huán)群，且|G|=n，則G = 。6、 拉格朗日定理說(shuō)明若<H , *>是群<G,*>的子群，則可建立G中的等價(jià)關(guān)系R= 。若|G|=n, |H|=m 則m和n關(guān)系為 。7、 設(shè)f是由群<G,>到群<,*>

17、;的同態(tài)映射，是中的幺元，則f的同態(tài)核Ker(f )= 。六、 選擇 20% （每小題 2分）1、設(shè)f是由群<G,>到群<,*>的同態(tài)映射，則ker (f)是（ ）。A、的子群； B、G的子群 ； C、包含； D、包含G。2、設(shè) <A ，+ ，·>是環(huán)，a·b的關(guān)于“+”的逆元是（ ）。A、(-a)·(-b)； B、(-a)·b； C、a·(-b)； D、a·b 。3、設(shè) <A ，+ ，·>是一代數(shù)系統(tǒng)且<A ，+ >是Abel群，如果還滿足（ ）<A ，+

18、，·>是域。A、<A ，·>是獨(dú)異點(diǎn)且·對(duì)+可分配；B、<A- ，·>是獨(dú)異點(diǎn)，無(wú)零因子且·對(duì)+可分配；C、<A- ，·>是Abel群且無(wú)零因子 ；D、<A- ，·>是Abel且·對(duì)+可分配。4、設(shè)<A ，+ ，·>是一代數(shù)系統(tǒng)，+、·為普通加法和乘法運(yùn)算，當(dāng)A為（ ）時(shí)，<A ，+ ，·>是域。A、 ；B、；C、 ； D、。5、設(shè)<A, >是一個(gè)格，由格誘導(dǎo)的代數(shù)系統(tǒng)為，則（ ）成立。A、；B、

19、；C、 ；D、。6、設(shè)<A, >是偏序集，“”定義為：，則當(dāng)A=（ ）時(shí)，<A, >是格。A、1,2,3,4,6,12； B、1,2,3,4,6,8,12,14； C、1,2,3,，12； D、1,2,3,4。7、設(shè)是由格<A, >誘導(dǎo)的代數(shù)系統(tǒng)，若對(duì)，當(dāng)時(shí)，有（ ）<A, >是模格。A、； B、；C、； D、。8、在（ ）中，補(bǔ)元是唯一的。A、有界格； B、有補(bǔ)格； C、分配格； D、有補(bǔ)分配格。9、在布爾代數(shù)中，當(dāng)且僅當(dāng)（ ）。A、； B、； C、； D、。10、設(shè)是布爾代數(shù)，f是從An到A的函數(shù)，則（ ） 。A、 f是布爾代數(shù)； B、f能表

20、示成析取范式，也能表示成合取范式；C、若A=0，1，則f一定能表示成析取范式，也能表示成合取范式；D、若f是布爾函數(shù)，它一定能表示成析（合）取范式。三、8%設(shè)A=1，2，A上所有函數(shù)的集合記為AA, 是函數(shù)的復(fù)合運(yùn)算，試給出AA上運(yùn)算的運(yùn)算表，并指出AA中是否有幺元，哪些元素有逆元。四、證明42%1、 設(shè)<R,*>是一個(gè)代數(shù)系統(tǒng)，*是R上二元運(yùn)算，則0是幺元且<R,*>是獨(dú)異點(diǎn)。（8分）2、 設(shè)<G,*>是n階循環(huán)群，G=(a)，設(shè)b=ak，則 元素b的階為，這里d=GCD ( n , k )。（10分）3、 證明如果f是由<A,>到<B,

21、*>的同態(tài)映射，g是由<B,*>到<C,>的同態(tài)映射，則是由<A,>到<C,>的同態(tài)映射。（6分）4、 設(shè)<A ，+ ，·>是一個(gè)含幺環(huán)，且任意都有a·a=a，若|A|3則<A ，+ ，·>不可能是整環(huán)。（8分）5、 K= 1, 2 , 5 , 10 , 11 , 22 , 55 ,110 是110的所有整因子的集合，證明：具有全上界110和全下界1的代數(shù)系統(tǒng)< K , LCM , GCD , >是一個(gè)布爾代數(shù)。（）。（10分）五、布爾表達(dá)式 10%設(shè)是布爾代數(shù)上的一個(gè)布爾表

22、達(dá)式，試寫(xiě)出其析取范式和合取范式。（10分）答案：一、填空 20%（每空2分）1、LCM（x,y）；2、乘法；3、，、；4、群；5、；6、；7、二、選擇 20%（每小題 2分）題目12345678910答案BB，CDABAADCC，D三、8%解：因?yàn)閨A|=2，所以A上共有22=4個(gè)不同函數(shù)。令，其中：為AA中的幺元，和有逆元。四、證明 42%1、（8分）證明：幺 ，即 乘 ，由于+，·在R封閉。所以即*在R上封閉。群 因此 ， R，*是獨(dú)異點(diǎn)。2、（10分）證明：（1）（2）若b的階不為n1，則b階m<n1，且有，則有，即，即，有因子，這與矛盾。由（1）、（2）知，元素b的階

23、為3、（6分）所以是由<A,>到<c,>的同態(tài)映射。4、（8分）證明：反證法：如果<A ，+ ，·>是整環(huán)，且|A|3，則且即有且，這與整環(huán)中無(wú)零因子矛盾。所以<A ，+ ，·>不可能是整環(huán)。5、（10分）（1） 代數(shù)系統(tǒng)<K , LCM , GCD, > 是由格<K , | >誘導(dǎo)的，其Hasst圖為Hass圖中不存在與五元素格和同構(gòu)的子格。所以<K,|>格是分配格。（2）即任元素都有補(bǔ)元，所以<K,|>有補(bǔ)格。<K , LCM , GCD,>是布爾代數(shù)。五、布爾表

24、達(dá)式 10%解：函數(shù)表為：00000011010101111001101111011110析取范式：合取范式：試卷十三試題與答案七、 填空 10% （每小題 2分）1、，*表示求兩數(shù)的最小公倍數(shù)的運(yùn)算（Z表示整數(shù)集合），對(duì)于*運(yùn)算的幺元是 ，零元是 。2、代數(shù)系統(tǒng)<A,*>中，|A|>1，如果分別為<A,*>的幺元和零元，則的關(guān)系為 。3、設(shè)<G,*>是一個(gè)群，<G,*>是阿貝爾群的充要條件是 。4、圖的完全關(guān)聯(lián)矩陣為 。5、一個(gè)圖是平面圖的充要條件是 。八、 選擇 10% （每小題 2分）1、 下面各集合都是N的子集，（ ）集合在普通加法

25、運(yùn)算下是封閉的。A、x | x 的冪可以被16整除； B、x | x 與5互質(zhì)；C、x | x是30的因子； D、x | x是30的倍數(shù)。2、 設(shè)，其中表示模3加法，*表示模2乘法，則積代數(shù)的幺元是（ ）。A、<0,0>； B、<0,1>； C、<1,0>； D、<1,1> 。3、 設(shè)集合S=1,2,3,6，“”為整除關(guān)系，則代數(shù)系統(tǒng)< S , >是（ ）。A、域； B、格，但不是布爾代數(shù)； C、布爾代數(shù)； D、不是代數(shù)系統(tǒng)。4、 設(shè)n階圖G有m條邊，每個(gè)結(jié)點(diǎn)度數(shù)不是k就是k+1，若G中有Nk個(gè)k度結(jié)點(diǎn)，則Nk=（ ）。A、n

26、3;k； B、n(k+1)； C、n(k+1)-m； D、n(k+1)-2m 。5、 一棵樹(shù)有7片樹(shù)葉，3個(gè)3度結(jié)點(diǎn)，其余全是4度結(jié)點(diǎn)，則該樹(shù)有（ ）個(gè)4度結(jié)點(diǎn)。A、1； B、2； C、3； D、4 。三、判斷10% （每小題 2分）1、（ ）設(shè)S=1,2，則S在普通加法和乘法運(yùn)算下都不封閉。2、（ ）在布爾格<A,>中，對(duì)A中任意原子a，和另一非零元b，在或中有且僅有一個(gè)成立。3、（ ）設(shè)，+,·為普通加法和乘法，則<S，+，·>是域。4、（ ）一條回路和任何一棵生成樹(shù)至少有一條公共邊。5、（ ）沒(méi)T是一棵m叉樹(shù)，它有t片樹(shù)葉，i個(gè)分枝點(diǎn)，則(m-

27、1)i = t-1。四、證明 38%1、（8分）對(duì)代數(shù)系統(tǒng)<A,*>，*是A上二元運(yùn)算，e為A中幺元，如果*是可結(jié)合的且每個(gè)元素都有右逆元，則（1）<A,*>中的每個(gè)元素在右逆元必定也是左逆元。（2）每個(gè)元素的逆元是唯一的。2、（12分）設(shè)是一個(gè)布爾代數(shù)，如果在A上定義二元運(yùn)算，為，則<A,>是一阿貝爾群。3、（10分）證明任一環(huán)的同態(tài)象也是一環(huán)。4、（8分）若是每一個(gè)面至少由k(k3)條邊圍成的連通平面圖，則。五、應(yīng)用 32%1、 （8分）某年級(jí)共有9門(mén)選修課程，期末考試前必須提前將這9門(mén)課程考完，每人每天只在下午考一門(mén)課，若以課程表示結(jié)點(diǎn)，有一人同時(shí)選兩

28、門(mén)課程，則這兩點(diǎn)間有邊（其圖如右），問(wèn)至少需幾天？2、 用washall方法求圖的可達(dá)矩陣，并判斷圖的連通性。（8分）3、 設(shè)有a、b、c、d、e、f、g七個(gè)人，他們分別會(huì)講的語(yǔ)言如下：a：英，b：漢、英，c：英、西班牙、俄，d：日、漢，e：德、西班牙，f：法、日、俄，g：法、德，能否將這七個(gè)人的座位安排在圓桌旁，使得每個(gè)人均能與他旁邊的人交談？（8分）4、 用 Huffman算法求出帶權(quán)為2，3，5，7，8，9的最優(yōu)二叉樹(shù)T，并求W（T）。若傳遞a ，b， c， d ，e， f 的頻率分別為2%， 3% ，5 %， 7% ，8% ，9%求傳輸它的最佳前綴碼。（8分）答案：七、 填空 10%（

29、每小題2分）1、1， 不存在；2、；3、有；4、11100-100010-101-100-1-105、它不包含與K3, 3或K5在2度結(jié)點(diǎn)內(nèi)同構(gòu)的子圖。八、 選擇 10%（每小題 2分）題目12345答案A，DBCDA九、 判斷 10%題目12345答案YYNNN十、 證明 38%1、（8分）證明：（1）設(shè)，b是a的右逆元，c是b的右逆元，由于，所以b是a的左逆元。（2）設(shè)元素a有兩個(gè)逆元b、c，那么a的逆元是唯一的。2、（12分）證明：乘 運(yùn)算在A上也封閉。群 即滿足結(jié)合性。幺 ,故全下界0是A中關(guān)于運(yùn)算的幺元。逆 ,即A中的每一個(gè)元素以其自身為逆元。交 即運(yùn)算具有可交換性。所以<A,

30、 >是Abel群。3、(10分) 證明:設(shè)是一環(huán),且是關(guān)于同態(tài)映射f的同態(tài)象。由是Abel群，易證也是Abel群。是半群，易證也是半群?，F(xiàn)只需證：對(duì)是可分配的。 于是同理可證因此也是環(huán)。5、（8分）證明：設(shè)G有r個(gè)面， 。十一、 應(yīng)用32%1、（8分）解：即為最少考試天數(shù)。用Welch-Powell方法對(duì)G著色：第一種顏色的點(diǎn) ，剩余點(diǎn)第二種顏色的點(diǎn) ，剩余點(diǎn)第三種顏色的點(diǎn) 所以3任構(gòu)成一圈，所以3故=3所以三天下午即可考完全部九門(mén)課程。2、（8分）解：1：A2，1=1，； 2： A4，2=1，3： A1，3=A2，3=A4，3=1，4： Ak，4=1，k=1，2，3，4，p中的各元素全

31、為1，所以G是強(qiáng)連通圖，當(dāng)然是單向連通和弱連通。3、（8分）解：用a,b,c,d,e,f,g 7個(gè)結(jié)點(diǎn)表示7個(gè)人，若兩人能交談可用一條無(wú)向邊連結(jié)，所得無(wú)向圖為此圖中的Hamilton回路即是圓桌安排座位的順序。Hamilton回路為a b d f g e c a。4、（8分）解：(1)（1） 用0000傳輸a、0001傳輸b、001傳輸c、01傳輸f、10傳輸d、11傳輸e傳輸它們的最優(yōu)前綴碼為0000，0001，001，01，10，11 。試卷十四試題與答案九、 填空 10% （每小題 2分）1、 設(shè)是由有限布爾格誘導(dǎo)的代數(shù)系統(tǒng)，S是布爾格，中所有原子的集合，則 。2、 集合S=，上的二元運(yùn)

32、算*為*那么，代數(shù)系統(tǒng)<S, *>中的幺元是 , 的逆元是 。3、 設(shè)I是整數(shù)集合，Z3是由模3的同余類(lèi)組成的同余類(lèi)集，在Z3上定義+3如下：，則+3的運(yùn)算表為 ；<Z+,+3>是否構(gòu)成群 。4、 設(shè)G是n階完全圖，則G的邊數(shù)m= 。5、 如果有一臺(tái)計(jì)算機(jī)，它有一條加法指令，可計(jì)算四數(shù)的和?，F(xiàn)有28個(gè)數(shù)需要計(jì)算和，它至少要執(zhí)行 次這個(gè)加法指令。十、 選擇 20% （每小題 2分）1、 在有理數(shù)集Q上定義的二元運(yùn)算*，有，則Q中滿足（ ）。A、 所有元素都有逆元； B、只有唯一逆元； C、時(shí)有逆元； D、所有元素都無(wú)逆元。2、 設(shè)S=0，1，*為普通乘法，則< S

33、, * >是（ ）。A、 半群，但不是獨(dú)異點(diǎn)； B、只是獨(dú)異點(diǎn)，但不是群；C、群； D、環(huán)，但不是群。3、圖 給出一個(gè)格L，則L是（ ）。A、分配格； B、有補(bǔ)格； C、布爾格； D、 A,B,C都不對(duì)。3、 有向圖D=<V , E> ，則長(zhǎng)度為2的通路有（ ）條。A、0； B、1； C、2； D、3 。4、 在Peterson圖中，至少填加（ ）條邊才能構(gòu)成Euler圖。A、1； B、2； C、4； D、5 。十一、 判斷 10% （每小題 2分）1、 在代數(shù)系統(tǒng)<A,*>中如果元素的左逆元存在，則它一定唯一且。（ ）2、 設(shè)<S,*>是群<G

34、,*>的子群，則<G,*>中幺元e是<S,*>中幺元。（ ）3、 設(shè)， +,·為普通加法和乘法，則代數(shù)系統(tǒng)<A，+，·>是域。（ ）4、 設(shè)G=<V ,E >是平面圖，|V|=v, |E|=e，r為其面數(shù)，則v-e + r=2。（ ）5、 如果一個(gè)有向圖D是歐拉圖，則D是強(qiáng)連通圖。（ ）四、證明 46%1、 設(shè)<A,*>，是半群，e是左幺元且，使得，則<A , *>是群。（10分）2、 循環(huán)群的任何非平凡子群也是循環(huán)群。（10分）3、 設(shè)aH和bH是子群H在群G中的兩個(gè)左陪集，證明：要末，要末 。

35、（8分）4、 設(shè)<A ,+ ,·>，是一個(gè)含幺環(huán)，|A|>3，且對(duì)任意，都有，則<A ,+ ,·>不可能是整環(huán)（這時(shí)稱(chēng)<A，+，·>是布爾環(huán)）。（8分）5、 若圖G不連通，則G的補(bǔ)圖是連通的。（10分）五、布爾表達(dá)式 8%設(shè)是布爾代數(shù)上的一個(gè)布爾表達(dá)式，試寫(xiě)出其的析取范式和合取范式。六、圖的應(yīng)用 16%1、 構(gòu)造一個(gè)結(jié)點(diǎn)v與邊數(shù)e奇偶性相反的歐拉圖。（6分）2、 假設(shè)英文字母，a，e，h，n，p，r，w，y出現(xiàn)的頻率分別為12%，8%，15%，7%，6%，10%，5%，10%，求傳輸它們的最佳前綴碼，并給出happy ne

36、w year的編碼信息。（10分）答案十二、 填空 10%（每小題2分）+30120012112022011、<P (S), >；2、，；3、 是；4、；5、9十三、 選擇 10%（每小題 2分）題目12345答案CBDBD十四、 判斷 10%（每小題2分）題目12345答案NYYNY十五、 證明 46%1、（10分）證明：（1）(2) e 是<A，*>之幺元。事實(shí)上：由于e是左幺元，現(xiàn)證e是右幺元。（3）由（2），（3）知：<A,*>為群。2、（10分）證明：設(shè)<G,*>是循環(huán)群,G=(a)，設(shè)<S,*>是<G,*>的子

37、群。且，則存在最小正整數(shù)m，使得：，對(duì)任意，必有，故： 即：所以但m是使的最小正整數(shù)，且，所以r=0即：這說(shuō)明S中任意元素是的乘冪。 所以<G,*>是以為生成元的循環(huán)群。3、（8分）證明：對(duì)集合，只有下列兩種情況：（1）； （2）對(duì)于，則至少存在，使得，即有，這時(shí)任意，有，故有同理可證：所以 4、（8分）證明：反證法：如果<A，+，·>，是整環(huán)，且有三個(gè)以上元素，則存在即有：這與整環(huán)中無(wú)零因子條件矛盾。因此<A，+，·>不可能是整環(huán)。5、（10分）證明：因?yàn)镚=< V，E>不連通，設(shè)其連通分支是，則有兩種情況：（1） u ,

38、v，分別屬于兩個(gè)不同結(jié)點(diǎn)子集Vi，Vj，由于G(Vi) , G(Vj)是兩連通分支，故(u , v)在不G中，故u , v 在中連通。（2） u ,v ，屬于同一個(gè)結(jié)點(diǎn)子集Vi，可在另一結(jié)點(diǎn)子集Vj中任取一點(diǎn)w，故(u , w),(w , v )均在中，故鄰接邊( u ,w ) ( w , v ) 組成的路連接結(jié)點(diǎn)u和v，即u , v在中也是連通的。五、布爾表達(dá)式 8%函數(shù)表為：00000011010001111000101111011111析取范式：合取范式：六、 樹(shù)的應(yīng)用 16%1、（6分）解：2、（10分）解：根據(jù)權(quán)數(shù)構(gòu)造最優(yōu)二叉樹(shù)：傳輸它們的最佳前綴碼如上圖所示，happy new year的編碼信息為：10 011 0101 0101 001 110 111 0100 001 111 011 000 附：最優(yōu)二叉樹(shù)求解過(guò)程如下：試卷十五試題與答案十二、 填空 20% （每空 2分）1、 如果有限集合A有n個(gè)元素，則|2A|= 。2、 某集合有101個(gè)元素，則有 個(gè)子集的元素為奇數(shù)。3、 設(shè)S=a1，a2,，a8，Bi是S的子集，由B17表達(dá)的子集為 ， 子集a2,a6,a7規(guī)定為 。4、 由A1，A2,，An，生成的最小集的形式為 ，它們的并為 集