离散数学期末复习题

1、离散数学期末复习题一、选择题1、永真式的否定是（2）(2) 永假式2、设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，则下列真命题为(1)(1) 3、设P：我听课，Q：我看小说，则命题R“我不能一边听课，一边看小说”的符号化为(3) 提示：4、下列表达式错误的有 5、下列表达式正确的有6、下列联接词运算不可交换的是(3)(3) 6、设D：全总个体域，F（x）：x是花，M(x) ：x是人，H(x,y)：x喜欢y，则命题“有的人喜欢所有的花”的逻辑符号化为 7、设L(x)：x是演员，J(x)：x是老师，A(x , y)：x钦佩y，命题“所有演员都钦佩某些老师

2、”的逻辑符号化为 8、谓词公式中的 x是既是自由变元又是约束变元 9、下列表达式错误的有 10、下列推导错在PUSESUG 11、下列推理步骤错在PUSESUGEG 12、设个体域为a,b，则去掉量词后，可表示为提示：原式二、填充题1、一个命题含有n个原子命题，则对其所有可能赋值有 种。2、n个命题变元可产生个互不等价的极小项，其中，任意两个不同极小项的合取式为矛盾式（永假式），而全体极小项的析取式为重言式（永真式），n个命题变元可构造包括F的不同的主析取范式类别为。3、n个命题变元可产生个互不等价的极大项，其中，任意两个不同极大项的析取式为重言式（永真式），而全体极小项的合取式为矛盾式（永假

3、式），n个命题变元可构造包括T的不同的主合取范式类别为。5、公式的对偶公式为。6、设P：它占据空间，Q：它有质量，R：它不断运动，S：它叫做物质。命题“占据空间的，有质量的而且不断运动的叫做物质”的逻辑符号可化为 。7、P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为； “虽然你努力了，但还是失败了”的翻译为。8、令：x会叫，：x是狗，：x会咬人，则命题“会叫的狗未必会咬人”的符号化为。9、设P(x)：x是大象，Q(x)：x是老鼠，R(x,y)：x比y重，则命题“大象比老鼠重”的符号化为。10、令A（x）:x是自然数，B（x,y）：x 小于y，则命题“存在最小的自然数” 的符号化为

4、。三、计算题1、用真值表方法判断下列公式的类型，并求（3）的主析取范式与主合取范式（1）（P®Q）«（ØPQ）；（2）Ø（P®Q）Q；（3）（P®Q）ØR；解 （1）、（2）和（3）的真值表如表1、表2和表3所示：表1 P QP®QØPQ（P®Q）«（PQ）0 0 0 1 1 0 1 1110111011111表2P Q P®QØ（P®Q）Ø（P®Q）Q0 0 0 1 1 0 1 1110100100000表3P Q RP®Q

5、ØR（P®Q）ØR0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1111100111010101010100010由上述真值表可知，（1）为永真式，（2）为永假式，（3）为可满足式。（3）的主析取范式为：；其主合取范式为。2、给定解释I：D=2，3，L（x,y）为L( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) = L (3 , 2 )=0 ,求谓词合式公式的真值。解：。3、个体域为1，2，求"x$y（x+y=4）的真值。解："x$y（x+y=4）Û"x（x

