【正文】 5）（7） Q （1），（5）（8） S （3），（6）（9） (Q→W)(S→X) 前提（10） Q→W （9）（11） S→X （10）（12） W （7），（10）（13） X （8），（11）（14） WX （12），（13）（15） (WX) 前提（16） (WX)(WX) （14），（15）(UV)→(MN), UP, P→(QS)，QS =M 證明：(1) QS 附加前提（2） P→(QS) 前提 （3） P （1），（2）（4） UP 前提（5） U （3），（4）（6） UV （5）（7） (UV)→(MN) 前提 （8） MN (6),(7)（9） M （8）BD，(E→F)→D，E=B證明：(1) B 附加前提(2) BD 前提 (3) D （1），（2）(4) (E→F)→D 前提(5) (E→F) （3），（4）(6) EF （5）(7) E （6）(8) E 前提(9) EE （7），（8）P→(Q→R)，R→(Q→S) = P→(Q→S)證明：（1） P 附加前提（2） Q 附加前提（3） P→(Q→R) 前提（4） Q→R （1），（3）（5） R （2），（4）（6） R→(Q→S) 前提（7） Q→S （5），（6）（8） S （2），（7）（9） Q→S CP，（2），（8）（10） P→(Q→S) CP，（1），（9）P→Q，P→R，R→S =S→Q 證明：（1） S 附加前提（2） R→S 前提（3） R （1），（2）（4） P→R 前提（5） P （3），（4）（6） P→Q 前提（7） Q (5），（6）（8） S→Q CP，（1），（7）P→(Q→R) = (P→Q)→(P→R)證明：(1) P→Q 附加前提(2) P 附加前提(3) Q (1),(2)(4) P→(Q→R) 前提(5) Q→R (2),(4)(6) R (3),(5)(7) P→R CP,(2),(6)(8) (P→Q) →(P→R) CP,(1),(7)P→(Q→R)，Q→P,S→R,P =S證明：（1） P 前提（2） P→(Q→R) 前提（3） Q→R (1)，(2)（4） Q→P 前提（5） Q (1)，(4)（6） R (3),(5)（7） S→R 前提（8） S (6)，(7)1A，A→B， A→C， B→(D→C) = D證明：（1） A 前提（2） A→B 前提（3） B (1)，(2)（4） A→C 前提（5） C (1)，(4)（6） B→(D→C) 前提（7） D→C (3)，(6)（8） D (5)，(7)1A→(CB)，B→A，D→C = A→D證明：（1） A 附加前提(2) A→(CB) 前提 (3) CB （1），（2）(4) B→A 前提(5) B （1），（4）(6) C （3），（5）(7) D→C 前提(8) D （6），（7）(9) A→D CP，（1），（8）1(PQ)(RQ) （PR）Q證明、(PQ)(RQ) (PQ)(RQ)(PR)Q （PR）Q(PR)Q1P(QP)P(PQ)證明、P(QP)P(QP)(P)(PQ)P(PQ)1（PQ）（PR），(QR)，SPS證明、(1) （PQ）（PR） 前提 （2） P (QR) (1) （3） (QR) 前提 （4） P （2），(3) (5) SP 前提 (6) S (4),(5)1PQ，QR，RS P證明、(1) P 附加前提 （2） PQ 前提 （3） Q （1），（2） （4） QR 前提 (5) R （3），（4） (6 ) RS 前提 （7） R （6） （8） RR （5），（7）1用真值表法證明ＰＱ (ＰＱ)(ＱＰ)證明、列出兩個(gè)公式的真值表：P Q PQ （PQ）（QP） F FF TT FT TT TF FF FT T由定義可知，這兩個(gè)公式是等價(jià)的。答：無簡(jiǎn)單回路7設(shè)無向圖G有16條邊且每個(gè)頂點(diǎn)的度數(shù)都是2，則圖G有( )個(gè)頂點(diǎn)。答：2n2（結(jié)點(diǎn)度數(shù)的定義）6下面給出的集合中，哪一個(gè)不是前綴碼( )。(1) 偶數(shù)　(2) 奇數(shù) (3) 4的倍數(shù) 　(4) 2的正整數(shù)次冪答：(4)（圖論部分）5設(shè)G是一個(gè)哈密爾頓圖，則G一定是( )。任取一個(gè)非單位元，它的階等于p，所以它生成的G的循環(huán)子群的階也是p，從而等于整個(gè)群G。答： （1） ab （2） b （考查群的性質(zhì)，即群滿足消去律）設(shè)a是12階群的生成元， 則a2是( )階元素，a3是( )階元素。答：RR ={〈1,1〉，〈1,3〉，〈2,2〉，〈2,4〉}（考查FG ={x,y|$t(x,t∈F217。(1) {a}P(A)　(2) {a}P(A)　(3) {{a}}P(A)　(4) {{a}}P(A)答：(2) （{a}是P（A）的一個(gè)元素）1在0（ ）之間寫上正確的符號(hào)。答：2不是偶數(shù)且3不是負(fù)數(shù)。 (2) 陜西師大是一座工廠。B(y，x))217。于是A(x)、B(y，x)和$z C(y，z)中y為自由變?cè)瑇和z為約束變?cè)?，在D(x)中x為自由變?cè)┡袛嘞铝姓Z句是不是命題。(1)　只有在生病時(shí)，我才不去學(xué)校 (2) 若我生病，則我不去學(xué)校(3)　當(dāng)且僅當(dāng)我生病時(shí)，我才不去學(xué)校(4) 若我不生病，則我一定去學(xué)校答：（1） （注意“只有……才……”和“除非……就……”兩者都是一個(gè)形式的） （2） （3） （4）設(shè)個(gè)體域?yàn)檎麛?shù)集，則下列公式的意義是( )。 $yR(y)（一對(duì)括號(hào)就是一個(gè)轄域）1令R(x):x是實(shí)數(shù)，Q(x):x是有理數(shù)。答：=（等于）2判斷下列命題哪幾個(gè)正確？(　　　　　)(1) 若A∪B＝A∪C，則B＝C (2) {a,b}={b,a} (3) P(A∩B)P(A)∩P(B) （P(S)表示S的冪集）(4) 若A為非空集，則AA∪A成立。答：2，6（單位元和零元的定義，單位元：e。答：循環(huán)群，任一非單位元（證明如下：任一元素的階整除群的階。答：k4在自然數(shù)集N上，下列哪種運(yùn)算是可結(jié)合的？（ ） (1) a*b=ab　　(2) a*b=max{a,b}　(3) a*b=a+2b　(4) a*b=|ab|答：(2)50、任意一個(gè)具有2個(gè)或以上元的半群，它（ ）。答：, n160、一棵無向樹的頂點(diǎn)數(shù)n與邊數(shù)m關(guān)系是(　　　　)。答：26任何連通無向圖G至少有( )棵生成樹，當(dāng)且僅當(dāng)G 是( )，G的生成樹只有一棵。(1) 5　　(2) 7 (3) 8 　(4) 9答：（4）7若一棵完全二元（叉）樹有2n1個(gè)頂點(diǎn)，則它（ ）片樹葉。(P→Q)(QR) P證明：設(shè)(P→Q)(QR)為T，則P→Q和(QR)都為T。結(jié)論: (5) D隊(duì)不是亞軍。 AB= 　　證明：設(shè)A=B，則AB=（AB）（BA）==。1(AB)(AC)=ABC證明： 因?yàn)?AB)(AC) =(A)(A) =A()=A= A(BC)，且(AB)(AC)=， 所以= A(BC)，故ABC。1(AB)CA(BC)證明：x(AB)C，有AB且xC，即A，xB且xC。從而SP(A)且SP(B)，故SP(A)P(B)。故這與已知（AB）B=（AB）B矛盾。（2）對(duì)每個(gè)自然數(shù)x，存在自然數(shù)y滿足xy=1。（2）xz是xy且yz的必要條件。(3) R={1,1,1,1,2,2,3,3}。對(duì), x,xBB。從而AC =。故BC。（3） (AB)2={a,c,a,c,a,c,b,c,b,c,a,c,b,c,b,c}。 (2) ={a,b,c,d,e}。又因?yàn)锽C，所以xC。(4) 成立。　證明：a∈A，因?yàn)镽和S都是A上的等價(jià)關(guān)系，所以xRx且xSx。因?yàn)镽和S都是A上的等價(jià)關(guān)系，所以aRc且aSc。即xRx，故R是自反的。故R=R1。同理可證（RS）（RT）R(ST)。是A上的偏序關(guān)系，a=b。它既不是自反的、反自反的、也不是對(duì)稱的、反對(duì)稱的、傳遞的。解：R誘導(dǎo)的劃分為{{1,5},{2,4},{3,6}}。(b)的極大元為b,d,極小元為b,d。上確界是e，下確界是c。因?yàn)閨e|=1,|a|=|a3|=|a5|=8,|a2|=|a6|=8, |a4|=2,且G 的子群的生成元是該子群中a的最小正冪，故G的所有子群除兩個(gè)平凡子群外，還有{e,a4},{e,a2,a4,a6}。2設(shè)G,c,d(a從而c故c1H。是有限群，則aG，有|a|=|a1|。b=ba。a=(a2a)a2=((aa2=ba4。對(duì)aI，a*2=a+22=a=2+a2=2*a.。試證Sa,cSa，即Sa關(guān)于運(yùn)算因?yàn)閑是關(guān)于運(yùn)算的單位元，所以e1=e1*e=e=e2*e=e2。即e0。3證明在一個(gè)群中單位元是惟一的。3在一個(gè)偶數(shù)階群中一定存在一個(gè)2階元素。證明：設(shè)e是該群的單位元。即ax1=b且ax2=b。b2。b=(a(bb)=(a(ab)，即(b故（3） a,b,cA,a*b*c=a*c。從而由已知條件知，a*b*c=a*c。f(a))1=(f(b故f是G到G上的滿函數(shù)。故f滿足同態(tài)方程。故H是G的不變子群。a1，ha}。故（ab=(xb，a1C（G）。h) 是沒有非平凡子群的有限群。若n是合數(shù)，則存在大于1 的整數(shù)k,m，使得n=mk。證明：用反證法證明。從而a由拉格朗日定理，k是p的正整因子。4設(shè)G,是群，且a∈G的階為n，k∈I，則|ak|＝，其中(k,n)為k和n的最大公因子。即｜ak｜＝。從而c= (cm)k= cmk。因?yàn)閎,amH, 且HG，所以arH。證明：對(duì)n 的每一正因子d，令k=,b=ak, H={e,b,b2,…,bd1}。從而H是G的惟一d階子群。(2) a∈G1，h(a)h(a1)=h(aa1)= h(e1)= e2,h(a1)h(a)=h(a1a)= h(e1)= e2,故h(a1)=h(a)1。從而h(