离散数学结构试题集

第1章

一.填空题 1.

2. 公式P→(Q→R)在联结词全功能集{﹁,∨}中等值形式为___________________。

3. 4.

5. 6.

7. 全体小项的析取式必为____________________式。

8. P,Q为两个命题，则德摩根律可表示为7. 全体小项的析取式必为_________式。

9. P,Q为两个命题，则吸收律可表示为____________________ 。

10. 设P：我有钱，Q：我去看电影。命题“虽然我有钱，但是我不去看电影”符号化为_____ _______________。

11. 设P：我生病，Q：我去学校。命题“如果我生病，那么我不去学校”符号化为_________ ___________。 12. 13.

14.

15. 设P、Q为两个命题，交换律可表示为____________________。 16.

17. 命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化 为____________________ 。 18. 19. 20.

21. P：你努力，Q：你失败。命题“除非你努力，否则你将失败”的翻译为_______________ _____。 22. 23.

24. 一个重言式和一个矛盾式的合取是____________________。

25. 全体小项的析取式为____________________ 。

26. 命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化 为____________________。 27.

28. 设P：它占据空间，Q：它有质量，R：它不断运动，S：它叫做物质。命题“占据空间的

，有质量的而且不断运动的叫做物质”的符号化为____________________。 29.

30.

二.选择题

1.

2.

3. 在除﹁之外的四大联结词中，满足结合律的有几个( )。 A. 2 B.3 C. 4 D. 1

4. 判断下列语句哪个是命题( )。 5.

A.你喜欢唱歌吗？ B.若7+8＞18，则三角形有4条边。 C.前进！ D. 给我一杯水吧！

6.

7.

8. 永真式的否定是（ ） A. 永真式 B. 永假式 C. 可满足式 D. A--D均有可能

9. 下面哪一个是假命题（ ）。

A.如果2是偶数，那么一个公式的析取范式唯一。 B.如果2是偶数，那么一个公式的析取范式不唯一。 C. 如果2是奇数，那么一个公式的析取范式唯一。 D. 如果2是奇数，那么一个公式的析取范式不唯一。

10. 设p:天下大雨，q:小王乘公共汽车上班，命题“只有天下大雨，小王才乘公共汽车上班 ”的符号化形式为( )。 A. p→q B. q→p C. p→┐q D. ┐p→q

11. 设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好 成绩”的符号化形式为( )。

A.p→q B.q→p C.┐q→p D.┐p→q

12. 下面4个推理定律中，不正确的为( )。 A.A=>(A∨B) (附加律) B.(A∨B)∧┐A=>B (析取三段论) C.(A→B)∧A=>B (假言推理) D.(A→B)∧┐B=>A (拒取式)

13. 使命题公式p→(p∧q)为假的赋值是 ( )。

A.10 B.01 C. 00 D.11

14. 令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ）。 A. p∧┐q B．p∨┐q C.p∧q D．p→┐q

15. 一个公式在等价意义下，下面哪个写法是唯一的（ ）。

Ａ．析取范式 B．合取范式

Ｃ．主析取范式 D．以上答案都不对

16. 令p：今天下雨了，q：我上学，则命题“因为今天下雨了，所以我不上学了”可符号化

为（ ）。 A．p→┐q B．p∨┐q 18.

C．p∧q D．p∧┐q

17. 下列各组公式中哪组互为对偶（ ）。(P为原子命题，A为复合命题)

A. P,P B. P, ┐P

C. A, (A*)* D. A,A

19.

20.

21.

22.

23. 24.

25. 下列语句哪个是命题（ ）。 A.9+5?12 B. x+3=5

C.我用的计算机CPU主频是1G吗？ D 我正在说谎。

26. 27.

28. n个命题变元可产生（ ）个互不等价的大项。 A. n B. n C. 2n D. 2

29. 下列各命题中真值为真的命题有（ ）。

A.2+2=4当且仅当3是奇数 B.2+2=4当且仅当3不是奇数 C.2+2≠4当且仅当3是奇数 D.2+2≠5当且仅当3不是奇数

2

n

30. 下列语句哪个不是命题（ ）。 A.雪是黑的。 B. 天气多好啊！ C.今天下雨。 D 我学英语，或者我学日语。

三.判断题

1. “我正在说谎。”是一个命题。 （ ）

2. 一个命题标识符如表示确定的命题，就称为命题常量。（ ）

3. “她昨天做了一顿或两顿饭。”是个原子命题。（ ）

4. 命题公式是没有真假值的，仅当在一个公式中命题变元用确定的命题代入时，才得到一 个命题。（ ）

5. 如果A和B是合式公式，那么(A→ B)是合式公式。（ ）

6. 原子谓词公式是合式公式。（ ）

7. 一般来说，n个命题变元组成的命题公式共有2n中真值情况。（ ）

8. 任何两个重言式的合取或析取，仍然是一个重言式。（ ）

9. 重言式和矛盾式的析取是重言式。（ ）

10. 在真值表中，一个公式的真值为F的指派所对应的大项的析取，即为此公式的主析取范式 。（ ）

11. 从假的命题出发，能证明任何命题。（ ）

12. 全体小项的析取式永为假 。（ ）

13. 连接词↑和↓是可交换的，也是可结合的。（ ）

14. P→Q =〉P→P∧Q。（ ）

