离散数学题库答案

1离散数学题库答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式1QQP2QPQ3PPQ4PPQP答（1），（4）2、下列公式中哪些是永真式1PQQR2PQQ3PQP4PPQ答（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式1PPQ2PQP3PQPQ4PPQQ5PQP6PPQP答（2），（3），（4），（5），（6）4、公式XAXBY，XZCY，ZDX中，自由变元是，约束变元是。答X,Y,X,Z5、判断下列语句是不是命题。若是，给出命题的真值。1北京是中华人民共和国的首都。2陕西师大是一座工厂。3你喜欢唱歌吗4若7818，则三角形有4条边。5前进6给我一杯水吧答（1）是，T（2）是，F（3）不是（4）是，T（5）不是（6）不是6、命题“存在一些人是大学生”的否定是，而命题“所有的人都是要死的”的否定是。答所有人都不是大学生，有些人不会死27、设P我生病，Q我去学校，则下列命题可符号化为。1只有在生病时，我才不去学校2若我生病，则我不去学校3当且仅当我生病时，我才不去学校4若我不生病，则我一定去学校答（1）（2）（3）（4）PQPP8、设个体域为整数集，则下列公式的意义是。1XYXY02YXXY0答（1）对任一整数X存在整数Y满足XY0（2）存在整数Y对任一整数X满足XY09、设全体域D是正整数集合，确定下列命题的真值1XYXYY2XYXYY3XYXYX4XYY2X答（1）F（2）F（3）F（4）T10、设谓词PXX是奇数，QXX是偶数，谓词公式XPXQX在哪个个体域中为真1自然数2实数3复数413均成立答（1）11、命题“2是偶数或3是负数”的否定是（）。答2不是偶数且3不是负数。12、永真式的否定是（）1永真式2永假式3可满足式413均有可能答（2）13、公式PQPQ化简为（），公式QPPQ可化简为（）。答P，QP14、谓词公式XPXYRYQX中量词X的辖域是（）。答PXYRY15、令RXX是实数，QXX是有理数。则命题“并非每个实数都是有理数”3的符号化表示为（）。答XRXQX（集合论部分）16、设AA,A，下列命题错误的是（）。1APA2APA3APA4APA答217、在0（）之间写上正确的符号。1234答418、若集合S的基数|S|5，则S的幂集的基数|PS|（）。答3219、设PX|X14且XR,QX|5X16且XR,则下列命题哪个正22确（）1QP2QP3PQ4PQ答（3）20、下列各集合中，哪几个分别相等。1A1A,B2A2B,A3A3A,B,A4A4A,B,C5A5X|XAXBXC06A6X|X2ABXAB0答A1A2A3A6，A4A521、若AB，则下列哪个结论不可能正确1A2B3AB4BA答（4）22、判断下列命题哪个为真1ABBAAB2空集是任何集合的真子集3空集只是非空集合的子集4若A的一个元素属于B，则AB答（1）423、判断下列命题哪几个为正确1,2,345A,BA,B,A,B答（2），（4）24、判断下列命题哪几个正确1所有空集都不相等24若A为非空集，则AA成立。答（2）25、设ABAC，BC，则BC。A答（等于）26、判断下列命题哪几个正确1若ABAC，则BC2A,BB,A3PABPAPB（PS表示S的幂集）4若A为非空集，则AAA成立。答（2）27、，是三个集合，则下列哪几个推理正确1AB，BCAC2AB，BCAB3AB，BCAC答（1）（二元关系部分）28、设1,2,3,4,5,6，B1,2,3，从到B的关系X,Y|XY2，求1R2R1。答（1）R,2R,129、举出集合A上的既是等价关系又是偏序关系的一个例子。答A上的恒等关系30、集合A上的等价关系的三个性质是什么答自反性、对称性和传递性531、集合A上的偏序关系的三个性质是什么答自反性、反对称性和传递性32、设S,，上的关系1,2，2,1，2,3，3,4求1RR2R1。答RR1,1，1,3，2,2，2,4R12,1，1,2，3,2，4,333、设1，2，3，4，5，6，是A上的整除关系，求R。答R,34、设1,2,3,4,5,6，B1,2,3，从到B的关系X,Y|X2Y，求1R2R1。答（1）R,2R,36135、设1,2,3,4,5,6，B1,2,3，从到B的关系X,Y|XY2，求R和R1的关系矩阵。答R的关系矩阵R的关系矩阵001101036、集合A1,2,10上的关系R|XY10,X,YA，则R的性质为（）。1自反的2对称的3传递的，对称的4传递的答（2）（代数结构部分）37、设A2,4,6，A上的二元运算定义为ABMAXA,B，则在独异点中，单位元是，零元是。答2，6638、设A3,6,9，A上的二元运算定义为ABMINA,B，则在独异点中，单位元是，零元是；答9，3（半群与群部分）39、设G,是一个群，则1若A,B,XG，AXB，则X；2若A,B,XG，AXAB，则X。答（1）AB（2）B40、设A是12阶群的生成元，则A2是阶元素，A3是阶元素。答6,441、代数系统是一个群，则G的等幂元是。答单位元42、设A是10阶群的生成元，则A4是阶元素，A3是阶元素。答5，1043、群的等幂元是，有个。答单位元，144、素数阶群一定是群,它的生成元是。答循环群，任一非单位元45、设G,是一个群，A,B,CG，则1若CAB，则C；2若CABA，则C。答（1）B2B1A46、是的子群的充分必要条件是。答是群或A，BG，ABH，A1H或A,BG，AB1H47、群A,的等幂元有个，是，零元有个。答1，单位元，0748、在一个群G,中，若G中的元素A的阶是K，则A1的阶是。答K49、在自然数集N上，下列哪种运算是可结合的（）1ABAB2ABMAXA,B3ABA2B4AB|AB|答250、任意一个具有2个或以上元的半群，它（）。1不可能是群2不一定是群3一定是群4是交换群答151、6阶有限群的任何子群一定不是（）。12阶23阶34阶46阶答3（格与布尔代数部分）52、下列哪个偏序集构成有界格（）1（N,）2（Z,）3（2,3,4,6,12,|（整除关系）4PA,答453、有限布尔代数的元素的个数一定等于（）。1偶数2奇数34的倍数42的正整数次幂答4（图论部分）54、设G是一个哈密尔顿图，则G一定是。1欧拉图2树3平面图4连通图答455、下面给出的集合中，哪一个是前缀码810，10，110，101111201，001，000，13B，C，AA，AB，ABA41，11，101，001，0011答（2）56、一个图的哈密尔顿路是一条通过图中的路。答所有结点一次且恰好一次57、在有向图中，结点V的出度DEGV表示，入度DEGV表示。答以V为起点的边的条数，以V为终点的边的条数58、设G是一棵树，则G的生成树有棵。1021324不能确定答159、N阶无向完全图KN的边数是，每个结点的度数是。答,N1260、一棵无向树的顶点数N与边数M关系是。答MN161、一个图的欧拉回路是一条通过图中的回路。答所有边一次且恰好一次62、有N个结点的树，其结点度数之和是。答2N263、下面给出的集合中，哪一个不是前缀码。1A，AB，110，A1B11201，001，000，131，2，00，01，0210412，11，101，002，0011答164、N个结点的有向完全图边数是，每个结点的度数是。答NN1,2N265、一个无向图有生成树的充分必要条件是。答它是连通图966、设G是一棵树，N,M分别表示顶点数和边数，则1NM2MN13NM14不能确定。答（3）67、设TV,E是一棵树，若|V|1，则T中至少存在片树叶。答268、任何连通无向图G至少有棵生成树，当且仅当G是，G的生成树只有一棵。答1，树69、设G是有N个结点M条边的连通平面图，且有K个面，则K等于1MN22NM23NM24MN2。答（1）70、设T是一棵树，则T是一个连通且图。答无简单回路71、设无向图G有16条边且每个顶点的度数都是2，则图G有个顶点。1102438416答（4）72、设无向图G有18条边且每个顶点的度数都是3，则图G有个顶点。1102438412答473、设图G，VA，B，C，D，E，E,则G是有向图还是无向图答有向图74、任一有向图中，度数为奇数的结点有个。答偶数75、具有6个顶点，12条边的连通简单平面图中，每个面都是由条边10围成12243345答（3）76、在有N个顶点的连通图中，其边数（）。1最多有N1条2至少有N1条3最多有N条4至少有N条答（2）77、一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则其1度顶点为（）。15273849答（4）78、若一棵完全二元（叉）树有2N1个顶点，则它（）片树叶。1N22N3N142答（1）79、下列哪一种图不一定是树（）。1无简单回路的连通图2有N个顶点N1条边的连通图3每对顶点间都有通路的图4连通但删去一条边便不连通的图答（3）80、连通图G是一棵树当且仅当G中（）。1有些边是割边2每条边都是割边3所有边都不是割边4图中存在一条欧拉路径答（2）（数理逻辑部分）二、求下列各公式的主析取范式和主合取范式1、PQR11解PQRPQRPRQR（析取范式）PQQRPPQRPQRPQRPQRPQRPQRPQRPQR（主析取范式）PQRPQRPQRPQRPQRPQR（原公式否定的主析取范式）PQRPQRPQRPQRPQRPQR（主合取范式）2、PRQRP解PRQRP（析取范式）PQQRPPQRPQQRRPQRPQRPQRPQRPQRPQRPQRPQRPQRPQRPQRPQRPQRPQR主析取范式（PRQRP）PQRPQR）（原公式否定的主析取范式）PRQRPPQRPQR（主合取范式）3、PQRP解PQRPPQRP（合取范式）PQRRPQQRPQRPQRPQRPQRPQRPQRPQR（主合取范式）PQRPPQRPQRPQRPQRPQR（原公式否定的主合取范式）PQRPPQRPQRPQRPQRPQR（主析取范式）124、QPR解QPRQPR（主合取范式）（QPR）PQRPQRPQRPQRPQRPQRPQR）（原公式否定的主合取范式）QPRPQRPQRPQRPQRPQRPQRPQR）（主析取范式）5、PPQP解PPQPPPQPPPT主合取范式PQPQPQPQ（主析取范式）6、PQRP解PQRPPQRPPQRP（析取范式）PQRRPQQRPQRPQRPQRPQRPQRPQRPQR（主析取范式）PQRPPQRPQRPQRPQRPQR（原公式否定的主析取范式）PQRPPQRPQRPQRPQRPQR（主合取范式）7、PPQ解PPQPPQPPQT主合取范式PQPQPQPQ（主析取范式）8、RQP13解RQPRQPRPQP（析取范式）RQQPRRQPRQPRQPRQPRQPPQRPQRPQR（主析取范式）RQPPQRPQR）PQRPQRPQR（原公式否定的主析取范式）RQPPQRPQRPQRPQRPQR（主合取范式）9、PQ解PQPQ（主合取范式）PQQPPQPQPQPQPQPQPQPQ（主析取范式）10、PQ解PQ（主合取范式）PQQPPQ）PQPQPQPQ）PQPQPQ（主析取范式）11、PQ解PQ（主析取范式）PQQPPQPQPQPQPQPQPQPQ（主合取范式）12、（PR）Q解（PR）QPRQPRQPQRQ（合取范式）PQRRPPQRPQRPQRPQRPQR14PQRPQRPQRPQRPQRPQRPQR（主合取范式）（PR）QPQRPQRPQRPQRPQR（原公式否定的主析取范式）（PR）QPQRPQRPQRPQRPQR（主析取范式）13、（PQ）R解（PQ）RPQRPQR析取范式PQRRPPQQRPQRPQRPQRPQRPQRPQRPQRPQRPQRPQRPQR主析取范式）（PQ）RPQRPQR析取范式PRQR合取范式PQQRPPQRPQRPQRPQRPQRPQRPQRPQR主合取范式14、PQRPQR解PQRPQRPQRPQRPQPRPQPR（合取范式）PQRRPQQRPQRRPQQRPQRPQRPQRPQR15PQRPQRPQRPQRPQRPQRPQRPQRPQRPQR主合取范式PQRPQRPQRPQR原公式否定的主合取范式PQRPQRPQRPQR主析取范式15、PPQQR解PPQQRPPQQRPQR主合取范式PQRPQRPQRPQRPQRPQRPQRPQR原公式否定的主合取范式PQRPQRPQRPQRPQRPQRPQRPQR主析取范式16、PQPR解、PQPRPQPR合取范式PQRRPQQRPQRPQRPQRPQRPQRPQRPQR主合取范式PQPRPQPRPQR合取范式PQQRRPPQRPQRPQRPQRPQRPQRPQRPQRPQRPQRPQRPQR16主析取范式三、证明1、PQ，QR，R，SPS证明1R前提2QR前提3Q（1），（2）4PQ前提5P（3），（4）6SP前提7S（5），（6）2、ABC，CDE，FDE,ABF证明1A前提2ABC前提3BC（1），（2）4B附加前提5C（3），（4）6CDE前提7DE（5），（6）8FDE前提9F（7），（8）10BFCP3、PQ，PR,QSRS证明1R附加前提2PR前提3P（1），（2）174PQ前提5Q（3），（4）6QS前提7S（5），（6）8RSCP，（1），（8）4、PQRS，QWSX，WX，PRP证明（1）P假设前提（2）PR前提（3）R（1），（2）（4）PQRS前提（5）PQ（4）（6）RS（5）（7）Q（1），（5）（8）S（3），（6）（9）QWSX前提（10）QW（9）（11）SX（10）（12）W（7），（10）（13）X（8），（11）（14）WX（12），（13）（15）WX前提（16）WXWX（14），（15）5、UVMN,UP,PQS，QSM证明1QS附加前提2PQS前提3P（1），（2）4UP前提185U（3），（4）6UV（5）7UVMN前提8MN6,79M（8）6、BD，EFD，EB证明1B附加前提2BD前提3D（1），（2）4EFD前提5EF（3），（4）6EF（5）7E（6）8E前提9EE（7），（8）7、PQR，RQSPQS证明（1）P附加前提（2）Q附加前提（3）PQR前提（4）QR（1），（3）（5）R（2），（4）（6）RQS前提（7）QS（5），（6）（8）S（2），（7）（9）QSCP，（2），（8）（10）PQSCP，（1），（9）8、PQ，PR，RSSQ19证明（1）S附加前提（2）RS前提（3）R（1），（2）（4）PR前提（5）P（3），（4）（6）PQ前提（7）Q5），（6）（8）SQCP，（1），（7）9、PQRPQPR证明1PQ附加前提2P附加前提3Q1,24PQR前提5QR2,46R3,57PRCP,2,68PQPRCP,1,710、PQR，QP,SR,PS证明（1）P前提（2）PQR前提（3）QR1，2（4）QP前提（5）Q1，4（6）R3,5（7）SR前提（8）S6，711、A，AB，AC，BDCD20证明（1）A前提（2）AB前提（3）B1，2（4）AC前提（5）C1，4（6）BDC前提（7）DC3，6（8）D5，712、ACB，BA，DCAD证明（1）A附加前提2ACB前提3CB（1），（2）4BA前提5B（1），（4）6C（3），（5）7DC前提8D（6），（7）9ADCP，（1），（8）13、PQRQ（PR）Q证明、PQRQPQRQPRQ（PR）QPRQ14、PQPPPQ证明、PQP21PQPPPQPPQ15、（PQ）（PR），QR，SPS证明、1（PQ）（PR）前提（2）PQR1（3）QR前提（4）P（2），35SP前提6S4,516、PQ，QR，RSP证明、1P附加前提（2）PQ前提（3）Q（1），（2）（4）QR前提5R（3），（4）6RS前提（7）R（6）（8）RR（5），（7）17、用真值表法证明证明、列出两个公式的真值表PQPQ（PQ）（QP）FFFTTFFFF22TTFTTTT由定义可知，这两个公式是等价的。18、PQPPQ证明、设PPQ为F，则P为T，PQ为F。所以P为T，Q为F，从而PQ也为F。所以PQPPQ。19、用先求主范式的方法证明PQPRP（QR）证明、先求出左右两个公式的主合取范式PQPRPQPRPQRRPQQRPQRPQRPQRPQRPQRPQRPQRP（QR）P（QR）PQPRPQRRPQQRPQRPQRPQRPQRPQRPQRPQR它们有一样的主合取范式，所以它们等价。20、PQQRP证明、设PQQR为T，则PQ和QR都为T。即PQ和QR都为T。故PQ，Q和R都为T，即PQ为T，Q和R都为F。从而P也为F，即P为T。从而PQQRP21、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效23前提1若A队得第一，则B队或C队获亚军2若C队获亚军，则A队不能获冠军3若D队获亚军，则B队不能获亚军4A队获第一结论5D队不是亚军。证明、设AA队得第一BB队获亚军CC队获亚军DD队获亚军则前提符号化为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不能同时为真。证明、1PR前提2P13PQ前提4Q2,35QR前提6QR57Q68QQ4,7集合论部分24四、设，是三个集合，证明1、ABCABAC证明ABACABAB（）CAACABABABA（B）AA（BC）2、ABACABC证明ABACAAABCBAABCC3、ABAC，BC，则CBA证明BBABBACCACACA4、ABABA证明ABAABABAABUAB5、ABAB证明设AB，则AB（AB）（BA）。设AB，则AB（AB）（BA）。故AB，BA，从而AB，BA，故AB。6、ABAC，ABAC，则CB证明BBABBACBABCACBCCABCAC25C7、ABAC，BC，则CBA证明BBABABACACCAC8、ABCABC证明ABCABAAABABCC9、ABACABC证明ABACAABCAAAABC10、ABB，则AB证明因为BAB，所以BBB（AB）B。从而AABB。11、AABACABC证明因为ABACAAACBAABC，且AABAC，C所以AABC，故ABC。因为ABC，所以ABCA。而ABCABAC，所以AABAC。12、ABACABC26证明因为ABACAAABCBAABC，且ABAC，C所以ABC，故ABC。因为ABC，所以ABCA。而ABCABAC，所以AABAC。13、ABBAAB证明因为ABBAA，所以BAA。但BAA，故BA。即BA，从而B（否则ABA，从而与ABBAA矛盾）。因为B，所以ABA且BA。从而ABBAA。14、ABCABC证明XABC，有AB且XC，即A，XB且XC。从而A，XBC，故XABC。从而ABCABC15、PAPBPAB（PS表示S的幂集）证明SPAPB，有SPA或SPB，所以SA或SB。从而SAB，故SPAB。即PAPBPAB16、PAPBPAB（PS表示S的幂集）证明SPAPB，有SPA且SPB，所以SA且SB。从而SAB，故SPAB。即PAPBPAB。SPAB，有SAB，所以SA且SB。从而SPA且SPB，故SPAPB。即PABPAPB。故PABPAPB17、（AB）B（AB）B当且仅当B。证明27当B时，因为（AB）B（A）A，（AB）B（A）A，所以（AB）B（AB）B。用反证法证明。假设B，则存在BB。因为BB且BAB，所以B（AB）B。而显然B（AB）B。故这与已知（AB）B（AB）B矛盾。五、证明或解答（数理逻辑、集合论与二元关系部分）1、设个体域是自然数，将下列各式翻译成自然语言1XY（XY1）2XYXY13XYXY04XY（XY0）5XYXYX6XY（XYX）7XYZXYZ答（1）存在自然数X，对任意自然数Y满足XY1（2）对每个自然数X，存在自然数Y满足XY1（3）对每个自然数X，存在自然数Y满足XY0（4）存在自然数X，对任意自然数Y满足XY1（5）对每个自然数X，存在自然数Y满足XYX（6）存在自然数X，对任意自然数Y满足XYX（7）对任意自然数X,Y，存在自然数Z满足XYZ。2、设AX,Y,ZXYZ,M（X,Y,Z）XYZ,LX,YXY，个体域为自然数。将下列命题符号化（1）没有小于0的自然数（2）XYZ（4）存在X，对任意Y使得XYY28（5）对任意X，存在Y使XYX。答（1）X（GX,0M（0,0,X）或XLX,0（2）XYZLX,YLY,ZLX,Z（3）XYLX,YZLZ,0GXZ,YZ（4）XYM（X,Y,Y）（5）XYAX,Y,X3、列出下列二元关系的所有元素（1）A0,1,2，B0,2,4，R|X,YBA（2）A1,2,3,4,5，B1,2，R|2XY4且X且YB（3）A1,2,3，B3,2,1,0,1，R|X|Y|且X且YB解1R,2R,3R,。4、对任意集合A,B，证明若AABB，则BB。证明若B，则BB。从而AA。故A。从而BA。若B，则BB。从而AA。对,BB。因为AABB，则A。从而XA。故XBA。同理可证，AB。故BA。5、对任意集合A,B，证明若A，ABAC，则BC。证明若B，则AB。从而AC。因为A，所以C。即BC。若B，则AB。从而AC。对,因为A，所以存在YA,使B。因为ABAC，则X29C。从而XC。故BC。A同理可证，CB。故BC。6、设AA,B,BC。求下列集合1A0,1B；2B2A；3AB24PAA。解（1）A0,1B,（2）B2A,（3）AB2,（4）PAA,。7、设全集UA,B,C,D,E,AA,D,BA,B,C,CB,D。求下列各集合（1）AB；（2）；（3）ACCCBAB（4）PAPB（5）ABBC（6）ABC解1ABA2A,B,C,D,E3（A）CB,D4PAPBD,A,D5ABBCD,C,A6ABCB,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。302不成立。反例如下AA,BA,B,CA,B,C。虽然AB，且BC，但AC。3不成立。反例如下AA,BA,B,CA,B,C。虽然AB，且BC，但AC。4成立。因为AB,且BC，所以AC。9、A上的任一良序关系一定是A上的全序关系。证明A，BA，则A,B是A的一个非空子集。是A上的良序关系，A,B有最小元。若最小元为A，则AB；否则BA。从而为A上的的全序关系。10、若R和S都是非空集A上的等价关系，则RS是A上的等价关系。证明AA，因为R和S都是A上的等价关系，所以XRX且XSX。故XRSX。从而RS是自反的。A,BA，ARSB，即ARB且ASB。因为R和S都是A上的等价关系，所以BRA且BSA。故BRSA。从而RS是对称的。A,B,CA，ARSB且BRSC，即ARB，ASB,BRC且BSC。因为R和S都是A上的等价关系，所以ARC且ASC。故ARSC。从而RS是传递的。故RS是A上的等价关系。11、设RAA，则R自反IAR。证明XA，R是自反的，XRX。即R，故IAR。XA，IAR，R。即XRX，故R是自反的。12、设A是集合，RAA，则R是对称的RR1。证明R，R是对称的，YRX。即R，故R_1。从而RR1。反之R1,即R。R是对称的，YRX。即R，R_1R。故RR1。31X，YA，若R，即R1。RR1，R。即YRX，故R是对称的。13、设A,B,C和D均是集合，RAB，SBC，TCD，则1RSTRSRT；2RSTRSRT；证明（1）RST，则由合成关系的定义知YB，使得R且ST。从而R且S或R且T，即RS或RT。故（RS）（RT）。从而RST（RS）（RT）。同理可证（RS）（RT）RST。故RST（RS）（RT）。2RST，则由合成关系的定义知YB，使得R且ST。从而R且S且T，即RS且RT。故（RS）（RT）。从而RSTRS）（RT）。14、设A,为偏序集，BA，若B有最大小元、上下确界，则它们是惟一的。证明设A,B都是B的最大元，则由最大元的定义AB，BA。是A上的偏序关系，AB。即B如果有最大元则它是惟一的。15、设A1,2,3,写出下列图示关系的关系矩阵，并讨论它们的性质111232323解（1）R,MR它是反自反的、反对称的、传递的；0132（2）R,MR它是反自反的、对称01的；（3）R,MR它既不是自反的、反自反的、也不10是对称的、反对称的、传递的。16、设A1,2,10。下列哪个是A的划分若是划分，则它们诱导的等价关系是什么（1）B1,3,6,2,8,10,4,5,7（2）C1,5,7,2,4,8,9,3,5,6,10（3）D1,2,7,3,5,10,4,6,8,9解（1）和（2）都不是A的划分。（3）是A的划分。其诱导的等价关系是I,。17、R是A1,2,3,4,5,6上的等价关系，RI,A求R诱导的划分。解R诱导的划分为1,5,2,4,3,6。18、A上的偏序关系的HASSE图如下。1下列哪些关系式成立AB,BA,CE,EF,DF,CF；2分别求出下列集合关于的极大（小）元、最大（小）元、上（下）界及上（下）确界（若存在的话）AABB,DCB,EDB,D,E33AEFBDC解1BA,CE,DF,CF成立；2A的极大元为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、求循环群C12E,A,A2,A11中HE,A4,A8的所有右陪集。解因为|C12|12，|H|3，所以H的不同右陪集有4个H，A,A5,A9,A2,A6,A10,A3,A7,A11。20、求下列置换的运算解（12）3654163542163541365142566543421、试求出8阶循环群的所有生成元和所有子群。解设G是8阶循环群，A是它的生成元。则GE,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，ABAB2。试问是循环群吗解是循环群。因为是无限阶的循环群，则它只有两个生成元。1和3是它的两个生成元。因为ANNA2N1，故1NN2N12N。从而对任一个KI,K22K12K，故1是的生成元。又因为1和3关于互为逆元，故3也是的生成元。23、设是群，AG。令HXG|AXXA。试证H是G的子群。证明C，DH，则对C，DHK，CAAC,DAAD。故CDACDACADCADACDACD。从而CDH。由于CAAC,且满足消去律，所以AC1C1A。故C1H。从而H是G的子群。24、证明偶数阶群中阶为2的元素的个数一定是奇数。证明设是偶数阶群，则由于群的元素中阶为1的只有一个单位元，阶大于2的元素是偶数个，剩下的元素中都是阶为2的元素。故偶数阶群中阶为2的元素一定是奇数个。25、证明有限群中阶大于2的元素的个数一定是偶数。证明设是有限群，则AG，有|A|A1|。且当A阶大于2时，A1。故阶数大于2的元素成对出现，从而其个数必为偶数。3526、试求中每个元素的阶。解0是中关于6的单位元。则|0|1；|1|5|6，|2|4|3，|3|2。27、设是群，A,BG，AE，且A4BBA5。试证ABBA。证明用反证法证明。假设ABBA。则A4BA3（AB）A3BAA5BAA2ABA（A2（BA）AA2BAAAABAAABAA2ABAA2BAAA2BA2A2BA2A2BA4。因为A4BBA5，所以BA5BA4。由消去律得，AE。这与已知矛盾。28、I上的二元运算定义为A,BI，ABAB2。试证为群。证明（1）A,B,CI，ABCABC2AB2C2ABC4,ABCABC2ABC22ABC4。故ABCABC，从而满足结合律。（2）记E2。对AI，A2A22A2A22A。故E2是I关于运算的单位元。（3）对AI，因为A（4A）A4A22E4AA24AA。故4A是A关于运算的逆元。综上所述，为群。29、设为半群，AS。令SAAI|II。试证是的子半群。证明B，CSA，则存在K,LI，使得BAK,CAL。从而BCAKALAKL。因为KLI，所以BCSA，即SA关于运算封闭。故是的子半群。30、单位元有惟一逆元。证明设是一个群，E是关于运算的单位元。36若E1,E2都是E的逆元，即E1EE且E2EE。因为E是关于运算的单位元，所以E1E1EEE2EE2。即单位元有惟一逆元。31、设E和0是关于A上二元运算的单位元和零元，如果|A|1，则E0。证明用反证法证明。假设E0。对A的任一元素A，因为E和0是A上关于二元运算的单位元和零元，则AAEA00。即A的所有元素都等于0,这与已知条件|A|1矛盾。从而假设错误。即E0。32、证明在元素不少于两个的群中不存在零元。证明（用反证法证明）设在素不少于两个的群中存在零元。对AG,由零元的定义有A。是群，关于消去律成立。AE。即G中只有一个元素，这与|G|2矛盾。故在元素不少于两个的群中不存在零元。33、证明在一个群中单位元是惟一的。证明设E1,E2都是群G,的单位元。则E1E1E2E2。所以单位元是惟一的。34、设A是一个群G，的生成元，则A1也是它的生成元。证明XG，因为A是G，的生成元，所以存在整数K，使得XA。K故XAAA。从而A1也是G，的生成元。K11K1K35、在一个偶数阶群中一定存在一个2阶元素。证明群中的每一个元素的阶均不为0且单位元是其中惟一的阶为1的元素。因为任一阶大于2的元素和它的逆元的阶相等。且当一个元素的阶大于2时，其逆元和它本身不相等。故阶大于2的元素是成对的。从而阶为1的元素与阶大于2的37元素个数之和是奇数。因为该群的阶是偶数，从而它一定有阶为2的元素。36、代数系统是一个群，则G除单位元以外无其它等幂元。证明设E是该群的单位元。若A是的等幂元，即AAA。因为AEA，所以AAAE。由于运算满足消去律，所以AE。即G除单位元以外无其它等幂元。37、设是一个群，则对于A,BG，必有唯一的XG，使得AXB。证明因为A1BG，且AA1BAA1BEBB，所以对于A,BG，必有XG，使得AXB。若X1,X2都满足要求。即AX1B且AX2B。故AX1AX2。由于满足消去律，故X1X2。从而对于A,BG，必有唯一的XG，使得AXB。38、设半群中消去律成立，则是可交换半群当且仅当A,BS，（AB）2A2B2。证明A,BS，（AB）2ABABABABAABBAABBAABBA2B2A,BS，因为（AB）2A2B2，所以ABABAABB。故ABABAABB。由于满足消去律，所以BABABB，即BABABB。从而ABBA。故满足交换律。39、设群除单位元外每个元素的阶均为2，则是交换群。证明对任一AG，由已知可得AAE，即A1A。对任一A,BG，因为ABAB1B1A1BA，所以运算满足交换律。从而G,是交换群。40、设是集合A上可结合的二元运算，且A,BA,若ABBA，则AB。试38证明（1）AA,AAA，即A是等幂元；（2）A,BA,ABAA（3）A,B,CA,ABCAC。证明（1）AA,记BAA。因为是可结合的，故有BAAAAAAAAB。由已知条件可得AAA。（2）A,BA,因为由（1），AABAAABAABA,ABAAABAAABAABA。故AABAABAA，从而ABAA。（3）A,B,CA,（ABC）（AC）（ABC）A）CABCAC且ACABCACABCACABC。由（2）可知ABCAA且CABCC，故（ABC）（AC）ABCACAC且ACABCACABCAC，即（ABC）（AC）ACABC。从而由已知条件知，ABCAC。41、设是群，作FGG,AA1。证明F是G的自同构G是交换群。证明设F是G的自同构。对A，BG，ABB1A11FBFA1FBA1BA11BA。故运算满足交换律，即G是可交换群。因为当AB时，A1B1，即FAFB，故F是G到G中的一个单一函数。又对AG，有FA1A11A。故F是G到G上的满函数。从而F是G到G上的自同构。对A，BG，因为G是可交换群，故FABAB1BA1A1B1FAFB。故F满足同态方程。从而F是G的自同构。42、若群的子群满足|G|2|H|，则一定是群的39正规子群。证明由已知可知，G关于H有两个不同的左陪集H，H1和两个不同的右陪集H，H2。因为HH1且HH1G，HH2且HH2G，故H1GHH2。对AG，若AH，则AHH,HAH。否则因为AGH，故AHH,HAH。从而AHHAGH。故H是G的不变子群。43、设H和K都是G的不变子群。证明HK也是G的不变子群。证明因为H和K都是G的不变子群，所以HK是G的子群。对AG，HHK，有AHA1AHA1，HA1AKA1。因为H和K都是G的不变子群，所以AHA1H且AHA1K。从而AHA1HK。故HK是G的不变子群。44、设群G的中心为C（G）AG|XG,AXXA。证明C（G）是G的不变子群。证明先证C（G）是G的子群。A,BC（G），对XG,有AXXA，BXXB。故（AB）XABXAXBAXBXABXAB,A1XXA1。从而AB，A1C（G）。故C（G）是G的子群。再证C（G）是G的不变子群。对AG，HCG，记BAHA1。下证BCG。因为HCG，所以BAHA1（HA）A1HAA1HCG。故C（G）是G的不变子群。45、设是没有非平凡子群的有限群。试证G是平凡群或质数阶的循环群。证明若G是平凡群，则结论显然成立。否则设的阶为N。任取AG且AE,记H（A）由A生成的G的子群。显40然HE，且G没有非平凡子群，故HG。从而G一定是循环群，且A是G的生成元。若N是合数，则存在大于1的整数K,M，使得NMK。记HE,AK,AK2,AKM1，易证H是G的子群，但1是P阶循环群，P是素数。对G中任一非单位元A。设A的阶为K,则K1。由拉格朗日定理，K是P的正整因子。因为P是素数，故KP。即A的阶就是P，即群G的阶。故A是G的生成元。48、若是可交换独异点，T为S中所有等幂元的集合，则是的子独异点。证明EEE，ET，即T是S的非空子集。A,BT,是可交换独异点,ABABABAB41ABAB（AAB）BAABBAABBAB,即ABT。故是的子独异点。49、设是群，且AG的阶为N，KI，则|AK|，其中K,N为K和,NN的最大公因子。证明记P,Q,AKM。由N和P的定义，显然有AKPE。故MP且,NKM|P。又由于AKME，所以由定理525知，N|KM。即P|QM。但P和Q互质，故P|M。由于P和M都是正整数，所以PM。即AK。,N50、设是有限群，|G|N，则AG，|A|N。证明AG，由封闭性及|G|N可知A,A2,AN,AN1中必有相同的元素，不妨设为AKAM,K到的群同态，G和G2的单位元分别为E1和1E2，则（1）HE1E2；（2）AG1，HA1HA1；（3）若HG1，则HHG2；（4）若H为单一同态，则AG1，|HA|A|。证明431因为HE1HE1HE1E1HE1E2HE1,所以HE1E2。2AG1，HAHA1HAA1HE1E2,HA1HAHA1AHE1E2,故HA1HA1。3C,DHH,A,BH，使得CHA,DHB。故CDHAHBHAB。因为HG，所以ABH，故CDHH。又C1HA1HA1且A1H，故C1HH。由定理532知HHG2。4若|A|N,则ANE1。故HANHANHE1E2。从而HA的阶也有限，且|HA|N。设|HA|M,则HAMHAMHE1E2。因为H是单一同态，所以AME1。即|A|M。故|HA|A|。若A的阶是无限的，则类似于上述证明过程可以得出，HA的阶也是无限的。故结论成立。55、有限群G的每个元素的阶均能整除G的阶。证明设|G|N，AG，则|A|M。令HE,A,A2,AM1。则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，故A1A,B1B,C1C。从而ABA,ABB,ABE,故ABC。同理可得ACCAB,CBBCA,BAC。57、在一个群中，若G中的元素A的阶是K，即|A|K，则A1的阶也是44K。证明因为|A|K，所以AKE。即（A1）KAK1E。从而A1的阶是有限的，且|A1|K。同理可证，A的阶小于等于|A1|。故A1的阶也是K。58、在一个群中，若A和B都是G的子群。若ABG，则AG或BG。证明用反证法证明。若AG且BG，则有AA,AB且BB,BA。因为A，B都是G的子群，故A,BG，从而ABG。因为AA,所以AA。若ABA,则BAABA，这与AB矛盾。从11而ABA。同理可证ABB。综合可得ABABG，这与已知矛盾。从而假设错误，得证AG或BG。59、设E是奇数阶交换群的单位元，则G的所有元素之积为E。证明设G，N为正整数。12因为G的阶数为奇数2N1，所以由拉格朗日定理知G中不存在2阶元素，即除了单位元E以外，G的所有元素的阶都大于2。故对G中的任一非单位元A，它的逆元A不是它本身，且G中不同的元素有不同的逆元。1由此可见，G中的2N个非单位元构成互为逆元的N对元素。因为G是交换群，故G的所有元素之积可变成单位元和N对互为逆元的元素之积的积，从而结果为E。60、设SQQ，Q为有理数集合，为S上的二元运算对任意A,B，C,DS,有45A,BC,DAC,ADB,求出S关于二元运算的单位元，以及当A0时，A,B关于的逆元。解设S关于的单位元为A,B。根据和单位元的定义，对X,YS,有A,BX,YAX,AYBX,Y,X,YA,BAX,XBYX,Y。即AXX,AYBY,XBYY对X,YQ都成立。解得A1,B0。所以S关于的单位元为1,0。当A0时，设A,B关于的逆元为C,D。根据逆元的定义，有A,BC,DAC,ADB1,0C,DA,BAC,CBD1,0即AC1,ADB0,CBD0。解得C,D。A1B所以A,B关