离散数学试题+答案

离散数学试题+答案

一、单项选择题(本大题共15小题,每小题1分,共15分)在每小题列出的四个选

项中只有一个选项是符合题目要求的,请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图G,如果它的所有结点的度数都是偶数,那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路

2.设G是连通简单平面图,G中有11个顶点5个面,则G中的边是( ) A.10 B.12 C.16 D.14

3.在布尔代数L中,表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( ) A.b∧(a∨c)

B.(a∧b)∨(a’∧b)

C.(a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c) 4.设i是虚数,·是复数乘法运算,则G=<{1,-1,i,-i},·>是群,下列是G的子群是( ) A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉 D.〈{-i},·〉

5.设Z为整数集,A为集合,A的幂集为P(A),+、-、/为数的加、减、除运算,∩为集合的交运算,下列系统中是代数系统的有( )

A.〈Z,+,/〉 B.〈Z,/〉 C.〈Z,-,/〉 D.〈P(A),∩〉 6.下列各代数系统中不含有零元素的是( ) A.〈Q,*〉Q是全体有理数集,*是数的乘法运算

B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合,*是矩阵乘法运算 C.〈Z,?〉,Z是整数集,?定义为x?xy=xy,?x,y∈Z D.〈Z,+〉,Z是整数集,+是数的加法运算

7.设A={1,2,3},A上二元关系R的关系图如下: R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性

8.设A={a,b,c},A上二元关系R={〈a,a〉,〈b,b〉〈,a,c〉},则关系R的对称闭包S(R)是( ) A.R∪IA B.R C.R∪{〈c,a〉} D.R∩IA 9.设X={a,b,c},Ix是X上恒等关系,要使Ix∪{〈a,b〉,〈b,c〉,〈c,a〉,〈b,a〉}∪R为X上的等价关系,R应取( ) A.{〈c,a〉,〈a,c〉} B.{〈c,b〉,〈b,a〉} C.{〈c,a〉,〈b,a〉} D.{〈a,c〉,〈c,b〉} 10.下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 11.设解释R如下:论域D为实数集,a=0,f(x,y)=x-y,A(x,y):x

A.( ? x)( ?y)( ?z)(A(x,y))→A(f(x,z),f(y,z)) B.( ?x)A(f(a,x),a)

C.(?x)(?y)(A(f(x,y),x))

1 / 6

离散数学试题+答案

D.(?x)(?y)(A(x,y)→A(f(x,a),a))

12.设B是不含变元x的公式,谓词公式(?x)(A(x)→B)等价于( ) A.(?x)A(x)→B B.(?x)A(x)→B

C.A(x)→B D.(?x)A(x)→(?x)B

13.谓词公式(?x)(P(x,y))→(?z)Q(x,z)∧(?y)R(x,y)中变元x( ) A.是自由变元但不是约束变元 B.既不是自由变元又不是约束变元 C.既是自由变元又是约束变元 D.是约束变元但不是自由变元

14.若P:他聪明;Q:他用功;则“他虽聪明,但不用功”,可符号化为( ) A.P∨Q B.P∧┐Q C.P→┐Q D.P∨┐Q 15.以下命题公式中,为永假式的是( )

A.p→(p∨q∨r) B.(p→┐p)→┐p

C.┐(q→q)∧p D.┐(q∨┐p)→(p∧┐p) 二、填空题(每空1分,共20分)

16.在一棵根树中,仅有一个结点的入度为______,称为树根,其余结点的入度均为______。 17.A={1,2,3,4}上二元关系R={〈2,4〉,〈3,3〉,〈4,2〉},R的关系矩阵MR中m24=______,m34=______。 18.设〈s,*〉是群,则那么s中除______外,不可能有别的幂等元;若〈s,*〉有零元,则|s|=______。

?〉19.设A为集合,P(A)为A的幂集,则〈P(A),是格,若x,y∈P(A),则x,y最大下界是______,最小上界是______。

20.设函数f:X→Y,如果对X中的任意两个不同的x1和x2,它们的象y1和y2也不同,我们说f是______函数,如果ranf=Y,则称f是______函数。

21.设R为非空集合A上的等价关系,其等价类记为〔x〕R。?x,y∈A,若〈x,y〉∈R,则 〔x〕R与〔y〕R的关系是______,而若〈x,y〉?R,则〔x〕R∩〔y〕R=______。

22.使公式(?x)( ?y)(A(x)∧B(y))?(?x)A(x)∧(?y)B(y)成立的条件是______不含有y,______不含有x。 23.设M(x):x是人,D(s):x是要死的,则命题“所有的人都是要死的”可符号化为(?x)______,其中量词(?x)的辖域是______。 24.若H1∧H2∧…∧Hn是______,则称H1,H2,…Hn是相容的,若H1∧H2∧…∧Hn是______,则称H1,H2,…Hn是不相容的。

25.判断一个语句是否为命题,首先要看它是否为 ,然后再看它是否具有唯一的 。

三、计算题 (共30分)

26.(4分)设有向图G=(V,E)如下图所示,试用邻接矩阵方法求长度为2的路的总数和回路总数。

27.(5)设A={a,b},P(A)是A的幂集,?是对称差

运算,可以验证是群。设n是正整数,求({a}-1{b}{a})n?{a}-n{b}n{a}n 28.(6分)设A={1,2,3,4,5},A上偏序关系 R={〈1,2〉,〈3,2〉,〈4,1〉,〈4,2〉,〈4,3〉,〈3,5〉,〈4,5〉}∪IA;

2 / 6

离散数学试题+答案

(1)作出偏序关系R的哈斯图

(2)令B={1,2,3,5},求B的最大,最小元,极大、极小元,上界,下确界,下界,下确界。 29.(6分)求┐(P→Q)?(P→┐Q)的主合取范式并给出所有使命题为真的赋值。

30.(5分)设带权无向图G如下,求G的最小生成树T及T的权总和,要求写出解的过程。

31.(4分)求公式┐((?x)F(x,y)→(?y)G(x,y))∨(?x)H(x)的前束范式。 四、证明题 (共20分)

32.(6分)设T是非平凡的无向树,T中度数最大的顶点有2个,它们的度数为k(k≥2),证明T中至少有2k-2片树叶。

33.(8分)设A是非空集合,F是所有从A到A的双射函数的集合,?是函数复合运算。 证明:〈F, ?〉是群。

34.(6分)在个体域D={a1,a2,…,an}中证明等价式: (?x)(A(x)→B(x))?(?x)A(x)→(?x)B(x) 五、应用题(共15分)

35.(9分)如果他是计算机系本科生或者是计算机系研究生,那么他一定学过DELPHI语言而且学过C++语言。只要他学过DELPHI语言或者C++语言,那么他就会编程序。因此如果他是计算机系本科生,那么他就会编程序。请用命题逻辑推理方法,证明该推理的有效结论。

36.(6分)一次学术会议的理事会共有20个人参加,他们之间有的相互认识但有的

相互不认识。但对任意两个人,他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁,使得任意一个人认识其旁边的两个人?根据是什么?

参考答案

一、单项选择题(本大题共15小题,每小题1分,共15分)

1.B 2.D 3.A 4.A 5.D 6.D 7.D 8.C 9.D 10.B 11.A 12.A 13.C 14.B 15.C 二、填空题 16.0 1 17.1 0

18.单位元 1

19.x∩y x∪y 20.入射 满射

21.[x]R=[y]R 22.A(x) B(y)

23.(M(x)→D(x)) M(x)→D(x)

3 / 6

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4