离散数学试卷及答案

一、单项选择题(本大题共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

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

(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

24.可满足式 永假式(或矛盾式) 25.陈述句 真值 三、计算题 ?1?1?26. M=??1??0?2?2?2 M=??2??1100?010???

011?011??110?111???

121?011??

??i?1j?144M2ij?18,

ij?6 ?M2i?14 G中长度为2的路总数为18，长度为2的回路总数为6。

27.当n是偶数时，?x∈P(A),xn=? 当n是奇数时，?x∈P(A),xn=x 于是：当n是偶数，(｛a｝-1｛b｝｛a｝)n?｛a｝-n｛b｝n｛a｝n =??(｛a｝-1)n｛b｝n｛a｝n=????? 当n是奇数时， (｛a｝-1｛b｝｛a｝)n?｛a｝-n｛b｝n｛a｝n =｛a｝-1｛b｝｛a｝?(｛a｝-1)n｛b｝n｛a｝n =｛a｝-1｛b｝｛a｝?｛a｝-1｛b｝｛a｝=? 28.(1)偏序关系R的哈斯图为

(2)B的最大元：无，最小元：无； 极大元：2，5，极小元：1，3 下界：4， 下确界4； 上界：无，上确界：无

29.原式?(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q)) ((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q)) (┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q)) (┐(P∧┐Q)∨(P∧┐Q)) (P∧Q)∨(P∧┐Q) P∧(Q∨┐Q) P∨(Q∧┐Q) (P∨Q)∧(P∨┐Q)

命题为真的赋值是P=1,Q=0和P=1,Q=1

4

30.令e1=(v1,v3), e2=(v4,v6) e3=(v2,v5), e4=(v3,v6) e5=(v2,v3), e6=(v1,v2) e7=(v1,v4), e8=(v4,v3) e9=(v3,v5), e10=(v5,v6) 令ai为ei上的权，则

a1

取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，

T的总权和=1+2+3+4+5=15

