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

1、試題總匯數(shù)理邏輯部分1、判斷下列句子中哪些是命題（1）2是素?cái)?shù)（2）血是黑色的（3）2+3=5（4）明年10月1日是晴天（5）3能被2整除（6）這朵花多好看呀！（7）明天下午有會(huì)嗎？（8）請(qǐng)關(guān)上門?。?）X + y > 5（10）地球外的星球上也有人2、將下列命題符號(hào)化（1）3不是偶數(shù)（2）2是素?cái)?shù)和偶數(shù)（3）李芳學(xué)過(guò)英語(yǔ)或日語(yǔ)（4）如果角A和角B是對(duì)頂角，則角A等于角B（5）李平雖然聰明，但不用功（6）李平不但聰明，而且用功（7）小王是游泳冠軍或者百米賽跑冠軍（8）小王現(xiàn)在在宿舍或者在圖書(shū)館（9）選小王或者小李中的一人當(dāng)班長(zhǎng)（10）如果我上街，我就去書(shū)店看看，除非我很累（11）如果明天

2、天氣好，我們?nèi)ソ加巍７駝t，不去郊游（12）你愛(ài)我，我就嫁給你3、判斷下列命題公式是否等值（1）（pq）與pq（2）（pq）與pq4、驗(yàn)證下列等值式（1）p（qr）（ pq）r（2）p（ pq）（pq）5、用等值演算法解決下面問(wèn)題：A、B、C、D 4人百米競(jìng)賽。觀眾甲、乙、丙預(yù)報(bào)比賽的名次為，（1）甲：C第一，B第二。（2）乙：C第二，D第三。（3）丙：A第二，D第四。比賽結(jié)束后發(fā)現(xiàn)甲、乙、丙每人報(bào)告的情況都是給對(duì)一半。試問(wèn)，實(shí)際名次如何？6、求下面命題公式的主析取范式和主合取范式（1）（pq）r）p7、利用真值表求主析取范式和主合取范式（1）（pq）r8、邏輯推理證明（1）前提：pr，qs，p

3、q。結(jié)論：rs。（2）前提：pq，pr，st，sr，t。結(jié)論：q（3）前提：p（qr），sp，q。結(jié)論：sr。（4）前提：p（rs）q），p，s。結(jié)論：q9、給定語(yǔ)句如下：（1）15是素?cái)?shù)（2）10能被2整除，3是偶數(shù)（3）你下午有會(huì)嗎？（4）2x+3> 0（5）2是素?cái)?shù)或是合數(shù)（6）這個(gè)男孩真勇敢呀?。?）如果2+2=6，則5是奇數(shù)（8）只有4是偶數(shù)，3才能被2整除（9）明年5月1日是晴天（10）圓的面積等于半徑的平方與的乘積以上10個(gè)語(yǔ)句中，是簡(jiǎn)單命題的為A，是復(fù)合命題的為B，是真命題的為C，是假命題的為D，真值待定（真值客觀存在，只是現(xiàn)在不知道）的命題為E。A：（1）、（4）、（8

4、）（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）（pq）（pq）（2）（pq）（pq）（qp）（3）（pq）q（4）（pp）q（5）p（pq）（6）（pp）（qq）r）（7）（pq）p）p（8）（pq）（pq）（9）（pq r）（p qr）（10）（pq）r11、給定命題公式如下：（pq）（p

5、q）該命題公式的主析取范式中含極小項(xiàng)的個(gè)數(shù)為A，主合取范式中含極大項(xiàng)的個(gè)數(shù)為B，成真賦值個(gè)數(shù)為C，成假賦值個(gè)數(shù)為D。A、B、C、D：（1）0,（2）1,(3)2,(4)3,(5)412、一公安人員審查一件盜竊案，已知的事實(shí)如下：（1）甲或乙盜竊了錄音機(jī)（2）若甲盜竊了錄音機(jī)，則作案時(shí)間不能發(fā)生在午夜前（3）若乙的證詞正確，則午夜時(shí)屋里燈光未滅（4）若乙的證詞不正確，則作案時(shí)間發(fā)生在午夜前（5）午夜時(shí)屋里燈光滅了推理證明，誰(shuí)盜竊了錄音機(jī)。13、設(shè)p=1，q=0，r=1，s=0，有下列命題公式（1）（pq）（sr）（2）（pqrs）(sq)（3）（pqr）（ps）那么，（1）的真值為 ；（2）的真

