《离散数学》题库及答案

《离散数学》题库答案

一、选择或填空 （数理逻辑部分）

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、判断下列语句是不是命题。若是，给出命题的真值。( (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。

1

)，约束)

(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))在哪个个体域中为真?( )

2

(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)

3

17、在0（ ）?之间写上正确的符号。

(1) = (2) ? (3) ? (4) ?

答：(4)

18、若集合S的基数|S|=5，则S的幂集的基数|P(S)|=（ ）。

答：32

19、设P={x|(x+1)2?4且x?R},Q={x|5?x2+16且x?R},则下列命题哪个正确（ ）

(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）

4

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成立。

答：（2）

27、Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理正确：

(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｝，

5

求(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的关系矩阵。

6

?1?0?0答：R的关系矩阵=??0??0??000?00??100000??00?? 000100 R?1的关系矩阵=???10????000000??00?00??36、集合A={1,2,…,10}上的关系R={|x+y=10,x,y?A}，则R 的性质为（ ）。

(1) 自反的 (2) 对称的 (3) 传递的，对称的 (4) 传递的

答：（2）

（代数结构部分）

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=( )；

7

(2) 若a,b,x∈G，a?x=a?b，则x=( )。

答： （1） a?1?b （2） b

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

答： 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=( )。

答：（1） b?a?1 (2) b

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

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

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

答：1，单位元，0

48、在一个群〈G,*〉中，若G中的元素a的阶是k，则a-1的阶是( )。

8

答：k

49、在自然数集N上，下列哪种运算是可结合的？（ ） (1) a*b=a-b (2) a*b=max{a,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)

（格与布尔代数部分）

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

(3) （{2,3,4,6,12},|（整除关系）） (4) (P(A),?)

答：(4)

53、有限布尔代数的元素的个数一定等于（ ）。

(1) 偶数 (2) 奇数 (3) 4的倍数 (4) 2的正整数次幂

答：(4)

9

（图论部分）

54、设G是一个哈密尔顿图，则G一定是( )。 (1) 欧拉图 (2) 树 (3) 平面图 (4) 连通图

答：(4)

55、下面给出的集合中，哪一个是前缀码？( ) (1) {0，10，110，101111} (2) {01，001，000，1} (3) {b，c，aa，ab，aba} (4) {1，11，101，001，0011}

答：（2）

56、一个图的哈密尔顿路是一条通过图中( )的路。

答：所有结点一次且恰好一次

57、在有向图中，结点v的出度deg+(v)表示( )，入度deg-(v)表示( 答：以v为起点的边的条数， 以v为终点的边的条数

58、设G是一棵树，则G 的生成树有( )棵。 (1) 0 (2) 1 (3) 2 (4) 不能确定

答：1

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

n(n?1)2, n-1 60、一棵无向树的顶点数n与边数m关系是( )。

答：m=n-1

10

)。

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，树

11

)，

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是一个连通且( )图。

答：无简单回路

71、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。

(1) 10 (2) 4 (3) 8 (4) 16

答：（4）

72、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。

(1) 10 (2) 4 (3) 8 (4) 12

答：(4)

73、设图G=，V={a，b，c，d，e}，E={,,,,},则G是有向图还是无向图？

答：有向图

74、任一有向图中，度数为奇数的结点有( )个。

答：偶数

75、具有6 个顶点，12条边的连通简单平面图中，每个面都是由( )条边围成？

12

(1) 2 (2) 4 (3) 3 (4) 5

答：（3）

76、在有n个顶点的连通图中，其边数（ ）。

(1) 最多有n-1条 (2) 至少有n-1 条 (3) 最多有n条 (4) 至少有n 条

答：（2）

77、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（ ）。

(1) 5 (2) 7 (3) 8 (4) 9

答：（4）

78、若一棵完全二元（叉）树有2n-1个顶点，则它（ ）片树叶。

(1) n (2) 2n (3) n-1 (4) 2

答：（1）

79、下列哪一种图不一定是树（ ）。

(1) 无简单回路的连通图 (2) 有n个顶点n-1条边的连通图 (3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图

答：（3）

80、连通图G是一棵树当且仅当G中（ ）。 (1) 有些边是割边 (2) 每条边都是割边

(3) 所有边都不是割边 (4) 图中存在一条欧拉路径

13

答：（2）

（数理逻辑部分）

二、求下列各公式的主析取范式和主合取范式： 1、(P→Q)?R

解：(P→Q)?R?(?P?Q )?R

?(?P?R)?(Q?R) （析取范式）

?(?P?(Q??Q)?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)

?(P?Q??R)?( P??Q??R)（原公式否定的主析取范式）

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

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

2、(P?R)?(Q?R)??P

解： (P?R)?(Q?R)??P（析取范式）

?(P?(Q??Q)?R)?((P??P)?Q?R)?(?P?(Q??Q)?(R??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) (主析取范式)

14

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

（原公式否定的主析取范式） ?(P??Q??R)?(P?Q??R）

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

3、(?P→Q)?(R?P)

解：(?P→Q)?(R?P)

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

?(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))

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

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

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

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

4、Q→(P??R)

解：Q→(P??R)

??Q?P??R（主合取范式） ?（Q→(P??R)）

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

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

Q→(P??R)

15

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

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

5、P→(P?(Q→P))

解：P→(P?(Q→P))

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

?(?P??Q)?(?P?Q)?(P??Q)?(P?Q)（主析取范式）

6、?(P→Q)?(R?P)

解： ?(P→Q)?(R?P)??(?P?Q)?(R?P)

?(P??Q)?(R?P)（析取范式） ?(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))?(P?Q??R)?(?P?Q?R)?(?P??Q?R)

? (?P??Q??R)?(?P?Q??R)（原公式否定的主析取范式）

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

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

7、P?(P→Q)

解：P?(P→Q)?P?(?P?Q)?(P??P)?Q

?T(主合取范式)

?(?P??Q)?(?P?Q)?(P??Q)?(P?Q)（主析取范式）

16

8、(R→Q)?P

解：(R→Q)?P?(?R?Q )?P

? (?R?P)?(Q?P) （析取范式） ? (?R?(Q??Q)?P)?((?R?R)?Q?P)

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

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

?(?P?Q?R)?(?P??Q?R)（原公式否定的主析取范式）

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

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

9、P→Q

解：P→Q??P?Q（主合取范式）

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

?(?P?Q)?(?P??Q)?(?P?Q)?(P?Q) ?(?P?Q)?(?P??Q)?(P?Q)（主析取范式）

10、 P??Q

解： P??Q （主合取范式）

?(P?(?Q?Q))?((?P?P)??Q） ?(P??Q)?(P?Q)?(?P??Q)?(P??Q） ?(P??Q)?(P?Q)?(?P??Q)（主析取范式）

11、P?Q

17

解：P?Q（主析取范式）?(P?(Q??Q))?((P??P)?Q)

?(P??Q)?(P?Q)?(P?Q)?(?P?Q) ?(P??Q)?(P?Q)?(?P?Q)（主合取范式）

12、（P?R）?Q

解：（P?R）?Q

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

?(?P?Q)?(?R?Q)（合取范式） ?(?P?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)（主合取范式） ?（P?R）?Q

?(?P??Q?R)?(?P??Q??R)?(P?Q?R)?(P??Q?R)?(P??Q??R) （原公式否定的主析取范式）

（P?R）?Q

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

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

13、（P?Q）?R

解：（P?Q）?R

??(?P?Q)?R

18

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

?(P??Q?(R??R))?((P??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?R)

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

（P?Q）?R

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

?(P?(Q??Q)?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)(主合取范式)

14、(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??R))?(?P?(Q??Q)?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??R)?(?P??Q?R)?(P??Q?R)

19

?(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)(主析取范式)

15、P?(?P?(Q?(?Q?R)))

解：P?(?P?(Q?(?Q?R)))

? P?(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?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)(主合取范式)

20

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关于运算*的

46

单位元。

（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、证明在元素不少于两个的群中不存在零元。

47

证明：（用反证法证明）

设在素不少于两个的群中存在零元?。对?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=((ak)?1)?1=((a?1)k)?1=(a?1)?k。从而a-1也是〈G，*〉的生成元。

35、在一个偶数阶群中一定存在一个2阶元素。

证明：

群中的每一个元素的阶均不为0 且单位元是其中惟一的阶为1的元素。因为任一阶大于2 的元素和它的逆元的阶相等。且当一个元素的阶大于2 时，其逆元和它本身不相等。故阶大于2 的元素是成对的。从而阶为1的元素与阶大于2 的元素个数之和是奇数。

因为该群的阶是偶数，从而它一定有阶为2 的元素。

36、代数系统是一个群，则G除单位元以外无其它等幂元。

48

证明：

设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）2=(a·b)·(a·b)=((a·b)·a)·b ??a,b?S，

=(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，则是交换群。

证明：

49

对任一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。

50

(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 前提 (3) ?Q （1），（2） (4) P→Q 前提 (5) ?P （3），（4） (6) ?S?P 前提 (7) ?S （5），（6）

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

证明：

(1) A 前提

21

(2) A→(B→C) 前提 (3) B→C （1），（2）

(4) B 附加前提 (5) C （3），（4） (6) C→(?D?E) 前提 (7) ?D?E （5），（6） (8) ?F→(D??E) 前提 (9) F （7），（8） (10) 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 假设前提

22

（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 附加前提 （2） （3） （4） （5）

P→(Q?S) 前提 ?P （1），（2） U?P 前提 U （3），（4）

23

（6） （7） （8） （9）

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）

24

（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)

25

(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

26

证明：

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

(4) B→?A 前提 (5) ?B （1），（4） (6) C （3），（5） (7) D→?C 前提 (8) ?D （6），（7） (9) 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)

27

??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) 前提 ?P （2），(3)

（4）

(5) S?P 前提 (6) S (4),(5)

16、P??Q，Q??R，R??S? ?P

证明、

(1) P 附加前提

（2） P? （3）

?Q 前提

?Q （1），（2）

?R 前提

（4） Q? (5)

?R （3），（4）

(6 ) R??S 前提

（7） R （6） （8） R??R （5），（7）

17、用真值表法证明Ｐ?Ｑ? (Ｐ?Ｑ)?(Ｑ?Ｐ)

证明、

列出两个公式的真值表：

28

P Q P?Q （P?Q）?（Q?P） F F F T T F T T T T F F F F 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)

29

? (?P?Q??R)?(?P?Q?R)?(?P??Q?R) 它们有一样的主合取范式，所以它们等价。

20、(P→Q)??(Q?R) ??P

证明、

设(P→Q)??(Q?R)为T，则P→Q和?(Q?R)都为T。即P→Q和?Q??R都为T。故P→Q，?Q和?R)都为T，即P→Q为T，Q和R都为F。从而P也为F，即?P为T。从而(P→Q)??(Q?R)

??P

21、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效?

前提: (1) 若A队得第一，则B队或C队获亚军;

(2) 若C队获亚军，则A队不能获冠军; (3) 若D队获亚军，则B队不能获亚军; (4) 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）

30

（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）

31

=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)

32

= (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=?

证明：

33

因为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)

34

证明：

?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=?。

证明：

（A?B）-B=（A??）?当B=?时，因为（A-B）?B=（A-?）??=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矛盾。

35

五、证明或解答：

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

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）x

36

个体域 （3）若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??。

37

对?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}。求下列各集合：

38

（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上的全序关系。

证明：

39

?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是对称的，?yRx。反之??R-1,即?R 。即?R， R_1?R。

故R=R-1。

??x，y?A，若?R ，即?R-1。? R=R-1，??R。即yRx，

40

故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?T）?R?T。故?（R?S） 。从而R?(S?T)?(R?S）。

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

证明：

设a,b都是B的最大元，则由最大元的定义a?b，b?a。??是A上的偏序关

系，?a=b。即B如果有最大元则它是惟一的。

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

41

2 3 2 3 2 3 解：

?000???（1）R={<2,1>,<3,1>,<2,3>};MR=?101?;它是反自反的、反对称的、传递的；

?100????011???（2）R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>};MR=?101?;它是反自反的、

?110???对称的；

?011???（3）R={<1,2>,<2,1>,<1,3>,<3,3>};MR=?100?;它既不是自反的、反自反的、

?001???也不是对称的、反对称的、传递的。

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>}。

42

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图如下。

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

（2） 分别求出下列集合关于?的极大（小）元、最大（小）元、上（下）

界及上（下）确界（若存在的话）： (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;无最大元和最小元；

43

上界是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?（1）??2431?????4321??=??1342??

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

???????123456??123456??123456?=??452631?????635124??=??123456?? ??????3221、试求出8阶循环群的所有生成元和所有子群。

解：

设G是8阶循环群，a是它的生成元。则G={e,a,a2,..,a7}。由于ak是G的生成元的充分必要条件是k与8互素，故a,a3,a5,a7是G的所有生成元。

44

因为循环群的子群也是循环群，且子群的阶数是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 的子群。

证明：

? 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 的元素一定是奇数个。

45

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