离散数学AB卷5套期末考试卷带答案-模拟试卷-测试卷-期末考试题.doc

请将选择题答案填入下表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

一、单项选择题（请从4个备选答案中选择最适合的一项，每小题2分，共30分）
得分

1．下列等价公式错误的是（ ）．
A．； B．；
C．； D．．
2．下列等价式不成立的是（ ）．
A．； B．；
C． ； D．．
3．以下推理错误的是（ ）．
A．； B． C．； D．．
4．设是图的邻接矩阵，，则为（ ）．
A．结点的度数； B．结点的度数；
C．图中由到长度为的路径的条数； D．结点的入度．
5．下列哪个命题是真命题（　　　　）．
A．如果2+5=6，则太阳从东方升起； B．严禁吸烟；
C．如果2+3=5，则太阳从西方升起； D．我正在说谎．
6．下列各图是欧拉图的是（ ）．

7．谓词公式中量词（）辖域是（ ）．
A．；　　　 B．；
C．；　　　　　　　　　　　　 D．．
8. 设，，下列哪个命题是真命题（　　　）．
A．若是单射，则是单射． B．若是单射，则是单射．
C．若是双射，则和都是双射． D．若是满射，则是满射．
9．设集合，是上的二元关系，，则的关系矩阵是( ) ．
A．　 B． C． D．
10．令：是金属，：是液体，：可以溶解在中，则命题“任何金属可以溶解在某种液体中”可符号化为( ) ．
A． B．
C． D．
11．下面哪一种图不一定是树（　　　　）．
A．无圈连通图；　　　　 　 B．有个结点条边的连通图；
C．每对结点间都有路的图；　 D．连通但删去一条边就不连通的图．
12．下面哪个图是强连通的（ ）．

13．设上的关系的关系图如右图，从关系图可知具有
的性质是（ ）．
A．自反性、对称性和传递性；　B．自反性、反对称性和传递性；
C．反自反性、对称性和传递性； D．反自反性、反对称性和传递性．
14．设，集合上的等价关系所确定的的划分是，则=( ) ．
A． B．
C． D．
15．下图中是哈密尔顿图的是( ) ．

二、填空题（每空2分，共40分）
得分

1．设表示：上午下雨，Q表示：我去看电影，表示：我在家里读书，表示：我在家里看报纸。则命题“如果上午不下雨，我就去看电影，否则我就在家里读书或看报纸。” 符号化为 ．
2．设命题公式A的真值表为

0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1

1
1
0
1
0
1
1
1

则命题公式A的主合取范式为 ．
3．谓词公式的前束范式为 ．
4．设集合={1,2,3,4,6,8,12,14}，≤是中的整除关系，则在偏序集中，集合={2,3,4,6}
的极小元是 ，最小元是 ，下确界是 ．
5．写出下表中各列所定义的命题联结词．

0 0
0 1
1 0
1 1
0 1
0 1
0 0
1 1
6．设表示“x是金子”， 表示“x是闪光的”，则命题“金子是闪光的，但闪光的不一定是金子”符号化为 ．
7．谓词公式 　　 ．
8．若集合的基数为4，则集合上的共有 个不同的等价关系．
9．在一棵根树中，有且只有一个结点的入度为 ，其余所有结点的入度均为1．
其中入度为0的结点称为树根，出度为_____的结点称为树叶．
10．设，则= ． 其中表示集合的幂集．
11．设图(＝｛,,,｝)的邻接矩阵= ，则从到长度为2的路共有 　条．
12．一棵树有2个4度结点，3个3度结点，其余结点都是叶子，则有 个叶结点．
13．设有40盏灯，拟公用一个电源，则至少需要4插头的接线板的数目为 ．
14．设个体域，消去公式中的量词，则∧ ．
15．设是到的函数，如果是 ，则是到的函数，此时有= ．

三、计算题（每小题6分，共18分）
得分

1．设={2，3，6，12，24，36},”/”为的整除关系． 说明〈，／〉是否为偏序集，若是，画出其哈斯图．

2．以给定权6，9，10，10，15，20，30构造一棵最优二叉树．

3．设 ={1,2,3,4,5,6}，集合上的关系
求及 ．

四、证明题（每小题6分，共12分）
得分

1．用谓词演算的推理规则证明：

2． 证明：， ，，，．

一、单项选择题（请从4个备选答案中选择最适合的一项，每小题2分，共30分）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
C
B
D
C
A
B
D
A
D
A
C
A
D
A
B

二、填空题（每空2分，共40分）
1． 2．
3． 4． 2,3 ， 无 ， 1 ．
5． 6． 7．
8．15 9．0，0 10． 11． 1 12．9 13．13
14． 15．双射，
三、计算题（每小题6分，共18分）

1．设={2，3，6，12，24，36},”/”为的整除关系． 说明〈，／〉是否为偏序集，若是，画出其哈斯图．
解：〈，／〉是偏序集． 其哈斯图为： （2分）
（4分）

2．以给定权6，9，10，10，15，20，30构造一棵最优二叉树．
答案：
（6分）
3．设 ={1,2,3,4,5,6}，集合上的关系
求及 ．
解：，（1分）
（1分）
（4分）
四、证明题（每小题6分，共12分）

1．用谓词演算的推理规则证明：

证：（1） P
（2） ES（1） （1分）
（3） P
（4） US（3） （1分）
（5） T（2）（4）I （1分）
（6） P
（7） US（6）
（8） T（7）E （1分）
（9） T（5）（8）I （1分）
（10） EG（9） （1分）
2．证明：， ，，，．
证： (1)
(2) （1分）
(3) (1)，(2) （1分）
(4)
（5） (3)，(4) （1分）
（6）
(7) (5)，(6) （1分）
(8)
(9) (7)，(8) （2分）
请将选择题答案填入下表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