6、值為 ；（3）的真值為 ；14、對(duì)于下面的語(yǔ)句，（1）只要43，就有32（2）只要43，就有32（3）只有43，才有32（4）只有43，才有32（5）除非43，否則32（6）43僅當(dāng)32（7）43當(dāng)且僅當(dāng)32則，他們的真值是（1） （2） （3） （4） （5） （6） （7） 。15、設(shè)A是含n個(gè)命題變項(xiàng)的公式，下面4個(gè)結(jié)論中，哪個(gè)是錯(cuò)誤的？（1）若A的主析取范式中含2n 個(gè)極小項(xiàng)，則A是重言式（2）若A的主合取范式中含2n 個(gè)極大項(xiàng)，則A是矛盾式（3）若A的主析取范式中不含任何極小項(xiàng)，則A的主析取范式為0（4）若A的主合取范式中不含任何極大項(xiàng)，則A的主合取范式為016、已知命題公式A含有3

7、個(gè)命題變項(xiàng)，其成真賦值為000，010，100，110。則A的主析取范式為 ，主合取范式為 。17、判斷下列語(yǔ)句是否為命題，如是命題請(qǐng)指出是簡(jiǎn)單命題還是復(fù)合命題，并討論真值（1）是無(wú)理數(shù)（2）5能被2整除（3）現(xiàn)在開(kāi)會(huì)嗎？（4）x+50（5）這朵花真好看呀?。?）2是素?cái)?shù)當(dāng)且僅當(dāng)三角形有3條邊（7）血是黑色的當(dāng)且僅當(dāng)太陽(yáng)從東方升起（8）2008年10月1日天氣晴朗（9）太陽(yáng)系以外的星球上有生物（10）小李在宿舍里（11）全體起立（12）4是2的倍數(shù)或是3的倍數(shù)（13）4是偶數(shù)且是奇數(shù)（14）李明與王華是同學(xué)（15）藍(lán)色和黃色可以調(diào)配成綠色18、將下列命題符號(hào)化，并討論其真值（1）如果今天是1號(hào)

8、，則明天是2號(hào)（2）如果今天是1號(hào)，則明天是3號(hào)19、設(shè)A、B、C為任意的命題公式（1）已知 ACBC，問(wèn)AB嗎？（2）已知 ACBC，問(wèn)AB嗎？（3）已知 A B，問(wèn)AB嗎？20、設(shè)計(jì)一個(gè)符合如下要求的室內(nèi)照明控制線路：在房間的門外、門內(nèi)及床頭分別裝有控制同一個(gè)電燈F的3個(gè)開(kāi)關(guān)A、B、C。當(dāng)且僅當(dāng)一個(gè)開(kāi)關(guān)的鍵向上或3個(gè)開(kāi)關(guān)的鍵都向上時(shí)電燈亮。則F的邏輯關(guān)系式可化簡(jiǎn)為 。（1）ABC （2）ABC（ABC） （3）AB（AC）（4）C（AB）21、將下列語(yǔ)句用謂詞表達(dá)式符號(hào)化（1）2是素?cái)?shù)且是偶數(shù)（2）如果2大于3，則2大于4（3）凡是有理數(shù)均可表成分?jǐn)?shù)（4）有的有理數(shù)是整數(shù)（5）沒(méi)有不吃飯的

