【正文】 （ B ）A. P→P∨Q B. (P→Q)(QP) C. P∨P→S D. P∧(P→Q)∧Q41．公式中 的轄域?yàn)? （ C ）A. B. C. D. 42．若 今天下雪了； 路滑；則“雖然今天下雪了，但是路不滑”，可符號(hào)化為 （ D ）A. B. C. D. 43. 設(shè)上的二元關(guān)系,則等于是(B ）A. B. C. D. 44. 指出下列語(yǔ)句中哪個(gè)是命題 （ D ）A. 這本書(shū)真好看??！ B. 上課請(qǐng)不要遲到！C. 你吃午飯了嗎？ D. 李白是唐朝的詩(shī)人。7. 不含多重邊和 環(huán) 的圖，稱(chēng)為簡(jiǎn)單圖。22. 若某連通簡(jiǎn)單平面圖有4個(gè)頂點(diǎn)，3 個(gè)區(qū)域，則有____5____條邊。39. 命題“如果1+1=0，則明天太陽(yáng)在東邊落下”的真值為　　T　 。47. 設(shè) 則= {2,3,4,5} 。16. 相容關(guān)系：給定集合A上的關(guān)系R，若R是自反的、對(duì)稱(chēng)的，則稱(chēng)R為A上的相容關(guān)系。B(3)) 217。(P 174。解：（1） 設(shè)M（x）：x是人，B（x）：x長(zhǎng)著綠色頭發(fā) 則命題（1）可表示為：（2） 設(shè)M（x）：x是上海市民，B（x）：x去過(guò)東方明珠塔； 則命題（2）可表示為：7. 給定有向圖G=V, E如下：試求：（1）各頂點(diǎn)的出、入度； (2) 寫(xiě)出 G 的鄰接矩陣 ； （3）利用矩陣計(jì)算求出從頂點(diǎn)1到4長(zhǎng)度分別為1，2和3的路各有幾條。16. 畫(huà)出符合下列條件的圖（1） 畫(huà)一個(gè)有一條歐拉回路和一條漢密爾頓回路的圖。當(dāng)a=1/2時(shí)，a無(wú)逆元；否則a1= a/(1+2a). 23. 設(shè)無(wú)向圖 GV,E , 其中 V={1,2,3,4,5} , E={(1,2),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)}(1). 畫(huà)出 G 所對(duì)應(yīng)的圖。 (P217。Q)218。此外，對(duì)任意a, b206。12． 設(shè)為模4剩余類(lèi)的集合，為模4加法，寫(xiě)出的運(yùn)算表并證明為群。 (1). aA,aG, 使a=a*a*a1 , (a,a) R, 即 R自反； (2). (a,b) R, 有cG, a=c*b*c1, 由(G,*)是群，c1G, b=c1*a*c, (b,a)R, R對(duì)稱(chēng)； (3). (a,b)，(b,c) R, 有 d,f G, 滿足a=d*b*d1, b=f*c*f1 , 于是a=d*b*d1＝d* f*c*f1*d1=(d*f)*c*(d*f)1，由(G,*)是群，d*f G， 即(a, c) R，故 R傳遞。證明：K, *是G, *的子群。R) 219。 五、 證明題1． 證明：(P174。(1). 運(yùn)算*滿足結(jié)合律嗎？(2). R,*有單位元e，求e。13. 求的主析取范式和主合取范式。5. 求表達(dá)式：(a+bc)247。3. 試求公式：P217。B(y))，其中R(3)= B(4)=T，R(4)= B(3)=F，且論域是{3, 4}，求該式的真值。11. 無(wú)向圖簡(jiǎn)單圖G的鄰接矩陣：設(shè)無(wú)向圖G有n個(gè)結(jié)點(diǎn)v1,v2,…,vn, 無(wú)多重邊，定義nn階矩陣M=(mij)是G的鄰接矩陣，其中12. 約束變?cè)膿Q名：對(duì)公式中的約束變?cè)裾找欢ㄒ?guī)則更改名稱(chēng)符號(hào)，稱(chēng)為約束變?cè)膿Q名。H 。34. 在一個(gè)有個(gè)元素的集合上，可以有 種不同的函數(shù)。17. 設(shè)A={1，2}，B={1，2}∪Φ，則A與B 　　相等 （相等、不相等）。2. 合式公式（x）F(x) ∧G(x,y)中 變?cè)獃是___自由___變?cè)?（填自由或約束） 3. 設(shè)M＝｛x | (x是整數(shù)) ∧ (1≤x≤12) ∧ (x被2整除) ｝,N={x | ( x是整數(shù)) ∧ (1≤x≤12) ∧ (x被3整除) }， 則M∩N=__{6,12}___。32. 設(shè)，則下列哪個(gè)集合是從的函數(shù) （ C ）A. B. C. D．33. 在謂詞演算中，下列各式正確的是 （ A ）A. B. C. D. 34. 設(shè)（A,+, ο）是整環(huán)，則以下斷言錯(cuò)誤的是 （ D ）A. （A,+）是阿貝爾群 B.（A,ο）是可交換獨(dú)異點(diǎn) C. 運(yùn)算ο對(duì)＋可分配 D.（A,ο）有零因子35. 以下格是分配格的是 （ C ）A. 鉆石格 B. 五角格 C. 小于5個(gè)元素的格 D. 含與鉆石格同構(gòu)的子格的格36. 指出下列語(yǔ)句中哪個(gè)是復(fù)合命題 ( C )A. 5是奇數(shù) 。($x) M(x) 等價(jià)的是 （ D ）A．(x) M(x) Ｂ．($x) 216。45. 設(shè)A={{1,2,3},{4,5},{6,7,8}},式子為真是 （ C ）A. 1∈ A。8. 任意兩個(gè)大項(xiàng)的析取為 永真 。23. 在根樹(shù)中，如果每一個(gè)結(jié)點(diǎn)的出度恰好等于 或零，則稱(chēng)這棵樹(shù)為完全叉樹(shù)。40. ( P217。48. 存在 歐拉 回路的圖，稱(chēng)為歐拉圖。17. 漢密爾頓圖：給定圖G，若存在一條回路，經(jīng)過(guò)圖中的每個(gè)結(jié)點(diǎn)恰好一次，這條回路稱(chēng)為漢密爾頓回路。(R(4) 218。Q ) 219。解：（1） 結(jié)點(diǎn) 1 2 3 4 結(jié)點(diǎn)的出度 2 2 2 1 結(jié)點(diǎn)的入度 0 3 1 3 （2）鄰接矩陣：（3）因?yàn)椋核詮捻旤c(diǎn)1到4長(zhǎng)度分別為1，2和3的路分別有2條。（2） 畫(huà)一個(gè)有一條歐拉回路，但沒(méi)有一條漢密爾頓回路的圖。 (2). 求各結(jié)點(diǎn)的度；(3). G 是否具有歐拉回路? 是否具有歐拉通路? 為什么? 若有請(qǐng)寫(xiě)出解：(1). 圖G為：(2). 結(jié)點(diǎn) 1 2 3 4 5 結(jié)點(diǎn)的度 2 4 3 3 4 (3). 因?yàn)榻Y(jié)點(diǎn)3的度是奇數(shù)，所以圖G無(wú)歐拉回路；因?yàn)閮H有兩個(gè)結(jié)點(diǎn)4的度是奇數(shù)，所以圖G有歐拉通路；歐拉通路為（3,2,1,5,2,4,5,3,4） 24. 設(shè)，定義上的二元關(guān)系，稱(chēng)稱(chēng)為小于關(guān)系，也可記為，試求出，dom，ran。Q)174。R 219。K，由于K, *是H, *的子群，故a*b206。證明：+4[0][1][2][3][0][0][1][2][3][1][1][2][3][0][2][2][3][0][1][3][3][0][1][2]Z4={[0]，[1]，[2]，[3] }由運(yùn)算表可知+4運(yùn)算在Z4上是封閉的；+6運(yùn)算是可結(jié)合的；存在幺元[0]，[1]和[3互為逆元， [0]和[2]的逆元為自己。證：證明R滿足自反性、對(duì)稱(chēng)性和傳遞性。證明：令是滿射， 使令，則是滿射的5． 設(shè)H, *是群G, *的子群，K, *是H, *的子群。Q218。解：設(shè)A= ┐(P∨ ┐Q)∧(P → Q) , 由真值表 P Q ┐Q P∨ ┐Q ┐(P∨ ┐Q) P → Q A 0 0 1 1 0 1 0 0 1 0 0 1 1 1 1 0 1 1 0 0 0 1 1 0 1 0 1 0 得使