【正文】 （原公式否定的主析取范式）（PR）Q(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）1（PQ）R解：（PQ）R(PQ)R(PQ)R(析取范式)(PQ(RR))((PP)()R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式）（PQ）R(PQ)R(PQ)R(析取范式)(PR)(QR)(合取范式)(P()R)((PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主合取范式)1(P(QR))(P(QR))解：(P(QR))(P(QR))(P(QR))(P(QR))(PQ)(PR)(PQ)(PR)（合取范式）(PQ(RR))(P()R)(PQ(RR))(P()R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主合取范式)(P(QR))(P(QR))(PQR)(PQR)(原公式否定的主合取范式)(P(QR))(P(QR))(PQR)(PQR)(主析取范式)1P(P(Q(QR)))解：P(P(Q(QR))) P(P(Q(QR))) PQR(主合取范式)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(原公式否定的主合取范式)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)1(PQ)(PR)解、(PQ)(PR)(PQ)(PR) (合取范式)(PQ(RR)(P()R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主合取范式)(PQ)(PR)(PQ)(PR)P(QR)(合取范式)(P()(RR))((PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)三、證明：P→Q，QR，R，SP=S證明：(1) R 前提(2) QR 前提(3) Q （1），（2）(4) P→Q 前提(5) P （3），（4）(6) SP 前提(7) S （5），（6）A→(B→C)，C→(DE)，F(xiàn)→(DE),A=B→F證明： (1) A 前提(2) A→(B→C) 前提 (3) B→C （1），（2）(4) B 附加前提(5) C （3），（4）(6) C→(DE) 前提(7) DE （5），（6）(8) F→(DE) 前提(9) F （7），（8）(10) B→F CP PQ， P→R, Q→S = RS證明：(1) R 附加前提(2) P→R 前提(3) P （1），（2）(4) PQ 前提(5) Q （3），（4）(6) Q→S 前提(7) S （5），（6）(8) RS CP，（1），（8）(P→Q)(R→S)，(Q→W)(S→X)，(WX)，P→R = P證明： （1） P 假設(shè)前提（2） P→R 前提（3） R （1），（2）（4） (P→Q)(R→S) 前提（5） P→Q （4）（6） R→S （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à)的。(1) 最多有n1條　　(2) 至少有n1 條(3) 最多有n條 　　(4) 至少有n 條答：（2）7一棵樹有2個(gè)2度頂點(diǎn)，1 個(gè)3度頂點(diǎn)，3個(gè)4度頂點(diǎn)，則其1度頂點(diǎn)為（ ）。答：無簡單回路7設(shè)無向圖G有16條邊且每個(gè)頂點(diǎn)的度數(shù)都是2，則圖G有( )個(gè)頂點(diǎn)。答：（3）6設(shè)T=〈V,E〉是一棵樹，若|V|1，則T中至少存在( )片樹葉。答：2n2（結(jié)點(diǎn)度數(shù)的定義）6下面給出的集合中，哪一個(gè)不是前綴碼( )。(1) 0　　(2) 1　　(3) 2　　(4) 不能確定答：15n階無向完全圖Kn 的邊數(shù)是( )，每個(gè)結(jié)點(diǎn)的度數(shù)是( )。(1) 偶數(shù)　(2) 奇數(shù) (3) 4的倍數(shù) 　(4) 2的正整數(shù)次冪答：(4)（圖論部分）5設(shè)G是一個(gè)哈密爾頓圖，則G一定是( )。答：1，單位元，04在一個(gè)群〈G,*〉中，若G中的元素a的階是k，則a1的階是( )。任取一個(gè)非單位元，它的階等于p，所以它生成的G的循環(huán)子群的階也是p，從而等于整個(gè)群G。答：單位元，1 （在群G,*中，除幺元即單位元e外不可能有任何別的冪等元）4素?cái)?shù)階群一定是( )群, 它的生成元是( )。答： （1） ab （2） b （考查群的性質(zhì)，即群滿足消去律）設(shè)a是12階群的生成元， 則a2是( )階元素，a3是( )階元素。(1) 自反的　　(2) 對稱的　　 (3) 傳遞的，對稱的 (4) 傳遞的答：（2）（考查自反 對稱 傳遞的定義）（代數(shù)系統(tǒng)部分）3設(shè)A={2,4,6}，A上的二元運(yùn)算*定義為：a*b=max{a,b}，則在獨(dú)異點(diǎn)A,*中，單位元是( )，零元是( )。答：RR ={〈1,1〉，〈1,3〉，〈2,2〉，〈2,4〉}（考查FG ={x,y|$t(x,t∈F217。答：（2）2設(shè)A∩B=A∩C，∩B=∩C，則B(　)C。(1) {a}P(A)　(2) {a}P(A)　(3) {{a}}P(A)