当前位置：文档之家› 离散数学复习题及答案

离散数学复习题及答案

1. 写出命题公式﹁（P →（P ∨ Q ））的真值表。答案：

2.证明答案：

3. 证明以下蕴涵关系成立：答案：

4. 写出下列式子的主析取范式：答案：

)()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P)

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

Q)P ((Q)Q)P (P)Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)()()(R P Q P ∨∧∧?

5. 构造下列推理的论证：p ∨q, p →r, s →t, s →r, t q 答案：

①s →t 前提 ②t 前提

③s ①②拒取式I12 ④s →r 前提

⑤r ③④假言推理I11 ⑥p →r 前提

⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提

⑨q ⑦⑧析取三段论I10

6. 用反证法证明：p →((r ∧s)→q), p, s q

)

()(R P Q P ∨∧∧?)

()(R P Q P ∨∧?∨??))(())(R Q P P Q P ∧?∨?∨∧?∨??)

()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??)

()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??)

()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨)

()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??)

(Q R P ?∧∧?∨

7. 请将下列命题符号化：

所有鱼都生活在水中。

答案：

令 F( x )：x 是鱼 W( x )：x 生活在水中

))((W(x)F(x)x →?

8. 请将下列命题符号化：

存在着不是有理数的实数。

答案：

令 Q ( x )：x 是有理数 R ( x )：x 是实数

Q(x))x)(R(x)(?∧?

9. 请将下列命题符号化：

尽管有人聪明，但并非一切人都聪明。

答案：

令M(x)：x 是人 C(x)：x 是聪明的则上述命题符号化为

10. 请将下列命题符号化：

对于所有的正实数x,y ，都有x+y ≥x 。

答案：

令P(x):x 是正实数 S(x,y): x+y ≥x

11. 请将下列命题符号化：

每个人都要参加一些课外活动。

答案：

令P(x):x 是人 Q(y): y 是课外活动 S(x,y):x 参加y

)))()((())()((x C x M x x C x M x →??∧∧?)),()()((y x S y P x P y x →∧??))(),()((y Q y x S x P y x ∧→??

12. 请将下列命题符号化：

某些人对某些药物过敏。

答案：

令P(x):x 是人 Q(y): y 是药 S(x,y):x 对y 过敏

13. 求)())()((y yR y Q x P y ?→→?的对偶式: 答案：

14. 求下列谓词公式的前束范式：答案：

15. 证明：

答案：

)

,,()),(),((u y x uQ z y P z x zP y x ?→∧???)

,,()),(),((u y x uQ z y P z x zP y x ?∨∧?????)

,,()),(),((u y x uQ z y P z x P z y x ?∨?∨?????)

,,()),(),((u t s uQ z y P x P y x ?∨?∨?????ωω))

,,(),(),((u t s Q z y P x P u y x ∨?∨??????ωω))(),()((y Q y x S x P y x ∧∧??),,()),(),((u y x uQ z y P z x zP y x ?→∧???

16. 用反证法证明：

x(P(x)∧Q(x)) , xP(x) xQ(x)

答案：

17. 证明：

前提：x(C(x)W(x)∧R(x)), x(C(x)∧Q(x)).

结论：x(Q(x)∧R(x)).

答案：

(1) x(C(x)∧Q(x)) 前提引入

(2) C(a)∧Q(a) (1)ES

(3) C(a) (2)化简规则

(4) x(C(x)W(x)∧R(x)) 前提引入

(5) C(a)W(a)∧R(a) (4)US

(6) W(a)∧R(a) (3)(5)假言推理

(7) R(a) (6)化简规则

(8) Q(a) (2)化简规则

(9) R(a)∧Q(a) (7)(8)合取引入规则

(10) x(Q(x)∧R(x)) (9)EG

18. 判断：下列命题是否正确

答案：

(1) √

(2) ×

(3) √

(4) √

(5) √

(6) √

(7) √

(8) ×

19. 列出下列集合的元素

(1) {x|x∈N∧t(t∈{2,3}∧x=2t)}

(2) {x|x∈N∧ts(t∈{0,1}∧s∈{3,4}∧t

(3){x|x∈N∧t(t整除2x≠t)}

答案：

(1) {4,6}

(2) {1,2,3}

(3) {3,4,5…}

20.

S={0,1,2,3,4,5,6,7,8,9}，A={2,4,5,6,8}

B={1,4,5,9}，C={x|x∈Z+, 2≤x≤5}

答案：

21. 一个学校有507，292，312和344个学生分别选择了A,B,C,D四门课程。有14人选了A

和B，213人选了A和D，211人选了B和C ，43人选了C和D。没有学生同时选择A和C，也没有学生同时选择B和D。问共有多少学生在这四门课程中选了课

答案：

解：画文氏图

280+87+38+88 + 14+211+213+43

=974

22. 分别求下列集合的幂集

(1) (2){} (3){1,{,1}}

答案：

解:(1) ρ()={} 空集的幂集的基数为1

(2) ρ({})={,{} } 幂集的基数为2

(3) ρ({1,{,1}})={,{1},{{,1}},{1,{,1}}}

23.

A={0,1},B={1,2},C={3,4,5},求A×B, B×A, A×B×C, A2, C2 .

答案：

A×B={(0,1),(0,2),(1,1),(1,2)}

B×A={(1,0),(2,0),(1,1),(2,1)}

A×B×C={ (0,1,3), (0,1,4), (0,1,5), (0,2,3), (0,2,4), (0,2,5), (1,1,3), (1,1,4), (1,1,5), (1,2,3), (1,2,4), (1,2,5)}

A2 ={ (0,0), (0,1), (1,0), (1,1)}

C2 ={ (3,3), (3,4), (3,5), (4,3), (4,4),(4,5),(5,3), (5,4),(5,5)}

24.

1. 设A={{1,2,3}, {4,5}, {6,7,8}},下列选项正确的是（C）

A. 1∈A

B. {1,2,3} A

C. {{4,5}} A

D. ∈A

2. 设A={x|x3 –x=0}, B={x|x2 – 4<0,x∈z},C={x|y=2x-1},D={x|x+y=5, xy=6}则有（A）

A. A=B

B. A=C

C. C=D

D. C=A

25. 求关系的定义域和值域：

设A = {2，4，6，8}，R 是A 上的小于关系，即当a, b ∈A 且a< b 时，（a, b ）∈R ，求R 及D( R ),C( R )

答案：

R = {（2，4）,（2，6）,（2，8）,（4，6）,（4，8）,（6，8）}. R 的定义域D( R ) ={2，4，6}， R 的值域C( R ) = {4，6，8}。

26. 设A = {a, b, c, d },求A 上的恒等关系。答案：I A = {(a, a), (b, b), (c, c), (d, d)}。

27. 设A = {1,2,3,4,5}, R 是A 上的小于等于关系, 即当a ≤ b 时, (a, b) ∈R 。求R 的关系矩阵和关系图。答案：

解:易知A 上的小于等于关系为

R = {（1,1),(1,2),(1,3),(1,4),(1,5),(2,2),(2,3), (2,4),(2,5),(3,3),(3,4),(3,5), (4,4),(4,5),(5,5)} 其关系矩阵为

???

????????=1000011000111001111011111R M

28. X={a,b,c}，Y={1,2}，

关系R={(a,1),(b,2),(c,1)} S={(a,1),(b,1),(c,1)} 求R ∪S 、R ∩S 和R 的补答案：

29. 设A={1，2，3}，B ={a, b, c, d},C ={x, y, z}，R 是A 到B 的二元关系，R = {(1, a), (1, b), (2, b), (3, c)}，S 是B 到C 的二元关系，S = {(a, x), (b, x), (b, y), (b, z)}。求复合关系R οS 的关系矩阵. 答案：

30.

答案：

31. 设A = {a,b,c}，R 是A 上的二元关系， R = {(a,a), (b,b), (a,b), (a,c), (c,a)}，问：R 是自反的吗是反自反的吗是对称的吗是反对称的吗是可传递的吗答案：

由于c ∈A ，而(c,c) ，所以R 不是自反的。 × 由于(a,a)∈R ，(b,b)∈R ，所以R 不是反自反的。 ×

由于(a,b)∈R ，而(b,a) ，所以R 不是对称的。 ×

由于(a,c)∈R ，且(c,a)∈R ，所以R 不是反对称的。 ×

由于(c,a)∈R ，且(a,c)∈R ，但(c,c) ，所以

R 不是可传递的。 ×

R ?R ?R ?

32.

设A={1,2,3}，分析A 上的下述5个关系具有哪些性质： L={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>} N={<1,3>,<2,3>}

S={<1,2>,<2,1>,<1,3>} G={<1,1>,<1,2>,<2,3>} 答案：

33. 设A = {a, b, c, d}，A 上的关系，R = {(a, b), (b, a), (b, c), (c, d)} 求r(R)、s(R)、t(R) 答案：

34. A={a,b,c}, R={(a,b),(b,c),(c,a)}，求r(R), S(R)和t(R) 答案：

c)}(d,b),d),(c,(c,c),(b,a),(b,b),{(a,c)}(d,b),(c,b),(a,a),{(b,d)}(c,c),(b,a),(b,b),{(a,R R S(R)d)}(d,c),b),(c,(b,a),(a,d),(c,c),(b,a),(b,b),{(a,I R r(R)A

=====Y Y Y ~

342324

32R d)}(b,b),(b,c),(a,a),{(a,R R R c)}(b,a),(b,d),(a,b),{(a,R R R d)}(b,b),(b,c),(a,a),{(a,R R R 而R R R R t(R)========οοοY Y Y

35. A={1,2,3,4}，R={(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4)},判断R是否是等价的。

答案：

36. 判断下列关系是否为等价关系

(1) A={a,b,c,d}，R={(a,a),(b,a),(b,b),(c,c),(d,d),(d,c)}

(2) A={1,2,3,4}，

R={(1,1),(1,2),(1,3),(2,1),(2,2),(3,1),(2,3),(3,3),(4,4),(3,2)}

答案：

（1）×

（2）√

37. A={1,2,3,4}在幂集ρ(A)上定义的二元关系如下：R={(S,T)|S,T∈ρ(A)，|S|=|T|}，写出商集ρ(A)/R。

答案：

解：首先求ρ(A)。

ρ(A)={, {1},{2},{3},{4} , {1,2},{1,3} ,{1,4} ,{2,3} ,{2,4} ,{3,4}, {1,2,3} ,{1,2,4} ,{1,3,4} ,{2,3,4} ,

{1,2,3,4} } 共16个元素！

38. 设集合X={2166，243，375，648，455}

X 中的关系R 为： R={(x,y)|x,y ∈X ，并且x 和y 中有相同数字} 问：R 是不是相容关系答案：

39. A = {1，2，3，4，5，6，8，10，12，16，24}，R 是A 上的整除关系，请画出Ｒ的哈斯图。答案：

40. 已知偏序集的哈斯图如图所示, 试求出集合A 和关系R 的表达式. 求 A 的极小元、最小元、极大元、最大元. 设 B ＝{b,c,d}, 求 B 的下界、上界、最大下界、最小上界

答案：

极小元：a, b, c, g ；极大元：a, f, h ；没有最小元与最大元. B 的下界和最大下界都不存在, 上界有d 和 f, 最小上界为 d.

41. 以下关系矩阵所代表的关系是什么关系 ??????

???

?????=11100111

答案：

相容关系

42. 设集合A = {1，2，3，4，5，6，8，10，12，16，24}，R是A上的整除关系，请问关系R是否是偏序关系是否是全序关系画出Ｒ的哈斯图，并根据图求集合A的极大极小元、最大最小元，

设B={2，3，4}，求集合B的上界、最小上界、下界、最大下界。

答案：

是偏序关系，不是全序关系。

A的极大元：24,16,10

A的极小元：1

A的最大元：没有

A的最小元：1

B的上界：12,24

B的最小上界：12

B的下界：1

B的最大下界：1

43. 找出如下哈斯图中的子集{a,b,c}、{j,h}和{a,c,d,f}的上界和下界。

答案：

{a,b,c} 上界：e,f,j,h 下界：a

{j,h} 上界：无下界：f,d,e,b,c,a

{a,c,d,f} 上界：f,j,h 下界：a

44. 判断下列关系是否是映射是否是单射是否是满射

答案：

映射（非单射、非满射）、映射（满射）

映射（单射）、不是映射

45. X={x1,x2,x3}, Y={y1,y2}, Z={z1,z2}

f:X→Y，g:Y→Z，求h= gf

答案：

46.

下列哪些关系可以构成函数（映射）

a. f={(x,y)|x,y∈N, x+y<10}

b. f={(x,y)|x,y∈R, x2=y}

答案：

能

不能

47.

判断下列函数是单射、满射或双射

a. f:N→N, f(x)=x+2;

b. f:N→N, f(x)=x (mod 2);

c. f:N→ρ(N), f(x)={x};

答案：

单射

什么都不是

单射

48. f1°f = ，f°f1=

答案：

f1°f =I A，f°f1= I B

49.

构造下列函数的反函数：

(x)=sinx

(x)=x2, x∈(-∞，0)

={1,2,3},B={a,b,c},f:A→B, f={(1,a),(2,c),(3,b)}

答案：

f-1(x)=arcsinx

f-1(x)=-x1/2

f-1={(a,1),(c,2),(b,3)}

50.

答案：

51.

已知x={a,b,c },Y={1,2,3,4} f:X→Y如图所示, 试构造函数g:Y→X,使得g·f=Ix 答案：

g={(1,a),(2,c),(3,b),(4,a)}

52.

请给出图中各点的度数，以及图的最大度数和最小度数。

答案：

d(v1)=4, d(v2)=4, d(v3)=2, d(v4)=1, d(v5)=3

D(G)=4, d(G)=1

53. 请给出图中各点的出度和入，以及图的最大出度和最小入度。

答案：

d+(a)=4, d-(a)=1, d(a)=5,

d+(b)=0, d-(b)=3, d(b)=3,

+(D)=4, +(D)=0, (D)=3,

(D)=1,(D)=5, (D)=3.

54. (3,3,3,4), (2,3,4,6,8)能成为图的度数序列吗

答案：

不可能. 它们都有奇数个奇数.

55. 已知图G有10条边, 4个3度顶点, 其余顶点的度数均小于等于2, 问G至少有多少个顶点

答案：

设G有n个顶点. 由握手定理,

43+2(n-4)210

解得n8

56. 下面无向图中有几个顶点

(1) 16条边，每个顶点都是2度顶点

(2) 21条边，3个4度顶点，其余的都是3度顶点

(3) 35条边，每个顶点的度数至少为3的图最多有几个顶点

答案：

57. 确定下列各图的出度、入度和度数

答案：

58. 判断下列图是否同构

答案：

是

不是

是

59. 下图中，

1. 写出{a,d,e}的导出子图

2. 画出它的一个生成子图

3. 边集{e4,e7,e6}的导出子图

答案：

60. 试画出以下两个图的并图、交图和环和。

答案：

61. 判断下列各图是否是连通图：

答案：

是、不是

62. 指出下列有向图的连通性

答案：

强连通图单向连通图弱连通图强连通图单向连通图弱连通图

63. 求下列图的强连通分支

答案：

64.

（1）{e5}、{e2 、e3}、{e6}、{e4}是否是下图的边割集

（2）{v5}、{v2 、v4}、{v3}、{v1 、v2}、{v2 、v3}是否是下图的点割集

答案：

（1）是、是、是、否

（2）是、是、是、否、否

65. 求出下图的全部割点和桥

答案：

66. 下列图是否是树如果是，找出树的分枝结点和树叶。

答案：

不是、是

分枝结点：e,f

树叶：a, b, c, d, g, h

67. 设一棵树T有2个度数为2的结点，1个度数为3的结点，3个度数为4的结点，求T 有几片树叶。

答案：

68. 已知无向树T有5片树叶, 2度与3度顶点各1个, 其余顶点的度数均为4. 求T的阶数n。

答案：

(完整版)离散数学试卷及答案

离散数学试题（A卷答案）一、（10分）求(P↓Q)→(P∧?(Q∨?R))的主析取范式解：(P↓Q)→(P∧?(Q∨?R))??(?( P∨Q))∨(P∧?Q∧R)) ?(P∨Q)∨(P∧?Q∧R)) ?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R) ?(P∨Q)∧(P∨Q∨R) ?(P∨Q∨(R∧?R))∧(P∨Q∨R) ?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断：甲说：王教授不是苏州人，是上海人。乙说：王教授不是上海人，是苏州人。丙说：王教授既不是上海人，也不是杭州人。王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？解设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有：甲：?P∧Q 乙：?Q∧P 丙：?Q∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为：

((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。证明设R 是非空集合A 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，，，，，，，}， (1)写出R 的关系矩阵。 (2)判断R 是不是偏序关系，为什么？解 (1) R 的关系矩阵为： ??? ??? ? ? ? ?=100001100010100 10110 11111 )(R M (2)由关系矩阵可知，对角线上所有元素全为1，故R 是自反的；ij r ＋ji r ≤1，故R 是反对称的；可计算对应的关系矩阵为：

离散数学期末试题

离散数学考试试题（A 卷及答案）一、（10分）求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式解：(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断：甲说：王教授不是苏州人，是上海人。乙说：王教授不是上海人，是苏州人。丙说：王教授既不是上海人，也不是杭州人。王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？解设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。则根据题意应有：甲：?P ∧Q 乙：?Q ∧P 丙：?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P ，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。证明设R 是非空集合A 上的二元关系，则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。

离散数学考试试题(A卷及答案)

离散数学考试试题（A卷及答案）一、（10分）证明?(A∨B)→?(P∨Q)，P，(B→A)∨?P A。证明：(1)?(A∨B)→?(P∨Q) P (2)(P∨Q)→(A∨B) T(1)，E (3)P P (4)A∨B T(2)(3)，I (5)(B→A)∨?P P (6)B→A T(3)(5)，I (7)A∨?B T(6)，E (8)(A∨B)∧(A∨?B) T(4)(7)，I (9)A∧(B∨?B) T(8)，E (10)A T(9)，E 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。请推出哪两个人参加了围棋比赛。解符号化命题，设A：甲参加了比赛；B：乙参加了比赛；C：丙参加了比赛；D：丁参加了比赛。依题意有， (1)甲和乙只有一人参加，符号化为A⊕B?(?A∧B)∨(A∧?B)； (2)丙参加，丁必参加，符号化为C→D； (3)乙或丁至多参加一人，符号化为?(B∧D)； (4)丁不参加，甲也不会参加，符号化为?D→?A。所以原命题为：(A⊕B)∧(C→D)∧(?(B∧D))∧(?D→?A) ?((?A∧B)∨(A∧?B))∧(?C∨D)∧(?B∨?D)∧(D∨?A) ?((?A∧B∧?C)∨(A∧?B∧?C)∨(?A∧B∧D)∨(A∧?B∧D))∧((?B∧D)∨(?B∧?A)∨(?D∧?A)) ?(A∧?B∧?C∧D)∨(A∧?B∧D)∨(?A∧B∧?C∧?D)?T 但依据题意条件，有且仅有两人参加竞赛，故?A∧B∧?C∧?D为F。所以只有：(A∧?B∧?C∧D)∨(A∧?B∧D)?T，即甲、丁参加了围棋比赛。三、（10分）指出下列推理中，在哪些步骤上有错误？为什么？给出正确的推理形式。 (1)?x(P(x)→Q(x)) P (2)P(y)→Q(y) T(1)，US (3)?xP(x) P (4)P(y) T(3)，ES (5)Q(y) T(2)(4)，I (6)?xQ(x) T(5)，EG 解 (4)中ES错，因为对存在量词限制的变元x引用ES规则，只能将x换成某个个体常元c，而不能将其改为自由变元。所以应将(4)中P(y)改为P(c)，c为个体常元。正确的推理过程为： (1)?xP(x) P (2)P(c) T(1)，ES (3)?x(P(x)→Q(x)) P (4)P(c)→Q(c) T(3)，US (5)Q(c) T(2)(4)，I (6)?xQ(x) T(5)，EG 四、（10分）设A＝{a，b，c}，试给出A上的一个二元关系R，使其同时不满足自反性、反自反性、对称性、反对称性和传递性。解设R＝{，，，}，则

离散数学期末试题及答案

326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )，)(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 5. 设G 是(7, 15)简单平面图，则G 一定是( )图，且其每个面恰由( )条边围成，G 的面数为( ).

离散数学试题与答案

试卷二试题与参考答案一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统,其中A={a,b,c}, 则幺元就是 ;就是否有幂等性 ;就是否有对称性。 6、4阶群必就是群或群。 7、下面偏序格就是分配格的就是。 8、n 个结点的无向完全图K n 的边数为 ,欧拉图的充要条件就是。 * a b c a b c a b c b b c c c b

二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。

离散数学期末试题及答案完整版

离散数学期末试题及答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】

326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ).

离散数学期末考试试卷(A卷)

离散数学期末考试试卷(A卷) 一、判断题：（每题2分，共10分）（1）（1）（2）对任意的命题公式, 若, 则（0）（3）设是集合上的等价关系, 是由诱导的上的等价关系，则。（1）（4）任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价。（0）（5）设是上的关系，分别表示的对称和传递闭包，则（0）二、填空题：（每题2分，共10分） (１) 空集的幂集的幂集为（）。 (２) 写出的对偶式（）。（３）设是我校本科生全体构成的集合，两位同学等价当且仅当他们在同一个班，则等价类的个数为（），同学小王所在的等价类为（）。（４）设是上的关系，则满足下列性质的哪几条：自反的，对称的，传递的，反自反的，反对称的。（） (5)写出命题公式的两种等价公式( ）。三、用命题公式符号化下列命题（１）（２）（３），用谓词公式符号化下列命题（４）（５）（６）。（12分）（１）（１）仅当今晚有时间，我去看电影。（２）（２）假如上午不下雨，我去看电影，否则就在家里读书。（3）你能通你能通过考试，除非你不复习。（４）（４）并非发光的都是金子。（５）（５）有些男同志，既是教练员，又是国家选手。（６）（６）有一个数比任何数都大。四、设，给定上的两个关系和分别是

（１）（１）写出和的关系矩阵。（２）求及（1２分）五、求的主析取范式和主合取范式。（１０分）六、设是到的关系，是到的关系，证明：（8分）七、设是一个等价关系，设对某一个 ,有，证明：也是一个等价关系。（10分）八、（1０分）用命题推理理论来论证下述推证是否有效？甲、乙、丙、丁四人参加比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获胜，如果甲不获胜，则丁不失败。所以，如果丙获胜，则丁不失败。九、（１０分）用谓词推理理论来论证下述推证。任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或喜欢乘汽车，或喜欢骑自行车（可能这两种都喜欢）。有的人不爱骑自行车，因而有的人不爱步行 (论域是人)。十、(8分) 利用命题公式求解下列问题。甲、乙、丙、丁四人参加考试后，有人问他们，谁的成绩最好，甲说：“不是我，”乙说：“是丁，”丙说：“是乙，” 丁说：“不是我。” 四人的回答只有一人符合实际，问若只有一人成绩最好，是谁？离散数学期末考试试卷答案(A 卷) 一、判断题：（每题2分，共10分）（1）}}{{}{x x x -∈ （ ∨） (2) 对任意的命题公式C B A ,,, 若 C B C A ∧?∧, 则B A ? ( ? ) （3）设R 是集合A 上的等价关系, L 是由 R A 诱导的A 上的等价关系，则L R =。 ( ∨ ) （4）任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价。（ ? ）（5）设R 是A 上的关系，)(),(R t R s 分别表示R 的对称和传递闭包，则 )()(R st R ts ? （ ? ）二、填空题：（每题2分，共10分）

离散数学期末试卷及答案

一．判断题（共10小题，每题1分，共10分）在各题末尾的括号内画表示正确，画表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法构成环。( ) 8．若无向连通图G中有桥，则G的点连通度和边连通度皆为1。( ) 9．设A={a,b,c},则A上的关系R={,}是传递的。( ) 10．设A、B、C为任意集合，则A?(B?C)=(A?B)?C。( ) 二、填空题（共10题，每题3分，共30分） 11．设p：天气热。q：他去游泳。则命题“只有天气热，他才去游泳”可符号化为。 12．设M(x)：x是人。S(x)：x到过月球。则命题“有人到过月球”可符号化为。 13．p?q的主合取范式是。 14．完全二部图K r,s（r < s）的边连通度等于。 15．设A={a,b}，,则A上共有个不同的偏序关系。 16．模6加群中，4是阶元。 17．设A={1,2,3,4,5}上的关系R={<1,3>,<1,5>,<2,5>,<3,3>,<4,5>}，则R的传递闭包t(R) = 。. 18．已知有向图D的度数列为(2,3,2,3)，出度列为(1,2,1,1)，则有向图D的入度

列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{,}，则R是A上的等价关系。求等价类[a]R、[c]R及商集A/R。 24．求图示带权图中的最小生成树，并计算最小生成树的权。 25．设R*为正实数集，代数系统< R*,+>、< R*,·>、< R*,/>中的运算依次为普通加法、乘法和除法运算。试确定这三个代数系统是否为群？是群者，求其单位元及每个元素的逆元。四、证明题（共3小题，共20分） 26 （8分）在自然推理系统P中构造下述推理的证明：前题：p→(q∨r)，?s→?q，p∧?s 结论：r 27 （6分）设是群，H={a| a∈G∧?g∈G，a*g=g*a},则是G的子群 28．（6分）设G是n(≥3)阶m条边、r个面的极大平面图，则r=2n-4。

离散数学期末试卷A卷及答案

《离散数学》试卷（A 卷）一、选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???.

2、公式)(Q P Q ?∨∧的主合取范式为。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。（ F ） 2、“张刚和小强是同桌。”是复合命题。（ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。（ T ） 4、)(T S R T R S R ??????。（ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。（ T ） 6、若f 、g 分别是单射,则g f ?是单射。（ T ） 7、若g f ?是满射，则g 是满射。（ F ） 8、若A B ?，则)()(A P B P ?。（ T ） 9、若R 具有自反性，则1-R 也具有自反性。（ T ） 10、B A ∈并且B A ?不可以同时成立。（F ）四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问（１）三门课程都不选的学生有多少？（２）只选修计算机课程的学生有多少？

离散数学试卷二十三试题与答案

试卷二十三试题与答案一、单项选择题：（每小题1分，本大题共10分） 1．命题公式)(P Q P ∨→是（）。 A 、矛盾式； B 、可满足式； C 、重言式； D 、等价式。 2．下列各式中哪个不成立（）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨?； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。 3．谓词公式)())()((x Q y yR x P x →?∨?中的 x 是（）。 A 、自由变元； B 、约束变元； C 、既是自由变元又是约束变元； D 、既不是自由变元又不是约束变元。 4．在0 Φ之间应填入（）符号。 A 、= ； B 、?； C 、∈； D 、?。 5．设< A ， > 是偏序集，A B ?，下面结论正确的是（）。 A 、 B 的极大元B b ∈且唯一； B 、B 的极大元A b ∈且不唯一； C 、B 的上界B b ∈且不唯一； D 、B 的上确界A b ∈且唯一。 6．在自然数集N 上，下列（）运算是可结合的。（对任意N b a ∈,） A 、b a b a -=*； B 、),max(b a b a =*； C 、b a b a 5+=*； D 、b a b a -=*。 7．Q 为有理数集N ，Q 上定义运算*为a*b = a + b – ab ,则的幺元为（）。 A 、a ； B 、b ； C 、1； D 、0。 8．给定下列序列，（）可以构成无向简单图的结点度数序列。 A 、（1，1，2，2，3）； B 、（1，1，2，2，2）； C 、（0，1，3，3，3）； D 、（1，3，4，4，5）。 9．设G 是简单有向图，可达矩阵P(G)刻划下列（）关系。 A 、点与边； B 、边与点； C 、点与点； D 、边与边。 10．一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（）。 A 、5； B 、7； C 、9； D 、8。

离散数学期末测验试题(有几套带答案1)

离散数学期末测验试题（有几套带答案1)

————————————————————————————————作者: ————————————————————————————————日期: ?

离散数学试题(A卷及答案）一、证明题（10分）１)(?P∧(?Q∧Ｒ)）∨(Q∧R）∨(P∧R）?Ｒ证明：左端?(?P∧?Q∧R)∨（(Q∨Ｐ)∧R)?（(?P∧?Q)∧R))∨((Ｑ∨Ｐ)∧R） ?(?(P∨Q）∧R)∨((Q∨P)∧Ｒ)?(?(P∨Q)∨(Ｑ∨Ｐ))∧R ?(?(P∨Q)∨(Ｐ∨Ｑ))∧R?T∧R(置换）?R 2）?x(Ａ（ｘ)→B(x)）??xＡ(x）→?xB(x) 证明:?x(A(x)→Ｂ(x））??x（?A（x)∨B(x))??x?A(x)∨?xB(x)???xA（x)∨?xB(x)??xA(x)→?xＢ(ｘ）二、求命题公式(P∨(Q∧Ｒ))→(Ｐ∧Q∧R）的主析取范式和主合取范式(１０分) 证明:(P∨（Ｑ∧Ｒ））→(P∧Q∧R)??(P∨(Ｑ∧Ｒ）)∨（P∧Q∧R)) ?（?P∧（?Q∨?R)）∨(Ｐ∧Q∧Ｒ） ?(?P∧?Ｑ)∨(?P∧?R)）∨(Ｐ∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Ｑ∧?R）∨(?Ｐ∧Q∧?R)）∨(?P∧?Q∧?R)）∨(Ｐ∧Ｑ∧R) ?m0∨ｍ1∨m2∨ｍ７ ?Ｍ3∨M4∨M5∨M6 三、推理证明题(10分) 1）Ｃ∨D， (C∨D)→?E, ?Ｅ→(A∧?B), (A∧?B)→(R ∨S)?R∨S 证明:(1) (C∨D）→?E (２) ?E→（A∧?Ｂ) ?? (3）（C∨D）→（A∧?Ｂ) （４) （Ａ∧?B)→(R∨Ｓ) ?? (5) （C∨D）→（R∨Ｓ) ? (6) C∨Ｄ?? (7) R∨S 2) ?x(P(ｘ)→Q(ｙ）∧R(x)），?xP(x)?Q(y）∧?x（P(x)∧R(x)) 证明（1)?xP(ｘ) (2）P(a) （3)?ｘ(P(x)→Q(y）∧R(x)) (4）P（a)→Q(y)∧R(a) (５)Q(y)∧Ｒ(a) (6)Q(y) （７)R(a） (8)P(a) (9)P(ａ)∧R(a) （10)?x(Ｐ(x)∧R(ｘ)) (11)Q（ｙ)∧?x(P（x）∧R(x)）五、已知Ａ、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C) （１5分) 证明∵x∈A-（Ｂ∪C)?x∈A∧x?（Ｂ∪C)?x∈A∧(x?Ｂ∧ｘ?C）?(x∈A∧x?B)∧（x∈A∧x?C）?x∈（Ａ-B)∧ｘ∈(A－C）?x∈(A－B）∩（A-Ｃ)∴A-(B∪Ｃ）=（A-B)∩(A-C）六、已知R、S是N上的关系，其定义如下：Ｒ=｛＜x，ｙ>| x，y∈N∧y=x2｝，Ｓ={| x,y∈Ｎ∧ｙ=x2｝，R*S=｛｜ｘ,ｙ∈N∧y=x2+1},S＊R={| x,y∈Ｎ∧ｙ=(x+１)2}, 七、若ｆ:A→B和ｇ:B→C是双射，则(gf)－１＝f－1g-1(1０分）。证明：因为ｆ、ｇ是双射,所以ｇf:A→C是双射，所以ｇf有逆函数(gf）-１：C→Ａ。同理可推f-1g－1：Ｃ→Ａ是双射。因为∈ｆ-1g-1?存在ｚ(∈g-1∧∈f∧<ｚ,ｘ>∈g)?∈ｇf?＜x,y＞∈（gf）-1,所以(gf)-1＝f-１g-1。 R{１，２}＝{<1,1＞，<２,4>},S[{1，２}]＝｛１,４}。

离散数学试卷及答案

填空10% （每小题 2 分） 1、若P，Q，为二命题，P Q 真值为0 当且仅当。 2、命题“对于任意给定的正实数，都存在比它大的实数” 令F（x）：x 为实数，L（x, y） : x y 则命题的逻辑谓词公式为。 3、谓词合式公式xP（x） xQ（x）的前束范式为。 4、将量词辖域中出现的和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为换名规则。 5、设x 是谓词合式公式A的一个客体变元，A的论域为D，A（x）关于y 是自由的，则被称为存在量词消去规则，记为ES。选择25% （每小题分） 1、下列语句是命题的有（）。 A、明年中秋节的晚上是晴天； C、xy 0 当且仅当x 和y 都大于0； D 、我正在说谎。 2、下列各命题中真值为真的命题有（）。 A、2+2=4当且仅当3是奇数； B、2+2=4当且仅当 3 不是奇数； C、2+2≠4 当且仅当3是奇数； D、2+2≠4当且仅当 3 不是奇数； 3、下列符号串是合式公式的有（） A、P Q ； B、P P Q； C、( P Q) (P Q)； D、(P Q) 。 4、下列等价式成立的有（）。 A、P QQ P ； B、P(P R) R； C、P (P Q) Q； D 、P (Q R) (P Q) R。 5、若A1,A2 A n和B为 wff ，且A1 A2 A n B 则（）。 A、称A1 A2 A n 为 B 的前件； B 、称 B 为A1,A2 A n 的有效结论

C 、 x(M (x) Mortal (x)) ； D 、 x(M(x) Mortal (x)) 8、公式 A x(P(x) Q(x))的解释 I 为：个体域 D={2} ，P(x) ：x>3, Q(x) ：x=4则 A 的真值为（）。 A 、 1； B 、 0； C 、可满足式； D 、无法判定。 9、下列等价关系正确的是（）。 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) xP(x) Q ； D 、 x(P(x) Q) xP(x) Q 。 10 、下列推理步骤错在（）。 ① x(F(x) G(x)) P ② F(y) G(y) US ① ③ xF(x) P ④ F(y) ES ③ ⑤G(y) T ②④I ⑥ xG(x) EG ⑤ A 、②； B 、④； C 、⑤； D 、⑥ 逻辑判断 30% 1、用等值演算法和真值表法判断公式 A ((P Q) (Q P)) (P Q) 的类型。 C 、当且仅当 A 1 A 2 A n D 、当且仅当 A 1 A 2 A n B F 。 6、 A ，B 为二合式公式，且 B ，则（）。 7、 A 、 A C 、 A B 为重言式； B 、 B ； E 、 A B 为重言式。人总是要死的”谓词公式表示为（）。论域为全总个体域） M （x ）： x 是人； Mortal(x) x 是要死的。 A 、 M (x) Mortal (x) ； B M (x) Mortal (x)

离散数学试卷及答案(1)

一、填空 20% （每小题2分） 1．设 }7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且（N ：自然数集，E + 正偶数）则 =?B A 。 2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为。 3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 4．公式P R S R P ?∨∧∨∧)()(的主合取范式为。 5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为。 6．设A={1，2，3，4}，A 上关系图为则 R 2 = 。 7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为则 R= 。

8．图的补图为。 9．设A={a ，b ，c ，d} ，A 上二元运算如下：那么代数系统的幺元是，有逆元的元素为，它们的逆元分别为。 10．下图所示的偏序集中，是格的为。二、选择 20% （每小题 2分） 1、下列是真命题的有（） A ． }}{{}{a a ? ； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（） A ．{4，3}Φ?； B ．{Φ，3，4}； C ．{4，Φ，3，3}； D ． {3，4}。 3、设A={1，2，3}，则A 上的二元关系有（）个。

A．23 ；B．32 ；C．332?；D．223?。 4、设R，S是集合A上的关系，则下列说法正确的是（） R 是自反的； A．若R，S 是自反的，则S R 是反自反的； B．若R，S 是反自反的，则S R 是对称的； C．若R，S 是对称的，则S R 是传递的。 D．若R，S 是传递的，则S 5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下 t s p R= t s ∈ =则P（A）/ R=（） < > ∧ A ) (| || |} ( , {t , | s A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}} 6、设A={Φ，{1}，{1，3}，{1，2，3}}则A上包含关系“?”的哈斯图为（） 7、下列函数是双射的为（） A．f : I→E , f (x) = 2x ；B．f : N→N?N, f (n) = ； C．f : R→I , f (x) = [x] ；D．f :I→N, f (x) = | x | 。（注：I—整数集，E—偶数集，N—自然数集，R—实数集） 8、图中从v1到v3长度为3 的通路有（）条。 A．0；B．1；C．2；D．3。 9、下图中既不是Eular图，也不是Hamilton图的图是（）

离散数学期末考试试题及答案

离散数学试题(Ｂ卷答案１）一、证明题(10分） 1）(P∧（Ｑ∧Ｒ）)∨(Q∧R）∨（Ｐ∧R)R 证明: 左端(P∧Q∧Ｒ）∨((Q∨P）∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((Ｐ∨Ｑ）∧R）∨((Ｑ∨P)∧Ｒ) (（P∨Q）∨（Ｑ∨P))∧Ｒ（(P∨Ｑ)∨(Ｐ∨Q))∧R T∧Ｒ(置换)Ｒ 2) x (A(x)B(ｘ）)xA(x)xＢ(ｘ) 证明：x(A(ｘ)B(x))x(Ａ(ｘ)∨B(x)） x A(ｘ)∨xB（ｘ) xA(x)∨xB(x） xＡ(x)xB(x) 二、求命题公式(P∨（Q∧R)）(P∧Q∧R)的主析取范式和主合取范式(10分）。证明：(P∨（Q∧R))(P∧Q∧R)（P∨(Q∧R)）∨(P∧Q∧R)) (P∧(Q∨Ｒ))∨（P∧Q∧Ｒ）（Ｐ∧Q)∨（P∧R)）∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧Ｒ)∨(P∧Q∧Ｒ))∨(P∧Ｑ∧R）)∨(Ｐ∧Q∧R） m0∨ｍ1∨m２∨ｍ７Ｍ３∨M４∨Ｍ５∨M6 三、推理证明题（１0分) 1）Ｃ∨D，（C∨D)E, E(A∧B)，(A∧Ｂ)(R∨S)R∨Ｓ证明：(１） (C∨D) E ?P (2) E（A∧Ｂ) ??P （3) (Ｃ∨D）（A∧B) Ｔ（1）(2），I (4) （A∧B)(R∨S）??P (5) (Ｃ∨D)(Ｒ∨S) ? T(3)(4)，I (6） C∨Ｄ P (7) R∨S T(5)，I 2) x(P(ｘ)Ｑ(y)∧R(ｘ)），xＰ(ｘ)Q（y)∧x(Ｐ(x)∧R(x)) 证明(1)ｘP(x) Ｐ

（2)Ｐ(ａ） T(1），ＥS (3)ｘ（P(x)Q（y)∧R(x）) Ｐ (４)P(a)Q（y)∧R(a） T(3)，ＵS (５)Q（ｙ)∧R(a） T(2)（4），I （6）Q(y) Ｔ(５)，I （7)R(ａ) T(5),I (8)P(a)∧Ｒ（ａ) T(2)(7),I （9)x(Ｐ(x）∧R(x)) Ｔ(8),ＥG (10)Q(ｙ)∧x(P(x)∧R(ｘ)) Ｔ(６）(9)，I 四、某班有２5名学生,其中14人会打篮球,１2人会打排球，6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。解：A，B,C分别表示会打排球、网球和篮球的学生集合。则｜A|=1２，|Ｂ|＝6,｜Ｃ|=14，｜A∩C|=6，｜B∩C｜=5，|Ａ∩Ｂ∩C｜=２。先求|A∩B|。 ∵6＝|（Ａ∪C)∩B|=|（A∩B）∪（Ｂ∩C)|=|（A∩B）|＋|（B∩C）｜-|A∩B∩C|=|(Ａ∩B)|+5-２，∴|(A∩B）|=３。于是|A∪Ｂ∪C｜=12+6+14-6-5－３＋２=20。不会打这三种球的人数25-20=5。五、已知Ａ、B、Ｃ是三个集合,证明A-(B∪Ｃ)=(A-B)∩(Ａ-C）(10分)。证明：∵x A-（B∪C） x A∧x（B∪C） xＡ∧(xＢ∧x C）（x A∧x B）∧(x A∧ｘC） x（A-B）∧x(Ａ-C）ｘ（Ａ-Ｂ）∩(A-C） ∴Ａ-（B∪Ｃ)=（Ａ－B）∩(A－Ｃ）六、已知R、S是Ｎ上的关系,其定义如下：R={| x,ｙN∧y=ｘ2} R*S＝｛| x，y N∧y＝x２+1} Ｓ*R=｛<ｘ,y>| x,ｙN∧y=(x＋1)２},R{1，２}＝{＜1，1>，＜2，４>｝,Ｓ[{1,2}]={1,4}。七、设Ｒ={<ａ，b>,,＜c，ａ>}，求ｒ(R)、s(Ｒ)和t(Ｒ) （１5分）。解：r(R）=｛,，,,<ｂ,b＞，｝

离散数学期末考试试题(有几套带答案)

离散数学试题(A卷及答案）一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R)?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R?T∧R(置换)?R 2)?x(A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x))??x?A(x)∨?xB(x)???xA(x)∨?xB(x)??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）证明：(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) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D, (C∨D)→?E, ?E→(A ∧?B), (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E (2) ?E→(A∧?B) (3) (C∨D)→(A∧?B) (4) (A∧?B)→(R∨S) (5) (C∨D)→(R∨S) (6) C∨D (7) R∨S 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明（1）?xP(x) (2)P(a) (3)?x(P(x)→Q(y)∧R(x)) (4)P(a)→Q(y)∧R(a) (5)Q(y)∧R(a)

相关主题

 离散数学试题及答案

离散数学期末试题

离散数学期末试题答案

离散数学试卷及答案

离散数学期末考试

离散数学考试试题

文本预览

相关文档

离散数学试卷及答案

离散数学期末考试题及答案

《离散数学》试题及答案

离散数学试卷与答案

(完整版)离散数学试卷及答案

离散数学练习题及答案

离散数学试卷六试题与答案

离散数学试题及答案

离散数学试题及答案

《离散数学》考试题库及答案

离散数学期末试卷及答案

离散数学试题及答案

离散数学试题及答案

《离散数学》试题及答案

离散数学练习题(含答案)

离散数学试题及答案

离散数学试题及答案

离散数学试卷及参考答案()

离散数学试卷及答案

离散数学试题与答案94119

最新文档

幼儿园小班科学《小动物过冬》PPT课件教案

2021年春新青岛版(五四制)科学四年级下册 20.《露和霜》教学课件

自然教育课件

小学语文优质课火烧云教材分析及课件

(超详)高中语文知识点归纳汇总

高中语文基础知识点总结(5篇)

高中语文基础知识点总结(最新)

高中语文知识点整理总结

高中语文知识点归纳

高中语文基础知识点总结大全

超详细的高中语文知识点归纳

高考语文知识点总结高中

高中语文知识点总结归纳

高中语文知识点整理总结

高中语文知识点归纳

高中语文知识点归纳(大全)

高中语文知识点总结归纳(汇总8篇)

高中语文基础知识点整理

化工厂应急预案

化工消防应急预案(精选8篇)