离散数学试题(2)
一、单项选择题(本大题共15小题,每小题1分,共15分)在每小题列出的四个选项中只有一个选项是符合题目要求的,请将正确选项前的字母填在题后的括号内。
1.一个连通的无向图G,如果它的所有结点的度数都是偶数,那么它具有一条()
A.汉密尔顿回路B.欧拉回路
C.汉密尔顿通路D.初级回路
2.设G是连通简单平面图,G中有11个顶点5个面,则G中的边是()
A.10B.12C.16D.1
43.在布尔代数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=是群,下列是G的子群是()
A.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是整数集,定义为xxy=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∪IAB.RC.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))
离散数学试题(2)
B.( x)A(f(a,x),a)
C.(x)(y)(A(f(x,y),x))
D.(x)(y)(A(x,y)→A(f(x,a),a))
12.设B是不含变元x的公式,谓词公式(x)(A(x)→B)等价于()
A.(x)A(x)→BB.(x)A(x)→B
C.A(x)→BD.(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∨QB.P∧┐QC.P→┐QD.P∨┐Q
15.以下命题公式中,为永假式的是()
A.p→(p∨q∨r)B.(p→┐p)→┐p
C.┐(q→q)∧pD.┐(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;
(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.B2.D3.A4.A5.D
6.D7.D8.C9.D10.B
11.A12.A13.C14.B15.C
二、填空题
16.0
117.10
18.单位元1
19.x∩yx∪y
20.入射满射
21.[x]R=[y]R
22.A(x)B(y)
23.(M(x)→D(x))M(x)→D(x)
24.可满足式永假式(或矛盾式)
25.陈述句真值
三、计算题
1100
26.M=1010
1011
0011
2110
M2=2111
2121
1011
4
4M2ij18,
i4Mij26 1j1i
1G中长度为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
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=1
531.原式┐(x1F(x1,y)→y1G(x,y1))∨x2H(x2)(换名)
┐x1y1(F(x1,y)→G(x,y1))∨x2H(x2)
x1y1┐(F(x1,y1)→G(x,y1))∨x2H(x2)
x1y1x2(┐(F(x1,y1)→G(x,y1))∨H(x2)
四、证明题
32.设T中有x片树叶,y个分支点。于是T中有x+y个顶点,有x+y-1 条边,由握手定理知
T中所有顶点的度数之的
xy
d(vi)=2(x+y-1)。
i
1又树叶的度为1,任一分支点的度大于等于
2且度最大的顶点必是分支点,于是
xy
d(vi)≥x·1+2(y-2)+k+k=x+2y+2K-
4i1
从而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的双射函数,故fg也是A到A的双射函数,从而集
合F关于运算是封闭的。
(2)f,g,h∈F,由函数复合运算的结合律有f(gh)=(fg)h故运算是可结合的。
(3)A上的恒等函数IA也是A到A的双射函数即IA∈F,且f∈F有IAf=fIA=f,故IA是〈F,
〉中的幺元
(4)f∈F,因为f是双射函数,故其逆函数是存在的,也是A到A的双射函数,且有ff-1=f-1
f=IA,因此f-1是f的逆元
由此上知〈F,〉是群
34.证明(x)(A(x)→B(x)) x(┐A(x)∨B(x))
(┐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
证①pP(附加前提)
②p∨qT①I
③(p∨q)→(r∧s)P(前提引入)
④r∧sT②③I
⑤rT④I
⑥r∨sT⑤I
⑦(r∨s)→tP(前提引入)
⑧tT⑤⑥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中一条汉密尔顿回路,按这条回路的顺序按其排座位即符合要求。