15. 由n个命题变元组成不等值的命题公式的个数为2n。（ ）

四.计算题

1. 2. 3. 4. 5. 6. 7. 8. 9.

10.

11. 12. 13.

14.

15.

五.证明题

1. 2. 3. 5.

第2章

一.填空题

前提：(1)若A队得第一，则B队或C队获亚军； (2)若C队获亚军，则A队不能获冠军； (3)若D队获亚军，则B队不能获亚军； (4)A 队获第一； 结论：(5) D队不是亚军。

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

1.

2. 3.

4. 5.

6.

7.

8. 9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21. 22.

23.

24. 25.

26. 27.

28.

29. 30.

二.选择题

1.

2.

3. 4.

5.

6. 7.

8. 9.

10.

11.

12. 13.

14.

15. 16.

17.

18. 19.

20.

21. 22.

23. 24.

25. 26.

27.

28.

29.

30.

三.判断题

1. “如果1+2=3，则4+5=9。”是真命题。（ ）

2. 约束变元换名时，一定要更改为作用域中没有出现的变元名称。（ ）

3.

4. 简单命题函数由一个谓词和一些客体变元组成。（ ）

5. 单独一个谓词，不是完整的命题。（ ）

6. 任意一个谓词公式均和一个前束范式等价。（ ） 7. 8. 9. 10.

11. 12. 13.

14. 15.

四.计算题 1.

2.

3. 4. 5.

6. 7.

8.

9.

10.

五.证明题 1.

2.

3. 4.

5. 符号化下列命题，并推证其结论。

所有有理数是实数，某些有理数是整数，因此某些实数是整数。

第3章

一.填空题

1. 设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},则A∪B=_________________。

2. A，B，C表示三个集合，图中阴影部分的集合表达式为____________________。

3. 设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},则A°B=_______________。

4. 设A={a，b，c，d}，其上偏序关系R的哈斯图为

则 R=_______________________。

5. 设A={1，2，3}，则A上既不是对称的又不是反对称的关系为R=____________________。

6. 设A={1，2，3}，则A上既是对称的又是反对称的关系为R=_____________________。

7. 设|A|=3，则A上有________________个二元关系。

8. 偏序集〈Ρ（{a,b}），?〉的哈斯图为________________。

9. 对集合X和Y，设|X|=m ，|Y|=n ，则从X到Y的函数有__________________个。

10. 关系R的自反闭包r (R) ＝________________。

11. 关系R的对称闭包s (R) ＝_________________。

12. 关系R的传递闭包t (R) ＝_____________________。

13. 若R是集合A上的偏序关系，则R满足___________________。

14. 若R是集合A上的等价关系，则R满足____________________。

15. 若R是集合A上的相容关系，则R满足__________________。

16. 设A，B是两集合，其中A={a，b，c}，B={a，b}，则A-B=_______________。

17. 设R={,,}，则ran(R) =______________。

18. 设R={,,}，则dom(R) =________________。

19. 设R={,,}，则FLD(R) =_________________。

20. 设A={a，b}，B＝｛1，2，3｝，则A×B=__________________。

21. 设R是A={1，2，3，4}上的二元关系,R={<1,1>,<1,2>,<2,3>,<3,4>},则R的对称闭包是__ _______________。

22. 设R是A={1，2，3，4}上的二元关系,R={<1,1>,<1,2>,<2,3>,<3,4>},则R的自反闭包是__ ________________。

23. 设R是A={1，2，3，4}上的二元关系,R={<1,1>,<1,2>,<2,3>,<3,4>},则R的传递闭包是__ __________________。

24. 设A,B是集合，|A|=3，|B|=4，|A∩B|=2，那么|A∪B|=_____________。

25. 集合A有n个元素，则A的幂集有___________个元素。

26. 一个集合的非平凡子集包括___________和全集。

27. 集合A={?,a}，则A的幂集P(A)=____________。

28. 设A,B为集合，则命题A-B=?<=>A=B的真值为（填“真”或“假”或“不可判别”）____ ____。

29. 设A={a,b,c,d}，A上的等价关系R=IA∪{(b,c),(c,b),(a,d),(d,a)}，则对

应于R的A的划分是_______________。

30. 给定集合A＝{1,2,3,4,5},R是A上的等价关系，且此关系R能产生划分{{1,2},{3,4,5}},

则R=_________________。

二.选择题

1. 设A={1,2,3}，则A上有（ ）个二元关系。 A.23 B.32 C. 22^3 D.2 3^2

2. 设X，Y，Z是集合，下列结论不正确的是（ ）。 A．若X?Y,则X∩Y=X B．(X-Y)-Z=X-(Y∩Z)

3. 设S={1,2,3,4}，R={<1,1>,<2,2>,<3,3>}，则R的性质是（ ）。

A.自反、对称、传递的 B.自反、对称、反对称的 C.对称、反对称、传递的 D.只有对称性

C．X⊕X=? D．X-Y=X∩(~Y)

4. 设R和S是P上的关系，P是所有人的集合，R={|x,y?P∧x是y的父亲}，S={|x, y?P∧x是y的母亲} 则S °R表示关系 （ ）。 A、{|x,y?P∧x是y的丈夫} B、{|x,y?P∧x是y的孙子或孙女}

C、?

-1

D、{|x,y?P∧x是y的祖父或祖母}

