离散数学习题集

离散数学课外习题集

编者：金鹏

时间：2008-5-6

目录：

第一章

一、选择题

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

A.2n

B.2

n

C.n

2

D

.22n

2. 设P：我将去镇上，Q：我有时间。命题“我将去镇上，仅当我有时间时”符号化

为（） A.PQ B.QP C.P Q D.QP 3. 下列各组公式中，哪组是互为对偶的？（）

A.P,P B.P, P C.A,(A*)* D.A,A （其中P为单独的命题变元，A为含有联结词的命题变元）

4. 设P：我们划船，Q：我们跑步。命题“我们不能即划船又跑步”符号化为（）

A. pQ B. PQ C. (PQ) D.PQ 5. 下面哪一个命题是命题“2是偶数或-3是负数”的否定？（）

A. 2是偶数或-3不是负数 C. 2是奇数或-3不是负数 C．2不是偶数且-3不是负数 D. 2是奇数且-3不是负数

6. 设P：张三可以作这件事，Q：李四可以作这件事。命题“张三或李四可以做这件

事”符号化为（） A.PQ B.PQ C.PQ D. (PQ) 7. 下列语句中哪个是真命题？（）

A.我正在说谎。 B.严禁吸烟。 C.如果1+2=3，那么雪是黑的。 D.如果1+2=5，那么雪是黑的。 8. 下面哪个联结词运算不可交换？（）

A. B. C. D. 9. 命题公式(P (PQ)) Q是（）。

A.矛盾式 B.蕴含式 C.重言式 D.等值式 10. 下面哪个命题公式是重言式？（）

A.(PQ)(Q P) B.(PQ)P C.(PQ)(PQ) D.(PQ) 11. 下列哪一组命题公式是等值的？（）

A. PQ,PQ B.A(BA),A(AB) C.Q(PQ),Q (PQ) D.A (AB),B 12. PQ的逆反式是（）

A.QP B. P  Q C. QP D. QP 13. PQ的逆反式是（）

A.QP B. P  Q C. QP D.P  Q 14. 下列命题联结词集合中，哪一个是最小联结词组？（）

A.{,} B.{,,} C.{} D.{,} 15. 下列联结词集合中，哪一个不是最小联结词组？（）

A.{,} B.{,} C.{,,} D.{}

16. 已知A是B的充分条件，B是C的必要条件，D是B的必要条件，则A是D的（）

A.充分条件 B.必要条件 C.充要条件 D.A、B、C都不对 17. P  Q的反换式是（）

A.QP B.PQ C.QP D.PQ 18. 下面哪一个命题公式是重言式？（）

A.P(QR) B.(PR)(PQ)

C.(PQ)  (QR) D.(P(QR)) ((PQ) (PR)) 19. 下列哪个命题公式不是重言式？（）

A.Q(PQ) B.(PQ)P C.(PQ) (PQ) D.(PQ)(PQ) 20. 重言式的否定式是（）

A.重言式 B.矛盾式 C.可满足式 D.蕴含式 21. 下面哪一个命题是假命题？（）

A.如果2是偶数，那么一个公式的析取范式惟一 B.如果2是偶数，那么一个公式的析取范式不惟一 C.如果2是奇数，那么一个公式的析取范式惟一 D.如果2是奇数，那么一个公式的析取范式不惟一 22. 下面哪一组命题公式不是等值的？（）

A.(AB),AB B.(AB),(AB)(AB) C.A(BC),A(BC) D. A(BC),(AB)C 23. 命题公式PQR的对偶式为（）

A.P(QR) B. P (QR) C.P (QR) D.P (QR) 24. 命题公式P(QR)是（）

A.重言式 B.可满足式 C.矛盾式 D.等值式 25. PQ（）

A.P (PQ) B.(PQ) (QP) C.(PQ)(QP) D.(PQ)(QP)

26. 命题公式(PQ)R的主析取范式中含极小项的个数为（）

A.8 B.3 C.5 D.0

27. 命题公式(PQ)R的主析取范式中含极大项的个数为（）

A.0 B.3 C.5 D.8 28. 命题公式(PQ)R的成真赋值为（）

A.000,001,110 B.001,011,101,110,111 C.全体赋值 D.无

29. 如果AB成立，则以下各种蕴含关系哪一个成立？（）

A.BA B.AB C.BA D.AB

二、填空题

1. 下列句子中，是命题的有 (1).我是教师。 (2).禁止吸烟！

(3).蚊子是鸟类动物。 (4).上课去！

(5).月亮比地球大。

2. 设P：我生病，Q：我去学校

(1).命题“我虽然生病但我仍去学校”符号化为 。

(2).命题“只有在生病的时候，我才不去学校”符号化为 。 (3).命题“如果我生病，那么我不去学校”符号化为 。 3. 设P：我有钱，Q：我去看电影。

(1).命题“如果我有钱，那么我就去看电影”符号化为 。 (2).命题“虽然我有钱，但我不去看电影”符号化为 。 (3).命题“当且仅当我有钱时，我才去看电影”符号化为 。

4. 对于下列各式，是永真式的有 。

(1).(P(PQ))Q (2).P(PQ) (3).Q(PQ)

(4).(P(PQ))Q

5. 6. 7.

8. 9. 10.

(5).(PQ) Q

(P(PQ)) R 。 P(PQ) 。 对于下列各式

(1).(PQ)(PQ)可化简为 。 (2).Q(P(PQ)) 可化简为 。

(3).(PQ)(QP)P可化简为 。

命题公式P(QR)的成真赋值为 ，成假赋值为 。 若 且 则称X是公式A的子公式。 写出表中各列所定义的命题联结词。

P 1 1 0 0

Q 1 0 1 0

P ① Q 1 0 0 0

P ② Q 0 1 1 1

11. 由n个命题变元可组成 个不等值的命题公式。 12. 用两种形式写出PQ的对偶式 ① ， ② 。 13. 两个重言式的析取是 ① ，一个重言式与一个矛盾式的析取是 ② 。 14. A、B为两个命题公式，AB当且仅当 ① ，AB当且仅当 ② 。 15. 设P、Q为两个命题公式，德●摩根律可表示为 ① ，吸收率可表示为 ② 。 16. 设命题公式A中仅含有联结词，，，若 得到公式A*，则A*称为A的对偶式。 17. 公式(PQ) R的只含联结词，，的等值式为 ① ，它的对偶式为 ② 。 18. 命题公式A(PQR)0，则其对偶式A* 。 19. 在命题演算中，一个蕴含式与它的 ① 式是等值的，它的 ② 式与它的 ③ 是不等值的。 20. 公式PQ的反换式为 ① ，逆反式为 ② 。 21. 任意两个不同极小项的合取为 ① 式，全体极小项的析取式必为 ② 。 22. 命题公式(PQ)的主析取范式为 ① ，主合取范式的编码表示为 ② 。 23. 已知公式A(P,Q,R)的主合取范式为M0M3M5，它的主析取范式为（写成编码形式） 。 24. 命题公式(PQ)的主析取范式为 ① ，其编码表示为 ② ，主合取范式的编码表示为 ③ 。 25. 对于前提：SQ，SR，R, PQ，其有效结论为 。 26. 对于前提：(PQ) R，RS, S，其有效结论为 。

三、判断题

1. “王兰和王英是姐妹”是复合命题，因为该命题中出现了联结词“和”。（） 2. 凡陈述句都是命题。（） 3. 语句3x+5y=0是一个命题。（）

4. 命题“两个角相等当且仅当它们是对顶角“的值为1。（） 5. 语句“x+y=4”是个命题。（）