一、单项选择题（请从4个备选答案中选择最适合的一项，每小题2分，共30分）
得分

1．下列哪个命题是真命题（　　　　）．
A．如果2+3=5，则太阳从西方升起； B．严禁吸烟；
C．如果2+5=6，则太阳从东方升起； D．我正在说谎．
2．设集合，是上的二元关系，，则的关系矩阵是( ) ．
A．　 B． C． D．
3．令：是金属，：是液体，：可以溶解在中，则命题“任何金属可以溶解在某种液体中”可符号化为( ) ．
A． B．
C． D．
4．设，集合上的等价关系所确定的的划分是，则=( ) ．
A． B．
C． D．
5．下列等价公式错误的是（ ）．
A．； B．；
C．； D．．
6．下图中是哈密尔顿图的是( ) ．

7．谓词公式中量词（）辖域是（ ）．
A．；　　　 B．；
C．；　　　　　　　　　　　　 D．．
8. 设，，下列哪个命题是真命题（　 　　）．
A．若是单射，则是单射． B．若是单射，则是单射．
C．若是双射，则和都是双射． D．若是满射，则是满射．
9．下列等价式不成立的是（ ）．
A．； B．；
C． ； D．．
10．以下推理错误的是（ ）．
A．； B． C．； D．．
11．下面哪一种图不一定是树（　　　　）．
A．无圈连通图；　　　　 　 B．有个结点条边的连通图；
C．每对结点间都有路的图；　 D．连通但删去一条边就不连通的图．
12．下面哪个图是强连通的（ ）．

13．设上的关系的关系图如右图，从关系图可知具有
的性质是（ ）．
A．自反性、对称性和传递性；　B．自反性、反对称性和传递性；
C．反自反性、对称性和传递性； D．反自反性、反对称性和传递性．
14．设是图的邻接矩阵，，则为（ ）．
A．图中由到长度为的路径的条数； B．结点的度数；
C．结点的度数； D．结点的入度．
15．下列各图是欧拉图的是（ ）．

二、填空题（每空2分，共40分）
得分

1．谓词公式 　　 ．
2．设集合={1,2,3,4,6,8,12,14}，≤是中的整除关系，则在偏序集中，集合={2,3,4,6}
的极小元是 ，最小元是 ，下确界是 ．
3．若集合的基数为4，则集合上的共有 个不同的等价关系．
4．设图(＝｛,,,｝)的邻接矩阵= ，则从到长度为2的路共有 　条．
5．设命题公式A的真值表为

0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1

1
1
0
1
0
1
1
1
则命题公式A的主合取范式为 ．
6．设是到的函数，如果是 ，则是到的函数，此时有= ．
7．设表示：上午下雨，Q表示：我去看电影，表示：我在家里读书，表示：我在家里看报纸。则命题“如果上午不下雨，我就去看电影，否则我就在家里读书或看报纸。” 符号化为 ．
8．谓词公式的前束范式为 ．
9．设有40盏灯，拟公用一个电源，则至少需要4插头的接线板的数目为 ．
10．设，则= ． 其中表示集合的幂集．
11．写出下表中各列所定义的命题联结词．

0 0
0 1
1 0
1 1
0 1
0 1
0 0
1 1
12．设个体域，消去公式中的量词，则∧ ．
13．在一棵根树中，有且只有一个结点的入度为 ，其余所有结点的入度均为1．
其中入度为0的结点称为树根，出度为_____的结点称为树叶．
14．一棵树有2个4度结点，3个3度结点，其余结点都是叶子，则有 个叶结点．
15．设表示“x是金子”， 表示“x是闪光的”，则命题“金子是闪光的，但闪光的不一定是金子”符号化为 ．

三、计算题（每小题6分，共18分）
得分

1．以给定权6，9，10，10，15，20，30构造一棵最优二叉树．

2．设={2，3，6，12，24，36},”/”为的整除关系． 说明〈，／〉是否为偏序集，若是，画出其哈斯图．

3．设 ={1,2,3,4,5,6}，集合上的关系
求及 ．

四、证明题（每小题6分，共12分）
得分

1．证明：， ，，，．

2．用谓词演算的推理规则证明：

一、单项选择题（请从4个备选答案中选择最适合的一项，每小题2分，共30分）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
C
B
D
C
A
B
D
A
D
A
C
A
D
A
B

二、填空题（每空2分，共40分）
1． 2． 2,3 ， 无 ， 1 ． 3． 15 4． 1
5． 6．双射， 7．
8． 9．13 10． 11．
12． 13． 0，0 14．9
15．
三、计算题（每小题6分，共18分）
1．以给定权6，9，10，10，15，20，30构造一棵最优二叉树．
答案：
（6分）

2．设={2，3，6，12，24，36},”/”为的整除关系． 说明〈，／〉是否为偏序集，若是，画出其哈斯图．
解：〈，／〉是偏序集． 其哈斯图为： （2分）
（4分）
3．设 ={1,2,3,4,5,6}，集合上的关系
求及 ．
解：，（1分）
（1分）
（4分）
四、证明题（每小题6分，共12分）

1．证明：， ，，，．
证： (1)
(2) （1分）
(3) (1)，(2) （1分）
(4)
（5） (3)，(4) （1分）
（6）
(7) (5)，(6) （1分）
(8)
(9) (7)，(8) （2分）

2．用谓词演算的推理规则证明：

证：（1） P
（2） ES（1） （1分）
（3） P
（4） US（3） （1分）
（5） T（2）（4）I （1分）
（6） P
（7） US（6）
（8） T（7）E （1分）
（9） T（5）（8）I （1分）
（10） EG（9） （1分）

1 A 第 16 页 共 16 页