9、人（6）素?cái)?shù)不全是奇數(shù)（7）一切人都不一樣高（8）有的自然數(shù)無(wú)先驅(qū)數(shù)（9）有些人喜歡所有的花（10）任何金屬都可以溶解在某種液體中（11）凡是對(duì)頂角都相等22、指出下列各合式公式中的指導(dǎo)變項(xiàng)、量詞的轄域、個(gè)體變項(xiàng)的自由出現(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，32）DI中特定元素a=23）函數(shù)f（x）為f（2）=3，f（3）=24）謂詞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(zhǎng)（ 2，2）= L（ 3，3）=

10、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愛(ài)吃糖。有人給出語(yǔ)句“不是所有人都愛(ài)吃糖”的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，使下面兩個(gè)公式在解釋I下均為假，從而說(shuō)明這兩個(gè)公式都不是永真式（1

11、）x（F（x）G（x）（xF（x）x G（x）（2）（xF（x）x G（x）x（F（x）G（x）27、取個(gè)體域?yàn)檎麛?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

12、）、（7）；（2）、（6）、（8）、（7）集合部分1、下列命題（1）；（2）；（3）；（4）正確的是 ；錯(cuò)誤的是 。2、計(jì)算一下冪集（1）P（）；（2）P（）；（3）P（，）；（4）P（1，2，3）3、證明（1）（A-B）B=AB；4、化簡(jiǎn) （ABC）（AB）- （A（B - C）A5、已知：AB=AC，證明：A = B6、求在1到1000之間不能被5和6，也不能被8整除的數(shù)的個(gè)數(shù)7、某班有25個(gè)學(xué)生，其中14人會(huì)打籃球，12人會(huì)打排球，6人會(huì)打籃球和排球，5人會(huì)打籃球和網(wǎng)球，還有2人會(huì)打這三種球。而6個(gè)會(huì)打網(wǎng)球的人都會(huì)打另一種球（指籃球或排球），求不會(huì)打這三種球的人數(shù)。8、設(shè)F表示一年級(jí)大學(xué)

13、生的集合，S表示二年級(jí)大學(xué)生的集合，R表示計(jì)算機(jī)科學(xué)系學(xué)生的集合，M表示數(shù)學(xué)系學(xué)生的集合，T表示選修離散數(shù)學(xué)的學(xué)生的集合，L表示愛(ài)好文學(xué)的學(xué)生的集合，P表示愛(ài)好體育運(yùn)動(dòng)的學(xué)生的集合，則下列各句子所對(duì)應(yīng)的集合表達(dá)式分別是：（1）所有計(jì)算機(jī)科學(xué)系二年級(jí)的學(xué)生都選修離散數(shù)學(xué)。A（2）數(shù)學(xué)系的學(xué)生或者愛(ài)好文學(xué)或者愛(ài)好體育運(yùn)動(dòng)。B（3）數(shù)學(xué)系一年級(jí)的學(xué)生都沒(méi)有選修離散數(shù)學(xué)。C（4）只有一、二年級(jí)的學(xué)生才愛(ài)好體育運(yùn)動(dòng)。D（5）除去數(shù)學(xué)系和計(jì)算機(jī)科學(xué)系二年級(jí)的學(xué)生外都不選修離散數(shù)學(xué)。EA、B、C、D、E：T（MR）S；RST；（MF）T =；MLP；PFS；S -（MR）P9、設(shè)S1=1，2，8，9，S2=

14、2，4，6，8，S3=1，3，5，7，9，S4=3，4，5，S5=3，5。確定在以下條件下X可能與S1,S5中哪個(gè)集合相等。（1）若XS5 = ，則A（2）若XS4但XS2 = ，則B（3）若XS1但XS3，則C（4）若X - S3= ，則D（5）若XS3但XS1，則EA、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）AB=ACB=C（2）AB=AB=（3）A（B - C）=（AB）-（AC）（

15、4）（AB）（B - A）= B11、設(shè)A、B為集合，試確定下列各式成立的充分必要條件：（1）A B = B（2）A B = B - A（3）AB = AB12、求使得以下集合等式成立時(shí)，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、計(jì)算AB、AB、A - B、AB（1）A=a，b，c，B=c，d（2）A=a，b，c，c，a，b，B=a，b，c，b（3）A=x|xNx<3，B=x|xNx2（4）A=x|xRx<1，B=x|xZx<1（5）A=x|xZx<0，B=x|xZx