6. 命题“十减四等于五”是一个原子命题。（） 7. 命题“如果1+2=3，那么雪是黑的”是真命题。（）

8. (P(QR))是一个命题演算的命题公式，其中P、Q、R是命题变元。（） 9. (P(QRQ))是一个命题公式，其中P、Q、R是命题变元。（）

10. 若A：张明和李红都是三好学生，则A：张明和李红都不是三好学生。（）

11. 若A：张明和李红都是运动员，则A：张明和李红不都是运动员。（） 12. 若P：每一个自然数都是偶数，则P：每一个自然数都不是偶数。（） 13. 若P：每个自然数都是偶数，则P：每个自然数不都是偶数。（） 14. 如果AB，则ACBC，ACBC。（） 15. 如果ACBC，则AB。（） 16. 联结词“”是可结合的。（） 17. 联结词“”是可结合的。（） 18. 联结词“”是可交换的。（） 19. 联结词“”是可交换的。（） 20. 联结词“”是满足交换律。（） 21. “学习有如逆水行舟，不进则退”。设P：学习如逆水行舟，Q：学习进步，R：学

习退步。则命题符号化为P(QR)。（）

22. P、Q、R定义同上，则“学习有如逆水行舟，不进则退”形式化为：P (QR)。

（）

23. 设P、Q是两个命题，当且仅当P、Q的真值均为1时，PQ的值为1。（） 24. 命题公式(P(PQ))Q是矛盾式。（） 25. 命题公式(P(PQ))Q是重言式。（） 26. 联结词与不是相互可分配的。（）

27. 在命题的演算中，每个最小联结词组至少有两个联结词。（） 28. 命题联结词集{,}是最小联结词集。（） 29. 命题联结词集{,,}是最小联结词集。（） 30. 命题联结词集{,}是最小联结词集。（） 31. 命题联结词集{}和{}是最小联结词集。（） 32. A是命题公式，A与(A*)*互为对偶式。（） 33. A是命题公式，A(A*)*。（） 34. P是命题变元，P与P互为对偶式。（）

35. 任一命题公式的主析取范式和它的主合取范式互为对偶式。（） 36. 任一命题公式都可以表示成与其等值的若干极小项的析取式。（）

四、综合题

1. 使用命题：

P：这个材料有趣。 Q：这些习题很难。 R：这门课程让人喜欢。

将下列句子用符号形式写出：

(1). 这个材料有趣，并且这些习题很难。 (2). 这个材料无趣，习题也不难，而且这门课程也不让人喜欢。 (3). 如果这个材料无趣，习题也不难，那么这门课程就不会让人喜欢。 (4). 这个材料有趣，意味着这些习题很难，并且反之亦然。 (5). 或者这个材料有趣，或者这些习题很难，并且两者恰具其一。 2. 用符号形式写出下列命题：

(1).假如上午不下雨，我去看电影，否则就在家里读书或者看报； (2).我今天进城，除非下雨； (3).仅当你走，我将留下；

(4).一个数是素数当且仅当它只能被1和它自身整除。

3. 判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题。

2是无理数。 (1).

(2).5能被2整除。 (3).现在开会吗？ (4).x+5>0。

(5).这朵花真好看呀！

(6).2是素数当且仅当三角形有三条边。 (7).雪是黑色的当且仅当太阳从东方升起。 (8).2000年10月1日天气晴好。 (9).太阳系以外的星球上有生物。 (10).小李在宿舍。 (11).全体起立！

(12).4是2的倍数或是3的倍数。 (13).4是偶数且是奇数。 (14).李明与王华是同学。

(15).蓝色和黄色可以调配成绿色。 4. 确定下列命题的真值：

(1).“如果太阳从西边出来，那么地球自转”； (2).“如果太阳从东边出来，那么地球自转停止”； (3).“如果8+9>30，那么三角形有三条边”； (4).“如果疑问句是命题，那么地球将停止转动”。 5. 判断下面语句是否是命题，若是，确定其真值：

(1).喜马拉雅山比华山高；

(2).如果时间静止不动，你就可以长生不老； (3).如果时间流失不止，你就可以长生不老； (4).伦敦是英国首都； (5).这盆茉莉花好香阿！

6. 给命题变元P、Q、R、S分别指派真值为1、1、0、0，求下列命题公式的真值：

(1).((PQ)R)(((PQ)R)S) (2).(P(Q(RP)))(QS)

7. 设A*、B*分别是命题公式A和B的对偶式，判断下列各式是否成立，若不成立，

请举例说明： (1).A*A

(2).AB则A*B* (3).AB则A*B* (4).(A*)*A

8. 命题联结词“”定义为PQ(PQ)

(1).构造PQ的真值表；

(2).证明、、可以用仅含联结词的等值公式表示。 9. 化简下列命题公式：

(1).A(A(BB)) (2).(ABC)(ABC) (3).((PQ)(QP))R (4).((AB)(BA)C

10. 如果有ACBC，是否一定有AB? 11. 如果有ACBC，是否一定有AB? 12. 如果AB是否有AB？

13. 用真值表判断下列各式是否为重言式：

(1).((PQ)(QR))(PR) (2).(PQR)(PRQ)

14. 设命题公式A的真值表如表所示，试求出A的主析取范式和主合取范式（用编码

表示和公式表示）： P 1 1 0

Q 1 0 1

A 1 1 0

0 0 1 15. 用等值演算法证明P(PQ) Q是重言式。 16. 证明下列命题的等值关系：

(1).(PQ)(RQ)(PR)Q

(2).(PQAC)(APQC)(A(PQ))C (3).P(QP)Q(PR) (4).(PQ)(PR)P(QR) (5).(PQ)(PQ)(PQ) 17. 求证下面命题的蕴含关系：

(1).PQPQ

(2).(P(QR))(PQ)(PR)

18. 求下面各式的主析取范式与主合取范式，并写出相应的为真赋值。

(1).(PQ)(PQ)

(2).(R(QP))(PQR)) (3).((PQ)Q)((QP)P) (4).(P(QR))(R(QP))