6、+1=4）（x+2=4）Û（1+1=4）（1+2=4）（2+1=4）（2+2=4）Û（00）（01）Û01Û0。四、证明题1、证明下列逻辑恒等式：（1） ()()证明、用真值表法证明P Q PQ （PQ）（QP） F FF TT FT TT TF FF FT T由定义可知，这两个公式是等价的。（2）P(QP)P(PQ)证明、P(QP)P(QP) P(PQ)P(PQ) P(PQ)P(PQ)（3） 证明 ： 左右（4）求证：$x(A(x)®B(x)Û "xA(x)®$xB(x)证明 ：$x(A(x)®B(x)

7、Û$x(ØA(x)B(x)Û$xØA(x)$xB(x)ÛØ"xA(x)$xB(x)Û"xA(x)®$xB(x)（5）求证："x(P(x)®Q(x)"xP(x)Û"x(P(x)Q(x)证明：左Û"x(P(x)®Q(x)P(x)Û"x(ØP(x)Q(x)P(x)Û"x(P(x)Q(x) Û右（6）求证："x"y(P(x)®Q(y)&

8、#219; $xP(x)®"yQ(y)证明："x"y(P(x)®Q(y)Û"x"y(ØP(x)Q(y)Û"x(ØP(x)"yQ(y)Û"xØP(x)"yQ(y)ÛØ$xP(x)"yQ(y)Û$xP(x)®"yQ(y)（7）求证：证明：左右2、用推理规则证明下列各结论是各前提的有效结论：（1）PQ，QR，R，SP=>S证明：(1) R P(2) QR P(3) Q

9、 T（1），（2）(析取三段论)(4) PQ P(5) P T（3），（4）(拒取式)(6) SP P(7) S T（5），（6）(析取三段论)（2）A(BC)，C(DE)，F(DE),A=>BF证明： (1) A P (2) A(BC) P (3) BC T（1），（2）(假言推理)(4) B P（附加前提）(5) C T（3），（4）(假言推理)(6) C(DE) 前提(7) DE T（5），（6）(假言推理)(8) F(DE) 前提(9) F T（7），（8）(拒取式)(10) BF CP （3）(PQ)(RS)，(QW)(SX)，(WX)，PR => P证明：（1） P P

10、 （假设前提）（2） PR P（3） R T（1），（2）(假言推理)（4） (PQ)(RS) P（5） PQ T（4）(化简律)（6） RS T（4）(化简律)（7） Q T （1），（5）(假言推理)（8） S T（3），（6）(假言推理)（9） (QW)(SX) P（10） QW T（9）(化简律)（11） SX T（9）(化简律)（12） W T（7），（10）(假言推理)（13） X T（8），（11）(假言推理)（14） WX T（12），（13）(合取引入)（15） (WX) P（16） (WX)(WX) T（14），（15）(合取引入)由（16）得出矛盾式，故P为原前提的有效结

11、论（4）"x(P(x)®Q(y)R(x)，$xP(x)ÞQ(y)$x(P(x)R(x)证明(1)$xP(x) P(2)P(a) T(1)，ES(3)"x(P(x)®Q(y)R(x) P(4)P(a)®Q(y)R(a) T(3)，US(5)Q(y)R(a) T(2)(4) (假言推理)(6)Q(y) T(5) (化简律) (7)R(a) T(5) (化简律)(8)P(a)R(a) T(2)(7) (合取引入)(9)$x(P(x)R(x) T(8)，EG(10)Q(y)$x(P(x)R(x) T(6)(9) (合取引入)（5）证明：$xP

12、(x) P（附加前提）P(e)TESPTUSQ(e)T(假言推理)TEGCP（6）Þ证明：PPT(假言推理)TESPTESTUST（附加律）T(假言推理)T(合取引入)TEGTEG（7）证明：（1） P（假设前提） （2） T （1） （3） T（2）(化简律) （4） T（3）ES （5） P （6） T （5） （7） T（6）US （8） T (4). (7) (假言推理)(9) T (2) (化简律)(10) T(9)US(11) T (8) (10) (合取引入)由（11）得出矛盾式，故为原前提的有效结论五、将下列命题形式化，并证明结论的有效性：1、为庆祝九七香港回归祖国，

13、四支足球队进行比赛，已知情况如下，问结论是否有效?前提: (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 P （2） A（BC） P （3） BC T（1），（2）(假言推理) （4） CA P （5） C T（1），（4）(拒取式) （6） B T（3），（5）(析取三段论)

14、（7） DB P （8） D T（6），（7）(拒取式) 故该结论有效2、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好。解 设P：今天天气好，Q：考试准时进行，A(e)：e提前进入考场，个体域：考生的集合，则命题可符号化为：ØP®$xØA(x)，"xA(x)«QQ®P。(1)ØP®$xØA(x) P(2)ØP®Ø"xA(x) T(1)(3)"xA(x)®P T

15、(2) (4)"xA(x)«Q P(5)("xA(x)®Q)(Q®"xA(x) T(4)(6)Q®"xA(x) T(5) (化简律)(7)Q®P T(6)(3) （假言三段论） 3、所有有理数都是实数，某些有理数是整数。因此，某些实数是整数。解：设Q(x)：x是有理数，R(x)：x是实数，Z(x)：x是整数。命题形式化： 。证明：（1） P (2) T(1) ES (3) T(2) (化简律) (4) P (5) T(4)US (6) T(3)(5) (假言推理) (7) T(2) (化简律) (8) T

16、(6)(7) (合取引入)(9) T (8) EG集合、关系、函数的重要知识一、关系的集合运算法则设，则有1.，2.，3.4.，二、关系特性的判断方法自反性非（反）自反性对称性非（反）对称性传递性定义若则若且则若且则集合运算关系矩阵主对角线元素全为1主对角线元素全为0对称矩阵若，且，则若，则关系图图中各顶点都有环图中各顶点都无环若两顶点间有边，必为双向边若两顶点间有边，必为单向边若两顶点通过中间点相联，则两顶点间必有直达边三、关系特性在各种运算下的遗传变异问题 设，则有四、函数的性质设函数，若是单射，则也是单射；若是满射，则也是满射；若是双射，则也是双射；若是单射，则是单射；若是满射，则是满射

17、；若是双射，则是满射，是单射集合、关系、函数的重要习题一、选择题1、下列为真命题的是（B）A、 B、 C、 D、2、下列结果错误的是（B）A、 B、 C、 D、3、非空集合上的空关系不具备的性质是（A）A、自反性 B、反自反性 C、对称性； D、传递性4、设R为S=1，2，3上的关系，其关系图如下，则下列为真命题的是（C）A、R对称，但不反对称 B、R反对称，但不对称C、R对称，又反对称 D、R不对称，也不反对称5、设R为S=1，2，3，4上的关系，其关系图如下，则下列为假命题的是（C）A、R不自反，也不反自反 B、R不对称，也不反对称 C、R传递 D、R不传递6、设R，S是集合A上的关系，则

18、下列断言正确的是（A）A、若自反，则自反 B、若对称，则对称；C、若反自反，则反自反 D、若反对称，则反对称7、设Z为整数集，下面哪个序偶不够成偏序集（A）A、 B、C、 D、8、设A=，1，1，3，1，2，3则A上包含关系“”的哈斯图为（C ）9、集合A=1，2，3，4上的偏序关系图为 则它的哈斯图为（A）10、下列关系中能构成函数的是（B）A、；B、；C、； D、11、下列函数是双射的为（A ）A、f : ZE , f (x) = 2x B、f : NNN, f (n) = <n , n+1> C、f : RZ , f (x) = 1 D、f : ZN, f (x) = | x

19、 | （注：Z整数集，E偶数集， N自然数集，R实数集）12、下面函数为单射而非满射的是（B）A、 B、；C、 D、13、下列命题正确的有（C ）A、若是双射，则都是单射 B、若是双射，则都是满射C、若是双射，则是单射, 是满射 D、若是双射，则是满射, 是单射二、填充题1、设， 则 6，12 ，2，4，8，10 ，2，3，4，8，9，102、集合的幂集=3、， 4、设，则 5、设关系A=<1,2>,<2 , 4 >,<3 , 3 > 与 B=<1,3>,<2,4>,<4,2>,则= < 1 , 4 > , &

20、lt; 2 , 2 > ， < 4 , 2 > 6、设集合A=1，2，3，4，5上偏序关系的Hass图为则集合A上的最大元为1，最小元为无，极大元为1，极小元为4,5，lub为1，glb为无；其子集B=2，3，4上的最大元为无，最小元为4，；极大元为2,3，极小元为4 ，lub为1，glb为47、偏序集的哈斯图为则= <a,b>,<a,d>,<a,e>,<a,c>,<a,f>,<a,g>,<b,d>,<b,e>,<c,f>,<c,g>8、 设A=1，2，3，

21、4，S=1，2，3，4，为A的一个分划，则由S导出的等价关系R=< 1 , 1 > , < 2 , 2> , < 2, 3 > , < 3 , 2 > , < 3 , 3 > < 4 , 4 > 9、设|X|=m，|Y|=n，则从X到Y有 种不同的关系，有 种不同的函数10、在一个有n个元素的集合上，可以有 种不同的关系，有 种不同的函数，有 种不同的双射11、设 f，g是自然数集N上的函数，则，三、问答、计算、证明题1、设R是X1，2，3，4上的二元关系，R<1，1>，<3，1>，<1，3&

22、gt;，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>(1)画出R的关系图(2)写出R的关系矩阵(3)说明R是否是自反、反自反、对称、传递的？解 (1)R的关系图如图所示：(2) R的关系矩阵为：(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，R不是反自反的；由于矩阵不对称，R不是对称的；从关系图看出，若两顶点通过中间点相联，则两顶点间必有直达边，所以R是传递的2、设X为集合，AÆX，且AÆ，若|X|n，问(1)偏序集<A，Í&

23、gt;是否有最大元？(2)偏序集<A，Í>是否有最小元？(3)偏序集<A，Í>中极大元和极小元的一般形式是什么？并说明理由。解：考察的哈斯图，最底层的顶点是空集，记作第0层，由底向上，第一层是单元集，第二层是二元集，由|X|n，则第n1层是X的n1元子集，第n层是X偏序集<A，Í>与偏序集<，Í>相比，恰好缺少第0层和第n层AÆ，则偏序集<A，Í>不存在最大元和最小元因此<A，Í>的极小元就是X的所有单元集，即x，xX；而极大元恰好是比X少一个元素，即X

24、x，xX3、 是集合上的关系，写出关系矩阵，画出关系图，问R是上的等价关系吗？解： R的关系图为 R是自反、对称的，但不传递，故不是等价关系4、求S=1，2，3，4，5上的等价关系R，使其诱导划分1，2，3，4，5，画出关系图 解：R1=1,2×1,2=<1,1>,<1,2>,<2,1>,<2,2> R2=3×3=<3,3> R3=4,5×4,5=<4,4>,<4,5>,<5,4>,<5,5> R=R1R2R3=<1,1>,<1,2>

25、,<2,1>,<2,2>,<3,3>,<4,4>,<4,5>,<5,4>,<5,5>5、设，从A到B的关系，试给出R的关系图和关系矩阵，并说明此关系及其逆关系是否为函数？为什么？ A234B2471012解：则R的关系图为：R的关系矩阵为 关系不是A到B的函数，因为元素2，4的象不唯一逆关系也不是B到A的函数因为元素7的象不存在6、设，R是A的等价关系且由R诱导的A的划分块数为4，则不同的R有多少种？解：我们知道一个集合上的等价关系数目与该集合的划分数目是一致的，因而，该题只需求出将8个元素的集合分成4份的划分

26、种数即可。 如果4份中元素个数分别为5，1，1，1，则共有种， 如果4份中元素个数分别为4，2，1，1，则共有种， 如果4份中元素个数分别为3，3，1，1，则共有种， 如果4份中元素个数分别为3，2，2，1，则共有种， 如果4份中元素个数分别为2，2，2，2，则共有种，因此，A上秩为4的等价关系共有+7、设，在上定义关系，证明：是上的等价关系，并求出证明： 1）即R自反 2）从而，即R对称 3）则 ， 从而即 R传递 综上得出，R是等价关系， 8、设A=1，2，3，4，在上规定二元关系，证明：R是上的等价关系，并写出， 商集证明：，由于，所以，即R自反的，若，则，R是对称的，若：，即： 所以R

27、是传递的由知，R是等价关系，9、若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上的等价关系10、设R是A上一个二元关系，试证明：若R是A上一个等价关系，则S也是A上的一个等价关系证明：（1），由R自反，则，即自反（2）则，且由R

28、对称，知，于是，即对称（3），则，且由R传递，知，于是，即S传递的由（1）、（2）、（3）得，S是等价关系11、设A=1，2，A上所有函数的集合记为AA, 是函数的复合运算，试给出AA上运算的运算表，并指出AA中是否有幺元，哪些元素有逆元？解：因为|A|=2，所以A上共有22=4个不同函数。令，其中：为AA中的幺元，和有逆元设函数f：R×R®R×R，f定义为：f(<x，y>)<xy，xy>。(1)证明f是双射；(2) 求逆函数f1；(3)求fof证明： (1)x，y，x1，y1R，若f(<x，y>)f(<x1，y1>

29、)，则<xy，xy><x1y1，x1y1>，xyx1y1，xyx1y1，从而xx1，yy1，故f是单射；<u，w>R×R，令x，y，则<x，y>R×R 且f(<x，y>)<，><u，w>，所以f是满射，故为双射(2)f1(<u，w>)<，>。(3)fof(<x，y>)f(<xy，xy>)<xyxy，xy(xy)><2x，2y>12、设f是A到A的满射，且，证明证明：因为f是满射，所以，存在使得，又因为f是函数，所以 即

30、由 ，知，则，由a的任意性知代数系统一、选择题：1、下列正整数集的子集在普通加法运算下封闭的是（ D ）A、 B、与互质 C、是的因子 D、是的倍数2、设S=1，2，10 ，则下面定义的运算*关于S非封闭的有（ D ）A、x*y=max(x ,y) B、x*y=min(x ,y) C、x*y=取其最大公约数D、x*y= 取其最小公倍数3、设集合的幂集为，为集合的交、并、差、笛卡尔乘积运算，则下列系统中是代数系统的为（ D ）A、 B、 C、 D、4、在自然数集上定义的下列四种运算，其中满足结合律的是（C）A、 B、 C、D、5、设为正整数集，*表示求两数的最小公倍数，对代数系统，有（ A ）A

31、、是么元，无零元 B、是零元，无么元 C、无零元，无么元 D、无等幂元6、设非空有限集的幂集为，对代数系统，有（ B ）A、是么元，是零元 B、是零元，是么元 C、唯一等幂元 D、无等幂元7、在有理数集Q上定义的二元运算*： ，则Q中元素满足（ C ）A、都有逆元 B、只有唯一逆元 C、时，有逆元 D、都无逆元8、设R是实数集合，“”为普通乘法，则代数系统<R ，×> 一定不是（ D ）A、半群 B、独异点 C、可交换的独异点 D、循环独异点9、设S=0，1，*为普通乘法，则< S , * >（ B ）A、是半群，但非独异点B、是独异点，但非群C、是群，但非阿

32、贝尔群D、是阿贝尔群10、任意具有多个等幂元的半群，它（A ）A、不能构成群B、不一定能构成群 C、能构成群 D、能构成阿贝尔群二、填充题：1、下表中的运算均定义在实数集上，请在相应的空格中打“”或填上具体实数（不满足或无该项者不填）×结合律×交换律×么元（含左、右么元）00（右幺元）1零元（含左、右零元）××02、设A=2,4,6，A上*为：a*b=maxa,b，则在独异点<A,*>中，么元是(2)，零元为(6)。3、设A=3,6,9，A上*为：a*b=mina,b，则在独异点<A,*>中，么元是(9)，零元为(3)

33、。4、代数系统<A,*>中，|A|>1，若分别为<A,*>的么元和零元，则的关系为 。*abcaabcbbaccccc5、设< a,b,c, * >为代数系统，* 运算如下：则它的么元为a ；零元为c； a、b、c的逆元分别为a、b、无。6、设G,*是一个群，则(1) 若a,b,xG，ax=b，则x=( ab)；(2) 若a,b,xG，ax=ab，则x=( b )。7、群<G,*>的等幂元是(么元)，有(1)个，零元有(0)个。8、设是12阶群的生成元， 则是(6 )阶元素，是(4)阶元素。9、设是10阶群的生成元， 则是(5 )阶元素，是

34、(10)阶元素。10、在一个群G,*中，若G中的元素的阶是k，则的阶是(k)。三、简答题：1、设A=1，2，A上所有函数的集合记为AA, 是函数的复合运算，试给出AA上运算的运算表，并指出AA中是否有么元，哪些元素有逆元？答：因为|A|=2，所以A上共有22=4个不同函数。令，其中：为AA中的么元，和有逆元。2、已知定义在集合上的运算*如下表：*abcdaabcdbbadcccdbaddcab 试问：1）是否为代数系统？2）是否为子群？3）是否为群？4）是否有单位元？5）是否满足交换律？题号12345答案3、设I是整数集合，Z3是由模3的同余类组成的同余类集，在Z3上定义+3如下：，试给出+3

35、的运算表，并指出<Z+,+3>是否构成群？+3012001211202201答：<Z+,+3>构成群。四、计算题：1、设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，则

36、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=1/a,d=-b/a。 所以(a,b)关于*的逆元为(1/a, -b/a)。2、试求<N6,+6>中每个元素的阶。解：0是<N6,+6>中关于+6的么元。则|0|=1；|1|=|5|=6，|2|=|4|=3，|3|=2。五、证明题：1、 设<R,*>是一个代数系统，*是R上二元运算，则0是么元且<R,

37、*>是独异点。证明：（1） 即 ，0是么元（2）由于+，·在R封闭，则*在R上封闭。（3） 因此 ， R，*是独异点。2、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+

38、4-a-2=2=e=4-a+a-2=(4-a)*a。故4-a是a关于运算*的逆元。综上所述，<I,*>为群。3、设*是集合A上可结合的二元运算，且a,bA,若a*b=b*a，则a=b。试证明：（1）aA,a*a=a，即a是等幂元；（2） a,bA,a*b*a=a。证明：（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

39、*a)*a，从而a*b*a=a。4、设半群<S,·>中消去律成立，则<S,·>是可交换半群当且仅当a,bS，（a·b）2=a2·b2。证明： a,bS，（a·b）2=(a·b)·(a·b)=(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&#

40、183;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。故·满足交换律。5、若<S,>是可交换独异点，T为S中所有等幂元的集合，则<T,>是<

41、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,>的子独异点。有么元且满足消去律的有限半群一定是群。证明 设<G，*>是一个有么元且满足消去律的有限半群，要证<G，*>是群，只需证明G的任一元素a可逆。，则，对a，a2，ak，因G只有有限个元素，所以存在kl，使得akal。令mkl，有al*eal*am，其中e是么元。由消去律得ame。于是，

42、当m1时，ae，而e是可逆的；当m1时，a*am-1am-1*ae。从而a是可逆的，其逆元是am-1。总之，a是可逆的。6、对独异点<A,*>，若A中每个元素都有右逆元，则<A,*>必为群。证明：设为<A,*>的么元， ，记b是a的右逆元，c是b的右逆元，则，则b是a的左逆元。故，a有唯一逆元b，于是，<A,*>必为群。7、设群<G,>除单位元外每个元素的阶均为2，则<G,>是交换群。证明：对任一aG，由已知可得a*a=e，即a-1=a。对任一a,bG，因a*b=(a*b)-1=b-1*a-1=b*a，所以*满足交换律。

43、从而G,*是交换群。8、证明：（1）有限群中阶大于2的元素的个数一定是偶数。（2）偶数阶群中阶为2 的元素的个数一定是奇数。证明：（1）设<G,·>是有限群，则aG，有|a|=|a-1|。且当a 阶大于2时，a-1。故阶数大于2 的元素成对出现，从而其个数必为偶数。证明：（2）设<G,·>是偶数阶群，则由于群的元素中阶为1 的只有一个单位元，阶大于2 的元素是偶数个，剩下元素中都是阶为2 的元素。故偶数阶群中阶为2 的元素一定是奇数个。9、设<G，*>是由g生成的循环群，则若G为无限循环群，则G只有两个生成元g和g1。证明：因为g是群&l

44、t;G，*>的生成元，所以对任意的aG，存在iZ使得agi。又a，所以g1也是群<G，*>的生成元。再证G只有g和g1这两个生成元。假设h也是G的生成元，对G的元素g，存在整数s，使得ghs。对于h来说，由g是G的生成元，存在整数t，使得hgt。于是，ghsgst。由G中的消去律得e。因为G是无限群，必有st10。从而有st1或st1，即hg或hg1。10、<G，*>是个群，uG，定义G中的运算“D”为aDb=a*u-1*b，对任意a，bG，求证：<G， D>也是个群。证明：1）"a，bG，aDb=a*u-1*bG，运算是封闭的。2）&quo

45、t;a，b，cG，（aDb）Dc=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=aD（bDc），运算是可结合的。3）"aG，设E为D的单位元，则aDE=a*u-1*E=a，得E=u，存在单位元u。4）"aG，aDx=a*u-1*x=E，x=u*a-1*u，则xDa=u*a-1*u*u-1*a=u=E，各元素都有逆元。所以<G， D>也是个群。11、设<G,·>是群，作f:GG,aa-1。证明：f是G的自同构G是交换群。证明： 设f 是G的自同构。对a，bG，a·b=(b-1·a-1)-1=(f(b) &

46、#183;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是G 的自同构。图论部分一、选择题：1欧拉回路是（B）A. 路径 B. 简单回路 C. 既是基本回路也是简单回路 D.既非基本回路也非简单回路2哈密尔顿回路是（C）A. 路径 B. 简单回路 C. 既是基本回路也是简单回路 D.既非基本回路也非简单回路3设G是简单有向图，可达矩阵P(G)刻划下列关系中的是（C）A、点与边 B、边与点 C、点与点 D、边与边4下列哪一种图不一定是树（C）。A.无简单回路的连通图 B. 有n个顶点n-1条边的连通图 C. 每对顶点间都有通路的