《离散数学》练习题和参考答案

更新时间：2024-01-30 04:20:01 阅读量：教育文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

《离散数学》试题及答案推荐度：
相关推荐

《离散数学》练习题和参考答案

一、选择或填空（数理逻辑部分） 1、下列哪些公式为永真蕴含式？( )

(1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P?(P?Q)=>?P 答：（1），（4） 2、下列公式中哪些是永真式？( )

(1)(┐P?Q)→(Q→?R) (2)P→(Q→Q) (3)(P?Q)→P (4)P→(P?Q) 答：（2），（3），（4） 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P?Q (2) P?Q=>P (3) P?Q=>P?Q

(4)P?(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P?(P?Q)=>?P 答：（2），（3），（4），（5），（6） 4、公式?x((A(x)?B(y，x))? ?z C(y，z))?D(x)中，自由变元是( )，约束变元是( )。答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( )

北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是

6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。答：所有人都不是大学生，有些人不会死

7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1） ?Q?P （2） P??Q （3） P??Q （4）?P?Q 8、设个体域为整数集，则下列公式的意义是( )。 (1) ?x?y(x+y=0) (2) ?y?x(x+y=0)

答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=0 9、设全体域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）T 10、设谓词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、公式(?P?Q)?(?P??Q)化简为（），公式 Q?(P?(P?Q))可化简为（）。答：?P ，Q?P 14、谓词公式?x(P(x)? ?yR(y))?Q(x)中量词?x的辖域是（）。答：P(x)? ?yR(y)

15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（）。

答：??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)|=（）。答：32

19、设P={x|(x+1)?4且x?R},Q={x|5?x+16且x?R},则下列命题哪个正确（） 22 (1) Q?P (2) Q?P (3) P?Q (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=A5

21、若A-B=Ф，则下列哪个结论不可能正确？( ) (1) A=Ф (2) B=Ф (3) A?B (4) B?A 答：（4）

22、判断下列命题哪个为真?( )

(1) A-B=B-A => A=B (2) 空集是任何集合的真子集

(3) 空集只是非空集合的子集 (4) 若A的一个元素属于B，则A=B 答：（1）

23、判断下列命题哪几个为正确？( )

(1) {Ф}∈{Ф,{{Ф}}} (2) {Ф}?{Ф,{{Ф}}} (3) Ф∈{{Ф}} (4) Ф?{Ф} (5) {a,b}∈{a,b,{a},{b}} 答：（2），（4）

24、判断下列命题哪几个正确？( )

(1) 所有空集都不相等 (2) {Ф}?Ф (4) 若A为非空集，则A?A成立。答：（2）

25、设A∩B=A∩C，A∩B=A∩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为非空集，则A?A∪A成立。 27、Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理正确：

答：=（等答：（2）

(1) A?B，B?C=> A?C (2) A?B，B?C=> 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,1>,<2,4>}

29、举出集合A上的既是等价关系又是偏序关系的一个例子。( ) 答：A上的恒等关系

30、集合A上的等价关系的三个性质是什么？( ) 答：自反性、对称性和传递性

31、集合A上的偏序关系的三个性质是什么？( ) 答：自反性、反对称性和传递性

32、设S={１,２,３,４}，Ａ上的关系Ｒ＝｛〈1,2〉，〈2,1〉，〈2,3〉，〈3,4〉｝求(1)R?R (2) R-1 。答：R?R ={〈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,1>,<2,4>,(36>}

35、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2｝，求R和R-1的关系矩阵。

??10?000?0??000????010??100000???000??000100??答：R的关系矩阵=??000??? R?1的关系矩阵=??000000??

36、集合A={1,2,…,10}上的关系R={|x+y=10,x,y?A}，则R 的性质为（）。

(1) 自反的 (2) 对称的 (3) 传递的，对称的 (4) 传递的（代数结构部分）

37、设A={2,4,6}，A上的二元运算*定义为：a*b=max{a,b}，则在独异点中，单位元是( )，零元是( )答：2，6

38、设A={3,6,9}，A上的二元运算*定义为：a*b=min{a,b}，则在独异点中，单位元是( )，零元是( )答：9，3 （半群与群部分）

39、设〈G,*〉是一个群，则

(1) 若a,b,x∈G，a?x=b，则x=( )；

(2) 若a,b,x∈G，a?x=a?b，则x=( )。答：（1） a?1?b b

40、设a是12阶群的生成元，则a2是( )阶元素，a3是( )阶元素。

。；（2）答：

6,4

41、代数系统是一个群，则G的等幂元是( )。答：单位元

42、设a是10阶群的生成元，则a4是( )阶元素，a3是( )阶元素。答：5，10

43、群的等幂元是( )，有( )个。答：单位元，1

44、素数阶群一定是( )群, 它的生成元是( )。答：循环群，任一非单位元

45、设〈G,*〉是一个群，a,b,c∈G，则

(1) 若c?a=b，则c=( )；(2) 若c?a=b?a，则c=( )。 b

46、是的子群的充分必要条件是( )。

答：是群或 ? a，b ?G， a?b?H，a-1?H 或? a,b ?G，a?b-1?H

47、群＜A,*＞的等幂元有( )个，是( )，零元有( )个。位元，0

48、在一个群〈G,*〉中，若G中的元素a的阶是k，则a-1的阶是( )。 49、在自然数集N上，下列哪种运算是可结合的？（）

(1) a*b=a-b (2) a*b=max{a,b} (3) a*b=a+2b (4) a*b=|a-b| 50、任意一个具有2个或以上元的半群，它（）。 (1) 不可能是群 (2) 不一定是群

(3) 一定是群 (4) 是交换群 51、6阶有限群的任何子群一定不是（）。

(1) 2阶 (2) 3 阶 (3) 4 阶 (4) 6 阶（格与布尔代数部分）

52、下列哪个偏序集构成有界格（） (1) （N,?） (2) （Z,?）

(3) （{2,3,4,6,12},|（整除关系）） (4) (P(A),?) 53、有限布尔代数的元素的个数一定等于（）。

(1) 偶数 (2) 奇数 (3) 4的倍数 (4) 2的正整数次幂（图论部分）

54、设G是一个哈密尔顿图，则G一定是( )。 (1) 欧拉图 (2) 树 (3) 平面图 (4) 连通图 55、下面给出的集合中，哪一个是前缀码？( ) (1) {0，10，110，101111} (2) {01，001，000，1}

答：（1） b?a?1 (2) 答：1，单答：k

(3) {b，c，aa，ab，aba} (4) {1，11，101，001，0011}

56、一个图的哈密尔顿路是一条通过图中( )的路。答：所有结点一次且恰好一次

57、在有向图中，结点v的出度deg+(v)表示( )，入度deg-(v)表示( )。答：以v为起点的边的条数，以v为终点的边的条数 58、设G是一棵树，则G 的生成树有( )棵。 (1) 0 (2) 1 (3) 2 (4) 不能确定

59、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。

n(n?1)2答：, n-1

60、一棵无向树的顶点数n与边数m关系是( )。答：m=n-1

61、一个图的欧拉回路是一条通过图中( )的回路。答：所有边一次且恰好一次

62、有n个结点的树，其结点度数之和是( )。答：2n-2

63、下面给出的集合中，哪一个不是前缀码( )。 (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-2

65、一个无向图有生成树的充分必要条件是( )。答：它是连通图

66、设G是一棵树，n,m分别表示顶点数和边数，则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。答：（3）

67、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。答：2

68、任何连通无向图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是一个连通且( )图。

?(P??Q?R)?(P??Q??R)?(P?Q??R)?(?P?Q?R)

?(?P?Q??R)?(?P??Q?R)?(?P??Q??R)

(原公式否定的主合取范式) (P?Q?R)

?(?P?Q??R)?(?P?Q?R)?(?P??Q?R)?(P??Q??R)

?(P??Q?R)?(P?Q??R)?(P?Q?R)(主析取范式)

16、(P?Q)?(P?R) 解、(P?Q)?(P?R)

?(?P?Q)?(?P?R) (合取范式)

?(?P?Q?(R??R)?(?P?(?Q?Q)?R)

?(?P?Q?R)?(?P?Q??R)?(?P??Q?R)?(?P?Q?R) ?(?P?Q?R)?(?P?Q??R)?(?P??Q?R)(主合取范式)

(P?Q)?(P?R)

?(?P?Q)?(?P?R) ??P?(Q?R)(合取范式)

?(?P?(Q??Q)?(R??R))?((?P?P)?Q?R)

?(?P?Q?R)?(?P??Q?R)?(?P?Q??R)?(?P??Q?R) ?(?P?Q?R)?(P?Q?R)

?(?P?Q?R)?(?P??Q?R)?(?P?Q??R)?(?P??Q?R)?(P?Q?R)

(主析取范式)

三、证明：

1、P→Q，?Q?R，?R，?S?P=>?S 证明：

(1) ?R 前提 (2) ?Q?R 前提 ?Q （1），（2） P→Q 前提 ?P （3），（4） ?S?P 前提 (7) ?S （5），（6）

2、A→(B→C)，C→(?D?E)，?F→(D??E),A=>B→F 证明：

(1) A 前提

(2) A→(B→C) 前提

(3) B→C （1），（2） (4) B 附加前提 C （3），（4） C→(?D?E) 前提 ?D?E （5），（6） ?F→(D??E) 前提 F （7），（8） B→F CP

3、P?Q， P→R, Q→S => R?S 证明：

(1) ?R 附加前提 (2) P→R 前提 (3) ?P （1），（2） (4) P?Q 前提 (5) Q （3），（4） (6) Q→S 前提 (7) S （5），（6） (8) R?S CP，（1），（8）

4、(P→Q)?(R→S)，(Q→W)?(S→X)，?(W?X)，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） W?X （12），（13）

（15） ?(W?X) 前提

（16） ?(W?X)?(W?X) （14），（15）

5、(U?V)→(M?N), U?P, P→(Q?S)，?Q??S =>M 证明：

(1) ?Q??S 附加前提 P→(Q?S) 前提 ?P （1），（2） U?P 前提 U （3），（4） U?V （5） (U?V)→(M?N) 前提 M?N (6),(7) M （8）

6、?B?D，(E→?F)→?D，?E=>?B 证明：

(1) B 附加前提 (2) ?B?D 前提 (3) D （1），（2） (4) (E→?F)→?D 前提 (5) ?(E→?F) （3），（4） (6) E??F （5） (7) E （6） (8) ?E 前提 (9) E??E （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）（5） R （2），（4）（6） R→(Q→S) 前提（7） Q→S （5），（6）（8） S （2），（7）（9） Q→S CP，（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→?Q CP，（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→R CP,(2),(6) (8) (P→Q) →(P→R) CP,(1),(7)

10、P→(?Q→?R)，Q→?P,S→R,P =>?S 证明：

（1） P 前提（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→(C?B)，B→?A，D→?C => A→?D 证明：

（1） A 附加前提 (2) A→(C?B) 前提

(3) C?B （1），（2） B→?A 前提 ?B （1），（4） C （3），（5） D→?C 前提 ?D （6），（7） A→?D CP，（1），（8） 13、(P?Q)?(R?Q) ?（P?R）?Q 证明、

(P?Q)?(R?Q)

?(?P?Q)?(?R?Q) ?(?P??R)?Q

??（P?R）?Q

?(P?R)?Q

14、P?(Q?P)??P?(P??Q) 证明、 P?(Q?P)

??P?(?Q?P) ??(?P)?(?P??Q) ??P?(P??Q)

15、（P?Q）?（P?R），?(Q?R)，S?P?S 证明、

(1) （P?Q）?（P?R）前提

（2） P? (Q?R) (1) （3） ?(Q?R) 前提

（4） ?P （2），(3) (5) S?P 前提 (6) S (4),(5) 16、P?证明、

(1) P 附加前提（2） P? （4） Q?

?Q，Q??R，R??S? ?P

?Q 前提

（3） ?Q （1），（2）

?R 前提 ?S 前提 ?R （5），（7）

(5) ?R （3），（4） (6 ) R? （7） R （6）（8） R?17、用真值表法证明Ｐ?Ｑ? (Ｐ?Ｑ)?(Ｑ?Ｐ) 证明、

列出两个公式的真值表：

P Q P?Q （P?Q）?（Q?P） F F T T F T F F T F F F T T T T 由定义可知，这两个公式是等价的。 18、P→Q?P→(P?Q) 证明、

设P→(P?Q)为F，则P为T，P?Q为F。所以P为T，Q为F ，从而P→Q也为F。所以P→Q?P→(P?Q)。 19、用先求主范式的方法证明(P→Q)?(P→R) ? (P→（Q?R）证明、

先求出左右两个公式的主合取范式 (P→Q)?(P→R) ?(?P?Q)?(?P?R)

?(?P?Q?(R??R)))?(?P?(Q??Q)?R)

? (?P?Q?R)?(?P?Q??R)?(?P?Q?R)?(?P??Q?R) ? (?P?Q??R)?(?P?Q?R)?(?P??Q?R)

(P→（Q?R）) ?(?P?（Q?R）)

?(?P?Q)?(?P?R)

?(?P?Q?(R??R))?(?P?(Q??Q)?R)

? (?P?Q?R)?(?P?Q??R)?(?P?Q?R)?(?P??Q?R) ? (?P?Q??R)?(?P?Q?R)?(?P??Q?R)

它们有一样的主合取范式，所以它们等价。 20、(P→Q)?证明、设(P→Q)??(Q?R) ??P

?(Q?R)为T，则P→Q和?(Q?R)都为T。即P→Q和?Q??R都为T。故P→Q，?Q和?R)都为T，即

?(Q?R) ??P

P→Q为T，Q和R都为F。从而P也为F，即?P为T。从而(P→Q)?21、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效? 前提: (1) 若A队得第一，则B队或C队获亚军; 若C队获亚军，则A队不能获冠军; 若D队获亚军，则B队不能获亚军; A 队获第一;

结论: (5) D队不是亚军。证明、

设A：A队得第一;B: B队获亚军;C: C队获亚军;D: D队获亚军;则前提符号化为A?（B?C），C??A，D??B，A；结论符号化为 ?D。

本题即证明 A?（B?C），C??A，D??B，A??D。（1） A 前提（2） A?（B?C）前提（3） B?C （1），（2）（4） C??A 前提（5） ?C （1），（4）（6） B （3），（5）（7） D??B 前提（8） ?D （6），（7）

22、用推理规则证明P?Q, ?(Q?R),P?R不能同时为真。证明、

(1) P?R 前提 (2) P (1) (3) P?Q 前提 (4) Q (2),(3) (5) ?(Q?R) 前提

(6) ?Q??R (5) (7) ?Q (6) (8) ?Q?Q (4),(7)

(集合论部分)

四、设Ａ，Ｂ，Ｃ是三个集合，证明： 1、A? (B－C)＝(A?B)－(A?C) 证明：

(A?B)－(A?C)= (A?B) ?A?C=(A?B) ?（A?C） =(A?B?A)?(A?B?C)= A?B?C=A?（B?C） =A?（B-C）

2、(A－B)?(A－C)=A－(B?C) 证明：

(A-B)?(A-C)=(A?B)?(A?C) =A? (B?C) =A?B?C= A-(B?C)

3、A?B=A?C，A?B=A?C，则C=B 证明：

B=B?(A?A)=(B?A)? (B?A) =(C?A)? (C?A)=C?(A?A)=C 4、A?B=A?(B-A) 证明：

A?(B-A)=A?(B?A)=(A?B)?(A?A) =(A?B)?U= A?B 5、A=B ? A?B=? 证明：

?设A=B，则A?B=（A-B）?（B-A）=???=?。

?设A?B=?，则A?B=（A-B）?（B-A）=?。故A-B=?，B-A=?，从而A?B，B?A，故A=B。

6、A?B = A?C，A?B=A?C，则C=B 证明：

B=B?(A?B)= B?(A?C)= (B?A)?(B?C) = (A?C)?(B∩C)= C?(A?B) = C?(A?C) =C

7、A?B=A?C，A?B=A?C，则C=B 证明：

B=B?(A?A)=(B?A)?(B?A) =(C?A)?(C?A)=C?(A?A) =C

8、A－(B?C)＝(A－B)－C 证明：

A－(B?C)= A?B?C =A?(B?C)=(A?B)?C =(A-B)?C=(A-B)-C

9、(A－B)?(A－C)=A－(B?C) 证明： (A-B)?(A－C) =(A?B)?(A?C) =(A?A)?(B?C) =A?B?C=A－(B?C) 10、A-B=B，则A=B=? 证明：

因为B=A-B，所以B=B?B=（A-B）?B=?。从而A=A-B=B=?。 11、A=(A-B)?(A-C)?A?B?C=? 证明：

? 因为(A-B)?(A-C) =(A?B)?(A?C) =A?(B?C)

=A?B?C= A-(B?C)，且A=(A-B)?(A-C)，所以A= A-(B?C)，故A?B?C=?。

? 因为A?B?C=?，所以A-(B?C)=A。而A-(B?C)= (A-B)?(A-C)，

所以A=(A-B)?(A-C)。 12、(A-B)?(A-C)=??A?B?C 证明：

? 因为(A-B)?(A-C) =(A?B)?(A?C) =A?(B?C)

=A?B?C= A-(B?C)，且(A-B)?(A-C)=?，所以?= A-(B?C)，故A?B?C。

? 因为A?B?C，所以A-(B?C)=A。而A-(B?C)= (A-B)?(A-C)，

所以A=(A-B)?(A-C)。 13、(A-B)?(B-A)=A ? B=? 证明：

? 因为(A-B)?(B-A)=A，所以B-A?A。但(B-A)?A=?，故B-A=?。

即B?A，从而B=?（否则A-B?A，从而与(A-B)?(B-A)=A矛盾）。

? 因为B=?，所以A-B=A且B-A=?。从而(A-B)?(B-A)=A。

14、(A-B)-C?A-(B-C) 证明：

?x?(A-B)-C，有x?A-B且x?C，即x?A，x?B且x?C。

从而x?A，x?B-C，故x?A-(B-C)。从而(A-B)-C?A-(B-C) 15、P(A)?P(B)?P(A?B) （P(S)表示S的幂集）证明：

?S?P(A)?P(B)，有S?P(A)或S?P(B)，所以S?A或S?B。

从而S?A?B，故S?P(A?B)。即P(A)?P(B)?P(A?B) 16、P(A)?P(B)=P(A?B) （P(S)表示S的幂集）证明：

?S?P(A)?P(B)，有S?P(A)且S?P(B)，所以S?A且S?B。

从而S?A?B，故S?P(A?B)。即P(A)?P(B)?P(A?B)。

?S?P(A?B)，有S?A?B，所以S?A且S?B。

从而S?P(A)且S?P(B)，故S?P(A)?P(B)。即P(A?B)?P(A)?P(B)。故P(A?B)=P(A)?P(B)

17、（A-B）?B=（A?B）-B当且仅当B=?。证明：

? 当B=?时，因为（A-B）?B=（A-?）??=A，（A?B）-B=（A??）-? =A，所以（A-B）?B=（A?B）-B。 ? 用反证法证明。假设B??，则存在b?B。因为b?B且b? A?B，所以b?（A?B）-B。而显然b?（A-B）?B。

故这与已知（A-B）?B=（A?B）-B矛盾。

五、证明或解答：

（数理逻辑、集合论与二元关系部分）

1、设个体域是自然数，将下列各式翻译成自然语言： (1) ?x?y（xy=1）; (2) ?x?y(xy=1); (3) ?x?y (xy=0); (4) ?x?y（xy=0）;

(5) ?x?y (xy=x); (6) ?x?y（xy=x）; (7) ?x?y?z (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; （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））或??x L(x,0) （2）?x?y?z ((L(x,y)?L(y,z))?L(x,z)) （3）?x?y ((L(x,y)??z(L(z,0)?G(xz,yz))) （4）?x?yM（x,y,y）（5）?x?yA(x,y,x)

3、列出下列二元关系的所有元素：

（1）A={0,1,2}，B={0,2,4}，R={|x,y?A?B};

（2）A={1,2,3,4,5}，B={1,2}，R={|2?x+y?4且x?A且y?B}; （3）A={1,2,3}，B={-3,-2,-1,0,1}，R={||x|=|y|且x?A且y?B}; 解：

(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，证明：若A?A=B?B，则B=B。证明：

若B=?，则B?B=?。从而A?A =?。故A=?。从而B=A。若B??，则B?B??。从而A?A??。

个体域为自然数。将下列命题符号化：

对?x?B, ?B?B。因为A?A=B?B，则?A?A。从而x?A。故B?A。同理可证，A?B。故B=A。

5、对任意集合A,B，证明：若A??，A?B=A?C，则B=C。证明：

若B=?，则A?B=?。从而A?C =?。因为A??，所以C=?。即B=C。若B??，则A?B??。从而A?C??。

对?x?B,因为A??，所以存在y?A, 使?A?B。因为A?B=A?C，则?A?C。从而x?C。故B?C。同理可证，C?B。故B=C。

6、设A={a,b}, B={c}。求下列集合： (1) A?{0,1}?B； (2) B2?A； (3) (A?B)2; (4) P(A)?A。解：

（1） A?{0,1}?B={,,,}; （2） B2?A={,};

（3） (A?B)2={,,,}; （4） P(A)?A={,,<{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）A?B?C；（2）A?B?C；（3）(A?B)?C; （4）P(A)-P(B); （5）(A-B)?(B-C); （6）(A?B)?C; 解：

(1) A?B?C={a}; (2) A?B?C={a,b,c,d,e}; (3) （A?B）?C={b,d}; (4) P(A)-P(B)={{d},{a,d}}; (5) (A-B)?(B-C)={d,c,a}; (6) (A?B) ?C={b,d}。 8、设A,B,C是任意集合，证明或否定下列断言：（1）若A?B，且B?C，则A?C；（2）若A?B，且B?C，则A?C; （3）若A?B，且B?C，则A?C；（4）若A?B，且B?C，则A?C；证明： (1) 成立。

对?x?A, 因为A?B，所以x?B。又因为B?C，所以x?C。即A?C。

(2) 不成立。反例如下：A={a}, B={a,b},C={a,b,c}。虽然A?B，且B?C，但A?C。 (3) 不成立。反例如下：A={a}, B={{a},b},C={{{a},b},c}。虽然A?B，且B?C，但A?C。 (4) 成立。因为A?B, 且B?C，所以A?C。 9、A上的任一良序关系一定是A上的全序关系。证明：

?a，b∈A，则{a,b}是A的一个非空子集。?≤是A上的良序关系，?{a,b}有最小元。若最小元为a，则a≤b；否则

b≤a。从而≤为A上的的全序关系。

10、若R和S都是非空集A上的等价关系，则R?S是A上的等价关系。证明：

?a∈A，因为R和S都是A上的等价关系，所以xRx且xSx。故xR?Sx。从而R?S是自反的。

?a,b∈A，aR?Sb，即aRb且aSb。因为R和S都是A上的等价关系，所以bRa且bSa。故bR?Sa。从而R?S是对

称的。

?a,b,c∈A，aR?Sb且bR?Sc，即aRb，aSb,bRc且bSc。因为R和S都是A上的等价关系，所以aRc且aSc。故aR?Sc。

从而R?S是传递的。故R?S是A上的等价关系。

11、设R?A×A，则R自反 ?IA?R。证明：

??x?A，?R是自反的，?xRx。即?R，故IA?R。 ??x?A，?IA?R，??R。即xRx，故R是自反的。

12、设A是集合，R?A×A，则R是对称的?R＝R－1。证明：

???R ，?R是对称的，?yRx。即?R，故?R_1 。从而R?R-1。

反之??R-1,即?R 。?R是对称的，?yRx。即?R， R_1?R。故R=R-1。

??x，y?A，若?R ，即?R-1。? R=R-1，??R。即yRx，故R是对称的。

13、设A,B,C和D均是集合，R?A×B，S?B×C，T?C×D，则 (1) R?(S?T)=(R?S)?(R?T)； (2) R?(S?T)?(R?S)?(R?T)；证明：

（1）??R?(S?T)，则由合成关系的定义知?y?B，使得?R且?S?T。从而?R且?S或?R且?T，即?R?S或?R?T。故?（R?S）?（R?T）。从而R?(S?T)?（R?S）?（R?T）。

同理可证（R?S）?（R?T）?R?(S?T)。故R?(S?T)=（R?S）?（R?T）。

(2) ??R?(S?T)，则由合成关系的定义知?y?B，使得?R且?S?T。从而?R且?S且?T，即?R?S且?R?T。故?（R?S）?（R?T）。从而R?(S?T)?(R?S）?（R?T）。

14、设〈A,≤〉为偏序集，??B?A，若B有最大(小)元、上(下)确界，则它们是惟一的。证明：

设a,b都是B的最大元，则由最大元的定义a?b，b?a。??是A上的偏序关系，?a=b。即B如果有最大元则它是惟一的。

15、设A={1,2,3},写出下列图示关系的关系矩阵，并讨论它们的性质： 1 1 1 2 3 2 3 2 3 解：

?000????101??100??;它是反自反的、反对称的、传递的；（1）R={<2,1>,<3,1>,<2,3>};MR=??011???101???110??;它是反自反的、对称的；（2）R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>};MR=??011????100??001??;它既不是自反的、反自反的、也不是对称的、反对称的、传递的。（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的划分。其诱导的等价关系是

IA?{<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=IA?{<1,5>,<5,1>,<2,4>,<4,2>,<3,6>,<6,3>} 求R诱导的划分。解：

R诱导的划分为{{1,5},{2,4},{3,6}}。 18、A上的偏序关系?的Hasse图如下。

下列哪些关系式成立：a?b,b?a,c?e,e?f,d?f,c?f；

分别求出下列集合关于?的极大（小）元、最大（小）元、上（下）界及上（下）确界（若存在的话）： (a) A; (b) {b,d}; (c) {b,e}; (d) {b,d,e} a e f b d c 解：

(1) b?a,c?e,d?f,c?f成立；

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

?1234??1234??1234???2431????4321????1342???????? ?（1）=

?123456??123456??123456???452631????452631????452631???????? ?（2）=?123456??123456??123456???452631????635124????123456???????? ?==

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,b?I，a*b=a+b-2。试问是循环群吗？解：

是循环群。因为是无限阶的循环群，则它只有两个生成元。1和3是它的两个生成元。因为an=na-2(n-1)，故1n=n-2(n-1)=2-n。从而对任一个k?I,k=2-(2-k)=12-k，故1是的生成元。又因为1和3 关于*互为逆元，故3 也是的生成元。

23、设是群，a?G。令H={x?G|a·x=x·a}。试证：H 是G 的子群。证明：

32? c，d?H，则对?c，d?HK，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·d?H。

由于c·a=a·c,且·满足消去律，所以a ·c-1=c-1·a。故c-1?H。从而H 是G的子群。

24、证明：偶数阶群中阶为2 的元素的个数一定是奇数。证明：

设是偶数阶群，则由于群的元素中阶为1 的只有一个单位元，阶大于2 的元素是偶数个，剩下的元素中都是阶为2 的元素。故偶数阶群中阶为2 的元素一定是奇数个。 25、证明：有限群中阶大于2的元素的个数一定是偶数。证明：

设是有限群，则?a?G，有|a|=|a-1|。且当a 阶大于2时，a?a-1。故阶数大于2 的元素成对出现，从而其个数必为偶数。

26、试求中每个元素的阶。解：

0是中关于+6的单位元。则|0|=1；|1|=|5|=6，|2|=|4|=3，|3|=2。

27、设是群，a,b?G，a?e，且a4·b=b·a5。试证a·b?b·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,b?I，a*b=a+b-2。试证：为群。证明：

（1）?a,b,c?I，(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。对?a?I，a*2=a+2-2=a=2+a-2=2*a.。故e=2是I关于运算*的单位元。

（3）对?a?I，因为a*（4-a）=a+4-a-2=2=e=4-a+a-2=(4-a)*a。故4-a是a关于运算*的逆元。综上所述，为群。

29、设为半群，a?S。令Sa={ai | i?I+ }。试证是的子半群。证明：

?b，c?Sa，则存在k,l?I+，使得b=ak,c=al。从而b·c=ak·al=ak+l。因为k+l?I+，所以b·c?Sa，即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，则e?0。证明：

用反证法证明。假设e=0。

对A的任一元素a，因为e和0是A上关于二元运算*的单位元和零元，则a=a*e=a*0=0。即A的所有元素都等于0,这与已知条件|A|>1矛盾。从而假设错误。即e?0。

32、证明在元素不少于两个的群中不存在零元。证明：（用反证法证明）

设在素不少于两个的群中存在零元?。对?a?G, 由零元的定义有 a*?=?。

? 是群，?关于*消去律成立。? a=e。即G中只有一个元素，这与|G|?2矛盾。故在元素不少于两个的群中不存在零元。

33、证明在一个群中单位元是惟一的。证明：

设e1,e2都是群〈G,*〉的单位元。则e1=e1*e2=e2。所以单位元是惟一的。

34、设a是一个群〈G，*〉的生成元，则a-1也是它的生成元。证明：

?x?G，因为a是〈G，*〉的生成元，所以存在整数k，使得x=ak。

故x=((a)

k?1)

?1=((a

?1))

k?1=(a

?1)

?k。从而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，使得a?x=b。证明：

因为a-1*b∈G，且a*(a-1*b)=(a*a-1)*b=e*b=b，所以对于a,b∈G，必有x∈G，使得a?x=b。若x1,x2都满足要求。即a?x1=b且a?x2=b。故a?x1=a?x2。由于*满足消去律，故x1=x2。

从而对于a,b∈G，必有唯一的x∈G，使得a?x=b。

38、设半群中消去律成立，则是可交换半群当且仅当?a,b?S，（a·b）2=a2·b2。证明：

??a,b?S，（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,b?S，因为（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)·b。从而a·b=b·a。故·满足交换律。 39、设群除单位元外每个元素的阶均为2，则是交换群。

证明：

对任一a?G，由已知可得a*a=e，即a-1=a。

对任一a,b?G，因为a*b=(a*b)-1=b-1*a-1=b*a，所以运算*满足交换律。从而＜G,*＞是交换群。

40、设*是集合A上可结合的二元运算，且?a,b?A,若a*b=b*a，则a=b。试证明：（1）?a?A,a*a=a，即a是等幂元；（2） ?a,b?A,a*b*a=a; （3） ?a,b,c?A,a*b*c=a*c。证明：

（1）?a?A,记b=a*a。因为*是可结合的，故有b*a=(a*a)*a=a*(a*a)=a*b。由已知条件可得a=a*a。（2）?a,b?A,因为由（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,c?A,（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:G?G,a?a-1。证明：f是G的自同构?G是交换群。证明：

? 设f 是G的自同构。对?a，b?G，a·b=(b-1·a-1)-1=(f(b) ·f(a))-1=(f(b·a))-1=((b·a)-1)-1=b·a。故

运算·满足交换律，即G是可交换群。

?因为当a?b时，a-1?b-1，即f(a)?f(b)，故f是G到G中的一个单一函数。又对?a?G，有f(a-1)=(a-1)-1=a。

故f是G到G上的满函数。从而f是G到G上的自同构。

对?a，b?G，因为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。因为H?H1=?且H?H1=G，H?H2=?且H?H2=G，故H1=G-H=H2。

对?a?G，若a?H，则aH=H,Ha=H。否则因为a?G-H，故aH?H,Ha?H。从而aH=Ha=G-H。故H是G的不变子群。 43、设H和K都是G的不变子群。证明：H?K也是G 的不变子群。

证明：

因为H和K都是G的不变子群，所以H?K是G 的子群。对?a?G，h?H?K，有a·h·a-1?a·H·a-1，·h·a-1?a·K·a-1。因为H和K都是G的不变子群，所以a·h·a-1?H且a·h·a-1?K。从而a·h·a-1?H?K。故H?K是G 的不变子群。

44、设群G的中心为C（G）={a?G|?x?G,a·x=x·a}。证明C（G）是G的不变子群。证明：

先证C（G）是G的子群。

?a,b?C（G），对?x?G,有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-1?C（G）。故C（G）是G 的子群。再证C（G）是G的不变子群。

?h?C(G)，对?a?G，记b=a·h·a-1。下证b?C(G)。因为h?C(G)，所以b=(a·h) ·a-1=（h·a）·a-1=h·(a·a-1)=h?C(G)。

故C（G）是G的不变子群。

45、设是没有非平凡子群的有限群。试证：G是平凡群或质数阶的循环群。证明：

若G是平凡群，则结论显然成立。

否则设的阶为n。任取a?G且a?e,记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

综上所述，G是平凡群或质数阶的循环群。

46、设H和K都是G 的有限子群，且|H|与|K|互质。试证：H?K={e}。证明：用反证法证明。

若H?K?{e}。则H?K是一个元素个数大于1的有限集。先证H?K也是G的子群，从而也是H和K的子群。

?a,b? H?K,则a,b? H且a,b?K。因为H和K都是G的子群，故 a·b,a-1? H且a·b,a-1? K。从而a·b?

H?K,a-1? H?K。故H?K是G的子群，从而也是H和K的子群。由拉格朗日定理可知，|H?K|是|H|和|K|的因子，这与已知矛盾。 47、素数阶循环群的每个非单位元都是生成元。证明：

设是p阶循环群，p是素数。

对G中任一非单位元a。设a的阶为k,则k?1。

由拉格朗日定理，k是p的正整因子。因为p是素数，故k=p。即a的阶就是p，即群G的阶。故a是G的生成元。

48、若是可交换独异点，T为S中所有等幂元的集合，则是的子独异点。证明：

? e?e=e，?e?T，即T是S的非空子集。

? a,b?T,? 是可交换独异点, ?(a?b)?(a?b)=((a?b)?a)?b

=(a?(b?a))?b=（a?(a?b)）?b =((a?a)?b)?b=(a?a)?(b?b) =a?b,即a?b?T。

故是的子独异点。

n49、设是群，且a∈G的阶为n，k∈I，则|ak|＝(k,n)，其中(k,n)为k和n的最大公因子。

证明：

nk记p=(k,n),q=(k,n),｜ak｜＝m。由n和p的定义，显然有(ak)p=e。故m?p且m|p。

又由于akm=e，所以由定理5.2.5知，n|km。即p|qm。但p和q 互质，故p|m。

n由于p和m都是正整数，所以p=m。即｜ak｜＝(k,n)。

50、设是有限群，|G|＝n，则?a∈G，|a|?n。证明：

?a?G，由封闭性及|G|=n可知a,a2,…,an,an+1中必有相同的元素，不妨设为ak=am,k

而|a|?m-k?n。

51、设G＝(a)，若G为无限群，则G只有两个生成元a和a-1；证明：

?b?G＝(a)，则?n?I,使b=an。故b=(a-n)-1=(a-1)-n,从而a-1也是G的生成元。

若c是G的生成元，则?k,m?I，分别满足c=ak和a=cm。从而c= (cm)k= cmk。若km?1，则由消去律可知c的阶是有限的，这与|G|无限矛盾。从而km=1，即k=1,m=1或k=-1,m=-1。故c=a或c=a-1。从而G只有两个生成元a和a-1。

52、设G＝(a)，{e}?H?G，am是H中a 的最小正幂，则（1） H＝(am)；

（2）若G为无限群，则H也是无限群；证明：

（1）?b?H, ?k?I, 使得b=ak。令k=mq+r, 0?r

由于0?r

（2）因为{e}?H，故H的生成元为am （m?0）。因为G是无限群，所以a的阶是无限的，从而am的阶也是无限的，故H也是无限群。

53、设G＝(a)，|G|＝n，则对于n 的每一正因子d，有且仅有一个d阶子群。因此n阶循环群的子群的个数恰为 n的正因子数。证明：

n?对n 的每一正因子d，令k=d,b=ak, H={e,b,b2,…,bd-1}。

因为|a|=n,所以bd=(ak)d=akd=an=e且|b|=d。从而H中的元素是两两不同的，易证H?G。故|H|=d。所以是G的一个d阶子群。

n设H1是G的任一d阶子群。则由定理5.4.4知，H1＝(am)，其中am是H1中a 的最小正幂，且|H|=m。因为|H|=d，n所以m=d=k，即H=H1。从而H是G的惟一d阶子群。

?设H是G的惟一的d阶子群。若d=1 ,则结论显然成立。否则H＝(am)，其中am是H中a 的最小正幂。由定理5.4.4

n知，d=m。故d是n的一个正因子。

54、设h是从群

（2） ?a?G1，h(a-1)=h(a)-1；（3）若H?G1，则h(H)?G2；

（4）若h为单一同态，则?a?G1，|h(a)|=|a|。证明：

(1) 因为h(e1)?h(e1)=h(e1?e1)= h(e1)= e2?h(e1),所以h(e1)=e2。 (2) ?a∈G1，h(a)?h(a-1)=h(a?a-1)= h(e1)= e2, h(a-1)?h(a)=h(a-1?a)= h(e1)= e2,故h(a-1)=h(a)-1。

(3) ?c,d∈h(H),?a,b∈H，使得c=h(a),d=h(b)。故c?d=h(a)?h(b) =h(a

?>到的群同态，G1和G2的单位元分别为e1和e2，则

?b)。因为H?G，所以a?b ∈H ，故c?d∈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，?a?G，则|a|=m。令H={e,a,a2,…,am-1}。

则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，故a-1=a,b-1=b,c-1=c。从而a?b?a, a?b?b, a?b?e,故a?b=c。同理可得a?c=c?a=b, c?b=b?c=a, b?a=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的子群。若A?B=G，则A=G或B=G。证明：用反证法证明。

若A?G且B?G，则有a?A,a?B且b?B,b?A。因为A，B都是G的子群，故a,b?G，从而a*b?G。因为a?A,所以a

?1?A。若a*b?A,则b= a?1*(a*b)?A，这与a?B矛盾。从而a*b?A。

同理可证a*b?B。

综合可得a*b?A?B=G，这与已知矛盾。从而假设错误，得证A=G或B=G。 59、设e是奇数阶交换群的单位元，则G的所有元素之积为e。证明：

设G=<{e,a1,a2,…,a2n},*>，n为正整数。

因为G的阶数为奇数2n+1，所以由拉格朗日定理知G中不存在2 阶元素，即除了单位元e以外，G的所有元素的阶都大于2。故对G中的任一非单位元a，它的逆元a

?1不是它本身，且G中不同的元素有不同的逆元。

由此可见，G中的2n个非单位元构成互为逆元的n对元素。因为G 是交换群，故G的所有元素之积可变成单位元和n对互为逆元的元素之积的积，从而结果为e。

60、设S=Q?Q，Q为有理数集合，*为S上的二元运算：对任意(a,b)，(c,d)?S,有 (a,b)*(c,d)=(ac,ad+b),

求出S关于二元运算*的单位元，以及当a?0时，(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,y?Q都成立。解得a=1,b=0。所以S关于*的单位元为(1,0)。

当a?0时，设(a,b)关于*的逆元为(c,d)。根据逆元的定义，有 (a,b)*(c,d)= (ac,ad+b)=(1,0) (c,d)*(a,b)= (ac,cb+d)=(1,0)

1b即ac=1,ad+b=0,cb+d=0。解得c=a,d=-a。 1b 所以(a,b)关于*的逆元为(a,-a)。

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, 使得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，a?H?a-1?H；（3） ?a∈G，a-1?H?a?H；

（4） ?a∈G，?h∈G，a?h?a-1?H。证明：

(1)?(2) ?a∈G，则对h∈H,令h1=a?h?a-1，因为a?h ? a?H且H?a=a?H，所以?h2∈H，使得a?h=h2?a。故h1=（h2?a）?a-1=h2?H。故 a?H?a-1?H。

(2)?(3) ?a∈G，对h∈H,令h1=a-1?h?a，则（h1）-1= a?h-1?a-1。因为h-1∈H，所以（h1）-1= a?h-1?a-1∈a?H?a-1。由（2）可知（h1）-1∈H,从而h1?H。故a-1?H?a?H 。 (3)?(4) 类似于（2）?(3)的证明。

(4)?(1) ?a∈G，对?b∈a?H，则?h∈H，使得b=a?h。故b=(a?h) ?(a-1?a)=(a?h?a-1)?a。由于a?h?a-1

∈H，所以b∈H?a。即a?H?H?a。

反之对?b∈H?a，则?h∈H，使得b=h?a。故b=(a?a-1) ?(h?a)=a?(a-1?h?a)=a?(a-1?h?(a-1)-1)。由于a-1?h?(a-1)-1∈H，所以b∈a?H。即H?a?a?H。即H?a=a?H。从而H是G的不变子群。

63、在半群中，若对?a,b?G，方程a*x=b 和y*a=b都有惟一解，则是一个群。证明：

任意取定a?G，记方程a*x=a的惟一解为eR。即a*eR=a。下证eR为关于运算*的右单位元。对?b?G，记方程y*a=b的惟一解为y。

?是半群，?运算*满足结合律。 ?b*eR=(y*a)*eR=y*(a*eR)=y*a=b。

类似地，记方程y*a=a的唯一解为eL。即eL*a=a。下证eL为关于运算*的左单位元。对?b?G，记方程a*x=b的惟一解为x。

?是半群，?运算*满足结合律。 ?eL*b=eL*(a*x)=(eL*a)*x=a*x=b。

从而在半群中, 关于运算*存在单位元，记为e。现证G中每个元素关于运算*存在逆元。

对?b?G，记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的子群。?c?HK，则c-1?HK，故存在a?H,b?K ,使得c-1=a·b。因为c=（a·b）-1=b-1·a-1。因为H

和K都是G 的子群，所以a-1?H,b-1?K ，即c?KH。从而HK?KH。 ?c?KH，则存在a?H,b?K ,使得c=b·a。因为c=（a-1·b-1）-1。因为H和K都是G 的子群，所以a-1?H,b-1?K ，即a-1·b-1?HK。因为HK是G的子群，所以c=（a-1·b-1）-1?HK。从而KH?HK。故HK=KH。

?HK=KH。对?c，d?HK，有a1,a2?H,b1,b2?K ,使得c=a1·b1 ,d=a2·b2。则

c·d=( a1·b1)·(a2·b2)=(( a1·b1)·a2)·b2=( a1·(b1·a2))·b2。因为b1·a2?KH=KH，所以存在a3?H,b3?K ,使得b1·a2 =a3·b3。从而c·d=( a1·（b1·a2）·b2=(a1·（a3·b3）)·b2=(a1·a3)·(b3·b2)。因为H和K都是G的子群，故a1·a3?H, b3·b2?K。从而c·d?HK。

又c-1=(a1·b1)-1=b-11·a-11。因为H和K都是G的子群，故a-11?H, b-11?K。从而c-1?KH。因为HK=KH，所以c-1?HK。

综上所述，HK是G的子群。

65、设H和K都是G的不变子群。证明：HK也是G 的不变子群。证明：

先证HK是G 的子群。

对?a?HK，有hH，k?K，使得a=h·k。因为a=h·k=(h·k·h-1)·h，且K是G 的不变子群，所以h·k·h-1K。故a?KH。从而HK?KH。同理可证，KH?HK。

故HK=KH。从而HK是G的子群。下证HK是G的不变子群。

对?a?G，b?HK，有hH，k?K，使得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-1?H且a·k·a-1?K。从而a·b·a-1?HK。故HK是G 的不变子群。 66、设为群，a,b,c?G。若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两边同时右乘ba*b=(c*b*a)*b=(c*b)*a*b=(c*b)*a*b

32n?2n?3

nn?1n?1???，再由a*b=c*b*a得

n?2n?3

=(c*b)*(a*b)*b

2n?2=(c*b)*(c*b*a)*b

=(c*b)*(a*b)*b=…=(c*b)*a,

nn?3

=(c*b)*(c*b*a)*b

再由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，两边同时左乘aa*b=a= a= a

m?2m?3mm?1m?1nnnnnn，再由a*b=b*a*c得

*(b*a*c)= a

2m?2* (a*b)*(a*c)= a

2m?2*(b*a*c)*(a*c)

2*b*(a*c)= a

3m?3*(a*b)*(a*c)= a

mm?3*(b*a*c)*(a*c)

*b*(a*c)=…=b*(a*c),

再由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)。

mmmmmm

（格与布尔代数）

67、当n分别是24，36，110时，是布尔代数吗？若是，则求出其原子集。解：

因为|S24|=8，|S36|=9，|S110|=8，故不是布尔代数。在中12没有补元，故它也不是布尔代数。是布尔代数，其原子集为{2,5,11}。 68、设L是有界格，且|L|>1。证明：0?1。证明：用反证法证明。

设0=1。则任取a?L，则由于L是有界格，故a?1且0?a。即0?a?1。因为0=1且?是L上的偏序关系，所以a=0。这与已知|L|>1矛盾。

69、设(L,≤)是格，若a,b,c?L，a≤b≤c，则 a?b=b⊙c , (a⊙b)?(b⊙c)=(a?b)⊙(a?c) 证明：

因为a?b?c，所以a?b=a，a?b=b=b，且b=b?c，以c=b?c。从而a?b=b?c。 (a?b)?(b?c)=a?(b?c)=a?(a?b)=(a?a) ?b=a?b=b， (a?b)?(a?c)=(b?c)?(a?c)=b?(c?(a?c))=b?c=b。 70、在布尔代数中，证明恒等式a?(a??b)=a?b 证明：

a?(a??b)=(a?a?)?(a?b)=1?(a?b)=a?b

71、设是格，a1,a2,…,an?L。试证：a1?a2?…?an= a1?a2?…?an当且仅当a1=a2=…=an。证明：

? 显然是成立的。

? 对任一k=1,2,..,n，a1?a2?…?an?ak，ak?a1?a2?…?an。

因为a1?a2?…?an= a1?a2?…?an，且?是L上的偏序关系，故ak=a1?a2?…?an。从而a1=a2=…=an。 72、在布尔代数中，证明恒等式(a?c)?(a??b)?(b?c)=(a?c)?(a??b) 证明：

((a?c)?(a??b))?(b?c)=((a?c)?(b?c))?((a??b)?(b?c)) =(a?b?c)?(a??b?c)=(a?a?)?b?c=1?b?c=b?c, 故 b?c?(a?c)?(a??b)，从而

(a?c)?(a??b)?(b?c)=(a?c)?(a??b)。 73、在布尔代数中，证明恒等式(a?b)?(a??c)?(b?证明：

(a?b)?(a??c)?(b?

?c)=(a?b)?c

?c)=(a?b)?((a??b?)?c)

=(a?b)?((a?b)??c)=(a?b)?c。

74、设是格，a,b,c,d?L。试证：若a?b且c?d，则 a?c?b?d 证明：

因为a?b，c?d，所以a=a?b,c=c?d。从而

(a?c)?(b?d)=((a?c)?b)?d=(b?(a?c))?d=((b?a)?c)?d =a?(c?d)=a?c，所以a?c?b?d。

75、当n分别是10,45时，画出的哈斯图。解：

10 ? ? 45 15? 9? ? 5 ?2 5? 3? 1? ? 1

76、在布尔代数中，证明恒等式

(a?b?)?(b?c?)?(c?a?)=(a??b)?(b??c)?(c??a) 证明：

(a?b?)?(b?c?)?(c?a?)

=(a?b?c)?(a?b?a?)?(a?c??a?)?(a?c??c)?(b??b?c)

?(b??c??c)?(b??c??a?)?(b??b?a?)=(a?b?c)?(b??c??a?)，

(a??b)?(b??c)?(c??a) =(a??b??c?)?(a??b??a)?(a??c?c?)?(a??c?a)?(b?b??c?)

?(b?b??a)?(b?c?c?)?(b?c?a)=(a?b?c)?(a??b??c?)，

故(a?b?)?(b?c?)?(c?a?)=(a??b)?(b??c)?(c??a)。 77、设是格，a,b?L，且a≤b，记 I[a,b]={x?L|a≤x≤b}

则是的子格。证明：

?x,y?I[a,b],a≤x≤b且a≤y≤b。由定理6.1.1有a≤x?y≤b且a≤x?y≤b。从而x?y?I[a,b]且x?y?I[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个。证明：

若≤是L上的全序关系，则它一定是良序关系(因为任一有限的全序集一定是良序集)。若设L={a,b,c,d}，则L的四个元素满足：a≤b≤c≤d。

若≤不是L上的全序关系，则L中一定存在两个元素（不妨设为b,c），b≤c和c≤b都不成立。因此b不可能相等，也不可能是b和c。不妨记a=b≤b,a≤c,a≤d,b≤d,c≤d。

d? ?d

c? b? ?c

b? a ?

80、设是有界格，?是A上的全序关系。若|A|＞2，则?a?A-{0,1}，a无补元。证明：

用反证法证明。

若? a?A-{0,1}，a有补元a'。即a?a'=1，a则a= a

?c和b?c既

?c,d=b?c。故的四个元素a,b,c,d满足a≤a,b≤b,c≤c,d≤d,a

?a'=0。因为?是A上的全序关系，所以a?a'或a'?a。若a?a'，

?a'=0。若a'?a，则a= a?a'=1。无论如何，这与a?0,a?1矛盾。 ?,?>是模格??a,b,c?L，有

81、格

?(a?c))=(a?b)?(a?c)

证明：

? ?a,b,c?L，记d= a?c。所以a?d,从而

a?(b

?(a?c))= a?(b?d)= (a?b)?d=(a?b)?(a?c)。 ?c= (a?b)?（a?c）= a?(b?(a?c))= a?(b?c)。

?,?>是分配格， a,b,c?L。若(a?b)＝(a?c)且(a?b)＝(a?c)，则b＝c。

? ?a,b,c?L，若a?c，则c= a?c。所以

(a?b)

82、设

由吸收律、分配律和交换律有 b=b?(a

?b)＝b?(a?c)=（b?a）?（b?c） ?(b?c)=c?(a?b)= c?(a?c)＝c。

=(a?c)

83、证明：在有补分配格中，每个元素的补元一定惟一。证明：

设是一个有补分配格。?a?L,设b和c都是a 的补元，即 a?b=1,a?c=1,a

?b=0,a?c=0。

由吸收律、分配律和交换律有 b= b?0＝b?(ac= c?0=c?(a

?c)=(b?a)?(b?c)=1?(b?c)=b?c,

?b)＝(c?a)?(c?b)=1?(c?b)=c?b。

故b=c。从而每个元素的补元是惟一的。

84、设是格，则L是分配格当且仅当?a,b,c?L，有 (a?b)?c?a?(b?c) 证明：

?设L是分配格。对?a,b,c?L，有

(a?b)?c=(a?c)?(b?c)

因为a?c?a，故(a?c)?(b?c) ?a?(b?c)。从而 (a?b)?c?a?(b?c)

?对?a,b,c?L，因为a?c?a,a?c? c,a? a?b,b?c? c,b?c? b,b? a?b,所以a?c? a?b，a?c? c，b?c?

c,b?c? a?b，

从而(a?c)?(b?c)?(a?b)?c。又由已知有

(a?b)?c=((b?a)?c)?c?(b?(a?c))?c=((a?c)?b)?c?(a?c)?(b?c)。故(a?b)?c=((a?c)?b)?c?(a?c)?(b?c)。

从而L是分配格。

85、设是一布尔代数，则是一个交换群，其中＋定义为 a+b=(a⊙b′)?(a′⊙b)。证明：

?a,b?S，?＜S,?,⊙,′,0,1>是一布尔代数，

? a+b=(a⊙b′)?(a′⊙b)= (b⊙a′)?(b′⊙a)=b+a。 ? 运算+满足交换律。

?a,b,c?S，(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)⊙(a?b′)⊙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

? 运算+满足结合律。

?a?S，?＜S,?,⊙,′,0,1>是一布尔代数，

? a+0=(a⊙0′)?(a′⊙0)= (a⊙1)?0=a。 ? 0关于运算+的单位元。

?a?S，?＜S,?,⊙,′,0,1>是一布尔代数，

? a+a=(a⊙a′)?(a′⊙a)=0?0=0。 ? a是a关于运算+的逆元。

综上所述，是一个交换群。

86、设是一布尔代数，则 R={ | a?b=b}是S上的偏序关系。证明：

?a?S，??满足等幂律，? a?a=a，故aRa。即R是自反的。

?a,b?S，若aRb且bRa,? ?满足交换律，? b=a?b=b?a=a。即R是反对称的。 ?a,b,c?S，若aRb且bRc,? ?满足结合律，? c=c?b=c?（b?a）

=(c?b)?a=c?a,故aRc。即R是反对称的。综上所述，R={ | a?b=b}是S上的偏序关系。

87、设是一布尔代数，则关系?={ | a⊙b=a}是S上的偏序关系。证明：

?a?S，因为⊙满足等幂律，所以a⊙a=a，故a?a。即?是自反的。

?a,b?S，若a?b且b?a,因为⊙满足交换律，所以a=a⊙b=b⊙a=b。即?是反对称的。

?a,b,c?S，若a?b且b?c,因为⊙满足结合律，因为a=a⊙b=a⊙(b⊙c)=(a⊙b)⊙c=a⊙c,故a?c。即?是反对称的。

综上所述，?={ | a⊙b=a}是S上的偏序关系。

（图论部分）

88、证明在有n个结点的树中，其结点度数之和是2n-2。证明：

设T=是任一棵树，则|V|=n，且|E|=n-1。由欧拉握手定理，树中所有结点的度数之和等于2|E|. 从而结点度数之和是2n-2。

88、任一图中度数为奇数的结点是偶数个。证明：

设G=〈V,E〉是任一图。设|V|=n。

由欧拉握手定理可得 v?Vdeg(v)=2|E|可得，图中所有结点度数之和是偶数。显然所有偶数度结点的度数之和仍为偶数，从而所有奇数度结点的度数之和也是偶数。因此，图中度数为奇数的结点一定为偶数个。

89、连通无向图G的任何边一定是G的某棵生成树的弦。这个断言对吗？若是对的请证明之，否则请举例说明。证明：不对。

反例如下：若G 本身是一棵树时，则G的每一条边都不可能是G的任一棵生成树（实际上只有惟一一棵）的弦。 90、设T=是一棵树，若|V|>1，则T中至少存在两片树叶。证明：

（用反证法证明）设|V|=n。

因为T=〈V,E〉是一棵树，所以|E|=n-1。由欧拉握手定理可得 v?Vdeg(v)=2|E|=2n-2。

假设T中最多只有1片树叶，则v?Vdeg(v)?2(n-1)+1>2n-2。得出矛盾。

91、画一个使它分别满足：

???

有欧拉回路和哈密尔顿回路；有欧拉回路，但无条哈密尔顿回路；无欧拉回路，但有哈密尔顿回路；既无欧拉回路，又无哈密尔顿回路。解

? ? ? ? ?

? ? ? ?

? ? ? ? ? ?

? ? ? ?

92、设无向图G=，|E|=12。已知有6个3度顶点，其他顶点的度数均小于3。问G中至少有多少个顶点？解：

设G中度数小于3的顶点有k个，由欧拉握手定理

24=v?V?deg(v)

知，度数小于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=v?V?deg(v)=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。

由欧拉握手定理可得 v?Vdeg(v)=2|E|=2n-2。

因为G连通，所以?v?V，deg(v)?1。假设G中没有1片树叶，则v?Vdeg(v)?2n>2n-2。

得出矛盾。

95、若n阶连通图中恰有n-1 条边，则图中至少有一个结点度数为1。证明：

（用反证法证明）设G=有n-1条边且|V|=n。由欧拉握手定理可得 v?Vdeg(v)=2|E|=2n-2。

因为G是连通图，所以G中任一结点的度数都大于等于1。

假设G中不存在度数为1 的结点，则G中任一结点的度数都大于等于2.故v?Vdeg(v)?2(n-1)+1>2n-2, 得出矛盾。

96、若G有n个结点，m条边，f个面，且每个面至少由k(k?3)条边围成，则 m?k(ｎ－2)／(ｋ－2)。证明：

设连通简单无向平面图G=〈V,E,F〉，则|V|=n,|E|=m,|F|=p。由已知对任一f?F, deg(f)?k。

由公式f?Fdeg(f)=2|E|可得，2|E|?k|F|。

???2再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+k|E|?2。

即k(n-2)?(k-2)m。所以m?k(ｎ－2)／(ｋ－2)。

97、设G=是连通的简单平面图，|V|=n?3，面数为k,则k?2n-4。证明：

记|E|=m。因为G=是连通的简单平面图，故每个面的度数都不小于3。从而由公式f?Fdeg(f)=2|E|可得 3k?2m

再由欧拉公式|V|-|E|+|F|=2有 m=n+k-2

?3及 2k?n+k-2

故 k?2n-4。

98、证明对于连通无向简单平面图，当边数e＜30时，必存在度数≤4的顶点。证明：

若结点个数小于等于3时，结论显然成立。当结点多于3 个时，用反证法证明。记|V|=n,|E|=m,|F|=k。

假设图中所有结点的度数都大于等于5。

由欧拉握手定理得v?Vdeg(v)=2|E|得 5n?2m。又因为G=〈V,E,F〉是一个连通简单无向平面图，所以对每个面f,deg(f)?3。

由公式f?Fdeg(f)=2|E|可得，2m?3k。

??221再由欧拉公式|V|-|E|+|F|=2可得2?5m-m+3m=15m

从而30?m,这与已知矛盾。

99、在一个连通简单无向平面图G=〈V，E，F〉中若|V|?3，则 |E|?3|V|－6。证明：

? |V|?3，且G=〈V，E，F〉是一个连通简单无向平面图， ? d(f) ?3，?f?F。

由公式f?Fdeg (f)=2|E|可得，2|E|?3|F|。

?2再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+3|E|?2。 ?|E|?3|V|－6。

100、给定连通简单平面图G=，且|V|=6, |E|=12, 则对于任意f?F, d(f)=3。证明：

因为|V|=6?3，且G=〈V,E,F〉是一个连通简单无向平面图，所以对任一f?F，deg(f)?3。由欧拉公式|V|-|E|+|F|=2可得|F|=8。

再由公式f?Fdeg(f)=2|E|，f?Fdeg(f)=24。

因为对任一f?F，deg(f)?3，故要使上述等式成立，对任一f?F，deg(f)=3。

101、设G=是n个顶点的无向图(n>2)，若对任意u,v?V，有d(u)+d(v)?n，则G是连通图。证明：用反证法证明。

若G 不连通，则它可分成两个独立的子图G1和G2，其中|V(G1)|+|V(G2)|-2=n ，且G1中的任一个顶点至多只和G1中的顶点邻接，而G2中的任一顶点至多只和G2中的顶点邻接。任取u?V(G1),v?V(G2),则 d(u)?|V(G1)|-1, d(v)?|V(G2)|-1。

故d(u)+d(v) ?(|V(G1)|-1)+(|V(G2)|-1)?|V(G1)|+|V(G2)|-2

本文来源：https://www.bwwdw.com/article/041w.html

相关文章：

正在阅读：

《离散数学》练习题和参考答案01-30

高二物理电场知识点整理06-06

南开19春学期(1709、1803、1809、1903)《政治经济学》在线作业11-01

企业战略解析联想的外向型国际化策略04-17

2011版小学数学新课程标准考试试卷（测试卷含答案）-(1)10-06

2011高考历史一轮复习教案：《苏联的社会主义建设》(新人教必修2)05-11

上一篇：GSM1800基站与GSM900基站共用BSC的研究报告 - 图文下一篇：200万高清卡口+超速线圈技术方案 - 图文