离散数学课后习题

1、一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？()(1)Q=>QP (2)Q=>PQ (3)P=>PQ (4)P(PQ)=>P 答：（1），（4）2、下列公式中哪些是永真式？( )(1)(PQ)(QR) (2)P(QQ) (3)(PQ)P (4)P(PQ)答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=>PQ (2) PQ=>P (3) PQ=>PQ (4)P(PQ)=>Q (5) (PQ)=>P (6) P(PQ)=>P答：（2），（3），（4），（5），（6）4、公式"x

2、(A(x)®B(y，x)Ù $z C(y，z)®D(x)中，自由变元是( )，约束变元是( )。答：x,y, x,z5、判断下列语句是不是命题。若是，给出命题的真值。( )(1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。(3) 你喜欢唱歌吗？ (4) 若7+818，则三角形有4条边。(5) 前进！ (6) 给我一杯水吧！ 答：（1） 是，T （2） 是，F （3） 不是（4） 是，T （5） 不是 （6） 不是6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。答：所有人都不是大学生，有些人不会死7、设P：我

3、生病，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(

4、x+y=x) ()(4) "x$y(y=2x) ()答：（1） F （2） F （3）F （4）T11、命题“2是偶数或-3是负数”的否定是（ ）。答：2不是偶数且-3不是负数。12、永真式的否定是（ ）(1) 永真式(2) 永假式(3) 可满足式(4) (1)-(3)均有可能答：（2）13、公式(PQ)(PQ)化简为（ ），公式 Q(P(PQ)可化简为（ ）。答：P ，QP15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（ ）。答："x(R(x)Q(x)（二元关系部分）28、设1,2,3,4,5,6，B=1,2,3，从到B的

5、关系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上的偏序关系的三个性质是什么？( )答：自反性、反对称性和传递性32、设S=,，上的关系1,2，2,1，2,3，3,4求(1)RR (2) R-1 。答：RR =1,1，1,3，2,2，2,4R-1 =2,1，1,2，3,2，4,333、设1，2，3，4，5，6，

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>

7、;,<2,4>,(3，6>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=maxa,b，则在独异点<A,*>中，单位元是( )，零元是( )。答：2，638、设A=3,6,9，A上的二元运算*定义为：a*b=mina,b，则

8、在独异点<A,*>中，单位元是( )，零元是( )；答：9，3（半群与群部分）39、设G,*是一个群，则(1) 若a,b,xG，ax=b，则x=( )；(2) 若a,b,xG，ax=ab，则x=( )。答： （1） ab （2） b40、设a是12阶群的生成元， 则a2是( )阶元素，a3是( )阶元素。答： 6,441、代数系统<G,*>是一个群，则G的等幂元是()。答：单位元42、设a是10阶群的生成元， 则a4是( )阶元素，a3是( )阶元素。答：5，1043、群<G,*>的等幂元是()，有()个。答：单位元，144、素数阶群一定是( )群, 它的生

9、成元是( )。答：循环群，任一非单位元45、设G,*是一个群，a,b,cG，则(1) 若ca=b，则c=( )；(2) 若ca=ba，则c=( )。答：（1） b (2) b46、<H,>是<G,>的子群的充分必要条件是( )。答：<H,>是群 或 " a，b G， abH，a-1H 或" a,b G，ab-1H 47、群A,*的等幂元有()个，是()，零元有()个。答：1，单位元，048、在一个群G,*中，若G中的元素a的阶是k，则a-1的阶是( )。答：k49、在自然数集N上，下列哪种运算是可结合的？（ ） (1) a*b=a-b(2

10、) a*b=maxa,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)（数理逻辑部分）二、求下列各公式的主析取范式和主合取范式： 1、(PQ)R 解：(PQ)R(PQ )R(PR)(QR) （析取范式）(P(QQ)R)(PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）(PQ)R)(PQR)(PQR)

11、(PQR) (PQR)( PQR)（原公式否定的主析取范式）(PQ)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、(PQ)(RP)解：(PQ)(RP)(PQ)(RP)（合取范式）(

12、PQ(RR)(P(QQ)R)(PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)（主合取范式） (PQ)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)（原公式否定的主合取范式）(PQ)(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(QP) 解：P(P(QP)P(P(QP)PP

13、T (主合取范式)(PQ)(PQ)(PQ)(PQ)（主析取范式）6、(PQ)(RP)解： (PQ)(RP)(PQ)(RP)(PQ)(RP)（析取范式）(PQ(RR)(P(QQ)R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）(PQ)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)（原公式否定的主析取范式）(PQ)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)（主合取范式）7、P(PQ) 解：P(PQ)P(PQ)(PP)QT(主合取范式)(PQ)(PQ)(PQ)(PQ)（主析取范式）8、(RQ)P解：(RQ)P(RQ )P(RP)(Q

14、P) （析取范式）(R(QQ)P)(RR)QP)(RQP)(RQP)(RQP)(RQP)(PQR)(PQR)(PQR)（主析取范式）(RQ)P)(PQR)(PQR）(PQR) (PQR)(PQR)（原公式否定的主析取范式）(RQ)P(PQR)(PQR)(PQR)(PQR)(PQR)（主合取范式）9、PQ 解：PQPQ（主合取范式）(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

15、)(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)(PQ

16、R)(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)(

17、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)

18、(PQR)(主合取范式)(PQ)(PR)(PQ)(PR)P(QR)(合取范式)(P(QQ)(RR)(PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)三、证明：1、PQ，QR，R，SP=>S证明：(1) R 前提(2) QR 前提(3) Q （1），（2）(4) PQ 前提(5) P （3），（4）(6) SP 前提(7) S （5），（6）2、A(BC)，C(DE)，F(DE),A=>BF证明： (1) A 前提(2) A(BC) 前提 (3) BC （1），（2）(4) B 附加前提(5) C

19、 （3），（4）(6) C(DE) 前提(7) DE （5），（6）(8) F(DE) 前提(9) F （7），（8）(10) BF CP 3、PQ， PR, QS => RS证明：(1) R 附加前提(2) PR 前提(3) P （1），（2）(4) PQ 前提(5) Q （3），（4）(6) QS 前提(7) S （5），（6）(8) RS CP，（1），（8）4、(PQ)(RS)，(QW)(SX)，(WX)，PR => P证明： （1） P 假设前提（2） PR 前提（3） R （1），（2）（4） (PQ)(RS) 前提（5） PQ （4）（6） RS （5）（7） Q （

20、1），（5）（8） S （3），（6）（9） (QW)(SX) 前提（10） QW （9）（11） SX （10）（12） W （7），（10）（13） X （8），（11）（14） WX （12），（13）（15） (WX) 前提（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，(EF)D，E=>B

21、证明：(1) B 附加前提(2) BD 前提 (3) D （1），（2）(4) (EF)D 前提(5) (EF) （3），（4）(6) EF （5）(7) E （6）(8) E 前提(9) EE （7），（8）7、P(QR)，R(QS) => P(QS)证明：（1） P 附加前提（2） Q 附加前提（3） P(QR) 前提（4） QR （1），（3）（5） R （2），（4）（6） R(QS) 前提（7） QS （5），（6）（8） S （2），（7）（9） QS CP，（2），（8）（10） P(QS) CP，（1），（9）8、PQ，PR，RS =>SQ 证明：（1） S 附加前

22、提（2） RS 前提（3） R （1），（2）（4） PR 前提（5） P （3），（4）（6） PQ 前提（7） Q (5），（6）（8） SQ CP，（1），（7）9、P(QR) => (PQ)(PR)证明：(1) PQ 附加前提(2) P 附加前提(3) Q (1),(2)(4) P(QR) 前提(5) QR (2),(4)(6) R (3),(5)(7) PR CP,(2),(6)(8) (PQ) (PR) CP,(1),(7)10、P(QR)，QP,SR,P =>S证明：（1） P 前提（2） P(QR) 前提（3） QR (1)，(2)（4） QP 前提（5） Q (1

23、)，(4)（6） R (3),(5)（7） SR 前提（8） S (6)，(7)11、A，AB， AC， B(DC) => D证明：（1） A 前提（2） AB 前提（3） B (1)，(2)（4） AC 前提（5） C (1)，(4)（6） B(DC) 前提（7） DC (3)，(6)（8） D (5)，(7)12、A(CB)，BA，DC => AD证明：（1） A 附加前提(2) A(CB) 前提 (3) CB （1），（2）(4) BA 前提(5) B （1），（4）(6) C （3），（5）(7) DC 前提(8) D （6），（7）(9) AD CP，（1），（8）13、

24、(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，RS P证明、(1) P 附加前提 （2） PQ 前提 （3） Q （1），（2） （4） QR 前提 (5) R （3），（4） (6 ) RS 前提 （7） R （6） （8） RR （5），（7

25、）17、用真值表法证明 ()()证明、列出两个公式的真值表：P Q PQ （PQ）（QP） F FF TT FT TT TF FF FT T由定义可知，这两个公式是等价的。18、PQP(PQ)证明、设P(PQ)为F，则P为T，PQ为F。所以P为T，Q为F ，从而PQ也为F。所以PQP(PQ)。19、用先求主范式的方法证明(PQ)(PR) (P（QR）证明、先求出左右两个公式 的主合取范式(PQ)(PR) (PQ)(PR) (PQ(RR)(P(QQ)R) (PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR) (P（QR）) (P（QR）) (PQ)(PR)(PQ(RR)(P(

26、QQ)R) (PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)它们有一样的主合取范式，所以它们等价。20、(PQ)(QR) P证明、设(PQ)(QR)为T，则PQ和(QR)都为T。即PQ和QR都为T。故PQ，Q和R)都为T，即PQ为T，Q和R都为F。从而P也为F，即P为T。从而(PQ)(QR) P21、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效?前提: (1) 若A队得第一，则B队或C队获亚军;(2) 若C队获亚军，则A队不能获冠军;(3) 若D队获亚军，则B队不能获亚军;(4) A 队获第一;结论: (5) D队不是亚军。证明、设A：A队得

27、第一;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),(

28、7)(7) 证明或解答：（数理逻辑、集合论与二元关系部分）3、列出下列二元关系的所有元素：（1）A=0,1,2，B=0,2,4，R=<x,y>|x,y;（2）A=1,2,3,4,5，B=1,2，R=<x,y>|2x+y4且x且yB;（3）A=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>

29、(3) R=<1,1>,<1,-1>,<2,-2>,<3,-3>。4、对任意集合A,B，证明：若AA=BB，则B=A。证明：若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，则<

30、;y,x>C。从而xC。故BC。同理可证，CB。故B=C。6、设A=a,b, B=c。求下列集合：(1) A0,1B； (2) B2A；(3) (AB)2; (4) P(A)A。解：（1） A0,1B=<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>,&

31、lt;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是任意集合，证明或否定下列断言：

32、（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，bA，则a,b是A的一个非空子集。是A上的良序关系，a,b有最小元。若最小元为a，则ab；否则ba。从而为A上的的全序关系

33、。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、设RA×A，则R自反 IAR。证明：xA，R是自反的，xRx。即<x,x>R，故IAR。xA，IAR，<x,x>

34、R。即xRx，故R是自反的。12、设A是集合，RA×A，则R是对称的RR1。证明：<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)

35、=(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）（RT）R(ST)。故R(ST)=（RS）（RT）。(2) <x，z>R(ST)，则由合成关系的定义知yB，使得<x，y>R且<

36、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,写出下列图示关系的关系矩阵，并讨论它们的性质： 1 1 12 3 2 3 2 3解：（1）R=<2,1>,<3,1>,&l

37、t;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;（

38、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上的

39、等价关系，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图如下。(11) 下列哪些关系式成立：ab,ba,ce,ef,df,cf；(12) 分别求出下列集合关于的极大（小）元、最大（小）元、上（下）界及上（下）确界（若存在的话）：(a) A; (b) b,d; (c) b,e; (d) b,d,e a e f b d c解：(1) ba,ce,df,cf成立；(2) (a)的极大元为a,e,f,极小元为c

40、;无最大元，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、求

41、下列置换的运算：解：（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

42、+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。

43、故(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 的元素

44、。故偶数阶群中阶为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&#

45、183;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)·

46、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是

47、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,·&g

48、t;的子半群。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、证明在元素不少于两个的群中不存在零元。证明：（用反证法证明）设在素不少于

49、两个的群<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 且单位元

50、是其中惟一的阶为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,bG，必有唯一的xG，使得ax=b。证明：因为a

51、-1*bG，且a*(a-1*b)=(a*a-1)*b=e*b=b，所以对于a,bG，必有xG，使得ax=b。若x1,x2都满足要求。即ax1=b且ax2=b。故ax1=ax2。由于*满足消去律，故x1=x2。从而对于a,bG，必有唯一的xG，使得ax=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·

52、;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)·

53、;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*(