離散數(shù)學(xué)題庫

《離散數(shù)學(xué)題庫》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)題庫（18頁珍藏版）》請在裝配圖網(wǎng)上搜索。

試題總匯 數(shù)理邏輯部分 1、判斷下列句子中哪些是命題 （1）2是素數(shù) （2）血是黑色的 （3）2+3=5 （4）明年10月1日是晴天 （5）3能被2整除 （6）這朵花多好看呀！ （7）明天下午有會嗎？ （8）請關(guān)上門！ （9）X + y > 5 （10）地球外的星球上也有人 2、將下列命題符號化 （1）3不是偶數(shù) （2）2是素數(shù)和偶數(shù) （3）李芳學(xué)過英語或日語 （4）如果角A和角B是對頂角，則角A等于角B （5）李平雖然聰明，但不用功 （6）李平不但聰明，而且用功 （7）小王是游泳冠軍或者百米賽跑冠軍 （8）小王現(xiàn)在在宿舍或者在圖書館 （9）選小王或者小李中的一人當(dāng)班長 （10）如果我上街，我就去書店看看，除非我很累 （11）如果明天天氣好，我們?nèi)ソ加?。否則，不去郊游 （12）你愛我，我就嫁給你 3、判斷下列命題公式是否等值 （1）（p∨q）與p∨q （2）（p∨q）與p∧q 4、驗證下列等值式 （1）p→（q→r）（ p∧q）→r （2）p（ p∧q）∨（p∧q） 5、用等值演算法解決下面問題： A、B、C、D 4人百米競賽。觀眾甲、乙、丙預(yù)報比賽的名次為， （1）甲：C第一，B第二。（2）乙：C第二，D第三。（3）丙：A第二，D第四。 比賽結(jié)束后發(fā)現(xiàn)甲、乙、丙每人報告的情況都是給對一半。試問，實際名次如何？ 6、求下面命題公式的主析取范式和主合取范式 （1）（（p∨q）→r）→p 7、利用真值表求主析取范式和主合取范式 （1）（p∧q）∨r 8、邏輯推理證明 （1）前提：p→r，q→s，p∨q。結(jié)論：r∨s。 （2）前提：p∨q，p→r，s→t，s→r，t。結(jié)論：q （3）前提：p→（q→r），s→p，q。結(jié)論：s→r。 （4）前提：p→（（r∧s）→q），p，s。結(jié)論：q 9、給定語句如下： （1）15是素數(shù) （2）10能被2整除，3是偶數(shù) （3）你下午有會嗎？ （4）2x+3> 0 （5）2是素數(shù)或是合數(shù) （6）這個男孩真勇敢呀！ （7）如果2+2=6，則5是奇數(shù) （8）只有4是偶數(shù)，3才能被2整除 （9）明年5月1日是晴天 （10）圓的面積等于半徑的平方與的乘積 以上10個語句中，是簡單命題的為A，是復(fù)合命題的為B，是真命題的為C，是假命題的為D，真值待定（真值客觀存在，只是現(xiàn)在不知道）的命題為E。 A：①（1）、（4）、（8）②（4）、（6）、（9）、（10）③（1）、（9）、（10） B：①（3）、（10）②（2）、（5）、（7）、（8）③（7）、（8） C：①（2）、（5）、（9）、（10）②（7）、（8）、（10）③（2）、（9）、（10）④（5）、（7）、（8）、（10） D：①（1）、（2）、（8）②（1）、（2）③（1）、（5） E：①（4）、（9）②（9）③（7）、（8） 10、判斷公式類型 （1）（p∧q）→（p∨q） （2）（pq）（（p→q）∧（q→p）） （3）（p→q）∧q （4）（p∧p）q （5）p→（p∨q） （6）（p∨p）→（（q∧q）∧r） （7）（（p→q）→p）p （8）（p∧q）∨（p∧q） （9）（p∨q ∨r）（p ∧q∧r） （10）（p∧q）∧r 11、給定命題公式如下：（p→q）→（p∨q） 該命題公式的主析取范式中含極小項的個數(shù)為A，主合取范式中含極大項的個數(shù)為B，成真賦值個數(shù)為C，成假賦值個數(shù)為D。 A、B、C、D：（1）0,（2）1,(3)2,(4)3,(5)4 12、一公安人員審查一件盜竊案，已知的事實如下： （1）甲或乙盜竊了錄音機(jī) （2）若甲盜竊了錄音機(jī)，則作案時間不能發(fā)生在午夜前 （3）若乙的證詞正確，則午夜時屋里燈光未滅 （4）若乙的證詞不正確，則作案時間發(fā)生在午夜前 （5）午夜時屋里燈光滅了 推理證明，誰盜竊了錄音機(jī)。 13、設(shè)p=1，q=0，r=1，s=0，有下列命題公式 （1）（p∧q）→（s∧r） （2）（p∧q∧r∧s）∨(s→q) （3）（p∧q∧r）（p∨s） 那么，（1）的真值為 ；（2）的真值為 ；（3）的真值為 ； 14、對于下面的語句， （1）只要4＜3，就有3＞2 （2）只要4＜3，就有3≤2 （3）只有4＜3，才有3＞2 （4）只有4＜3，才有3≤2 （5）除非4＜3，否則3＞2 （6）4≥3僅當(dāng)3≤2 （7）4＜3當(dāng)且僅當(dāng)3＞2 則，他們的真值是（1） （2） （3） （4） （5） （6） （7） 。 15、設(shè)A是含n個命題變項的公式，下面4個結(jié)論中，哪個是錯誤的？ （1）若A的主析取范式中含2n 個極小項，則A是重言式 （2）若A的主合取范式中含2n 個極大項，則A是矛盾式 （3）若A的主析取范式中不含任何極小項，則A的主析取范式為0 （4）若A的主合取范式中不含任何極大項，則A的主合取范式為0 16、已知命題公式A含有3個命題變項，其成真賦值為000，010，100，110。 則A的主析取范式為 ，主合取范式為 。 17、判斷下列語句是否為命題，如是命題請指出是簡單命題還是復(fù)合命題，并討論真值 （1）是無理數(shù) （2）5能被2整除 （3）現(xiàn)在開會嗎？ （4）x+5＞0 （5）這朵花真好看呀！ （6）2是素數(shù)當(dāng)且僅當(dāng)三角形有3條邊 （7）血是黑色的當(dāng)且僅當(dāng)太陽從東方升起 （8）2008年10月1日天氣晴朗 （9）太陽系以外的星球上有生物 （10）小李在宿舍里 （11）全體起立 （12）4是2的倍數(shù)或是3的倍數(shù) （13）4是偶數(shù)且是奇數(shù) （14）李明與王華是同學(xué) （15）藍(lán)色和黃色可以調(diào)配成綠色 18、將下列命題符號化，并討論其真值 （1）如果今天是1號，則明天是2號 （2）如果今天是1號，則明天是3號 19、設(shè)A、B、C為任意的命題公式 （1）已知 A∨CB∨C，問AB嗎？ （2）已知 A∧CB∧C，問AB嗎？ （3）已知 A B，問AB嗎？ 20、設(shè)計一個符合如下要求的室內(nèi)照明控制線路：在房間的門外、門內(nèi)及床頭分別裝有控制同一個電燈F的3個開關(guān)A、B、C。當(dāng)且僅當(dāng)一個開關(guān)的鍵向上或3個開關(guān)的鍵都向上時電燈亮。則F的邏輯關(guān)系式可化簡為 。 （1）A∨B∨C （2）A∨B∨C∨（A∧B∧C） （3）A∨B∨（A∧C） （4）C∨（A∧B） 21、將下列語句用謂詞表達(dá)式符號化 （1）2是素數(shù)且是偶數(shù) （2）如果2大于3，則2大于4 （3）凡是有理數(shù)均可表成分?jǐn)?shù) （4）有的有理數(shù)是整數(shù) （5）沒有不吃飯的人 （6）素數(shù)不全是奇數(shù) （7）一切人都不一樣高 （8）有的自然數(shù)無先驅(qū)數(shù) （9）有些人喜歡所有的花 （10）任何金屬都可以溶解在某種液體中 （11）凡是對頂角都相等 22、指出下列各合式公式中的指導(dǎo)變項、量詞的轄域、個體變項的自由出現(xiàn)和約束出現(xiàn) （1）x（F（x）→yH（x，y）） （2）x F（x）∧G（x，y） （3）xy（R（x，y）∨L（x，y））∧x H（x，y） 23、給定解釋I如下： 1）DI={2，3} 2）DI中特定元素a=2 3）函數(shù)f（x）為f（2）=3，f（3）=2 4）謂詞F（x）為F（2）=0，F(xiàn)（3）=1； G（x，y）為G（ i，j）=1，i，j=2，3； L（x，y）為L（ 2，2）= L（ 3，3）=1；L（ 2，3）= L（ 3，2）=0 在解釋I下，求下列各式的值。 （1）x（F（x）∧G（x，a）） （2）x（F（f（x））∧G（x，f（x））） （3）xy L（x，y） 24、求下列公式的前束范式 （1）xF（x）∧x G（x） （2）xF（x）∨x G（x） （3）xF（x）→x G（x） （4）xF（x）→x G（x） 25、設(shè)F（x）：x是人，G（x）：x愛吃糖。有人給出語句“不是所有人都愛吃糖”的4種謂詞表達(dá)式： （1）x（F（x）∧G（x）） （2）x（F（x）→G（x）） （3）x（F（x）∧G（x）） （4）x（F（x）∧G（x）） 正確的答案是 。 26、給出解釋I，使下面兩個公式在解釋I下均為假，從而說明這兩個公式都不是永真式 （1）x（F（x）∨G（x））→（xF（x）∨x G（x）） （2）（xF（x）∧x G（x））→x（F（x）∧G（x）） 27、取個體域為整數(shù)集，給定下列公式 （1）xy（x*y=0） （2）xy（x*y=1） （3）yx（x*y=2） （4）xy z（x – y = z） （5）x – y = - y + x （6）xy（x *y = y） （7）x（x*y = x） （8）xy（x + y = 2y） 在上面的公式中，真命題的為A，假命題的為B。 A：①（1）、（3）、（4）、（6）；②（3）、（4）、（5）； ③（1）、（3）、（4）、（5）；④（3）、（4）、（6）、（7） B：①（2）、（3）、（6）；②（2）、（6）、（8）； ③（1）、（2）、（6）、（7）；④（2）、（6）、（8）、（7） 集合部分 1、下列命題 （1）；（2）；（3）｛｝；（4）｛｝ 正確的是 ；錯誤的是 。 2、計算一下冪集 （1）P（）；（2）P（｛｝）；（3）P（｛，｛｝｝）；（4）P（｛1，｛2，3｝｝） 3、證明 （1）（A-B）∪B=A∪B； 4、化簡 （（A∪B∪C）∩（A∪B））- （（A∪（B - C））∩A 5、已知：AB=AC，證明：A = B 6、求在1到1000之間不能被5和6，也不能被8整除的數(shù)的個數(shù) 7、某班有25個學(xué)生，其中14人會打籃球，12人會打排球，6人會打籃球和排球，5人會打籃球和網(wǎng)球，還有2人會打這三種球。而6個會打網(wǎng)球的人都會打另一種球（指籃球或排球），求不會打這三種球的人數(shù)。 8、設(shè)F表示一年級大學(xué)生的集合，S表示二年級大學(xué)生的集合，R表示計算機(jī)科學(xué)系學(xué)生的集合，M表示數(shù)學(xué)系學(xué)生的集合，T表示選修離散數(shù)學(xué)的學(xué)生的集合，L表示愛好文學(xué)的學(xué)生的集合，P表示愛好體育運(yùn)動的學(xué)生的集合，則下列各句子所對應(yīng)的集合表達(dá)式分別是： （1）所有計算機(jī)科學(xué)系二年級的學(xué)生都選修離散數(shù)學(xué)。A （2）數(shù)學(xué)系的學(xué)生或者愛好文學(xué)或者愛好體育運(yùn)動。B （3）數(shù)學(xué)系一年級的學(xué)生都沒有選修離散數(shù)學(xué)。C （4）只有一、二年級的學(xué)生才愛好體育運(yùn)動。D （5）除去數(shù)學(xué)系和計算機(jī)科學(xué)系二年級的學(xué)生外都不選修離散數(shù)學(xué)。E A、B、C、D、E： ①T（M∪R）∩S；②R∩ST；③（M∩F）∩T =； ④ML∪P；⑤PF∪S；⑥S -（M∪R）P 9、設(shè)S1=｛1，2，…，8，9｝，S2=｛2，4，6，8｝，S3=｛1，3，5，7，9｝， S4=｛3，4，5｝，S5=｛3，5｝。確定在以下條件下X可能與S1,…,S5中哪個集合相等。 （1）若X∩S5 = ，則A （2）若XS4但X∩S2 = ，則B （3）若XS1但XS3，則C （4）若X - S3= ，則D （5）若XS3但XS1，則E A、B、C、D、E： ①X=S2或者S3；②X= S4或者S5；③X=S1，S2或者S4； ④X與其中任何集合都不等；⑤X=S2；⑥X=S5；⑦X=S3或者S5； ⑧X=S2或者S4； 10、設(shè)A、B、C為任意集合，判斷下述命題是否恒真，如果恒真給出證明，否則舉出反例。 （1）A∪B=A∪CB=C （2）AB=AB= （3）A∩（B - C）=（A∩B）-（A∩C） （4）（A∩B）∪（B - A）= B 11、設(shè)A、B為集合，試確定下列各式成立的充分必要條件： （1）A – B = B （2）A – B = B - A （3）A∪B = A∩B 12、求使得以下集合等式成立時，a，b，c，d應(yīng)該滿足的條件： （1）｛a，b｝=｛a，b，c｝ （2）｛a，b，a｝=｛a，b｝ （3）｛a，｛b，c｝｝=｛a，｛d｝｝ （4）｛｛a，b｝，｛c｝｝=｛｛b｝｝ （5）｛｛a，｝，b，｛c｝｝=｛｛｝｝ 13、計算A∩B、A∪B、A - B、AB （1）A=｛｛a，b｝，c｝，B=｛c，d｝ （2）A={{a，}，c，｛c｝，｛a，b｝}，B=｛｛a，b｝，c，｛b｝｝ （3）A=｛x|x∈N∧x<3｝，B=｛x|x∈N∧x≥2｝ （4）A=｛x|x∈R∧x<1｝，B=｛x|x∈Z∧x<1｝ （5）A=｛x|x∈Z∧x<0｝，B=｛x|x∈Z∧x≥2｝ 14、設(shè)|A|=3，|P（A）|=64，|P（A∪B）|=256， 求：|B|，|A∩B|，|A - B|，|AB| 15、設(shè)A=｛1，2｝，求：P（A）A 16、設(shè)A、B、C、D為任意集合，判斷以下等式是否成立，若成立給與證明，否則，舉出反例。 （1）（A∩B）（C∩D）=（A∩C）（B∩D） （2）（A∪B）（C∪D）=（A∪C）（B∪D） （3）（A - B）（C - D）=（A - C）（B - D） （4）（AB）（CD）=（AC）（BD） 17、設(shè)F、G是N上的關(guān)系，其定義為： F=｛|x，y∈N∧y =x2｝；G=｛|x，y∈N∧y =x+1｝； 求：G-1、FG、GF、F↑｛1，2｝、F[｛1，2｝] 18、設(shè)F=｛，<｛a｝，｛a，｛a｝｝>｝，求：FF，F(xiàn)↑｛a｝，F(xiàn)[｛a｝]。 19、設(shè)A=｛a，b，c，d｝，R=｛，，，｝。給出R、r（R）、s（R）、t（R）的關(guān)系圖。 20、設(shè)A=｛1，2，3｝，求出A上的所有的等價關(guān)系 21、設(shè)A=｛1，2，3，…，11，12｝，R為A上整除關(guān)系，畫出哈斯圖。 22、畫出的哈斯圖。 23、R是X上的二元關(guān)系，對于x∈X定義集合：R（x）={y|xRy} 顯然R（x） X。如果X={-4，-3，-2，-1，0，1，2，3，4}，且令 R1=｛|x，y∈X∧x< y｝， R2=｛|x，y∈X∧y -1< x< y +2｝， R3=｛|x，y∈X∧x2≤ y｝， 則下列集合滿足 （1）R1（0）=A （2）R2（0）=B （3）R3（3）=C （4）R1（1）=D （5）R2（-1）=E A、B、C、D、E： ①；②｛-4，-3，-2，-1｝；③｛-2，-1｝；④｛-1，0，1｝； ⑤｛-1，0｝；⑥｛1，2，3｝；⑦｛2，3，4｝；⑧｛0，1，2，3｝； ⑨｛1，2，3，4｝；⑩以上結(jié)果都不對 24、設(shè)S=｛1，2，3｝，定義SS上的等價關(guān)系R， ，∈SS有：～a + d = b + c 則由R產(chǎn)生了SS的一個劃分。在該劃分中共有A 個劃分塊， 其中最大的塊有B 個元素，并且含有元素C 。最小的劃分塊有D 塊，每塊含有E 個元素。 A、B、D、E： ①1；②2；③3；④4；⑤5；⑥6；⑦9； C： ⑧1；⑨<1，2>；⑩<2，2> 25、設(shè)S=｛0，1｝，F(xiàn)是S中的字符構(gòu)成的長度不超過4的串的集合，即 F=｛，0，1，00，01，… ，1111｝，其中表示空串。 在F上定義偏序關(guān)系R：x，y∈F， 有∈Rx 是y的前綴。 例如，00是001的前綴，但01不是001的前綴。 （1）偏序集的哈斯圖是A； （2）的極小元是B； （3）的最大元是C； （4）GF，G=｛101，1001｝，則G的最小上界是D ，最大下屆是E 。 A：①鏈；②樹；③既不是鏈，也不是樹； B、C、D、E： ④；⑤0；⑥0、1和；⑦不存在；⑧10；⑨1；⑩1111 26、設(shè)S=｛1，2｝，則S上可定義A 個不同的二元關(guān)系，其中B 個等價關(guān)系， C 個偏序關(guān)系，Is是D ，是E 。 A、B、C： ①1；②2；③3；④4；⑤8；⑥16； D、E： ⑦等價關(guān)系但不是偏序關(guān)系；⑧偏序關(guān)系但不是等價關(guān)系； ⑨等價關(guān)系和偏序關(guān)系；⑩既不是等價關(guān)系也不是偏序關(guān)系； 27、下面給定5個函數(shù)，其中單射而非滿射的有A ，滿射而非單射的有B ， 雙射的有C ，既不單射，又不滿射的有D 。 設(shè)R為實數(shù)集合，Z為整數(shù)集合，R+、Z+分別表示正實數(shù)和正整數(shù)集合。 ①f：R→R，f（x）= -x2+2x-1； ②f：R→Z+，f（x）=lnx； ③f：R→Z，f（x）=，表示不大于x的最大整數(shù)； ④f：R→R，f（x）=2 x+1； ⑤f：R+→R+，f（x）= 28、對于給定集合A和B，構(gòu)造從A到B的雙射函數(shù)。 （1）A=Z，B=N，其中Z，N分別表示整數(shù)集和自然數(shù)集； （2）A=[，2]，B=[-1，1]的實數(shù)區(qū)間 29、（1）設(shè)S=｛1，2｝，R為S上的二元關(guān)系，且xRy。如果R=Is，則A ；如果R是數(shù)的小于等于關(guān)系，則B ；如果R=Es，則C 。 （2）設(shè)有序?qū)? x+2，4 > 與有序?qū)?5，2x+y >相等，則x=D ，y=E 。 A、B、C： ①x與y可任意選擇1或2；②x=1，y=1；③x=1，y=1或2；x=y=2； ④x=2，y=2；⑤x=y=1或x=y=2；⑥x=1，y=2；⑦x=2，y=1； D、E： ⑧3；⑨9；⑩ -2 30、設(shè)S=<1，2，3，4>，R為S上的關(guān)系，其關(guān)系矩陣是 ， 則（1）R的關(guān)系表達(dá)式是A； （2）domR=B ；ranR=C ； （3）RR中有D 個有序?qū)Γ? （4）R-1的關(guān)系圖中有E 個環(huán)。 A：①｛<1，1>，<1，2>，<1，4>，<4，1>，<4，3>｝； ②｛<1，1>，<1，4>，<2，1>，<4，1>，<3，4>｝； B、C： ③｛1，2，3，4｝；④｛1，2，4｝；⑤｛1，4｝；⑥｛1，3，4｝； D、E： ⑦1；⑧3；⑨6；⑩7 31、設(shè)S=｛1，2，…，9，10｝，是S上的整除關(guān)系，則的哈斯圖是A ，其中最大元是B ，最小元是C ，最小上界是D ，最大下界是E 。 A：①一棵樹；②一條鏈；③以上都不對； B、C、D、E： ④；⑤1；⑥10；⑦6，7，8，9，10；⑧6；⑨0；⑩不存在 32、設(shè)R的關(guān)系圖如所示，試給出r（R）、s（R）、t（R）的關(guān)系圖。 33、畫出下列集合關(guān)于整除關(guān)系的哈斯圖。 （1）｛1，2，3，4，6，8，12，24｝ （2）｛1，2，…，8，9｝ 34、設(shè)A=｛a，b｝，B=｛0，1｝， （1）求P（A）和BA； （2）構(gòu)造一個從P（A）到BA的雙射函數(shù)。 代數(shù)系統(tǒng)部分 1、設(shè)Z+=｛x|x∈Z∧x>0｝，*表示求兩個數(shù)的最小公倍數(shù)的運(yùn)算，則 （1）4*6=A； （2）*在Z+上B； （3）對于*運(yùn)算的幺元是C ，零元是D ； （4）在Z+中E； A：①24；②12； B：③只滿足交換率；④只滿足結(jié)合律； ⑤滿足交換率、結(jié)合律和冪等律； C、D：⑥0；⑦1；⑧不存在； E：⑨不存在逆元；⑩只有唯一的逆元 2、在有理數(shù)集合Q上定義二元運(yùn)算*，x，y∈Q有 x * y = x + y - xy 則（1）2*（-5）=A ，7*1/2 = B 。 （2）*在Q上是C； （3）關(guān)于*的幺元是D； （4）Q中滿足E； A、B：①4；②7；③-13； C：④可結(jié)合的；⑤不可結(jié)合的； D：⑥1；⑦0； E：⑧所有的元素都有逆元；⑨只有唯一的逆元； ⑩x∈Q，x1時，有逆元x-1。 3、設(shè)V1=，V2=，其中S1=｛a，b，c，d｝，S2={0，1，2，3}。和*由運(yùn)算表1和表2給出。 定義同態(tài)：S1→S2，且 （a）=0，（b）=1，（c）=0，（d）=1， 則（1）V1中的運(yùn)算A ，其幺元是B ，V2中的運(yùn)算*C ； （2）是D ，V1在下的同態(tài)像是E ； A、C：①滿足交換律，不滿足結(jié)合律；②不滿足交換律，滿足結(jié)合律； ③滿足交換律，滿足結(jié)合律； B：④a；⑤d； D：⑥單同態(tài)；⑦滿同態(tài)；⑧以上兩者都不是； E：⑨；⑩<｛0，1｝，*> 4、設(shè)V1=<｛1，2，3｝，，1>，其中xy表示取x和y之中較大的數(shù)，V2=<｛5，6｝，*，6>，其中x*y表示取x和y之中較小的數(shù)。 （1）V1含有A 個子代數(shù)，其中平凡的真子代數(shù)有B 個； V2含有C 個平凡的子代數(shù)。 （2）積代數(shù)V1V2中有D 個元素，其幺元是E 。 A、B、C、D： ①0；②1；③2；④3；⑤4；⑥5；⑦6； E：⑧<1，5>；⑨<1，6>；⑩<3，6> 5、設(shè)S=｛a，b｝，則S上可以定義A 個二元運(yùn)算，其中有4個運(yùn)算f1，f2，f3，f4，其運(yùn)算表如下： 則只有B 滿足交換律，C 滿足冪等律，D 有幺元，E 有零元。 A：①4；②8；③16；④2； B、C、D、E： ⑤f1和f2；⑥f1、f2和f3；⑦f3和f4； ⑧f4；⑨f1；⑩f2； 6、設(shè)S=｛1，2，…，9，10｝，問下面定義的二元運(yùn)算*是否為S上的二元運(yùn)算？ （1）x*y = gcd（x，y），x與y的最大公約數(shù)； （2）x*y = lcm（x，y），x與y的最小公倍數(shù)； （3）x*y =大于等于xy的最小整數(shù)； （4）x*y =max（x，y）； （5）x*y =質(zhì)數(shù)P的個數(shù)，其中x≤p≤y。 7、設(shè)V = 是代數(shù)系統(tǒng)，其中R*為非零實數(shù)的集合。分別對下述小題討論運(yùn)算是否可交換、可結(jié)合，并求幺元和所有可逆元素的逆元。 8、某二進(jìn)制通信編碼由4個數(shù)據(jù)位x1、x2、x3、x4和3個校驗位x5、x6、x7構(gòu)成，它們的關(guān)系如下： x5=x1x2x3；x6=x1x2x4；x7=x1x3x4； 其中為異或運(yùn)算。 （1）設(shè)S為所有滿足上述關(guān)系的碼字的集合，且x，y∈S， 有xy =(x1y1,x2y2，…,x7y7)，那么是一個A 。 （2）設(shè)x，y∈S，定義H（x，y）=，那么當(dāng)x≠y時，H（x，y）≥B 。 （3）使用該種碼可查出接收碼中包含的所有k≤C 位錯誤。 （4）使用該種碼可糾正接收碼中包含的所有k≤D 位錯誤。 （5）如果接收到1000011，且知有一位出錯，那么出錯位是第E 位。 A：①半群，但不是群；②群；③環(huán)，但不是域；④域；⑤前4種都不對； B、C、D、E： ①1；②2；③3；④4；⑤5；⑥6；⑦7；⑧0； 9、對以下定義的集合和運(yùn)算判斷它們是不是代數(shù)系統(tǒng)。如果是，是哪一種？ （1）S1=｛1，1/2，2，1/3，3，1/4，4｝，*為普通乘法，則S1是A ； （2）S2=｛a1，a2，…，an｝，n≥2，ai∈R，i=1，2，…，n， ai，aj∈S2，有aiaj=ai，則S2是B ； （3）S3=｛0，1｝，*為普通乘法，則S3是C ； （4）S4=｛1，2，3，6｝，為整除關(guān)系，則S4是D ； （5）S5=｛0，1｝，+、*分別為模2加法和乘法，則S5是E 。 A、B、C、D、E： ①半群，但不是獨異點；②是獨異點，但不是群；③群； ④環(huán)，但不是域；⑤域；⑥格，但不是布爾代數(shù)；⑦布爾代數(shù)； ⑧代數(shù)系統(tǒng)，但不是以上7種；⑨不是代數(shù)系統(tǒng)； 10、圖6-5給出一個格L，則 （1）L是A 元格； （2）L是B ； （3）b的補(bǔ)元是C ，a的補(bǔ)元是D ，1的補(bǔ)元是E 。 A：①5；②6； B：③分配格；④有補(bǔ)格；⑤布爾格；⑥以上都不對； C、D、E： ⑦不存在；⑧c和d；⑨0；⑩c； 11、設(shè)是布爾代數(shù)， （1）a，b∈B，公式f為b∧（a∨（a′∧（b∨b′）））,在B中化簡f； （2）在B中等式（a∧b′）∨（a′∧b）=0 成立的條件是什么？ 12、對以下定義的集合和運(yùn)算判斷它們能否構(gòu)成代數(shù)系統(tǒng)？如果能，請說明是構(gòu)成哪一種代數(shù)系統(tǒng)？ （1）S1=｛0，1，2，…，n｝，+為普通加法，則S1是A ； （2）S2=｛1/2，0，2｝，*為普通乘法，則S2是B ； （3）S3=｛0，1，2，…，n-1｝，n為任意給定的正整數(shù)，且n≥2，*為模n乘法，為模n加法，則S3是C ； （4）S4=｛0，1，2，3｝，≤為小于等于關(guān)系，則S4是D ； （5）S5=Mn（R），+為矩陣加法，則S5是E ； A、B、C、D、E： ①半群，不是獨異點；②獨異點，不是群；③群； ④環(huán)，不一定是域；⑤域；⑥格，不是布爾代數(shù)；⑦布爾代數(shù)； ⑧代數(shù)系統(tǒng)，不是以上7種；⑨不是代數(shù)系統(tǒng)； 13、（1）設(shè)G=｛0，1，2，3｝，若為模4乘法，則構(gòu)成A ； （2）若為模4加法，則是B 階群，且是C 。 G中的2階元是D ，4階元是E 。 A：①群；②半群，不是群； B：③有限；④無限； C：⑤Klein群；⑥置換群；⑦循環(huán)群； D、E：⑧0；⑨1和3；⑩2； 14、（1）設(shè)是布爾代數(shù)，則L中的運(yùn)算∧和∨A ，運(yùn)算∨的幺元是B ，零元是C ，最小的子布爾代數(shù)是由集合D 構(gòu)成； （2）在布爾代數(shù)L中的表達(dá)式 （a∧b）∨（a∧b∧c）∨（b∧c） 的等價式是E ； A： ①適合德.摩根律、冪等律、消去律和結(jié)合律； ②適合德.摩根律、冪等律、分配律和結(jié)合律； ③適合結(jié)合律、交換律、消去律和分配律； B、C：④0；⑤1； D：⑥｛1｝；⑦｛0，1｝； E： ⑧b∧（a∨c）；⑨（a∧c）∨（a∧b′）；⑩（a∨b）∧（a∨b∨c）∧（b∨c）； 15、下列各集合對于整除關(guān)系都構(gòu)成偏序集，判斷哪些偏序集是格？ （1）L=｛1，2，3，4，5｝； （2）L=｛1，2，3，6，12｝； （3）L=｛1，2，3，4，6，9，12，18，36｝； （4）L=｛1，2，22，…，2n｝； 16、設(shè)A=｛1，2，3，4，5｝，構(gòu)成群，其中為集合的對稱差。 （1）求解方程｛1，3｝X=｛3，4，5｝； （2）令B=｛1，4，5｝，求由B生成的循環(huán)子群； 17、設(shè)A=｛1，2，5，10，11，22，55，110｝是110的正因子集，構(gòu)成偏序集，其中≤為整除關(guān)系。 （1）畫出偏序集的哈斯圖； （2）說明該偏序集是否構(gòu)成布爾代數(shù)，為什么？ 18、在圖6-7所示的3個有界格中哪些元素有補(bǔ)元？如果有，請指出該元素的所有的補(bǔ)元。 P154 圖論部分 1、（1）（3，3，2，3）、（5，2，3，1，4）能成為圖的度數(shù)序列嗎？為什么？ （2）已知圖G有10條邊，4個3度頂點，其余頂點的度數(shù)均小于等于2，問G中至少有多少個頂點？為什么？ 2、（1）畫出4個頂點3條邊的所有可能非同構(gòu)的無向簡單圖； （2）畫出3個頂點3條邊的所有可能非同構(gòu)的有向簡單圖； 3、給定下列各圖： （1）G1=，其中，V1=（a，b，c，d，e），E1={（a，b），（b，c），（c，d），（a，e）}； （2）G2=，其中，V2=V1，E2={（a，b），（b，e），（e，b），（a，e），（d，e）}； （3）G3=，其中，V3=V1，E3={（a，b），（b，e），（e，d），（c，c）}； （4）G4=，其中，V4=V1，E4={，，，，，}； （5）G5=，其中，V5=V1，E5={，，，，}； （6）G6=，其中，V6=V1，E6={，，，，}； 在以上6個圖中，A 為簡單圖，B 為多重圖。 A：①（1），（3），（6）；②（3），（4），（5）； ③（1），（2），（4）；④（1），（4） B：①（2），（4），（5）；②（2），（5）；③（4），（5） 4、給定下列各頂點度數(shù)序列： （1）（2，2，2，2，2）； （2）（1，1，2，2，3）； （3）（1，1，2，2，2）； （4）（0，1，3，3，3）； （5）（1，3，4，4，5）； 以上5組數(shù)中，A 可以構(gòu)成無向簡單圖的度數(shù)序列。 A：①（1），（3），（4）；②（1），（2）；③（1），（3）；④（3），（4），（5）； 5、完全圖K4的所有非同構(gòu)的生成子圖中，0條邊的有A 個；1條邊的有B 個； 2條邊的有C 個；3條邊的有D 個；4條邊的有E 個；5條邊的有F 個； 6條邊的有G 個； A、B、C、D、E、F、G： ①0；②1；③2；④3；⑤4；⑥5； 6、設(shè)G為9階無向圖，每個頂點的度數(shù)不是5就是6，證明：G中至少有5個6度頂點或者至少6個5度頂點。 7、畫出5階7條邊的所有非同構(gòu)的無向簡單圖。 8、下列各組數(shù)中，哪些 能構(gòu)成無向圖的度數(shù)列？哪些 能構(gòu)成無向簡單圖的度數(shù)列？ （1）1，1，1，2，3； （2）2，2，2，2，2； （3）3，3，3，3； （4）1，2，3，4，5； （5）1，3，3，3； 9、設(shè)有向簡單圖D的度數(shù)列為2，2，3，3，其中入度列為0，0，2，3， 出度列為 。 10、設(shè)D是4階有向簡單圖，度數(shù)列為3，3，3，3，它的入度列能為1，1，1，1嗎？ （能或者不能） 11、下面各無向圖中有幾個頂點？ （1）16條邊，每個頂點都是2度頂點； （2）21條邊，3個4度頂點，其余都是3度頂點； （3）24條邊，各頂點的度數(shù)是相同的； 12、一個n（n≥2）階無向簡單圖G中，n為奇數(shù)，已知G中有r 個奇數(shù)度頂點，問G的補(bǔ)圖中有幾個奇數(shù)度頂點？ 13、畫出K4的所有非同構(gòu)的字圖，其中有幾個是生成子圖？生成子圖中有幾個是連通圖？ 14、畫出3階有向完全圖所有非同構(gòu)的子圖，問其中有幾個是生成子圖？生成子圖中又有幾個是自補(bǔ)圖？ 15、設(shè)G1、G2、G3均為4階無向簡單圖，它們均有兩條邊，它們能彼此均非同構(gòu)嗎？為什么？ 16、在K6的邊上涂上紅色或藍(lán)色。證明對于任意一種隨意的涂法，總存在紅色K3或者藍(lán)色K3。 17、（1）非同構(gòu)的無向的4階自補(bǔ)圖有A 個； （2）非同構(gòu)的無向的5階自補(bǔ)圖有B 個； A、B：①0；②1；③2；④3； 18、給定有向帶權(quán)圖如圖所示，P175 圖中b到a的最短路徑的權(quán)為A ；b到d的最短路徑的權(quán)為B ； b 到e的最短路徑的權(quán)為C ；b到g的最短路徑的權(quán)為D ； A、B、C、D： ①4；②5；③6；④7；⑤8；⑥9；⑦10； 19、某中學(xué)有3個課外小組：物理組、化學(xué)組、生物組。今有張、王、李、趙、陳5名同學(xué)。若已知： （1）張、王為物理組成員，張、李、趙為化學(xué)組成員，李、趙、陳為生物組成員； （2）張為物理組成員，王、李、趙為化學(xué)組成員，王、李、趙、陳為生物組成員； （3）張為物理組和化學(xué)組成員，王、李、趙、陳為生物組成員； 問在以上3中情況下能否各選出3名不兼職的組長？ 20、在圖8-17所示的各圖中，A 為歐拉圖，B 為哈密頓圖。 P185 A、B： ①（a），（b），（c）；②（d），（e），（f）；③（c），（e）； ④（b），（c），（d），（e），（f）；⑤（b），（c），（d），（e）； 21、在圖8-18所示的各圖中，是二部圖的為A ，在二部圖中存在完美匹配的是B ，它的匹配數(shù)是C 。 P186 A、B： ①（a）；②（b）；③（c）；④（d）；⑤（e）；⑥（f）； ⑦（a），（b）；⑧（b），（f）；⑨（c），（d），（e）；⑩（d），（e）； C：①1；②2；③3；④4； 22、圖8-19所示的平面嵌入中，面數(shù)為A ，次數(shù)最高的面的次數(shù)為B ， 次數(shù)最低的面的次數(shù)為C ，總次數(shù)為D 。 A、B、C： ①5；②6；③7；④8；⑤9；⑥10；⑦11；⑧1； D：①24；②26；③28； 23、畫出完全二部圖K13，K24，K22。 24、完全二部圖Krs中，邊數(shù)為 ，匹配數(shù)1為 。 25、今有工人甲、乙、丙去完成三項任務(wù)a、b、c。已知甲能勝任a、b、c三項任務(wù)；乙能勝任a、b兩項任務(wù)；丙能勝任b、c兩項任務(wù)。你能給出一種安排方案，使每個工人各去完成一項他們能勝任的任務(wù)嗎？ 26、畫一個無向歐拉圖，使它具有： （1）偶數(shù)個頂點，偶數(shù)條邊； （2）奇數(shù)個頂點，奇數(shù)條邊； （3）偶數(shù)個頂點，奇數(shù)條邊； （4）奇數(shù)個頂點，偶數(shù)條邊； 27、畫一個無向圖，使它是： （1）是歐拉圖，是哈密頓圖； （2）是歐拉圖，不是哈密頓圖； （3）不是歐拉圖，是哈密頓圖； （4）不是歐拉圖，不是哈密頓圖； 28、今有a、b、c、d、e、f、g7個人，已知如下事實： a：會講英語； b：會講英語和漢語； c：會講英語、意大利語和俄語； d：會講日語和漢語； e：會講德語和意大利語； f：會講法語、日語和俄語； g：會講法語和德語； 試問：這7個人要圍成一圈，應(yīng)如何排座位，才能使每個人都能和他身邊（相鄰）的人交談？ 29、彼得森圖如圖8-23所示。證明它不是二部圖，也不是歐拉圖，更不是平面圖。 P189 30、證明圖8-24所示圖G是哈密頓圖，但不是平面圖。 P189 31、圖8-25所示圖G為平面圖，試給出它的一個平面嵌入，它是極大平面圖嗎？ P189 32、（1）完全圖Kn（n≥1）都是歐拉圖，這個命題真值為A； （2）完全圖Kn（n≥1）都是哈密頓圖，這個命題真值為B； （3）完全二部圖Knm（n≥1，m≥1）都是歐拉圖，這個命題真值為C； （4）完全二部圖Knm（n≥1，m≥1）都是哈密頓圖，這個命題真值為D； A、B、C、D：①真；②假； 33、6個頂點11條邊的所有可能的非同構(gòu)的連通的簡單的非平面圖有A 個， 其中有B 個含子圖K33，有C 個含與K5同胚的子圖。 A、B、C： ①1；②2；③3；④4；⑤5；⑥6；⑦7；⑧8； 34、圖9-3所示的圖G中，實線邊所構(gòu)成的子圖是G的一顆生成樹T，求T對應(yīng)的基本回路和基本回路系統(tǒng)，基本割集和基本割集系統(tǒng) P193 35、（1）求帶權(quán)為1、3、4、5、6的最優(yōu)二元樹； （2）求帶權(quán)為2、3、5、7、8、8的最優(yōu)二元樹； 36、計算非同構(gòu)無向樹的個數(shù)。 （1）2個頂點非同構(gòu)無向樹的有A 顆； （2）4個頂點非同構(gòu)無向樹的有B 顆； （3）6個頂點非同構(gòu)無向樹的有C 顆； （4）7個頂點非同構(gòu)無向樹的有D 顆； A、B、C、D： ①1；②2；③4；④6；⑤7；⑥8；⑦9；⑧10；⑨11；⑩12； 37、（1）在一棵樹中有7片樹葉，3個3度頂點，其余都是4度頂點， 則該樹有A 個4度頂點； （2）在一棵樹中有2個4度頂點，3個3度頂點，其余都是樹葉， 則該樹有B 片樹葉； （3）一棵樹中有ni個頂點的度數(shù)為i，i=2，3，…，k，而其余的頂點都是樹葉， 則該樹中有C 片樹葉。 A、 B： ①1；②2；③3；④4；⑤5；⑥6；⑦7；⑧8；⑨9；⑩10； C： ①；②；③；④； 38、圖9-16給出兩個帶權(quán)圖。 P200 （1）圖（a）中最小生成樹的權(quán)為A； （2）圖（b）中最小生成樹的權(quán)為B； ①10；②14；③15；④21；⑤22；⑥24；⑦25；⑧26；⑨27；⑩28； 39、用Huffman算法求帶權(quán)為2、3、5、7、8的最優(yōu)二元樹T。 （1）T的權(quán)為A ； （2）T中有B 片樹葉，C 個2度頂點，D 個3度頂點，E 個4度頂點， （3）T的高度為F 。 A：①40；②45；③50；④55；⑤60； B、C、D、E、F： ①0；②1；③2；④3；⑤4；⑥5；⑦6；⑧7；⑨8； 40、（1）求一個帶權(quán)為1、2、3、4、5、5.5、7.5的最優(yōu)三元樹，其權(quán)為A； （2）求一個帶權(quán)為1.5、2.5、3、4、5、6的最優(yōu)三元樹，其權(quán)為B； A、B： ①30；②35；③37；④45；⑤47；⑥48；⑦48.5；⑧50；⑨52；⑩55； 41、設(shè)無向樹T有3個3度、2個2度頂點，其余頂點都是樹葉，樹葉頂點數(shù)為 。 42、設(shè)無向樹T有7片樹葉，其余頂點的度數(shù)均為3，求T中3度頂點數(shù)？畫出所有具有此種度數(shù)的非同構(gòu)的無向樹。 45、畫出度數(shù)列為1，1，1，1，2，2，4的所有非同構(gòu)的7階無向樹。 46、在圖9-20所示的無向圖G中，實線邊所示的子圖為G的一棵生成樹T，求G對應(yīng)于T的基本回路系統(tǒng)和基本割集系統(tǒng)。 P203 47、求圖9-21所示兩個帶權(quán)圖的最小生成樹，并計算它們的權(quán)。 P203 48、計算非同構(gòu)的根數(shù)的個數(shù)。 （1）2個頂點非同構(gòu)的根數(shù)為A 個； （2）3個頂點非同構(gòu)的根數(shù)為B 個； （3）4個頂點非同構(gòu)的根數(shù)為C 個； （4）5個頂點非同構(gòu)的根數(shù)為D 個； A、B、C、D： ①1；②2；③3；④4；⑤5；⑥6；⑦7；⑧8；⑨9；⑩10；