《离散数学》课程教学资源（试卷习题）2004~2005学年第二学期离散数学科目考试试题A卷

2004~2005学年第二学期离散数学科目考试试题A卷 使用班级(老师填写):05计算机函授本科 五六|七|八|九 阅卷人 单项选择题(将答案填入下表中,每小题2分,共20分) 题号 2 3 5 8 答案 命题公式为曹(P?Q)()。 A.重言式B.可满足式C.矛盾式D.等值式 :2·设集合A={1,a},则P(A)=()。 A.{1},{a} B.{f,{1},{a} !〓 C.{f,{1},{a},{l,a}D.{{1},a},{1,a} 彐:3.下列命题中正确的结论是:( A.集合上A的关系如果不是自反的,就一定是反自反的 B.若关系R,S都是反自反的,那么RoS必也为反自反的 温 C.若关系R,S都是自反的,那么R。S必也为自反的 D.每一个全序集必为良序集 她;4.下列结论中不正确的结论是:() A.三个命题变元的布尔小项一PAQ∧-R的编码是mo0 B.三个命题变元的布尔大项刳Q谪R的编码是M1o1 C.任意两个不同的布尔小项的合取式必为永假式 D.任意两个不同的布尔大项的合取式必为永假式 5.设集合A和二元运算*,可交换的代数运算是() A.设A=P({x,y}),Va,b∈A,a*b=aUb B.设A={-1,2,3,4,-5},Va,b∈A,a*b=b C.设A=Mn(R),运算*是矩阵的乘法 D.设A=Z,a,b∈A,a*b=a+2b 第1页(共页)

班 第 1 页 （共 页） 级（学生填写）： 姓名： 学号： 命题： 审题： 审批： -------------------------------------------------------------------- 密 ---------------------------- 封 --------------------------- 线 ----------------------------------------------------------- （ 答 题 不 能 超 出 密 封 装 订 线 ） 2004～2005 学年第二学期 离散数学 科目考试试题 A 卷 使用班级（老师填写）：05 计算机函授本科 题 号 一 二 三 四 五 六 七 八 九 总 分 得 分 阅卷人 一．单项选择题（将答案填入下表中，每小题 2 分，共 20 分） 题号 1 2 3 4 5 6 7 8 9 10 答案 1．命题公式为 禺P P Q ( ) ? （ ）。 A．重言式 B．可满足式 C．矛盾式 D．等值式 2．设集合 A = {1，a}，则 P(A) =（ ）。 A．{{1}，{a}} B．{ f ，{1}，{a}} C．{ f ，{1}，{a}，{1，a}} D．{{1}，{a}，{1，a}} 3．下列命题中正确的结论是：（ ） A．集合上 A 的关系如果不是自反的，就一定是反自反的； B．若关系 R, S 都是反自反的，那么 R S 必也为反自反的； C．若关系 R, S 都是自反的，那么 R S 必也为自反的； D．每一个全序集必为良序集. 4．下列结论中不正确的结论是：（ ） A．三个命题变元的布尔小项 P Q  R 的编码是 m010 ； B．三个命题变元的布尔大项 刳 谪 P Q R 的编码是 M101 ； C．任意两个不同的布尔小项的合取式必为永假式； D．任意两个不同的布尔大项的合取式必为永假式. 5．设集合 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.以下命题中不正确的结论是 A.素数阶群必为循环群 B.Abel群必为循环群; C.循环群必为Abel群 D.4阶群必为Abel群 7.设代数系统(K12·)和(K2。),存在映射f:k1→K2,如果Va,b∈K1,都有(),称 K1与K2同态。 A.f(aob)=f(a)·f(b) B.f(a·b)=f(a)。f(b) f(aob)=f(a)°f(b) f(a·b)=f(a)·f(b) 8.图G有21条边,3个4度结点,其余均为3度结点,则G有()个结点。 B C.17 9.以下命题中正确的结论是 A.n=2k时,完全图K必为欧拉图 B.如果一个连通图的奇结点的个数大于2,那么它可能是一个 Euler图 C.一棵树必是连通图,且其中没有回路 D.图的邻接矩阵必为对称阵 10.若连通图G=,其中V}n,EFm,则要删去G中()条边,才能确定G 的一棵生成树。 A. n+m-1 B 填空题(每题2分,共20分) 11.公式(P∧Q)-R的对偶式为 12.子集公理的逻辑表达式为 13.设集合A={abc4,A上的二元关系R={ab>b,Ccd},那么Dom(R); 14.设集合B={abc上的二元关系R的关系矩阵MR=001,则R具有的性质 它的对称闭包S(R) 第2页(共页)

第 2 页 （共 页） 6．以下命题中不正确的结论是（ ） A．素数阶群必为循环群； B．Abel 群必为循环群； C．循环群必为 Abel 群 D．4 阶群必为 Abel 群. 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．以下命题中正确的结论是（ ） A． n k = 2 时，完全图 K n 必为欧拉图 B．如果一个连通图的奇结点的个数大于 2，那么它可能是一个 Euler 图； C．一棵树必是连通图，且其中没有回路； D．图的邻接矩阵必为对称阵. 10．若连通图 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 二．填空题（每题 2 分，共 20 分） 11．公式 ( ) P Q R    的对偶式为 。 12．子集公理的逻辑表达式为 。 13．设集合 A = {a,b,c,d}，A 上的二元关系 R = {,,,}，那么 Dom(R) = ，Ran(R) = 。 14．设集合 B = {a,b,c}上的二元关系 R 的关系矩阵           = 0 0 0 0 0 1 1 1 0 M R ，则 R 具有的性质 是 ，且它的对称闭包 S R( ) ＝

15.设集合A={a,b},B={1,2},则从A到B的所有函数是 其中双射的函数 16.完全图K,是平面图的充要条件是n≤ 17.在布尔代数中,有a+(a·b)=a+b成立,则其对偶式 8:18.已知下图,它的点连通度k(G为,边连通度A(G)为 :19.给定平面图G,如下图所示,则G的面数为 G中面的总次数为_ 彐 如 20.若二部图Kmn为完全二部图,则其边数为 计算题(一)(每小题5分,共30分) 21.符号化下述两个语句,并说明其区别 (1)如果天不下雨,我们就去旅游:(2)只有不下雨,我们才去旅游。 m+==: 第3页(共页)

第 3 页 （共 页） -------------------------------------------------------------------- 密 ---------------------------- 封 --------------------------- 线 ----------------------------------------------------------- （ 答 题 不 能 超 出 密 封 装 订 线 ） 班 级（学生填写）： 姓名： 学号： 15．设集合 A = {a,b}，B = {1,2}，则从 A 到 B 的所有函数是 ，其中双射的函数 。 16．完全图 K n 是平面图的充要条件是 n  17．在布尔代数中，有 a + (a b) = a + b 成立，则其对偶式 成立。 18．已知下图，它的点连通度  (G) 为 ，边连通度 (G) 为 。 19．给定平面图 G，如下图所示，则 G 的面数为 ，G 中面的总次数为 。 20．若二部图 Km n, 为完全二部图，则其边数为 三．计算题(一)（每小题 5 分，共 30 分） 21．符号化下述两个语句，并说明其区别： （1）如果天不下雨，我们就去旅游；（2）只有不下雨，我们才去旅游

22.将下命题化为主析取范式和主合取范式:(pV(q∧r)→(p∧qAr) 23.设R={0.1>,,,},求:(1)R*R;(2)R*R1: (3)R-U,{f}};(4)R[U,f 24.设集合A={1,2,3,4},A上的二元关系R,其中R={,, ,,,,4,4>},说明R是否A上的等价关系。 第4页(共页)

第 4 页 （共 页） 22．将下命题化为主析取范式和主合取范式： ( p  (q  r)) → ( p  q  r). 23．设 R = { 0,1 , 1, 0 , 0, 2 , 2, 0 } ，求：⑴ R R* ；⑵ 1 R R- * ； ⑶ R ­ { ,{ }} f f ；⑷ R[{ ,{ }}] f f 24．设集合Ａ＝｛１，２，３，４｝，Ａ上的二元关系Ｒ，其中Ｒ＝｛,,, ,,,,｝，说明Ｒ是否Ａ上的等价关系

25.分别画下图中的强分图、单向分图。 6·设代数系统(Z,*),其中Z是整数集,二元运算定义为 1:ya,b∈z,a*b=a+b-2。a∈z,求a的逆元 燕阳盎长铷 计算题(二)(每小题7分,共14分) 27.设(B,+,·,0,1)是布尔代数,Vanb,c∈B,化简a+agb(ga+b) 试 28.求下图D的邻接矩阵A(D),并算出其可达矩阵P(D) e m+==: 第5页(共页)

第 5 页 （共 页） -------------------------------------------------------------------- 密 ---------------------------- 封 --------------------------- 线 ----------------------------------------------------------- （ 答 题 不 能 超 出 密 封 装 订 线 ） 班 级（学生填写）： 姓名： 学号： 25．分别画下图中的强分图、单向分图。 26 ． 设代数系统 ( Z ,  ) , 其 中 Z 是整数 集 ， 二 元 运 算 定 义 为  a , b Z , a  b = a + b − 2 。 a  Z ,求 a 的逆元. 三．计算题(二)（每小题 7 分，共 14 分） 27．设 (B,+, • , ,0,1) 是布尔代数， a,b,c  B ，化简 a a b c a b + + g g ( ) 。 28．求下图 D 的邻接矩阵 A D( ) ，并算出其可达矩阵 P D( )

五.证明题(每小题8分,共16分) 29.试证明:("x)(P(x)?Q(x))、(x)?P(x)($xQ(x) 30.给定正整数m,令G={m|k?z},证明:(G,+)是一个群,其中+是数的普通加; ----,=,=,=,-, 第6页(共页)

第 6 页 （共 页） 五．证明题（每小题 8 分，共 16 分） 29．试证明：( )( ( ) ( )), ( ) ( ) " ? ? x P x Q x x P x ┣ ( ) ( ) $x Q x 30．给定正整数 m，令 G km k Z = ? { | } ，证明：( , ) G + 是一个群，其中+是数的普通加 法