5. 若X是Y的子集，则一定有（ ）。 A.X不属于Y B.X?Y

C.X真包含于Y D.X∩Y=X

6. 下列式子中正确的是（ ）。 A．?=0 B． ??? C．??{a，b} D．??{?}

7. 下面那条不是偏序关系的性质：（ ） A).自反性 B)相容性 C)传递性 D)反对称性

8. 关于闭包运算，下面那条性质不对（ ）

A)rs(R)=sr(R) B)rt(R)=tr(R) C)st(R)=ts(R) D)rtr(R)=tr(R)

9. 设某集合有m个元素，则可以构成（ ）个子集。

A)m B)m! C)2 D)2-1

m

m

10. A, B为两个集合，如果A?B，则下面那个是错误的。（ ） A)A∩B≠? B) ~B?~A C) (B-A)∪A=B D)(B-A)∪A=A

11. 设S={1,2,3}，S上关系R的关系图为

则R具有（ ）性质。

A．自反性、对称性、传递性； B．反自反性、反对称性； C．反自反性、反对称性、传递性； D．自反性 。

12. 设A={?，{1}，{1，3}，{1，2，3}}则A上包含关系“?”的哈斯图为（ ）

13. 集合A={1，2，3，4}上的偏序关系图为

则它的哈斯图为（ ）。

14. 集合A={1，2，3，4}上的偏序关系为）。

，则它的Hass图为（

15. 设R，S是集合A上的关系，则下列（ ）断言是正确的。 A、R,S自反的，则R°S是自反的；

B、若R,S对称的，则R°S是对称的； C、若R,S传递的，则R°S是传递的；

D、若R,S反对称的，则R°S是反对称的

16. 下图描述的偏序集中，子集{b,e,f}的上界为 （ ）。

A、b,c ； B、a,b ； C、 b； D、a,b,c。

17. 设R，S是集合A上的关系，则下列说法正确的是（ ）。

A．若R，S 是自反的， 则R°S是自反的； B．若R，S 是反自反的， 则R°S是反自反的； C．若R，S 是对称的， 则R°S是对称的； D．若R，S 是传递的， 则R°S是传递的。

18. 设R是集合A上的二元关系，IA是A上的恒等关系，IA?R下面四 个命题为真的是 ( )。

A.R是自反的 B.R是传递的 C.R是对称的 D.R是反对称的

19. 已知A,B是集合│A│=15，│B│=10，│A∪B│=20，则│A∩B│=（ ） A．10 B．5 C．20 D．13

20. 设A={a,b,c,d}，A上的等价关系R={,,,}∪IA，则对应于R的A的划 分是（ ）。 A．{{a},{b,c},{d}} B．{{a,b},{c},{d}} C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}

21. 集合A={1，2，3，4}，则对 A 的元素进行划分正确的是（ ）

A. {,{1,2},{3,4}} B. {{1,2,3},{3,4}} C. {{1},{3,4}} D. {{1,2,3,4}}

22. 设集合A={2,{a},3,4}，B = {{a},3,4,1}，E为全集，则下列命题正确的是( )。

(A){2}?A (B){a}?A (C)??{{a}}?B?E (D){{a},1,3,4}?B

23. 设集合A={1,2,3},A上的关系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则R不具备( ).

(A)自反性 (B)传递性 (C)对称性 (D)反对称性

24. 设A, B为集合，当( )时A－B＝B. (A)A＝B (B)A?B (C)B?A (D)A＝B＝?.

25. 设集合A = {1,2,3,4}, A上的关系R＝{(1,1),(2,3),(2,4),(3,4)}, 则R具有( )。 (A)自反性 (B)传递性 (C)对称性 (D)以上答案都不对

26. 下列关于集合的表示中正确的为( )。 (A){a}?{a,b,c} (B){a}?{a,b,c}

(C)??{a,b,c} (D){a,b}?{a,b,c}

27. 设R和S是集合A上的关系，若R和S是传递的，则（ ） (A) R∩S是传递的； (B) R∪S是传递的；

28. 下列命题正确的是 ( )

(A){1,2}?{{1,2},{1,2,3},1} (B){1,2}?{1,{1,2},{1,2,3},2} (C){1,2}?{{1},{2},{1,2}} (D){1,2}?{1,2,{2},{1,2,3}}

29. 下列关系矩阵所对应的关系具有反自反性的是（ ）

(C) R°S是传递的； (D) 以上都不对。

30. 设R1和R2是集合A上的相容关系，下列关于R1 &opl

us;R2的说法正确的是（ ） (A) 一定是相容关系； (B) 一定不是相容关系；

(C) 可能是也可能不是相容关系； (D) 一定是等价关系。

三.判断题

1. 设集合A={ a,b,c,d,e,f}，那么S1= {?, {a,b},{c,d},{f}}是集合A的一个覆盖。( )

2. 恒等关系既是等价关系又是偏序关系。 ( )

3. 设F,R都是二元关系,则(F°R)-1=F-1 °R-1。

( )

4. 设A,B,C是三集合，已知A∪B＝A∪C，则一定有B＝C。 ( )

5. 设集合A={ a,b,c,d,e,f}，那么S1= { {a,b},{c,d,e},{e,f } }是集合A的划分。( )

6. 集合A上的等价关系确定了A的一个划分。( )

