大学《离散数学》题库及答案

《离散数学》题库与答案一、选择或填空〔数理逻辑部分〕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、公式*((A(*)B(y，*))zC(y，z))D(*)中，自由变元是()，约束变元是()。答：*,y,*,z〔考察定义在公式*A和*A中，称*为指导变元，A为量词的辖域。在*A和*A的辖域中，*的所有出现都称为约束出现，即称*为约束变元，A中不是约束出现的其他变项那么称为自由变元。于是A(*)、B(y，*)和zC(y，z)中y为自由变元，*和z为约束变元，在D(*)中*为自由变元〕5、判断以下语句是不是命题。假设是，给出命题的真值。()北京是中华人民共和国的首都。(2)陕西师大是一座工厂。(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〕〔4〕8、设个体域为整数集，那么以下公式的意义是()。(1)*y(*+y=0)(2)y*(*+y=0)答：〔1〕对任一整数*存在整数y满足*+y=0〔2〕存在整数y对任一整数*满足*+y=09、设全体域D是正整数集合，确定以下命题的真值：(1)*y(*y=y)()(2)*y(*+y=y)()(3)*y(*+y=*)()(4)*y(y=2*)()答：〔1〕F(反证法：假假设存在，那么〔*-1〕*y=0对所有的*都成立，显然这个与前提条件相矛盾)〔2〕F〔同理〕〔3〕F〔同理〕〔4〕T〔对任一整数*存在整数y满足条件y=2*很明显是正确的〕10、设谓词P(*)：*是奇数，Q(*)：*是偶数，谓词公式*(P(*)Q(*))在哪个个体域中为真?()(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、谓词公式*(P(*)yR(y))Q(*)中量词*的辖域是〔〕。答：P(*)yR(y)〔一对括号就是一个辖域〕15、令R(*):*是实数，Q(*):*是有理数。那么命题〞并非每个实数都是有理数〞的符号化表示为〔〕。答：*(R(*)Q(*))〔集合论部分〕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={*|(*+1)4且*R},Q={*|5*+16且*R},那么以下命题哪个正确〔〕(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={*|(*-a)(*-b)(*-c)=0}(6)A6={*|*2-(a+b)*+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〕，〔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〕〔〔3〕的反例C为{｛0，1｝，0｝B为｛0，1｝，A为1很明显结论不对〕〔二元关系部分〕28、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈*,y〉|*=y2求(1)R(2)R-1答：〔1〕R={<1,1>,<4,2>}(2)R={<1,1>,<2,4>}〔考查二元关系的定义，R为R的逆关系，即R=｛<*,y>｝|<y,*>∈R〕29、举出集合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={<*,y>|t(<*,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的关系Ｒ＝｛〈*,y〉|*=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的关系Ｒ＝｛〈*,y〉|*=y2｝，求R和R-1的关系矩阵。答：R的关系矩阵=R的关系矩阵=36、集合A={1,2,…,10}上的关系R={<*,y>|*+y=10,*,yA}，那么R的性质为〔〕。(1)自反的(2)对称的(3)传递的，对称的(4)传递的答：〔2〕〔考查自反对称传递的定义〕〔代数系统部分〕37、设A={2,4,6}，A上的二元运算*定义为：a*b=ma*{a,b}，那么在独异点<A,*>中，单位元是()，零元是()。答：2，6〔单位元和零元的定义，单位元：e。*=*零元：θ。*=θ〕38、设A={3,6,9}，A上的二元运算*定义为：a*b=min{a,b}，那么在独异点<A,*>中，单位元是()，零元是()；答：9，3〔半群与群部分〕39、设〈G,*〉是一个群，那么(1)假设a,b,*∈G，a*=b，那么*=()；(2)假设a,b,*∈G，a*=ab，那么*=()。答：〔1〕ab〔2〕b〔考查群的性质，即群满足消去律〕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=()。答：〔1〕b(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=ma*{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}答：〔2〕56、一个图的哈密尔顿路是一条通过图中()的路。答：所有结点一次且恰好一次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)不能确定。答：〔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条边且每个顶点的度数都是2，那么图G有()个顶点。(1)10(2)4(3)8(4)16答：〔4〕72、设无向图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答：〔3〕76、在有n个顶点的连通图中，其边数〔〕。(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〕〔数理逻辑部分〕二、求以下各公式的主析取范式和主合取范式：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→(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→*)，(W*)，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→*)前提〔10〕Q→W〔9〕〔11〕S→*〔10〕〔12〕W〔7〕，〔10〕〔13〕*〔8〕，〔11〕〔14〕W*〔12〕，〔13〕〔15〕(W*)前提〔16〕(W*)(W*)〔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、用推理规那么证明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)证明：*(A-B)-C，有A-B且*C，即A，*B且*C。从而A，*B-C，故*A-(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矛盾。五、证明或解答：〔数理逻辑、集合论与二元关系部分〕1、设个体域是自然数，将以下各式翻译成自然语言：(1)*y〔*y=1〕;(2)*y(*y=1);(3)*y(*y=0);(4)*y〔*y=0〕;(5)*y(*y=*);(6)*y〔*y=*〕;(7)*yz(*-y=z)答：〔1〕存在自然数*，对任意自然数y满足*y=1;〔2〕对每个自然数*，存在自然数y满足*y=1;〔3〕对每个自然数*，存在自然数y满足*y=0;〔4〕存在自然数*，对任意自然数y满足*y=1;〔5〕对每个自然数*，存在自然数y满足*y=*;〔6〕存在自然数*，对任意自然数y满足*y=*;〔7〕对任意自然数*,y，存在自然数z满足*-y=z。2、设A(*,y,z):*+y=z,M〔*,y,z〕:*y=z,L(*,y):*<y,G(*,y):*>y，个体域为自然数。将以下命题符号化：〔1〕没有小于0的自然数;〔2〕*<z是*<y且y<z的必要条件;〔3〕假设*<y，那么存在某些z，使z<0,*z>yz;〔4〕存在*，对任意y使得*y=y;〔5〕对任意*，存在y使*+y=*。答：〔1〕*〔G(*,0)M〔0,0,*〕〕或*L(*,0)〔2〕*yz((L(*,y)L(y,z))L(*,z))〔3〕*y((L(*,y)z(L(z,0)G(*z,yz)))〔4〕*yM〔*,y,y〕〔5〕*yA(*,y,*)3、列出以下二元关系的所有元素：〔1〕A={0,1,2}，B={0,2,4}，R={<*,y>|*,y};〔2〕A={1,2,3,4,5}，B={1,2}，R={<*,y>|2*+y4且*且yB};〔3〕A={1,2,3}，B={-3,-2,-1,0,1}，R={<*,y>||*|=|y|且*且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。对,<*,*>BB。因为AA=BB，那么<*,*>A。从而*A。故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,*>B。因为AB=AC，那么<y,*>C。从而*C。故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>,<{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}。求以下各集合：〔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)={{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)成立。对*A,因为AB，所以*B。又因为BC，所以*C。即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上的等价关系，所以*R*且*S*。故*RS*。从而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。证明：*A，R是自反的，*R*。即<*,*>R，故IAR。*A，IAR，<*,*>R。即*R*，故R是自反的。12、设A是集合，RA×A，那么R是对称的R＝R－1。证明：<*,y>R，R是对称的，yR*。即<y,*>R，故<*,y>R_1。从而RR-1。反之<y,*>R-1,即<*,y>R。R是对称的，yR*。即<y,*>R，R_1R。故R=R-1。*，yA，假设<*,y>R，即<y,*>R-1。R=R-1，<y,*>R。即yR*，故R是对称的。13、设A,B,C和D均是集合，RA×B，SB×C，TC×D，那么(1)R(ST)=(RS)(RT)；(2)R(ST)(RS)(RT)；证明：〔1〕<*，z>R(ST)，那么由合成关系的定义知yB，使得<*，y>R且<y，z>ST。从而<*，y>R且<y，z>S或<*，y>R且<y，z>T，即<*，z>RS或<*，z>RT。故<*，z>〔RS〕〔RT〕。从而R(ST)〔RS〕〔RT〕。同理可证〔RS〕〔RT〕R(ST)。故R(ST)=〔RS〕〔RT〕。(2)<*，z>R(ST)，那么由合成关系的定义知yB，使得<*，y>R且<y，z>ST。从而<*，y>R且<y，z>S且<y，z>T，即<*，z>RS且<*，z>RT。故<*，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、求循环群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={*G|a·*=*·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,*>为群。证明：〔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也是它的生成元。证明：*G，因为a是〈G，*〉的生成元，所以存在整数k，使得*=a。故*=((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，必有唯一的*∈G，使得a*=b。证明：因为a-1*b∈G，且a*(a-1*b)=(a*a-1)*b=e*b=b，所以对于a,b∈G，必有*∈G，使得a*=b。假设*1,*2都满足要求。即a*1=b且a*2=b。故a*1=a*2。由于*满足消去律，故*1=*2。从而对于a,b∈G，必有唯一的*∈G，使得a*=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中的一个单一函数。又对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|*G,a·*=*·a}。证明C〔G〕是G的不变子群。证明：先证C〔G〕是G的子群。a,bC〔G〕，对*G,有a·*=*·a，b·*=*·b。故〔a·b〕·*=a·(b·*)=a·(*·b)=(a·*)·b=(*·a)·b=*·(a·b),a-1·*=*·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，所以由定理5.2.5知，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的最小正幂，那么〔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阶循环群的子群的个数恰为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阶子群。那么由定理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知