2023年新版離散數(shù)學題庫及答案

《離散數(shù)學》題庫答案一、選擇或填空（數(shù)理邏輯部分）1、下列哪些公式為永真蘊含式？()(1)Q=>Q→P(2)Q=>P→Q(3)P=>P→Q(4)P(PQ)=>P答：（1），（4）2、下列公式中哪些是永真式？()(1)(┐PQ)→(Q→R)(2)P→(Q→Q)(3)(PQ)→P(4)P→(PQ)答：（2），（3），（4）3、設有下列公式，請問哪幾個是永真蘊涵式?()(1)P=>PQ(2)PQ=>P(3)PQ=>PQ(4)P(P→Q)=>Q(5)(P→Q)=>P(6)P(PQ)=>P答：（2），（3），（4），（5），（6）4、公式x((A(x)B(y，x))zC(y，z))D(x)中，自由變元是()，約束變元是()。答：x,y,x,z5、判斷下列語句是不是命題。若是，給出命題的真值。()北京是中華人民共和國的首都。(2)陜西師大是一座工廠。(3)你喜歡唱歌嗎？(4)若7+8＞18，則三角形有4條邊。(5)前進！(6)給我一杯水吧！答：（1）是，T（2）是，F(xiàn)（3）不是（4）是，T（5）不是（6）不是6、命題“存在一些人是大學生”的否認是()，而命題“所有的人都是要死的”的否認是()。答：所有人都不是大學生，有些人不會死7、設P：我生病，Q：我去學校，則下列命題可符號化為()。(1)只有在生病時，我才不去學校(2)若我生病，則我不去學校(3)當且僅當我生病時，我才不去學校(4)若我不生病，則我一定去學校答：（1）（2）（3）（4）8、設個體域為整數(shù)集，則下列公式的意義是()。(1)xy(x+y=0)(2)yx(x+y=0)答：（1）對任一整數(shù)x存在整數(shù)y滿足x+y=0（2）存在整數(shù)y對任一整數(shù)x滿足x+y=09、設全體域D是正整數(shù)集合，擬定下列命題的真值：(1)xy(xy=y)()(2)xy(x+y=y)()(3)xy(x+y=x)()(4)xy(y=2x)()答：（1）F（2）F（3）F（4）T10、設謂詞P(x)：x是奇數(shù)，Q(x)：x是偶數(shù)，謂詞公式x(P(x)Q(x))在哪個個體域中為真?()(1)自然數(shù)(2)實數(shù)(3)復數(shù)(4)(1)--(3)均成立答：（1）11、命題“2是偶數(shù)或-3是負數(shù)”的否認是（）。答：2不是偶數(shù)且-3不是負數(shù)。12、永真式的否認是（）(1)永真式(2)永假式(3)可滿足式(4)(1)--(3)均有也許答：（2）13、公式(PQ)(PQ)化簡為（），公式Q(P(PQ))可化簡為（）。答：P，QP14、謂詞公式x(P(x)yR(y))Q(x)中量詞x的轄域是（）。答：P(x)yR(y)15、令R(x):x是實數(shù)，Q(x):x是有理數(shù)。則命題“并非每個實數(shù)都是有理數(shù)”的符號化表達為（）。答：x(R(x)Q(x))（集合論部分）16、設A={a,{a}}，下列命題錯誤的是（）。(1){a}P(A)(2){a}P(A)(3){{a}}P(A)(4){{a}}P(A)答：(2)17、在0（）之間寫上對的的符號。(1)=(2)(3)(4)答：(4)18、若集合S的基數(shù)|S|=5，則S的冪集的基數(shù)|P(S)|=（）。答：3219、設P={x|(x+1)4且xR},Q={x|5x+16且xR},則下列命題哪個對的（）(1)QP(2)QP(3)PQ(4)P=Q答：（3）20、下列各集合中，哪幾個分別相等()。(1)A1={a,b}(2)A2={b,a}(3)A3={a,b,a}(4)A4={a,b,c}(5)A5={x|(x-a)(x-b)(x-c)=0}(6)A6={x|x2-(a+b)x+ab=0}答：A1=A2=A3=A6，A4=A521、若A-B=Ф，則下列哪個結論不也許對的？()(1)A=Ф(2)B=Ф(3)AB(4)BA答：（4）22、判斷下列命題哪個為真?()(1)A-B=B-A=>A=B(2)空集是任何集合的真子集(3)空集只是非空集合的子集(4)若A的一個元素屬于B，則A=B答：（1）23、判斷下列命題哪幾個為對的？()(1){Ф}∈{Ф,{{Ф}}}(2){Ф}{Ф,{{Ф}}}(3)Ф∈{{Ф}}(4)Ф{Ф}(5){a,b}∈{a,b,{a},}答：（2），（4）24、判斷下列命題哪幾個對的？()(1)所有空集都不相等(2){Ф}Ф(4)若A為非空集，則AA成立。答：（2）25、設A∩B=A∩C，∩B=∩C，則B()C。答：=（等于）26、判斷下列命題哪幾個對的？()(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）27、Ａ，Ｂ，Ｃ是三個集合，則下列哪幾個推理對的：(1)AB，BC=>AC(2)AB，BC=>A∈B(3)A∈B，B∈C=>A∈C答：（1）（二元關系部分）28、設Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，從Ａ到B的關系Ｒ＝｛〈x,y〉|x=y2｝，求(1)R(2)R-1。答：（1）R={<1,1>,<4,2>}(2)R={<1,1>,<2,4>}29、舉出集合A上的既是等價關系又是偏序關系的一個例子。()答：A上的恒等關系30、集合A上的等價關系的三個性質是什么？()答：自反性、對稱性和傳遞性31、集合A上的偏序關系的三個性質是什么？()答：自反性、反對稱性和傳遞性32、設S={１,２,３,４}，Ａ上的關系Ｒ＝｛〈1,2〉，〈2,1〉，〈2,3〉，〈3,4〉｝求(1)RR(2)R-1。答：RR={〈1,1〉，〈1,3〉，〈2,2〉，〈2,4〉}R-1=｛〈2,1〉，〈1,2〉，〈3,2〉，〈4,3〉｝33、設Ａ＝｛1，2，3，4，5，6｝，Ｒ是A上的整除關系，求R={()}。答：R={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,4>,<2,6>,<3,6>}34、設Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，從Ａ到B的關系Ｒ＝｛〈x,y〉|x=2y｝，求(1)R(2)R-1。答：（1）R={<1,1>,<4,2>,<6,3>}(2)R={<1,1>,<2,4>,(36>}35、設Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，從Ａ到B的關系Ｒ＝｛〈x,y〉|x=y2｝，求R和R-1的關系矩陣。答：R的關系矩陣=R的關系矩陣=36、集合A={1,2,…,10}上的關系R={<x,y>|x+y=10,x,yA}，則R的性質為（）。(1)自反的(2)對稱的(3)傳遞的，對稱的(4)傳遞的答：（2）（代數(shù)結構部分）37、設A={2,4,6}，A上的二元運算*定義為：a*b=max{a,b}，則在獨異點<A,*>中，單位元是()，零元是()。答：2，638、設A={3,6,9}，A上的二元運算*定義為：a*b=min{a,b}，則在獨異點<A,*>中，單位元是()，零元是()；答：9，3（半群與群部分）39、設〈G,*〉是一個群，則(1)若a,b,x∈G，ax=b，則x=()；(2)若a,b,x∈G，ax=ab，則x=()。答：（1）ab（2）b40、設a是12階群的生成元，則a2是()階元素，a3是()階元素。答：6,441、代數(shù)系統(tǒng)<G,*>是一個群，則G的等冪元是()。答：單位元42、設a是10階群的生成元，則a4是()階元素，a3是()階元素。答：5，1043、群<G,*>的等冪元是()，有()個。答：單位元，144、素數(shù)階群一定是()群,它的生成元是()。答：循環(huán)群，任一非單位元45、設〈G,*〉是一個群，a,b,c∈G，則(1)若ca=b，則c=()；(2)若ca=ba，則c=()。答：（1）b(2)b46、<H,,>是<G,,>的子群的充足必要條件是()。答：<H,,>是群或a，bG，abH，a-1H或a,bG，ab-1H47、群＜A,*＞的等冪元有()個，是()，零元有()個。答：1，單位元，048、在一個群〈G,*〉中，若G中的元素a的階是k，則a-1的階是()。答：k49、在自然數(shù)集N上，下列哪種運算是可結合的？（）(1)a*b=a-b(2)a*b=max{a,b}(3)a*b=a+2b(4)a*b=|a-b|答：(2)50、任意一個具有2個或以上元的半群，它（）。(1)不也許是群(2)不一定是群(3)一定是群(4)是互換群答：(1)51、6階有限群的任何子群一定不是（）。(1)2階(2)3階(3)4階(4)6階答：(3)（格與布爾代數(shù)部分）52、下列哪個偏序集構成有界格（）(1)（N,）(2)（Z,）(3)（{2,3,4,6,12},|（整除關系））(4)(P(A),)答：(4)53、有限布爾代數(shù)的元素的個數(shù)一定等于（）。(1)偶數(shù)(2)奇數(shù)(3)4的倍數(shù)(4)2的正整數(shù)次冪答：(4)（圖論部分）54、設G是一個哈密爾頓圖，則G一定是()。(1)歐拉圖(2)樹(3)平面圖(4)連通圖答：(4)55、下面給出的集合中，哪一個是前綴碼？()(1){0，10，110，101111}(2){01，001，000，1}(3){b，c，aa，ab，aba}(4){1，11，101，001，0011}答：（2）56、一個圖的哈密爾頓路是一條通過圖中()的路。答：所有結點一次且恰好一次57、在有向圖中，結點v的出度deg+(v)表達()，入度deg-(v)表達()。答：以v為起點的邊的條數(shù)，以v為終點的邊的條數(shù)58、設G是一棵樹，則G的生成樹有()棵。(1)0(2)1(3)2(4)不能擬定答：159、n階無向完全圖Kn的邊數(shù)是()，每個結點的度數(shù)是()。答：,n-160、一棵無向樹的頂點數(shù)n與邊數(shù)m關系是()。答：m=n-161、一個圖的歐拉回路是一條通過圖中()的回路。答：所有邊一次且恰好一次62、有n個結點的樹，其結點度數(shù)之和是()。答：2n-263、下面給出的集合中，哪一個不是前綴碼()。(1){a，ab，110，a1b11}(2){01，001，000，1}(3){1，2，00，01，0210}(4){12，11，101，002，0011}答：(1)64、n個結點的有向完全圖邊數(shù)是()，每個結點的度數(shù)是()。答：n(n-1),2n-265、一個無向圖有生成樹的充足必要條件是()。答：它是連通圖66、設G是一棵樹，n,m分別表達頂點數(shù)和邊數(shù)，則(1)n=m(2)m=n+1(3)n=m+1(4)不能擬定。答：（3）67、設T=〈V,E〉是一棵樹，若|V|>1，則T中至少存在()片樹葉。答：268、任何連通無向圖G至少有()棵生成樹，當且僅當G是()，G的生成樹只有一棵。答：1，樹69、設G是有n個結點m條邊的連通平面圖，且有k個面，則k等于:(1)m-n+2(2)n-m-2(3)n+m-2(4)m+n+2。答：（1）70、設T是一棵樹，則T是一個連通且()圖。答：無簡樸回路71、設無向圖G有16條邊且每個頂點的度數(shù)都是2，則圖G有()個頂點。(1)10(2)4(3)8(4)16答：（4）72、設無向圖G有18條邊且每個頂點的度數(shù)都是3，則圖G有()個頂點。(1)10(2)4(3)8(4)12答：(4)73、設圖G=<V，E>，V={a，b，c，d，e}，E={<a,b>,<a,c>,<b,c>,<c,d>,<d,e>},則G是有向圖還是無向圖？答：有向圖74、任一有向圖中，度數(shù)為奇數(shù)的結點有()個。答：偶數(shù)75、具有6個頂點，12條邊的連通簡樸平面圖中，每個面都是由()條邊圍成？(1)2(2)4(3)3(4)5答：（3）76、在有n個頂點的連通圖中，其邊數(shù)（）。(1)最多有n-1條(2)至少有n-1條(3)最多有n條(4)至少有n條答：（2）77、一棵樹有2個2度頂點，1個3度頂點，3個4度頂點，則其1度頂點為（）。(1)5(2)7(3)8(4)9答：（4）78、若一棵完全二元（叉）樹有2n-1個頂點，則它（）片樹葉。(1)n(2)2n(3)n-1(4)2答：（1）79、下列哪一種圖不一定是樹（）。(1)無簡樸回路的連通圖(2)有n個頂點n-1條邊的連通圖(3)每對頂點間都有通路的圖(4)連通但刪去一條邊便不連通的圖答：（3）80、連通圖G是一棵樹當且僅當G中（）。(1)有些邊是割邊(2)每條邊都是割邊(3)所有邊都不是割邊(4)圖中存在一條歐拉途徑答：（2）（數(shù)理邏輯部分）二、求下列各公式的主析取范式和主合取范式：1、(P→Q)R解：(P→Q)R(PQ)R(PR)(QR)（析取范式）(P(QQ)R)((PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）((P→Q)R)(PQR)(PQR)(PQR)(PQR)(PQR)（原公式否認的主析取范式）(P→Q)R(PQR)(PQR)(PQR)(PQR)(PQR)（主合取范式）2、(PR)(QR)P解：(PR)(QR)P（析取范式）(P(QQ)R)((PP)QR)(P(QQ)(RR))(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)（(PR)(QR)P）(PQR)(PQR）（原公式否認的主析取范式）(PR)(QR)P(PQR)(PQR)（主合取范式）3、(P→Q)(RP)解：(P→Q)(RP)(PQ)(RP)（合取范式）(PQ(RR))(P(QQ))R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（主合取范式）((P→Q)(RP))(PQR)(PQR)(PQR)(PQR)(PQR)（原公式否認的主合取范式）(P→Q)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）4、Q→(PR)解：Q→(PR)QPR（主合取范式）（Q→(PR)）(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR）（原公式否認的主合取范式）Q→(PR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR）（主析取范式）5、P→(P(Q→P))解：P→(P(Q→P))P(P(QP))PPT(主合取范式)(PQ)(PQ)(PQ)(PQ)（主析取范式）6、(P→Q)(RP)解：(P→Q)(RP)(PQ)(RP)(PQ)(RP)（析取范式）(PQ(RR))(P(QQ)R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）((P→Q)(RP))(PQR)(PQR)(PQR) (PQR)(PQR)（原公式否認的主析取范式）(P→Q)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)（主合取范式）7、P(P→Q)解：P(P→Q)P(PQ)(PP)QT(主合取范式)(PQ)(PQ)(PQ)(PQ)（主析取范式）8、(R→Q)P解：(R→Q)P(RQ)P (RP)(QP)（析取范式） (R(QQ)P)((RR)QP)(RQP)(RQP)(RQP)(RQP)(PQR)(PQR)(PQR)（主析取范式）((R→Q)P)(PQR)(PQR）(PQR)(PQR)(PQR)（原公式否認的主析取范式）(R→Q)P(PQR)(PQR)(PQR)(PQR)(PQR)（主合取范式）9、P→Q解：P→QPQ（主合取范式）(P(QQ))((PP)Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)（主析取范式）10、PQ解：PQ（主合取范式）(P(QQ))((PP)Q）(PQ)(PQ)(PQ)(PQ）(PQ)(PQ)(PQ)（主析取范式）11、PQ解：PQ（主析取范式）(P(QQ))((PP)Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)（主合取范式）12、（PR）Q解：（PR）Q(PR)Q(PR)Q(PQ)(RQ)（合取范式）(PQ(RR))((PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（主合取范式）（PR）Q(PQR)(PQR)(PQR)(PQR)(PQR)（原公式否認的主析取范式）（PR）Q(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）13、（PQ）R解：（PQ）R(PQ)R(PQ)R(析取范式)(PQ(RR))((PP)(QQ)R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式）（PQ）R(PQ)R(PQ)R(析取范式)(PR)(QR)(合取范式)(P(QQ)R)((PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主合取范式)14、(P(QR))(P(QR))解：(P(QR))(P(QR))(P(QR))(P(QR))(PQ)(PR)(PQ)(PR)（合取范式）(PQ(RR))(P(QQ)R)(PQ(RR))(P(QQ)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)(主析取范式)15、P(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)(主析取范式)16、(PQ)(PR)解、(PQ)(PR)(PQ)(PR)(合取范式)(PQ(RR)(P(QQ)R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主合取范式)(PQ)(PR)(PQ)(PR)P(QR)(合取范式)(P(QQ)(RR))((PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)三、證明：1、P→Q，QR，R，SP=>S證明：(1)R前提(2)QR前提Q（1），（2）P→Q前提P（3），（4）SP前提(7)S（5），（6）2、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附加前提C（3），（4）C→(DE)前提DE（5），（6）F→(DE)前提F（7），（8）B→FCP3、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)RSCP，（1），（8）4、(P→Q)(R→S)，(Q→W)(S→X)，(WX)，P→R=>P證明：（1）P假設前提（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）5、(UV)→(MN),UP,P→(QS)，QS=>M證明：(1)QS附加前提P→(QS)前提P（1），（2）UP前提U（3），（4）UV（5）(UV)→(MN)前提MN(6),(7)M（8）6、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）7、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→SCP，（2），（8）（10）P→(Q→S)CP，（1），（9）8、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→QCP，（1），（7）9、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→RCP,(2),(6)(8)(P→Q)→(P→R)CP,(1),(7)10、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)11、A，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)12、A→(CB)，B→A，D→C=>A→D證明：（1）A附加前提(2)A→(CB)前提(3)CB（1），（2）B→A前提B（1），（4）C（3），（5）D→C前提D（6），（7）A→DCP，（1），（8）13、(PQ)(RQ)（PR）Q證明、(PQ)(RQ)(PQ)(RQ)(PR)Q（PR）Q(PR)Q14、P(QP)P(PQ)證明、P(QP)P(QP)(P)(PQ)P(PQ)15、（PQ）（PR），(QR)，SPS證明、(1)（PQ）（PR）前提（2）P(QR)(1)（3）(QR)前提（4）P（2），(3)(5)SP前提(6)S(4),(5)16、PQ，QR，RSP證明、(1)P附加前提（2）PQ前提（3）Q（1），（2）（4）QR前提(5)R（3），（4）(6)RS前提（7）R（6）（8）RR（5），（7）17、用真值表法證明ＰＱ(ＰＱ)(ＱＰ)證明、列出兩個公式的真值表：PQPQ（PQ）（QP）FFFTTFTTTTFFFFTT由定義可知，這兩個公式是等價的。18、P→QP→(PQ)證明、設P→(PQ)為F，則P為T，PQ為F。所以P為T，Q為F，從而P→Q也為F。所以P→QP→(PQ)。19、用先求主范式的方法證明(P→Q)(P→R)(P→（QR）證明、先求出左右兩個公式的主合取范式(P→Q)(P→R)(PQ)(PR)(PQ(RR)))(P(QQ)R) (PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(P→（QR）)(P（QR）)(PQ)(PR)(PQ(RR))(P(QQ)R) (PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)它們有同樣的主合取范式，所以它們等價。20、(P→Q)(QR)P證明、設(P→Q)(QR)為T，則P→Q和(QR)都為T。即P→Q和QR都為T。故P→Q，Q和R)都為T，即P→Q為T，Q和R都為F。從而P也為F，即P為T。從而(P→Q)(QR)P21、為慶祝九七香港回歸祖國，四支足球隊進行比賽，已知情況如下，問結論是否有效?前提:(1)若A隊得第一，則B隊或C隊獲亞軍;若C隊獲亞軍，則A隊不能獲冠軍;若D隊獲亞軍，則B隊不能獲亞軍;A隊獲第一;結論:(5)D隊不是亞軍。證明、設A：A隊得第一;B:B隊獲亞軍;C:C隊獲亞軍;D:D隊獲亞軍;則前提符號化為A（BC），CA，DB，A；結論符號化為D。本題即證明A（BC），CA，DB，AD。（1）A前提（2）A（BC）前提（3）BC（1），（2）（4）CA前提（5）C（1），（4）（6）B（3），（5）（7）DB前提（8）D（6），（7）22、用推理規(guī)則證明PQ,(QR),PR不能同時為真。證明、(1)PR前提(2)P(1)(3)PQ前提(4)Q(2),(3)(5)(QR)前提(6)QR(5)(7)Q(6)(8)QQ(4),(7)(集合論部分)四、設Ａ，Ｂ，Ｃ是三個集合，證明：1、A(B－C)＝(AB)－(AC)證明：(AB)－(AC)=(AB)=(AB)（）=(AB)(AB)=AB=A（B）=A（B-C）2、(A－B)(A－C)=A－(BC)證明：(A-B)(A-C)=(A)(A)=A()=A=A-(BC)3、AB=AC，B=C，則C=B證明：B=B(A)=(B)(BA)=(C)(CA)=C(A)=C4、AB=A(B-A)證明：A(B-A)=A(B)=(AB)(A)=(AB)U=AB5、A=BAB=證明：設A=B，則AB=（A-B）（B-A）==。設AB=，則AB=（A-B）（B-A）=。故A-B=，B-A=，從而AB，BA，故A=B。6、AB=AC，AB=AC，則C=B證明：B=B(AB)=B(AC)=(BA)(BC)=(AC)(B∩C)=C(AB)=C(AC)=C7、AB=AC，B=C，則C=B證明：B=B(A)=(BA)(B)=(CA)(C)=C(A)=C8、A－(BC)＝(A－B)－C證明：A－(BC)=A=A()=(A)=(A-B)=(A-B)-C9、(A－B)(A－C)=A－(BC)證明：(A-B)(A－C)=(A)(A)=(AA)()=A=A－(BC)10、A-B=B，則A=B=證明：由于B=A-B，所以B=BB=（A-B）B=。從而A=A-B=B=。11、A=(A-B)(A-C)ABC=證明：由于(A-B)(A-C)=(A)(A)=A()=A=A-(BC)，且A=(A-B)(A-C)，所以A=A-(BC)，故ABC=。由于ABC=，所以A-(BC)=A。而A-(BC)=(A-B)(A-C)，所以A=(A-B)(A-C)。12、(A-B)(A-C)=ABC證明：由于(A-B)(A-C)=(A)(A)=A()=A=A-(BC)，且(A-B)(A-C)=，所以=A-(BC)，故ABC。由于ABC，所以A-(BC)=A。而A-(BC)=(A-B)(A-C)，所以A=(A-B)(A-C)。13、(A-B)(B-A)=AB=證明：由于(A-B)(B-A)=A，所以B-AA。但(B-A)A=，故B-A=。即BA，從而B=（否則A-BA，從而與(A-B)(B-A)=A矛盾）。由于B=，所以A-B=A且B-A=。從而(A-B)(B-A)=A。14、(A-B)-CA-(B-C)證明：x(A-B)-C，有A-B且xC，即A，xB且xC。從而A，xB-C，故xA-(B-C)。從而(A-B)-CA-(B-C)15、P(A)P(B)P(AB)（P(S)表達S的冪集）證明：SP(A)P(B)，有SP(A)或SP(B)，所以SA或SB。從而SAB，故SP(AB)。即P(A)P(B)P(AB)16、P(A)P(B)=P(AB)（P(S)表達S的冪集）證明：SP(A)P(B)，有SP(A)且SP(B)，所以SA且SB。從而SAB，故SP(AB)。即P(A)P(B)P(AB)。SP(AB)，有SAB，所以SA且SB。從而SP(A)且SP(B)，故SP(A)P(B)。即P(AB)P(A)P(B)。故P(AB)=P(A)P(B)17、（A-B）B=（AB）-B當且僅當B=。證明： 當B=時，由于（A-B）B=（A-）=A，（AB）-B=（A）-=A，所以（A-B）B=（AB）-B。 用反證法證明。假設B，則存在bB。由于bB且bAB，所以b（AB）-B。而顯然b（A-B）B。故這與已知（A-B）B=（AB）-B矛盾。五、證明或解答：（數(shù)理邏輯、集合論與二元關系部分）1、設個體域是自然數(shù)，將下列各式翻譯成自然語言：(1)xy（xy=1）;(2)xy(xy=1);(3)xy(xy=0);(4)xy（xy=0）;(5)xy(xy=x);(6)xy（xy=x）;(7)xyz(x-y=z)答：（1）存在自然數(shù)x，對任意自然數(shù)y滿足xy=1;（2）對每個自然數(shù)x，存在自然數(shù)y滿足xy=1;（3）對每個自然數(shù)x，存在自然數(shù)y滿足xy=0;（4）存在自然數(shù)x，對任意自然數(shù)y滿足xy=1;（5）對每個自然數(shù)x，存在自然數(shù)y滿足xy=x;（6）存在自然數(shù)x，對任意自然數(shù)y滿足xy=x;（7）對任意自然數(shù)x,y，存在自然數(shù)z滿足x-y=z。2、設A(x,y,z):x+y=z,M（x,y,z）:xy=z,L(x,y):x<y,G(x,y):x>y，個體域為自然數(shù)。將下列命題符號化：（1）沒有小于0的自然數(shù);（2）x<z是x<y且y<z的必要條件;（3）若x<y，則存在某些z，使z<0,xz>yz;（4）存在x，對任意y使得xy=y;（5）對任意x，存在y使x+y=x。答：（1）x（G(x,0)M（0,0,x））或xL(x,0)（2）xyz((L(x,y)L(y,z))L(x,z))（3）xy((L(x,y)z(L(z,0)G(xz,yz)))（4）xyM（x,y,y）（5）xyA(x,y,x)3、列出下列二元關系的所有元素：（1）A={0,1,2}，B={0,2,4}，R={<x,y>|x,y};（2）A={1,2,3,4,5}，B={1,2}，R={<x,y>|2x+y4且x且yB};（3）A={1,2,3}，B={-3,-2,-1,0,1}，R={<x,y>||x|=|y|且x且yB};解：(1)R={<0,0>,<0,2>,<2,0>,<2,2>}(2)R={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>};(3)R={<1,1>,<1,-1>,<2,-2>,<3,-3>}。4、對任意集合A,B，證明：若AA=BB，則B=B。證明：若B=，則BB=。從而AA=。故A=。從而B=A。若B，則BB。從而AA。對,<x,x>BB。由于AA=BB，則<x,x>A。從而xA。故BA。同理可證，AB。故B=A。5、對任意集合A,B，證明：若A，AB=AC，則B=C。證明：若B=，則AB=。從而AC=。由于A，所以C=。即B=C。若B，則AB。從而AC。對,由于A，所以存在yA,使<y,x>B。由于AB=AC，則<y,x>C。從而xC。故BC。同理可證，CB。故B=C。6、設A={a,b},B={c}。求下列集合：(1)A{0,1}B；(2)B2A；(3)(AB)2;(4)P(A)A。解：（1）A{0,1}B={<a,0,c>,<a,1,c>,<b,0,c>,<b,1,c>};（2）B2A={<c,c,a>,<c,c,b>};（3）(AB)2={<a,c,a,c>,<a,c,b,c>,<b,c,a,c>,<b,c,b,c>};（4）P(A)A={<,a>,<,b>,<{a},a>,<{a},b>,<,a>,<,b>,<A,a>,<A,b>}。7、設全集U={a,b,c,d,e},A={a,d},B={a,b,c},C={b,d}。求下列各集合：（1）AB；（2）；（3）(A)C;（4）P(A)-P(B);（5）(A-B)(B-C);（6）(AB)C;解：(1)AB={a};(2)={a,b,c,d,e};(3)（A）C={b,d};(4)P(A)-P(B)={2mhmmw1,{a,d}};(5)(A-B)(B-C)={d,c,a};(6)(AB)C={b,d}。8、設A,B,C是任意集合，證明或否認下列斷言：（1）若AB，且BC，則AC；（2）若AB，且BC，則AC;（3）若AB，且BC，則AC；（4）若AB，且BC，則AC；證明：(1)成立。對xA,由于AB，所以xB。又由于BC，所以xC。即AC。(2)不成立。反例如下：A={a},B={a,b},C={a,b,c}。雖然AB，且BC，但AC。(3)不成立。反例如下：A={a},B={{a},b},C={{{a},b},c}。雖然AB，且BC，但AC。(4)成立。由于AB,且BC，所以AC。9、A上的任一良序關系一定是A上的全序關系。證明：a，b∈A，則{a,b}是A的一個非空子集?！苁茿上的良序關系，{a,b}有最小元。若最小元為a，則a≤b；否則b≤a。從而≤為A上的的全序關系。10、若R和S都是非空集A上的等價關系，則RS是A上的等價關系。證明：a∈A，由于R和S都是A上的等價關系，所以xRx且xSx。故xRSx。從而RS是自反的。a,b∈A，aRSb，即aRb且aSb。由于R和S都是A上的等價關系，所以bRa且bSa。故bRSa。從而RS是對稱的。a,b,c∈A，aRSb且bRSc，即aRb，aSb,bRc且bSc。由于R和S都是A上的等價關系，所以aRc且aSc。故aRSc。從而RS是傳遞的。故RS是A上的等價關系。11、設RA×A，則R自反IAR。證明：xA，R是自反的，xRx。即<x,x>R，故IAR。xA，IAR，<x,x>R。即xRx，故R是自反的。12、設A是集合，RA×A，則R是對稱的R＝R－1。證明：<x,y>R，R是對稱的，yRx。即<y,x>R，故<x,y>R_1。從而RR-1。反之<y,x>R-1,即<x,y>R。R是對稱的，yRx。即<y,x>R，R_1R。故R=R-1。x，yA，若<x,y>R，即<y,x>R-1。R=R-1，<y,x>R。即yRx，故R是對稱的。13、設A,B,C和D均是集合，RA×B，SB×C，TC×D，則(1)R(ST)=(RS)(RT)；(2)R(ST)(RS)(RT)；證明：（1）<x，z>R(ST)，則由合成關系的定義知yB，使得<x，y>R且<y，z>ST。從而<x，y>R且<y，z>S或<x，y>R且<y，z>T，即<x，z>RS或<x，z>RT。故<x，z>（RS）（RT）。從而R(ST)（RS）（RT）。同理可證（RS）（RT）R(ST)。故R(ST)=（RS）（RT）。(2)<x，z>R(ST)，則由合成關系的定義知yB，使得<x，y>R且<y，z>ST。從而<x，y>R且<y，z>S且<y，z>T，即<x，z>RS且<x，z>RT。故<x，z>（RS）（RT）。從而R(ST)(RS）（RT）。14、設〈A,≤〉為偏序集，BA，若B有最大(小)元、上(下)確界，則它們是惟一的。證明：設a,b都是B的最大元，則由最大元的定義ab，ba。是A上的偏序關系，a=b。即B假如有最大元則它是惟一的。15、設A={1,2,3},寫出下列圖示關系的關系矩陣，并討論它們的性質：111232323解：（1）R={<2,1>,<3,1>,<2,3>};MR=;它是反自反的、反對稱的、傳遞的；（2）R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>};MR=;它是反自反的、對稱的；（3）R={<1,2>,<2,1>,<1,3>,<3,3>};MR=;它既不是自反的、反自反的、也不是對稱的、反對稱的、傳遞的。16、設A={1,2,…,10}。下列哪個是A的劃分？若是劃分，則它們誘導的等價關系是什么？（1）B={{1,3,6},{2,8,10},{4,5,7}};（2）C={{1,5,7},{2,4,8,9},{3,5,6,10}};（3）D={{1,2,7},{3,5,10},{4,6,8},{9}}解：（1）和（2）都不是A的劃分。（3）是A的劃分。其誘導的等價關系是I{<1,2>,<2,1>,<1,7>,<7,1>,<2,7>,<7,2>,<3,5>,<5,3>,<3,10>,<10,3>,<10,5>,<5,10>,<4,6>,<6,4>,<4,8>,<8,4>,<6,8>,<8,6>}。17、R是A={1,2,3,4,5,6}上的等價關系，R=I{<1,5>,<5,1>,<2,4>,<4,2>,<3,6>,<6,3>}求R誘導的劃分。解：R誘導的劃分為{{1,5},{2,4},{3,6}}。18、A上的偏序關系的Hasse圖如下。下列哪些關系式成立：ab,ba,ce,ef,df,cf；分別求出下列集合關于的極大（?。┰⒆畲螅ㄐ。┰⑸希ㄏ拢┙缂吧希ㄏ拢┐_界（若存在的話）：(a)A;(b){b,d};(c){b,e};(d){b,d,e}aefbdc解：(1)ba,ce,df,cf成立；(2)(a)的極大元為a,e,f,極小元為c;無最大元，c是最小元；無上界，下界是c;無上確界，下確界是c。(b)的極大元為b,d,極小元為b,d;無最大元和最小元；上界是e，下界是c;上確界是e，下確界是c。(c)的極大元為e,極小元為b;最大元是e，b是最小元；上界是e，下界是b;上確界是e，下確界是b。(d)的極大元為e,極小元為b,d;最大元是e，無最小元；上界是e，下界是c;上確界是e，下確界是c。（半群與群部分）19、求循環(huán)群C12={e,a,a2,…,a11}中H={e,a4,a8}的所有右陪集。解：由于|C12|=12，|H|=3，所以H的不同右陪集有4個：H，{a,a5,a9},{a2,a6,a10},{a3,a7,a11}。20、求下列置換的運算：解：（1）=（2）===21、試求出8階循環(huán)群的所有生成元和所有子群。解：設G是8階循環(huán)群，a是它的生成元。則G={e,a,a2,..,a7}。由于ak是G的生成元的充足必要條件是k與8互素，故a,a3,a5,a7是G的所有生成元。由于循環(huán)群的子群也是循環(huán)群，且子群的階數(shù)是G的階數(shù)的因子，故G的子群只能是1階的、2階的、4階的或8階的。由于|e|=1,|a|=|a3|=|a5|=8,|a2|=|a6|=8,|a4|=2,且G的子群的生成元是該子群中a的最小正冪，故G的所有子群除兩個平凡子群外，尚有{e,a4},{e,a2,a4,a6}。22、I上的二元運算*定義為：a,bI，a*b=a+b-2。試問<I,*>是循環(huán)群嗎？解：<I,*>是循環(huán)群。由于<I,*>是無限階的循環(huán)群，則它只有兩個生成元。1和3是它的兩個生成元。由于an=na-2(n-1)，故1n=n-2(n-1)=2-n。從而對任一個kI,k=2-(2-k)=12-k，故1是的生成元。又由于1和3關于*互為逆元，故3也是<I,*>的生成元。23、設<G,·>是群，aG。令H={xG|a·x=x·a}。試證：H是G的子群。證明： c，dH，則對c，dHK，c·a=a·c,d·a=a·d。故(c·d)·a=c·(d·a)=c·(a·d)=(c·a)·d=(a·c)·d=a·(c·d)。從而c·dH。由于c·a=a·c,且·滿足消去律，所以a·c-1=c-1·a。故c-1H。從而H是G的子群。24、證明：偶數(shù)階群中階為2的元素的個數(shù)一定是奇數(shù)。證明：設<G,·>是偶數(shù)階群，則由于群的元素中階為1的只有一個單位元，階大于2的元素是偶數(shù)個，剩下的元素中都是階為2的元素。故偶數(shù)階群中階為2的元素一定是奇數(shù)個。25、證明：有限群中階大于2的元素的個數(shù)一定是偶數(shù)。證明：設<G,·>是有限群，則aG，有|a|=|a-1|。且當a階大于2時，a-1。故階數(shù)大于2的元素成對出現(xiàn)，從而其個數(shù)必為偶數(shù)。26、試求<N6,+6>中每個元素的階。解：0是<N6,+6>中關于+6的單位元。則|0|=1；|1|=|5|=6，|2|=|4|=3，|3|=2。27、設<G,·>是群，a,bG，ae，且a4·b=b·a5。試證a·bb·a。證明：用反證法證明。假設a·b=b·a。則a4·b=a3·（a·b）=a3·(b·a)=(a5·b)·a=(a2·(a·b))·a=（a2·（b·a））·a=((a2·b)·a)·a=(a·(a·b))·(a·a)=(a·(b·a))·a2=((a·b)·a)·a2=((b·a)·a)·a2=(b·a2)·a2=b·(a2·a2)=b·a4。由于a4·b=b·a5，所以b·a5=b·a4。由消去律得，a=e。這與已知矛盾。28、I上的二元運算*定義為：a,bI，a*b=a+b-2。試證：<I,*>為群。證明：（1）a,b,cI，(a*b)*c=(a*b)+c-2=(a+b-2)+c-2=a+b+c-4,a*(b*c)=a+(b*c)-2=a+(b+c-2)-2=a+b+c-4。故(a*b)*c=a*(b*c)，從而*滿足結合律。（2）記e=2。對aI，a*2=a+2-2=a=2+a-2=2*a.。故e=2是I關于運算*的單位元。（3）對aI，由于a*（4-a）=a+4-a-2=2=e=4-a+a-2=(4-a)*a。故4-a是a關于運算*的逆元。綜上所述，<I,*>為群。29、設<S,·>為半群，aS。令Sa={ai|iI+}。試證<Sa,·>是<S,·>的子半群。證明：b，cSa，則存在k,lI+，使得b=ak,c=al。從而b·c=ak·al=ak+l。由于k+lI+，所以b·cSa，即Sa關于運算·封閉。故<Sa,·>是<S,·>的子半群。30、單位元有惟一逆元。證明：設<G,>是一個群，e是關于運算的單位元。若e1,e2都是e的逆元，即e1*e=e且e2*e=e。由于e是關于運算的單位元，所以e1=e1*e=e=e2*e=e2。即單位元有惟一逆元。31、設e和0是關于A上二元運算*的單位元和零元，假如|A|>1，則e0。證明：用反證法證明。假設e=0。對A的任一元素a，由于e和0是A上關于二元運算*的單位元和零元，則a=a*e=a*0=0。即A的所有元素都等于0,這與已知條件|A|>1矛盾。從而假設錯誤。即e0。32、證明在元素不少于兩個的群中不存在零元。證明：（用反證法證明）設在素不少于兩個的群<G,>中存在零元。對aG,由零元的定義有a*=。 <G,>是群，關于*消去律成立。a=e。即G中只有一個元素，這與|G|2矛盾。故在元素不少于兩個的群中不存在零元。33、證明在一個群中單位元是惟一的。證明：設e1,e2都是群〈G,*〉的單位元。則e1=e1*e2=e2。所以單位元是惟一的。34、設a是一個群〈G，*〉的生成元，則a-1也是它的生成元。證明：xG，由于a是〈G，*〉的生成元，所以存在整數(shù)k，使得x=a。故x=((a))=((a))=(a)。從而a-1也是〈G，*〉的生成元。35、在一個偶數(shù)階群中一定存在一個2階元素。證明：群中的每一個元素的階均不為0且單位元是其中惟一的階為1的元素。由于任一階大于2的元素和它的逆元的階相等。且當一個元素的階大于2時，其逆元和它自身不相等。故階大于2的元素是成對的。從而階為1的元素與階大于2的元素個數(shù)之和是奇數(shù)。由于該群的階是偶數(shù)，從而它一定有階為2的元素。36、代數(shù)系統(tǒng)<G,*>是一個群，則G除單位元以外無其它等冪元。證明：設e是該群的單位元。若a是<G,*>的等冪元，即a*a=a。由于a*e=a，所以a*a=a*e。由于運算*滿足消去律，所以a=e。即G除單位元以外無其它等冪元。37、設<G,>是一個群，則對于a,b∈G，必有唯一的x∈G，使得ax=b。證明：由于a-1*b∈G，且a*(a-1*b)=(a*a-1)*b=e*b=b，所以對于a,b∈G，必有x∈G，使得ax=b。若x1,x2都滿足規(guī)定。即ax1=b且ax2=b。故ax1=ax2。由于*滿足消去律，故x1=x2。從而對于a,b∈G，必有唯一的x∈G，使得ax=b。38、設半群<S,·>中消去律成立，則<S,·>是可互換半群當且僅當a,bS，（a·b）2=a2·b2。證明：a,bS，（a·b）2=(a·b)·(a·b)=((a·b)·a)·b=(a·(a·b))·b=((a·a)·b)·b=(a·a)·(b·b)=a2·b2; a,bS，由于（a·b）2=a2·b2，所以(a·b)·(a·b)=(a·a)·(b·b)。故a·((b·a)·b)=a·(a·(b·b))。由于·滿足消去律，所以(b·a)·b=a·(b·b)，即(b·a)·b=(a·b)·b。從而a·b=b·a。故·滿足互換律。39、設群<G,＊>除單位元外每個元素的階均為2，則<G,＊>是互換群。證明：對任一aG，由已知可得a*a=e，即a-1=a。對任一a,bG，由于a*b=(a*b)-1=b-1*a-1=b*a，所以運算*滿足互換律。從而＜G,*＞是互換群。40、設*是集合A上可結合的二元運算，且a,bA,若a*b=b*a，則a=b。試證明：（1）aA,a*a=a，即a是等冪元；（2）a,bA,a*b*a=a;（3）a,b,cA,a*b*c=a*c。證明：（1）aA,記b=a*a。由于*是可結合的，故有b*a=(a*a)*a=a*(a*a)=a*b。由已知條件可得a=a*a。（2）a,bA,由于由（1），a*(a*b*a)=(a*a)*(b*a)=a*(b*a),(a*b*a)*a=(a*b)*(a*a)=(a*b)*a=a*(b*a)。故a*(a*b*a)=(a*b*a)*a，從而a*b*a=a。（3）a,b,cA,（a*b*c）*（a*c）=（（a*b*c）*a）*c=(a*(b*c)*a)*c且(a*c)*(a*b*c)=a*(c*(a*b*c))=a*(c*(a*b)*c))。由（2）可知a*(b*c)*a=a且c*(a*b)*c=c，故（a*b*c）*（a*c）=(a*(b*c)*a)*c=a*c且(a*c)*(a*b*c)=a*(c*(a*b)*c))=a*c，即（a*b*c）*（a*c）=(a*c)*(a*b*c)。從而由已知條件知，a*b*c=a*c。41、設<G,·>是群，作f:GG,aa-1。證明：f是G的自同構G是互換群。證明： 設f是G的自同構。對a，bG，a·b=(b-1·a-1)-1=(f(b)·f(a))-1=(f(b·a))-1=((b·a)-1)-1=b·a。故運算·滿足互換律，即G是可互換群。由于當ab時，a-1b-1，即f(a)f(b)，故f是G到G中的一個單一函數(shù)。又對aG，有f(a-1)=(a-1)-1=a。故f是G到G上的滿函數(shù)。從而f是G到G上的自同構。對a，bG，由于G是可互換群，故f(a·b)=(a·b)-1=(b·a)-1=a-1·b-1=f(a)·f(b)。故f滿足同態(tài)方程。從而f是G的自同構。42、若群<G,＊>的子群<H,＊>滿足|G|＝2|H|，則<H,＊>一定是群<G,＊>的正規(guī)子群。證明：由已知可知，G關于H有兩個不同的左陪集H，H1和兩個不同的右陪集H，H2。由于HH1=且HH1=G，HH2=且HH2=G，故H1=G-H=H2。對aG，若aH，則aH=H,Ha=H。否則由于aG-H，故aHH,HaH。從而aH=Ha=G-H。故H是G的不變子群。43、設H和K都是G的不變子群。證明：HK也是G的不變子群。證明：由于H和K都是G的不變子群，所以HK是G的子群。對aG，hHK，有a·h·a-1a·H·a-1，·h·a-1a·K·a-1。由于H和K都是G的不變子群，所以a·h·a-1H且a·h·a-1K。從而a·h·a-1HK。故HK是G的不變子群。44、設群G的中心為C（G）={aG|xG,a·x=x·a}。證明C（G）是G的不變子群。證明：先證C（G）是G的子群。a,bC（G），對xG,有a·x=x·a，b·x=x·b。故（a·b）·x=a·(b·x)=a·(x·b)=(a·x)·b=(x·a)·b=x·(a·b),a-1·x=x·a-1。從而a·b，a-1C（G）。故C（G）是G的子群。再證C（G）是G的不變子群。對aG，hC(G)，記b=a·h·a-1。下證bC(G)。由于hC(G)，所以b=(a·h)·a-1=（h·a）·a-1=h·(a·a-1)=hC(G)。故C（G）是G的不變子群。45、設<G,·>是沒有非平凡子群的有限群。試證：G是平凡群或質數(shù)階的循環(huán)群。證明：若G是平凡群，則結論顯然成立。否則設<G,·>的階為n。任取aG且ae,記H=（a）(由a生成的G的子群)。顯然H{e}，且G沒有非平凡子群，故H=G。從而G一定是循環(huán)群，且a是G的生成元。若n是合數(shù)，則存在大于1的整數(shù)k,m，使得n=mk。記H={e,ak,(ak)2,…,(ak)m-1}，易證H是G的子群，但1<|H|=m<n，故H是G的非平凡子群。這與已知矛盾。從而n是質數(shù)。故G是質數(shù)階的循環(huán)群。綜上所述，G是平凡群或質數(shù)階的循環(huán)群。46、設H和K都是G的有限子群，且|H|與|K|互質。試證：HK={e}。證明：用反證法證明。若HK{e}。則HK是一個元素個數(shù)大于1的有限集。先證HK也是G的子群，從而也是H和K的子群。a,bHK,則a,bH且a,bK。由于H和K都是G的子群，故a·b,a-1H且a·b,a-1K。從而a·bHK,a-1HK。故HK是G的子群，從而也是H和K的子群。由拉格朗日定理可知，|HK|是|H|和|K|的因子，這與已知矛盾。47、素數(shù)階循環(huán)群的每個非單位元都是生成元。證明：設<G,*>是p階循環(huán)群，p是素數(shù)。對G中任一非單位元a。設a的階為k,則k1。由拉格朗日定理，k是p的正整因子。由于p是素數(shù)，故k=p。即a的階就是p，即群G的階。故a是G的生成元。48、若<S,>是可互換獨異點，T為S中所有等冪元的集合，則<T,>是<S,>的子獨異點。證明： ee=e，eT，即T是S的非空子集。 a,bT,<S，>是可互換獨異點,(ab)(ab)=((ab)a)b=(a(ba))b=（a(ab)）b=((aa)b)b=(aa)(bb)=ab,即abT。故<T,>是<S,>的子獨異點。49、設<G,>是群，且a∈G的階為n，k∈I，則|ak|＝，其中(k,n)為k和n的最大公因子。證明：記p=,q=,｜ak｜＝m。由n和p的定義，顯然有(ak)p=e。故mp且m|p。又由于akm=e，所以由定理5.2.5知，n|km。即p|qm。但p和q互質，故p|m。由于p和m都是正整數(shù)，所以p=m。即｜ak｜＝。50、設<G,>是有限群，|G|＝n，則a∈G，|a|n。證明：aG，由封閉性及|G|=n可知a,a2,…,an,an+1中必有相同的元素，不妨設為ak=am,k<m。由消去律得am-k=e。從而|a|m-kn。51、設G＝(a)，若G為無限群，則G只有兩個生成元a和a-1；證明：bG＝(a)，則nI,使b=an。故b=(a-n)-1=(a-1)-n,從而a-1也是G的生成元。若c是G的生成元，則k,mI，分別滿足c=ak和a=cm。從而c=(cm)k=cmk。若km1，則由消去律可知c的階是有限的，這與|G|無限矛盾。從而km=1，即k=1,m=1或k=-1,m=-1。故c=a或c=a-1。從而G只有兩個生成元a和a-1。52、設G＝(a)，{e}HG，am是H中a的最小正冪，則（1）H＝(am)；（2）若G為無限群，則H也是無限群；證明：（1）bH,kI,使得b=ak。令k=mq+r,0r<m。則ar=ak-mq=aka-mq=b(am)-q。由于b,amH,且HG，所以arH。由于0r<m，且am是H中a的最小正冪，故r=0,即k=mq。從而b=(am)q。故am是H的生成元。（2）由于{e}H，故H的生成元為am（m0）。由于G是無限群，所以a的階是無限的，從而am的階也是無限的，故H也是無限群。53、設G＝(a)，|G|＝n，則對于n的每一正因子d，有且僅有一個d階子群。因此n階循環(huán)群的子群的個數(shù)恰為n的正因子數(shù)。證明：對n的每一正因子d，令k=,b=ak,H={e,b,b2,…,bd-1}。由于|a|=n,所以bd=(ak)d=akd=an=e且|b|=d。從而H中的元素是兩兩不同的，易證HG。故|H|=d。所以是G的一個d階子群。設H1是G的任一d階子群。則由定理5.4.4知，H1＝(am)，其中am是H1中a的最小正冪，且|H|=。由于|H|=d，所以m==k，即H=H1。從而H是G的惟一d階子群。設H是G的惟一的d階子群。若d=1,則結論顯然成立。否則H＝(am)，其中am是H中a的最小正冪。由定理5.4.4知，d=。故d是n的一個正因子。54、設h是從群<G1,>到<G2,>的群同態(tài)，G和G2的單位元分別為e1和e2，則（1）h(e1)=e2；（2）aG1，h(a-1)=h(a)-1；（3）若HG1，則h(H)G2；（4）若h為單一同態(tài)，則aG1，|h(a)|=|a|。證明：(1)由于h(e1)h(e1)=h(e1e1)=h(e1)=e2h(e1),所以h(e1)=e2。(2)a∈G1，h(a)h(a-1)=h(aa-1)=h(e1)=e2,h(a-1)h(a)=h(a-1a)=h(e1)=e2,故h(a-1)=h(a)-1。(3)c,d∈h(H),a,b∈H，使得c=h(a),d=h(b)。故cd=h(a)h(b)=h(ab)。由于HG，所以ab∈H，故cd∈h(H)。又c-1=(h(a))-1=h(a-1)且a-1∈H，故c-1∈h(H)。由定理5.3.2知h(H)G2。(4)若|a|=n,則an=e1。故(h(a))n=h(an)=h(e1)=e2。從而h(a)的階也有限，且|h(a)|n。設|h(a)|=m,則h(am)=(h(a))m=h(e1)=e2。由于h是單一同態(tài)，所以am=e1。即|a|m。故|h(a)|=|a|。若a的階是無限的，則類似于上述證明過程可以得出，h(a)的階也是無限的。故結論成立。55、有限群G的每個元素的階均能整除G的階。證明：設|G|=n，aG，則|a|=m。令H={e,a,a2,…,am-1}。則H是G的子群且|H|=m。由Lagrange定理知|H|能整除|G|，故a的階能整除G的階。56、證明：在同構意義下，只有兩個四階群，且都是循環(huán)群。證明：在4階群G中，由Lagrange定理知，G中的元素的階只能是1，2或4。階為1的元素恰有一個，就是單位元e.若G有一個4階元素，不妨設為a，則G=（a）,即G是循環(huán)群，從而是可互換群。若G沒有4階元素，則除單位元e外，G的其余3個階均為2。不妨記為a,b,c。由于a,b,c的階均為2，故a-1=a,b-1=b,c-1=c。從而aba,abb,abe,故ab=c。同理可得ac=ca=b,cb=bc=a,ba=c。57、在一個群<G,*>中，若G中的元素a的階是k，即|a|=k，則a-1的階也是k。證明：由于|a|=k，所以ak=e。即（a-1）k=(ak)-1=e。從而a-1的階是有限的，且|a-1|k。同理可證，a的階小于等于|a-1|。故a-1的階也是k。58、在一個群<G,*>中，若A和B都是G的子群。若AB=G，則A=G或B=G。證明：用反證法證明。若AG且BG，則有aA,aB且bB,bA。由于A，B都是G的子群，故a,bG，從而a*bG。由于aA,所以aA。若a*bA,則b=a*(a*b)A，這與aB矛盾。從而a*bA。同理可證a*bB。綜合可得a*bAB=G，這與已知矛盾。從而假設錯誤，得證A=G或B=G。59、設e是奇數(shù)階互換群<G,*>的單位元，則G的所有元素之積為e。證明：設G=<{e,a,a,…,a},*>，n為正整數(shù)。由于G的階數(shù)為奇數(shù)2n+1，所以由拉格朗日定理知G中不存在2階元素，即除了單位元e以外，G的所有元素的階都大于2。故對G中的任一非單位元a，它的逆元a不是它自身，且G中不同的元素有不同的逆元。由此可見，G中的2n個非單位元構成互為逆元的n對元素。由于G是互換群，故G的所有元素之積可變成單位元和n對互為逆元的元素之積的積，從而結果為e。60、設S=QQ，Q為有理數(shù)集合，*為S上的二元運算：對任意(a,b)，(c,d)S,有(a,b)*(c,d)=(ac,ad+b),求出S關于二元運算*的單位元，以及當a0時，(a,b)關于*的逆元。解：設S關于*的單位元為(a,b)。根據(jù)*和單位元的定義，對(x,y)S,有(a,b)*(x,y)=(ax,ay+b)=(x,y),(x,y)*(a,b)=(ax,xb+