7. 集合A上的偏序关系的三个性质是反自反性、对称性和传递性。 ( )

8. 偏序集合中，链上的任何两个元素都是有关系的。( )

9. 空集是任何集合的真子集。( )

10. 设集合A、B、C为任意集合，若A×B = A×C，则B = C。 ( )

11. 若集合A上的关系R是对称的，则R-1也是对称的。

12. 对于一个给定的集合，其划分是唯一的。 （ ）

13. 设R为X上的二元关系，则R是对称的<=>R=Rc。 （ ）

14. 设R为X上的二元关系，则R是反对称的<=>R∩Rc?IX。 （ ）

15. 设R为X上的二元关系，则R是传递的<=> (R°R) ?R。 （ ）

四.计算题

1. 设S={1,2,3,4,6,8,12,24}，“?”为S上整除关系，问：

（1）偏序集的Hass图如何？

（2）偏序集的极小元、最小元、极大元、最大元是什么?

2. A={a，b，c，d}，R={,,},R是集合A上的二元关系。 （1）画出的R的关系图；

（2）求R的自反闭包和对称闭包。

3. 在实数平面上，画出关系R={|x-y+2>0∧x-y-2<0}，并判定关系的特殊性质。

4. R1={<1,2>,<1,3>,<2,3>,<3,3>}, R2={<2,2>,<2,3>,<3,4>}, (1) 求 R1-1 (2) 求R2 °R1

5. 设集合A＝{a,b,c,d}上的关系R＝{,,,}，写出它的关系矩阵和关 系图，并用矩阵运算方法求出R的传递闭包。

6. 设R是自然数集合N上的关系，且xRy<=>x+2y=10。 (1)求dom R；

(2)说明R具有的性质(自反、反自反、对称、反对称、传递)。

7. 集合S={1，2，3，4，5}，找出S上的等价关系，此关系能产生划分{{1，2}，{3}，{4，5

}}，并画出关系图。

8. 集合上的关系R={<1,1>,<1,3>,<2,2>,<3,3>,<3,1>,<3,4>,<4,3>,<4,4>},写出关系矩阵 ，画出关系图并讨论R的性质。

五.证明题

1. 令I是整数集合，I上关系R定义为：R＝{|x-y可被3整除}，求证R是自反、对称和传

递的。

2. 设A、B、C是任意集合，证明：A-(B∪C)=(A-B)∩(A-C)

3. A, B为两个任意集合，求证：A－(A∩B) = (A∪B)－B .

4. 试证明实数集R上的小于等于关系“?” 是偏序关系。

5. 设A、B、C为任意三个集合，证明A×(B∪C) = (A×B)∪(A×C)。

第4章

一.填空题

1. 设f是集合X到集合Y的一个关系，如果对?x?X，有唯一的y?Y使得?f，则称关系

f为X到Y的__________。

2. 设X，U，V，Y都是实数集，f1:X->U，且f1(x)=ex； f2:U->V，且f2(u)=u(1+u)；f3:V->Y，且f3

(v)=cosv。那么f3°f2 °f1的 定义域是__________ ____。

3. 设X，U，V，Y都是实数集，f1:X->U，且f1(x)=e； f2:U->V，且f2(u)=u(1+u)；f3:V->Y，且f3 (v)=cosv。那么f3°f2 °f1(x)=______________。

4. F={,,}______（“是”或者“不是”）函数。

5. F={,}_______（“是 ”或者“不是”）函数。

6. 设f，g是自然数集N上的函数，?x?N，f(x)=x+1，g(x)=2x，则f°g(x)＝_______。

7. 设函数f:X→Y,如果对X中的任意两个不同的x1和x2，它们的象y1和y2也不同，我们说f是

x

______函数。

8. 设函数f:A→B, 则f 的逆关系是函数当且仅当f 是________（“入射”或“满射”或“ 双射”）。

9. 若函数f:A→B存在逆函数f,则 f °f =_________。

10. 若函数f:A→B存在逆函数f则f° f=_________。

11. 如果IA=_______，则称IA：A→A为集合X上的恒等函数。

12. 函数f:I->I,f(j)=j(mod3)______（“是”或者“不是”）入射函数。

-1,

-1

-1

-1

13. 函数射函数。

_____（“是”或者“不是”）满

14. 函数f:I->I,f(j)=j(mod3)_______(“是”或者“不是”)双射函数。

15. 函数f:I->N,f(i)=|2i|+1_______（“是”或者“不是”）入射函数。

二.选择题

1. 设集合A，B是有穷集合，且|A|=m，|B|=n，则从A到B有（ ）个不同的双射函 数。

A、n ； B、m ； C、n! ； D、m! 。

2. 下列命题正确的有（ ）。

A、若g,f是满射，则g°f是满射； B、若g°f是满射，则g,f都是满射； C、若g°f是单射，则g,f都是单射； D、若g°f是双射，则f是双射。

3. 设f，g是函数，当（ ）时，f=g 。

A、?x?domf 都有f(x)=g(x)； B、domg?domf且f?g；

C、f与g的表达式相同； D、domg=domf,rangef=rangef

4. N是自然数集，定义f:N->N,f(x)=(x)mod3（即x除以3的余数），则f是（ ） 。

A、满射不是单射；B、单射不是满射；C、双射；D、不是单射也不是满射。

