《离散数学》2004~2005学年第二学期离散数学科目考试试题B卷

2004~2005学年第二学期离散数学科目考试试题B卷 使用班级(老师填写):计科04-1班 五六|七|八|九 阅卷人 单项选择题(将答案填入下表中,每小题2分,共20分) 题号 2 3 5 8 答案 1.下列哪个语句是真命题()。 A.我正在说谎 B.如果1+2=3,则雪是黑色的 C.如果1+2=5,则雪是黑色的D.上网了吗 !〓:2.设L(x):x是演员,J(x):x是教师,A(x,y):x佩服y,命题“所有演员都佩服某些 ;教师”可符号化为()。 A.VxL(x)→A(x,y) B.Vx(L(x)→3y(J(y)∧A(x,y)) g C. VXy(L()AJ()AA(x,y) D. VXy(L()AJ()A(x,y)) 四!K;3.设A,B,C为任意三个集合,下列命题正确的是() 墨:A.若儿∪B=AUC,则B=C B.若A∩B=A∩C,则B=C 如 ~;C.若~A∪B=E且A≥B,则A=BD.若A-B=φ,则A=B ::4.设集合A={a,b}上的二元关系R={aa>,b.b>},则R()。 A.是等价关系但不是偏序关系 B.是偏序关系但不是等价关系 C.既是等价关系又是偏序关系 D.既不是等价关系也不是偏序关系 5.1.设集合A和二元运算*,可交换的代数运算是()。 A.设A=P({x,y}),Va,b∈A,a*b=aUb B.设A={,-1,2,34,-5},Va,b∈A,a*b=b C.设A=Mn(R),运算*是矩阵的乘法 D.设A=Z,Va,b∈A,a*b=a+2b :m:-= 第1页(共页)

班 第 1 页 （共 页） 级（学生填写）： 姓名： 学号： 命题： 审题： 审批： -------------------------------------------------------------------- 密 ---------------------------- 封 --------------------------- 线 ----------------------------------------------------------- （ 答 题 不 能 超 出 密 封 装 订 线 ） 2004～2005 学年第二学期 离散数学 科目考试试题 B 卷 使用班级（老师填写）：计科 04－1 班 题 号 一 二 三 四 五 六 七 八 九 总 分 得 分 阅卷人 一．单项选择题（将答案填入下表中，每小题 2 分，共 20 分） 题号 1 2 3 4 5 6 7 8 9 10 答案 1．下列哪个语句是真命题（ ）。 A．我正在说谎 B．如果 1+2 = 3，则雪是黑色的 C．如果 1+2 = 5，则雪是黑色的 D．上网了吗 2．设 L(x)：x 是演员，J(x)：x 是教师，A(x，y)：x 佩服 y，命题“所有演员都佩服某些 教师”可符号化为（ ）。 A．xL(x) → A(x, y) B．x(L(x) → y(J ( y)  A(x, y))) C．xy(L(x)  J ( y)  A(x, y)) D．xy(L(x)  J ( y) → A(x, y)) 3．设 A，B，C 为任意三个集合，下列命题正确的是（ ）。 A．若 A B = AC ，则 B = C B．若 A B = AC ，则 B = C C．若 ~ A B = E 且 A  B，则 A = B D．若 A − B =  ，则 A = B 4．设集合 A= {a，b}上的二元关系 R = {,}，则 R（ ）。 A．是等价关系但不是偏序关系 B．是偏序关系但不是等价关系 C．既是等价关系又是偏序关系 D．既不是等价关系也不是偏序关系 5．1．设集合 A 和二元运算*，可交换的代数运算是（ ）。 A．设 A = P({x, y}),a,b  A,a b = a b B．设 A = {1,−1,2,3,4,−5},a,b  A,a b =| b | C．设 A M (R) = n ，运算  是矩阵的乘法 D．设 A = Z,a,b  A,a b = a + 2b

6.设G是6阶循环群,a是生成元。则下列集合能构成G的子群的是() e,a}B.{e,a2}C.{e,a3} {e,a4} 7.设代数系统(K1·)和(K2,),存在映射f:K1→>K2,如果Va,b∈K1,都有(),称 K1与K2同态。 A.f(aob)=f(a)·f(b) B.f(a·b)=f(a)°f(b) C.f(ab)=f(a)°f(b) f(a·b)=f(a)·f(b 8.图G有21条边,3个4度结点,其余均为3度结点,则G有()个结点。 13 B 15 9.若连通图G=V,E>,其中 VEn,EI=m,则要删去G中()条边,才能确定G; 的一棵生成树。 n-m+ 10.如下图所示各图,其中存在哈密顿回路的图是()。 .填空题(每题2分,共20分) 11.任意两个不同极小项的合取为 式,全体极小项的析取式必为 12.命题“任意实数总能比较大小”可符号化为 13.由集合运算的吸收律,(AUB)∩B AU(A∩B)= 14.设集合A={ab,cd,A上的二元关系R={,,bd},S={,,} 则RS= R 第2页(共页)

第 2 页 （共 页） 6．设 G 是 6 阶循环群，a 是生成元。则下列集合能构成 G 的子群的是（ ）。 A．{e,a} B．{ , } 2 e a C．{ , } 3 e a D．{ , } 4 e a 7．设代数系统 ( , ) 1 K • 和 ( , ) 2 K  ，存在映射 1 2 f : K → K ，如果 1 a,bK ，都有（ ），称 K1 与 K2 同态。 A． f (a  b) = f (a) • f (b) B． f (a • b) = f (a) f (b) C． f (a  b) = f (a) f (b) D． f (a • b) = f (a) • f (b) 8．图 G 有 21 条边，3 个 4 度结点，其余均为 3 度结点，则 G 有（ ）个结点。 A． 13 B． 15 C． 17 D． 19 9．若连通图 G = V, E  ，其中 |V |= n,| E |= m ，则要删去 G 中（ ）条边，才能确定 G 的一棵生成树。 A． n + m−1 B． n − m+1 C． m− n +1 D． m− n −1 10．如下图所示各图，其中存在哈密顿回路的图是（ ）。 A B C D 二．填空题（每题 2 分，共 20 分） 11．任意两个不同极小项的合取为 式，全体极小项的析取式必为 式。 12．命题“任意实数总能比较大小”可符号化为 。 13．由集合运算的吸收律， (A B)  B = ， A (A B) = 。 14．设集合 A = {a,b,c,d}，A 上的二元关系 R = {,,}，S = {,,,}， 则 R·S = ，R 2 =

15.设集合A={ab,cd,A上的二元关系R={,,c,C>,<cdb},那么Dom(R) Ran(r) 16.设集合B={ab,c}上的二元关系R的关系矩阵MR=001,则R具有的性 质是 部}:17.在布尔代数中,有a+(ab)=a+b成立,则其对偶式 成立 :18.已知下图,它的点连通度x(G)为,边连通度A(G)为 图 彐 ;19给定平面图G,如下图所示,则G的面数为 G中面的总次数为 如 20.二部图G中所有基本圈的长度为 (奇数或偶数) 三.计算题(每小题5分,共30分) 21.符号化下述两个语句,并说明其区别 (1)如果天不下雨,我们就去郊游;(2)只有不下雨,我们才去郊游 m+==: 第3页(共页)

第 3 页 （共 页） -------------------------------------------------------------------- 密 ---------------------------- 封 --------------------------- 线 ----------------------------------------------------------- （ 答 题 不 能 超 出 密 封 装 订 线 ） 班 级（学生填写）： 姓名： 学号： 15．设集合 A = {a,b,c,d}，A 上的二元关系 R = {,,,}，那么 Dom(R) = ，Ran(R) = 。 16．设集合 B = {a,b,c}上的二元关系 R 的关系矩阵           = 0 0 0 0 0 1 1 1 0 M R ，则 R 具有的性 质是 17．在布尔代数中，有 a + (a b) = a + b 成立，则其对偶式 成立。 18．已知下图，它的点连通度  (G) 为 ，边连通度 (G) 为 。 19．给定平面图 G，如下图所示，则 G 的面数为 ，G 中面的总次数为 。 20．二部图 G 中所有基本圈的长度为 （奇数或偶数） 三．计算题（每小题 5 分，共 30 分） 21．符号化下述两个语句，并说明其区别： （1）如果天不下雨，我们就去郊游；（2）只有不下雨，我们才去郊游

22.试求命题公式P∧OⅴR的主析取范式和主合取范式。 23.设R={,,,,},求:(1)R*R;(2)R*R (3)R1↑1}:(4)R[{}] 24.设集合A={a,b},B={1,2,3},C={3,4,求A×(B∩C),(AxB)∩(AxC), 并验证Ax(B∩C)=(A×B)∩(A×C)。 第4页(共页)

第 4 页 （共 页） 22．试求命题公式 P  Q  R 的主析取范式和主合取范式。 23．设 R = { 0,1 , 0, 2 , 0, 3 , 1, 3 , 2, 3 } ，求：⑴ R R* ；⑵ 1 R R−  ； ⑶ 1 R {1} −  ；⑷ 1 R [{1}] − 24．设集合 A = {a，b}，B = {1，2，3}，C = {3，4}，求 A (B  C) ，(A B)  (AC) ， 并验证 A (B C) = (A B)  (AC)

25.设集合A={0,1,2,34,5}上的二元关系R={,,,21>, ,4,4>,,,<5 试说明R在A上是等价关系 26.设Z是正整数集,Va,b∈Z,aob=km(a,b)(即a,b的最小公倍数)。 :试问(Z°是半群,是含单位元的半群吗? 阳彐 四.计算题(二)(每小题7分,共14分) 长迦 27.设(B,+,·,,0,1)是布尔代数,"a,bc?B,化简 agg agg bg+ agg+ aggg 28.求图D的邻接矩阵A(D),计算A(D),并找出v到v长度为2,3的所有 通路 试 m+==: 第5页(共页)

第 5 页 （共 页） -------------------------------------------------------------------- 密 ---------------------------- 封 --------------------------- 线 ----------------------------------------------------------- （ 答 题 不 能 超 出 密 封 装 订 线 ） 班 级（学生填写）： 姓名： 学号： 25．设集合A = {0,1,2,3,4,5}上的二元关系R = {,,,,,, ,,,,,,,}，试说明 R 在 A 上是等价关系。 26．设 Z+是正整数集， a bZ+ , ， a  b = lcm(a,b) （即 a,b 的最小公倍数）。 试问 ( , ) Z+ 是半群，是含单位元的半群吗？ 四．计算题（二）（每小题 7 分，共 14 分） 27．设 (B,+, • , ,0,1) 是布尔代数， " ? a b c B , , ，化简 a b c a b c b c a b c a b c g g g g g g g g g + + + + 。 28．求图 D 的邻接矩阵 A(D) ，计算 ( ) 3 A D ，并找出 1 v 到 4 v 长度为 2，3 的所有 通路

五.证明题(每小题8分,共16分) 29.试证明:"xA(x)?xB(x)?x(A(x)?B(x)) 30.在整数集合Z上定义如下的乘法运算“o”:aob=a+b-2,那么构成 一个什么样的代数结构?试证明你的结论。 ----,=,=,=,-, 第6页(共页)

第 6 页 （共 页） 五．证明题（每小题 8 分，共 16 分） 29．试证明： " ? ? ? xA x xB x x A x B x ( ) ( ) (( ( ) ( )) 30．在整数集合 Z 上定义如下的乘法运算“  ”： a b a b o = + - 2 ，那么 Z, o 构成 一个什么样的代数结构？试证明你的结论