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

离散数学复习题及答案

离散数学复习题及答案文件排版存档编号：[UYTR-OUPT28-KBNTL98-UYNN208]

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

2.证明

答案：

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

答案：

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

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

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

所有鱼都生活在水中。

)

()(R P Q P ∨∧∧?

答案：

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

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

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

答案：

令 Q ( x )：x 是有理数 R ( x )：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 12. 请将下列命题符号化：

某些人对某些药物过敏。

答案：

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

(

))

(

)

(

→

?的对偶式:

答案：

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

答案：

15. 证明：

答案：

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), (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)} 其关系矩阵为

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 不是对称的。 ×

?R ?

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

由于(c,a)∈R ，且(a,c)∈R ，但(c,c) ，所以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)

答案：

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. 以下关系矩阵所代表的关系是什么关系

答案：

相容关系

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

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。

答案：

69. 求下列树的树根、树叶、树高、内点、分枝点、各个结点的层数

答案：

a是树根.

b,e,f,h,i是树叶.

c,d,g是内点.

a,c,d,g是分枝点.

a为0层;1层有b,c; 2层有d,e,f;

3层有g,h; 4层有i.

树高为4.

70. 求下列树的树高、内点数、分枝点树、几叉树

答案：

4、5、6、4

71. 下列树是不是完全二叉树是不是满二叉树

答案：

4叉树、完全3叉树

72. 求下列二叉树的前序、中序、后序遍历

答案：

前序：a → b → d → e → h → c → f → g → i → j 中序：d → b → h → e → a → f → c → i → g → j 后序：d → h → e → b → f → i → j → g → c → a 73. 求下列二叉树的前序、中序、后序遍历

答案：

74. 构造下列数的排序二叉树：15, 3, 1, 6, 18, 7, 10, 20答案：

75. 求树叶权为4，2，3，5，1的最优树。

答案：

最优树的权重W(T)为：

1×3 + 2×3 + 3×2 + 4×2 + 5×2 =33

76. 求带权图的最小生成树。

答案：

这棵最小生成树的权为:1+1+2+2+3+4=13.

77. 求下图的邻接矩阵

答案：

78.写出下列表达式的“波兰表示式”

((a – 4b) c – (7d + b)) / (c + 5a)

答案：先表示成二叉树的形式

再对二叉树进行前序遍历即的波兰式为：/ –×– a×4bc +×7db + c×5a

100道离散数学填空题分解

离散数学试题库——填空题（每空2分） 1 命题: ? ? {{a }} ? {{a },3,4,1} 的真值 = __ __ . 2. 设A= {a,b}, B = {x | x 2－(a+b) x+ab = 0}, 则两个集合的关系为: __ __. 3. 设集合A ＝{a ,b ,c },B ={a ,b }, 那么 P(B )－P(A )=__ __ . 4. 无孤立点的有限有向图有欧拉路的充分必要条件为: 5.公式))(),(()),()((x S z y R z y x Q x P x →?∨→?的自由变元是 , 约束变元是 . 6.)))()()(()),()(()((x R z Q z y x P y x →?→???的前束范式是 . 7．设 }7|{)},5()(|{<∈=<∈=+ x E x x B x N x x A 且且（N ：自然数集，E + 正偶数）则 =?B A 。 8．A ，B ，C 。 9．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 10．公式P R S R P ?∨∧∨∧)()(的主合取范式为。 11．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为。 12．设A={1，2，3，4}，A 上关系图为则 R 2 = 。 13．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为

则 R= 。 14．图的补图为。15．设A={a，b，c，d} ，A上二元运算如下：那么代数系统的，元的元素为，它们的逆元分别为。 16. P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为；“虽然你努力了，但还是失败了”的翻译为。 17. 论域D={1，2}，指定谓词P

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

离散数学试题（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 。

离散数学期末试题及答案

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的补元( ).

离散数学期末练习题-(带答案)

离散数学复习注意事项： 1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习情况，要认真理解,注意做题思路与方法。离散数学综合练习题一、选择题 1．下列句子中，（）是命题。 A．2是常数。B．这朵花多好看呀！ C．请把门关上！D．下午有会吗？ 2．令p: 今天下雪了，q:路滑，r:他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（）。 A. p q r ∨→ ∧→ B. p q r C. p q r ∨? ∧∧ D. p q r 3．令:p今天下雪了，:q路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。 A.p q ∧ ∧? B.p q C.p q →? ∨? D. p q 4．设() Q x:x会飞，命题“有的鸟不会飞”可符号化为（）。 P x:x是鸟，() A. ()(()()) Q x ??∧()) x P x Q x ??→ B. ()(() x P x C. ()(()()) Q x ??∧()) x P x Q x ??→ D. ()(() x P x 5.设() L x y：x大于等于y；命题“所有整数 f x:x的绝对值，(,) P x:x是整数，() 的绝对值大于等于0”可符号化为（）。 A. (()((),0)) ?→ x P x L f x ?∧B. (()((),0)) x P x L f x C. ()((),0) ?→ xP x L f x ?∧ D. ()((),0) xP x L f x 6.设() F x:x是人，() G x:x犯错误，命题“没有不犯错误的人”符号化为（）。 A．(()()) ??→? x F x G x ?∧B．(()()) x F x G x C．(()()) ??∧? x F x G x ??∧D．(()()) x F x G x 7.下列命题公式不是永真式的是（）。 A. () p q p →→ →→ B. () p q p C. () →∨ p q p p q p ?∨→ D. () 8．设() R x:x为有理数；() Q x:x为实数。命题“任何有理数都是实数”的符号化为（）

离散数学期末试卷及答案

一．判断题（共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)

离散数学期末测验试题（有几套带答案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，２}]＝｛１,４}。