16、214、設(shè)|A|=3，|P（A）|=64，|P（AB）|=256，求：|B|，|AB|，|A - B|，|AB|15、設(shè)A=1，2，求：P（A）×A16、設(shè)A、B、C、D為任意集合，判斷以下等式是否成立，若成立給與證明，否則，舉出反例。（1）（AB）×（CD）=（AC）×（BD）（2）（AB）×（CD）=（AC）×（BD）（3）（A - B）×（C - D）=（A - C）×（B - D）（4）（AB）×（CD）=（AC）×（BD）17、設(shè)F、G是N上的關(guān)系，其定義為：F=<x，y>|x，yN

17、y =x2；G=<x，y>|x，yNy =x+1；求：G-1、FG、GF、F1，2、F1，218、設(shè)F=<a，a>，<a，a，a>，求：FF，F(xiàn)a，F(xiàn)a。19、設(shè)A=a，b，c，d，R=<a，b>，<b，a>，<b，c>，<c，d>。給出R、r（R）、s（R）、t（R）的關(guān)系圖。20、設(shè)A=1，2，3，求出A上的所有的等價(jià)關(guān)系21、設(shè)A=1，2，3，11，12，R為A上整除關(guān)系，畫出哈斯圖。22、畫出<P（a，b，c），R>的哈斯圖。23、R是X上的二元關(guān)系，對(duì)于xX定義集合：R（x）=y|xRy顯

18、然R（x） X。如果X=-4，-3，-2，-1，0，1，2，3，4，且令R1=<x，y>|x，yXx< y，R2=<x，y>|x，yXy -1< x< y +2，R3=<x，y>|x，yXx2 y，則下列集合滿足（1）R1（0）=A（2）R2（0）=B（3）R3（3）=C（4）R1（1）=D（5）R2（-1）=EA、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é)果都不對(duì)24、設(shè)S=1，2，3，定義S×S上的等價(jià)關(guān)系R，<a，b>

19、;，<c，d>S×S有：<a，b><c，d>a + d = b + c則由R產(chǎn)生了S×S的一個(gè)劃分。在該劃分中共有A 個(gè)劃分塊，其中最大的塊有B 個(gè)元素，并且含有元素C 。最小的劃分塊有D 塊，每塊含有E 個(gè)元素。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)成的長(zhǎng)度不超過(guò)4的串的集合，即F=，0，1，00，01， ，1111，其中表示空串。在F上定義偏序關(guān)系R：x，yF，有<x，y>Rx 是y的前綴。例如，00是001的前綴，但01不是0

20、01的前綴。（1）偏序集<F，R>的哈斯圖是A；（2）<F，R>的極小元是B；（3）<F，R>的最大元是C；（4）GF，G=101，1001，則G的最小上界是D ，最大下屆是E 。A：鏈；樹(shù)；既不是鏈，也不是樹(shù)；B、C、D、E：；0；0、1和；不存在；10；1；111126、設(shè)S=1，2，則S上可定義A 個(gè)不同的二元關(guān)系，其中B 個(gè)等價(jià)關(guān)系，C 個(gè)偏序關(guān)系，Is是D ，是E 。A、B、C：1；2；3；4；8；16；D、E：等價(jià)關(guān)系但不是偏序關(guān)系；偏序關(guān)系但不是等價(jià)關(guān)系；等價(jià)關(guān)系和偏序關(guān)系；既不是等價(jià)關(guān)系也不是偏序關(guān)系；27、下面給定5個(gè)函數(shù)，其中單射而非滿射