5. 下列关系中能构成函数的是（ ）。

A、{|(x,y?N)∧(x+y<10)}；B、{|(x,y?R)∧(y=x)}；

2

2

C、{|(x,y?R)∧(y =x)}； D、{|(x,y?I)∧(x≡y mod3)}

6. 下面函数（ ）是单射而非满射。 A、f：R->R，f(x)=-x2 +2x-1； B、f:Z+ ->R，f(x)=ln x；

C、f:R->Z，f(x)=[x],[x]表示不大于x的最大整数； D、f:R->R，f(x)=2x+1。

7. 若函数g和f的复合函数g°f 是双射，则（ ）一定是正确的。

8. X={a，b，c，d，e}，Y={1，2，3，4}，f从X到Y的映射，其中f(a)=2, f(b)=4, f(c)=1, f(d)=3,f(e)=4,则f是（ ）。 A双射 B 满射 C 单射 D 以上都不是

9. 对于下面函数f的描述，那条不对（ ）

A)f(x)的像必然唯一存在 B)如果f存在逆函数，则必是满射的

C)如果f是入射的，则必存在逆函数 D)如果f是双射的，则必是入射的 A、g是入射；B、f是入射；C、g是双射；D、f是满射。

10. 设函数f：N→N（N 为自然数集），f(n)=n+1，下面四个命题为真的是 ( )。 A. f是单射 B. f是满射 C. f是双射的 D.f非单射非满射

11. 函数f:N->N,f(j)=______函数。

是

A .入射但是非满射 B. 满射但是非入射

C. 双射 D.既不是入射，也不是满射

12. 函数是 f: I->I, f(j)=j(mod3)是______函数。

13. 函数f: R->R, f(r)=2r-15 是_____ 函数。 A .入射但是非满射 B. 满射但是非入射

C. 双射 D.既不是入射，也不是满射 A .入射但是非满射 B. 满射但是非入射

C. 双射 D.既不是入射，也不是满射

14. 函数f:I->I, f(j)=j(mod 4)是_____ 函数。 A .入射但是非满射 B. 满射但是非入射 C. 双射 D.既不是入射，也不是满射

15. 函数f:I->I, f(j)=j(mod 5)是_____ 函数。 A .入射但是非满射 B. 满射但是非入射 C. 双射 D.既不是入射，也不是满射

三.判断题

1. 若X和Y的元素个数相同，即|X|=|Y|，则f : X->Y是入射的当且仅当它是一个满射。( )

2. 设f : X->Y是满射，即对任意的y?Y，必存在x?X，使得f(x) = y成立。( )

3. 一个函数必然是一个关系。( )

4. 一个关系就是一个函数。( )

5. 函数f : X->Y就是从集合X到集合Y的一个映射。( )

6. 一个双射函数必然是一个入射函数。（ ）

7. 一个满射函数必然是一个双射函数。（ ）

8. 一个双射函数有可能不是一个入射函数。（ ）

四.计算题

1. 设R是实数集合，σ,τ,υ是R上的三个映射，σ(x) = x+3, τ(x) = 2x, υ(x) ＝ x/4 ,试求复合映射σ?τ，σ?σ, σ?υ, υ?τ，σ?υ?τ.

2. 下面有三个关系图，判断它们是函数否？如果不是，请说明原因。

3. 设A={1,2,3,4},B={x,y,z,w},决定下列(1)--(5)的每个关系R是不是从A到B的一个函数。

如果是一个函数,找出其定义域和值域,并确定它是不是入射的或满射的。

(1){<1,x>,<2,x>,<3,z>,<4,y>};

(2){<1,z>,<2,x>,<3,y>,<4,z>,<2,w>}; (3){<1,z>,<2,w>,<3,x>,<4,y>}; (4){<1,w>,<2,w>,<4,x>} (5){<1,y>,<2,y>,<3,y>,<4,y>}。

4. 设集合A={1,2,3}, f、g是集合A到A的函数，f={<1,2>,<2,3>,<3,1>}，g={<1,2>,<2,1>, <3,3>}, 计算f °g，g °f。

5. 设集合A={1,2,3},B={a,b}, f:A->B, 且f={<1,a>,<2,b>,<3,b>}，试判断f是不是一个函 数?如果是函数，是否存在逆函数？

五.证明题

1. 令g οf 是一个复合函数。若g 和 f 是满射，则g οf是满射的。

2. 设f °g是复合函数，证明：如果f °g是满射的，那么f是满射的。

3. 设f °g是复合函数，证明：如果f °g是入射的，那么g是入射的。

4. 设f °g是复合函数，证明：如果f °g是双射的，那么f是满射的而g是入射的。

5. 令g °f 是一个复合函数。若g 和 f 是入射的，则g°f是入射的。

第5章

一.填空题

1. 群中有唯一的（ ）。

2. 如果群运算是可交换的，则群为（ ）。

3. 设*是定义在集合A上的二元运算，如果对于A中任意的两个元素x,y，都有x*y?A，则称

二元运算*在A上是（ ）。

4. 设*是定义在集合A上的二元运算，如果对于A中任意的两个元素x,y，都有x*y=y*x，则称

二元运算*在A上是（ ）。

5. 设★是定义在有理数集合Q上的二元运算，如果对于Q中任意的两个元素x,y，都有x★y=x

