【正文】 等, 稱(chēng)A和B是等價(jià)的.9. 子群：設(shè)是一個(gè)群，S是G的非空子群，如果也構(gòu)成群，則稱(chēng)是的一個(gè)子群。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名。14. 歐拉回路：給定有向圖G，通過(guò)圖中每邊一次且一次的一條回路稱(chēng)作歐拉回路。16. 相容關(guān)系：給定集合A上的關(guān)系R，若R是自反的、對(duì)稱(chēng)的，則稱(chēng)R為A上的相容關(guān)系。具有漢密爾頓回路的圖稱(chēng)作漢密爾頓圖。20. 等價(jià)關(guān)系：一個(gè)二元關(guān)系若滿(mǎn)足自反性，對(duì)稱(chēng)性和傳遞性稱(chēng)為等價(jià)關(guān)系。則稱(chēng)為R的對(duì)稱(chēng)閉包。23. 樹(shù)：連通且無(wú)回路的無(wú)向圖稱(chēng)為樹(shù)。25. 命題公式的對(duì)偶式：命題公式A中含聯(lián)結(jié)詞，將互換，T與F互換所得公式A*稱(chēng)為A的對(duì)偶式。B(y))，其中R(3)= B(4)=T，R(4)= B(3)=F，且論域是{3, 4}，求該式的真值。B(y)) 219。B(3)) 217。B(4)) 219。F) 217。T) 219。2． 如果我有時(shí)間，我就來(lái)看你。5． 別講話(huà)了！6． 小王和小李是同學(xué)。3. 試求公式：P217。Q ) 的析取范式和合取范式。(P 174。 P217。P218。 (P217。P) 218。Q) 析取范式 4. 設(shè)A是18的除1以外的正因數(shù)組成的集合，“|”為整除關(guān)系，畫(huà)出（A，|）的哈斯圖；若存在的話(huà)，分別求出其最大元、最小元，極大元，極小元，上確界，下確界，上界和下界。5. 求表達(dá)式：(a+bc)247。解： 6. 在一階邏輯中，將下面命題符號(hào)化，并且要求只能使用全稱(chēng)量詞：（1） 沒(méi)有人長(zhǎng)著綠色頭發(fā)。解：（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的路各有幾條。8. 設(shè)的關(guān)系為：，求以及。試找出G的所有子群。解：11. 在一階邏輯中，將下面命題符號(hào)化，并且要求只能使用全稱(chēng)量詞：（1） 沒(méi)有人長(zhǎng)著綠色頭發(fā)。解：（1）設(shè)M（x）：x是人，B（x）：x長(zhǎng)著綠色頭發(fā)則命題（1）可表示為：（2）設(shè)M（x）：x是上海市民，B（x）：x去過(guò)東方明珠塔； 則命題（2）可表示為：12. 設(shè)是上的整除關(guān)系。 解：（1）R={1,1,1,3,1,4,1,12,1,24,3,3,3,12,3,24,4,4,4,12,4,24,12,12,12,24,24,24}（2）畫(huà)出哈斯圖得2分。13. 求的主析取范式和主合取范式。（1）已知，問(wèn)嗎？（2）已知，問(wèn)嗎？解：（1）設(shè)有某種指派，使公式的真值為，但的真值為，的真值為，則和的真值為，故成立，但不一定成立。16. 畫(huà)出符合下列條件的圖（1） 畫(huà)一個(gè)有一條歐拉回路和一條漢密爾頓回路的圖。（3） 畫(huà)一個(gè)沒(méi)有一條歐拉回路，但有一條漢密爾頓回路的圖。答：(1). A1是X的一個(gè)覆蓋，但不是X的一個(gè)劃分；A2不是X的一個(gè)覆蓋； A3是X的一個(gè)劃分。19. 設(shè) X={a,b,c} 上關(guān)系 R={a,b,a,c,b,c} , 求R的自反閉包 r(R) , 對(duì)稱(chēng)閉包 s(R) , 和傳遞閉包 t(R) 。s(R)={a,b,a,c,b,a,b,c,c,a,c,b}。解：(1). R={1,1,1,2,1,3,1,5,1,6,1,12,2,2,2,6,2,12,3,3,3,6, 3,12, 5,5, 6,6,6,12,12,12} (2). (X,R)的哈斯圖為：(3). X無(wú)最大元； 有最小元1； 極大元5,12； 極小元1. 21. 設(shè)，其上關(guān)系為，寫(xiě)出關(guān)系中的各元素，并求出dom, ran及。(1). 運(yùn)算*滿(mǎn)足結(jié)合律嗎？(2). R,*有單位元e，求e。 因?yàn)?滿(mǎn)足交換律，所以右單位元就是單位元，元素的右逆元就是該元素的逆元。當(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)的圖。解：dom，（1分）ran，（1分）。 解：26. 將公式化為只含聯(lián)結(jié)詞、∨、∧的等價(jià)公式。如取，則。（1） （2）解：（1） 李華乘坐火車(chē)并且在看書(shū)，但沒(méi)有思考問(wèn)題。30. 求公式 ┐(P∨ ┐Q)∧(P → Q) 的主析取范式和主合取范式。 五、 證明題1． 證明：(P174。 (Q174。 (P217。R。R) 218。R) 219。P218。(216。R) 219。P218。Q)218。(216。Q)218。 (P217。R 2． 證明：證明： 而所以 3． 證明：n個(gè)頂點(diǎn)的樹(shù)T，其頂點(diǎn)度數(shù)之和為2n2。4． 設(shè)函數(shù)；若是滿(mǎn)射的，則是滿(mǎn)射的。證明：K, *是G, *的子群。H，且為H, *的幺元；又因?yàn)镵, *是H, *的子群，所以H, *的幺元e206。此外，對(duì)任意a, b206。K，a1206。綜上所述，由定理K, *是G, *的子群。7． 用CP規(guī)則證明證明： （1） （附加前提）（2） （3） （4） （5） （6） 8． 形式化下命題，并用推理規(guī)則證明其結(jié)論每一個(gè)自然數(shù)不是奇數(shù)就是偶數(shù)；自然數(shù)是偶數(shù)當(dāng)且僅當(dāng)它能被2整除；并不是所有自然數(shù)都能被2整除。證明：(x )( ┐ A(x) →B(x) ) , (x ) ┐B(x) 222。證明：設(shè)G=V,E，|V|=v，|E|=,若每一個(gè)結(jié)點(diǎn)的度數(shù)≥6, 又（2分） ∴2≥6v ，所以≥3v＞3v6， 與＜3v6矛盾10． 設(shè)（G，*）是一個(gè)群，定義關(guān)系R是GG的子集，其中R={(a,b)|c∈G,使b=c*a*c1 }. 試證R是G上的等價(jià)關(guā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, 滿(mǎn)足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傳遞。 另一方面，(x,y) (AC) (BC)，有 (x,y) AC，(x,y) BC，即 xA，yC， xB，于是 (x,y) (A B)C，因此 (AC) (BC) (A B)C。12． 設(shè)為模4剩余類(lèi)的集合，為模4加法，寫(xiě)出的運(yùn)算表并證明為群。因此，（Z4,+4）為群13． 證明前提P∨Q, P→R, Q→S 的結(jié)論是S∨R.證：(1). P∨Q P (2). P→Q T,(1),E (3). Q→S P (4). P→S T,(2),(3),I (5). S→P T,(4),E (6). P→R P (7). S→R T,(5),(6),I (8). S∨R T,(7),E 14． 符號(hào)化證明 人總是要死的，蘇格拉底是人，因此，蘇格拉底是要死的。證明：（1），即自反； （2）從而，即是對(duì)稱(chēng)的；（3），從而可得出，即是傳遞的；綜上所述，是上的等