《离散数学》题库及答案.doc 68页

'《离散数学》题库答案一、选择或填空（数理逻辑部分）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、判断下列语句是不是命题。若是，给出命题的真值。()(1)北京是中华人民共和国的首都。(2)陕西师大是一座工厂。　(3)你喜欢唱歌吗？(4)若7+8＞18，则三角形有4条边。　(5)前进！(6)给我一杯水吧！答：（1）是，T（2）是，F（3）不是（4）是，T（5）不是（6）不是6、命题“存在一些人是大学生”的否定是()，而命题“所有的人都是要死的”的否定是()。答：所有人都不是大学生，有些人不会死68 7、设P：我生病，Q：我去学校，则下列命题可符号化为()。(1)　只有在生病时，我才不去学校(2)若我生病，则我不去学校(3)　当且仅当我生病时，我才不去学校(4)若我不生病，则我一定去学校答：（1）（2）（3）（4）8、设个体域为整数集，则下列公式的意义是()。(1)"x$y(x+y=0)(2)$y"x(x+y=0)答：（1）对任一整数x存在整数y满足x+y=0（2）存在整数y对任一整数x满足x+y=09、设全体域D是正整数集合，确定下列命题的真值：(1)"x$y(xy=y)　　(　　)　　(2)$x"y(x+y=y)　　(　　)(3)$x"y(x+y=x)　(　　)　　(4)"x$y(y=2x)　　(　　)答：（1）F（2）F（3）F（4）T10、设谓词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，QP14、谓词公式"x(P(x)Ú$yR(y))Q(x)中量词"x的辖域是（）。答：P(x)Ú$yR(y)15、令R(x):x是实数，Q(x):x是有理数。则命题“68 并非每个实数都是有理数”的符号化表示为（）。答："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的基数|S|=5，则S的幂集的基数|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）68 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）（二元关系部分）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上的偏序关系的三个性质是什么？()68 答：自反性、反对称性和传递性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=10,x,yA}，则R的性质为（）。(1)自反的　　(2)对称的　　(3)传递的，对称的(4)传递的答：（2）（代数结构部分）37、设A={2,4,6}，A上的二元运算*定义为：a*b=max{a,b}，则在独异点中，单位元是()，零元是()。68 答：2，638、设A={3,6,9}，A上的二元运算*定义为：a*b=min{a,b}，则在独异点中，单位元是()，零元是()；答：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、代数系统是一个群，则G的等幂元是(　　　　)。答：单位元42、设a是10阶群的生成元，则a4是()阶元素，a3是()阶元素。答：5，1043、群的等幂元是(　　)，有(　　　)个。答：单位元，144、素数阶群一定是()群,它的生成元是()。答：循环群，任一非单位元45、设〈G,*〉是一个群，a,b,c∈G，则(1)若ca=b，则c=()；(2)若ca=ba，则c=()。答：（1）b(2)b46、是的子群的充分必要条件是()。答：是群或"a，bG，abH，a-1H或"a,bG，ab-1H47、群＜A,*＞的等幂元有(　　　)个，是(　　　)，零元有(　　　)个。答：1，单位元，068 48、在一个群〈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、下面给出的集合中，哪一个是前缀码？(　　　　　　)68 (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-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个结点的有向完全图边数是()，每个结点的度数是()。答：n(n-1),2n-265、一个无向图有生成树的充分必要条件是()。68 答：它是连通图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={a，b，c，d，e}，E={,,,,},则G是有向图还是无向图？答：有向图74、任一有向图中，度数为奇数的结点有(　　　)个。答：偶数75、具有6个顶点，12条边的连通简单平面图中，每个面都是由(　　)条边围成？68 (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)R68 (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)68 （主析取范式）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(主合取范式)68 (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)Q68 (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))68 (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)(主合取范式)68 (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前提(3)Q（1），（2）(4)P→Q前提(5)P（3），（4）(6)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附加前提(5)C（3），（4）(6)C→(DE)前提(7)DE（5），（6）(8)F→(DE)前提68 (5)F（7），（8）(6)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)前提68 （16）(WX)(WX)（14），（15）5、(UV)→(MN),UP,P→(QS)，QS=>M证明：(1)QS附加前提（2）P→(QS)前提（3）P（1），（2）（4）UP前提（5）U（3），（4）（6）UV（5）（7）(UV)→(MN)前提（8）MN(6),(7)（9）M（8）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）68 （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前提68 （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）(4)B→A前提(5)B（1），（4）(6)C（3），（5）(7)D→C前提(8)D（6），（7）(9)A→DCP，（1），（8）13、(PQ)(RQ)（PR）Q68 证明、(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）68 （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)P68 证明、设(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队获亚军;(2)若C队获亚军，则A队不能获冠军;(3)若D队获亚军，则B队不能获亚军;(4)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前提68 (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=BóAB=　　证明：设A=B，则AB=（A-B）（B-A）==。68 设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=68 证明：因为(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的幂集）证明：68 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)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;68 （7）对任意自然数x,y，存在自然数z满足x-y=z。2、设A(x,y,z):x+y=z,M（x,y,z）:xy=z,L(x,y):xy，个体域为自然数。将下列命题符号化：（1）没有小于0的自然数;（2）xyz;（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};（2）A={1,2,3,4,5}，B={1,2}，R={|2x+y4且x且yB};（3）A={1,2,3}，B={-3,-2,-1,0,1}，R={||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。对,BB。因为AA=BB，则A。从而xA。故BA。68 同理可证，AB。故B=A。5、对任意集合A,B，证明：若A，AB=AC，则B=C。证明：若B=，则AB=。从而AC=。因为A，所以C=。即B=C。若B，则AB。从而AC。对,因为A，所以存在yA,使B。因为AB=AC，则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={,,,};（2）B2A={,};（3）(AB)2={,,,};（4）P(A)A={<,a>,<,b>,<{a},a>,<{a},b>,<{b},a>,<{b},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；68 （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。即R，故IAR。xA，IAR，R。即xRx，故R是自反的。68 12、设A是集合，RA×A，则R是对称的R＝R－1。证明：R，R是对称的，yRx。即R，故R_1。从而RR-1。反之R-1,即R。R是对称的，yRx。即R，R_1R。故R=R-1。x，yA，若R，即R-1。R=R-1，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）R(ST)，则由合成关系的定义知yB，使得R且ST。从而R且S或R且T，即RS或RT。故（RS）（RT）。从而R(ST)（RS）（RT）。同理可证（RS）（RT）R(ST)。故R(ST)=（RS）（RT）。(2)R(ST)，则由合成关系的定义知yB，使得R且ST。从而R且S且T，即RS且RT。故（RS）（RT）。从而R(ST)(RS）（RT）。14、设〈A,≤〉为偏序集，BA，若B有最大(小)元、上(下)确界，则它们是惟一的。证明：设a,b都是B的最大元，则由最大元的定义ab，ba。是A上的偏序关系，a=b。即B如果有最大元则它是惟一的。15、设A={1,2,3},写出下列图示关系的关系矩阵，并讨论它们的性质：11168 232323解：（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诱导的划分。解：68 R诱导的划分为{{1,5},{2,4},{3,6}}。18、A上的偏序关系的Hasse图如下。（1）下列哪些关系式成立：ab,ba,ce,ef,df,cf；（2）分别求出下列集合关于的极大（小）元、最大（小）元、上（下）界及上（下）确界（若存在的话）：(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、求下列置换的运算：68 解：（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。试问是循环群吗？解：是循环群。因为是无限阶的循环群，则它只有两个生成元。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也是的生成元。23、设是群，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的元素的个数一定是奇数。68 证明：设是偶数阶群，则由于群的元素中阶为1的只有一个单位元，阶大于2的元素是偶数个，剩下的元素中都是阶为2的元素。故偶数阶群中阶为2的元素一定是奇数个。25、证明：有限群中阶大于2的元素的个数一定是偶数。证明：设是有限群，则aG，有|a|=|a-1|。且当a阶大于2时，a-1。故阶数大于2的元素成对出现，从而其个数必为偶数。26、试求中每个元素的阶。解：0是中关于+6的单位元。则|0|=1；|1|=|5|=6，|2|=|4|=3，|3|=2。27、设是群，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。试证：为群。证明：（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关于运算*的逆元。综上所述，为群。68 29、设为半群，aS。令Sa={ai|iI+}。试证是的子半群。证明：b，cSa，则存在k,lI+，使得b=ak,c=al。从而b·c=ak·al=ak+l。因为k+lI+，所以b·cSa，即Sa关于运算·封闭。故是的子半群。30、单位元有惟一逆元。证明：设是一个群，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、证明在元素不少于两个的群中不存在零元。证明：（用反证法证明）设在素不少于两个的群中存在零元。对aG,由零元的定义有a*=。是群，关于*消去律成立。a=e。即G中只有一个元素，这与|G|2矛盾。故在元素不少于两个的群中不存在零元。33、证明在一个群中单位元是惟一的。证明：设e1,e2都是群〈G,*〉的单位元。则e1=e1*e2=e2。所以单位元是惟一的。34、设a是一个群〈G，*〉的生成元，则a-1也是它的生成元。68 证明：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除单位元以外无其它等幂元。证明：设e是该群的单位元。若a是的等幂元，即a*a=a。因为a*e=a，所以a*a=a*e。由于运算*满足消去律，所以a=e。即G除单位元以外无其它等幂元。37、设是一个群，则对于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、设半群中消去律成立，则是可交换半群当且仅当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))。由于·68 满足消去律，所以(b·a)·b=a·(b·b)，即(b·a)·b=(a·b)·b。从而a·b=b·a。故·满足交换律。39、设群除单位元外每个元素的阶均为2，则是交换群。证明：对任一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、设是群，作f:GG,aa-1。证明：f是G的自同构G是交换群。证明：68 设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|＝2|H|，则一定是群的正规子群。证明：由已知可知，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的子群。68 再证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是平凡群，则结论显然成立。否则设的阶为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是p阶循环群，p是素数。对G中任一非单位元a。设a的阶为k,则k1。68 由拉格朗日定理，k是p的正整因子。因为p是素数，故k=p。即a的阶就是p，即群G的阶。故a是G的生成元。48、若是可交换独异点，T为S中所有等幂元的集合，则是的子独异点。证明：ee=e，eT，即T是S的非空子集。a,bT,是可交换独异点,(ab)(ab)=((ab)a)b=(a(ba))b=（a(ab)）b=((aa)b)b=(aa)(bb)=ab,即abT。故是的子独异点。49、设是群，且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|＝n，则a∈G，|a|n。证明：aG，由封闭性及|G|=n可知a,a2,…,an,an+1中必有相同的元素，不妨设为ak=am,k到的群同态，G和G2的单位元分别为e1和e2，则（1）h(e1)=e2；（2）aG1，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)。由定理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是单一同态，所以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的阶。68 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中的元素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、在一个群中，若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是奇数阶交换群的单位元，则G的所有元素之积为e。证明：设G=<{e,a,a,…,a},*>，n为正整数。68 因为G的阶数为奇数2n+1，所以由拉格朗日定理知G中不存在2阶元素，即除了单位元e以外，G的所有元素的阶都大于2。故对G中的任一非单位元a，它的逆元a不是它本身，且G中不同的元素有不同的逆元。由此可见，G中的2n个非单位元构成互为逆元的n对元素。因为G是交换群，故G的所有元素之积可变成单位元和n对互为逆元的元素之积的积，从而结果为e。60、设S=QQ，Q为有理数集合，*为S上的二元运算：对任意(a,b)，(c,d)S,有(a,b)*(c,d)=(ac,ad+b),求出S关于二元运算*的单位元，以及当a0时，(a,b)关于*的逆元。解：设S关于*的单位元为(a,b)。根据*和单位元的定义，对(x,y)S,有(a,b)*(x,y)=(ax,ay+b)=(x,y),(x,y)*(a,b)=(ax,xb+y)=(x,y)。即ax=x,ay+b=y,xb+y=y对x,yQ都成立。解得a=1,b=0。所以S关于*的单位元为(1,0)。当a0时，设(a,b)关于*的逆元为(c,d)。根据逆元的定义，有(a,b)*(c,d)=(ac,ad+b)=(1,0)(c,d)*(a,b)=(ac,cb+d)=(1,0)即ac=1,ad+b=0,cb+d=0。解得c=,d=-。所以(a,b)关于*的逆元为(,-)。61、设是一个群，H、K是其子群。定义G上的关系R：对任意a,b∈G，aRbó存在h∈H,k∈K,使得b=h*a*k，则R是G上的等价关系。证明：a∈G，因为H、K是G的子群，所以e∈H且e∈K。令h=k=e,则a=e*a*a=h*e*k,从而aRa。即R是自反的。a,b∈G，若aRb，则存在h∈H，k∈K,使得b=h*a*k。因为H、K是G的子群，所以h-1∈H且k-1∈K。故a=h-1*a*k-1,从而bRa。即R是对称的。a,b,c∈G，若aRb,bRc,则存在h,g∈H，k,l∈K,68 使得b=h*a*k，c=g*b*l。所以c=g*b*l=g*(h*a*k)*l=(g*h)*a*(k*l)。因为H、K是G的子群，所以g*h∈H且k*l∈K。从而aRc。即R是传递的。综上所述，R是G上的等价关系。62、设H是G的子群，则下列条件等价：（1）H是G的不变子群；（2）a∈G，aHa-1H；（3）a∈G，a-1HaH；（4）a∈G，h∈G，aha-1H。证明：(1)(2)a∈G，则对h∈H,令h1=aha-1，因为ahaH且Ha=aH，所以h2∈H，使得ah=h2a。故h1=（h2a）a-1=h2H。故aHa-1H。(2)(3)a∈G，对h∈H,令h1=a-1ha，则（h1）-1=ah-1a-1。因为h-1∈H，所以（h1）-1=ah-1a-1∈aHa-1。由（2）可知（h1）-1∈H,从而h1H。故a-1HaH。(3)(4)类似于（2）(3)的证明。(4)(1)a∈G，对b∈aH，则h∈H，使得b=ah。故b=(ah)(a-1a)=(aha-1)a。由于aha-1∈H，所以b∈Ha。即aHHa。反之对b∈Ha，则h∈H，使得b=ha。故b=(aa-1)(ha)=a(a-1ha)=a(a-1h(a-1)-1)。由于a-1h(a-1)-1∈H，所以b∈aH。即HaaH。即Ha=aH。从而H是G的不变子群。63、在半群中，若对a,bG，方程a*x=b和y*a=b都有惟一解，则是一个群。证明：任意取定aG，记方程a*x=a的惟一解为eR。即a*eR=a。下证eR为关于运算*的右单位元。对bG，记方程y*a=b的惟一解为y。68 是半群，运算*满足结合律。b*eR=(y*a)*eR=y*(a*eR)=y*a=b。类似地，记方程y*a=a的唯一解为eL。即eL*a=a。下证eL为关于运算*的左单位元。对bG，记方程a*x=b的惟一解为x。是半群，运算*满足结合律。eL*b=eL*(a*x)=(eL*a)*x=a*x=b。从而在半群中,关于运算*存在单位元，记为e。现证G中每个元素关于运算*存在逆元。对bG，记c为方程b*x=e的惟一解。下证c为b关于运算的逆元。记d=c*b。则b*d=(b*c)*b=e*b=b。b*e=b,且方程b*x=b有惟一解，d=e。b*c=c*b=e。从而c为b关于运算的逆元。综上所述，是一个群。64、设是群，H和K都是G的子群，令HK={h*s|s∈K，h∈H},KH={s*h|s∈K,h∈H},，是G的子群的充分必要条件是HK=KH。证明：HK是G的子群。cHK，则c-1HK，故存在aH,bK,使得c-1=a·b。因为c=（a·b）-1=b-1·a-1。因为H和K都是G的子群，所以a-1H,b-1K，即cKH。从而HKKH。cKH，则存在aH,bK,使得c=b·a。因为c=（a-1·b-1）-1。因为H和K都是G的子群，所以a-1H,b-1K，即a-1·b-1HK。因为HK是G的子群，所以c=（a-1·b-1）-1HK。从而KHHK。故HK=KH。HK=KH。对c，dHK，有a1,a2H,b1,b2K,使得c=a1·b1,d=a2·b2。则c·d=(a1·b1)·(a2·b2)=((a1·b1)·a2)·b2=(a1·(b1·a2))·b2。因为b1·a2KH=KH，所以存在a3H,b3K,使得b1·a2=a3·b3。从而c·d=(a1·（b1·a2）·b2=(a1·（a3·b3）)·b2=(a1·a3)·(b3·b2)。因为H和K都是G的子群，故a1·a3H,b3·b2K。从而c·dHK。又c-1=(a1·b1)-1=b-11·a-11。因为H和K都是G的子群，故a-11H,b-1168 K。从而c-1KH。因为HK=KH，所以c-1HK。综上所述，HK是G的子群。65、设H和K都是G的不变子群。证明：HK也是G的不变子群。证明：先证HK是G的子群。对aHK，有hH，kK，使得a=h·k。因为a=h·k=(h·k·h-1)·h，且K是G的不变子群，所以h·k·h-1K。故aKH。从而HKKH。同理可证，KHHK。故HK=KH。从而HK是G的子群。下证HK是G的不变子群。对aG，bHK，有hH，kK，使得b=h·k。故a·b·a-1=a·(h·k)·a-1=(a·h·a-1)·(a·k·a-1)。因为H和K都是G的不变子群，所以a·h·a-1H且a·k·a-1K。从而a·b·a-1HK。故HK是G的不变子群。66、设为群，a,b,cG。若a*b=c*b*a,a*c=c*a,b*c=c*b，且a,b的阶分别为m,n，则c的阶整除m与n的最大公因子(m,n)。证明：设c的阶为k。在a*b=c*b*a两边同时右乘b，再由a*b=c*b*a得a*b=(c*b*a)*b=(c*b)*(a*b)*b=(c*b)*(c*b*a)*b=(c*b)*a*b=(c*b)*(a*b)*b=(c*b)*(c*b*a)*b=(c*b)*a*b=…=(c*b)*a,再由b*c=c*b及b的阶为n得a=a*b=(c*b)*a=(c*b)*a=c*a,所以c=e。故由元素阶的定义有k|n。由a*b=c*b*a,a*c=c*a,b*c=c*b得a*b=b*a*c，两边同时左乘a，再由a*b=b*a*c得a*b=a*(b*a*c)=a*(a*b)*(a*c)=a*(b*a*c)*(a*c)=a*b*(a*c)=a*(a*b)*(a*c)=a*(b*a*c)*(a*c)=a*b*(a*c)=…=b*(a*c),68 再由a*c=c*a及a的阶为m得b=a*b=b*(a*c)=b*a*c=b*c,所以c=e。故由元素阶的定义有k|m。由此可见，k是m和n的公因子，从而能整除m和n的最大公因子(m,n)。（格与布尔代数）67、当n分别是24，36，110时，是布尔代数吗？若是，则求出其原子集。解：因为|S24|=8，|S36|=9，|S110|=8，故不是布尔代数。在中12没有补元，故它也不是布尔代数。是布尔代数，其原子集为{2,5,11}。68、设L是有界格，且|L|>1。证明：01。证明：用反证法证明。设0=1。则任取aL，则由于L是有界格，故a1且0a。即0a1。因为0=1且是L上的偏序关系，所以a=0。这与已知|L|>1矛盾。69、设(L,≤)是格，若a,b,cL，a≤b≤c，则ab=b⊙c,(a⊙b)(b⊙c)=(ab)⊙(ac)证明：因为abc，所以ab=a，ab=b=b，且b=bc，以c=bc。从而ab=bc。(ab)(bc)=a(bc)=a(ab)=(aa)b=ab=b，(ab)(ac)=(bc)(ac)=b(c(ac))=bc=b。70、在布尔代数中，证明恒等式a(b)=ab证明：a(b)=(a)(ab)=1(ab)=ab71、设是格，a1,a2,…,anL。试证：a1a2…an=a1a2…an当且仅当a1=a2=…=an。68 证明：显然是成立的。对任一k=1,2,..,n，a1a2…anak，aka1a2…an。因为a1a2…an=a1a2…an，且是L上的偏序关系，故ak=a1a2…an。从而a1=a2=…=an。72、在布尔代数中，证明恒等式(ac)(b)(bc)=(ac)(b)证明：((ac)(b))(bc)=((ac)(bc))((b)(bc))=(abc)(bc)=(a)bc=1bc=bc,故bc(ac)(b)，从而(ac)(b)(bc)=(ac)(b)。73、在布尔代数中，证明恒等式(ab)(c)(c)=(ab)c证明：(ab)(c)(c)=(ab)(()c)=(ab)(c)=(ab)c。74、设是格，a,b,c,dL。试证：若ab且cd，则acbd证明：因为ab，cd，所以a=ab,c=cd。从而(ac)(bd)=((ac)b)d=(b(ac))d=((ba)c)d=a(cd)=ac，所以acbd。75、当n分别是10,45时，画出的哈斯图。解：104515952531168 76、在布尔代数中，证明恒等式(a)(b)(c)=(b)(c)(a)证明：(a)(b)(c)=(abc)(ab)(a)(ac)(bc)(c)()(b)=(abc)()，(b)(c)(a)=()(a)(c)(ca)(b)(ba)(bc)(bca)=(abc)()，故(a)(b)(c)=(b)(c)(a)。77、设是格，a,bL，且a≤b，记I[a,b]={xL|a≤x≤b}则是的子格。证明：x,yI[a,b],a≤x≤b且a≤y≤b。由定理6.1.1有a≤xy≤b且a≤xy≤b。从而xyI[a,b]且xyI[a,b]。故I[a,b]关于和是封闭的，从而是的子格。78、设A＝{a,b,c}，求的子格（P(A)表示A的幂集）。解：P(A)={,{a},{b},{c},{a,b},{a,c},{b,c},A}。在P(A)的所有非空子集中，只要它关于和是封闭的，则它就是的子格。显然和<{},>是的子格。<{,{a}},>、<{,{b}},>、<{,{c}},>、<{,{a,b}},>、<{,{a,c}},>、<{,{b,c}},>、<{,A},>、<{,{c},{a,c},{b,c},A}，>等都是的子格。79、证明：在同构意义下，4阶格只有2个。证明：若≤68 是L上的全序关系，则它一定是良序关系(因为任一有限的全序集一定是良序集)。若设L={a,b,c,d}，则L的四个元素满足：a≤b≤c≤d。若≤不是L上的全序关系，则L中一定存在两个元素（不妨设为b,c），b≤c和c≤b都不成立。因此bc和bc既不可能相等，也不可能是b和c。不妨记a=bc,d=bc。故的四个元素a,b,c,d满足a≤a,b≤b,c≤c,d≤d,a≤b,a≤c,a≤d,b≤d,c≤d。ddcbcbaa80、设是有界格，是A上的全序关系。若|A|＞2，则aA-{0,1}，a无补元。证明：用反证法证明。若aA-{0,1}，a有补元a"。即aa"=1，aa"=0。因为是A上的全序关系，所以aa"或a"a。若aa"，则a=aa"=0。若a"a，则a=aa"=1。无论如何，这与a矛盾。81、格是模格a,b,cL，有a(b(ac))=(ab)(ac)证明：a,b,cL，记d=ac。所以ad,从而a(b(ac))=a(bd)=(ab)d=(ab)(ac)。a,b,cL，若ac，则c=ac。所以(ab)c=(ab)（ac）=a(b(ac))=a(bc)。82、设是分配格，a,b,cL。若(ab)＝(ac)且(ab)＝(ac)，则b＝c。68 证明：由吸收律、分配律和交换律有b=b(ab)＝b(ac)=（ba）（bc）=(ac)(bc)=c(ab)=c(ac)＝c。83、证明：在有补分配格中，每个元素的补元一定惟一。证明：设是一个有补分配格。aL,设b和c都是a的补元，即ab=1,ac=1,ab=0,ac=0。由吸收律、分配律和交换律有b=b0＝b(ac)=(ba)(bc)=1(bc)=bc,c=c0=c(ab)＝(ca)(cb)=1(cb)=cb。故b=c。从而每个元素的补元是惟一的。84、设是格，则L是分配格当且仅当a,b,cL，有(ab)ca(bc)证明：设L是分配格。对a,b,cL，有(ab)c=(ac)(bc)因为aca，故(ac)(bc)a(bc)。从而(ab)ca(bc)对a,b,cL，因为aca,acc,aab,bcc,bcb,bab,所以acab，acc，bcc,bcab，从而(ac)(bc)(ab)c。又由已知有(ab)c=((ba)c)c(b(ac))c=((ac)b)c(ac)(bc)。故(ab)c=((ac)b)c(ac)(bc)。从而L是分配格。85、设是一布尔代数，则是一个交换群，其中＋定义为68 a+b=(a⊙b′)(a′⊙b)。证明：a,bS，＜S,,⊙,′,0,1>是一布尔代数，a+b=(a⊙b′)(a′⊙b)=(b⊙a′)(b′⊙a)=b+a。运算+满足交换律。a,b,cS，(a+b)+c=((a⊙b′)(a′⊙b))+c=(((a⊙b′)(a′⊙b))⊙c′)(((a⊙b′)(a′⊙b))′⊙c)=(a⊙b′⊙c′)(a′⊙b⊙c′)((a′b)⊙(ab′)⊙c)=(a⊙b′⊙c′)(a′⊙b⊙c′)(((a′⊙b′)(b⊙a)))⊙c)=(a⊙b′⊙c′)(a′⊙b⊙c′)(a′⊙b′⊙c)(a⊙b⊙c)a+(b+c)=(c+b)+a=(c⊙b′⊙a′)(c′⊙b⊙a′)(c′⊙b′⊙a)(c⊙b⊙a)=(a⊙b′⊙c′)(a′⊙b⊙c′)(a′⊙b′⊙c)(a⊙b⊙c)=(a+b)+c运算+满足结合律。aS，＜S,,⊙,′,0,1>是一布尔代数，a+0=(a⊙0′)(a′⊙0)=(a⊙1)0=a。0关于运算+的单位元。aS，＜S,,⊙,′,0,1>是一布尔代数，a+a=(a⊙a′)(a′⊙a)=00=0。a是a关于运算+的逆元。综上所述，是一个交换群。86、设是一布尔代数，则R={|ab=b}是S上的偏序关系。证明：aS，满足等幂律，aa=a，故aRa。即R是自反的。a,bS，若aRb且bRa,满足交换律，b=ab=ba=a。即R是反对称的。a,b,cS，若aRb且bRc,满足结合律，c=cb=c（ba）68 =(cb)a=ca,故aRc。即R是反对称的。综上所述，R={|ab=b}是S上的偏序关系。87、设是一布尔代数，则关系={|a⊙b=a}是S上的偏序关系。　证明：aS，因为⊙满足等幂律，所以a⊙a=a，故aa。即是自反的。a,bS，若ab且ba,因为⊙满足交换律，所以a=a⊙b=b⊙a=b。即是反对称的。a,b,cS，若ab且bc,因为⊙满足结合律，因为a=a⊙b=a⊙(b⊙c)=(a⊙b)⊙c=a⊙c,故ac。即是反对称的。综上所述，={|a⊙b=a}是S上的偏序关系。（图论部分）88、证明在有n个结点的树中，其结点度数之和是2n-2。证明：设T=是任一棵树，则|V|=n，且|E|=n-1。由欧拉握手定理，树中所有结点的度数之和等于2|E|.从而结点度数之和是2n-2。88、任一图中度数为奇数的结点是偶数个。证明：设G=〈V,E〉是任一图。设|V|=n。由欧拉握手定理可得deg(v)=2|E|可得，图中所有结点度数之和是偶数。显然所有偶数度结点的度数之和仍为偶数，从而所有奇数度结点的度数之和也是偶数。因此，图中度数为奇数的结点一定为偶数个。89、连通无向图G的任何边一定是G的某棵生成树的弦。这个断言对吗？若是对的请证明之，否则请举例说明。证明：不对。68 反例如下：若G本身是一棵树时，则G的每一条边都不可能是G的任一棵生成树（实际上只有惟一一棵）的弦。90、设T=是一棵树，若|V|>1，则T中至少存在两片树叶。证明：（用反证法证明）设|V|=n。因为T=〈V,E〉是一棵树，所以|E|=n-1。由欧拉握手定理可得deg(v)=2|E|=2n-2。假设T中最多只有1片树叶，则deg(v)2(n-1)+1>2n-2。得出矛盾。91、画一个使它分别满足：(1)有欧拉回路和哈密尔顿回路；(2)有欧拉回路，但无条哈密尔顿回路；(3)无欧拉回路，但有哈密尔顿回路；(4)既无欧拉回路，又无哈密尔顿回路。解92、设无向图G=，|E|=12。已知有6个3度顶点，其他顶点的度数均小于3。问G中至少有多少个顶点？解：设G中度数小于3的顶点有k个，由欧拉握手定理68 24=知，度数小于3的顶点度数之和为6。故当其余的顶点度数都为2时，G的顶点最少。即G中至少有9个顶点。93、设图G=，|V|=n，|E|=m。k度顶点有nk个，且每个顶点或是k度顶点或是k+1度顶点。证明：nk=(k+1)-2m。证明：由已知可知，G中k+1度顶点为n-nk个。再由欧拉握手定理可知2m==knk+(k+1)(n-nk)=(k+1)n+-nk故nk=(k+1)-2m。94、设G=是一个连通且|V|=|E|+1的图，则G中有一个度为1的结点。证明：(用反证法证明）设|V|=n，则|E|=n-1。由欧拉握手定理可得deg(v)=2|E|=2n-2。因为G连通，所以vV，deg(v)1。假设G中没有1片树叶，则deg(v)2n>2n-2。得出矛盾。95、若n阶连通图中恰有n-1条边，则图中至少有一个结点度数为1。证明：（用反证法证明）设G=有n-1条边且|V|=n。由欧拉握手定理可得deg(v)=2|E|=2n-2。因为G是连通图，所以G中任一结点的度数都大于等于1。假设G中不存在度数为1的结点，则G中任一结点的度数都大于等于2.故deg(v)2(n-1)+1>2n-2,得出矛盾。68 96、若G有n个结点，m条边，f个面，且每个面至少由k(k3)条边围成，则mk(ｎ－2)／(ｋ－2)。证明：设连通简单无向平面图G=〈V,E,F〉，则|V|=n,|E|=m,|F|=p。由已知对任一fF,deg(f)k。由公式deg(f)=2|E|可得，2|E|k|F|。再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+|E|2。即k(n-2)(k-2)m。所以mk(ｎ－2)／(ｋ－2)。97、设G=是连通的简单平面图，|V|=n3，面数为k,则k2n-4。证明：记|E|=m。因为G=是连通的简单平面图，故每个面的度数都不小于3。从而由公式deg(f)=2|E|可得3k2m再由欧拉公式|V|-|E|+|F|=2有m=n+k-2及kn+k-2故k2n-4。98、证明对于连通无向简单平面图，当边数e＜30时，必存在度数≤4的顶点。证明：若结点个数小于等于3时，结论显然成立。当结点多于3个时，用反证法证明。记|V|=n,|E|=m,|F|=k。假设图中所有结点的度数都大于等于5。由欧拉握手定理得deg(v)=2|E|得5n2m。68 又因为G=〈V,E,F〉是一个连通简单无向平面图，所以对每个面f,deg(f)3。由公式deg(f)=2|E|可得，2m3k。再由欧拉公式|V|-|E|+|F|=2可得2m-m+m=m从而30m,这与已知矛盾。99、在一个连通简单无向平面图G=〈V，E，F〉中若|V|3，则|E|3|V|－6。证明：|V|3，且G=〈V，E，F〉是一个连通简单无向平面图，d(f)3，fF。由公式deg(f)=2|E|可得，2|E|3|F|。再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+|E|2。|E|3|V|－6。100、给定连通简单平面图G=，且|V|=6,|E|=12,则对于任意fF,d(f)=3。证明：因为|V|=63，且G=〈V,E,F〉是一个连通简单无向平面图，所以对任一fF，deg(f)3。由欧拉公式|V|-|E|+|F|=2可得|F|=8。再由公式deg(f)=2|E|，deg(f)=24。因为对任一fF，deg(f)3，故要使上述等式成立，对任一fF，deg(f)=3。101、设G=是n个顶点的无向图(n>2)，若对任意u,vV，有d(u)+d(v)n，则G是连通图。证明：用反证法证明。68 若G不连通，则它可分成两个独立的子图G和G，其中|V(G)|+|V(G)|-2=n，且G中的任一个顶点至多只和G中的顶点邻接，而G中的任一顶点至多只和G中的顶点邻接。任取uV(G),vV(G),则d(u)|V(G)|-1,d(v)|V(G)|-1。故d(u)+d(v)(|V(G)|-1)+(|V(G)|-1)|V(G)|+|V(G)|-2=n-2，（1）求G的邻接矩阵；（2）G中v1到v4的长度为4的通路有多少条？（3）G中经过v1的长度为3的回路有多少条？（4）G中长度不超过4的通路有多少条？其中有多少条通路？解：（1）A=，A2=A3=，A4=（2）G中v1到v4的长度为4的通路有4条；（3）G中经过v1的长度为3的回路有3条；（4）G中长度不超过4的通路有72条，其中有19条回路。v1v4v2v3题104图105、求下列无向图中每个顶点的度数；求下列有向图中每个顶点的出度、入度和度。解：ade68 cbf在这个无向图中d(a)=3,d(b)=6,d(c)=4,d(d)=3,d(e)=0,d(f)=0。cba在这个有向图中d(a)=3,d(b)=4,d(c)=3,d(a)=2,d(a)=1,d(b)=2,d(b)=2,d(c)=1,d(a)=2。adecbf题106图106、求下列无向图的子图、生成子图、由边集诱导的子图和由顶点集诱导的子图。解：cb它的一个子图daecbf68 它的一个生成子图dacb由边集{(a,b),(a,c),(a,d),(b,d)}诱导出的子图dabf由顶点集{a,b,d,f}诱导出的子图107、求下列赋权图顶点间的距离。dae43571cb14f解：d(a,b)=3,d(a,c)=3,d(a,d)=,d(a,e)=8,d(a,f)=16,d(b,c)=1,d(b,d)=,d(b,e)=6,d(b,f)=13,d(c,d)=,d(c,e)=5,d(c,f)=12,d(d,e)=,d(d,f)=,d(e,f)=7,108、求下列赋权图中v1到其他顶点的距离。68 v210v43v1226434v6v32v5解：Sl(v2)l(v3)l(v4)l(v5)l(v6)tl(t){v1}34v23{v1,v2}413v34{v1,v2,v3}76v56{v1,v2,v3,v5}710v47{v1,v2,v3,v5,v4}9v69{v1,v2,v3,v5,v4,v6}故v1到v2,v3,v4,v5,v6的距离分别是3，4，7，6，9。109、求下图的可达矩阵。daebc解：该图的邻接矩阵为A=68 则A2==A3=A4=故图的可达矩阵为P=110、求下列图的生成树。解：下面是它的两棵生成树：68 111、在一个有n个顶点的G=中，u,vV。若存在一条从u到v的一条通路，则必有一条从u到v的长度不超过n-1的通路。证明：设v0e1v1e2…elvl是从u=v0到v=vl的长为l的通路。若ln-1，则结论显然成立。否则因为l+1>n，故v0，v1，…，vl中必有一个顶点是重复出现的。不妨设vi=vj(0i是强连通图。任取u,vV，则u和v相互可达，即从u到v有路径P，从v到u有路径P。故从P和P首尾相接可得到一条经过u和v的回路C。若C经过G中所有顶点至少一次，则C就是满足结论要求的回路。否则若C没有经过顶点w，则类似地我们可得到一条经过u和w的回路C。从C和C我们可得到一条经过更多顶点的回路C（先从u经过P到v,再从v经过C回到v,再从v经过P回到u）。对C重复上述过程，直到得到一条经过所有顶点的回路为止。若G中存在一条经过G中所有顶点至少一次的回路，则G中任意两个顶点是相互可达的，从而G是强连通的。115、一个有向图是单向连通图ó它有一条经过所有结点的路。证明：设G=是单向连通图。任取u,vV，则u可达v或v可达u。不妨设u可达v，即从u到v有路径P。若P经过G中所有顶点至少一次，则P就是满足结论要求的路径。否则若P没有经过顶点w，则如果v经过路径T可达w,连接P和T我们可得一条经过P经过的所有顶点及w的更长的路径P；否则若w经过路径S可达u，连接S和P我们也可得一条经过w及P经过的所有顶点的更长的路径P；再否则我们一定可以找到P经过的两个相邻顶点t和s，t到s有边，t经过路径T可达w，w经过路径T可达s（否则就与u可达w，w可达v矛盾），我们构造这样一条路径P：从u出发经过P到达t,t经过路径T到达w，再从w出发经过路径T到达s，然后从s出发经过P到达v。这是一条经过w及P所经过的所有顶点的更长的路径。68 PPuvuvTSwwPutsvTTw对P重复上述过程，直到得到一条经过所有顶点的路径为止。若G中存在一条经过G中所有顶点至少一次的路径，则G中任意两个顶点中至少有一个可达另一个，从而G是单向连通的。68'