《離散數(shù)學(xué)》題庫(kù)及答案解析

.PAGE.《離散數(shù)學(xué)》題庫(kù)與答案一、選擇或填空〔數(shù)理邏輯部分1、下列哪些公式為永真蘊(yùn)含式？<A><1>Q=>Q→P<2>Q=>P→Q<3>P=>P→Q<4>P<PQ>=>P答：在第三章里面有公式〔1是附加律,〔4可以由第二章的蘊(yùn)含等值式求出〔注意與吸收律區(qū)別2、下列公式中哪些是永真式？<><1><┐PQ>→<Q→R><2>P→<Q→Q><3><PQ>→P<4>P→<PQ>答：〔2,〔3,〔4可用蘊(yùn)含等值式證明3、設(shè)有下列公式,請(qǐng)問(wèn)哪幾個(gè)是永真蘊(yùn)涵式?<><1>P=>PQ<2>PQ=>P<3>PQ=>PQ<4>P<P→Q>=>Q<5><P→Q>=>P<6>P<PQ>=>P答：〔2是第三章的化簡(jiǎn)律,〔3類似附加律,〔4是假言推理,〔3,〔5,〔6都可以用蘊(yùn)含等值式來(lái)證明出是永真蘊(yùn)含式4、公式x<<A<x>B<y,x>>zC<y,z>>D<x>中,自由變?cè)?lt;>,約束變?cè)?lt;>。答：x,y,x,z〔考察定義在公式xA和xA中,稱x為指導(dǎo)變?cè)?A為量詞的轄域。在xA和xA的轄域中,x的所有出現(xiàn)都稱為約束出現(xiàn),即稱x為約束變?cè)?A中不是約束出現(xiàn)的其他變項(xiàng)則稱為自由變?cè)?。于是A<x>、B<y,x>和zC<y,z>中y為自由變?cè)?x和z為約束變?cè)?在D<x>中x為自由變?cè)?、判斷下列語(yǔ)句是不是命題。若是,給出命題的真值。<>北京是中華人民XX國(guó)的首都。<2>XX師大是一座工廠。<3>你喜歡唱歌嗎？<4>若7+8＞18,則三角形有4條邊。<5>前進(jìn)！<6>給我一杯水吧！答：〔1是,T〔2是,F〔3不是〔4是,T〔5不是〔6不是〔命題必須滿足是陳述句,不能是疑問(wèn)句或者祈使句。6、命題"存在一些人是大學(xué)生"的否定是<>,而命題"所有的人都是要死的"的否定是<>。答：所有人都不是大學(xué)生,有些人不會(huì)死〔命題的否定就是把命題前提中的量詞"換成存在,換成",然后將命題的結(jié)論否定,"且變或或變且"7、設(shè)P：我生病,Q：我去學(xué)校,則下列命題可符號(hào)化為<>。<1>只有在生病時(shí),我才不去學(xué)校<2>若我生病,則我不去學(xué)校<3>當(dāng)且僅當(dāng)我生病時(shí),我才不去學(xué)校<4>若我不生病,則我一定去學(xué)校答：〔1〔注意"只有……才……"和"除非……就……"兩者都是一個(gè)形式的〔2〔3〔48、設(shè)個(gè)體域?yàn)檎麛?shù)集,則下列公式的意義是<>。<1>xy<x+y=0><2>yx<x+y=0>答：〔1對(duì)任一整數(shù)x存在整數(shù)y滿足x+y=0〔2存在整數(shù)y對(duì)任一整數(shù)x滿足x+y=09、設(shè)全體域D是正整數(shù)集合,確定下列命題的真值：<1>xy<xy=y><><2>xy<x+y=y><><3>xy<x+y=x><><4>xy<y=2x><>答：〔1F<反證法：假若存在,則〔x-1*y=0對(duì)所有的x都成立,顯然這個(gè)與前提條件相矛盾>〔2F〔同理〔3F〔同理〔4T〔對(duì)任一整數(shù)x存在整數(shù)y滿足條件y=2x很明顯是正確的10、設(shè)謂詞P<x>：x是奇數(shù),Q<x>：x是偶數(shù),謂詞公式x<P<x>Q<x>>在哪個(gè)個(gè)體域中為真?<><1>自然數(shù)<2>實(shí)數(shù)<3>復(fù)數(shù)<4><1>--<3>均成立答：〔1〔在某個(gè)體域中滿足不是奇數(shù)就是偶數(shù),在整數(shù)域中才滿足條件,而自然數(shù)子整數(shù)的子集,當(dāng)然滿足條件了11、命題"2是偶數(shù)或-3是負(fù)數(shù)"的否定是〔。答：2不是偶數(shù)且-3不是負(fù)數(shù)。12、永真式的否定是〔<1>永真式<2>永假式<3>可滿足式<4><1>--<3>均有可能答：〔2〔這個(gè)記住就行了13、公式<PQ><PQ>化簡(jiǎn)為〔,公式Q<P<PQ>>可化簡(jiǎn)為〔。答：P,QP〔考查分配率和蘊(yùn)含等值式知識(shí)的掌握14、謂詞公式x<P<x>yR<y>>Q<x>中量詞x的轄域是〔。答：P<x>yR<y>〔一對(duì)括號(hào)就是一個(gè)轄域15、令R<x>:x是實(shí)數(shù),Q<x>:x是有理數(shù)。則命題"并非每個(gè)實(shí)數(shù)都是有理數(shù)"的符號(hào)化表示為〔。答：x<R<x>Q<x>>〔集合論部分16、設(shè)A={a,{a}},下列命題錯(cuò)誤的是〔。<1>{a}P<A><2>{a}P<A><3>{{a}}P<A><4>{{a}}P<A>答：<2>〔{a}是P〔A的一個(gè)元素17、在0〔之間寫(xiě)上正確的符號(hào)。<1>=<2><3><4>答：<4>〔空集沒(méi)有任何元素,且是任何集合的子集18、若集合S的基數(shù)|S|=5,則S的冪集的基數(shù)|P<S>|=〔。答：32〔2的5次方考查冪集的定義,即冪集是集合S的全體子集構(gòu)成的集合19、設(shè)P={x|<x+1>4且xR},Q={x|5x+16且xR},則下列命題哪個(gè)正確〔<1>QP<2>QP<3>PQ<4>P=Q答：〔3〔Q是集合R,P只是R中的一部分,所以P是Q的真子集20、下列各集合中,哪幾個(gè)分別相等<>。<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=A5〔集合具有無(wú)序性、確定性和互異性21、若A-B=Ф,則下列哪個(gè)結(jié)論不可能正確？<><1>A=Ф<2>B=Ф<3>AB<4>BA答：〔4〔差集的定義22、判斷下列命題哪個(gè)為真?<><1>A-B=B-A=>A=B<2>空集是任何集合的真子集<3>空集只是非空集合的子集<4>若A的一個(gè)元素屬于B,則A=B答：〔1〔考查空集和差集的相關(guān)知識(shí)23、判斷下列命題哪幾個(gè)為正確？<><1>{Ф}∈{Ф,{{Ф}}}<2>{Ф}{Ф,{{Ф}}}<3>Ф∈{{Ф}}<4>Ф{Ф}<5>{a,b}∈{a,b,{a},}答：〔2,〔424、判斷下列命題哪幾個(gè)正確？<><1>所有空集都不相等<2>{Ф}Ф<4>若A為非空集,則AA成立。答：〔225、設(shè)A∩B=A∩C,∩B=∩C,則B<>C。答：=〔等于26、判斷下列命題哪幾個(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成立。答：〔227、Ａ,Ｂ,Ｃ是三個(gè)集合,則下列哪幾個(gè)推理正確：<1>AB,BC=>AC<2>AB,BC=>A∈B<3>A∈B,B∈C=>A∈C答：〔1〔〔3的反例C為{｛0,1｝,0｝B為｛0,1｝,A為1很明顯結(jié)論不對(duì)〔二元關(guān)系部分28、設(shè)Ａ＝｛1,2,3,4,5,6｝,B={1,2,3},從Ａ到B的關(guān)系Ｒ＝｛〈x,y〉|x=y2求<1>R<2>R-1答：〔1R={<1,1>,<4,2>}<2>R={<1,1>,<2,4>}〔考查二元關(guān)系的定義,R為R的逆關(guān)系,即R=｛<x,y>｝|<y,x>∈R29、舉出集合A上的既是等價(jià)關(guān)系又是偏序關(guān)系的一個(gè)例子。<>答：A上的恒等關(guān)系30、集合A上的等價(jià)關(guān)系的三個(gè)性質(zhì)是什么？<>答：自反性、對(duì)稱性和傳遞性31、集合A上的偏序關(guān)系的三個(gè)性質(zhì)是什么？<>答：自反性、反對(duì)稱性和傳遞性<題29,30,31全是考查定義>32、設(shè)S={１,２,３,４},Ａ上的關(guān)系Ｒ＝｛〈1,2〉,〈2,1〉,〈2,3〉,〈3,4〉｝求<1>RR<2>R-1。答：RR={〈1,1〉,〈1,3〉,〈2,2〉,〈2,4〉}〔考查FG={<x,y>|t<<x,t>∈F<t,y>∈G>}R-1=｛〈2,1〉,〈1,2〉,〈3,2〉,〈4,3〉｝33、設(shè)Ａ＝｛1,2,3,4,5,6｝,Ｒ是A上的整除關(guān)系,求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、設(shè)Ａ＝｛1,2,3,4,5,6｝,B={1,2,3},從Ａ到B的關(guān)系Ｒ＝｛〈x,y〉|x=2y｝,求<1>R<2>R-1。答：〔1R={<1,1>,<4,2>,<6,3>}<2>R={<1,1>,<2,4>,<36>}35、設(shè)Ａ＝｛1,2,3,4,5,6｝,B={1,2,3},從Ａ到B的關(guān)系Ｒ＝｛〈x,y〉|x=y2｝,求R和R-1的關(guān)系矩陣。答：R的關(guān)系矩陣=R的關(guān)系矩陣=36、集合A={1,2,…,10}上的關(guān)系R={<x,y>|x+y=10,x,yA},則R的性質(zhì)為〔。<1>自反的<2>對(duì)稱的<3>傳遞的,對(duì)稱的<4>傳遞的答：〔2〔考查自反對(duì)稱傳遞的定義〔代數(shù)系統(tǒng)部分37、設(shè)A={2,4,6},A上的二元運(yùn)算*定義為：a*b=max{a,b},則在獨(dú)異點(diǎn)<A,*>中,單位元是<>,零元是<>。答：2,6〔單位元和零元的定義,單位元：e。x=x零元：θ。x=θ38、設(shè)A={3,6,9},A上的二元運(yùn)算*定義為：a*b=min{a,b},則在獨(dú)異點(diǎn)<A,*>中,單位元是<>,零元是<>；答：9,3〔半群與群部分39、設(shè)〈G,*〉是一個(gè)群,則<1>若a,b,x∈G,ax=b,則x=<>；<2>若a,b,x∈G,ax=ab,則x=<>。答：〔1ab〔2b〔考查群的性質(zhì),即群滿足消去律40、設(shè)a是12階群的生成元,則a2是<>階元素,a3是<>階元素。答：6,441、代數(shù)系統(tǒng)<G,*>是一個(gè)群,則G的等冪元是<>。答：?jiǎn)挝辉灿蒩^2=a,用歸納法可證a^n=a*a^<n-1>=a*a=a,所以等冪元一定是冪等元,反之若a^n=a對(duì)一切N成立,則對(duì)n=2也成立,所以冪等元一定是等冪元,并且在群<G,*>中,除幺元即單位元e外不可能有任何別的冪等元42、設(shè)a是10階群的生成元,則a4是<>階元素,a3是<>階元素答：5,10〔若一個(gè)群G的每一個(gè)元都是G的某一個(gè)固定元a的乘方,我們就把G叫做循環(huán)群；我們也說(shuō),G是由元a生成的,并且用符號(hào)G=<a>表示,且稱a為一個(gè)生成元。并且一元素的階整除群的階43、群<G,*>的等冪元是<>,有<>個(gè)。答：?jiǎn)挝辉?1〔在群<G,*>中,除幺元即單位元e外不可能有任何別的冪等元44、素?cái)?shù)階群一定是<>群,它的生成元是<>。答：循環(huán)群,任一非單位元〔證明如下：任一元素的階整除群的階?，F(xiàn)在群的階是素?cái)?shù)p,所以元素的階要么是1要么是p。G中只有一個(gè)單位元,其它元素的階都不等于1,所以都是p。任取一個(gè)非單位元,它的階等于p,所以它生成的G的循環(huán)子群的階也是p,從而等于整個(gè)群G。所以G等于它的任一非單位元生成的循環(huán)群45、設(shè)〈G,*〉是一個(gè)群,a,b,c∈G,則<1>若ca=b,則c=<>；<2>若ca=ba,則c=<>。答：〔1b<2>b〔群的性質(zhì)46、<H,,>是<G,,>的子群的充分必要條件是<>。答：<H,,>是群或a,bG,abH,a-1H或a,bG,ab-1H47、群＜A,*＞的等冪元有<>個(gè),是<>,零元有<>個(gè)。答：1,單位元,048、在一個(gè)群〈G,*〉中,若G中的元素a的階是k,則a-1的階是<>。答：k49、在自然數(shù)集N上,下列哪種運(yùn)算是可結(jié)合的？〔<1>a*b=a-b<2>a*b=max{a,b}<3>a*b=a+2b<4>a*b=|a-b|答：<2>50、任意一個(gè)具有2個(gè)或以上元的半群,它〔。<1>不可能是群<2>不一定是群<3>一定是群<4>是交換群答：<1>51、6階有限群的任何子群一定不是〔。<1>2階<2>3階<3>4階<4>6階答：<3>〔格與布爾代數(shù)部分52、下列哪個(gè)偏序集構(gòu)成有界格〔<1>〔N,<2>〔Z,<3>〔{2,3,4,6,12},|〔整除關(guān)系<4><P<A>,>答：<4>〔考查冪集的定義53、有限布爾代數(shù)的元素的個(gè)數(shù)一定等于〔。<1>偶數(shù)<2>奇數(shù)<3>4的倍數(shù)<4>2的正整數(shù)次冪答：<4>〔圖論部分54、設(shè)G是一個(gè)哈密爾頓圖,則G一定是<>。<1>歐拉圖<2>樹(shù)<3>平面圖<4>連通圖答：<4>〔考察圖的定義55、下面給出的集合中,哪一個(gè)是前綴碼？<><1>{0,10,110,101111}<2>{01,001,000,1}<3>{b,c,aa,ab,aba}<4>{1,11,101,001,0011}答：〔256、一個(gè)圖的哈密爾頓路是一條通過(guò)圖中<>的路。答：所有結(jié)點(diǎn)一次且恰好一次57、在有向圖中,結(jié)點(diǎn)v的出度deg+<v>表示<>,入度deg-<v>表示<>。答：以v為起點(diǎn)的邊的條數(shù),以v為終點(diǎn)的邊的條數(shù)58、設(shè)G是一棵樹(shù),則G的生成樹(shù)有<>棵。<1>0<2>1<3>2<4>不能確定答：159、n階無(wú)向完全圖Kn的邊數(shù)是<>,每個(gè)結(jié)點(diǎn)的度數(shù)是<>。答：,n-160、一棵無(wú)向樹(shù)的頂點(diǎn)數(shù)n與邊數(shù)m關(guān)系是<>。答：m=n-161、一個(gè)圖的歐拉回路是一條通過(guò)圖中<>的回路。答：所有邊一次且恰好一次62、有n個(gè)結(jié)點(diǎn)的樹(shù),其結(jié)點(diǎn)度數(shù)之和是<>。答：2n-2〔結(jié)點(diǎn)度數(shù)的定義63、下面給出的集合中,哪一個(gè)不是前綴碼<>。<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個(gè)結(jié)點(diǎn)的有向完全圖邊數(shù)是<>,每個(gè)結(jié)點(diǎn)的度數(shù)是<>。答：n<n-1>,2n-265、一個(gè)無(wú)向圖有生成樹(shù)的充分必要條件是<>。答：它是連通圖66、設(shè)G是一棵樹(shù),n,m分別表示頂點(diǎn)數(shù)和邊數(shù),則<1>n=m<2>m=n+1<3>n=m+1<4>不能確定。答：〔367、設(shè)T=〈V,E〉是一棵樹(shù),若|V|>1,則T中至少存在<>片樹(shù)葉。答：268、任何連通無(wú)向圖G至少有<>棵生成樹(shù),當(dāng)且僅當(dāng)G是<>,G的生成樹(shù)只有一棵。答：1,樹(shù)69、設(shè)G是有n個(gè)結(jié)點(diǎn)m條邊的連通平面圖,且有k個(gè)面,則k等于:<1>m-n+2<2>n-m-2<3>n+m-2<4>m+n+2。答：〔170、設(shè)T是一棵樹(shù),則T是一個(gè)連通且<>圖。答：無(wú)簡(jiǎn)單回路71、設(shè)無(wú)向圖G有16條邊且每個(gè)頂點(diǎn)的度數(shù)都是2,則圖G有<>個(gè)頂點(diǎn)。<1>10<2>4<3>8<4>16答：〔472、設(shè)無(wú)向圖G有18條邊且每個(gè)頂點(diǎn)的度數(shù)都是3,則圖G有<>個(gè)頂點(diǎn)。<1>10<2>4<3>8<4>12答：<4>73、設(shè)圖G=<V,E>,V={a,b,c,d,e},E={<a,b>,<a,c>,<b,c>,<c,d>,<d,e>},則G是有向圖還是無(wú)向圖？答：有向圖74、任一有向圖中,度數(shù)為奇數(shù)的結(jié)點(diǎn)有<>個(gè)。答：偶數(shù)75、具有6個(gè)頂點(diǎn),12條邊的連通簡(jiǎn)單平面圖中,每個(gè)面都是由<>條邊圍成？<1>2<2>4<3>3<4>5答：〔376、在有n個(gè)頂點(diǎn)的連通圖中,其邊數(shù)〔。<1>最多有n-1條<2>至少有n-1條<3>最多有n條<4>至少有n條答：〔277、一棵樹(shù)有2個(gè)2度頂點(diǎn),1個(gè)3度頂點(diǎn),3個(gè)4度頂點(diǎn),則其1度頂點(diǎn)為〔。<1>5<2>7<3>8<4>9答：〔478、若一棵完全二元〔叉樹(shù)有2n-1個(gè)頂點(diǎn),則它〔片樹(shù)葉。<1>n<2>2n<3>n-1<4>2答：〔179、下列哪一種圖不一定是樹(shù)〔。<1>無(wú)簡(jiǎn)單回路的連通圖<2>有n個(gè)頂點(diǎn)n-1條邊的連通圖<3>每對(duì)頂點(diǎn)間都有通路的圖<4>連通但刪去一條邊便不連通的圖答：〔380、連通圖G是一棵樹(shù)當(dāng)且僅當(dāng)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、〔PRQ解：〔PRQ<PR>Q<PR>Q<PQ><RQ>〔合取范式<PQ<RR>><<PP>QR><PQR><PQR><PQR><PQR><PQR><PQR><PQR><PQR><PQR><PQR><PQR>〔主合取范式〔PRQ<PQR><PQR><PQR><PQR><PQR>〔原公式否定的主析取范式〔PRQ<PQR><PQR><PQR><PQR><PQR>〔主析取范式13、〔PQR解：〔PQR<PQ>R<PQ>R<析取范式><PQ<RR>><<PP><QQ>R><PQR><PQR><PQR><PQR><PQR><PQR><PQR><PQR><PQR><PQR><PQR><主析取范式〔PQR<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,〔2P→Q前提P〔3,〔4SP前提<7>S〔5,〔62、A→<B→C>,C→<DE>,F→<DE>,A=>B→F證明：<1>A前提<2>A→<B→C>前提<3>B→C〔1,〔2<4>B附加前提C〔3,〔4C→<DE>前提DE〔5,〔6F→<DE>前提F〔7,〔8B→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,〔84、<P→Q><R→S>,<Q→W><S→X>,<WX>,P→R=>P證明：〔1P假設(shè)前提〔2P→R前提〔3R〔1,〔2〔4<P→Q><R→S>前提〔5P→Q〔4〔6R→S〔5〔7Q〔1,〔5〔8S〔3,〔6〔9<Q→W><S→X>前提〔10Q→W〔9〔11S→X〔10〔12W〔7,〔10〔13X〔8,〔11〔14WX〔12,〔13〔15<WX>前提〔16<WX><WX>〔14,〔155、<UV>→<MN>,UP,P→<QS>,QS=>M證明：<1>QS附加前提P→<QS>前提P〔1,〔2UP前提U〔3,〔4UV〔5<UV>→<MN>前提MN<6>,<7>M〔86、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,〔87、P→<Q→R>,R→<Q→S>=>P→<Q→S>證明：〔1P附加前提〔2Q附加前提〔3P→<Q→R>前提〔4Q→R〔1,〔3〔5R〔2,〔4〔6R→<Q→S>前提〔7Q→S〔5,〔6〔8S〔2,〔7〔9Q→SCP,〔2,〔8〔10P→<Q→S>CP,〔1,〔98、P→Q,P→R,R→S=>S→Q證明：〔1S附加前提〔2R→S前提〔3R〔1,〔2〔4P→R前提〔5P〔3,〔4〔6P→Q前提〔7Q<5,〔6〔8S→QCP,〔1,〔79、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證明：〔1P前提〔2P→<Q→R>前提〔3Q→R<1>,<2>〔4Q→P前提〔5Q<1>,<4>〔6R<3>,<5>〔7S→R前提〔8S<6>,<7>11、A,A→B,A→C,B→<D→C>=>D證明：〔1A前提〔2A→B前提〔3B<1>,<2>〔4A→C前提〔5C<1>,<4>〔6B→<D→C>前提〔7D→C<3>,<6>〔8D<5>,<7>12、A→<CB>,B→A,D→C=>A→D證明：〔1A附加前提<2>A→<CB>前提<3>CB〔1,〔2B→A前提B〔1,〔4C〔3,〔5D→C前提D〔6,〔7A→DCP,〔1,〔813、<PQ><RQ>〔PRQ證明、<PQ><RQ><PQ><RQ><PR>Q〔PRQ<PR>Q14、P<QP>P<PQ>證明、P<QP>P<QP><P><PQ>P<PQ>15、〔PQ〔PR,<QR>,SPS證明、<1>〔PQ〔PR前提〔2P<QR><1>〔3<QR>前提〔4P〔2,<3><5>SP前提<6>S<4>,<5>16、PQ,QR,RSP證明、<1>P附加前提〔2PQ前提〔3Q〔1,〔2〔4QR前提<5>R〔3,〔4<6>RS前提〔7R〔6〔8RR〔5,〔717、用真值表法證明ＰＱ<ＰＱ><ＱＰ>證明、列出兩個(gè)公式的真值表：PQPQ〔PQ〔QPFFFTTFTTTTFFFFTT由定義可知,這兩個(gè)公式是等價(jià)的。18、P→QP→<PQ>證明：設(shè)P→<PQ>為F,則P為T(mén),PQ為F。所以P為T(mén),Q為F,從而P→Q也為F。所以P→QP→<PQ>。19、用先求主范式的方法證明<P→Q><P→R><P→〔QR證明：先求出左右兩個(gè)公式的主合取范式<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>它們有一樣的主合取范式,所以它們等價(jià)。20、<P→Q><QR>P證明：設(shè)<P→Q><QR>為T(mén),則P→Q和<QR>都為T(mén)。即P→Q和QR都為T(mén)。故P→Q,Q和R>都為T(mén),即P→Q為T(mén),Q和R都為F。從而P也為F,即P為T(mén)。從而<P→Q><QR>P21、為慶祝九七香港回歸祖國(guó),四支足球隊(duì)進(jìn)行比賽,已知情況如下,問(wèn)結(jié)論是否有效?前提:<1>若A隊(duì)得第一,則B隊(duì)或C隊(duì)獲亞軍;若C隊(duì)獲亞軍,則A隊(duì)不能獲冠軍;若D隊(duì)獲亞軍,則B隊(duì)不能獲亞軍;A隊(duì)獲第一;結(jié)論:<5>D隊(duì)不是亞軍。證明：設(shè)A：A隊(duì)得第一;B:B隊(duì)獲亞軍;C:C隊(duì)獲亞軍;D:D隊(duì)獲亞軍;則前提符號(hào)化為A〔BC,CA,DB,A；結(jié)論符號(hào)化為D。本題即證明A〔BC,CA,DB,AD〔1A前提〔2A〔BC前提〔3BC〔1,〔2〔4CA前提〔5C〔1,〔4〔6B〔3,〔5〔7DB前提〔8D〔6,〔722、用推理規(guī)則證明PQ,<QR>,PR不能同時(shí)為真。證明：<1>PR前提<2>P<1><3>PQ前提<4>Q<2>,<3><5><QR>前提<6>QR<5><7>Q<6><8>QQ<4>,<7><集合論部分>四、設(shè)Ａ,Ｂ,Ｃ是三個(gè)集合,證明：1、A<B－C>＝<AB>－<AC>證明：<AB>－<AC>=<AB>=<AB>〔=<AB><AB>=AB=A〔B=A〔B-C2、<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=證明：設(shè)A=B,則AB=〔A-B〔B-A==。設(shè)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=證明：因?yàn)锽=A-B,所以B=BB=〔A-BB=。從而A=A-B=B=。11、A=<A-B><A-C>ABC=證明：因?yàn)?lt;A-B><A-C>=<A><A>=A<>=A=A-<BC>,且A=<A-B><A-C>,所以A=A-<BC>,故ABC=。因?yàn)锳BC=,所以A-<BC>=A。而A-<BC>=<A-B><A-C>,所以A=<A-B><A-C>。12、<A-B><A-C>=ABC證明：因?yàn)?lt;A-B><A-C>=<A><A>=A<>=A=A-<BC>,且<A-B><A-C>=,所以=A-<BC>,故ABC。因?yàn)锳BC,所以A-<BC>=A。而A-<BC>=<A-B><A-C>,所以A=<A-B><A-C>。13、<A-B><B-A>=AB=證明：因?yàn)?lt;A-B><B-A>=A,所以B-AA。但<B-A>A=,故B-A=。即BA,從而B(niǎo)=〔否則A-BA,從而與<A-B><B-A>=A矛盾。因?yàn)锽=,所以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-BB=〔AB-B當(dāng)且僅當(dāng)B=。證明： 當(dāng)B=時(shí),因?yàn)椤睞-BB=〔A-=A,〔AB-B=〔A-=A,所以〔A-BB=〔AB-B。 用反證法證明。假設(shè)B,則存在bB。因?yàn)閎B且bAB,所以b〔AB-B。而顯然b〔A-BB。故這與已知〔A-BB=〔AB-B矛盾。五、證明或解答：〔數(shù)理邏輯、集合論與二元關(guān)系部分1、設(shè)個(gè)體域是自然數(shù),將下列各式翻譯成自然語(yǔ)言：<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,對(duì)任意自然數(shù)y滿足xy=1;〔2對(duì)每個(gè)自然數(shù)x,存在自然數(shù)y滿足xy=1;〔3對(duì)每個(gè)自然數(shù)x,存在自然數(shù)y滿足xy=0;〔4存在自然數(shù)x,對(duì)任意自然數(shù)y滿足xy=1;〔5對(duì)每個(gè)自然數(shù)x,存在自然數(shù)y滿足xy=x;〔6存在自然數(shù)x,對(duì)任意自然數(shù)y滿足xy=x;〔7對(duì)任意自然數(shù)x,y,存在自然數(shù)z滿足x-y=z。2、設(shè)A<x,y,z>:x+y=z,M〔x,y,z:xy=z,L<x,y>:x<y,G<x,y>:x>y,個(gè)體域?yàn)樽匀粩?shù)。將下列命題符號(hào)化：〔1沒(méi)有小于0的自然數(shù);〔2x<z是x<y且y<z的必要條件;〔3若x<y,則存在某些z,使z<0,xz>yz;〔4存在x,對(duì)任意y使得xy=y;〔5對(duì)任意x,存在y使x+y=x。答：〔1x〔G<x,0>M〔0,0,x或xL<x,0>〔2xyz<<L<x,y>L<y,z>>L<x,z>>〔3xy<<L<x,y>z<L<z,0>G<xz,yz>>>〔4xyM〔x,y,y〔5xyA<x,y,x>3、列出下列二元關(guān)系的所有元素：〔1A={0,1,2},B={0,2,4},R={<x,y>|x,y};〔2A={1,2,3,4,5},B={1,2},R={<x,y>|2x+y4且x且yB};〔3A={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、對(duì)任意集合A,B,證明：若AA=BB,則B=B。證明：若B=,則BB=。從而AA=。故A=。從而B(niǎo)=A。若B,則BB。從而AA。對(duì),<x,x>BB。因?yàn)锳A=BB,則<x,x>A。從而xA。故BA。同理可證,AB。故B=A。5、對(duì)任意集合A,B,證明：若A,AB=AC,則B=C。證明：若B=,則AB=。從而AC=。因?yàn)锳,所以C=。即B=C。若B,則AB。從而AC。對(duì),因?yàn)锳,所以存在yA,使<y,x>B。因?yàn)锳B=AC,則<y,x>C。從而xC。故BC。同理可證,CB。故B=C。6、設(shè)A={a,b},B={c}。求下列集合：<1>A{0,1}B；<2>B2A；<3><AB>2;<4>P<A>A。解：〔1A{0,1}B={<a,0,c>,<a,1,c>,<b,0,c>,<b,1,c>};〔2B2A〔3<AB>2={<a,c,a,c>,<a,c,b,c>,<b,c,a,c>,<b,c,b,c>};〔4P<A>A={<,a>,<,b>,<{a},a>,<{a},b>,<,a>,<,b>,<A,a>,<A,b>}。7、設(shè)全集U={a,b,c,d,e},A={a,d},B={a,b,c},C={b,d}。求下列各集合：〔1AB；〔2；〔3<A>C;〔4P<A>-P<B>;〔5<A-B><B-C>;〔6<AB>C;解：<1>AB={a};<2>={a,b,c,d,e};<3>〔AC={b,d};<4>P<A>-P<B>={0wqf5mn,{a,d}};<5><A-B><B-C>={d,c,a};<6><AB>C={b,d}。8、設(shè)A,B,C是任意集合,證明或否定下列斷言：〔1若AB,且BC,則AC；〔2若AB,且BC,則AC;〔3若AB,且BC,則AC；〔4若AB,且BC,則AC；證明：<1>成立。對(duì)xA,因?yàn)锳B,所以xB。又因?yàn)锽C,所以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>成立。因?yàn)锳B,且BC,所以AC。9、A上的任一良序關(guān)系一定是A上的全序關(guān)系。證明：a,b∈A,則{a,b}是A的一個(gè)非空子集?！苁茿上的良序關(guān)系,{a,b}有最小元。若最小元為a,則a≤b；否則b≤a。從而≤為A上的的全序關(guān)系。10、若R和S都是非空集A上的等價(jià)關(guān)系,則RS是A上的等價(jià)關(guān)系。證明：a∈A,因?yàn)镽和S都是A上的等價(jià)關(guān)系,所以xRx且xSx。故xRSx。從而RS是自反的。a,b∈A,aRSb,即aRb且aSb。因?yàn)镽和S都是A上的等價(jià)關(guān)系,所以bRa且bSa。故bRSa。從而RS是對(duì)稱的。a,b,c∈A,aRSb且bRSc,即aRb,aSb,bRc且bSc。因?yàn)镽和S都是A上的等價(jià)關(guān)系,所以aRc且aSc。故aRSc。從而RS是傳遞的。故RS是A上的等價(jià)關(guān)系。11、設(shè)RA×A,則R自反IAR。證明：xA,R是自反的,xRx。即<x,x>R,故IAR。xA,IAR,<x,x>R。即xRx,故R是自反的。12、設(shè)A是集合,RA×A,則R是對(duì)稱的R＝R－1。證明：<x,y>R,R是對(duì)稱的,yRx。即<y,x>R,故<x,y>R_1。從而RR-1。反之<y,x>R-1,即<x,y>R。R是對(duì)稱的,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是對(duì)稱的。13、設(shè)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>,則由合成關(guān)系的定義知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〔RTR<ST>。故R<ST>=〔RS〔RT。<2><x,z>R<ST>,則由合成關(guān)系的定義知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、設(shè)〈A,≤〉為偏序集,BA,若B有最大<小>元、上<下>確界,則它們是惟一的。證明：設(shè)a,b都是B的最大元,則由最大元的定義ab,ba。是A上的偏序關(guān)系,a=b。即B如果有最大元?jiǎng)t它是惟一的。15、設(shè)A={1,2,3},寫(xiě)出下列圖示關(guān)系的關(guān)系矩陣,并討論它們的性質(zhì)：111232323解：〔1R={<2,1>,<3,1>,<2,3>};MR=;它是反自反的、反對(duì)稱的、傳遞的；〔2R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>};MR=;它是反自反的、對(duì)稱的；〔3R={<1,2>,<2,1>,<1,3>,<3,3>};MR=;它既不是自反的、反自反的、也不是對(duì)稱的、反對(duì)稱的、傳遞的。16、設(shè)A={1,2,…,10}。下列哪個(gè)是A的劃分？若是劃分,則它們誘導(dǎo)的等價(jià)關(guān)系是什么？〔1B={{1,3,6},{2,8,10},{4,5,7}};〔2C={{1,5,7},{2,4,8,9},{3,5,6,10}};〔3D={{1,2,7},{3,5,10},{4,6,8},{9}}解：〔1和〔2都不是A的劃分?！?是A的劃分。其誘導(dǎo)的等價(jià)關(guān)系是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}上的等價(jià)關(guān)系,R=I{<1,5>,<5,1>,<2,4>,<4,2>,<3,6>,<6,3>}求R誘導(dǎo)的劃分。解：R誘導(dǎo)的劃分為{{1,5},{2,4},{3,6}}。18、A上的偏序關(guān)系的Hasse圖如下。下列哪些關(guān)系式成立：ab,ba,ce,ef,df,cf；分別求出下列集合關(guān)于的極大〔小元、最大〔小元、上〔下界及上〔下確界〔若存在的話：<a>A;<b>{b,d};<c>{b,e};<d>{b,d,e}aefbdc解：<1>ba,ce,df,cf成立；<2><a>的極大元為a,e,f,極小元為c;無(wú)最大元,c是最小元；無(wú)上界,下界是c;無(wú)上確界,下確界是c。<b>的極大元為b,d,極小元為b,d;無(wú)最大元和最小元；上界是e,下界是c;上確界是e,下確界是c。<c>的極大元為e,極小元為b;最大元是e,b是最小元；上界是e,下界是b;上確界是e,下確界是b。<d>的極大元為e,極小元為b,d;最大元是e,無(wú)最小元；上界是e,下界是c;上確界是e,下確界是c?！舶肴号c群部分19、求循環(huán)群C12={e,a,a2,…,a11}中H={e,a4,a8}的所有右陪集。解：因?yàn)閨C12|=12,|H|=3,所以H的不同右陪集有4個(gè)：H,{a,a5,a9},{a2,a6,a10},{a3,a7,a11}。20、求下列置換的運(yùn)算：解：〔1=〔2===21、試求出8階循環(huán)群的所有生成元和所有子群。解：設(shè)G是8階循環(huán)群,a是它的生成元。則G={e,a,a2,..,a7}。由于ak是G的生成元的充分必要條件是k與8互素,故a,a3,a5,a7是G的所有生成元。因?yàn)檠h(huán)群的子群也是循環(huán)群,且子群的階數(shù)是G的階數(shù)的因子,故G的子群只能是1階的、2階的、4階的或8階的。因?yàn)閨e|=1,|a|=|a3|=|a5|=8,|a2|=|a6|=8,|a4|=2,且G的子群的生成元是該子群中a的最小正冪,故G的所有子群除兩個(gè)平凡子群外,還有{e,a4},{e,a2,a4,a6}。22、I上的二元運(yùn)算*定義為：a,bI,a*b=a+b-2。試問(wèn)<I,*>是循環(huán)群?jiǎn)幔拷猓?lt;I,*>是循環(huán)群。因?yàn)?lt;I,*>是無(wú)限階的循環(huán)群,則它只有兩個(gè)生成元。1和3是它的兩個(gè)生成元。因?yàn)閍n=na-2<n-1>,故1n=n-2<n-1>=2-n。從而對(duì)任一個(gè)kI,k=2-<2-k>=12-k,故1是的生成元。又因?yàn)?和3關(guān)于*互為逆元,故3也是<I,*>的生成元。23、設(shè)<G,·>是群,aG。令H={xG|a·x=x·a}。試證：H是G的子群。證明：c,dH,則對(duì)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的元素的個(gè)數(shù)一定是奇數(shù)。證明：設(shè)<G,·>是偶數(shù)階群,則由于群的元素中階為1的只有一個(gè)單位元,階大于2的元素是偶數(shù)個(gè),剩下的元素中都是階為2的元素。故偶數(shù)階群中階為2的元素一定是奇數(shù)個(gè)。25、證明：有限群中階大于2的元素的個(gè)數(shù)一定是偶數(shù)。證明：設(shè)<G,·>是有限群,則aG,有|a|=|a-1|。且當(dāng)a階大于2時(shí),a-1。故階數(shù)大于2的元素成對(duì)出現(xiàn),從而其個(gè)數(shù)必為偶數(shù)。26、試求<N6,+6>中每個(gè)元素的階。解：0是<N6,+6>中關(guān)于+6的單位元。則|0|=1；|1|=|5|=6,|2|=|4|=3,|3|=2。27、設(shè)<G,·>是群,a,bG,ae,且a4·b=b·a5。試證a·bb·a。證明：用反證法證明。假設(shè)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。因?yàn)閍4·b=b·a5,所以b·a5=b·a4。由消去律得,a=e。這與已知矛盾。28、I上的二元運(yùn)算*定義為：a,bI,a*b=a+b-2。試證：<I,*>為群。證明：〔1a,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>,從而*滿足結(jié)合律?！?記e=2。對(duì)aI,a*2=a+2-2=a=2+a-2=2*a.。故e=2是I關(guān)于運(yùn)算*的單位元。〔3對(duì)aI,因?yàn)閍*〔4-a=a+4-a-2=2=e=4-a+a-2=<4-a>*a。故4-a是a關(guān)于運(yùn)算*的逆元。綜上所述,<I,*>為群。29、設(shè)<S,·>為半群,aS。令Sa={ai|iI+}。試證<Sa,·>是<S,·>的子半群。證明：b,cSa,則存在k,lI+,使得b=ak,c=al。從而b·c=ak·al=ak+l。因?yàn)閗+lI+,所以b·cSa,即Sa關(guān)于運(yùn)算·封閉。故<Sa,·>是<S,·>的子半群。30、單位元有惟一逆元。證明：設(shè)<G,>是一個(gè)群,e是關(guān)于運(yùn)算的單位元。若e1,e2都是e的逆元,即e1*e=e且e2*e=e。因?yàn)閑是關(guān)于運(yùn)算的單位元,所以e1=e1*e=e=e2*e=e2。即單位元有惟一逆元。31、設(shè)e和0是關(guān)于A上二元運(yùn)算*的單位元和零元,如果|A|>1,則e0。證明：用反證法證明。假設(shè)e=0。對(duì)A的任一元素a,因?yàn)閑和0是A上關(guān)于二元運(yùn)算*的單位元和零元,則a=a*e=a*0=0。即A的所有元素都等于0,這與已知條件|A|>1矛盾。從而假設(shè)錯(cuò)誤。即e0。32、證明在元素不少于兩個(gè)的群中不存在零元。證明：〔用反證法證明設(shè)在素不少于兩個(gè)的群<G,>中存在零元。對(duì)aG,由零元的定義有a*=。 <G,>是群,關(guān)于*消去律成立。a=e。即G中只有一個(gè)元素,這與|G|2矛盾。故在元素不少于兩個(gè)的群中不存在零元。33、證明在一個(gè)群中單位元是惟一的。證明：設(shè)e1,e2都是群〈G,*〉的單位元。則e1=e1*e2=e2。所以單位元是惟一的。34、設(shè)a是一個(gè)群〈G,*〉的生成元,則a-1也是它的生成元。證明：xG,因?yàn)閍是〈G,*〉的生成元,所以存在整數(shù)k,使得x=a。故x=<<a>>=<<a>>=<a>。從而a-1也是〈G,*〉的生成元。35、在一個(gè)偶數(shù)階群中一定存在一個(gè)2階元素。證明：群中的每一個(gè)元素的階均不為0且單位元是其中惟一的階為1的元素。因?yàn)槿我浑A大于2的元素和它的逆元的階相等。且當(dāng)一個(gè)元素的階大于2時(shí),其逆元和它本身不相等。故階大于2的元素是成對(duì)的。從而階為1的元素與階大于2的元素個(gè)數(shù)之和是奇數(shù)。因?yàn)樵撊旱碾A是偶數(shù),從而它一定有階為2的元素。36、代數(shù)系統(tǒng)<G,*>是一個(gè)群,則G除單位元以外無(wú)其它等冪元。證明：設(shè)e是該群的單位元。若a是<G,*>的等冪元,即a*a=a。因?yàn)閍*e=a,所以a*a=a*e。由于運(yùn)算*滿足消去律,所以a=e。即G除單位元以外無(wú)其它等冪元。37、設(shè)<G,>是一個(gè)群,則對(duì)于a,b∈G,必有唯一的x∈G,使得ax=b。證明：因?yàn)閍-1*b∈G,且a*<a-1*b>=<a*a-1>*b=e*b=b,所以對(duì)于a,b∈G,必有x∈G,使得ax=b。若x1,x2都滿足要求。即ax1=b且ax2=b。故ax1=ax2。由于*滿足消去律,故x1=x2。從而對(duì)于a,b∈G,必有唯一的x∈G,使得ax=b。38、設(shè)半群<S,·>中消去律成立,則<S,·>是可交換半群當(dāng)且僅當(dāng)a,bS,〔a·b2=a2·b2。證明：a,bS,〔a·b2=<a·b>·<a·b>=<<a·b>·a>·b=<a·<a·b>>·b=<<a·a>·b>·b=<a·a>·<b·b>=a2·b2;a,bS,因?yàn)椤瞐·b2=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、設(shè)群<G,＊>除單位元外每個(gè)元素的階均為2,則<G,＊>是交換群。證明：對(duì)任一aG,由已知可得a*a=e,即a-1=a。對(duì)任一a,bG,因?yàn)閍*b=<a*b>-1=b-1*a-1=b*a,所以運(yùn)算*滿足交換律。從而＜G,*＞是交換群。40、設(shè)*是集合A上可結(jié)合的二元運(yùn)算,且a,bA,若a*b=b*a,則a=b。試證明：〔1aA,a*a=a,即a是等冪元；〔2a,bA,a*b*a=a;〔3a,b,cA,a*b*c=a*c。證明：〔1aA,記b=a*a。因?yàn)?是可結(jié)合的,故有b*a=<a*a>*a=a*<a*a>=a*b。由已知條件可得a=a*a。〔2a,bA,因?yàn)橛伞?,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?！?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、設(shè)<G,·>是群,作f:GG,aa-1。證明：f是G的自同構(gòu)G是交換群。證明：設(shè)f是G的自同構(gòu)。對(duì)a,bG,a·b=<b-1·a-1>-1=<f<b>·f<a>>-1=<f<b·a>>-1=<<b·a>-1>-1=b·a。故運(yùn)算·滿足交換律,即G是可交換群。因?yàn)楫?dāng)ab時(shí),a-1b-1,即f<a>f<b>,故f是G到G中的一個(gè)單一函數(shù)。又對(duì)aG,有f<a-1>=<a-1>-1=a。故f是G到G上的滿函數(shù)。從而f是G到G上的自同構(gòu)。對(duì)a,bG,因?yàn)镚是可交換群,故f<a·b>=<a·b>-1=<b·a>-1=a-1·b-1=f<a>·f<b>。故f滿足同態(tài)方程。從而f是G的自同構(gòu)。42、若群<G,＊>的子群<H,＊>滿足|G|＝2|H|,則<H,＊>一定是群<G,＊>的正規(guī)子群。證明：由已知可知,G關(guān)于H有兩個(gè)不同的左陪集H,H1和兩個(gè)不同的右陪集H,H2。因?yàn)镠H1=且HH1=G,HH2=且HH2=G,故H1=G-H=H2。對(duì)aG,若aH,則aH=H,Ha=H。否則因?yàn)閍G-H,故aHH,HaH。從而aH=Ha=G-H。故H是G的不變子群。43、設(shè)H和K都是G的不變子群。證明：HK也是G的不變子群。證明：因?yàn)镠和K都是G的不變子群,所以HK是G的子群。對(duì)aG,hHK,有a·h·a-1a·H·a-1,·h·a-1a·K·a-1。因?yàn)镠和K都是G的不變子群,所以a·h·a-1H且a·h·a-1K。從而a·h·a-1HK。故HK是G的不變子群。44、設(shè)群G的中心為C〔G={aG|xG,a·x=x·a}。證明C〔G是G的不變子群。證明：先證C〔G是G的子群。a,bC〔G,對(duì)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的不變子群。對(duì)aG,hC<G>,記b=a·h·a-1。下證bC<G>。因?yàn)閔C<G>,所以b=<a·h>·a-1=〔h·a·a-1=h·<a·a-1>=hC<G>。故C〔G是G的不變子群。45、設(shè)<G,·>是沒(méi)有非平凡子群的有限群。試證：G是平凡群或質(zhì)數(shù)階的循環(huán)群。證明：若G是平凡群,則結(jié)論顯然成立。否則設(shè)<G,·>的階為n。任取aG且ae,記H=〔a<由a生成的G的子群>。顯然H{e},且G沒(méi)有非平凡子群,故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是質(zhì)數(shù)。故G是質(zhì)數(shù)階的循環(huán)群。綜上所述,G是平凡群或質(zhì)數(shù)階的循環(huán)群。46、設(shè)H和K都是G的有限子群,且|H|與|K|互質(zhì)。試證：HK={e}。證明：用反證法證明。若HK{e}。則HK是一個(gè)元素個(gè)數(shù)大于1的有限集。先證HK也是G的子群,從而也是H和K的子群。a,bHK,則a,bH且a,bK。因?yàn)镠和K都是G的子群,故a·b,a-1H且a·b,a-1K。從而a·bHK,a-1HK。故HK是G的子群,從而也是H和K的子群。由拉格朗日定理可知,|HK|是|H|和|K|的因子,這與已知矛盾。47、素?cái)?shù)階循環(huán)群的每個(gè)非單位元都是生成元。證明：設(shè)<G,*>是p階循環(huán)群,p是素?cái)?shù)。對(duì)G中任一非單位元a。設(shè)a的階為k,則k1。由拉格朗日定理,k是p的正整因子。因?yàn)閜是素?cái)?shù),故k=p。即a的階就是p,即群G的階。故a是G的生成元。48、若<S,>是可交換獨(dú)異點(diǎn),T為S中所有等冪元的集合,則<T,>是<S,>的子獨(dú)異點(diǎn)。證明： ee=e,eT,即T是S的非空子集。 a,bT,<S,>是可交換獨(dú)異點(diǎn),<ab><ab>=<<ab>a>b=<a<ba>>b=〔a<ab>b=<<aa>b>b=<aa><bb>=ab,即abT。故<T,>是<S,>的子獨(dú)異點(diǎn)。49、設(shè)<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,所以由定理知,n|km。即p|qm。但p和q互質(zhì),故p|m。由于p和m都是正整數(shù),所以p=m。即｜ak｜＝。50、設(shè)<G,>是有限群,|G|＝n,則a∈G,|a|n。證明：aG,由封閉性及|G|=n可知a,a2,…,an,an+1中必有相同的元素,不妨設(shè)為ak=am,k<m。由消去律得am-k=e。從而|a|m-kn。51、設(shè)G＝<a>,若G為無(wú)限群,則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|無(wú)限矛盾。從而km=1,即k=1,m=1或k=-1,m=-1。故c=a或c=a-1。從而G只有兩個(gè)生成元a和a-1。52、設(shè)G＝<a>,{e}HG,am是H中a的最小正冪,則〔1H＝<am>；〔2若G為無(wú)限群,則H也是無(wú)限群；證明：〔1bH,kI,使得b=ak。令k=mq+r,0r<m。則ar=ak-mq=aka-mq=b<am>-q。因?yàn)閎,amH,且HG,所以arH。由于0r<m,且am是H中a的最小正冪,故r=0,即k=mq。從而b=<am>q。故am是H的生成元?！?因?yàn)閧e}H,故H的生成元為am〔m0。因?yàn)镚是無(wú)限群,所以a的階是無(wú)限的,從而am的階也是無(wú)限的,故H也是無(wú)限群。53、設(shè)G＝<a>,|G|＝n,則對(duì)于n的每一正因子d,有且僅有一個(gè)d階子群。因此n階循環(huán)群的子群的個(gè)數(shù)恰為n的正因子數(shù)。證明：對(duì)n的每一正因子d,令k=,b=ak,H={e,b,b2,…,bd-1}。因?yàn)閨a|=n,所以bd=<ak>d=akd=an=e且|b|=d。從而H中的元素是兩兩不同的,易證HG。故|H|=d。所以是G的一個(gè)d階子群。設(shè)H1是G的任一d階子群。則由定理知,H1＝<am>,其中am是H1中a的最小正冪,且|H|=。因?yàn)閨H|=d,所以m==k,即H=H1。從而H是G的惟一d階子群。設(shè)H是G的惟一的d階子群。若d=1,則結(jié)論顯然成立。否則H＝<am>,其中am是H中a的最小正冪。由定理知,d=。故d是n的一個(gè)正因子。54、設(shè)h是從群<G1,>到<G2,>的群同態(tài),G和G2的單位元分別為e1和e2,則〔1h<e1>=e2；〔2aG1,h<a-1>=h<a>-1；〔3若HG1,則h<H>G2；〔4若h為單一同態(tài),則aG1,|h<a>|=|a|。證明：<1>因?yàn)閔<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>。因?yàn)镠G,所以ab∈H,故cd∈h<H>。又c-1=<h<a>>-1=h<a-1>且a-1∈H,故c-1∈h<H>。由定理知h<H>G2。<4>若|a|=n,則an=e1。故<h<a>>n=h<an>=h<e1>=e2。從而h<a>的階也有限,且|h<a>|n。設(shè)|h<a>|=m,則h<am>=<h<a>>m=h<e1>=e2。因?yàn)閔是單一同態(tài),所以am=e1。即|a|m。故|h<a>|=|a|。若a的階是無(wú)限的,則類似于上述證明過(guò)程可以得出,h<a>的階也是無(wú)限的。故結(jié)論成立。55、有限群G的每個(gè)元素的階均能整除G的階。證明：設(shè)|G|=n,aG,則|a|=m。令H={e,a,a2,…,am-1}。則H是G的子群且|H|=m。由Lagrange定理知|H|能整除|G|,故a的階能整除G的階。56、證明：在同構(gòu)意義下,只有兩個(gè)四階群,且都是循環(huán)群。證明：在4階群G中,由Lagrange定理知,G中的元素的階只能是1,2或4。階為1的元素恰有一個(gè),就是單位元e.若G有一個(gè)4階元素,不妨設(shè)為a,則G=〔a,即G是循環(huán)群,從而是可交換群。若G沒(méi)有4階元素,則除單位元e外,G的其余3個(gè)階均為2。不妨記為a,b,c。因?yàn)閍,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,*>中,若G中的元素a的階是k,即|a|=k,則a-1的階也是k。證明：因?yàn)閨a|=k,所以ak=e。即〔a-1k=<ak>-1=e。從而a-1的階是有限的,且|a-1|k。同理可證,a的階小于等于|a-1|。故a-1的階也是k。58、在一個(gè)群<G,*>中,若A和B都是G的子群。若AB=G,則A=G或B=G。證明：用反證法證明。若AG且B