+y-x*y，其中*表示普通乘法元算，则二元运算★在Q上是（ ）。（填写可交 互/不可交换）

6. 设*是定义在集合A上的二元运算，如果对于A中任意的元素x,y,z，都有(x*y)*z=x*(y*z) ，则称二元运算*在A上是（ ）。

7. 设★是定义在非空集合A上的二元运算，如果对于A中任意的两个元素x,y，都有x*y=y， 则二元运算★在A上是（ ）。（填写可结合/不可结合）

8. 设*，★是定义在集合A上的两个二元运算，如果对于A中任意的元素x,y,z，都有(x*y) ★z=（x★z）*(y★z)，z★(x*y)=(z★x)*(z★y),则称二元运算★对于*在A上是（ ）。

9. 设*，★是定义在集合A上的两个可交换的二元运算，如果对于A中任意的元素x,y，都有x

*(x★y)=x, x★(x*y)=x,则称二元运算*对于★在A上满足（ ）。

10. 设*是定义在集合A上的二元运算，如果对于A中任意的元素x，都有x*x=x，则称二元运算

*是（ ）。

11. 设*是定义在集合A上的二元运算，如果在A中存在元素el，对于A中任意的元素x，都有el

*x=x，则称el为A中关于运算*的（ ）。

12. 设*是定义在集合A上的二元运算，如果在A中存在元素ol，对于A中任意的元素x，都有ol

*x=x，则称ol为A中关于运算*的（ ）。

13. 设*是定义在集合A上的二元运算，如果在A中存在元素er，对于A中任意的元素x，都有x*

erl =x，则称er为A中关于运算*的（ ）。

14. 设*是定义在集合A上的二元运算，如果在A中存在元素or，对于A中任意的元素x，都有x*

or=x，则称or为A中关于运算*的（ ）。

15. 如果对于集合中的二元运算*，存在左零元和右零元，且左零元等于右零元，则零元是（

）。

16. 如果对于集合中的二元运算*，存在左么元和右么元，且左么元等于右么元，则么元是（

）。

17. 设*是定义在集合A上的二元运算，且e是A中关于运算*的么元，如果对于A中的元素x，存

在A中的元素y，有y*x=e，则称y为x的（ ）。

18. 对于实数域上的乘法元算，每个元素（ ）逆元。（填写一定有/不一定有 ）

19. 对于实数域上的加法运算，（ ）零元。（填写存在/不存在）

20. 对于整数域上的加法运算，（ ）么元。（填写存在/不存在）

21. 对于非空集合S上二元运算*，是封闭且可结合的，那么叫做（ ）。

22. 正整数上的加法运算（ ）半群。（填写是/不是）

23. 实数域上的除法运算（ ）半群。（填写是/不是）

24. 整数域上的加法运算（ ）群。（填写是/不是）

25. .如果群的运算满足交换率，则这个群叫（ ）。

26. 循环群（ ）生成元。(填写必有/不一定有)

27. 设f是由到的一个同态，如果f( ),则称f为满同态的 。

28. 设f是由到的一个同态，如果f( ),则称f为同构的。

29. 设f是群到的一个同态映射，如果e’是B中的么元，Ker(f)=( )，则称Ker(f)为同态映射f的核。

30. 设R是代数系统上的一个等价关系，如果当,?R时，蕴含着?R，则称R为A上关于★的（ ）。

二.选择题

1. 下面那个性质不是群必有的？（ ） A)运算的封闭性 B)幺元 C)零元 D)运算的交换性

2. 设集合A={1,2,?,10},下面定义的那个二元运算*关于A不封闭？（ ） A)x*y=max(x,y) B)x*y=质数p的个数，使得x<=p<=y

C)x*y=min(x,y) D)x*y=((x+y)mod 10)+1

3. 是一个半群，如果S是一个有限集，则必有（ ） A)幺元 B)零元 C)等幂元 D)不确定

4. 下面那个代数系统表示的范围最大？（ ） A)群 B)半群 C)阿贝尔群 D)独异点

5. 同构关系必然是一个（ ） A）等价关系 B)偏序关系 C)同余关系 D)同态关系

6. 在自然数集N上，下列哪种运算是可结合的？（ ）

8. 设是群，a,b?G,则下列结论不正确的是（ ） A．(a*b)-1=b-1*a-1 B．a*x=b有唯一解

C．a*x=a*y,则x=y D．a*b=b*a

A) a*b=a-b B) a*b=max{a,b} C) a*b=a+2b D) a*b=|a-b|

7. 同构关系必然是一个（ ）

A．等价关系 B.偏序关系 C.同余关系 D.相容关系

9. 下面那个运算不满足运算的封闭性？（ ） A）自然数上的加法 B）有理数上的乘法 C）1到10之间的模11加法 D）0到9之 间的模10加法

10. 下面那个不满足结合律？（ ） A)自然数上的加法 B）有理数上的乘法 C）自然数上的max(a,b) D)自然数上的减法

11. 对于代数系统，Nk ={0,1,?,k-1}，+k是定义在Nk上的模k加法，下面说法不对 的是：（ ） A）有零元 B)有么元 C)每个元素都有逆元 D）是半群

12. 下面关于半群的说法正确的是（ ） A）必有零元 B）必有么元 C）必然服从交换律 D)必然服从结合律