21、的有A ，滿射而非單射的有B ，雙射的有C ，既不單射，又不滿射的有D 。設(shè)R為實(shí)數(shù)集合，Z為整數(shù)集合，R+、Z+分別表示正實(shí)數(shù)和正整數(shù)集合。f：RR，f（x）= -x2+2x-1；f：RZ+，f（x）=lnx；f：RZ，f（x）=，表示不大于x的最大整數(shù)；f：RR，f（x）=2 x+1；f：R+R+，f（x）=28、對(duì)于給定集合A和B，構(gòu)造從A到B的雙射函數(shù)。（1）A=Z，B=N，其中Z，N分別表示整數(shù)集和自然數(shù)集；（2）A=，2，B=-1，1的實(shí)數(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）

22、設(shè)有序?qū)?lt; x+2，4 > 與有序?qū)?lt;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； -230、設(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 個(gè)有序?qū)?；?）R-1的關(guān)系圖中有E 個(gè)環(huán)。A：<1，1>，<1，2>，<1，4>，<4，1>，<4，3

23、>；<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；731、設(shè)S=1，2，9，10，是S上的整除關(guān)系，則<S, >的哈斯圖是A ，其中最大元是B ，最小元是C ，最小上界是D ，最大下界是E 。A：一棵樹(shù)；一條鏈；以上都不對(duì)；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、，24（2）1，2，8，934、設(shè)A=a，b，B=0，1，（1）求P（A）和BA；（2）構(gòu)造一個(gè)從P（A）到BA的雙射函數(shù)。代數(shù)系統(tǒng)部分1、設(shè)Z+=x|xZx>0，*表示求兩個(gè)數(shù)的最小公倍數(shù)的運(yùn)算，則（1）4*6=A；（2）*在Z+上B；（3）對(duì)于*運(yùn)算的幺元是C ，零元是D ；（4）在Z+中E；A：24；12；B：只滿足交換率；只滿足結(jié)合律；滿足交換率、結(jié)合律和冪等律；C、D：0；1；不存在；E：不存在逆元；只有唯一的逆元2、在有理數(shù)集合Q上定義二元運(yùn)算*，x，yQ有 x * y = x + y - xy則（1）2*（-5）=A ，7*1/2 = B 。（2）*在Q上是C；（3）關(guān)于*

25、的幺元是D；（4）Q中滿足E；A、B：4；7；-13；C：可結(jié)合的；不可結(jié)合的；D：1；0；E：所有的元素都有逆元；只有唯一的逆元；xQ，x1時(shí)，有逆元x-1。3、設(shè)V1=<S1，>，V2=<S2，*>，其中S1=a，b，c，d，S2=0，1，2，3。和*由運(yùn)算表1和表2給出。定義同態(tài)：S1S2，且 （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：?jiǎn)瓮瑧B(tài)；滿同態(tài)；以上兩者都不

26、是；E：<S2，*>；<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 個(gè)子代數(shù)，其中平凡的真子代數(shù)有B 個(gè)；V2含有C 個(gè)平凡的子代數(shù)。（2）積代數(shù)V1×V2中有D 個(gè)元素，其幺元是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 個(gè)二元運(yùn)算，其中有4個(gè)運(yùn)算f1，f2，f3，f4，其運(yùn)算表如下：則只有B 滿足交換律，C