(5).((PQ)(RP))((RQ)P

19. 联结词f1，f2由表所示真值表定义，证明 { f1，f2}是最小联结词组。

P 1 1 0 0

Q 1 0 1 0

f1P 0 0 1 1

P f1Q 1 1 0 1

20. 设计一种简单的表决器，表决者每人座位旁边有一按钮，若同意则按下按钮，否则不按按钮，当表决结果超过半数时，会场电铃就会响，否则铃不响。试以表决人数为3人的情况设计表决器电路的逻辑关系。

21. 证明{}时最小联结词组。

22. 设计一加法器，实现两自然数相加的功能。

23. 某勘探队有3名队员。有一天取得一块矿样，3人的判断如下：

甲说：这不是铁，也不是铜； 乙说：这不是铁，是锡； 丙说：这不是锡，时铁。

经实验室鉴定后发现，其中一人两个判断都正确，一个人判对一半，另一个全错了。根据以上情况判断矿样的种类。

24. 观察下列推理过程，是否正确，结论是否有效，说明理由。

(1).①PQR P (2).②PR T①I (3).③P P (4).④R T②③I 所以PQR，PR。

25. 下列证明过程是否正确，若正确补足每一步推理依据，否则指出错误。

(1).①DA (2).②D (3).③A

(4).④A(CB) (5).⑤CB (6).⑥C (7).⑦B (8).⑧DB

26. 证明A(BC)，B(CD)A(BD)。

27. 用CP规则证明P(QR)，Q(RS)，PQS。 28. 用推理规则说明AB,(BC)，AC是否能同时为真。

29. 用推理规则说明(PQ)R，SU，RS，UW，WPQ。

30. 用推理规则证明下列推理的正确性：如果A努力工作，那么B或C感到愉快；如

果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。

31. 用等值演算法证明P(PQ)是矛盾式。

32. 用CP规则证明A(BC)，(EF)C，B(AS)BE。

33. 用反证法证明(AB)(CD)，(BE)(DF)，(EF)，ACA。 34. 用反证法证明AB，(BC)C，(AD)D。

第二章

一、选择题

1. 谓词公式x(P(x)yR(y))Q(x)中量词x的作用域是（）

A. x(P(x)yR(y)) B.P(x) C. (P(x)yR(y)) D.P(x)，Q(x) 2. 谓词公式x(P(x)yR(y))Q(x)中变元x是（）

A.自由变量 B.约束变量 C.既不是自由变量也不是约束变量 D.既是自由变量也是约束变量

3. 若个体域为整体域，下列公式中哪个值为真？（）

A.xy(x+y=0) B.yx(x+y=0) C.xy(x+y=0) D.xy(x+y=0)

4. 设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式x(P(x)Q(x))在下面哪个论域

中是可满足的？（） A.自然数集 B.整数集 C.实数集 D.以上均不成立

5. 设C(x)：x是运动员，G(x)：x是强壮的。命题“没有一个运动员不是强壮的”可

符号化为（）

A.x(C(x)G(x)) B.x(C(x)G(x)) C.x(C(x)G(x)) D.x(C(x)G(x))

6. 设A(x)：x是人，B(x)：x犯错误，命题“没有不犯错误的人”符号化为（）

A.x(A(x)B(x)) B.x(A(x)B(x)) C.x(A(x)B(x)) D.x(A(x)B(x))

7. 设Z(x)：x是整数，N(x)：x是负数，S(x,y)：y是x的平方，则“任何整数的平方

非负”可表示为下述谓词公式（） A.xy(Z(x)S(x,y)N(y)) B.xy(Z(x)S(x,y)N(y)) C.xy(Z(x)S(x,y)N(y)) D.x(Z(x)S(x,y)N(y))

8. 令F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快。则语句“某些汽车比所有

的火车慢”可表示为（） A.y(G(y)x(F(x)H(x,y))) B.y(G(y)x(F(x)H(x,y))) C.xy(G(y)(F(x)H(x,y))) D.y(G(y)x(F(x)H(x,y)))

9. 设个体域A={a,b}，公式xP(x)xS(x)在A中消去量词后应为（）

A.P(x)S(x)

B.P(a)P(b)(S(a)S(b)) C.P(a)S(b)

D.P(a)P(b)S(a)S(b)

10. 在谓词演算中，下列各式哪个是正确的？（）

A.xyA(x,y)yxA(x,y) B.xyA(x,y)yxA(x,y) C.xyA(x,y)xyA(x,y) D.xyA(x,y)yxA(x,y) 11. 下列各式哪个不正确？（）

A.x(P(x)Q(x))xP(x)xQ(x) B.x(P(x)Q(x))xP(x)xQ(x)

C.x(P(x)Q(x))xP(x)xQ(x) D.xP(x)Q)xP(x)Q

12. 下面谓词公式哪个是前束范式？（）

A.xyz(B(x,y)A(z)) B.xyB(x,y)

C.xyx(A(x,y)B(x,y)) D.x(A(x,y)yB(y))

13. 在谓词演算中：P(a)是xP(x)的有效结论，其理论根据是（）

A.全称规定规则(US) B.全称推广规则(UG) C.存在规定规则(ES) D.存在推广规则(EG)

二、填空题

1. 令R(x)：x是实数，Q(x)：x是有理数。

(1) 命题“并非每个实数都是有理数”。其符号化为 ① 。 (2) 命题“虽然有些实数是有理数，但并非一切实数都是有理数”。则其符号化可

表示为 ② 。

2. 设G(x)：x是金子，F(x)：x是闪光的，则命题“金子是闪光的，但闪光的不一定是金子”符号化为 。

3. 设C(x)：x是计算机，P(x,y)：x能做y，I(x)：x是智能工作，则命题“并非所有智能工作都能由计算机来做”符号化为 。

4. 设Q(x)：x是偶数，P(x)：x是素数，则命题“存在惟一一个偶素数”可符号化为 ① ，“至多存在一个偶素数”可符号化为 ② 。

5. 设Q(x)：x是奇数，Z(x)：x是整数，则语句“不是所有整数都是奇数”所对应的谓词公式为 。

6. 设个体域为自然数集，P(x)：x是奇数，Q(x)：x是偶数，则命题“不存在既是奇数又是偶数的自然数”可符号化为 。

7. 设个体域为全总个体域，R(x)：x是实数，Q(x)：x是有理数，Z(x)：x是整数，则命题“所有的有理数是实数”，“有些有理数是整数”，“有些有理数是实数担不是整数”符号化分别为 ① ， ② ， ③ 。

8. xy(P(x,y)Q(y,z))xP(x,y)中x的作用域为 ① ，y的作用域为 ② ，x的作用域为 ③ 。

9. 公式x(P(x)Q(x,y)R(y,z))S(x)中自由变量为 ① ，约束变量为 ② 。

10. 取个体域为整数集，给定下列公式：

(1).xy(x·y=0) (2).xy(x·y=1) (3)xy(x·y=2) (4)xyz(x-y=z) (5).x-y=-y+x (5).xy(x·y=y) (7)x(x·y=x) (8).xy(x+y=2y)

上面公式中，真命题的有 ① ，假命题的有 ② 。 *11. 下列谓词公式 (1).(xA(x))与xA(x) (2).x(A(x)B(x))与xA(x)xB(x) (3).x(A(x)B(x))与xA(x)xB(x) (4).xyD(x,y)与yxD(x,y)

中 是等值的。

12. 对公式x(P(x)Q(x))，其中P(x):x=1，Q(x):x=2，当论域为{1,2}时，其真值为 ① ，当论域为{0,1,2}时，其真值为 ② 。

13. 设个体域为A={a,b,c}，消去公式xP(x)xQ(x)中的量词，可得 。 14. 下列各式

(1).x(P(x)Q(x))(xP(x)xQ(x)) (2).(x(A(x)B(x))A(c))A(c)

(3).(x(A(x)B(x))xB(x))xA(x) (4).(x(P(x)Q(x)))xP(x)Q(x)) 其中 是永真式。 15. 下列各式

(1).yxA(x,y) (2).xyA(x,y) (3).xy A(x,y) (4).xyA(x,y) 它们之间存在着 的推理关系。 可供选择的项有：

A.(1)(2)；(2) (3) B.(2) (1)；(3) (4) C.(1) (3)；(4) (3) D.(4) (1)；(1) (3) E.(1) (3)；(2) (4)

16. 填上联结词：xP(x)xQ(x) x(P(x)Q(x)) *17. 只用联结词，，，表示以下的公式。 (1).x(P(x)Q(x))= ① ；

(2).x(P(x)yQ(y))= ② ； (3).y(xP(x)Q(y))= ③ 。 18. 给定下面谓词公式：

(1).x(F(x)F(x)) (2).xF(x)xF(x)

(3).(F(x)(yG(x,y)F(x))) (4).xyF(x,y)xyF(x,y) (5).xF(x)xF(x)

(6).x(F(x)G(x))(xF(x)xG(x)) (7).xyF(x,y)xyF(x,y)

(8).x(F(x)G(x))(xF(x)xG(x)) (9).(xF(x)xG(x))x(F(x)G(x)) (10).xyF(x,y)yxF(x,y) (11).(xF(x)yG(y))yG(y)