13. 若果为半群，且S是有限集合，则以下说法正确的是（ ）

A)必有a?S,且a*a=a B) 必有a?S,且a*b=b C)必有零元 D）必有零元

14. 关于独异点，下列说法正确的是（ ）

A)必有零元 B)必有等幂元 C）必有么元 D)必然满足交换律

15. 以下说法不正确的是（ ）

A)群表示范围比半群小 B)交换群表示范围比半群小 C)阿贝尔群表示范围比群小 D）广群表示的范围比半群小

16. 下面关于群的说法不正确的是（ ） A）必有零元 B）必有么元 C）每个必然有逆元 D)必然服从结合律

17. 下面那个是群？（ ） A)自然数上的乘法 B)实数域上的乘法 C) 0到9之间的模10加法 D) 0到9之间的

模10乘法

18. 下面关于群的说法不正确的是（ ）

19. 下面关于群的说法正确的是（ ） A)没有等幂元 B) 有1个等幂元 C)有2个等幂元 D)和群的阶数有关

20. 设为一个群，下面关于G的子群的说法正确的是（ ）

A)如果S是G的非空子集且*在S上是封闭的，则就是的子群 B) 如果S是G的非空子集且含有么元，则就是的子群 C) 如果S是G的非空子集，且对于任意S中的连个元素a,b都有a*b-1?G,则就是 A)对于任a,b?G,存在唯一的x?G,使得a*x=b B)对于任a,b,c?G，若有a*b=a*c,则必有b=c C)任a?G，必有唯一的x?G,使得a*x=e,e为么元 D) 任a?G，必有唯一的x?G,使得a*x=x,x为零元

的子群

D) 如果S是G的非空子集，且是半群,则就是的子群

21. 下列说法那个是错误的。（ ） A)循环群必定是阿贝尔群 B)循环群必定有等幂元 C)阿贝尔群必定是循环群 D)循 环群必定是交换群

22. 下列那个说法是正确的？（ ） A)同态一定是同构的 B）同构一定是同态的 C)同态一定是同余的 D)同态一定是等价的

23. 如果f：R->R，对于任意的x?R,f(x)=5x,则f是从到的一个（ ）

A)单一同态 B)满同态 C)双射同态 D)同构

24. 含有3个元素的群有（ ）种情形。 A)1 B) 2 C) 3 D)0

25. .设G是非零乘法群，判断下列哪个f不是G到G的同态映射。（ ） A）f(x)=|x| B)f(x)=-x C)f(x)=x+1 D)f(x)=1/x

26. 下面关于群的说法不正确的是：（ ）

A）有么元 B）有零元 C）每个元素都有逆元 D）满足结合律

27. .下面那个是群。（ ）

A）整数域上的加法运算 B）实数域上的乘法运算 C）自然数域上的除法运算 D）

整

数1到5之间的模6加法运算

28. .如果是一个环，下列关于环的说法错误的是（ ）。

A）是阿贝尔群 B）是阿贝尔群 C）运算*对于+是可分配的 D）运算+对于*是可分配的

29. 关于独异点说法错误的是（ ）。

30. 关于阿贝尔群说法错误的是（ ）。

A)必有左么元 B)必有右零元 C)必然满足交换律 D)必是半群 A)必有左么元 B)必有右零元 C)必然满足结合律 D)必是含么半群

三.判断题

1. 半群一定是独异点。( )

2. 代数系统中有可能有很多个左零元和右零元，它们有可能相等，也有可能不等。( )

3. 群中不可能有零元。( )

4. 群中的某些元素可能有多个不同的逆元。 （ ）

5. 群的运算一定符合交换律。（ ）

6. 如果定义在集合A上的*运算既有左零元，又有右零元，那么必有唯一的零元。（ ）

7. 循环群必有等幂元。（ ）

8. 有等幂元的群一定是有限群。（ ）

9. 阿贝尔群运算一定符合交换律。（ ）

10. 有限群一定有么元。（ ）

11. 含有零元的半群叫独异点。（ ）

12. 在群中，出了么元外，可能还还有其他等幂元。（ ）

13. 对一个群，它的任意一个非空有限子集B, 如果*在B上封闭，则一定也是群。 （ ）

14. .循环群一定是阿贝尔群。（ ）

15. 同构的一定是同态的。（ ）

16. 同态可以诱导一个唯一的等价关系。（ ）

17. .f是代数系统到代数系统的同态映射，如果半群，则在f作用下，同 态象也是半群。（ ）

18. 循环群中必有零元。（ ）

19. (*表示乘法)与同构。（ ）

20. 定义在自然数集合上的模k加法是一个群。（ ）

四.计算题

1. 验证二元运算 在实数集 上是否满足交换律和结合律？ 2.

对于实数集合R，在下面表格中填写“是”或“否”

*

min

|x-y|

可结合性

[4]

[6]

[2]

[6]

[3]

[1]

4. 考察代数系统，以下定义在I上的二元关系R是同余关系吗？如不是，找出反例。 1) ?R当且仅当（x<0∧y<0）∨(x?0∧y?0) 2) ?R当且仅当|x-y|<10

5. 考察代数系统，以下定义在I上的二元关系R是同余关系吗？如不是，找出反例。

1) ?R当且仅当（x=y=0）∨(x≠0∧y≠0) 2) ?R当且仅当x?y

五.证明题

