《离散数学》题库及答案解析

.PAGE.《离散数学》题库与答案一、选择或填空〔数理逻辑部分1、下列哪些公式为永真蕴含式？<A><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是假言推理,〔3,〔5,〔6都可以用蕴含等值式来证明出是永真蕴含式4、公式x<<A<x>B<y,x>>zC<y,z>>D<x>中,自由变元是<>,约束变元是<>。答：x,y,x,z〔考察定义在公式xA和xA中,称x为指导变元,A为量词的辖域。在xA和xA的辖域中,x的所有出现都称为约束出现,即称x为约束变元,A中不是约束出现的其他变项则称为自由变元。于是A<x>、B<y,x>和zC<y,z>中y为自由变元,x和z为约束变元,在D<x>中x为自由变元5、判断下列语句是不是命题。若是,给出命题的真值。<>北京是中华人民XX国的首都。<2>XX师大是一座工厂。<3>你喜欢唱歌吗？<4>若7+8＞18,则三角形有4条边。<5>前进！<6>给我一杯水吧！答：〔1是,T〔2是,F〔3不是〔4是,T〔5不是〔6不是〔命题必须满足是陈述句,不能是疑问句或者祈使句。6、命题"存在一些人是大学生"的否定是<>,而命题"所有的人都是要死的"的否定是<>。答：所有人都不是大学生,有些人不会死〔命题的否定就是把命题前提中的量词"换成存在,换成",然后将命题的结论否定,"且变或或变且"7、设P：我生病,Q：我去学校,则下列命题可符号化为<>。<1>只有在生病时,我才不去学校<2>若我生病,则我不去学校<3>当且仅当我生病时,我才不去学校<4>若我不生病,则我一定去学校答：〔1〔注意"只有……才……"和"除非……就……"两者都是一个形式的〔2〔3〔48、设个体域为整数集,则下列公式的意义是<>。<1>xy<x+y=0><2>yx<x+y=0>答：〔1对任一整数x存在整数y满足x+y=0〔2存在整数y对任一整数x满足x+y=09、设全体域D是正整数集合,确定下列命题的真值：<1>xy<xy=y><><2>xy<x+y=y><><3>xy<x+y=x><><4>xy<y=2x><>答：〔1F<反证法：假若存在,则〔x-1*y=0对所有的x都成立,显然这个与前提条件相矛盾>〔2F〔同理〔3F〔同理〔4T〔对任一整数x存在整数y满足条件y=2x很明显是正确的10、设谓词P<x>：x是奇数,Q<x>：x是偶数,谓词公式x<P<x>Q<x>>在哪个个体域中为真?<><1>自然数<2>实数<3>复数<4><1>--<3>均成立答：〔1〔在某个体域中满足不是奇数就是偶数,在整数域中才满足条件,而自然数子整数的子集,当然满足条件了11、命题"2是偶数或-3是负数"的否定是〔。答：2不是偶数且-3不是负数。12、永真式的否定是〔<1>永真式<2>永假式<3>可满足式<4><1>--<3>均有可能答：〔2〔这个记住就行了13、公式<PQ><PQ>化简为〔,公式Q<P<PQ>>可化简为〔。答：P,QP〔考查分配率和蕴含等值式知识的掌握14、谓词公式x<P<x>yR<y>>Q<x>中量词x的辖域是〔。答：P<x>yR<y>〔一对括号就是一个辖域15、令R<x>:x是实数,Q<x>:x是有理数。则命题"并非每个实数都是有理数"的符号化表示为〔。答：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>〔{a}是P〔A的一个元素17、在0〔之间写上正确的符号。<1>=<2><3><4>答：<4>〔空集没有任何元素,且是任何集合的子集18、若集合S的基数|S|=5,则S的幂集的基数|P<S>|=〔。答：32〔2的5次方考查幂集的定义,即幂集是集合S的全体子集构成的集合19、设P={x|<x+1>4且xR},Q={x|5x+16且xR},则下列命题哪个正确〔<1>QP<2>QP<3>PQ<4>P=Q答：〔3〔Q是集合R,P只是R中的一部分,所以P是Q的真子集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=A5〔集合具有无序性、确定性和互异性21、若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},{b}}答：〔2,〔424、判断下列命题哪几个正确？<><1>所有空集都不相等<2>{Ф}Ф<4>若A为非空集,则AA成立。答：〔225、设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成立。答：〔227、Ａ,Ｂ,Ｃ是三个集合,则下列哪几个推理正确：<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很明显结论不对〔二元关系部分28、设Ａ＝｛1,2,3,4,5,6｝,B={1,2,3},从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2求<1>R<2>R-1答：〔1R={<1,1>,<4,2>}<2>R={<1,1>,<2,4>}〔考查二元关系的定义,R为R的逆关系,即R=｛<x,y>｝|<y,x>∈R29、举出集合A上的既是等价关系又是偏序关系的一个例子。<>答：A上的恒等关系30、集合A上的等价关系的三个性质是什么？<>答：自反性、对称性和传递性31、集合A上的偏序关系的三个性质是什么？<>答：自反性、反对称性和传递性<题29,30,31全是考查定义>32、设S={１,２,３,４},Ａ上的关系Ｒ＝｛〈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、设Ａ＝｛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。答：〔1R={<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〔考查自反对称传递的定义〔代数系统部分37、设A={2,4,6},A上的二元运算*定义为：a*b=max{a,b},则在独异点<A,*>中,单位元是<>,零元是<>。答：2,6〔单位元和零元的定义,单位元：e。x=x零元：θ。x=θ38、设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=<>。答：〔1ab〔2b〔考查群的性质,即群满足消去律40、设a是12阶群的生成元,则a2是<>阶元素,a3是<>阶元素。答：6,441、代数系统<G,*>是一个群,则G的等幂元是<>。答：单位元〔由a^2=a,用归纳法可证a^n=a*a^<n-1>=a*a=a,所以等幂元一定是幂等元,反之若a^n=a对一切N成立,则对n=2也成立,所以幂等元一定是等幂元,并且在群<G,*>中,除幺元即单位元e外不可能有任何别的幂等元42、设a是10阶群的生成元,则a4是<>阶元素,a3是<>阶元素答：5,10〔若一个群G的每一个元都是G的某一个固定元a的乘方,我们就把G叫做循环群；我们也说,G是由元a生成的,并且用符号G=<a>表示,且称a为一个生成元。并且一元素的阶整除群的阶43、群<G,*>的等幂元是<>,有<>个。答：单位元,1〔在群<G,*>中,除幺元即单位元e外不可能有任何别的幂等元44、素数阶群一定是<>群,它的生成元是<>。答：循环群,任一非单位元〔证明如下：任一元素的阶整除群的阶。现在群的阶是素数p,所以元素的阶要么是1要么是p。G中只有一个单位元,其它元素的阶都不等于1,所以都是p。任取一个非单位元,它的阶等于p,所以它生成的G的循环子群的阶也是p,从而等于整个群G。所以G等于它的任一非单位元生成的循环群45、设〈G,*〉是一个群,a,b,c∈G,则<1>若ca=b,则c=<>；<2>若ca=ba,则c=<>。答：〔1b<2>b〔群的性质46、<H,,>是<G,,>的子群的充分必要条件是<>。答：<H,,>是群或a,bG,abH,a-1H或a,bG,ab-1H47、群＜A,*＞的等幂元有<>个,是<>,零元有<>个。答：1,单位元,048、在一个群〈G,*〉中,若G中的元素a的阶是k,则a-1的阶是<>。答：k49、在自然数集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>〔格与布尔代数部分52、下列哪个偏序集构成有界格〔<1>〔N,<2>〔Z,<3>〔{2,3,4,6,12},|〔整除关系<4><P<A>,>答：<4>〔考查幂集的定义53、有限布尔代数的元素的个数一定等于〔。<1>偶数<2>奇数<3>4的倍数<4>2的正整数次幂答：<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}答：〔256、一个图的哈密尔顿路是一条通过图中<>的路。答：所有结点一次且恰好一次57、在有向图中,结点v的出度deg+<v>表示<>,入度deg-<v>表示<>。答：以v为起点的边的条数,以v为终点的边的条数58、设G是一棵树,则G的生成树有<>棵。<1>0<2>1<3>2<4>不能确定答：159、n阶无向完全图Kn的边数是<>,每个结点的度数是<>。答：,n-160、一棵无向树的顶点数n与边数m关系是<>。答：m=n-161、一个图的欧拉回路是一条通过图中<>的回路。答：所有边一次且恰好一次62、有n个结点的树,其结点度数之和是<>。答：2n-2〔结点度数的定义63、下面给出的集合中,哪一个不是前缀码<>。<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个结点的有向完全图边数是<>,每个结点的度数是<>。答：n<n-1>,2n-265、一个无向图有生成树的充分必要条件是<>。答：它是连通图66、设G是一棵树,n,m分别表示顶点数和边数,则<1>n=m<2>m=n+1<3>n=m+1<4>不能确定。答：〔367、设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。答：〔170、设T是一棵树,则T是一个连通且<>图。答：无简单回路71、设无向图G有16条边且每个顶点的度数都是2,则图G有<>个顶点。<1>10<2>4<3>8<4>16答：〔472、设无向图G有18条边且每个顶点的度数都是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、任一有向图中,度数为奇数的结点有<>个。答：偶数75、具有6个顶点,12条边的连通简单平面图中,每个面都是由<>条边围成？<1>2<2>4<3>3<4>5答：〔376、在有n个顶点的连通图中,其边数〔。<1>最多有n-1条<2>至少有n-1条<3>最多有n条<4>至少有n条答：〔277、一棵树有2个2度顶点,1个3度顶点,3个4度顶点,则其1度顶点为〔。<1>5<2>7<3>8<4>9答：〔478、若一棵完全二元〔叉树有2n-1个顶点,则它〔片树叶。<1>n<2>2n<3>n-1<4>2答：〔179、下列哪一种图不一定是树〔。<1>无简单回路的连通图<2>有n个顶点n-1条边的连通图<3>每对顶点间都有通路的图<4>连通但删去一条边便不连通的图答：〔380、连通图G是一棵树当且仅当G中〔。<1>有些边是割边<2>每条边都是割边<3>所有边都不是割边<4>图中存在一条欧拉路径答：〔2〔数理逻辑部分二、求下列各公式的主析取范式和主合取范式：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假设前提〔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、用真值表法证明ＰＱ<ＰＱ><ＱＰ>证明、列出两个公式的真值表：PQPQ〔PQ〔QPFFFTTFTTTTFFFFTT由定义可知,这两个公式是等价的。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〔1A前提〔2A〔BC前提〔3BC〔1,〔2〔4CA前提〔5C〔1,〔4〔6B〔3,〔5〔7DB前提〔8D〔6,〔722、用推理规则证明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-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=证明：设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-BB=。从而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-BB=〔AB-B当且仅当B=。证明： 当B=时,因为〔A-BB=〔A-=A,〔AB-B=〔A-=A,所以〔A-BB=〔AB-B。 用反证法证明。假设B,则存在bB。因为bB且bAB,所以b〔AB-B。而显然b〔A-BB。故这与已知〔A-BB=〔AB-B矛盾。五、证明或解答：〔数理逻辑、集合论与二元关系部分1、设个体域是自然数,将下列各式翻译成自然语言：<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存在自然数x,对任意自然数y满足xy=1;〔2对每个自然数x,存在自然数y满足xy=1;〔3对每个自然数x,存在自然数y满足xy=0;〔4存在自然数x,对任意自然数y满足xy=1;〔5对每个自然数x,存在自然数y满足xy=x;〔6存在自然数x,对任意自然数y满足xy=x;〔7对任意自然数x,y,存在自然数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,个体域为自然数。将下列命题符号化：〔1没有小于0的自然数;〔2x<z是x<y且y<z的必要条件;〔3若x<y,则存在某些z,使z<0,xz>yz;〔4存在x,对任意y使得xy=y;〔5对任意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、列出下列二元关系的所有元素：〔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、对任意集合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。解：〔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>,<{b},a>,<{b},b>,<A,a>,<A,b>}。7、设全集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>={{d},{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上的良序关系,{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〔RTR<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解：〔1R={<2,1>,<3,1>,<2,3>};MR=;它是反自反的、反对称的、传递的；〔2R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>};MR=;它是反自反的、对称的；〔3R={<1,2>,<2,1>,<1,3>,<3,3>};MR=;它既不是自反的、反自反的、也不是对称的、反对称的、传递的。16、设A={1,2,…,10}。下列哪个是A的划分？若是划分,则它们诱导的等价关系是什么？〔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的划分。〔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、求循环群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阶循环群的所有生成元和所有子群。解：设G是8阶循环群,a是它的生成元。则G={e,a,a2,..,a7}。由于ak是G的生成元的充分必要条件是k与8互素,故a,a3,a5,a7是G的所有生成元。因为循环群的子群也是循环群,且子群的阶数是G的阶数的因子,故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,*>是循环群吗？解：<I,*>是循环群。因为<I,*>是无限阶的循环群,则它只有两个生成元。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、证明：偶数阶群中阶为2的元素的个数一定是奇数。证明：设<G,·>是偶数阶群,则由于群的元素中阶为1的只有一个单位元,阶大于2的元素是偶数个,剩下的元素中都是阶为2的元素。故偶数阶群中阶为2的元素一定是奇数个。25、证明：有限群中阶大于2的元素的个数一定是偶数。证明：设<G,·>是有限群,则aG,有|a|=|a-1|。且当a阶大于2时,a-1。故阶数大于2的元素成对出现,从而其个数必为偶数。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,*>为群。证明：〔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>,从而*满足结合律。〔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,*〉的生成元,所以存在整数k,使得x=a。故x=<<a>>=<<a>>=<a>。从而a-1也是〈G,*〉的生成元。35、在一个偶数阶群中一定存在一个2阶元素。证明：群中的每一个元素的阶均不为0且单位元是其中惟一的阶为1的元素。因为任一阶大于2的元素和它的逆元的阶相等。且当一个元素的阶大于2时,其逆元和它本身不相等。故阶大于2的元素是成对的。从而阶为1的元素与阶大于2的元素个数之和是奇数。因为该群的阶是偶数,从而它一定有阶为2的元素。36、代数系统<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都满足要求。即ax1=b且ax2=b。故ax1=ax2。由于*满足消去律,故x1=x2。从而对于a,b∈G,必有唯一的x∈G,使得ax=b。38、设半群<S,·>中消去律成立,则<S,·>是可交换半群当且仅当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,因为〔a·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、设群<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。试证明：〔1aA,a*a=a,即a是等幂元；〔2a,bA,a*b*a=a;〔3a,b,cA,a*b*c=a*c。证明：〔1aA,记b=a*a。因为*是可结合的,故有b*a=<a*a>*a=a*<a*a>=a*b。由已知条件可得a=a*a。〔2a,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。〔3a,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中的一个单一函数。又对aG,有f<a-1>=<a-1>-1=a。故f是G到G上的满函数。从而f是G到G上的自同构。对a,bG,因为G是可交换群,故f<a·b>=<a·b>-1=<b·a>-1=a-1·b-1=f<a>·f<b>。故f满足同态方程。从而f是G的自同构。42、若群<G,＊>的子群<H,＊>满足|G|＝2|H|,则<H,＊>一定是群<G,＊>的正规子群。证明：由已知可知,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是平凡群或质数阶的循环群。证明：若G是平凡群,则结论显然成立。否则设<G,·>的阶为n。任取aG且ae,记H=〔a<由a生成的G的子群>。显然H{e},且G没有非平凡子群,故H=G。从而G一定是循环群,且a是G的生成元。若n是合数,则存在大于1的整数k,m,使得n=mk。记H={e,ak,<ak>2,…,<ak>m-1},易证H是G的子群,但1<|H|=m<n,故H是G的非平凡子群。这与已知矛盾。从而n是质数。故G是质数阶的循环群。综上所述,G是平凡群或质数阶的循环群。46、设H和K都是G的有限子群,且|H|与|K|互质。试证：HK={e}。证明：用反证法证明。若HK{e}。则HK是一个元素个数大于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、素数阶循环群的每个非单位元都是生成元。证明：设<G,*>是p阶循环群,p是素数。对G中任一非单位元a。设a的阶为k,则k1。由拉格朗日定理,k是p的正整因子。因为p是素数,故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,所以由定理知,n|km。即p|qm。但p和q互质,故p|m。由于p和m都是正整数,所以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的最小正幂,则〔1H＝<am>；〔2若G为无限群,则H也是无限群；证明：〔1bH,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阶循环群的子群的个数恰为n的正因子数。证明：对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阶子群。则由定理知,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的最小正幂。由定理知,d=。故d是n的一个正因子。54、设h是从群<G1,>到<G2,>的群同态,G和G2的单位元分别为e1和e2,则〔1h<e1>=e2；〔2aG1,h<a-1>=h<a>-1；〔3若HG1,则h<H>G2；〔4若h为单一同态,则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>。由定理知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是单一同态,所以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、证明：在同构意义下,只有两个四阶群,且都是循环群。证明：在4阶群G中,由Lagrange定理知,G中的元素的阶只能是1,2或4。阶为1的元素恰有一个,就是单位元e.若G有一个4阶元素,不妨设为a,则G=〔a,即G是循环群,从而是可交换群。若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-1k=<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且B