【正文】 單射，f是滿射；因IC恒等函數(shù)，由gofoh＝IC可得h是單射，g是滿射。由hogof＝IA，得f＝hog；由fohog＝IB，得g＝foh；由gofoh＝IC，得h＝gof。x＝y(tǒng)，證明：若G有限，則G是一群。由a*x＝a*y222。于是可證，對(duì)任意的a∈G，有aG＝G。令e∈G使得a*e＝a。對(duì)任意a∈G，由aG＝G可知，存在b∈G使得a*b＝e，再由運(yùn)算*滿足交換律得b*a＝e，所以b是a的逆元。故G是一群。證明 不妨設(shè)G是無向連通圖（若G為有向圖，可略去邊的方向討論對(duì)應(yīng)的無向圖）。由連通性，必存在與v1相鄰的結(jié)點(diǎn)，不妨設(shè)它為v2（否則可重新編號(hào)），連接v1和v2，得邊e1，還是由連通性，在vv…、vn中必存在與v1或v2相鄰的結(jié)點(diǎn)，不妨設(shè)為v3，將其連接得邊e2，續(xù)行此法，vn必與vv…、vn1中的某個(gè)結(jié)點(diǎn)相鄰，得新邊en1，由此可見G中至少有n－1條邊。試證：若n≥Cm1＋2，則G是哈密爾頓圖。1＋2，則2n≥m－3m＋6（1）2若存在兩個(gè)不相鄰結(jié)點(diǎn)u、v使得d(u)＋d(v)＜m，則有2n＝w206。d(w)＜m＋(m－2)(m－3)＋m＝m－23m＋6，與（1）矛盾。G是哈密爾頓圖。Q)174。(Q174。證明：因?yàn)?P174。(P∧Q)219。(216。(P∧216。P)∧(P∨Q)219。Q∨P)∧(P∨Q)219。Q)∨(216。(P∧216。(P∧216。Q))219。Q)∨(P∧Q)∨(P∧216。(P∧216。Q)174。(Q174。二、（10分）證明下述推理： 如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。解 設(shè)A：A努力工作；B、C、D分別表示B、C、D愉快；則推理化形式為： A174。216。216。216。B∨C P(3)B∨C T(1)(2)，I(4)B174。A P(5)A174。BT(4)，E(6)216。216。D T(7)(8)，I(10)A174。D CP三、（10分）證明xy(P(x)174。($xP(x)174。xy(P(x)174。xy(216。x(216。x216。216。($xP(x)174。1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)197。解 P(A)＝{198。}，{1}，{{1}}，{198。{1}}，{1，{1}}，{198。{0}，{{0}}，{0，{0}}－{0}＝{198。B＝{198。{0，{0}}＝{198。(2)寫出R的關(guān)系矩陣。解(1)R的關(guān)系圖如圖所示：(2)R的關(guān)系矩陣為：230。231。1231。1232。247。 0247。0247。(3)對(duì)于R的關(guān)系矩陣，由于對(duì)角線上不全為1，R不是自反的；由于對(duì)角線上存在非0元，R不是230。231。1231。1232。247。=M(R)，所以R是傳遞的。0247。248。RR，f定義為：f()＝。(2)證明f是滿射。(4)求復(fù)合函數(shù)fof和fof。(2)對(duì)任意的∈RR，令x＝－1－1u+wuwu+wuwu+w，y＝，則f()＝＝，所以f是滿射。22－1－1(4)fof()＝f(f())＝f()＝x+y+xyx+y(xy)，＝44455fof()＝f(f())＝f()＝＝。證明 對(duì)G中任意元a和b。同理，由a*b＝(a*b)可得，a*b＝(b*a)。于是(a*b)*(b*a)＝(b*a)＝a*b，即b*a＝a*b。由于(a*b)*b＝a*b＝b*a＝b*(b*a)＝b*(a*b)＝(b*a)*b，故a*b＝b*a。證明 不妨設(shè)G是無向連通圖（若G為有向圖，可略去邊的方向討論對(duì)應(yīng)的無向圖）。由連通性，必存在與v1相鄰的結(jié)點(diǎn)，不妨設(shè)它為v2（否則可重新編號(hào)），連接v1和v2，得邊e1，還是由連通性，在vv…、vn中必存在與v1或v2相鄰的結(jié)點(diǎn)，不妨設(shè)為v3，將其連接得邊e2，續(xù)行此法，vn必與vv…、vn1中的某個(gè)結(jié)點(diǎn)相鄰，得新邊en1，由此可見G中至少有n－1條邊。解 下圖滿足條件但不連通。A、F205。A； C、{{4，5}}204。A。174。R ； B.(P218。(P174。Q)171。R)；D、(P174。R))174。Q)174。R))。A、x(L(x)174。$y(J(y)217。J(y)217。J(y)174。（x）(y)(P(x,y)∧Q(y,z))∧(x)p(x,y),下面的描述中錯(cuò)誤的是__B_____ A．（x）的轄域是（y）（P（x,y）∧Q(y,z)）B．z是該謂詞公式的約束變?cè)狢．（x）的轄域是P（x,y）D．x是該謂詞公式的約束變?cè)?8． 設(shè)S205。B，下列各式中____B___________是正確的。B ； B、domS205。A； D、domS 200。9．設(shè)集合X185。A、自反性； B、反自反性； C、對(duì)稱性； D、傳遞性。A,且R={(1,2),(1,2),(2,1),(2,2),(2,3),(2,4),(3,4),(4,1)},則頂點(diǎn)2的入度和出度分別是___D_______ ,3 ,4 ,3 ,4 (n≥2)，m條邊，當(dāng)下面條件__C____滿足時(shí)，Kn中存在歐拉回路．A．m為奇數(shù) B．n為偶數(shù) C．n為奇數(shù) D．m為偶數(shù) ,3是歐拉圖 K3,3是哈密爾頓圖 K3,32,3是既不是歐拉圖也不哈密爾頓圖，邊數(shù)是14，則該平面圖有__D___個(gè)面 16．設(shè)G是n個(gè)結(jié)點(diǎn)、m條邊和r個(gè)面的連通平面圖，則m等于___A____。不是群的是___D____ A. B. C. D.(這里Z，Q，R，N分別表示整數(shù)集、有理數(shù)集、實(shí)數(shù)集、自然數(shù)集，+普通加法)二、問答題，有如下形式的判斷語句： if(a=0)if(b1)if(c請(qǐng)將這段程序化簡(jiǎn)，并說明化簡(jiǎn)的理由。amp。amp。r:cA=P→(q→(r→s))經(jīng)過等值演算可得，A與下面的公式是等值的 P∧q∧r→s={ 1, 2, 3, 4, 5, 6, 7, 8, 9 }，R={(x,y)| x|y}, ①證明R是偏序關(guān)系。所以R是A上的偏序關(guān)系。該公司65人，有些職工（例如項(xiàng)目管理人員、設(shè)計(jì)人員）可能從事不止一個(gè)崗位的工作?，F(xiàn)在軟件設(shè)計(jì)崗位（崗位A）（包括需求分析、概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)等工作）的人數(shù)是15人，代碼編寫崗位（崗位B）的人數(shù)是32人，軟件測(cè)試崗位（崗位C）的人數(shù)是28人，同時(shí)參加崗位A和崗位B的有12人, 同時(shí)參加崗位B和崗位C的有8人, 同時(shí)參加崗位A和崗位C組的有3人，問，三個(gè)崗位參加的有多少人？解： 已知 |A|=15，|B|=32，|C|=28，|A∩B|=12，|B∩C|=8，|A∩C|=3 設(shè)S表示全班同學(xué)總?cè)藬?shù)，則 |S|=65 求：|A∩B∩C|=？根據(jù)容斥原理：|A∪B∪C|=|A|+|B|+|C||A∩B||B∩C||A∩C|+|A∩B∩C| 所以|A∩B∩C|=|A∪B∪C||A||B||C|+|A∩B|+|B∩C|+|A∩C| 因?yàn)槊總€(gè)同學(xué)至少參加一個(gè)小組，所以：|A∪B∪C|=|S| 因此：|A∩B∩C|=65153228+12+8+3=13 答：三個(gè)小組都參加的人數(shù)是13人(n,r)= C(n1,r1)+ C(n1,r)說明：也可以直接利用組合演算公式進(jìn)行演算 ? 解：1228的個(gè)位數(shù)就是1228 mod 10的余數(shù)1228mod10=(12mod10)28mod10=24*7mod10=(27mod10)4mod10=8mod10=64, 4個(gè)3度頂點(diǎn), 其余頂點(diǎn)的度數(shù)均小于2, 問G至少有多少個(gè)頂點(diǎn)?解：由握手定理∑d(v)=2m=20，度數(shù)為3的頂點(diǎn)有3個(gè)占去12度，還有8度由其余頂點(diǎn)占有，而由題意，其余頂點(diǎn)的度數(shù)可為0，1，當(dāng)均為1時(shí)所用頂點(diǎn)數(shù)最少，所以應(yīng)有8個(gè)頂點(diǎn)占有此8度，即G中至少有8+4=12個(gè)頂點(diǎn)。（2）若甲盜竊了電腦，則作案時(shí)間不能發(fā)生在午夜前。（4）若乙證詞不正確，則作案時(shí)間發(fā)生在午夜前。請(qǐng)通過命題邏輯推理，推論出誰是真正的盜竊犯？（寫出詳細(xì)的推理步驟）解 設(shè)p： 甲盜竊了電腦，q： 乙盜竊了電腦，r： 作案時(shí)間發(fā)生在午夜前，s： 乙證詞正確，t：午夜時(shí)屋里燈光滅了。，求出T與n的顯示關(guān)系表達(dá)式236。238。239。=T(n2)+n2+n1239。=T(n3)+n3+n2+n1 239。239。=T(nk)+kn(1+2+Lk)239。k(k+1)239。令nk=1，那么 k=n1，所以：n(n1)n(n1)n(n1)236。222238。1(mod 3)x186。3(mod 5)解：已知a1=1,a2=2,a3=3。1(mod m1)即20x186。20180。15180。12180。計(jì)算 n=p*q=7*19=133 計(jì)算φ(n)=(p1)*(q1)=(71)*(191)=108 選取較小的數(shù)w,使w與108互質(zhì), 5是最小的,于是w=5 計(jì)算d,使d*w≡1(mod φ(n)),即d*5 mod 108=1,取d=65，d*5除以108余數(shù)為1, 于是算出d=65 至此加密、解密參數(shù)計(jì)算完成：公鑰w=5,n==65,n=133.② 加密c=mwmodn=85mod133=((82mod133)*(83mod133))mod133=(64*113)mod133=50③ 解密a=cdmodn=5065mod133a=A0A6 其中，A0=50, Ai=(Ai1)2根據(jù)上述遞推公式可以計(jì)算出：A1=502mod133=106,A2=1062mod133=64A3=642mod133=106，??, A6=1062mod133=64 a=A0A6=(50*64)mod133=8解密后的明文與原來的明文是相等的，所以算法正確。b(mod 3)}，（1）證明R是一個(gè)等價(jià)關(guān)系；（2）寫出A的商集；問題說明：假設(shè)我們需要從5個(gè)元素中選取3個(gè)的所有組合，已知組合個(gè)數(shù)為 C（５，３）＝１０，按字典序，其具體組合為： 123,124,125,134,135,145,234,235,245,345 所謂按字典序生成組合，就是已知當(dāng)前的組合（例如135），求下一個(gè)組合（例如，145）。max_val=n。while(s[m]==max_val){m=m1。}s[m]=s[m]+1。js[j]=s[j1]+1。(2)若B去, 則C不能去