上面11个公式中，为重言式的有 ① ，为矛盾式的有 ② 。 19. 给定下列各公式：

(1).(xF(x)yG(y))(F(u)zH(z)) (2).xF(y,x)yG(y) (3).x(F(x,y)yG(x,y))

则 ① 是(1)的前束范式， ② 是(2)的前束范式， ③ 是(3)的前束范式。 供选择的答案有

①xyz((F(x)G(y))(F(u)H(z))) ②xyz((F(x)G(y))(F(u)H(z))) ③xy(F(y,x)G(y)) ④xy(F(z,x)G(y)) ⑤xy(F(z,x)G(y)) ⑥xy(F(x,z)G(x,y)) ⑦xy(F(x,z)G(x,y)) ⑧yx(F(x,z)G(x,y)) ⑨yx(F(x,z)G(y))

20. 谓词公式xP(x)xQ(x)yR(y)的前束范式为 。

21. 谓词公式x(P(x)Q(x,y)zR(y,z))S(x)的前束范式为 。 *22. 谓词公式x(yG(y,b)H(x))的前束范式为 。 23. 在谓词逻辑中给出四个推理：

(1).前提：x(F(x)G(x))，yF(y)； 结论：yG(y) (2).前提：x(F(x)G(x))； 结论：yF(y) (3).前提：xF(x)，xG(x)； 结论：y(F(y)G(y))

(4).前提：x(F(x)H(x))，H(y)； 结论：x(F(x)) 以上四个推理中正确的有 。 24. 在谓词逻辑中构造下面推理的证明：

每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。

命题符号化：F(x)：x喜欢步行；G(x)：x喜欢坐汽车；H(x)：x喜欢骑自行车。 前提：x(F(x)G(x))，x(G(x)H(x))，x(H(x))； 结论：x(F(x))。

三、判断题

1. 在谓词公式中，一个变量只能是自由变量或约束变量中的一种。（） 2. 公式x(P(x)Q(x))R(y)中x的作用域为P(x)。（） 3. 同一谓词公式，指定不同的论域，其真值不一定相同。（） 4. 谓词公式xP(x)y(P(y))是矛盾式。（） *5. x(P(x)Q(x))(xP(x)xQ(x))为真。（）

6. 对公式z(P(z)Q(x,z)M(z,y))R(z)中自由变量代入后，有z(P(z)Q(a,z)M(z,b))R(z)（）

7. xy(P(x)Q(y))xP(x)yQ(y)（）

*8. P(x)，Q(x)表示谓词，P表示命题，有x(P(x)P)xP(x)P（） *9. x(A(x)B(x))xA(x)xB(x)（） *10. x(A(x)B(x))xA(x)xB(x)（）

11. 任意一个谓词公式都与一个前束范式等价。（）

12. 公式xP(x)yQ(x,y)前束范式xy(P(x)Q(x,y))为（）

13. 公式x(yP(x,y)(zQ(z)R(x)))的前束范式为xyz(P(x,y)Q(z)R(x))（） 14. 下面的推理：

条件：x(P(x)Q(x))，根据全称规定（US）有：P(a)Q(b)是正确的。（）

15. 对公式z(P(z)Q(x,z)M(z,y))R(z)中约束变量z改名后，得到的等价公式为： t(P9t)Q(x,t)M(t,y))R(t)（）

四、综合题

1. 用谓词和量词将下列命题符号化：

(1).没有不犯错误的人；

(2).尽管有人聪明，但未必一切人都很聪明； (3).每个计算机系的学生都学离散数学； (4).所有的人都学习和工作；

(5).并非一切推理都能用计算机完成； (6).任何自然数都有惟一的一个后继数。 *2. 令S(x,y,z)表示“x+y=z”，G(x,y)表示“x=y”，L(x,y)表示“x0当且仅当有这样的y，使得x≥y。 (2).并非对一切x，都存在y，使得x≤y。 (3).对任意的x，若x+y=x，当且仅当y=0。

3. 用谓词公式表示命题“xa”，并写出该命题的否定命题。

*4. 设P(x)：x是外语学的好的学生，Q(x)：x是三好学生，对下述自然语言用谓词符号化： (1).并不是外语学的好的都是三好学生。 (2).有这样的学生，外语学的好而不是三好学生，但外语学不好的学生一定不是三好学生。

5. 指出下列公式中量词每次出现的作用域，并指出个体变量是约束变量还是自由变

量。

limf(x)A

(1).xy(R(x,y)L(y,z))xH(x,y) (2).x(P(x)xQ(x))(xP(x)Q(x))

6. 设f,g,h是二元运算符号，E，L是二元谓词符号，考查的个体域为有理数集。给出

解释如下： f(x,y)=x·y； g(x,y)=x+y； h(x,y)=x2-y2； a=0； b=1； E(x,y):x=y； L(x,y):x根据上面的解释，以下公式中哪些为真，哪些为假？ (1).E(f(x,y),g(x,y)) (2).E(f(x,x),h(x,a)) (3).L(x,y)L(y,x) (4).xE(f(x,y),b)

(5).E(x,a)E(g(y,x),y)

7. 在谓词逻辑中将命题(1)(2)(3)符号化，并指出各命题的真值。对应的个体域分别为

①②③：

①非负整数集N； ②实数集R； ③整数集Z。

(1).对于任意的x，均有(x+1)2=x2+2x+1 (2).存在x，使得x+1=0 (3).存在x，使得5x=1

