离散数学试题十五套.docx
- 文档编号:767796
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:194
- 大小:96.78KB
离散数学试题十五套.docx
《离散数学试题十五套.docx》由会员分享,可在线阅读,更多相关《离散数学试题十五套.docx(194页珍藏版)》请在冰点文库上搜索。
离散数学试题十五套
087离散数学试题与答案试卷一
一、填空20%(每小题2分)
1.设A
{x|(x
N)且(x
5)},B
{x|x
E且x
7}(N:
自然数集,E+正偶
数)则AB。
2.A,B,C表示三个集合,文图中阴影部分的集合表达式为
。
AB
C
3.设P,Q的真值为0,R,S的真值为1,则
(P(Q(R
P)))(R
S)的真值=。
4.公式(P
R)(SR)
P的主合取范式为
。
5.若解释I的论域D仅包含一个元素,则
xP(x)
。
xP(x)
在I下真值为
6.设{1,2,3,4},A上关系图为
则R2=。
7.设{a,b,c,d},其上偏序关系R的哈斯图为
则。
8.图的补图为。
9.设{a,b,c,d},A上二元运算如下:
*
a
b
c
d
a
a
b
c
d
b
b
c
d
a
c
c
d
a
b
d
d
a
b
c
那么代数系统的幺元是,有逆元的元素为,它们的逆元分别为。
10.下图所示的偏序集中,是格的为。
二、选择20%(每小题2分)
1、下列是真命题的有()
A.{a}
{{a}}
;B.{{}}
{,{
}};
C.{{
},}
;D.{}{{
}}。
2、下列集合中相等的有()
3
A.{4,3};B.{,3,4};C.{4,,3,3};D.{3,4}。
3、设{1,2,3},则A上的二元关系有()个。
A.23;B.32;C.
233;D.22。
4、设R,S是集合A上的关系,则下列说法正确的是()
A.若R,S是自反的,则R
S是自反的;
B.若R,S是反自反的,则R
S是反自反的;
C.若R,S是对称的,则R
D.若R,S是传递的,则R
S是对称的;S是传递的。
5、设{1,2,3,4},P(A)(A的幂集)上规定二元系如下
R{s,t
|s,t
p(A)
(|s|
|t|}则P(A)/()
A.A;B.P(A);C.{{{1}},{{1,2}},{{1,2,3}},{{1,2,3,4}}};
D.{{
},{2},{2,3},{{2,3,4}},{A}}0
6、设{
,{1},{1,3},{1,2,3}}则A上包含关系“
”的哈斯图为(
)
7、下列函数是双射的为(
)
A.f:
f(x)=2x;B.f:
f(n)=
C.f:
f(x)=[x];D.f
f(x)
=|x|。
(注:
I—整数集,E—偶数集,N—自然数集,R—实数集)
8、图中
从v1到v3长度为3的通路有(
)条。
A.0;B.
.3。
1;
C.2;
D
9、下图中既不是图,也不是图的图是(
)
10、在一棵树中有7片树叶,3个3度结点,其余都是4度结点则该树有()个4
度结点。
A.1;B.2;C.3;D.4。
三、证明26%
1、R是集合X上的一个自反关系,求证:
R是对称和传递的,当且仅当
(8分)
2、f和g都是群
群。
其中
{x|x
G1且f(x)
g(x)}
(8分)
3、
k(v
e
k
2)
2,由此证明彼得森图()图是非平面图。
(11分)
四、逻辑推演16%
用规则证明下题(每小题8分)
1、A
2、
B
x(P(x)
CD,DQ(x))
EF
xP(x)
AF
xQ(x)
五、计算18%
1、设集合{a,b,c,d}上的关系{,,,
的传递闭包t(R)。
(9分)
2、如下图所示的赋权图表示某七个城市
v1,v2,
v7及预先算出它们之间的一些直接通
信线路造价,试给出一个设计方案,使得各城市之间能够通信而且总造价最小。
(9分)
试卷一答案:
一、填空20%(每小题2分)
1、{0,1,2,3,4,6};2、(B
C)A;3、1;4、(P
SR)(P
SR);
5、1;6、{<1,1>,<1,.3>,<2,2>,<2,4>};7、{<>,<>,<>,<>,<>};8、
9、a;a,b,c;a,d,c,d;10、c;
二、选择20%(每小题2分)
题目
1
2
3
4
5
6
7
8
9
10
答案
CD
B、C
C
A
D
C
A
D
B
A
三、证明26%
1、证:
“”
a,b,cX
若,<
a,c>
R由R对称性知
,<
c,a
R,由R传递性得
R
“”若
R,<
a,c>
R有<
b,c>R
任意a,b
X,因
R若<
a,b>R
R所以R是对称的。
R,<
b,c>
R则<
b,a>R
b,cR
即R是传递的。
2、证
a,bC,有
f(a)
g(a),
f(b)
g(b),又
1
f(b1)
f1(b),
g(b1)
g1(b)
f(b1)
f
1(b)
g
1(b)
g(b1)
1
f(a★b)
f(a)*f
1(b)
g(a)*
g(b1)
g(a★b)
a★b1C
3、证:
2e
①设G有r个面,则
r
d(Fi)
i1
rk2e
r
,即k。
而
ver2故
2ver
2e
ve
k即得
k(v
e
k
2)
2。
(8分)
②彼得森图为k
5,e
15,v
e
10,这样
k(vk
2)
2不成立,
②P(c)
①
③
x(P(x)
Q(x))
P
④P(c)
⑤Q(c)
Q(c)
③
T②④I
⑥
xQ(x)
⑤
⑦
xP(x)
xQ(x)
三、计算18%
所以彼得森图非平面图。
(3分)
二、逻辑推演
16%
1、证明:
①A
P(附加前提)
②AB
T①I
③AB
C
D
P
④CD
⑤D
T②③I
T④I
⑥DE
T⑤I
⑦DE
F
P
⑧F
T⑥⑦I
⑨AF
2、证明
①xP(x)
P(附加前提)
1、解:
0
1
0
0
1
0
1
0
MR
1
0
0
0
1
0
0
MR2MRMR
1
0
0
1
0
0
0
1
0
0000,0
0
0
0
MR3
MR4
MR2MR
0
1
0
1
1
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
1
0
1
0
0
0
0
0
0
0
0
1
1
1
1
,
MR3MR
Mt(R)
MRMR2
MR3
MR4
1
1
1
1
0
0
0
1
0
0
0
0
,
2、解:
用库斯克()算法求产生的最优树。
算法略。
结果如图:
树权C(T)=23+1+4+9+3+17=57即为总造价。
试卷二试题与答案
一、填空20%(每小题2分)
1、P:
你努力,Q:
你失败。
“除非你努力,否则你将失败”的翻y译为
;“虽然你努力了,但还是失败了”的翻译为
。
2、论域{1,2},指定谓词P
P(1,1)P(1,2)P(2,1)P(2,2)
则公式
TTFF
xyP(y,x)真值为。
2、设{a1,a2,,a8},是S的子集,则由B31所表达的子集是
。
3、设{2,3,4,5,6}上的二元关系R{
x,y|x
yx是质数},则
(列举法)。
R的关系矩阵
。
5、设{1,2,3},则A上既不是对称的又不是反对称的关系;
A上既是对称的又是反对称的关系。
6、设代数系统,其中{a,b,c},
*abc
aabc
bbbc
cccb
则幺元是;是否有幂等性;是否有对称性。
7、4阶群必是群或群。
8、下面偏序格是分配格的是。
9、n个结点的无向完全图的边数为,欧拉图的充要条件是
。
10、公式(P
(PQ))
((PQ)
R的根树表示为
。
二、选择20%(每小题2分)
1、在下述公式中是重言式为()
A.(PQ)
(PQ);B.(P
Q)((P
Q)(Q
P));
C.(P
Q)Q;D.P
(PQ)。
2、命题公式(P
Q)(Q
P)中极小项的个数为(),成真赋值的个数
为()。
A.0;B.1;C.2;D.3。
3、设S
{,{1},{1,2}},则
2S有()个元素。
A.3;B.6;C.7;D.8。
4、设S
{1,
2,3}
,定义S
S上的等价关系
R{a,b,
c,d
|a,b
SS,
c,d
SS,ad
bc}
则由R产生
的SS上一个划分共有()个分块。
A.4;B.5;C.6;D.9。
5、设S
{1,
2,3}
,S上关系R的关系图为
则R具有()性质。
A.自反性、对称性、传递性;B.反自反性、反对称性;C.反自反性、反对称性、传递性;D.自反性。
6、设,为普通加法和乘法,则()
S,,
是域。
A.S
{x|x
ab3,
a,bQ}
B.
S
{x|x
2n,
a,bZ}
C.S
{x|x
2n1,nZ}
D.
S
{x|xZ
x0}
=N。
7、下面偏序集()能构成格。
8、在如下的有向图中,从V1到V4长度为3的道路有()条。
A.1;B.2;C.3;D.4。
9、在如下各图中()欧拉图。
10、
设R是实数集合,“
A.群;
”为普通乘法,则代数系统
B.独异点;C.半群
。
)。
三、证明46%
1、设R是A上一个二元关系,
S{a,b
|(a,b
A)(对于某一个c
A,有
a,c
R且c,b
R)}试证
明若R是A上一个等价关系,则S也是A上的一个等价关系。
(9分)
2、用逻辑推理证明:
所有的舞蹈者都很有风度,王华是个学生且是个舞蹈者。
因此有些学生很有风度。
(11分)
3、若
f:
A
B是从A到B的函数,定义一个函数
g:
B
A
2对任意bB有
g(b)
{x|(x
A)
(f
(x)
b)}
,证明:
若f是A到B的满射,则g是从B到2A
的单射。
(10分)
4、若无向图G中只有两个奇数度结点,则这两个结点一定连通。
(8分)
m
5、设G是具有n个结点的无向简单图,其边数
分)
四、计算14%
1
(n
2
1)(n2)
2
,则G是图(8
1、设
(7分)
2、权数1,4,9,16,25,36,49,64,81,100构造一棵最优二叉树。
(7分)试卷二答案:
一、填空20%(每小题2分)
1、P
Q;P
Q2、T3、
B31
B00011111
{a4,a5,a6,a7,a8}4、
{<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,3>,
<5,4>,<5,5>,<5,6>};
5、{<1,2>,<1,3>,<2,1>};{<1,1>,<2,2>,<3,3>}
1
1
1
1
1
1
1
1
1
1
0
0
0
1
1
1
1
1
1
1
0
0
0
0
0
1
6、a;否;有7、四元群;循环群8、B9、
10、
二、选择20%(每小题2分)
n(n
2
1)
;图中无奇度结点且连通
题目
1
2
3
4
5
6
7
8
9
10
答案
B、D
D;D
D
B
D
A
B
B
B
B、C
三、证明46%
1、(9分)
(1)S自反的
aA,由R自反,
(a,a
R)(
a,a
R),
a,aS
(2)S对称的
a,bAa,bS
(a,c
(a,c
R)(
R)(
c,bR)
c,bR)
S定义R对称
(3)S传递的
b,aS
R传递
a,b,ca,b
(
(
AS
a,d
a,b
b,c
R)
R)
S
(d,b
(b,c
R)(R)
b,e
R)(R传递
e,cR)
a,cS
S定义
由
(1)、
(2)、(3)得;S是等价关系。
2、11分
证明:
设P(x):
x是个舞蹈者;Q(x):
x很有风度;S(x):
x是个学生;a:
王华上述句子符号化为:
前提:
x(P(x)
Q(x))、S(a)
P(a)
结论:
x(S(x)
Q(x))3分
①S(a)P(a)P
②x(P(x)Q(x))P
③P(a)
④P(a)
⑤Q(a).
⑥S(a)
⑦S(a)
Q(a)
Q(a)
②
T①I
T③④IT①I
T⑤⑥I
⑧x(S(x)
Q(x)
⑦11分
3、10分
证明:
b1,b2
B,(b1
b2)
f满射
a1,a2A
使f(a1)
b1,
f(a2)
b2,且
f(a1)
f(a2),由于f是函数,
a1a2
又g(b1)
{x|(x
A)(
f(x)
b1)},
g(b2)
{x|(x
A)
(
f(x)
b2)}
a1g(b1),a2
g(b2)
但a1
g(b2),a2
g(b1)
g(b1)
g(b2)
由b1,b2任意性知,
4、8分
g为单射。
证明:
设G中两奇数度结点分别为u和v,若u,v不连通,则G至少有两个连通分支G1、G2,使得u和v分别属于G1和G2,于是G1和G2中各含有1个奇数度结点,这与图论基本定理矛盾,因而u,v一定连通。
5、8分
证明:
证G中任何两结点之和不小于n。
反证法:
若存在两结点u,v不相邻且
d(u)
d(v)
n1,令V1
{u,v},则1是
m'
具有2个结点的简单图,它的边数
1(n
2
1)(n2)
2(n
1)
可得
m'1(n2
2)(n
3)1
,这与G11为2个结点为简单图的题设矛盾,因而G中任何
两个相邻的结点度数和不少于n。
所以G为图.
四、计算14
1、7分
解:
子群有<{[0]}6>;<{[0],[3]}6>;<{[0],[2],[4]}6>;<{Z6}6>
{[0]}的左陪集:
{[0]},{[1]};{[2]},{[3]};{[4]},{[5]}
{[0],[3]}的左陪集:
{[0],[3]};{[1],[4]};{[2],[5]}
{[0],[2],[4]}的左陪集:
{[0],[2],[4]};{[1],[3],[5]}
Z6的左陪集:
Z6。
2、7分
试卷三试题与答案
一、填空20%(每空2分)
1、设f,g是自然数集N上的函数
xN,
f(x)
x1,
g(x)
2x,
则fg(x)。
则s(R)=。
3、{1,2,3,4,5,6},A上二元关系T
T的关系图为
{x,y|x
;
y是素数},则用列举法
;
T具有性质。
4、集合
A{{
2},{2}}
的幂集
2A=。
5、P,Q真值为0;R,S真值为1。
则
wff(P
(RS))
((PQ)
(RS))的
真值为。
6、wff
((PQ)R)R
的主合取范式
为。
7、设P(x):
x是素数,E(x):
x是偶数,O(x):
x是奇数N():
x可以整数y。
则
谓词wff
x(P(x)
y(O(y)
N(y,x)))
的自然语言是
。
8、谓词
wff
xy(
z(P(x,z)
P(y,z))
uQ(x,
y,u))
的前束范式为
。
二、选择20%(每小题2分)
1、下述命题公式中,是重言式的为()。
A、(pq)
(pq);B、(p
q)((p
q))(q
p));
C、(p
q)q;D、(p
p)q。
2、wff
(pq)
r的主析取范式中含极小项的个数为()。
A、2;B、3;C、5;D、0;E、8。
3、给定推理
①x(F(x)G(x))P
②F(y)G(y)①
③xF(x)P
④F(y)
⑤G(y)
③
T②④I
⑥xG(x)
x(F(x)
G(x))
⑤
xG(x)
推理过程中错在()。
A、①->②;B、②->③;C、③->④;D、④->⑤;E、⑤->⑥
4、设S1={1,2,,8,9},S2={2,4,6,8},S3={1,3,5,7,9},S4={3,4,5},
S5={3,5},在条件X
S1且X
S3下X与()集合相等。
A、2或S5;B、4或S5;
C、1,S2或S4;D、X与S1,,S5中任何集合都不等。
5、设R和S是P上的关系,P是所有人的集合,
R{x,y
|x,y
Px是y的父亲},S{
x,y
|x,yP
x是y的母亲}
1
则SR表示关系()。
A、{
B、{
x,y
x,y
|x,y
|
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 试题 十五