31.原式?┐(?x1F(x1,y)→?y1G(x,y1))∨?x2H(x2) (换名) ?┐?x1?y1(F(x1,y)→G(x,y1))∨?x2H(x2) ??x1?y1┐(F(x1,y1)→G(x,y1))∨?x2H(x2) ??x1?y1?x2(┐(F(x1,y1)→G(x,y1))∨H(x2) 四、证明题

32.设T中有x片树叶，y个分支点。于是T中有x+y个顶点，有x+y-1 条边，由握手定理知T中所有顶点的度数之的

x?y

?d(vi)=2(x+y-1)。

i?1 又树叶的度为1，任一分支点的度大于等于2 且度最大的顶点必是分支点，于是

x?y

?d(vi)≥x·1+2(y-2)+k+k=x+2y+2K-4

i?1 从而2(x+y-1)≥x+2y+2k-4 x≥2k-2

33.从定义出发证明：由于集合A是非空的，故显然从A到A的双射函数总是存在的，如A上恒等函数，因此F非空

(1)?f,g∈F,因为f和g都是A到A的双射函数，故f?g也是A到A的双射函数，从而集合F关于运算?是封闭的。

(2)?f,g,h∈F,由函数复合运算的结合律有f?(g?h)=(f?g)?h故运算?是可结合的。 (3)A上的恒等函数IA也是A到A的双射函数即IA∈F,且?f∈F有IA?f=f?IA=f,故IA是〈F，

?〉中的幺元

(4)?f∈F,因为f是双射函数，故其逆函数是存在的，也是A到A的双射函数，且有f?f-1=f-1

?f=IA,因此f-1是f的逆元 由此上知〈F，?〉是群

34.证明(?x)(A(x)→B(x)) ? ?x(┐A(x)∨B(x))

5

?(┐A(a1)∨B(a1))∨(┐A(a2)∨B(a2))∨…∨(┐A(an)∨B(an))) ?(┐A(a1)∨A(a2)∨…∨┐A(an)∨(B(a1)∨B(a2)∨…∨(B(an)) ?┐(A(a1)∧A(a2)∧…∧A(an))∨(┐B(a1)∨B(a2)∨…∨(B(an)) ?┐(?x)A(x)∨(?x)B(x) ? (?x)A(x)→(?x)B(x) 五、应用题

35.令p：他是计算机系本科生 q：他是计算机系研究生 r：他学过DELPHI语言 s:他学过C++语言 t:他会编程序

前提：(p∨q)→(r∧s),(r∨s)→t 结论：p→t

证①p P(附加前提) ②p∨q T①I

③(p∨q)→(r∧s) P(前提引入) ④r∧s T②③I ⑤r T④I ⑥r∨s T⑤I

⑦(r∨s)→t P(前提引入) ⑧t T⑤⑥I

36.可以把这20个人排在圆桌旁，使得任一人认识其旁边的两个人。

根据：构造无向简单图G=,其中V={v1,v2,…，V20}是以20个人为顶点的集合，E中的边是若任两个人vi和vj相互认识则在vi与vj之间连一条边。

?Vi∈V,d(vi)是与vi相互认识的人的数目，由题意知?vi,vj∈V有d(vi)+d(vj)?20,于是G中存在汉密尔顿回路。

设C=Vi1Vi2…Vi20Vi1是G中一条汉密尔顿回路，按这条回路的顺序按其排座

位即符合要求。

6

一、单项选择题（本大题共15小题，每小题1分，共15分）

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1．下列是两个命题变元p，q的小项是（ ） A．p∧┐p∧q B．┐p∨q C．┐p∧q D．┐p∨p∨q 2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ） A．p→┐q B．p∨┐q C．p∧q D．p∧┐q 3．下列语句中是命题的只有（ ） A．1+1=10 B．x+y=10 C．sinx+siny<0 D．x mod 3=2 4．下列等值式不正确的是（ ） A．┐(?x)A?(?x)┐A

B．(?x)(B→A(x))?B→(?x)A(x)

C．(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)

D．(?x)(?y)(A(x)→B(y))?(?x)A(x)→(?y)B(y)

5．谓词公式(?x)P(x,y)∧(?x)(Q(x,z)→(?x)(?y)R(x,y,z)中量词?x的辖域是（ ） A．(?x)Q(x,z)→(?x)(?y)R(x,y,z)) B．Q(x,z)→(?y)R(x,y,z)

C．Q(x,z)→(?x)(?y)R(x,y,z) D．Q(x,z)

6．设R为实数集，函数f：R→R，f(x)=2x，则f是（ ） A．满射函数 B．入射函数 C．双射函数 D．非入射非满射

7．设A={a,b,c,d}，A上的等价关系R={,,,}∪IA，则对应于R的A的划分是（ ） A．{{a},{b,c},{d}} B．{{a,b},{c},{d}} C．{{a},{b},{c},{d}} D．{{a,b},{c,d}} 8．设A={?}，B=P(P(A))，以下正确的式子是（ ） A．{?,{?}}∈B B．{{?,?}}∈B C．{{?},{{?}}}∈B D．{?,{{?}}}∈B

9．设X，Y，Z是集合，一是集合相对补运算，下列等式不正确的是（ ） A．(X-Y)-Z=X-(Y∩Z) B．(X-Y)-Z=(X-Z)-Y C．(X-Y)-Z=(X-Z)-(Y-Z) D．(X-Y)-Z=X-(Y∪Z)

10．设*是集合A上的二元运算，称Z是A上关于运算*的零元，若（ ） A．?x?A,有x*Z=Z*x=Z

B．Z?A，且?x?A有x*Z=Z*x=Z C．Z?A，且?x?A有x*Z=Z*x=x D．Z?A，且?x?A有x*Z=Z*x=Z

11．在自然数集N上，下列定义的运算中不可结合的只有（ ） A．a*b=min(a,b)

7

B．a*b=a+b

C．a*b=GCD(a,b)(a,b的最大公约数) D．a*b=a(mod b)

12．设R为实数集，R+={x|x∈R∧x>0}，*是数的乘法运算，是一个群，则下列集合

关于数的乘法运算构成该群的子群的是（ ） A．{R+中的有理数} B．{R+中的无理数} C．{R+中的自然数} D．{1，2，3} 13．设是环，则下列正确的是（ ） A．是交换群 B．是加法群 C．?对*是可分配的 D．*对?是可分配的 14．下列各图不是欧拉图的是（ ）

15．设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ ） A．2个面 B．3个面 C．4个面 D．5个面

第二部分 非选择题（共85分）

二、填空题（本大题共10小题，每空1分，共20分）

请在每小题的空格中填上正确答案。错填、不填均无分。

16．一公式为 之充分必要条件是其析取范式之每一析取项中均必同时包含一命题变元及其否定；一公式为 之充分必要条件是其合取范式之每一合取项中均必同时包含 一命题变元及其否定。

17．前束范式具有形式(Q1V1)(Q2V2)…(QnVn)A，其中Qi(1≤i≤n)为 ，A为 的谓

词公式。

18．设论域是{a,b,c}，则(?x)S(x)等价于命题公式 ；(?x)S(x)等价于命题公式 。 19．设R为A上的关系，则R的自反闭包r(R)= ，对称闭包s(R)= 。 20．某集合A上的二元关系R具有对称性，反对称性，自反性和传递性，此关系R是 ，其关系矩阵是 。

21．设是一个偏序集，如果S中的任意两个元素都有 和 ，则称S关于≤

构成一个格。

22．设Z是整数集，在Z上定义二元运算*为a*b=a+b+a·b，其中+和·是数的加法和乘法，

则代数系统的幺元是 ，零元是 。

23．如下平面图有2个面R1和R2，其中deg(R1)= ，deg(R2)= 。

8

24．无向图G具有一条欧拉回路，当且仅当G是 ，并且所有结点的度数都是 。 25．在下图中，结点v2的度数是 ，结点v5的度数是 。

三、计算题（本大题共6小题，第26—27小题每小题4分，第28、30小题每小题5分，第

29、31小题每小题6分，共30分） 26．（4分）求出从A={1,2}到B={x,y}的所有函数，并指出哪些是双射函数，哪些是满射函

数。 27．（4分）如果论域是集合{a,b,c}，试消去给定公式中的量词：(?y)(?x)(x?y?0)。 28．（5分）设A={a,b,c }，P（A）是A的幂集，?是集合对称差运算。已知是群。

在群中，①找出其幺元。②找出任一元素的逆元。③求元素x使满足{a}?x={b}。 29．（6分）用等值演算法求公式┐(p→q)??(p→┐q)的主合取范式

30．（5分）画出5个具有5个结点5条边的非同构的无向连通简单图。 31．（6分）在偏序集中，其中Z={1,2,3,4,6,8,12,14}，≤是Z中的整除关系，求集合

D={2,3,4,6}的极大元，极小元，最大元，最小元，最小上界和最大下界。

四、证明题（本大题共3小题，第32~33小题每小题6分，第34小题8分，共20分） 32．（6分）用等值演算法证明((q∧s)→r)∧(s→(p∨r))?(s∧(p→q))→r 33．（6分）设n阶无向树G=中有m条边，证明m=n-1。 34．（8分）设P={?,{1},{1,2},{1,2,3}}，?是集合P上的包含关系。

（1）证明：是偏序集。

（2）在（1）的基础上证明是全序集 五、应用题(15分） 35．（9分）在谓词逻辑中构造下面推理的证明：每个在学校读书的人都获得知识。所以如果

没有人获得知识就没有人在学校读书。（个体域：所有人的集合）

9

10

本文来源：https://www.bwwdw.com/article/1vor.html