离散数学练习题七

9.给定算式: {[(a ＋b)＊c]＊(d ＋e)}＋[f －(g ＊h)] 此算式的波兰符号表示式为( ), 逆波兰符号表示式为( ). A 、＋＊＊a ＋bc ＋def －g ＊h B 、＋＊＊＋abc ＋de －f ＊gh C 、＊－＊＋abc ＋de －fgh ＋ D 、ab ＋c ＊de ＋＊fgh ＊－＋ 10．设R,Z,N 分别为实数,整数和自然数集，函数f ：R →R ，f(x)＝x ，f 是（）; g: Z →N, g(x)＝|x|, g 是( ); h: N →N ×N. h(n)＝﹤n,n ＋1﹥,h({5})＝( ) A ．满射函数 B ．单射函数 C ．双射函数 D ．非单射非满射 E. 满射非单射 F.单射非满射 G ,<5,6> H,{<5,6>} J,以上答案都不对. 11. 75个学生去书店买语文,数学,英语书,每种书每个学生至多买1本.已知20个学生每人买3本书,55个学生每人至少买2本书.每本书的价格都是1元,所有学生总共花费 140元,恰好买2本书的有( )多少个学生.至少买2本书的学生花费( )元.买 1本书的有( )个学生.至少买1本书的有( )个学生.没买书的有( )个学生. A.55 B.40 C.35 D.15 E.30 F.130 G.65 H.140 J.60 K.10 12. 为每个逻辑断言选择正确的解释。T(x)：x 今天来上课，S(x)：x 学计算机专业的学生， P(x)：x 编程序，G(x)：x 玩游戏。个体域是殷都大学。 ?x T(x)表示（），??x T(x)表示（），?x ? T(x)表示（），?x(S(x)→P(x))表示（），?x(S(x)∧G(x))表示（），?x(S(x)∧P(x))表示（），?x(S(x)→G(x))表示（）。 A 学计算机专业的学生会编程序， B 殷都大学的学生都是计算机专业且会编程序。 C 有些计算机专业的学生玩游戏， D 所有同学今天都来上课了， E 今天有同学没来上课。 F 计算机专业的学生玩游戏， G 今天没有同学来上课。二、计算与应用题（共40分） 1. S={ 1，2，…，10 }，定义S 上的关系R={ | x,y ∈S ∧ x+y=10 }，试列举出R 中的所有有序对，并分析说明R 具有哪些性质。(10分)

离散数学试卷及答案

填空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、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：（1），（4） 2、下列公式中哪些是永真式？( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2），（3），（4），（5），（6） 4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。(5) 前进！ (6) 给我一杯水吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。答：所有人都不是大学生，有些人不会死 7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1） P Q→ ?（2）Q P? →（3）Q P? ?（4）Q P→ ? 8、设个体域为整数集，则下列公式的意义是( )。 (1) ?x?y(x+y=0) (2) ?y?x(x+y=0) 答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值： (1) ?x?y (xy=y) ( ) (2) ?x?y(x+y=y) ( ) (3) ?x?y(x+y=x) ( ) (4) ?x?y(y=2x) ( )答：（1） F （2） F （3）F （4）T 10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式?x(P(x)∨Q(x))在哪个个体域中为真?( ) (1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立答：（1） 11、命题“2是偶数或-3是负数”的否定是（）。答：2不是偶数且-3不是负数。 12、永真式的否定是（） (1) 永真式(2) 永假式(3) 可满足式(4) (1)--(3)均有可能答：（2） 13、公式(?P∧Q)∨(?P∧?Q)化简为（），公式 Q→(P∨(P∧Q))可化简为（）。答：?P ，Q→P 14、谓词公式?x(P(x)∨?yR(y))→Q(x)中量词?x的辖域是（）。答：P(x)∨?yR(y) 15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（）。

离散数学试卷及答案(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＞，｝

相关文档

 离散数学填空题及答案

离散数学试题及答案

离散数学期末试题答案

离散数学试卷及答案

离散数学期末考试

离散数学填空题

相关文档

离散数学期末练习试题[带答案]

离散数学填空题及答案

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

离散数学章练习题及答案

离散数学小测试题及答案

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

离散数学试题与答案94119

离散数学练习题及答案

离散数学模拟题及答案

离散数学练习题及答案

《离散数学》期末试题及答案

《离散数学》题库及答案

离散数学复习题题库-填空题

离散数学填空题及答案

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

《离散数学》试题及答案详解

离散数学填空题及答案解析

离散数学试题与答案

山东大学离散数学题库及答案(计本)

离散数学填空题及答案

最新文档

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

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

自然教育课件

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

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

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

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

高中语文知识点整理总结

高中语文知识点归纳

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

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

高考语文知识点总结高中

高中语文知识点总结归纳

高中语文知识点整理总结

高中语文知识点归纳

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

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

高中语文基础知识点整理

化工厂应急预案

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