《离散数学》试卷A&答案

《离散数学》试卷A&答案

第1学期

《离散数学》试卷 A

（试卷共6页，答题时间120分钟）

一、选择题（每小题 2分，共 20 分。请将答案

填在下面的表格内）

1、从集合分类的角度看,命题公式可分为( )

A.永真式、矛盾式 B. 永真式、可满足式、矛盾式 C. 可满足式、矛盾式 D. 永真式、可满足式 2、设B不含有x， x(A(x) B)等值于 ( )

A. xA(x) B B. x(A(x) B) C. xA(x) B D. x(A(x) B) 3、设S,T,M是集合，下列结论正确的是（ ）

A．如果S∪T=S∪M，则T=M B．如果S-T=Φ，则S=T C．S S S D．S T S (~T) 4、设R是集合A上的偏序关系，则R不一定是( )

A.自反的 B.

对称的 C. 反对称的 D. 传递的 5 设R为实数集，定义R上4个二元运算，不满足结合律的是（ ）。 A. f1(x,y)= x+y B. f2(x,y)=x-y C. f3(x,y)=xy

D. f4(x,y)=max{x,y}

《离散数学》试卷A&答案

6、设<L, , >是一个格，则它不满足( )

A.交换律 B. 结合律 C. 吸收律 D. 消去律 7、设A={1,2},则群 P(A), 的单位元和零元是( )

A. 与A B. A 与 C. {1}与 D. {1}与A 8、下列编码是前缀码的是( ).

A.{1,11,101} B.{1,001,0011} C. {1,01,001,000} D.{0,00,000} 9、下图中既是欧拉图又是哈密顿图的是（ ）

A． K9 B．K10 C．K2,3 D．K3,3 10、下图所示的二叉树中序遍历的结果是（ ）

b

A．abcde B．edcba C．bdeca D．badce

二、填空题（每题3分，共24分）

1、含3个命题变项的命题公式的主合取范式为M0 M3 M4 M6 M7, 则它的主析取范式为 。(表示成m m的形势)

2、〈Z4， 〉模4加群， 则3是阶元，3 ，3的逆元是 3、设V=<Z,+>,其中“+”是普通加法。令 1(x)=x, 2(x)=-x, 3(x)=x+5, x Z，

4(x)=2x，其中有.

123456 4、设 231546 是集合A={1，2，3，4,5,6}上的一个置换，则

《离散数学》试卷A&答案

把它表示成不相交的轮换的积是 。

4、已知n阶无向简单图G有m条边，则G的补图有 条边。 5、一个有向图是强连通的充分必要条件是 。 7、已知n阶无向图G中有m条边，各顶点的度数均为3。又已知2n-3=m， 则m= .

8、在下图中从A点开始，用普里姆算法构造最小生成树，加入生成树的第三条边是 （ ）。

AB

2C4D

三、计算题（每题9分，共 36分）

1、已知命题公式( p q) ( q p)，

(1) 构造真值表。 (2) 求主析取范式(要求通过等值演算推出)。

2、R1={<1,2>,<1,3>,<2,3>}, R2={<2,2>,<2,3>,<3,4>},求：

(1)R1 R2 （２）R1 1 (３) 求R2 R1 ３、设<A,R>为一个偏序集，其中，A={1，2，3，4，6，9，12，24},R是A上的整除关系。

（1）画R出的哈斯图； （2）求A的极大元和极小元； （3）求B={4,6}的上确界和下确界。

４、画一棵带权为1，1，1，3，3，5，8的最优二叉树T，并计算它的权W（T）。

《离散数学》试卷A&答案

四、证明题（共 20分）

1、（7分）前提： p (q s),q,p r

结论: r s

2、（7分）A={(0,0),(0,1),(1,0),(1,3),(2,2),(2,3),(3,1)}, R={<(a,b),(c,d)>| (a,b),(c,d) A且a+b=c+d }. (1)证明：R是A上的等价关系． (2)给出R确定的对A的划分(分类).

3、（6分）设 G, 是群, S {x|x G且对于 y G,x y y x}, 证明S是G的子群.

《离散数学》试卷 A

参考答案

一、选择题（每小题 2分，共 20 分。请将答案填在下面的表格内）

二、填空题（每题3分，共24分） 1、m1 m2 m5 2、3、2 4、（123）（45）。

4、

n(n 1)

n 52

《离散数学》试卷A&答案

7、 9 . 8、 d,c 或 c，d

三、计算题（每题9分，共 36分）

1

(2) 主析取范式(5分):

( p q) ( q p) (p q) ( q p) (p q) ( q p) ( p q) (

q p) ( p q) (p q) (p q) m0 m2 m3 (0,2,3)

2、(每小题3分)

(1)R1 R2(２)R1 1 ={<2,1>,<3,1>,<3,2>}

(1) 求R2 R1

３、 (每小题3分)

(1)（4分）

49

（2）（3分）A的极大元9,24; 极小元1; （3）（2分）B={4,6}的上确界12 下确界2。

《离散数学》试卷A&答案

４、画图(7分) W（T）=55(2分

)

223

1

1

四、证明题（共 20分）

1、（7分）证明：附加前提证明法..1分 ① r ② p r

③ p ①② .. 3分 ④ p (q s)

⑤ q s ③④ .. 5分 ⑥ q

⑦ s ⑤⑥ . 7分 2、证明：（1）（5分）

自反性。对于 (a,b) A,

a b a b

(a,b)R(a,b) 自反性成立

对称性。对于 (a,b),(c,d) A,如果(a,b)R(c,d), c d a b所以(c,d)R(a,b) 对称性成立

a b c d

《离散数学》试卷A&答案

传递性。 (a,b),(c,d),(x,y) A,如果(a,b)R(c,d),

a b c d,c d x y,所以

a b x y,

(c,d)R(x,y), 从而

(a,b)R(x,y)

传递性成立

（2）A/R={{(0,0)},{(0,1),(1,0)},{(1,3),(2,2),(3,1)},{(2,3)}}

（2分）

3、证明：（每步各2分）

（1）S不空： G, 是群，设e是 G, 的单位元，那么 y G,都有ey ye,（2） x1