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

試題總匯數(shù)理邏輯某些1、判斷下列句子中哪些是命題（1）2是素?cái)?shù)（2）血是黑色（3）2+3=5（4）來年10月1日是晴天（5）3能被2整除（6）這朵花多好看呀?。?）明天下午有會(huì)嗎？（8）請(qǐng)關(guān)上門?。?）X+y>5（10）地球外星球上也有人2、將下列命題符號(hào)化（1）3不是偶數(shù)（2）2是素?cái)?shù)和偶數(shù)（3）李芳學(xué)過英語或日語（4）如果角A和角B是對(duì)頂角，則角A等于角B（5）李平雖然聰穎，但不用功（6）李平不但聰穎，并且用功（7）小王是游泳冠軍或者百米賽跑冠軍（8）小王當(dāng)前在宿舍或者在圖書館（9）選小王或者小李中一人當(dāng)班長(zhǎng)（10）如果我上街，我就去書店看看，除非我很累（11）如果明每天氣好，咱們?nèi)ソ加?。否則，不去郊游（12）你愛我，我就嫁給你3、判斷下列命題公式與否等值（1）（p∨q）與p∨q（2）（p∨q）與p∧q4、驗(yàn)證下列等值式（1）p→（q→r）（p∧q）→r（2）p（p∧q）∨（p∧q）5、用等值演算法解決下面問題：A、B、C、D4人百米競(jìng)賽。觀眾甲、乙、丙預(yù)報(bào)比賽名次為，（1）甲：C第一，B第二。（2）乙：C第二，D第三。（3）丙：A第二，D第四。比賽結(jié)束后發(fā)現(xiàn)甲、乙、丙每人報(bào)告狀況都是給對(duì)一半。試問，實(shí)際名次如何？6、求下面命題公式主析取范式和主合取范式（1）（（p∨q）→r）→p7、運(yùn)用真值表求主析取范式和主合取范式（1）（p∧q）∨r8、邏輯推理證明（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é)論：q9、給定語句如下：（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è)語句中，是簡(jiǎn)樸命題為A，是復(fù)合命題為B，是真命題為C，是假命題為D，真值待定（真值客觀存在，只是當(dāng)前不懂得）命題為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）∧r11、給定命題公式如下：（p→q）→（p∨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）若乙證詞對(duì)的，則半夜時(shí)屋里燈光未滅（4）若乙證詞不對(duì)的，則作案時(shí)間發(fā)生在半夜前（5）半夜時(shí)屋里燈光滅了推理證明，誰盜竊了錄音機(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、對(duì)于下面語句，（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個(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個(gè)命題變項(xiàng)，其成真賦值為000，010，100，110。則A主析取范式為，主合取范式為。17、判斷下列語句與否為命題，如是命題請(qǐng)指出是簡(jiǎn)樸命題還是復(fù)合命題，并討論真值（1）是無理數(shù)（2）5能被2整除（3）當(dāng)前開會(huì)嗎？（4）x+5＞0（5）這朵花真好看呀?。?）2是素?cái)?shù)當(dāng)且僅當(dāng)三角形有3條邊（7）血是黑色當(dāng)且僅當(dāng)太陽從東方升起（8）10月1日天氣晴朗（9）太陽系以外星球上有生物（10）小李在宿舍里（11）全體起立（12）4是2倍數(shù)或是3倍數(shù)（13）4是偶數(shù)且是奇數(shù)（14）李明與王華是同窗（15）藍(lán)色和黃色可以調(diào)配成綠色18、將下列命題符號(hào)化，并討論其真值（1）如果今天是1號(hào)，則明天是2號(hào)（2）如果今天是1號(hào)，則明天是3號(hào)19、設(shè)A、B、C為任意命題公式（1）已知A∨CB∨C，問AB嗎？（2）已知A∧CB∧C，問AB嗎？（3）已知AB，問AB嗎？20、設(shè)計(jì)一種符合如下規(guī)定室內(nèi)照明控制線路：在房間門外、門內(nèi)及床頭分別裝有控制同一種電燈F3個(gè)開關(guān)A、B、C。當(dāng)且僅當(dāng)一種開核心向上或3個(gè)開核心都向上時(shí)電燈亮。則F邏輯關(guān)系式可化簡(jiǎn)為。（1）A∨B∨C（2）A∨B∨C∨（A∧B∧C）（3）A∨B∨（A∧C）（4）C∨（A∧B）21、將下列語句用謂詞表達(dá)式符號(hào)化（1）2是素?cái)?shù)且是偶數(shù)（2）如果2不不大于3，則2不不大于4（3）凡是有理數(shù)均可表成分?jǐn)?shù)（4）有有理數(shù)是整數(shù)（5）沒有不吃飯人（6）素?cái)?shù)不全是奇數(shù)（7）一切人都不同樣高（8）有自然數(shù)無先驅(qū)數(shù)（9）有人喜歡所有花（10）任何金屬都可以溶解在某種液體中（11）凡是對(duì)頂角都相等22、指出下列各合式公式中指引變項(xiàng)、量詞轄域、個(gè)體變項(xiàng)自由浮現(xiàn)和約束浮現(xiàn)（1）x（F（x）→yH（x，y））（2）xF（x）∧G（x，y）（3）xy（R（x，y）∨L（x，y））∧xH（x，y）23、給定解釋I如下：1）DI={2，3}2）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）=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）xyL（x，y）24、求下列公式前束范式（1）xF（x）∧xG（x）（2）xF（x）∨xG（x）（3）xF（x）→xG（x）（4）xF（x）→xG（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））對(duì)的答案是。26、給出解釋I，使下面兩個(gè)公式在解釋I下均為假，從而闡明這兩個(gè)公式都不是永真式（1）x（F（x）∨G（x））→（xF（x）∨xG（x））（2）（xF（x）∧xG（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）xyz（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）｛｝對(duì)的是；錯(cuò)誤是。2、計(jì)算一下冪集（1）P（）；（2）P（｛｝）；（3）P（｛，｛｝｝）；（4）P（｛1，｛2，3｝｝）3、證明（1）（A-B）∪B=A∪B；4、化簡(jiǎn)（（A∪B∪C）∩（A∪B））-（（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表達(dá)一年級(jí)大學(xué)生集合，S表達(dá)二年級(jí)大學(xué)生集合，R表達(dá)計(jì)算機(jī)科學(xué)系學(xué)生集合，M表達(dá)數(shù)學(xué)系學(xué)生集合，T表達(dá)選修離散數(shù)學(xué)學(xué)生集合，L表達(dá)興趣文學(xué)學(xué)生集合，P表達(dá)興趣體育運(yùn)動(dòng)學(xué)生集合，則下列各句子所相應(yīng)集合表達(dá)式分別是：（1）所有計(jì)算機(jī)科學(xué)系二年級(jí)學(xué)生都選修離散數(shù)學(xué)。A（2）數(shù)學(xué)系學(xué)生或者興趣文學(xué)或者興趣體育運(yùn)動(dòng)。B（3）數(shù)學(xué)系一年級(jí)學(xué)生都沒有選修離散數(shù)學(xué)。C（4）只有一、二年級(jí)學(xué)生才興趣體育運(yùn)動(dòng)。D（5）除去數(shù)學(xué)系和計(jì)算機(jī)科學(xué)系二年級(jí)學(xué)生外都不選修離散數(shù)學(xué)。EA、B、C、D、E：①T（M∪R）∩S；②R∩ST；③（M∩F）∩T=；④ML∪P；⑤PF∪S；⑥S-（M∪R）P9、設(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中哪個(gè)集合相等。（1）若X∩S5=，則A（2）若XS4但X∩S2=，則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）A∪B=A∪CB=C（2）AB=AB=（3）A∩（B-C）=（A∩B）-（A∩C）（4）（A∩B）∪（B-A）=B11、設(shè)A、B為集合，試擬定下列各式成立充分必要條件：（1）A–B=B（2）A–B=B-A（3）A∪B=A∩B12、求使得如下集合等式成立時(shí)，a，b，c，d應(yīng)當(dā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ì)算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）×A16、設(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>|x，y∈N∧y=x2｝；G=｛<x，y>|x，y∈N∧y=x+1｝；求：G-1、FG、GF、F↑｛1，2｝、F[｛1，2｝]18、設(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ì)于x∈X定義集合：R（x）={y|xRy}顯然R（x）X。如果X={-4，-3，-2，-1，0，1，2，3，4}，且令R1=｛<x，y>|x，y∈X∧x<y｝，R2=｛<x，y>|x，y∈X∧y-1<x<y+2｝，R3=｛<x，y>|x，y∈X∧x2≤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｝；⑩以上成果都不對(duì)24、設(shè)S=｛1，2，3｝，定義S×S上等價(jià)關(guān)系R，<a，b>，<c，d>∈S×S有：<a，b>～<c，d>a+d=b+c則由R產(chǎn)生了S×S一種劃分。在該劃分中共有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)度不超過4串集合，即F=｛，0，1，00，01，…，1111｝，其中表達(dá)空串。在F上定義偏序關(guān)系R：x，y∈F，有<x，y>∈Rx是y前綴。例如，00是001前綴，但01不是001前綴。（1）偏序集<F，R>哈斯圖是A；（2）<F，R>極小元是B；（3）<F，R>最大元是C；（4）GF，G=｛101，1001｝，則G最小上界是D，最大下屆是E。A：①鏈；②樹；③既不是鏈，也不是樹；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ù)，其中單射而非滿射有A，滿射而非單射有B，雙射有C，既不單射，又不滿射有D。設(shè)R為實(shí)數(shù)集合，Z為整數(shù)集合，R+、Z+分別表達(dá)正實(shí)數(shù)和正整數(shù)集合。①f：R→R，f（x）=-x2+2x-1；②f：R→Z+，f（x）=lnx；③f：R→Z，f（x）=，表達(dá)不不不大于x最大整數(shù)；④f：R→R，f（x）=2x+1；⑤f：R+→R+，f（x）=28、對(duì)于給定集合A和B，構(gòu)造從A到B雙射函數(shù)。（1）A=Z，B=N，其中Z，N分別表達(dá)整數(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）設(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>｝；②｛<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：①一棵樹；②一條鏈；③以上都不對(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｝（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｝，*表達(dá)求兩個(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，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時(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)：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：⑨<S2，*>；⑩<｛0，1｝，*>4、設(shè)V1=<｛1，2，3｝，，1>，其中xy表達(dá)取x和y之中較大數(shù)，V2=<｛5，6｝，*，6>，其中x*y表達(dá)取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滿足冪等律，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個(gè)數(shù)，其中x≤p≤y。7、設(shè)V=<R*，>是代數(shù)系統(tǒng)，其中R*為非零實(shí)數(shù)集合。分別對(duì)下述小題討論運(yùn)算與否可互換、可結(jié)合，并求幺元和所有可逆元素逆元。8、某二進(jìn)制通信編碼由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，y∈S，有xy=(x1y1,x2y2，…,x7y7)，那么<S，>是一種A。（2）設(shè)x，y∈S，定義H（x，y）=，那么當(dāng)x≠y時(shí)，H（x，y）≥B。（3）使用該種碼可查出接受碼中包括所有k≤C位錯(cuò)誤。（4）使用該種碼可糾正接受碼中包括所有k≤D位錯(cuò)誤。（5）如果接受到1000011，且知有一位出錯(cuò)，那么出錯(cuò)位是第E位。A：①半群，但不是群；②群；③環(huán)，但不是域；④域；⑤前4種都不對(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｝，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：①半群，但不是獨(dú)異點(diǎn)；②是獨(dú)異點(diǎn)，但不是群；③群；④環(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ǔ)格；⑤布爾格；⑥以上都不對(duì)；C、D、E：⑦不存在；⑧c和d；⑨0；⑩c；11、設(shè)<B，∧，∨，′，0，1>是布爾代數(shù)，（1）a，b∈B，公式f為b∧（a∨（a′∧（b∨b′）））,在B中化簡(jiǎn)f；（2）在B中檔式（a∧b′）∨（a′∧b）=0成立條件是什么？12、對(duì)如下定義集合和運(yùn)算判斷它們能否構(gòu)成代數(shù)系統(tǒng)？如果能，請(qǐ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：①半群，不是獨(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：③有限；④無限；C：⑤Klein群；⑥置換群；⑦循環(huán)群；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á)式（a∧b）∨（a∧b∧c）∨（b∧c）等價(jià)式是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、下列各集合對(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，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，3｝X=｛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）闡明該偏序集與否構(gòu)成布爾代數(shù)，為什么？18、在圖6-7所示3個(gè)有界格中哪些元素有補(bǔ)元？如果有，請(qǐng)指出該元素所有補(bǔ)元。P154圖論某些1、（1）（3，3，2，3）、（5，2，3，1，4）能成為圖度數(shù)序列嗎？為什么？（2）已知圖G有10條邊，4個(gè)3度頂點(diǎn)，別的頂點(diǎn)度數(shù)均不大于等于2，問G中至少有多少個(gè)頂點(diǎn)？為什么？2、（1）畫出4個(gè)頂點(diǎn)3條邊所有也許非同構(gòu)無向簡(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，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>}；在以上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)成無向簡(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個(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階無向圖，每個(gè)頂點(diǎn)度數(shù)不是5就是6，證明：G中至少有5個(gè)6度頂點(diǎn)或者至少6個(gè)5度頂點(diǎn)。7、畫出5階7條邊所有非同構(gòu)無向簡(jiǎn)樸圖。8、下列各組數(shù)中，哪些能構(gòu)成無向圖度數(shù)列？哪些能構(gòu)成無向簡(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，3，3，它入度列能為1，1，1，1嗎？（能或者不能）11、下面各無向圖中有幾種頂點(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、一種n（n≥2）階無向簡(jiǎn)樸圖G中，n為奇數(shù)，已知G中有r個(gè)奇數(shù)度頂點(diǎn)，問G補(bǔ)圖中有幾種奇數(shù)度頂點(diǎn)？13、畫出K4所有非同構(gòu)字圖，其中有幾種是生成子圖？生成子圖中有幾種是連通圖？14、畫出3階有向完全圖所有非同構(gòu)子圖，問其中有幾種是生成子圖？生成子圖中又有幾種是自補(bǔ)圖？15、設(shè)G1、G2、G3均為4階無向簡(jiǎn)樸圖，它們均有兩條邊，它們能彼此均非同構(gòu)嗎？為什么？16、在K6邊上涂上紅色或藍(lán)色。證明對(duì)于任意一種隨意涂法，總存在紅色K3或者藍(lán)色K3。17、（1）非同構(gòu)無向4階自補(bǔ)圖有A個(gè)；（2）非同構(gòu)無向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名同窗。若已知：（1）張、王為物理構(gòu)成員，張、李、趙為化學(xué)構(gòu)成員，李、趙、陳為生物構(gòu)成員；（2）張為物理構(gòu)成員，王、李、趙為化學(xué)構(gòu)成員，王、李、趙、陳為生物構(gòu)成員；（3）張為物理組和化學(xué)構(gòu)成員，王、李、趙、陳為生物構(gòu)成員；問在以上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；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、畫一種無向歐拉圖，使它具備：（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、畫一種無向圖，使它是：（1）是歐拉圖，是哈密頓圖；（2）是歐拉圖，不是哈密頓圖；（3）不是歐拉圖，是哈密頓圖；（4）不是歐拉圖，不是哈密頓圖；28、今有a、b、c、d、e、f、g7個(gè)人，已知如下事實(shí)：a：會(huì)講英語；b：會(huì)講英語和漢語；c：會(huì)講英語、意大利語和俄語；d：會(huì)講日語和漢語；e：會(huì)講德語和意大利語；f：會(huì)講法語、日語和俄語；g：會(huì)講法語和德語；試問：這7個(gè)人要圍成一圈，應(yīng)如何排座位，才干使每個(gè)人都能和她身邊（相鄰）人交談？29、彼得森圖如圖8-23所示。證明它不是二部圖，也不是歐拉圖，更不是平面圖。P18930、證明圖8-24所示圖G是哈密頓圖，但不是平面圖。P18931、圖8-25