本科離散數(shù)學(xué)

1．設(shè)P：a是偶數(shù)，Q：b是偶數(shù)。R：a+b是偶數(shù)，則命題“若a是偶數(shù)，b是偶數(shù)，則a+b也是偶數(shù)”符號化為（D．PQ→R）。2．表達(dá)式x（P（x，y）Q（z））y（Q（x，y）→zQ（z））中x的轄域是（P（x，y）Q（z））。3．設(shè)則命題為假的是（）。4．設(shè)G是有n個(gè)結(jié)點(diǎn)的無向完全圖，則G的邊數(shù)（1/2n（n-1））。5．設(shè)G是連通平面圖，有v個(gè)結(jié)點(diǎn)，e條邊，r個(gè)面，則r=（e-v+2）。6．若集合A={1，{2}，{1，2}}，則下列表述正確的是({1}A)．7．已知一棵無向樹T中有8個(gè)頂點(diǎn)，4度、3度、2度的分支點(diǎn)各一個(gè)，T的樹葉數(shù)為(5)．8．設(shè)無向圖G的鄰接矩陣為則G的邊數(shù)為(7)．9．設(shè)集合A={a}，則A的冪集為({，{a}})．10．下列公式中(AB(AB))為永真式．11．若G是一個(gè)漢密爾頓圖，則G一定是(連通圖)．12．集合A={1,2,3,4}上的關(guān)系R={<x，y>|x=y且x,yA}，則R的性質(zhì)為（傳遞的）．13．設(shè)集合A={1，2，3，4，5}，偏序關(guān)系是A上的整除關(guān)系，則偏序集<A，>上的元素5是集合A的（極大元）．14．圖G如圖一所示，以下說法正確的是({(a,d),(b,d)}是邊割集)．圖一15．設(shè)A（x）：x是人，B（x）：x是工人，則命題“有人是工人”可符號化為（(x)(A(x)∧B(x))）．16．若集合A={1，2}，B={1，2，{1，2}}，則下列表述正確的是(AB，且AB)．17．設(shè)有向圖（a）、（b）、（c）與（d）如圖一所示，則下列結(jié)論成立的是(（d）是強(qiáng)連通的)．18．設(shè)圖G的鄰接矩陣為則G的邊數(shù)為(5)．19．無向簡單圖G是棵樹，當(dāng)且僅當(dāng)(G連通且邊數(shù)比結(jié)點(diǎn)數(shù)少1)．20．下列公式((P(QP))(P(PQ)))為重言式．21．若集合A＝{a，{a}，{1，2}}，則下列表述正確的是({a}A)．22．設(shè)圖G＝<V,E>，vV，則下列結(jié)論成立的是()．23．命題公式（P∨Q）→R的析取范式是(（P∧Q）∨R)24．下列等價(jià)公式成立的為(P(QP)P(PQ))．25．設(shè)A={a,b}，B={1,2}，R1，R2，R3是A到B的二元關(guān)系，且R1={<a，2>,<b，2>}，R2={<a，1>,<a，2>,<b，1>}，R3={<a，1>,<b，2>}，則（R2）不是從A到B的函數(shù)．26．設(shè)A={1,2,3,4,5,6,7,8}，R是A上的整除關(guān)系，B={2,4,6}，則集合B的最大元、最小元、上界、下界依次為(無、2、無、2)．27．若集合A的元素個(gè)數(shù)為10，則其冪集的元素個(gè)數(shù)為（1024）．28．如圖一所示，以下說法正確的是(e是割點(diǎn))．圖一29．設(shè)完全圖K有n個(gè)結(jié)點(diǎn)(n≥2)，m條邊，當(dāng)（n為奇數(shù)）時(shí)，K中存在歐拉回路．30．已知圖G的鄰接矩陣為，則G有（5點(diǎn)，7邊）．二、填空題（每小題3分，共15分）1．設(shè)A，B為任意命題公式，C為重言式，若ACBC，那么AB是重言式（重言式、矛盾式或可滿足式）。2．命題公式（P→Q）P的主合取范式為。3．設(shè)集合A={，{a}}，則P（A）=。4．設(shè)圖G=〈V，E〉，G′=〈V′，E′〉，若V′=V,E′E,則G′是G的生成子圖。5．在平面G=〈V，E〉中，則=2|E|，其中（i=1，2，…，r）是G的面。6．命題公式的真值是假（或F，或0）．7．若無向樹T有5個(gè)結(jié)點(diǎn)，則T的邊數(shù)為4．8．設(shè)正則m叉樹的樹葉數(shù)為t，分支數(shù)為i，則(m-1)i=t-1．9．設(shè)集合A={1，2}上的關(guān)系R＝{<1,1>,<1,2>}，則在R中僅需加一個(gè)元素<2,1>，就可使新得到的關(guān)系為對稱的．10．(x)(A(x)→B(x，z)∨C(y))中的自由變元有z，y．11．若集合A={1，3，5，7}，B={2，4，6，8}，則A∩B=空集（或）．12．設(shè)集合A={1，2，3}上的函數(shù)分別為：f={<1,2>,<2,1>,<3,3>,}，g={<1,3>,<2,2>,<3,2>,}，則復(fù)合函數(shù)gf={<1,2>,<2,3>,<3,2>,}．13．設(shè)G是一個(gè)圖，結(jié)點(diǎn)集合為V，邊集合為E，則G的結(jié)點(diǎn)度數(shù)之和為2|E|（或“邊數(shù)的兩倍”）．14．無向連通圖G的結(jié)點(diǎn)數(shù)為v，邊數(shù)為e，則G當(dāng)v與e滿足e=v-1關(guān)系時(shí)是樹．15．設(shè)個(gè)體域D＝{1,2,3}，P(x)為“x小于2”，則謂詞公式(x)P(x)的真值為假（或F，或0）16．命題公式的真值是T（或1）．17．若圖G=<V,E>中具有一條漢密爾頓回路，則對于結(jié)點(diǎn)集V的每個(gè)非空子集S，在G中刪除S中的所有結(jié)點(diǎn)得到的連通分支數(shù)為W，則S中結(jié)點(diǎn)數(shù)|S|與W滿足的關(guān)系式為W|S|．18．給定一個(gè)序列集合{000，001，01，10，0}，若去掉其中的元素0，則該序列集合構(gòu)成前綴碼．19．已知一棵無向樹T中有8個(gè)結(jié)點(diǎn)，4度，3度，2度的分支點(diǎn)各一個(gè)，T的樹葉數(shù)為5．20．(x)(P(x)→Q(x)∨R(x，y))中的自由變元為R(x，y)中的y．21．設(shè)集合A={0,1,2,3}，B={2,3,4,5}，R是A到B的二元關(guān)系，則R的有序?qū)蠟閧<2,2>，<2,3>，<3,2>}，<3,3>．22．設(shè)G是連通平面圖，v,e,r分別表示G的結(jié)點(diǎn)數(shù)，邊數(shù)和面數(shù)，則v，e和r滿足的關(guān)系式v-e+r=2．23．設(shè)G＝<V,E>是有6個(gè)結(jié)點(diǎn)，8條邊的連通圖，則從G中刪去3條邊，可以確定圖G的一棵生成樹．24．無向圖G存在歐拉回路，當(dāng)且僅當(dāng)G連通且所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)．25．設(shè)個(gè)體域D＝{1,2}，則謂詞公式消去量詞后的等值式為A(1)A(2)．26．設(shè)集合A＝{a，b}，那么集合A的冪集是{,{a,b},{a},}．27．如果R1和R2是A上的自反關(guān)系，則R1∪R2，R1∩R2，R1-R2中自反關(guān)系有2個(gè)．28．設(shè)圖G是有6個(gè)結(jié)點(diǎn)的連通圖，結(jié)點(diǎn)的總度數(shù)為18，則可從G中刪去4條邊后使之變成樹．29．設(shè)連通平面圖G的結(jié)點(diǎn)數(shù)為5，邊數(shù)為6，則面數(shù)為3．30．設(shè)個(gè)體域D＝{a,b}，則謂詞公式(x)A(x)∧（x）B（x）消去量詞后的等值式為(A(a)∧A(b))∧(B（a）∨B（b）)．31.設(shè)集合A={0，1，2}，B={l，2，3，剖，R是A到B的二元關(guān)系，R={<x,y>|x∈A且y∈B且x，y∈A∩B}則R的有序?qū)蠟開__{<1,1>,<1,2>,<2,1>,<2,2>}___32.設(shè)G是連通平面圖，v，e，r分別表示G的結(jié)點(diǎn)數(shù)，邊數(shù)和面數(shù)，則v，e和r滿足的關(guān)系式__v-e+r=2_____33.G=<V,E>是有20個(gè)結(jié)點(diǎn)，25條邊的連通圖,則從G中刪去__6__條邊，可以確定圖G的一棵生成樹.34.無向圖G存在歐拉回路，當(dāng)且僅當(dāng)G所有結(jié)點(diǎn)的度數(shù)全為偶數(shù)且_連通____35.設(shè)個(gè)體域D={1,2}，則謂詞公式"xA(x)消去量詞后的等值式為__A(1)∧A(2)___三、化簡解答題11．設(shè)集合A={1，2，3，4}，A上的二元關(guān)系R，R={〈1，1〉，〈1，4〉，〈2，2〉，〈2，3〉，〈3，2〉，〈3，3〉，〈4，1〉，〈4，4〉}，說明R是A上的等價(jià)關(guān)系。解從R的表達(dá)式知，即R具有自反性；三、邏輯公式翻譯1．將語句“今天上課．”翻譯成命題公式．設(shè)P：今天上課，則命題公式為：P．2．將語句“他去操場鍛煉，僅當(dāng)他有時(shí)間．”翻譯成命題公式． 設(shè)P：他去操場鍛煉，Q：他有時(shí)間，則命題公式為：PQ．3．將語句“他是學(xué)生．”翻譯成命題公式．設(shè)P：他是學(xué)生，則命題公式為：P．4．將語句“如果明天不下雨，我們就去郊游．”翻譯成命題公式．設(shè)P：明天下雨，Q：我們就去郊游，則命題公式為：PQ．5．將語句“他不去學(xué)校．”翻譯成命題公式．設(shè)P：他去學(xué)校，P．6．將語句“他去旅游，僅當(dāng)他有時(shí)間．”翻譯成命題公式．設(shè)P：他去旅游，Q：他有時(shí)間，PQ．7．將語句“所有的人都學(xué)習(xí)努力．”翻譯成命題公式．設(shè)P(x)：x是人，Q(x)：x學(xué)習(xí)努力，（x）(P(x)Q(x))．8．將語句“如果你去了，那么他就不去．”翻譯成命題公式．設(shè)P：你去，Q：他去，PQ．9．將語句“小王去旅游，小李也去旅游．”翻譯成命題公式．設(shè)P：小王去旅游，Q：小李去旅游，PQ．10．將語句“所有人都去工作．”翻譯成謂詞公式．設(shè)P(x)：x是人，Q(x)：x去工作，(x)(P(x)Q(x))．11．將語句“如果所有人今天都去參加活動，則明天的會議取消．”翻譯成命題公式．設(shè)P：所有人今天都去參加活動，Q：明天的會議取消， PQ．12．將語句“今天沒有人來．”翻譯成命題公式．設(shè)P：今天有人來，P．13．將語句“有人去上課．”翻譯成謂詞公式．設(shè)P(x)：x是人，Q(x)：x去上課，(x)(P(x)Q(x))．11.將語句"如果小李學(xué)習(xí)努力，那么他就會取得好成績."翻譯成命題公式.設(shè)P：小李學(xué)習(xí)努力，Q:小李會取得好成績，P→Q12.將語句"小張學(xué)習(xí)努力,小王取得好成績."翻譯成命題公式.設(shè)P：小張學(xué)習(xí)努力，Q:小王取得好成績，P∧Q四、判斷說明題1．設(shè)集合A={1，2}，B={3，4}，從A到B的關(guān)系為f={<1,3>}，則f是A到B的函數(shù)．錯(cuò)誤．因?yàn)锳中元素2沒有B中元素與之對應(yīng)，故f不是A到B的函數(shù)．2．設(shè)G是一個(gè)有4個(gè)結(jié)點(diǎn)10條邊的連通圖，則G為平面圖． 錯(cuò)誤．不滿足“設(shè)G是一個(gè)有v個(gè)結(jié)點(diǎn)e條邊的連通簡單平面圖，若v≥3，則e≤3v-6．”3．設(shè)N、R分別為自然數(shù)集與實(shí)數(shù)集，f：N→R，f(x)=x+6，則f是單射．正確．設(shè)x1，x2為自然數(shù)且x1x2，則有f(x1)=x1+6x2+6=f(x2)，故f為單射．4．下面的推理是否正確，試予以說明．(1)（x）F（x）→G（x）前提引入(2)F（y）→G（y）US（1）．錯(cuò)誤．（2）應(yīng)為F（y）→G（x），換名時(shí)，約束變元與自由變元不能混淆．5．如圖二所示的圖G存在一條歐拉回路．圖二錯(cuò)誤．因?yàn)閳DG為中包含度數(shù)為奇數(shù)的結(jié)點(diǎn)．6．設(shè)G是一個(gè)有6個(gè)結(jié)點(diǎn)14條邊的連通圖，則G為平面圖．錯(cuò)誤．不滿足“設(shè)G是一個(gè)有v個(gè)結(jié)點(diǎn)e條邊的連通簡單平面圖，若v≥3，則e≤3v-6．”7．如果R1和R2是A上的自反關(guān)系，則R1∪R2是自反的．正確．R1和R2是自反的，xA，<x,x>R1，<x,x>R2，則<x,x>R1R2，所以R1∪R2是自反的．8．如圖二所示的圖G存在一條歐拉回路．vv1v2v3v5v4dbacefghn圖二正確．因?yàn)閳DG為連通的，且其中每個(gè)頂點(diǎn)的度數(shù)為偶數(shù)．9．┐P∧（P→┐Q）∨P為永真式．正確．┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）與P組成的析取式，如果P的值為真，則┐P∧（P→┐Q）∨P為真，如果P的值為假，則┐P與P→┐Q為真，即┐P∧（P→┐Q）為真，也即┐P∧（P→┐Q）∨P為真，所以┐P∧（P→┐Q）∨P是永真式．另種說明：┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）與P組成的析取式，只要其中一項(xiàng)為真，則整個(gè)公式為真．可以看到，不論P(yáng)的值為真或?yàn)榧伲碢∧（P→┐Q）與P總有一個(gè)為真，所以┐P∧（P→┐Q）∨P是永真式．或用等價(jià)演算┐P∧（P→┐Q）∨PT10．若偏序集<A，R>的哈斯圖如圖一所示，則集合A的最大元為a，最小元不存在．圖一正確．對于集合A的任意元素x，均有<x,a>R（或xRa），所以a是集合A中的最大元．按照最小元的定義，在集合A中不存在最小元．11.如果R1和R2是A上的自反關(guān)系，則R1∩R2是自反的。正確，R1和R2，是自反的，"x∈A,<x,x>∈R1,<x,x>∈R2,則<x,x>∈R1∩R2，所以R1∩R2是自反的.12.如圖二所示的圖中存在一條歐拉回路.圖二正確，因?yàn)閳DG為連通的，且其中每個(gè)頂點(diǎn)的度數(shù)為偶數(shù)。五．計(jì)算題（每小題12分，本題共36分）1．試求出（P∨Q）→（R∨Q）的析取范式．（P∨Q）→（R∨Q）┐(P∨Q)∨（R∨Q）(┐P∧┐Q)∨（R∨Q）(┐P∧┐Q)∨R∨Q（析取范式）2．設(shè)A={{1},1,2}，B={1,{2}}，試計(jì)算（1）（A∩B）（2）（A∪B）（3）A（A∩B）．（1）（A∩B）={1}（2）（A∪B）={1,2,{1},{2}}（3）A（A∩B）={{1},1,2}3．圖G=<V,E>，其中V={a,b,c,d}，E={(a,b),(a,c),(a,d),(b,c),(b,d),(c,d)}，對應(yīng)邊的權(quán)值依次為1、2、3、1、4及5，試（1）畫出G的圖形；（2）寫出G的鄰接矩陣；圖一圖一abcd112453（1）G的圖形表示如圖一所示：圖二圖二abcd112453（3）最小的生成樹如圖二中的粗線所示：權(quán)為：1+1+3=54．畫一棵帶權(quán)為1,2,2,3,4的最優(yōu)二叉樹,計(jì)算它們的權(quán)．1223347512圖三權(quán)為13+23+22+32+42=275．求（P∨Q）→R的析取范式與合取范式．（P∨Q）→R（P∨Q）∨R(P∧Q)∨R（析取范式）(P∨R)∧(Q∨R)（合取范式）6．設(shè)A={0，1，2，3}，R={<x，y>|xA，yA且x+y<0}，S={<x，y>|xA，yA且x+y2}，試求R，S，RS，S-1，r(R)．R=,S={<0,0>,<0,1>,<0,2>,<1,0>,<1,1>,<2,0>}RS=，S-1=S，r(R)=IA={<0,0>,<1,1>,<2,2>,<3,3>}．7．試求出（P∨Q）→R的析取范式，合取范式，主合取范式． （P∨Q）→R┐(P∨Q)∨R(┐P∧┐Q)∨R（析取范式）(┐P∨R)∧(┐Q∨R)（合取范式）((┐P∨R)∨(Q∧┐Q))∧((┐Q∨R)∨(P∧┐P))(┐P∨R∨Q)∧(┐P∨R∨┐Q)∧(┐Q∨R∨P)∧(┐Q∨R∨┐P)(┐P∨Q∨R)∧(┐P∨┐Q∨R)∧(P∨┐Q∨R)8．設(shè)A={{a,b},1,2}，B={a,b,{1},1}，試計(jì)算（1）（AB）（2）（A∪B）（3）（A∪B）（A∩B）．（1）（AB）={{a,b},2}（2）（A∪B）={{a,b},1,2,a,b,{1}}（3）（A∪B）（A∩B）={{a,b},2,a,b,{1}}9．圖G=<V,E>，其中V={a,b,c,d,e}，E={(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(c,d),(d,e)}，對應(yīng)邊的權(quán)值依次為2、1、2、3、6、1、4及5，試（1）畫出G的圖形；（2）寫出G的鄰接矩陣；（3）求出G權(quán)最小的生成樹及其權(quán)值．（1）G的圖形表示為：（2）鄰接矩陣：（3）粗線表示最小的生成樹，權(quán)為7：10．設(shè)謂詞公式，試（1）寫出量詞的轄域；（2）指出該公式的自由變元和約束變元．（1）x量詞的轄域?yàn)椋瑉量詞的轄域?yàn)?y量詞的轄域?yàn)椋?）自由變元為與中的y，以及中的z約束變元為x與中的z，以及中的y．11．設(shè)A={{1},{2},1,2}，B={1,2,{1,2}}，試計(jì)算（1）（AB）；（2）（A∩B）；（3）A×B．（1）AB={{1},{2}}（2）A∩B={1,2}（3）A×B={<{1},1>，<{1},2>，<{1},{1,2}>，<{2},1>，<{2},2>，<{2},{1,2}>，<1,1>，<1,2>，<1,{1,2}>，<2,1>，<2,2>,<2,{1,2}>}12．設(shè)G=<V，E>，V={v1，v2，v3，v4，v5}，E={(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)}，試（1）給出G的圖形表示；（2）寫出其鄰接矩陣；（3）求出每個(gè)結(jié)點(diǎn)的度數(shù)；（4）畫出其補(bǔ)圖的圖形． （1）G的圖形表示為：（2）鄰接矩陣：（3）v1，v2，v3，v4，v5結(jié)點(diǎn)的度數(shù)依次為1，2，4，3，2（4）補(bǔ)圖如下：13．設(shè)集合A={1，2，3，4}，R={<x,y>|x,yA；|xy|=1或xy=0}，試（1）寫出R的有序?qū)Ρ硎?；?）畫出R的關(guān)系圖；（3）說明R滿足自反性，不滿足傳遞性．（1）R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>}12343）因?yàn)?lt;1,1>,<2,2>,<3,3>,<4,4>均屬于R，即A的每個(gè)元素構(gòu)成的有序?qū)赗中，故R在A上是自反的。因有<2,3>與<3,4>屬于R，但<2,4>不屬于R，所以R在A上不是傳遞的。14．求PQR的析取范式，合取范式、主析取范式，主合取范式．P→（R∨Q）?┐P∨(R∨Q)?┐P∨Q∨R（析取、合取、主合取范式）?(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧R)∨(P∧┐Q∧┐R)∨(P∧┐Q∧R)∨(P∧Q∧┐R)∨(P∧Q∧R)（主析取范式）15．設(shè)圖G=<V，E>，V={v1，v2，v3，v4，v5}，E={(v1,v2)，(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)}，試畫出G的圖形表示；寫出其鄰接矩陣；(3)求出每個(gè)結(jié)點(diǎn)的度數(shù)；v1v2v1v2v3v4v5（1）關(guān)系圖（2）鄰接矩陣（3）deg(v1)=2deg(v2)=3deg(v3)=4deg(v4)=3v1v2vv1v2v3v4v5（4）補(bǔ)圖16．設(shè)謂詞公式$x(A(x,y)∧"zB(x,y,z))∧"yC(y,z)試

(1)寫出量詞的轄域;

$x量詞的轄域?yàn)?A(x,y)∧"zB(x,y,z)),"z量詞的轄域?yàn)锽(x,y,z),"y量詞的轄域?yàn)镃(y,z)(2)指出該公式的自由變元和約束變元. 自由變元為(A(x,y)∧"zB(x,y,z))中的y,以及C(y,z)中的z.約束變元為(A(x,y)∧"zB(x,y,z))中的x與B(x,y,z)中的z,以及C(y,z)中的y。六、證明題1．試證明：若R與S是集合A上的自反關(guān)系，則R∩S也是集合A上的自反關(guān)系．證明：設(shè)xA，因?yàn)镽自反，所以xRx，即<x,x>R；又因?yàn)镾自反，所以xRx，即<x,x>S．即<x,x>R∩S故R∩S自反．2．試證明集合等式A(BC)=(AB)(AC)．證明：設(shè)S=A(BC)，T=(AB)(AC)，若x∈S，則x∈A或x∈BC，即x∈A或x∈B且x∈A或x∈C．也即x∈AB且x∈AC，即x∈T，所以ST．反之，若x∈T，則x∈AB且x∈AC，即x∈A或x∈B且x∈A或x∈C，也即x∈A或x∈BC，即x∈S，所以TS．因此T=S．3．試證明集合等式A(BC)=(AB)(AC)．證明：設(shè)S=A∩(B∪C)，T=(A∩B)∪(A∩C)，若x∈S，則x∈A且x∈B∪C，即x∈A且x∈B或x∈A且x∈C，也即x∈A∩B或x∈A∩C，即x∈T，所以ST．反之，若x∈T，則x∈A∩B或x∈A∩C，即x∈A且x∈B或x∈A且x∈C也即x∈A且x∈B∪C，即x∈S，所以TS．因此T=S．4．試證明集合等式A(BC)=(AB)(AC)．證明：設(shè)S=A(BC)，T=(AB)(AC)，若x∈S，則x∈A或x∈BC，即x∈A或x∈B且x∈A或x∈C．也即x∈AB且x∈AC，即x∈T，所以ST．反之，若x∈T，則x∈AB且x∈AC，即x∈A或x∈B且x∈A或x∈C，也即x∈A或x∈BC，即x∈S，所以TS．因此T=S．5．試證明（x）（P（x）∧R（x））（x）P（x）∧（x）R（x）．證明：（1）（$x）（P（x）∧R（x））P（2）P（a）∧R（a）ES(1)（3）P（a）T(2)I（4）（$x）P（x）EG(3)（5）R（a）T(2)I（6）（$x）R（x）EG(5)（7）（$x）P（x）∧（$x）R（x）T(5)(6)I6．設(shè)m是一個(gè)取定的正整數(shù)，證明：在任取m＋1個(gè)整數(shù)中，至少有兩個(gè)整數(shù)，它們的差是m的整數(shù)倍證明設(shè)，，…，為任取的m＋1個(gè)整數(shù)，用m去除它們所得余數(shù)只能是0，1，…，m－1，由抽屜原理可知，，，…，這m＋1個(gè)整數(shù)中至少存在兩個(gè)數(shù)和，它們被m除所得余數(shù)相同，因此和的差是m的整數(shù)倍。7．已知A、B、C是三個(gè)集合，證明A-(B∪C)=(A-B)∩(A-C)證明∵xA-（B∪C）xA∧x（B∪C）xA∧（xB∧xC）（xA∧xB）∧（xA∧xC）x（A-B）∧x（A-C）x（A-B）∩（A-C）∴A-（B∪C）=（A-B）∩（A-C）8．（15分）設(shè)<A，*>是半群，對A中任意元a和b，如a≠b必有a*b≠b*a，證明：(1)對A中每個(gè)元a，有a*a＝a。(2)對A中任意元a和b，有a*b*a＝a。(3)對A中任意元a、b和c，有a*b*c＝a*c。證明由題意可知，若a*b＝b*a，則必有a＝b。(1)由(a*a)*a＝a*(a*a)，所以a*a＝a。(2)由a*(a*b*a)＝(a*a)*(b*a)＝a*b*(a*a)＝(a*b*a)*a，所以有a*b*a＝a。(3)由(a*c)*(a*b*c)＝(a*c*a)*(b*c)＝a*(b*c)