27、 滿足冪等律，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，問(wèn)下面定義的二元運(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的個(gè)數(shù)，其中xpy。7、設(shè)V = <R*，> 是代數(shù)系統(tǒng)，其中R*為非零實(shí)數(shù)的集合。分別對(duì)下述小題討論運(yùn)算是否可交換、可結(jié)合，并求幺元和所有可逆元素的逆元。8、某二進(jìn)制通信

28、編碼由4個(gè)數(shù)據(jù)位x1、x2、x3、x4和3個(gè)校驗(yàn)位x5、x6、x7構(gòu)成，它們的關(guān)系如下： x5=x1x2x3；x6=x1x2x4；x7=x1x3x4；其中為異或運(yùn)算。（1）設(shè)S為所有滿足上述關(guān)系的碼字的集合，且x，yS，有xy =(x1y1,x2y2，,x7y7)，那么<S，>是一個(gè)A 。（2）設(shè)x，yS，定義H（x，y）=，那么當(dāng)xy時(shí)，H（x，y）B 。（3）使用該種碼可查出接收碼中包含的所有kC 位錯(cuò)誤。（4）使用該種碼可糾正接收碼中包含的所有kD 位錯(cuò)誤。（5）如果接收到1000011，且知有一位出錯(cuò)，那么出錯(cuò)位是第E 位。A：半群，但不是群；群；環(huán)，但不是域；域；前4種都

29、不對(duì)；B、C、D、E：1；2；3；4；5；6；7；0；9、對(duì)以下定義的集合和運(yùn)算判斷它們是不是代數(shù)系統(tǒng)。如果是，是哪一種？（1）S1=1，1/2，2，1/3，3，1/4，4，*為普通乘法，則S1是A ；（2）S2=a1，a2，an，n2，aiR，i=1，2，n， ai，ajS2，有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：半群，但不是獨(dú)異點(diǎn)；是獨(dú)異點(diǎn)，但不是群；群；環(huán)，但不是域；域；格，但不是布爾代數(shù)；布爾代數(shù)；代數(shù)系統(tǒng)，但

30、不是以上7種；不是代數(shù)系統(tǒng)；10、圖6-5給出一個(gè)格L，則（1）L是A 元格；（2）L是B ；（3）b的補(bǔ)元是C ，a的補(bǔ)元是D ，1的補(bǔ)元是E 。A：5；6；B：分配格；有補(bǔ)格；布爾格；以上都不對(duì)；C、D、E：不存在；c和d；0；c；11、設(shè)<B，0，1>是布爾代數(shù)，（1）a，bB，公式f為b（a（a（bb）,在B中化簡(jiǎn)f；（2）在B中等式（ab）（ab）=0 成立的條件是什么？12、對(duì)以下定義的集合和運(yùn)算判斷它們能否構(gòu)成代數(shù)系統(tǒng)？如果能，請(qǐng)說(shuō)明是構(gòu)成哪一種代數(shù)系統(tǒng)？（1）S1=0，1，2，n，+為普通加法，則S1是A ；（2）S2=1/2，0，2，*為普通乘法，則S2是B ；（

31、3）S3=0，1，2，n-1，n為任意給定的正整數(shù)，且n2，*為模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：半群，不是獨(dú)異點(diǎn)；獨(dú)異點(diǎn)，不是群；群；環(huán)，不一定是域；域；格，不是布爾代數(shù)；布爾代數(shù)；代數(shù)系統(tǒng)，不是以上7種；不是代數(shù)系統(tǒng)；13、（1）設(shè)G=0，1，2，3，若為模4乘法，則<G，>構(gòu)成A ；（2）若為模4加法，則<G，>是B 階群，且是C 。G中的2階元是D ，4階元是E 。A：群；半群，不是群；B：有限；無(wú)限；C：Klein群；置換群；循環(huán)

32、群；D、E：0；1和3；2；14、（1）設(shè)<L，0，1>是布爾代數(shù)，則L中的運(yùn)算和A ，運(yùn)算的幺元是B ，零元是C ，最小的子布爾代數(shù)是由集合D 構(gòu)成；（2）在布爾代數(shù)L中的表達(dá)式 （ab）（abc）（bc）的等價(jià)式是E ；A：適合德.摩根律、冪等律、消去律和結(jié)合律；適合德.摩根律、冪等律、分配律和結(jié)合律；適合結(jié)合律、交換律、消去律和分配律；B、C：0；1；D：1；0，1；E：b（ac）；（ac）（ab）；（ab）（abc）（bc）；15、下列各集合對(duì)于整除關(guān)系都構(gòu)成偏序集，判斷哪些偏序集是格？（1）L=1，2，3，4，5；（2）L=1，2，3，6，12；（3）L=1，2，3，4，

33、6，9，12，18，36；（4）L=1，2，22，2n；16、設(shè)A=1，2，3，4，5，<P（A），>構(gòu)成群，其中為集合的對(duì)稱差。（1）求解方程1，3X=3，4，5；（2）令B=1，4，5，求由B生成的循環(huán)子群<B>；17、設(shè)A=1，2，5，10，11，22，55，110是110的正因子集，<A，>構(gòu)成偏序集，其中為整除關(guān)系。（1）畫出偏序集<A，>的哈斯圖；（2）說(shuō)明該偏序集是否構(gòu)成布爾代數(shù)，為什么？18、在圖6-7所示的3個(gè)有界格中哪些元素有補(bǔ)元？如果有，請(qǐng)指出該元素的所有的補(bǔ)元。P154圖論部分1、（1）（3，3，2，3）、（5，2，3，1

34、，4）能成為圖的度數(shù)序列嗎？為什么？（2）已知圖G有10條邊，4個(gè)3度頂點(diǎn)，其余頂點(diǎn)的度數(shù)均小于等于2，問(wèn)G中至少有多少個(gè)頂點(diǎn)？為什么？2、（1）畫出4個(gè)頂點(diǎn)3條邊的所有可能非同構(gòu)的無(wú)向簡(jiǎn)單圖；（2）畫出3個(gè)頂點(diǎn)3條邊的所有可能非同構(gòu)的有向簡(jiǎn)單圖；3、給定下列各圖：（1）G1=<V1，E1>，其中，V1=（a，b，c，d，e），E1=（a，b），（b，c），（c，d），（a，e）；（2）G2=<V2，E2>，其中，V2=V1，E2=（a，b），（b，e），（e，b），（a，e），（d，e）；（3）G3=<V3，E3>，其中，V3=V1，E3=（a，b），（b

35、，e），（e，d），（c，c）；（4）G4=<V4，E4>，其中，V4=V1，E4=<a，b>，<b，c>，<c，a>，<a，d>，<d，a>，<d，e>；（5）G5=<V5，E5>，其中，V5=V1，E5=<a，b>，<a，b>，<b，c>，<c，d>，<d，e>；（6）G6=<V6，E6>，其中，V6=V1，E6=<a，a>，<a，b>，<b，c>，<e，c>，<e，d&

36、gt;；在以上6個(gè)圖中，A 為簡(jiǎn)單圖，B 為多重圖。A：（1），（3），（6）；（3），（4），（5）；（1），（2），（4）；（1），（4）B：（2），（4），（5）；（2），（5）；（4），（5）4、給定下列各頂點(diǎn)度數(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)成無(wú)向簡(jiǎn)單圖的度數(shù)序列。A：（1），（3），（4）；（1），（2）；（1），（3）；（3），（4），（5）；5、完全圖K4的所有非同構(gòu)的生成子圖中，0條邊的有A 個(gè)；1條邊的有B 個(gè)；2條邊的有C

37、個(gè)；3條邊的有D 個(gè)；4條邊的有E 個(gè)；5條邊的有F 個(gè)；6條邊的有G 個(gè)；A、B、C、D、E、F、G：0；1；2；3；4；5；6、設(shè)G為9階無(wú)向圖，每個(gè)頂點(diǎn)的度數(shù)不是5就是6，證明：G中至少有5個(gè)6度頂點(diǎn)或者至少6個(gè)5度頂點(diǎn)。7、畫出5階7條邊的所有非同構(gòu)的無(wú)向簡(jiǎn)單圖。8、下列各組數(shù)中，哪些 能構(gòu)成無(wú)向圖的度數(shù)列？哪些 能構(gòu)成無(wú)向簡(jiǎn)單圖的度數(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è)有向簡(jiǎn)單圖D的度數(shù)列為2，2，3，3，其中入度列為0，0，2，3，出度列為 。10、設(shè)D是4階有向簡(jiǎn)單圖，度數(shù)列為3，3，

38、3，3，它的入度列能為1，1，1，1嗎？ （能或者不能）11、下面各無(wú)向圖中有幾個(gè)頂點(diǎn)？（1）16條邊，每個(gè)頂點(diǎn)都是2度頂點(diǎn)；（2）21條邊，3個(gè)4度頂點(diǎn)，其余都是3度頂點(diǎn)；（3）24條邊，各頂點(diǎn)的度數(shù)是相同的；12、一個(gè)n（n2）階無(wú)向簡(jiǎn)單圖G中，n為奇數(shù)，已知G中有r 個(gè)奇數(shù)度頂點(diǎn)，問(wèn)G的補(bǔ)圖中有幾個(gè)奇數(shù)度頂點(diǎn)？13、畫出K4的所有非同構(gòu)的字圖，其中有幾個(gè)是生成子圖？生成子圖中有幾個(gè)是連通圖？14、畫出3階有向完全圖所有非同構(gòu)的子圖，問(wèn)其中有幾個(gè)是生成子圖？生成子圖中又有幾個(gè)是自補(bǔ)圖？15、設(shè)G1、G2、G3均為4階無(wú)向簡(jiǎn)單圖，它們均有兩條邊，它們能彼此均非同構(gòu)嗎？為什么？16、在K6的邊

39、上涂上紅色或藍(lán)色。證明對(duì)于任意一種隨意的涂法，總存在紅色K3或者藍(lán)色K3。17、（1）非同構(gòu)的無(wú)向的4階自補(bǔ)圖有A 個(gè)；（2）非同構(gòu)的無(wú)向的5階自補(bǔ)圖有B 個(gè)；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個(gè)課外小組：物理組、化學(xué)組、生物組。今有張、王、李、趙、陳5名同學(xué)。若已知：（1）張、王為物理組成員，張、李、趙為化學(xué)組成員，李、趙、陳為生物組成員；（2）張為物理組成員，王、李、趙為化學(xué)組成員，王

40、、李、趙、陳為生物組成員；（3）張為物理組和化學(xué)組成員，王、李、趙、陳為生物組成員；問(wèn)在以上3中情況下能否各選出3名不兼職的組長(zhǎng)？20、在圖8-17所示的各圖中，A 為歐拉圖，B 為哈密頓圖。P185A、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 。P186A、B：（a）；（b）；（c）；（d）；（e）；（f）；（a），（b）；（b），（f）；（c），（d），（e）；（d），（e）；C：1；2；3；4；

41、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、今有工人甲、乙、丙去完成三項(xiàng)任務(wù)a、b、c。已知甲能勝任a、b、c三項(xiàng)任務(wù)；乙能勝任a、b兩項(xiàng)任務(wù)；丙能勝任b、c兩項(xiàng)任務(wù)。你能給出一種安排方案，使每個(gè)工人各去完成一項(xiàng)他們能勝任的任務(wù)嗎？26、畫一個(gè)無(wú)向歐拉圖，使它具有：（1）偶數(shù)個(gè)頂點(diǎn)，偶數(shù)條邊；（2）奇數(shù)個(gè)頂點(diǎn)，奇數(shù)條邊；（3）偶數(shù)個(gè)頂點(diǎn)，奇數(shù)條邊；（4）奇數(shù)個(gè)頂點(diǎn)，偶數(shù)條邊；27、畫一個(gè)無(wú)向圖，使它是：（1）是歐拉圖，是哈密頓圖；（2）是歐拉圖，不是哈密頓圖；（3）不是歐拉圖，是哈密頓圖；（4）不是歐拉圖，不是哈密頓圖；28、今有a、b、c、d、e、f、g7個(gè)人，已知如下事實(shí)：a：會(huì)講英語(yǔ)；b：會(huì)講英語(yǔ)和漢語(yǔ)；c：會(huì)講英語(yǔ)、意大利語(yǔ)和俄語(yǔ)；d：會(huì)講日語(yǔ)和漢語(yǔ)；e：會(huì)講德語(yǔ)和意大利語(yǔ)；f：會(huì)講法語(yǔ)、日語(yǔ)和俄語(yǔ)；g：會(huì)講法語(yǔ)和德語(yǔ)；試問(wèn)：這7個(gè)人要圍成一圈，應(yīng)如何排座位，才能使每個(gè)人都能和他身邊（相鄰）的人交談？29、彼得森圖如圖8-23所示。證明