1. 设A=｛a，b｝，〈A，*〉为半群，且a*a=b。证明：a*b=b*a 。

2. 定义I+上的两个二元运算为：

a*b=ab

a○b=ab a,b?I+ 证明：*对○是不可分配的。

3. 如果是半群，且*是可交换的，称是可交换半群。证明：如果S中有元素a,b， 使得a*a=a和b*b=b,则（a*b）*(a*b)=a*b。

4. 设是群，且|S|=2n，n?I+。证明：在S中至少存在a≠e，使得a*a=e，其中e为么元 。

5. 证明：如果f是由到的同态映射，g是由到的同态映射，那么，g 。f是由到的同态映射。

6. 设f是从群到的同态映射,则f是入射当且仅当Ker(f)={e}。其中e是G1中 的么元。

7. 设是一个独异点，且对于G中的每一个元素x都有x*x=e，其中e是么元，证明 是一个阿贝尔群。

8. 设是一个代数系统，且对于任意的a?A,有a★b=a,证明二元运算*对★时可分 配的。 第6章

一.填空题 二.选择题 三.判断题 四.计算题 五.证明题 第7章

一.填空题

1. 把（ ）的图叫做简单图。

2. 无向图具有一条欧拉路，当且仅当图是联通的，而且（ ）。

3. 把（ ）的图叫做完全图。

4. 把（ ）的图叫做连通图。

5. 如果一个连通图有m个结点，则它的完全关联矩阵的秩为（ ）。

6. 含有平行边的任何一个图叫做（ ）。

7. 给定图G,若存在一条路（ ），这条路叫做汉密 尔顿路。

8. 在一个含有n个节点的图中，度数为奇数节点的个数必为（ ）个。

9. 在含有n个节点的完全图中，其边数为（ ）。

10. 若图G只有一个连通分支，则G叫作（ ）。

11. 无回路的连通图又叫做（ ）。

12. 给定一个无孤立节点的图G，若存在一条路，经过图中每边一次仅且一次，则这条路叫做

（ ）。

13. G是具有n个节点的简单图，如果G中每对节点度数之和大于等于n，则G中存在一条（

）。

14. 设G=是一个无向图，如果能够把G的所有节点和边画在平面上，且使得任何两条边

出了端点之外没有其他的交点，就称G为（ ）。

15. 还有v个节点，e条边,r个面的连通平面图G,满足欧拉公式（ ）。

二.选择题

1. 如果一个连通图有m个结点，则它的完全关联矩阵的秩为（ ） A)m B)m+1 C)m-1 D)m/2

2. 一个有n个节点连通图至少有（ ）条边。 A)n B)n-1 C)n+1 D)(n-1)n/2

3. 关联同一节点的两条边叫做（ ）。 A）环 B)回路 C)圈 D）邻接边

4. 含有平行边的任何一个图叫做（ ）。

A）欧拉图 B）汉米尔顿图 C）连通图 D）多重图

5. 在一个含有n个节点的图中，度数为奇数节点的个数必为（ ）个。 A）2 B）n-1 C）偶数 D）奇数

6. 在任何有向图中，所有节点的出度之和等于（ ）。

A)所有节点的入度之和 B）所有节点入度之和的2倍 C）所有节点入度之和的一半 D）没有必然联系

7. 在含有n个节点的完全图中，其边数为（ ）。 A)n B)n-1 C)n+1 D)(n-1)n/2

8. 在含有n个节点的图，它有（ ）个补图。 A)1 B)n C) (n-1)n/2 D)0

9. .如果两个图是同构的，那么下面那条是错误的.( )

A)节点数相等 B)边数相等 C)度数相同的节点数相等 D)连通的

10. 在具有n个节点的图中，如果两个节点之间有路，则必有一条路的长度（ ）。 A)至少为n B)至少为n-1 C)至多为n-1 D)n

11. 若图G只有一个连通分支，则G叫作（ ）。

A)连通图 B)强连通图 C）欧拉图 D）平面图

12. 含有m个节点的简单图，其边数不会多于（ ）。

A）1 B）m C)m-1 D)m(m-1)/2

13. 含有n个节点的图，至少生成（ ）棵生成树。 A)1 B)n C) (n-1)n/2 D)0

14. 连通图必然有（ ）。

A）欧拉路 B)汉米尔顿路 C)欧拉回路 D)通过各节点的路

15. 如果一个连通图有m个结点，则它的邻接矩阵的秩为（ ）

A)m B)m+1 C)m-1 D)不确定

三.判断题

1. 在任何图中，度数为偶数的节点必有奇数个。( )

2. 在任何有向图中，所有节点的入度之和等于所有节点的出度之和。（ ）

3. 每个图中，边数等于节点度数的两倍。（ ）

4. 连通图必有欧拉回路。（ ）

5. 有汉米尔顿路的图必有欧拉路。（ ）

6. 含有欧拉回路的图中每个节点的度数必为偶数。（ ）

7. 含有欧拉回路的图必有汉密尔顿路。（ ）

8. 一个图的边连通度一定大于等于其点连通度。（

四.计算题

1. 画出下图的完全补图。

2. 给一个含有5个节点的自补图。

3. 求下图中 1）从A到F所有通路。 2）从A到F的所有迹。

4. 求下图的邻接矩阵，并求出可达性矩阵。

）

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