自考离散数学02324真题含答案(2009.4-2016.4年整理版)
-
全国<
/p>
2009
年
4
月
自学考试
离散数学试题（附答案）
课程代码：
02324
一、单项选择
题（本大题共
15
小题，每小题
1
分，共
15
分）
在每小题列出的四个备选项中只有一个是符合题目要求的，
请将
其代码填写在题后的括号内。
错选、
多
选或未选均无分。
1
．下列为两个命
题变元
P
，
Q
的小项是（
）
A
．
P
∧
Q
∧
P
B
．
P
∨
Q
C
．
P
∧
Q
D
．
P
∨
P
∨
Q
2
．下列语句中是真命题的是（
）
A
．我正在说谎
B
．严禁吸烟
C
．如果
1+2=3
，那么雪是黑的
D
．如果
1
+2=5
，那么雪是黑的
3
．设
P
：我们划船，
Q
：我们跑步。命题“我们不能既划船又跑步”符号化为（
）
A
．
P
∧
Q
B
．
P
∨
Q
C
．
（
P<
/p>
Q
）
D
．
（
P
∨
Q
）
4
．命
题公式（
P
∧（
P
→
Q
）
）→
Q
是（
）
A
．矛盾式
B
．蕴含式
C
．重言式
D
．等价式
5
．命题公式
（
P
∧
Q
）→
R
的成真指派是（
）
A
．
000
，
001
，
110
，
B
．
001
，
011
，
101
，
110
，
111
C
．全体指派
D
．无
6<
/p>
．在公式（
x
）
F
（
x
，<
/p>
y
）→（
<
/p>
y
）
G
（
x
，
y
）中变元
x
是（
）
A
．自由变元
B
．约束变元
C
．既是自由变元，又是约束变元
D
．既不是自由变元，又不是约束变元
7
．集合
A={1
，
2
，…，
10}
上的关系
R={<
x
，
y
>|
x
+
y
=10
，
x
∈
A
，
y
∈
A}
，则
R
的性质是（
A
．自反的
B
．对称的
C
．传递的、对称的
D
．反自反的、传递的
8
．若
R
和
S
是集合
A
上的两个关系，则
下述结论正确的是（
）
A
．若<
/p>
R
和
S
是自反的
，则
R
∩
S
是
自反的
B
．若
R
和
S
是对称的，则
R
S
是对称的
C
．若
R
和
S
是反对称的，则
R
S
是反对称的
<
/p>
D
．若
R
和
S
是传递的，则
R
∪
S
是传递的
9
．
R={<1
，
< br>4>
，
<2
，
< br>3>
，
<3
，
< br>1>
，
<4
，
< br>3>}
，则下列不是
．．
t
（
R
）中元素的是（
）
A
．
<1
，<
/p>
1>
B
．
<1
，
2>
C
．
<1
，
3>
D
．
<1
，
4
>
1
/
33
）
10
．设
A
={{1
，
2
，
3}
，
{4
，
5}
，
{6
，
7
，
8}}
，下列选项正确的是（<
/p>
）
A
．
1
∈
A
C
．
{{4
，
5}}<
/p>
A
B
．
{1
，
2
，
3}
A
D
．
∈
A
11
．在自然数集
N
上
，下列运算是可结合的是（
）
A
．
a
b
=
a
-2
b
C
．
a
b
=-
a
-
< br>b
B
．
a
b
=min{
< br>a
，
b
}
D
．
a
b
=|
a
-
b
|
12
．在代数系统中，整环和域的
关系是（
）
A
．整环一定是域
C
．域一定是整环
B
．域不一定是整环
D
．域一定不是整环
13
．下列所示的哈斯图所对应的偏序集中能构成格的是（
）
A
．
B
．
C
．
D
．
14<
/p>
．设
G
为有
n<
/p>
个结点的简单图，则有（
）
A
．
Δ
(G)
＜
n
C
．
Δ
(G)
＞
n
B
．
Δ
(G)
≤
n
D
．
Δ
(G)
≥
n
15
．具有
4
个结点的非同构的无向树的数目是（
）
A
．
2
C
．
4
<
/p>
二、填空题（本大题共
10
小题，每小题
2
分，共
20
分）
请在每小题的空格中填上正确答案。错填、不填均无分。
B
．
3
D
．
5
16
．
（
x
）
（
y
）
（
P
（
x
，
y
）
< br>Q
（
y
，
z
）
）∧
x
P
（
x
，<
/p>
y
）中
x
的辖域为
________
，
x
的辖域为
______
__
。
17
．两个重言式的析取是
________
式，一个重言式与一个
矛盾式的析取是
________
式。
18
．设
N
是
自然数集合，
f
和
g
< br>是
N
到
N
的函数，且
f
（
n
< br>）
=2
n
+1
< br>，
g
（
n
）
=
n
2
，
那么复合函数（
f
f
）
（
n
）
=________
（
g
f
）
（
n
）
=________
。
19
．设复合函数
g
< br>
f
是从
A
到
C
的函数，如果
g
f
是满射，那么
____
____
必是满射，如果
g
f
是入射，那
么
___
_____
必是入射。
20
．设
A={1
，
2}<
/p>
，
B={2
，
3
}
，则
A-A=________
，<
/p>
A-B=________
。
21
．设
S
是非空有限
集，代数系统
（
S
）
，∪
>
中，其中
P
（
S
）为集合
S
的幂集，则
P
（
S
）对∪运算的单
位元是
< br>________
，零元是
________
。
2
/
33
+
>
中，
2
的阶是
________
。
< br>
22
．在
<
br>．设
<
br>________ 的度数是 v
6
,
○
23
，≤
>
是格，其中
A={1
，
2
，
3
，
4
，
6
，
8
，
12
，
24}
，≤为整除关系，则
3
的补元是
。
24
．在下图中，结点
v
2
________
。
0
1
25
．设图
D=
，
E>
，
V={
1
，
v
2
，
v
3
，<
/p>
v
4
}
，若
D
的邻接矩阵
A=
1
<
/p>
1
1
0
1
0
0
1
0
0
1
1
，则
deg
-
（
v
）
=________
，从
1
0
<
/p>
1
v
2
到
v
4
长度为
2
的路有
____
____
条。
三、计算题（本大题共
5
小题，第
26
、
27
小题各
5
分，第
28
、
< br>29
小题各
6
分，第
30
小题
8
分，共
30
分）
+
B
，
A
的幂集
P
（
A
）
26
．已知
A={{
<
/p>
}
，
{
，
1}}
，
B={{
，
1}
，<
/p>
{1}}
，计算
A
∪
B
，
A
○
。
27
．构造命题公式（
（
P
∧
Q
< br>）→
P
）∨
R
< br>的真值表。
28
．下
图给出了一个有向图。
（
1
）求出它的
邻接矩阵
A
；
（
2
）求出
A
2
，
A
3
，
A
4
及可达矩阵
P
。
29
．求下列公式的主合取范式和主析取范式：
P
∨（
P
→（
Q
∨（
Q
→
R
）
）
）
< br>
30
．设
A={1
，
2
，
3
，
4
，
6
，
8
，
12
，
2
4}
，
R
为
A
上的整除关系，试画
，
R>
的哈斯图，并求
A
中
的最大
元、最小元、极大元、极小元。
3
/
33
四、证明题（本大题共
3
小题，第
31
、
32
小题各
6
分，第
3
3
小题
8
分，共
20
分）
31
．在整数集
Z
上定义：
a
b
a
b
2
< br>,
a
,
b
Z
，证明：
，
>
是一个群。
32
．
R<
/p>
是集合
A
上自反和传递的关系，试证明：
R
R=R
。
33
．证明：边
e
是图
G
的一条割边，当且仅当图
G
中不存在包含边
e
的简单回路。
五、应用题（本大题共
2
小题，第
34
小题
6
分，第
35
小题
9
分，共
15
分）
34
．构造下面推理的证明。
如果小张和小王去看电影，
则小李也去看电影。
小赵不去看电影或小张去看电影。
小王去看电影。
所以，
当小赵去看电影时，小李也去。
35
．今
有
n
个人，已知他们中任何
2
人的朋友合起来一定包含其余
n-2
人。试证明
：
（
1
）<
/p>
当
n
≥
3
时，
这
n
个人能排成
一列，
使得中间任何人是其两旁的人的朋友，
而两头的人是其左
边
（或
右边）的人的朋友。
（
2
）当
n
≥
4
时，这
n
个人能排成一圆圈，使得每个人是其两旁的人的朋友。
4
/
33
5
/
33
6
/
33
7
/
33
全国
2010
年
4<
/p>
月自学考试
离散数学试题
课程代码：
02324
一、单项选择题
(
本大题共
15
小题，每小题
1
分，共
15
分
)
在每小题列出
的四个备选项中只有一个是符合题目要求的，
请将其代码填写在题后的括号内。
错选、
多
选或未选均不得分。
< br>
1.
下列句子为命题的是
(
)
A.
全体起立
!
B.
x
=0
C.
我在说谎
D.
张三生于
1886
年的春天
2.
下列式子不是
谓词合式公式的是
(
)
．．
A.
(
x<
/p>
)(
P
(
x
,
y
)
Q
(
x
,
z
))
(
z
)
R
(
x
,
z
)
B.
(
x
)(
y
)
P
(
x
,
y
)
Q
(
x
,
z
)
(
< br>
x
)
P
(
x
,
y
)
C.
(
x
)
P
(
x
)
Q
(
x
))
(
x
)(
P
(
x
< br>)
Q
(
x
))
D.
(
x
)
P
(
x
)
<
/p>
Q
(
y
,
z
)
3.
下列式子为矛盾式的是
(
)
A.
P
P
C.<
/p>
P
P
B.
P
(
P
Q
)
D.
(
P
Q
)
P
Q<
/p>
4.
设给定赋值
N
如下：个体域为自然数集；特定元素
a
=0
；特定函数
f
(
x
,
y
)=
x+y,g
(
x
,
y
)=
xy
；特定谓词<
/p>
F
(
x
,
y
)
为
x
=
y
。在赋值
N
下，下列公式为真的是
(
)
A.
(
x
)
F
(
g
(
x
,
a
),
x
)
B.
(
x
)(
y
)(
F
(
f
(
x
,
a
),
y
)
F
(
f
(
y
,
a
),
x
< br>))
C.
(
x
)(
< br>y
)(
z
)
F
(
f
(
x
,
y
),
z
)
D.
(
x
)(<
/p>
y
)
F
(
f
(
x
,
y
),
g
(
x
,
y
< br>))
5.
对于公式
(
x
)(
P
(
x
,
< br>y
)
Q
(
x
,
z
)
)
(
z<
/p>
)
R
(
x
,
z
)
，下列说法正
确的是
(
)
A.
y
是自由变元
B.
x
是约束变元
C.
(
x
)
的辖域是
(
P
(
x
,
y<
/p>
)
Q
(
x
,
z
))
(
z
)
R
(
x
< br>,
z
)
D.
(
x
)
的辖域是
P
(
x
,
y
)
6.
设论域为
{l
，
2}
，与公式
(
x
)
A
(
x
)
等价的是
< br>(
)
A.
A
(1)
A
(
2)
C.
A
(1)
B.
A
(1)
A
(2)
D.
A
(2)
A
(1)
7.
< br>设
Z
+
是正整数集合，
f
:
Z
+
→
Z
+
，
< br>f
(
n
)=2
< br>n
-2,
则
f
< br>(
)
A.
仅是入射
B.
仅是满射
C.
是双射
D.
不是函数
8.
下列关系矩阵所对应的关系具有反自反性的是
(
)
1
0<
/p>
1
0
1
1
A.
1
0
0
< br>
0
0
1
0
0
1
C.
1
0
0
8
/
33
1
0
0
0
1
1
B.
1
0
1
1
0
1
< br>
0
1
0
D.
1
0
0
9.
设
R<
/p>
1
和
R
2
是集合
A
上的相容关系，下列关于
R
1
R
2
的说法正确的是
(
)
A.
一定是相容关系
B.
一定不是相容关系
C.
可能是也可能不是相容关系
D.
一定是等价关系
10.
设
A
是奇数集合，下列
构成独异点的是
(
)
A.
<
A
，
+>
B.<
A
，
->
C.<
A
，×
>
D.<
A
，
÷
>
11.
设
A
是整数集，下列说法正确的是
(
)
A.<
A
，
+>
有零元
B.<
A
，
÷
>
有零元
C.<
< br>A
，
+>
有幺元
D.<
A
，
÷
>
有幺元
12.
下列说法不正确
的是
(
)
．．．
A.
在实数集上，乘法对加法是可分配的
B.
< br>在实数集上，加法对乘法是可分配的
C.
在某集合的幂集上，∪对∩是可分配的
D.
在某集合的幂集上，∩对∪是可分配的
13.
右图的最大入度是
(
)
A.0
B.1
C.2
D.3
14.
下列可一笔画成的图形是
(
)
15.
一棵树有
5
个
3
度结点，
2
个
2
度结点，其它的都是
l
度结点，那么这棵树的结点数是
(
)
A.13
B.14
C.16
D.17
二、填空题
(
本大题共
10
小题，每小
题
2
分，共
20
分
)
请在每小题的空格中填上正确答案。错填、不填均不得分。
<
/p>
16.
请写出表示分配律的两个命题公式等价定理
________,________
。
17.
n
个命题变元的
_
_______
称为大项，其中每个变元与它的否定不能同时出现，但两者必须
________
。
18.
在谓词推理过程中，
由
(
x
)
P
(
x
)
得到
P
(
a
)
< br>，
其中
a
为论域的某个个体，<
/p>
用的是
________
规则，
记为
________
规则。
< br>
19.
请用联结词
，
表示联结词
和联结词
：
__
______
，
________
。<
/p>
20.
设
A<
/p>
={1
，
2
，<
/p>
3
，
4}
，
B
={2
，
4
，
6}
，则
A
-
B
=________
< br>，
A
B
=________
。
21.
给出
A
={l
，<
/p>
2}
上的一个等价关系
________
，并给出其对应的划分
________
。
22.
设
A
={l
，
2
，
3
，
4}
，
A
上的二元关系
R
< br>={<1
，
2>
，
<2
，
3>
，
<3
，
2>}
，
S
R
，则称该图为汉密尔顿图。
={
，
3>
，
<2
，
3>
，
<4
，
3>}
，则
R
∩
S
=________
，
(
—
S
)
-1
=________
。
23.
代数系统
<
A<
/p>
，
+
，
。
>
是域，则
________
和
________
都是交换群。
24.
若图中存在
______
__
，它经过图中所有的
________
25.
n
点完全图记为
K
n
，那么当
________
时，
K
n
是平面图，当
_____
时，
K
n
是非平面图
。
9
/
33
三、计算题
(
本大题共
6
小题，每小题
5
分，共
30
分
)
26.
列出
(<
/p>
Q
P
)
((
P
R
)
Q
)
< br>的真值表。
27.
用等值演算求
P
(
Q
R
)
的主析取范式。
28.
设
A
={1
,2,3,4}
，给定
A
上的二元关系
R
={<1,2>,<2,1>,<2,3>,<3,4>}<
/p>
，求
R
的传递闭包。
29.
求
右图所示格的所有
5
元和
6
元子格。
30.
求
<
Z
7
一
{0}
，
>
的所有
生成元及所有
2
阶、
3
阶子群，其中
为模
7
乘法。
31.
用矩阵的方法求右图中结点<
/p>
v
1
，
v
3
之间长度为
2
的路
径的数目。
四、证
明题
(
本大题共
3
小题，第
32
小题
8
分，第
33
、
34
小题各
6
分，共
20<
/p>
分
)
10
/
33
32.
用
推理方法证明：
P
Q
,
Q
R
,
R
,
(
P<
/p>
S
)
S
。
33.
设
H
是
G
的非空子集，则
< br><
H
，
·
>
是群
<
G
，
·
>
的子群当且仅当对任意
a
,
b
H
有
a
·
< br>b
-1
H
。
34
．证
明整数集
Z
上的大于等于关系“
”是一个偏序关系。
五、综合应用题
(
本大题共
2
小题，第
35
小题
6
分，第
36
小题
9
分，共
15
分<
/p>
)
35
．将下面命题符号化，并构造推
理证明：
所有有理数是实数，有些有理数是整数，所以有些实数是整数。
36
．某
城市拟在六个区之间架设有线电话网，其网点间的距离如下列有权矩阵给出，请绘出有权图，给出架
0
1
< br>
0
设线路的最优方案，并计
算线路的总长度。
2
9
< br>0
1
0
4
0
8
0
4
0
3
0
2
9
0
8
3
0
0
7
7
0
0
5
< br>
10
6
0
0
<
/p>
5
10
6
0
11
/
33
12
/
33
13
/
33
14
/
33
15
/
33
全国
2011
年
4
月自学考试离散数学试题
课程代码：
02324
一、单项选择
题
(
本大题共
15
小题，每小题
1
分，共
15
分
)
在每小题列出的四个备选项中只有一个
是符合题目要求的
,
请将其代码填写在题后的括号内。错选、多
选或未选均不得分。
二、填空题
(
本大题共
10
小题，每小题
2
分，共
20
分
)
16
/
33