*8. 假设论域为自然数集N={1,2,3,……}，a为2，P为命题“2>1”；A(x)表示“x>1”；B(x)表示“x是某个自然数的平方”。请在此基础上，求下面公式的真值： x(A(x)(A(a)B(x))((PxA(x))B(a))

9. 下列各式翻译成自然语言，然后在不同的个体域中确定它们的真值：

(1).xy(x·y=0) (2).xy(x·y=0) (3).xy(x·y=1) (4).xy(x·y=1) (5).xy(x·y=x) (6).xy(x·y=x) (7).xyz(x-y=z)

个体域分别为：①实数集②整数集③正整数集④非负实数集

10. 设解释T如下：个体域为实数集R，元素a=0，函数f(x,y)=x-y，特定谓词F(x,y)为

x(2).xy(F(f(x,y),x))

(3).xyz(F(x,y)F(f(x,z),f(y,z))) (4).xyF(x,f(f(x,y),y)) 11. 求下面谓词公式

x(X(x)y(X(y)((Y(x,z)Y(y,z)p)t(X(t)(Y(x,t)Y(y,t)))))) 在赋值(z;p;X(x);Y(x,y))=(2;1;x是自然数;x12. 设解释T为：个体域为D＝{-2,3,6}，谓词F(x)：x≤3，G(x)：x>5，R(x)：x≤7。

根据解释T，求下列各式的真值： (1).x(F(x)G(x))

(2).x(R(x)F(x))G(5) (3).x(F(x)G(x))

13. 设A(x)是一个含有个体变量x的谓词公式，证明下面等值式成立：

xA(x)x(A(x))

14. 设A(x)，B(x)均为含有自由变量x的任意谓词公式，证明：

x(A(x)B(x))xA(x)xB(x)

15. 证明：xy(G(x)H(y))xG(x)xH(x)。

16. 设G(x)，H(x)分别是谓词公式，试证明xG(x)xH(x)x(G(x)H(x))

17. 下列公式是否成立，成立则证明，不成立，则举例说明之。 (1).xyA(x,y)xyA(x,y) (2).xA(x)xB(x)x(A(x)B(x)) 18. 下面公式是否是永真式？说明理由。 (1).(AxB(x))x(AB(x)) (2).x(A(x)B(x))(xA(x)xB(x))

19. 下面的公式是否是永真式？是则证明之，不是，请举出反例： (1).xyA(x,y)yxA(x,y) (2).(xA(x)xB(x))x(A(x)B(x))

20. 下面公式是否有效，对有效的公式加以证明，对无效的公式加以反驳。 (1).x(P(x)Q(x))(xP(x)xQ(x)) (2).(xP(x)xQ(x))x(P(x)Q(x))

21. 航海家都教育自己的孩子成为航海家，有一个人教育他的孩子去做飞行员，证明：这个人一定不是航海家。

22．指出下列推理中的错误：

(1). ①xF(x)G(x) 前提引入

②F(y)G(y) ①US (2). ①x(F(x)G(x)) 前提引入

②F(a)G(b) ①US (3). ①F(x)G(x) 前提引入

②y(F(y)G(y)) ①EG (4). ①F(x)G(c) 前提引入

②x(F(x)G(x)) ①EG (5). ①F(a)G(b) 前提引入

②x(F(x)G(x)) ①EG (6). ①x(F(x)G(x)) 前提引入

②y(H(y)R(y)) 前提引入 ③F(c)G(c) ①ES ④F(c) ③化简 ⑤H(c)R(c) ②ES ⑥H(c) ⑤化简 ⑦F(c)H(c) ④⑥合取 ⑧x(F(x)H(x)) ⑦EG

23. 试找出下列推理过程中的错误，写出正确的推导过程，说明理由： ①x(P(x)Q(x)) 条件

②P(y)Q(y) 全称规定(US) ③xP(x) 条件 ④P(y) 存在规定(ES) ⑤Q(y) 由条件②④ ⑥xQ(x) 存在推广(EG) 24. 下面推理是否是一个有效的推理，为什么？ ①xyQ(x,y) 条件

②yQ(a,y) 全称规定(US) ③Q(a,b) 存在规定(ES) ④xQ(x,b) 全称推广(UG) ⑤yxQ(x,y) 存在推广(EG) 25. 下面推广是否正确，若有错，请指出： x(A(x)B(x)) x(A(x)B(x)) ①

X(A(x)B(x)) ② x(A(x)B(x)) ③ (xA(x)xB(x)) ④

xA(x)x(B(x)) ⑤ xA(x)xB(x) ⑥ xA(x)xB(x) ⑦

26. 用谓词演算推理规则证明： x(P(x)(Q(y)R(x)))，xP(x)Q(y)x(P(x)R(x)) 27．改正下面证明中的错误：

前提：x(y(S(x,y)M(y))z(P(z)R(x,z)))； 结论：zP(z)xy(S(x,y)M(y))。 证明过程：

①x(y(S(x,y)M(y))z(P(z)R(x,z)))； ②y(S(b,y)M(y))z(P(z)R(b,z)) ③zP(z) ④z(P(z)) ⑤P(a) ⑥P(a)R(b,a) ⑦z(P(z)R(b,z)) ⑧z(P(z)R(b,z)) ⑨y(S(b,y)M(y)) ⑩y(S(b,y)M(y)) ⑾y(S(b,y)M(y)) ⑿xy(S(x,y)M(y)) ⒀zP(z)xy(S(x,y)M(y)) P ①US P(附加前提) ③T,E ④US T,⑤I ⑥UG ⑦T,E ②,⑧T,L ⑨T,E ⑩T,E ⑾UG CP

第三章

一、选择题

1. 对任意集合A、B、C，下述论断正确的是（）

A.若AB，BC，则AC B.若AB，BC，则AC C.若AB，BC，则AC D.若AB，BC，则AC 2. 设A-B=，则有（）

A.B= B.B C.AB D.AB

22

3. 设P={x|(x+1)≤4}，Q={x|x+16≥5x}，则下列选项正确的是（）

A.PQ B.PQ C.QP D.Q=P 4. 设A={{1,2,3},{4,5},{6,7,8}}，下列选项正确的是（）

A.1A B.{1,2,3}A C.{{4,5}}A D.A 5. 下列个选项错误的是（）

A. B. C.{} D.{}

32

6. 设A={x|x-x=0}，B={x|x-4<0,xZ}，C={x|y=2x-1}，D={x|x+y=5,xy=6}，则有（）

A.A=B B.A=C C.C=D D.C=A 7. 在0 之间填上正确的符号。 A.= B. C. D. 8. 设M={x|f1(x)=0}，N={x|f2(x)=0}，则方程f1(x)·f2(x)=0的解为（）

A.M∩N B.M∪N C.M⊕N D.M-N 9. 设A={a,{a}}，下列选项错误的是（）

A.{a}P(A) B.{a}P(A) C.{{a}}P(A) D.{{a}}P(A) 10. 设A={}，B=P(P(A))，下列选项错误的是（）

A.B B.{}B C.{{}}B D.{,{}}P(A) 11. 幂集P(P(P()))为（）

A.{{},{,{}}} B.{,{,{}},{}} C.{,{,{}},{{}},{}} D.{,{,{}}} *12.空集的幂集P()的基数是（） A.0 B.1 C.3 D.4

13. 集合A={1,2,…,10}上的关系R={|x+y=10,xA,yA}，则R的性质为（）

A.自反的 B.对称的 C.传递的，对称的 D.反自反的，传递的 14.设A={a,b,c}上的关系如下，有传递性的有（） A.ρ1={,,,} B.ρ2={,} C.ρ3={,,,} D.ρ4={}

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.若R和S是集合A上的两个关系，则下述结论正确的是（） A.若R和S是自反的，则R∩S也是自反的 B.若R和S是对称的，则RS也是对称的 C.若R和S是反对称的，则RS也是反对称的

D.若R和S是传递的，则R∪S也是传递的

17.设A={1,2,3,4,5}，ρ={|i,,,}，那么R是（） A.反自反的 B.反对称的 C.可传递的 D.不可传递的 19.设R和S是集合A上的等价关系，则R∪S的对称性（） A.一定成立 B.一定不成立 C.不一定成立 D.不可能成立 20.设R和S是非空集合A上的等价关系，下述各式是等价关系的为（） A.(A×A)-R B.R2 C.R-S D.r(R-S) 21.集合A上的关系R是相容关系的必要条件是（） A.自反、反对称的 B.反自反、对称的 C.传递、自反的 D.自反、对称的

是R的逆关系，则R∪R是（） 22.设R是集合A上的偏序关系，R A.偏序关系 B.等价关系 C.相容关系 D.都不是 23.设集合A中有4个元素，则A上的不同的等价关系的个数为（） A.11个 B.14个 C.15个 D.17个

二、填空题

1. 设M={1≤x≤12，x被2整除，x∈Z}，N={x|1≤x≤12，x被3整除，x∈Z}，则M∪N= ① ，M∩N ② 。

2. 设全集U={1,2,…,7}的子集为A={偶数}，B={奇数}，C={3的倍数}，则A∩B=

① ，A∩C= ② ，AC= ③ ,B∩C= ④ 。 3. 设集合A={x|x<3，xZ}，B={x|x=2k，kZ}，C={1,2,3,4,5}。

(1).AC= ① (2).(AB)∩C= ② (3).BB= ③ (4).A(C-B)= ④

4. 设I为整数集合，A={x|x2<30，xI}，B={x|x是素数，x<20}，C={1,3,5}。

(1).(A∩B)∪C= ① (2).(B-A)∪C= ② (3).(C-A)∩(B-A)= ③ (4).(B∩C)-A= ④ 5. 设全集U={1,2,3,…,20}，A、B、C是其子集，且A={x|x<4}，B={x|x2-6x-7=0}，

C={x|x2<100}。

(1).(A-B)∩C= ① (2).A∩B∩C= ②

(3).(A∩B)-C= ③

6. 设A、B是集合，求A与B之间的关系。

(1).如果A={1}，B={1,{1,2}}，则 ① (2).如果A=，B={}，则 ②

(3).如果A={a}，B={,a,{}}，则 ③ (4).如果A={}，B={,{}}，则 ④ 供选择项：

A. AB且AB B.AB且AB C. AB但AB D.AB且AB 7. 设A={{x,y},,x,y}，求下列各式的结果： A-{x,y}= ① ；A-{}= ② ；{{x,y}}-A= ③ ；

-A= ④ ；A的幂集P(A)= ⑤ 。 8. 集合A={,{a}}的幂集P(A)= 。 9. 集合A={{1,2},{3}},B={{1},{2},{3}}，试写出 A∪B= ① ，A∩B= ② ，P(A)= ③ 。 10. 设A={x|100(!).∩{}= ① (2).{,{}}-= ② (3).{,{}}-{}= ③ 13. 某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有17人两次考试都没有得优，那么两次考试都得优的学生人数是 。

14. 某学校有足球队员38人，篮球队员15人，排球队员20人，三队队员总数为58人，且其中只有3人同时参加3种球队，那么仅仅参加两种球队得队员人数是 。

15. 设A={a,b,c}，则集合S1={{a,b},{b,c}}，S2={{a},{a,b},{a,c}}，S3={{a},{b,c}}，S4={{a,b,c}}，S5={{a},{b},{c}}和S6={{a},{a,c}}中是A的完全覆盖的有 ① ，是A的划分的有 ② 。

16. 设D为同一平面上直线的集合，并且∥表示两直线间的平行关系，⊥表示两直线间的垂直关系，则∥2= ① ，⊥2= ② ，⊥3= ③ 。 17. 关系R是反自反的，当且仅当在关系矩阵中 ① ，在关系图上 ② 。 18. 关系R是对称的，当且仅当关系矩阵是 ① ，在关系图上 ② 。 19. 关系R是反对称的，当且仅当关系矩阵是 ① ，在关系图上 ② 。 20. 设A={1,2,3}上的关系R={<1,1>,<1,2>,<1,3>,<3,3>}，则关系R具备 ① 性，不具备 ② 性。

21. 设A={1,2,3,4}上关系R={<1,2>,<2,4>,<3,3>,<1,3>}，则r(R)= ① ，s(R)= ② 。

22. 设集合A仅含有3个元素，那么

(1).在A上可定义. 种不同的二元关系。 (2).在A上可定义 种不同的自反关系。 (3).在A上可定义 种不同的反自反关系。 (4).在A上可定义 种不同的对称关系。 (5).在A上可定义 种不同的反对称关系。 23. 如果R1和R2是A上的对称关系，有下列观点：

(1).R1∪R2是对称的 (2).R1∩R2是对称的 (3).R1R2是对称的

其中 是正确的。

24. 如果R1和R2是A上的反对称关系，有下列观点：

(1).R1∪R2是反对称的 (2).R1∩R2是反对称的 (3).R1R2是反对称的

其中 是正确的。

25. 如果R1和R2是A上的传递关系，有下列观点：

(1).R1∪R2是传递关系 (2).R1∩R2是传递关系 (3).R1R2是传递关系 (4).R12是传递关系

其中 是正确的。

26. R是A的二元关系，那么有下列观点：

(1).当R是自反关系时，R的传递闭包也是自反关系

(2). 当R是反自反关系时，R的传递闭包也是反自反关系 其中 是正确的。

27. R是A的二元关系，那么有下列观点：

(1).当R是对称关系时，R的传递闭包也是对称关系

(2). 当R是反对称关系时，R的传递闭包也是反对称关系 其中 是正确的。

28. 集合A={a,b,c,d,e,f,g}，A上的一个划分π={{a,b},{c,d,e},{f,g}}，那么π所对应的等价关系R应有 个有序对。

29. 设R是集合{1,2,…,10}上的模7同余关系，则[2]R= 。 30. 设R1和R2是A的相容关系，那么对于下列观点：

(1).R1∪R2是相容关系 (2).R1∩R2是相容关系 (3).R1R2是相容关系 其中 是正确的。

*31. 整数集上的小于关系“<”具有 ① ， ② 和 ③ 关系。 32. 设A={a,b,c}上偏序关系(P(A),)，则P(A)的子集B={,{a},{b},{a,b},{b,c}}的极大元是 ① ，最大元是 ② ，上界是 ③ ，下确界是 ④ 。

33. A={2,3,4,5,6,8,10,12,24}，R是A上的整除关系。那么A的极大元是 ① ，极小元是 ② 。

34. A={1,2,3,4,5,6,7,8,9,10,11,12}，R是A上的整除关系。子集B={2,4,6}，那么B的最大元是 ① ，B的最小元是 ② ，B的上界是 ③ ，B的下界是 ④ 。

35. A={1,2,3,4,5,6,8,10,24,36}，R是A上的整除关系。子集B={1,2,3,4}，那么B的上界是 ① ，B的下界是 ② ，B的上确界是 ③ ，B的下确界是 ④ 。

三、判断题

1. 若AB=AC，则B=C。（） 2. 若P∪Q=Q，P∩Q=，则P=。（） 3. {}{,{}}且{}{,{}}。（）

4. 设A={}，B=P(P(A))，则有{}B，且{}B。（） 5. A，B是集合，则命题AB和AB可能同时成立。（） 6. 设A，B为任意集合，则P(A-B)=P(A)-P(B)。（） 7. 若A-BB，则BA。（） 8. 对每个集合A，有{A}P(A)。（）

9. 设A与B是任意两个集合，若{A∩B,B-A}是A∪B的一个划分，则有A-B=。（） 10. 若{A-B,B-A}是集合A∪B的一个划分，则有A∩B=，其中A，B。（） 11. 设A，B是两个任意的集合，若{A∩B,A-B,B-A}是A∪B的一个划分，则有A∩B=，A-B=，B-A=。（）

12. 若{A∩B}是A∪B的一个划分，则有A-B=B-A=。（）

2

13. 若R是集合A上的传递关系，则R也是集合A上的传递关系。（）

14. 15. 16. 17. 18. 19. 20. 21.

也是对称的。若集合A上的关系R是对称的，则R（）

一个不是自反的关系，一定是反自反的。（）

集合A={1,2,3}的任何关系R都不可能既是对称的，又是反对称的。（） 集合A={a,b,c}上的关系R={,}是不可传递的。（）

若R和S是集合A上的任意两个自反关系，则RS也是自反的。（） 若R和S是集合A上的任意两个反自反关系，则RS也是反自反的。（） 若R和S是集合A上的任意两个对称关系，则RS也是对称的。（） 若R和S是集合A上的任意两个传递关系，则RS也是传递的。（）

22. 若R为集合A上的反对称关系，则t(R)一定是反对称的。（） 23. 设R和S是集合A上的关系，则有：

r(R∪S)=r(R)∪r(S)；（） s(R∪S)=s(R)∪s(S)；（） t(R∪S)t(R)∪t(S)；（）

24. 设R和S是集合A上的等价关系，则R∪S一定是等价的。（）

25. 设R和S是集合A上的两个相容关系，则RS和R∩S都是相容关系。（） 26. 平面上直线间的平行关系是等价关系。（）

27. 设人的集合A上的朋友关系为R，则R是A上的相容关系。（）

四、综合题

1. 举出集合A，B，C的例子，使其满足AB，BC，但AC。 2. 判断以下命题的真假：

(1).a{{a}} (2).{a}{{a}} (3).x{x}-{{x}} (4).{x}{x}-{{x}} (5).A-B=AB= (6).A-B=A=B (7).AA=A

(8).A-(B∪C)=(A-B)∩(A-C) (9).如果A∩B=B，则A=B

(10).A={x}∪x，则xA且xA

3. 设A，B，C，D是Z的子集，其中：

A={1,2,7,8} B={x2|x2<50且xZ} C={x|xZ且0≤x≤30且x可以被3整除} D={x|x=2k且kZ且0≤k≤6} 用描述法表示下面集合并计算： (1).A∪B∪C∪D (2).A∩B∩C∩D (3).B-(A∪C) (4).(A∩B)∪D

4. 设全集U={1,2,…,12}，A={1,3,5,7,9,11}，B={2,3,5,7,11}，C={2,3,6,12}，D={2,4,8}。

确定下面的集合：

(1)A∪B (2)A∩C (3)(A∪B)∩C (4)A-B (5)C-D (6)BD 5. A={{},{,1},{1,1, }}，B={{,1},{1}}。

计算A∪B，A∩B，A-B，P(A)。 6. 化简((A∪(B-C))∩A)∪(B-(B-A))。

第四章

第五章

一、选择题

*1. 设S={a,b}，则S上总共可定义的二元运算的个数是（） A.4 B.8 C.16 D.32

2. 设集合A={1,2,3,…,10}，下面定义的哪种运算关于集合A是不封闭的？（）

A. x*y=max{x,y} B. x*y=min{x,y}

C. x*y=GCD(x,y)，即x，y的最大公约数 D. x*y=LCM(x,y)，即x，y的最小公倍数

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

A.a*b=a-b B.a*b=max{a,b} C.a*b=a+2b D.a*b=|a-b| 4. 对自然数集N，下列哪种运算不是可结合的？（）

A.a*b=a+b+3 B.a*b=min{a,b} C.a*b=a+2b D.a*b=ab(mod 3) 5. 下列运算中，哪种运算关于整数集不能构成半群？（）

A.aοb=max{a,b} B.aοb=b C.aοb=2ab D.aοb=|a-b|

6.*运算如下表所示，哪个能使({a,b},*)成为独异点？（）

7. Q是有理数，(Q,*)（其中*为普通乘法）不能构成（）

A.群 B.独异点 C.半群 D.交换半群 8. R为实数集，运算*定义为：a,bR，a*b=a|b|，则代数系统(R,*)是（）

A.半群 B.独异点 C.群 D.阿贝尔群 *9. 下列代数系统(S,*)中，哪个是群？（）

A. S={0,1,3,5}，*是模7的加法 B. S=Q(有理数集合)，*是一般乘法 C. S=Z(整数集合)，*是一般乘法 D. S={1,3,4,5,9}，*是模11的乘法

10. 具有如下定义的代数系统(G,*)，哪个不够成群？（）

A. G={1,10}，*是模11的乘法 B. G={1,3,4,5,9}，*是模11的乘法 C. G=Q，*是普通加法 D. G=Q，*是普通乘法

*11. 设x，y是群（G,*）的任意两个元素，n是大于0的整数，xn表示n个x进行乘法运算，则下述等式中哪个不成立？（） A.(x*y)n=xn*yn B.(x*y)n+1=x*(y*x) n*y C.y*(x*y) n*y =(y*x) n*y D. (x*y) n*x= x*(y*x) n

*12. 任何一个有限群在同构的意义下可以看作是（） A.循环群 B.置换群 C.交换群 D.阿贝尔群

13. 设H，K是群(G,ο)的子群，下面哪个代数系统仍是(G,ο)的子群？（） A.(HK,ο) B.(H∩K,ο) C.(K-H,ο) D.(H-K,ο) 14. 任意一个具有多个等幂元的半群，它（）。

A.不能构成群 B.不一定能构成群 C.必能构成群 D.能构成交换群

*15. 设Z是整数集合，+是一般加法，则下述函数中哪一个不是群(Z,+)的自同态？（） A.f(x)=2x B.f(x)=1000x C.f(x)=|x| D.f(x)=0 16. 群(R,+)与(R-{0},×)之间的关系是（） A.同态 B.同构 C.后者是前者的子群 D.B，C均正确 17. 若(H,*)是(G,*)的真子群，且|H|=n，|G|=m，则有（） A.n整除m B.m整除n C.n整除m且m整除n D.n不整除m且m不整除n *18. 6阶群的任何非平凡子群一定不是（） A.2阶 B.3阶 C.4阶 D.6阶 19. 设Z是整数集，+，，分别是普通加法和乘法，则(Z,+,)是（） A.域 B.整环和域 C.整环 D.含零因子环 20. 下面哪个集合关于指定的运算构成环？（）

A.{a+b2|a,bZ}，关于数的加法和乘法 B.{n阶实数矩阵}，关于矩阵的加法和乘法 C.{a+b2|a,bZ}，关于数的加法和乘法

3

*21.+,为一般的加法和乘法，则下述代数系统中哪一个是整环？（） A. S={x|x=a+b3，a,bQ}

B. S={x|xZ且|x|有非1因子}∪{1} C. S={x|x=2n,nZ} D. S={x|x=2n+1,nZ}

22. 在代数系统中，整环和域的关系为（） A.整环一定是域 B.域不一定是整环 C.域一定是整环 D.域一定不是整环

二、填空题

*1. 集合A={a,b,c}上总共可定义的二元运算的个数为 。

2. 设S是非空有限集，代数系统(P(A),∪,∩)中，P(S)对∪运算的单位元是

① ，零元是 ② ，P(S)对∩运算的单位 * a b c 元是 ③ 。 a a b c 3. 设(S,*)是代数系统，其中S={a,b,c},*定义如表所示，则(S,*) ①

b b a a 半群，(S,*) ② 独异点，因为 ③ 。

c c a a 4. 在运算表中空白处填入适当符号，使({a,b,c},ο)成为群。 ο a b c 5. (G,*)是群，BG，且B是有限集，(B,*)是G的子群 a ① a ② 当且仅当 。

b a b c 1c ③ c ④ 6. 设(G,*)是非零实数乘法群，f：GG是同态映射，f(x)=x，则f(G)=

① ，Ker(f)= ② 。

7. 设H={0,4,8}，(H,+12)是群(N12,+12)的子群，其中N12={0,1,2,…,11}，+12是模12加法，则(N12,+12)有 ① 个真子群，H的左陪集3H= ② ，4H= ③ 。

8. 任意一个无限群有 个子群。 9. 设G={1,5,7,11}，(G,*)为群，其中*为模12乘法，则5的阶（周期）为 ① ，(G,*)有 ② 个真子群。

abba|a,bZ}，关于矩阵的加法和乘法 D.{三、判断题

1. 设(N,*)是代数系统，其中N为自然数集，*为二元运算，定义为：对任何的a,bN，有a*b=a，则*是可结合的。（）

2. 在一个代数系统中，若一个元素的逆元是惟一的，则运算必定是可结合的。（） 3. 设*是S上的可结合运算，若aS是可逆的，则a也是可约的。（） 4. 设*是S上的可结合运算，若aS是可约的，则a也是可逆的。（）

5. 设(A,ο,*)是一个代数系统，对于任意的a,bA，有aοb=a，而*是A上的任意二元运算，则*对ο不一定是可分配的。（） *6. 若半群有左单位元，则左单位元惟一。（）

7. (S,*)是独异点，a,bS，且a,b均有逆元，则(a*b)-1=a-1*b-1。（） 8. (S,*)是可交换独异点，T={x|xS,x*x=x}，则T也是独异点。（） 9. 有单位元且适合消去律的有限半群一定是群。（）

10. (G,*)是独异点，e是单位元，若对任意的aG，有a*a=e，则(G,*)是Abel群。（） 11. 设(G,*)是一个半群，若存在单位元且每个元素都有右逆元，则(G,*)是群。（） 12. 一个群可以有多个等幂元。（） 13. 任何一个Abel群不一定是循环群。（）

mn

14. 设G={23|m,nZ},×是普通乘法，则(G,×)不一定是群。（） 15. 设G是循环群，G同构于H，则H也是循环群。（） *16. 非循环群的每一个子群必是非循环群。（） *17. 4阶群中必有4阶元。（）

*18. 若H，K是群G的子群，则H∪K也是G的子群。（）

19. 设(G,+)是一个交换群，E是G的全体自同态构成的集合，对f,gE，令(f+g)(x)=f(x)+g(x)，xG，则(E,+)不是一个交换群。（） 20. 任一群都同构于变换群。（）

-1

21. 设G是一群，令f(x)=x，对任一xG，f是G的自同构当且仅当G是交换群。（） *22. f是群G到群H的同态映射，若G是交换群，则H也是交换群。（） 23. 在代数系统中域一定是整环。（）

24. 设A=

ab2baa,bZ ，则A关于矩阵的加法和乘法构成一整环。（）

第六章

第七章

一、选择题

1. 设D=为有向图，则有（）

A.EV×V B.EV×V C.V×VE D.V×V=E

2. 设G=为无环的无向图，|V|=6，|E|=16，则G是（）

A.完全图 B.零图 C.简单图 D.多重图 3. 含5个结点、3条边的不同构的简单图有（）

A.2个 B.3个 C.4个 D.5个 4. 设G为有n个结点的简单图，则有（）

A.△(G)n D.△(G)≥n 5. 设G=(n,m)，且G中每个结点的度数不是k就是k+1，则G中度为k的结点的个数

是（） A.n/2 B.n(n+1) C.nk D.n(k+1)-2m 6. 给定下列序列，可构成无向简单图的结点度数序列的是（）

A.(1,1,2,2,3) B.(1,1,2,2,2) C.(0,1,3,3,3) D.(1,3,4,4,5) 7. 图G和G’的结点和边分别存在一一对应关系是G和G’同构的（）

A.充分条件 B.必要条件 C.充要条件 D.既不充分也不必要条件 8. n个结点可构造的简单无向图（含同构图）的个数是（）

A.2 B.2 C.n 9. K4中含有3条边的不同构生成子图有（）

A.1个 B.3个 C.4个

n

n2

2

D.2n(n1)2

D.2个

10. 若简单图G与其补图G同构，称G为自补图。则含5个结点不同构的无向自补图

的个数为（） A.0 B.1 C.2 D.3 11. 设G=为无向图，u,vV，若u,v连通，则（）

A.d(u,v)>0 B.d(u,v)=0 C.d(u,v)<0 D.d(u,v)≥0 12. 任何无向图中结点间的连通关系是（）

A.偏序关系 B.等价关系 C.相容关系 D.拟序关系

13. 设D=为有向图，V={a,b,c,d,e,f}，E={,,,,}是（）

A.强连通图 B.单向连通图 C.弱连通图 D.不连通图 14. 设|V|>1，D=是强连通图，当且仅当（）

A. D中至少有一条通路 B. D中至少有一条回路

C. D中有通过每个结点至少一次的通路 D. D中有通过每个结点至少一次的回路

15. 设V={a,b,c,d}，则与V构成强连通图的边集为（）

A. E1={,,,,} B. E2={,,,,} C. E3={,,,,} D. E4={,,,,}

16. 无向图G中的边e是G的割边的充要条件是（）。

A.e是重边 B.e不是重边 C.e不包含在G的任一简单回路中 D.e不包含在G的某一回路中 17. 在有n个结点的连通图中，其边数（）

A.最多有n-1条 B.至少有n-1条 C.最多有n条 D.至少有n条

18. 设G=(n,m)为无向简单图，可构成邻接矩阵的数目为（）

A.n! B.m! 19. 欧拉回路是（）

A.路径 B.简单回路 C.既是基本回路也是简单回路 D.既非基本回路也非简单回路 20. 哈密尔顿回路是（）

A.路径 B.简单回路 C.既是基本回路也是简单回路 D.既非基本回路也非简单回路 21. 设G=(n,m)是欧拉图，则n，m有关系（）

A.n=m B.n，m的奇偶性必相同 C.n，m的奇偶性必相反 D.n，m的奇偶性既可相同也可相反

二、填空题

1. 设无向图G有12条边，有6个3度结点，其余结点度数均小于3，则G中至少有 个结点。

2. 设G＝（那么）是简单图，V是G中度数为k的结点，e是G中一条边，则G-v

中有 ① 个结点， ② 条边。G-e中有 ③ 个结点， ④ 条边。

3. 3个结点可构成 ① 个不同构的简单无向图，可构成 ② 个不同构的简单有向图。

4. 设G=(100,100)为无向连通图，则从G中能找到 条回路。

5. 设D是有向图，当且仅当D中有一条通过每个结点的通路时，D为 连通的。

6. 设有向图D=，V={a,b,c,d}，E={,,,,}，则D是 ① 连通的，e的可达集为 ② ，d(c,a)= ③ 。 7. K5的点连通度为 ① ，边连通度为 ② 。

mCnC.

nCmD.

0

11

8. 设图D=；V={v1,v2,v3,v4}，若D的邻接矩阵A=1

1

0100100

10110101

1

0100100

1100，

则deg-(v1)= ① ,deg+(v4)= ② ，从v2到v4长度为2的通路有 ③

条。

9. 无向图G有一条欧拉通路，当且仅当 。 10. 当n为 数时，Kn必为欧拉图。 11. Kn,m为哈密尔顿图，当且仅当 。

12. 若连通平面图G有4个结点，3个面，则G有 条边。 13. 仅当n 时，Kn为平面图。

14. 设G=(7,15)为简单平面图，则G一定是 ① ，且每个面均为 ② 。

三、判断题

1. 任一图G的△(G)必小于其结点数。（）

2. 3. 4. 5. 6.

在n个结点的简单图G中，若n为奇数，则G与G的度为奇数的结点数相同。（） K4有10个生成子图。（）

图G和G’同构当且仅当G和G’的结点和边分别存在一一对应关系。（） 具有3个结点的有向完全图，含4条边的不同构的子图有4个。（） 3个(4,2)无向简单图中，至少有2个同构。（）

7. 若无向图中恰有2个度为奇数的结点，则这两个结点必连通。（） 8. 在有向图中，结点间的可达关系是等价的。（）

9. 若有向图中有两个奇度结点，则它们一个可达另一个或相互可达。（） 10. 11. 12. 13. 14. 15. 16. 17. 18.

若图G不连通，则G必连通。（）

有向图的每个结点恰位于一个单向分图中。（）

若图G的边e不包含在图G的某简单回路中，则e是G的割边。（） 若无向连通图中无回路，则其每条边均为割边。（） 若有向图D强连通，则D必为欧拉图。（） 若有向图D是欧拉图，则D必为强连通图。（） Kn是哈密尔顿图。（） K5,3不是哈密尔顿图。（）

任一(n,m)平面图，若n≥3，则m≤3n-6。（）

19. 设G=，|V|≥11，则G或G是非平面图。（） 20. 极大平面图必连通。（）

21. 设G=为连通的简单平面图，若|V|≥3，则所有结点v，有deg(v) ≤5。（）