離散數學題庫

《離散數學題庫》由會員分享，可在線閱讀，更多相關《離散數學題庫（18頁珍藏版）》請在裝配圖網上搜索。

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