离散数学王素霞习题答案

基础习题1(1)是，简单命题(2)是，简单命题(3)是，复合命题(4)不是(5)不是(6)是，复合命题(7)是，简单命题(8)不是(9)不是(10)是，简单命题(11)是，复合命题(12)是，复合命题(13)是，复合命题(14)不是(15)是，简单命题2(1)p，其中p:古埃及是世界四大文明古国之一。真值为1。(2)p，其中p:是无理数。真值为1。(3)p∨q，其中p:2是素数，q:5是素数。真值为1。(6)p∧q，其中p:2是正数，q:-3是正(7)p，其中p:王健与魏钢是朋友。真值依实际情况而定，非0即1。(10)p，其中p:圆的周长等于直径乘以。真值为1。(11)q→p，其中p:5是奇数，q:7是2的倍数。真值为1。(12)q↔p，其中p:4是奇数，q:(13)p，其中p:2050年10月1日是晴天。真值依10月1日的实际天气情况而定，非0即1。(15))p，其中p:外星人是存在的。真值非0即1，3(1)p∧q，其中p:苹果树是落叶乔木，q:(2)p∧q，其中p:8是2的倍数，q:8(3)p∧¬q，其中p:0是最小的自然数，q:0(4)p∧q，其中p:3是偶数，q:3是素(5)p，其中p:豆沙包是由面粉和红小豆做成的。真值为1。4(1)p∨q，其中p:2是偶数，q:4是偶数。真值为1。(2)p∨q，其中p:5是奇数，q:2是奇数。真值为1。(3)¬p∨¬q，其中p:2是素数，q:6是(4)(p∧¬q)V(¬p∧q)，其中p:小丽能买一个盲盒，q:小丽能买一个拼图。依据实际情况，真值、(5)p∨q，其中p:王冬的生日是9月12日，q:王冬的生日是9月13日。依据实际情况，真值、。5设p:，q:地球是静止的(1)p→q，真值为1；(2)p→¬q，真值为1；(3)¬q→p，真值为0；(4)¬q6p↔q，其中p:今天是星期六，q:p↔q，其中p:实函数在点可导，q:实函数在点连续。真值为0。p↔q，其中p:4是偶数，q:三角形有四个内p↔q，其中p:，q:。真值为1。7设：2是正整数；：中国有四大发明；：太阳从东方落下。求下列命题的真值。(1)0(2)0(3)0(4)18(1)矛盾式：（等值演算法）(2)重言式：（等值演算法）(3)非重言式的可满足式：（真值表法）000111001111010111011111100001101010110100111111(4)重言式：（等值演算法）(5)非重言式的可满足式：（真值表法）001100010100101010110100(6)非重言式的可满足式：（主范式法）非重言式的可满足式：（等值演算法）9(1)×(2)√(3)√(4)×(5)×(6)×(7)√10(1)(2)(3)(4)11（1）主合取范式：；主析取范式：；成假赋值10；成真赋值00、01、11。（2）主析取范式：；主合取范式：；成真赋值000、001、010、100、110；成假赋值011、101、111。（3）0001000111010100111110001101001101011111主析取范式：；主合取范式：；成真赋值001、011、100、111；成假赋值000、010、101、110。（4）主合取范式：；主析取范式：；成真赋值000、001、010、011、100、101、110、111；无成假赋值。12（1）主析取范式：；主合取范式：；（2）主合取范式：；主析取范式：。13设p:今年是2024年，q:明年是2025年，r:明年是2026（1）推理正确，p→r，p⇒r（假言推理规则）。（2）推理的形式结构为(p→q)⋀q→00101011101000111111(3)推理正确，p→r，¬r(4)推理的形式结构为(p→q)⋀¬0011111011011010010001100100(5)推理的形式结构为(p→(q(6)推理正确，推理的形式结构为前提，结论证明①前提引入规则②①置换规则③②化简规则④前提引入规则⑤③④拒取式规则14(1)前提：，，，结论：证明：①前提引入规则②前提引入规则③①②拒取式规则④前提引入规则⑤③④析取三段论规则⑥前提引入规则⑦⑤⑥假言推理规则⑧①⑥合取引入规则前提：，结论：证明：①附加前提引入规则②前提引入规则③前提引入规则④②③假言推理规则⑤①④假言推理规则⑥⑤化简规则由附加前提证明法证得推理是正确的。前提：，，结论：证明：①前提引入规则②前提引入规则③①②析取三段论规则④否定结论引入规则⑤③④拒取式规则⑥④⑤合取引入规则⑦⑥置换规则⑧前提引入规则⑨⑦⑧假言推理规则⑩⑨置换规则⑪⑩化简规则⑫①⑪合取引入规则⑫得到了矛盾式，由归谬法证得推理是正确的。前提：，，结论：证明：①前提引入规则②前提引入规则③①②假言推理规则④前提引入规则⑤③④假言推理规则⑥⑤附加规则15设p:今天我有空，q:我去博物馆玩，r:我去奥体公园玩，s:前提：p→(q∨r)，s→¬q结论：r证明：①p前提引入规则②p→(q∨r)③q∨r④s前提引入规则⑤s→¬q⑥¬q④⑤⑦r③⑥析取三段论规则提升习题1设p1：陈思为大队长，q1：陈思为宣传委员，r1：陈思为组织委员，p2：孙瑶为大队长，q2：孙瑶为宣传委员，1⟺(p11⟺(1⟺(①∧②得1⟺¬p1③∧④得1⟺¬最终得出：孙瑶为宣传委员，王博为大队长，陈思为组织委员。2（1）主析取范式：，主合取范式：1。（2）主析取范式：0，主合取范式：。3设p:老大在撒谎，q:老二在撒谎，r:老三在撒谎。本题即为求00000000010110010110001110101001000101111111001101110000所以得到老大、老三在撒谎，老二没有撒谎。4设p:她学习态度认真，q:她能学好，r:她学习方法对，s:前提：p→q，r→s，¬结论：¬证明：①p→q前提引入规则②¬q→¬p③r→s前提引入规则④¬s→¬r⑤¬q∨¬⑥¬p∨¬r

基础习题1在谓词逻辑中符号化下述命题：（1），其中是淮南人，爱喝牛肉汤。（2），其中是人，会犯错。（3），其中是人，聪明。（4），其中是有勇气的人，怕困难。（5），其中是火车，是汽车，比快。2（1）假（2）真（3）假（4）真。3指出下列公式的辖域和变元的约束情况：（1）的辖域：，的辖域：，都是约束变元。（2）的辖域，的辖域，的辖域：,中的是约束变元，是自由变元，中的是约束变元，是自由变元45（1）若为真，则，为真且为真，因此为真，从而为真；（2）若为假，则，为假或为假，若为假，则为假。若，为假，即为假，则为假。所以，对任意个体域，。6给定解释:个体域，为奇数，为偶数，为假，为真78构造下面推理证明：前提：，结论：证明：①前提引入规则②①规则③②化简规则④前提引入规则⑤④规则⑥③⑤假言推理规则⑦②化简规则⑧⑥⑦合取规则⑨⑧规则提升习题1说明当一谓词公式中出现多个量词时，量词的顺序一般不能随意改变。2证明：由于，即证，采用附加前提证明法，具体过程如下：①附加前提引入规则②①置换规则③②规则④前提引入规则⑤④规则⑥③⑤析取三段论规则⑦⑥规则3证明：。①前提引入规则②①规则③前提引入规则④③规则⑤②④假言推理规则⑥⑤规则⑦②附加规则⑧⑥⑦假言推理规则⑨②⑧合取规则⑩⑨规则4证明：①附加前提引入规则②①规则③前提引入规则④③规则⑤②④假言推理规则⑥⑤规则5设是哺乳动物，是脊椎动物，是胎生动物。前提：，结论：证明：①前提引入规则②①置换规则③②规则④③化简规则⑤前提引入规则⑥⑤规则⑦④⑥假言推理规则⑧③化简规则⑨⑦⑧合取规则⑩⑨规则6设能表示成分数，是有理数，是无理数。前提：，结论：证明：①前提引入规则②①置换规则③②规则④前提引入规则⑤④规则⑥③⑤假言三段论规则⑦⑥规则

１（1）x/x=2k+1,k∈Z（2）x/0（3）x,y,z2（2）（3）3（1）A∪B=AA−B=A（2）A∪B=AA−B=A（3）A∪B=AA−B=A4（1）A的子集有：∅所以P（2）A=A的子集有：∅∅∅所以PA（3）A=A的子集有：∅所以P5第五大题需要修改,将下面的原题修改为：设A,B,C,D代表任意集合，试判断下列命题的真假。如果为真，给出证明；如果为假，给出反例说明。（1）A⊆B⇔P（2）A−B（3）A∩B⊕（4）A−B答案：（1）A⊆B⇔PA“⇒”任取x，x∈PA“⇐”任取x，x∈A⇒x因此A⊆B⇔P（2）为假，反例如下：A=1（3）A∩BA====A∩=A∩=A∩A∪设A=1B又因为A∪所以A∪所以A∪（4）A−B∪A−B===6设A,B,C表示1到300之间能被3、5、7整除的整数的集合A=AA∩A∪所以不能被3或5，也不能被7整除的数的个数为：300−162=138。7设只修语文的人数为S1，只修数学的人数为S2，只修英语的人数为S1=170,S所以一个有306名学生报名选修课。8设A1表示参加篮球运动的集合，A2表示参加足球运动的集合，AA（1）参加两种球类运动的学生为：A（2）因为A所以~A9设A1表示第一次测试通过的学生集合，设A（1）因为A1所以A由包含排斥原理得A所以A即有14名学生在两次考试中都得到A。（2）因为A所以AA因为A1∪所以46=2A1−6即A所以在第一次测试中通过的学生仅有20人，在第二次测试中通过的学生仅有20人，两次测试都通过的学生有6人。提升题1设全集为U，总人数U=24，E:英语，K:韩语，G:德语，F:EKE由包含排斥原理得：E∪K∪G设同时会说英语、德语、法语得人数为x=即24=13+5+10+9−2−4−4−0−0−4+0+0+x+0−0所以x=1只会说韩语得人数为y，则y=只会说德语得人数为z，则z=只会说法语得人数为u，则u=只会说英语得人数为v，则v=所以只会说英语的4人，只会说韩语的3人，只会说德语的3人，只会说法语的2人，同时会说英、德、法的1人。2由于112设集合S=x/1令S中不能被2、3、5和7中任何一个数整除的数就是不超过120的素数个数为N=上述公式中+3的理由是：2、3、5、7这四个数不属于A1∩AAAA由包含排斥原理得N=−所以不超过120的素数的个数是30个。3给定正整数n，n=p1αAi=则ϕnA由包含排斥原理得ϕ

基础习题1，在平面直角坐标系中，它表示一个以为顶点的实心方形区域。2不能，例如，，，此时，但3（1），，4（1）（2）（3）（4）。5具有自反性、对称性、反对称性、传递性；具有反自反性、反对称性；具有反自反性、反对称性、传递性；具有对称性、反对称性、传递性。6（1）（2）（3）7的关系图，的关系图，的关系图分别如下8（1）,满足自反性。,满足对称性。，满足传递性。由此，为上的等价关系。（2）9；，，。10证明：即，从而具有自反性；，则，即具有反对称性；，则，即，从而具有传递性。由此，为上的偏序关系。Hasse图如下11（1），其中，，，，，。，，（2），其中，，，，，，，，。12，由，所以，，由此，显然，从而为满射。，若，有即，所以为单射。从而，为双射。提升习题1（1）<黄山，安徽>（2）<泰山，山东>（6）<峨眉山，四川>（7）<嵩山，河南>（8）<衡山，湖南>（9）<庐山，江西>（10）<长白山，吉林>均属于2（1）自反关系（2）反自反关系（3）对称关系但不是反对称关系（4）反对称关系但不是对称关系（5）既是对称关系又是反对称关系（6）传递关系。3自反关系，反自反关系，对称关系，反对称关系分别有64，64，64，216个。4（1）都是上的自反关系,则,从而,又，所以,故是反自反关系。（2），都是上的自反关系，,,从而，故是自反关系。5（1），；，，，；；，；，，6（1），，；，，；，；（4），。

第五章习题参考答案基础习题1（a）为多重图，平行边的重数分别为2和3。（b）为多重图，平行边的重数分别为2和3。（c）为线图，也为简单图。（d）为线图，但不是简单图。2图5-30的补图分别为（b）（c）（d）3（b）为K5的子图、真子图、为由v1,v2,v3,（c）为K5的子图、真子图、为由v1,v2,v3,（d）为K5的子图、真子图、为由v1,v2,v3,4G=（V，E）=（v1,<v5（2）（3）（4）6（1）由握手定理知，该图有16个结点。设该图有a个结点，由握手定理知，2×4+2×3+2×(a-2-2)=10×2，解得a=7设该图有a个结点，由握手定理知，2×4+1×6+2×(a-2-1)=10×2，解得a=6设该图有a个结点，每个结点的度数为b，ab=24×2，解得a=2；a=3；a=4；a=6；a=8；a=12；a=24。7（1）（2）（3）（5）能构成无向图的度数序列。（2）（3）能构成无向简单图的度数序列。8由握手定理，有向图中，所有结点的入度之和等于所有结点的出度之和等于边数。图G的入度序列能成为2,2,2,2。9由握手定理，有向图中，所有结点的入度之和等于所有结点的出度之和等于边数。图G的入度序列不能成为1,1,1,1。10图5-7(a)的邻接矩阵为A5−7(a)图5-8(a)的邻接矩阵为A图5-9(a)的邻接矩阵为A11图5-7(a)的关联矩阵为M图5-8(a)的关联矩阵为M图5-9(a)的关联矩阵为M12图5-8(a)的邻接矩阵为A=0011长度为3的回路数为A3的对角线元素之和313图5-9(a)的邻接矩阵为A=01001011长度为2的回路数为A2的对角线元素之和1+3+2+2=814K4的所有非同构的子图如下，其中8-18是生成子图，3、6、7、11、12、13、14、16、17是连通图。1516提升习题1设无向图G有12条边，G中度数为3的结点有6个，其余结点的度数均小于或等于3，问G中至少有多少个结点？为什么？答：由握手定理知，G中各结点度数之和为24，6个3度结点占去18度，若其余全是3度结点，还需要2个结点，所以至少有6+2=8个结点。23阶有向完全图的所有非同构子图如下图所示，其中5-20是生成子图。

3图5-29(a)的邻接矩阵为A2−29(a)=0a13(2)=5,所以从结点v1到结点v3a33(2)=9,所以从结点v3到自身的长度为2所有长度为2的通路数为A24图5-25b的邻接矩阵为B3=所以从v1到v1是可达的，从v2到v1、v2、v3是可达的，从v3到v3是可达的，从v4到v1、v3、v4是可达的，从v1到dv2,dv1,vd5v1v2v3v4v5v123456789100(无)0(无)|v1∗6(v1)3(v1)2(v1)∞(v16(v1)3(v1)2(v1)|v4∗8(v4)5(v3)3(v1)|v3∗8(v4)125(v3)|v2∗6(v2)12(v4)6(v2)|v5∗12(v412(v4)8(v5)|v7∗11(v8)9(v511(v8)|v11(v7到的最短路径为到的最短路径为到的最短路径为到的最短路径为到的最短路径为到的最短路径为到的最短路径为到的最短路径为6v1v2v3v1234560(无)0(无)|v1∗3(v1)9(v1)3(v1)|v2∗5(v25(v2)4(v2)|v45(v2)|v3∗9(v4)|v5∗到的最短路径为到的最短路径为到的最短路径为到的最短路径为

第六章习题参考答案基础习题1n个结点的有向完全图中，哪些是欧拉图？为什么？答:n个结点的有向完全图都是欧拉图，因为有向完全图中每个结点和其他n-1个结点之间都有两个方向相反的有向边，因此每个结点的出度和入度都等于n-1。2判断图能否一笔画出，本质上是判断该图是否有欧拉通路。由定理6.1及推论6.1知（a）不能一笔画出，（b）（c）（d）能一笔画出3本题答案很多，如4在第3题图中，把无向圈换成有向圈。56在第4题图中，把无向圈换成有向圈。7将a、b、c、d、e、f、g七个人看作7个结点，如果其中两个人能够交谈，就在对应字母之间连一条线，得到下图该图为二部图，其中b,d,f为一组，g,a,c,e为一组，同一组中没有两个人能互相交谈。8（a）是偶图，V1=（b）不是偶图，因为图中存在长度为3的回路。（c）是偶图，V1=（b）不是偶图，因为图中存在长度为3的回路。9（a）有2个面，如图所示，R0的边界为初级回路abcdafaea,degR0=8。R1的边界为初级回路abcda，（b）有2个面，如图所示，R0的边界为初级回路abefgfeca，degR0=8。R1的边界为初级回路abecdca，提升习题1由于Kn的所有结点的度数均为n-1，要使n-1为偶数，n必须为奇数，故当n≥1且为奇数时，无向完全图Kn是欧拉图。要使无向完全图中仅存在欧拉通路而不存在欧拉回路就必须使图中有且仅有两个奇度数结点，其他均为偶度数结点。由于Kn的所有结点的度数均为n-1，因此其中只能有两个奇度数结点，当n=2时，K2除K2不是哈密顿图之外，Kn(n≥3)全是哈密顿图，当n为奇数时，3彼德森图每个结点的度数为3，要使其变成欧拉图，要求每个结点的度数为偶数，故至少添加5条边才能构成欧拉图。至少加两条边才能构成哈密顿图。4做无向图G=(V,E)，其中V={v1,v2,v3,v4,v5,5根据条件有，，从而根据欧拉定理有。6做无向图G=<V,E>，其中，V={a,b,c,d,e,f,g)E={(u,v)|u,v∈V且u与v会讲同一种语言}，则图G如图所示。于是，能否将这7个人排坐在圆桌周围使得每个人能与两边的人交谈，就转化成图G中是否存在哈密顿回路。通过观察发现abdfgeca是一条哈密顿回路。

第七章习题解答1分析①计算总度数.n阶无向树的边数m=n−1,由握手定理可知i=1n②构造可能的度数列.将2n−2划分成n份，第i份为对应顶点vi数d(vi),1≤d(vi③按每一个度数列画树.按不同的度数列画出的树都是不同构的，对同一个度数列可能画出多棵非同构的树.本题中：(1)n=5,m=4,度数之和为8.将8划分成3份的方案为：①1,1,1,1,4;②1,1,1,2,3;③1,1,2,2,2.每种方案都只有1棵非同构的树，共3棵非同构树，如图7-9.图7-9(2)n=7,m=6①1,1,1,1,1,1,6;②1,1,1,1,1,2,5;③1,1,1,1,1,3,4;④1,1,1,1,2,2,4;⑤1,1,1,1,2,3,3;⑥1,1,1,2,2,2,3;⑦1,1,2,2,2,2,2.在以上7种方案中，①、②、③、⑦各有1棵非同构的树分别如图7-10(a)(b)(c)(g)，④、⑤各有2棵非同构的树分别如图7-10(d)(e)，而⑥有3棵非同构的树如图7-10(f)，共有11棵7阶非同构的树。例如④有唯一的4度顶点必须与2度顶点相邻。它与一个2度顶点相邻，所得树是非同构的，再没有其他情况，因而有2棵非同构的树。图7-102分析设T有x个1度顶点(即树叶),则T的顶点数n=3+2+x=5+x,T2解得x=5.有5片树叶,所求无向树的度数序列1,1,1,1,1,2,2,3,3,3.由这个度数序列可以画多棵非同构的无向树，图7-11给出4棵这样的树。图7-113分析设3度顶点为x个，则阶数n=5+3+x=8+x，边数m=7+x.由握手定理2m=14+2x=5×1+3×2+3x=11+3x解得x=3，故n=8+3=11.4分析设T中有x个3度顶点，则T中的顶点数n=7+x,边数由握手定理得方程2m=12+2x=3x+7解得x=5,即T中有5个3度顶点.T的度数序列为1,1,1,1,1,1,1,3,3,3,3,3.由于T中只有树叶和3度顶点，因而3度顶点可依次相邻，如图7-12所示。还有一棵与它非同构白树，请读者自己画出。图7-125分析n阶无向树T有n−1条边，这是无向树T的必要条件，但不是充分条件。例如，n−1个顶点的初级回路和一个孤立点组成的n阶无向简单图有n−1条边，但它显然不是树。即不一定。6分析当∆(T)=2时，即T的度数列为1,1,2,2,⋯,2,2的情况，此时T是一条长度为n−1的路径，故T中最长路径的长度为n−1.7分析图7-1中有5个结点，因此要选取4条边。期过程如图7-13(a)-(d)所示，W(T)=22。图7-138分析图7-2中有6个结点，因此要选取5条边。其过程如图7-14(a)-(e)所示，W(T)=17。图7-149分析图7-3是5阶图，5阶非同构的无向树只有3棵，理由如下：5阶无向树中，顶点数n=5,边数m=4,各顶点度数之和为8,度数分配方案有3种，分别如下：①1.1.1,1,4;②1,1,1,2,3;③1,1,2,2,2。每种方案只有一棵非同构的树.图7-9中顶点的最大度数是3,所以不可能有度数序列为①的生成树.于是，该图最多有两棵非同构的生成树。在图7-9中是它的两个非同构的生成树，其中图7-9(b)的度数序列为③,图7-9(c)的度数序列为②.9.分析图7-4(a)(1)c、d、g、h为弦，它们对应的基本回路为Cc=cab，Cd=dabf，Cg(2)a、b、e、f为树枝，它们对应的基本割集系统为Sa=a,c,d,g,h,Sb=b,c,d,g,h,图7-4(b)(1)g、c、d、h、i为弦，它们对应的基本回路Cg=gfe,CcCh=hjaeb,Ci(2)a、b、e、f、j为树枝.它们对应的基本割集为Sa=a,d,h,i,Sb=b,c,h,i,Se10分析用Kruskal算法求解，求出的图7-5(a)的最小生成树T如图7-15(a)所示，其权W(T)=14。图7-5(b)的最小生成树如图7-15(b)所示，其权W(T)=11。图7-1511分析8421码是等长码，每个数字的代码长为4，因此在译码时把编码划分为小段，每段4位，对应一个十进制数字。例如，把0101000110000111划分成0101,0001,1000,0111，分别对应5,1,8,7，故原文是5187.(1)据上可推算出7201的编码是0111001000000001,1509的编码是0001010100001001.(2)0101000110000111的原文是5187,0011010100100100的原文是3524.12分析在C1、C2、C4中任何符号串都不是另外符号串的前缀，因而他们都是前缀码.而在C3中，1是11、101的前缀.在C5中，a是aa、ac13分析一般地，由r叉树产生r元前缀码。由图7-4(a)给出的二元前缀码为C由图7-4(b)给出的二元前缀码为C214分析然后继续往下.如11001010100、1、11和110都不是代码，1100是4的代码，译出4.继续往下，1和10都不是代码，101是3的代码，译出3.再往下，01、00分别是1、0的代码.于是，它的原文是4310.(2)6014的编码是111000011100,1725的编码是0111111001101.(3)11001010100代表的八进制数是4310,01111100100代表的八进制数是1702.15分析将所有的频率都乘100，所得结果按从小到大顺序排序：wg=5，wf=5，wc=15，w以上各数为权，用Huffman算法求一课最优二叉树，图7-16所示。图7-16对照各个权可知各字母的前缀码如下：a−10，b−01，c=111，d−110，e−001，f−0001，g于是，a、b的码长为2，c、d、e的码长为3，f、g的码长为4.W(T)=255（各分支点的权之和），W(T)是传输100个按给定频率出现的字母所用的二进制数字的个数，因而传输104个按上述频率出现的字母要用2.55×最后还应指出一点，在画最优树时，由于顶点位置的不同，可能得到不同的前缀码.事实上，交换相同码长的代码和交换频率相同的字母的代码不会改变需要的二进制数字的期望个数.从而，只要它们中有一个是最佳前缀码，其他的也都是最佳前缀码.分析(1)用中序遍历法访问该树，得到(((a∗b−c)÷(d+e∗f))∗省去一些圆括号，得到算式的表达式((a∗b−c)÷(d+e∗f))∗(2)用前序遍历法访问这棵树并删去所有的圆括号，得到算式的波兰符号法表达式+∗÷−∗abc+d∗ef(3)用后序遍历法访问这棵树并删去所有的圆括号，得到算式的逆波兰符号法表达式ab∗c−def∗+÷提升习题1分析(1)用中序行遍法访问这棵树，得到(((a+(b∗c))∗d−e)÷(f+省去一些圆括号，得到算式的表达式((a+(b∗c))∗d−e)÷(f+用前序行遍法访问这棵树并删去所有的圆括号，得到算式的波兰符号法表达式+÷−∗+a∗bcde+f(3)用后序行遍法访问这棵树并删去所有的圆括号，得到算式的逆波兰符号法表达式abc∗+d∗e−fg+÷hi∗j∗+将变量的值代入波兰符号法表达式+÷−∗+4∗3133+12∗∗321计算如下：+÷−∗+4∗3133+12∗+÷−∗+4∗3133+12+÷−∗+4∗3133+÷−∗+4∗31+÷−∗+÷−+÷−(21)3++66(12)在上面为了区分一位数和二位数，用括号把二位数括起来.将变量的值代入逆波兰符号法表达式431∗+3∗3−12+÷32∗1∗+计算如下：431∗43+73∗(21)3−12+÷32∗1∗+(18)(18)3632∗661∗66+(12)2分析逻辑运算中有一元运算符¬，因此表示命题公式的二叉树不是正则的.由于¬的运算对象跟在它的后面，所以为了用中序行遍法访问能恢复原式，¬所在顶点的儿子应为右儿子.不过抱着对用前序行遍法访问和用后序行遍法访问的结果没有影响.表示命题公式的二叉树如图7-17所示.用前序行遍法访问该树并删去所有圆括号，得到命题公式的前缀符号法表达式→⋀⋁pq¬r→∧pq∨qr用后序行遍法访问该树并删去所有圆括号，得到命题公式的后缀符号法表达式pq∨r¬∧p¬q∧qr∨→→图7-173分析（1）设计思路输入：赋权连通图G=<V,E>。输出：G的一个最小生成树。实现语言：C语言。基本思路：使用Prim算法。在G中任意选取一个结点v1，置VT={v1在V−VT中选取与某个vi∈VT邻接的结点vj，使得边(重复（b），直到k=|V|。（2）参考代码/*Prim算法求赋权图的最小生成树*/#include<stdi.h>#defineN7//图的阶数#defineINF1000//不相邻的点，距离设为一个极大数字structedge{intstart;Intend;intweight;};//w为图的权值矩阵intw[N][N]={{0,12,INF,INF,INF,16,14},{12,0,10,INF,INF,7,INF},{INF,10,0,3,5,6,INF},{INF,INF,3,0,4,INF,INF},{INF,INF,5,4,0,2,8},{14,INF,INF,INF,8,9,0}};intverteces[N}={0};//点加入生成树的顺序,node中的点属U,不在node中的属于V-Ustructedgeedges[N];//U中顶点到V-U中顶点的最小权值的边inttree[N][N]={0};//存储最小生成树intsum=0;/*从所有的u属于U,v属于V-U(V-U表示除去U的所有顶点)的边中选取权值最小的边(u,v)，*将顶点v加入集合U中,将边(u,v)加入集合T中*/intmain(){//将权值数组初始化为“第1个顶点”到“该顶点”的权值。for(intk=0;k<N;k++){edges[k}.start=0;edges[k].end=k;edges[k].weight=w[0][k];}//第一个点加入node,此为起点vertexes[0]=1;//Primfor(intk=1;k<N;k++){intindex=0;intmin=INF;//找到权值最小的uv边,u属于U,v属于V-Ufor(intj=0;j<N;j++){if(edges[j].weight!=0&&edges[j].weight<min){min=edges[j].weight;index=j;}}if(min==INF){printf(“图G没有最小生成树！\n”);return0;}elsesum+=min;//顶点(index+1)加入nodes,到该顶点的权值置0vertexes[k]=index+1;tree[edges[index].start][edges[index].end]=edges[index].weight;tree[edges[index].end][edges[index].start]=edges[index].weight;edges[index].weight=0’//更新weightsfor(intj=0;j<N;j++){//当第j个节点没有在树中，并且有权值更小的边时才被更新if(edges[j].weight!=0&&w[index][j]<edges[j].weight){edges[j].start=index;edges[j].weight=w[index][j];}}}printf(“顶点选择顺序:”);for(intk=0;k<N;k++)printf(“%d,”,vertexes[k]);printf(“最小权值:%\n”,sum);printf(“最小生成树:\n”);for(intr=0;r<N;r++){for(intc=0;c<N;c++)printf(“d%”,tree[r][c]);printf(“\n”);}return0;}

基础练习1.判断下列集合对所给的二元运算是否封闭：（1）设集合C={3n|n∈ℤ}（2）设集合D={x|x=2（3）设集合F={a+b2解（1）对减法封闭，对除法不封闭。（2）对乘法和加法都不封闭。（3）对乘法封闭，对除法不封闭。2.在实数集R上如下定义二元运算“∘”和“∗”,∀x,y∈Rx∘y=x+y−xy,x∗y=分别讨论x∘y与x∗y是否满足结合律、交换律？是否存在单位元和逆元？解因为x∘yy∘x=y+x−yx=x+y−xy=x∘y.所以∘运算满足结合律和交换律。另外可以按照定义直接验证∘运算下0是单位元，任何不为1的实数x的逆元是xx−1同理，∗运算不满足结合律但满足交换律，但在此运算下不存在单位元，进而无法讨论逆元。3.设集合A=−5,−2,0,2,5,7，∀a,b∈A，a∗b=|a|，则集合A及其上定义的运算“解∀a∈A,a∈A，运算“∗”4.设代数系统<ℤ,⋅>，令K为所有奇数的集合，证明<K,⋅>是证由于两个奇数相乘还是奇数，即运算“⋅”在K中满足封闭性，因此<K,⋅>是<ℤ,⋅>5.设实数集R，二元运算“+”和“×”分别为数的加法与乘法，证明：代数系统<R,+>与证设映射f:R→R,fa=2a.则fa+b=f(a)f(b)，所以f提升练习1.设集合K为三维空间中的向量x,y,z(x,y,z∈ℤ)的集合，定义运算⊕为向量的点积，运算⊗为向量的叉积，判断K对运算⊕和⊗解K对⊕运算不封闭，K对⊗运算封闭.2.设S=ℤ×ℤ，ℤ是整数集，∘是S上的二元运算，对∀(m,n),(p,q)∈S，有(m,n)∘(p,q)=(mp,mq+n)。(1)运算∘在S上是否可交换、可结合、幂等的？(2)运算∘是否有单位元、零元？若有，请求出，并求出S中所有可逆元素的逆元。解(1)不可交换、可结合、非幂等.(2)运算∘的单位元是(1,0)，没有零元。当m≠0时，(m,n)的逆元为(13.如下定义正整数集ℤ+上的两种运算“∘”和“∗”，∀a,b∈ℤ+，a∘b=ab,a∗b=ab，证明：“∘”证∀a,b,c∈ℤ+,a∘b∗c=a∘bc=abc≠(a∘b)∗a∘c=4.设集合S=a,b,c，在其上如下定义运算“∘abcaabcbbaccccc解满足封闭性、交换律、结合律。a是单位元，c是零元。a和b存在逆元且a的逆元是a，b的逆元是b.5.整系数多项式ℤ[x]和多项式乘法运算“*”构成代数系统<ℤ[x],⋅>，令S为所有形如a0证由于两个不含奇数项的多项式相乘一定不含奇数项，则运算满足封闭性，所以<S,∗>是<ℤ6.设运算“×”是数的乘法，运算“∗”是矩阵的乘法，f是从实数集R到矩阵集合M的映射，其中M=xx证可以证明这样定义的映射f为同构映射，事实上，令f:<R,×>→<M,∗>,x↦xff为同构映射，即<R7.证明：<ℤ,+>上的模7同余关系R={(x,证显然R为等价关系，设x1,y1∈R,x2,y2∈R,则x1≡

群习题9解答1分析(1)运算显然是封闭的.下面验证结合律.∀x,y,z∈S，(x∗y)∗z=x∗z=x，x∗(y∗z)=x∗y=x任取e∉S，定义T=S∪e，∀x∈S，x∗e=e∗x=x，e∗e=e.那么<T,∗>2分析(a∗b)∗(a∗b)=a∗b∗a∗b=a∗a∗b∗b=a∗b3分析能构成群.运算封闭.∀x,y,z∈Z，(x∘y)∘z=(x+y−2)+z−2=x+y+z−4x∘(y∘z)=x∘(y+z−2)=x+(y+z−2)−2=x+y+z−4结合律成立，单位元是2，x的逆元是4−x.4分析设矩阵A=1001，B=那么运算表如表10-1所示.运算封闭，矩阵乘法满足结合律，单位元为A，每个矩阵的逆元都是它自己.因此G关于矩阵乘法构成群.表10-1∙ABCDAABCDBBADCCCDABDDCBA5分析1∈T，∀x,y∈T，(x,n)=1，(y,n)=1，因此存在整数a，b，c，d，使得xa+nb=1，yc+nd=1从而得到xa=1−nb，yc=1−nd(xa)(yc)=1−nb−nd+根据除法存在整数k和a'使得a=nk+a',其中.于是有x(kn+a')+nb=1,即xa'+n(b+xk)=1a<G,∗提升习题1分析如图9-1所示.图10-1对面的置换根据立方体旋转或翻转的对称轴不同分类.围绕过一对面中心的对称轴（3个）旋转90度、180度、270度，产生的置换结构如下：90度、270度：(∙)(∙)(∙∙∙∙)6个180度：(∙∙)(∙∙)(∙)(∙)3个围绕过一棱中点的对称轴（6个）翻转180度，产生的置换结构如下180度：(∙∙)(∙∙)(∙∙)6个围绕过一对顶点的对称轴（4个）旋转120度、240度，产生的置换结构如下120度、240度：(∙∙∙)(∙∙∙)8个还有恒等置换，其结构是0度：(∙)(∙)(∙)(∙)(∙)(∙)1个总计24个置换.代入Polya定理得12分析围绕中心旋转60度、120度、180度、240度、300度的置换结构如下：60度、300度：(∙∙∙∙∙∙)2个120度、240度：(∙∙∙)(∙∙∙)2个180度：(∙∙)(∙∙)(∙∙)1个围绕过一对弦中点的对称轴（3个）翻转180度，产生的置换结构如下180度：(∙∙)(∙∙)(∙∙)3个围绕过一对顶点的对存在（3个）翻转180度，产生的置换结构如下180度：(∙∙)(∙∙)(∙)(∙)3个还有恒等置换，其结构是0度：(∙)(∙)(∙)(∙)(∙)(∙)1个代入Polya定理得M=3分析（1）设计思路输入：指定的置换。输出：该置换的类型。实现语言：可自选，C/C++、Java、Python均可。基本思路：首先将置换转换为轮换，确定每一种轮换的个数，得到置换的类型。（2）核心代码这里用Python代码表示如下：defgetRotations(perm):#得到置换的轮换表达式，输入形式类似perm1=[1,4,3,6,2,5]rots=[]a=set(range(1,len(perm)+1))whilea:start=min(a)nt=perm[start-1]r=[start]whilestart!=nt:r.append(nt)nt=perm[nt-1]rots.append(r)a=a-set(r)returnrotsdefinegetPermutationType(rotations):#得到置换的类型，输入为getRotations输出的轮换结果ptype={}foriinrotat