资源描述
一、单选题（20小题，每小题2分，共40分）
得分
1、有理数集和上定义的下列运算不能构成代数系统的是( )。
A． B．
C． D．
2、设是集合上的任意函数，下列哪个命题是真命题（ ）。
A． B．
C． D．
3、任何无向图G中结点间的连通关系是（ ）。
A．良序关系 B．偏序关系
C．全序关系 D．等价关系
4、设是一条链，且，则( )。
A．是布尔代数 B．是有补格
C．是分配格 D．都不是
5、集合上的等价关系，其等价类的集合｛｝称为（ ）．
A．与的并集，记为∪ B．与的交集，记为∩
C．与的商集，记为／ D．与的差集，记为－．
6、给定命题公式如下：（ØP ®Q）®（Ø P ÙQ）该命题公式的成真赋值个数（ ）
A．0 B．1 C．2 D．3
7、设，*为普通乘法，则是（ ）。
A．代数系统； B．半群； C．群； D．都不是
8、下列公式中，（ ）是矛盾式。
A．("x) F（x）®( $y)F（y）
B．("x) ( $y) F(x,,y) ®($x) ("y) F(x,,y)
C．Ø (P（x）® (("y) G(x,,y) ® P（x）))
D． ("x) (ØP（x）® ØP（a）)
9、下列各图是欧拉图的是（ ）．
10、下面哪一种图不一定是树（ ）．
A．无圈的连通图； B．有ｎ个结点ｎ－１条边的连通图；
C．每对结点间都有路的图； D．连通但删去一条边就不连通的图．
11、设有向图，其中，则G是（ ）。
A．强连通图 B．单向连通图 C．弱连通图 D．非连通图
12、设有向图，其中，，则G是（ ）。
A．强连通图 B．单向连通图 C．弱连通图 D．非连通图
13、具有个结点的完全图是欧拉图，则为( )。
A．偶数； B．奇数； C．9； D．10．
14、在自然数N上，下列哪种运算可使<N,*>构成可交换半群( )。
A． B．
C． D．
15、谓词演算中，是的有效结论，其理论依据是（ ）。
A．全称指定规则（US） C．全称推广规则（UG）
B．存在指定规则（ES） D．存在推广规则（EG）
16、设为整数集，：，，则是（ ）。
A．是入射不是满射
B．是满射不是入射
C．既非入射也非满射
D．是双射
17、下列关系中能构成函数的是（ ）。
A． B．
C． D．
18、下面哪个哈斯图构成分配格（ ）。
19、下列等价公式正确的是（ ）。
A．； B．；
C．； D．．
20、设，则有（ ）个元素。
A．3； B．6； C．7； D．8
二、填空题（20小题，每空1分，共20分）
得分
1、代数系统〈Z，+〉（Z为整数集，+为普通加法）中，Z关于“+”的幺元为 。
2、无向图G具有生成树，当且仅当___________________。
3、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除关系，则集合={2,3,4,6}的最大元是
4、设=｛｛，｛｝｝｝，则×= 。其中表示集合的幂集．
5、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除关系，则集合={2,3,4,6}的极小元是
6、设有33盏灯，拟公用一个电源，则至少需要5插头的接线板的数目为 。
7、设表示“我去学校”， 表示“明天上午8点下雨”，则命题“只有当明天上午8点不下雨时我才去学校”符号化为 。
8、设集合Ａ＝｛ａ，ｂ，ｃ｝上的关系Ｒ＝｛〈ａ，ｂ〉，〈ａ，ｃ〉，〈ｃ，ｃ〉｝，ｔ（Ｒ）＝ 。
9、设图G=〈V，E〉，V＝｛,,,｝的邻接矩阵A(G) = ，则从到长度为２的路共有 条。
10、谓词公式 。
11、无向图中有10条边，且每个结点的度数均为4，则结点数是 。
12、命题公式的逆反式是 。
13、代数系统〈Z，+〉（Z为整数集，+为普通加法）中，Z关于“+”的零元为 。
14、在格中，对，当且仅当 。
15、在格中，对，当且仅当 。
16、设，则A的幂集是 ．
17、为实数集合，运算*的定义为：对任意的有，则代数系统最强是 。
18、命题公式（ØP ®Q）®（Ø QÚ P）的主合取范式为 。
19、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除关系，则集合={2,3,4,6}的最小元是
20、在偏序集中，，≤是上的整除关系，则的极大元是 。
三、简答题（4小题，每小题6分，共24分）
得分
1、对下图所给的偏序集，求下表所列集合的上确界，下确界，并将结果填入表中。
子 集
上确界
下确界
2、为简单有向图，写出的邻接矩阵，算出，，且确定到有多少条长度为3的路? 到有多少条长度为2的路? 到自身长度为3和长度为4的回路各多少条?
3、下图给出的赋权图表示八个城市及架起城市间直接通讯线路的预测造价，试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小造价。
4、设={1,2,3,5,6,10,15,30} ， “／” 为集合上的整除关系。
(1)．〈，／〉是否为偏序集? 若是，画出其哈斯图；
(2)．〈，／〉是否构成格？为什么？
(3)．〈，／〉是否构成布尔代数？为什么？
四、证明题（2小题，每小题8分，共16分）
得分
1、设 定义为 ，证明：是双射，并求出其逆映射。
2、指出下面推理证明过程中的错误, 并给出正确的证明。
用谓词演算的推理规则证明:
证: (1) P (6) T(4) I
(2) US(1) (7) T(2),(5) I
(3) P (8) T(6),(7) I
(4) ES(3) (9) EG(8)
(5) T(4) I
一、单选题（20小题，每小题2分，共40分）
1、B
2、C
3、D
4、C
5、C
6、C
7、D
8、C
9、B
10、C
11、C
12、C
13、B
14、B
15、A
16、C
17、B
18、D
19、B
20、D
二、填空题（20小题，每空1分，共20分）
1、0
2、图G连通
3、无
4、
5、2,3
6、8
7、
8、｛〈ａ，ｂ〉，〈ａ，ｃ〉，〈ｃ，ｃ〉｝
9、1
10、
11、5
12、
13、不存在
14、b
15、
16、
17、半群
18、或PÚØ Q
19、无
20、4，5，6
三、简答题（4小题，每小题6分，共24分）
1、答：
子 集
上 确 界
下 确 界
无
无
2、解：邻接矩阵及，，如下：（2分）
=2，所以到长度为3的路有2条，它们分别是：和。
（1分）
=1，所以到长度为2的路有1条：。 （1分）
=0，到自身无长度为3的回路。 （1分）
=4，到自身有4条长度为4的回路，它们分别是：、、和。 （1分）
3、解：该问题相当于求上图的最小生成树。按下图架起八个城市间直接通讯线路的造价最小．最小造价为：
W（T）=180+240+200+280+120+90+220=1330 （2分）
（4分）
4、解：(1)．〈，／〉是偏序集。 其哈斯图为：
（3分）
(2)．〈，／〉构成格。因为其任意两个元素都有上确界和下确界。 （1分）
(3)．〈，／〉构成布尔代数。因为它是有界分配格，且其任意元素都有唯一补元素。 （2分）
四、证明题（2小题，每小题8分，共16分）
1、证明：
①
②
③
且是入射
根据①②③知f是双射
。
2、（1）该证明的错误在于: (1)、 (2) 与 (3)、 (4) 的顺序颠倒了，应该先指定存在后指定全称。 （2分）
（2）正确的证明是：（6分）
(1) P (6) T(2) I
(2) ES (1) (7) T(4),(5) I
(3) P (8) T(6),(7) I
(4) US (3) (9) EG(8)
(5) T(2) I
一、单选题（20小题，每小题2分，共40分）
得分
1、给定命题公式如下：（ØP ®Q）®（Ø P ÙQ）该命题公式的成真赋值个数（ ）。
A．0 B．1 C．2 D．3
2、设，*为普通乘法，则是（ ）。
A．代数系统 B．半群 C．群 D．都不是
3、设为整数集，：，，则是（ ）。
A．是入射不是满射
B．是满射不是入射
C．既非入射也非满射
D．是双射
4、下列各图是欧拉图的是（ ）。
5、下面哪一种图不一定是树（ ）。
A．无圈的连通图 B．有ｎ个结点ｎ－１条边的连通图
C．每对结点间都有路的图 D．连通但删去一条边就不连通的图
6、谓词演算中，是的有效结论，其理论依据是（ ）。
A．全称指定规则（US） C．全称推广规则（UG）
B．存在指定规则（ES） D．存在推广规则（EG）
7、集合上的等价关系，其等价类的集合｛｝称为（ ）。
A．与的并集，记为∪ B．与的交集，记为∩
C．与的商集，记为／ D．与的差集，记为－
8、下列公式中，（ ）是矛盾式。
A．("x) F（x）®( $y)F（y）
B．("x) ( $y) F(x,,y) ®($x) ("y) F(x,,y)
C．Ø (P（x）® (("y) G(x,,y) ® P（x）))
D． ("x) (ØP（x）® ØP（a）)
9、下面哪个哈斯图构成分配格（ ）。
10、设，则有（ ）个元素。
A．3 B．6 C．7 D．8
11、设有向图，其中，，则G是（ ）。
A．强连通图 B．单向连通图 C．弱连通图 D．非连通图
12、有理数集和上定义的下列运算不能构成代数系统的是( )。
A． B．
C． D．
13、设有向图，其中，则G是（ ）。
A．强连通图 B．单向连通图 C．弱连通图 D．非连通图
14、在自然数N上，下列哪种运算可使<N,*>构成可交换半群( )。
A． B．
C． D．
15、设是集合上的任意函数，下列哪个命题是真命题（ ）。
A． B．
C． D．
16、任何无向图G中结点间的连通关系是（ ）。
A．良序关系 B．偏序关系
C．全序关系 D．等价关系
17、设是一条链，且，则( )。
A．是布尔代数 B．是有补格
C．是分配格 D．都不是
18、下列等价公式正确的是（ ）。
A．； B．；
C．； D．．
19、具有个结点的完全图是欧拉图，则为( )。
A．偶数； B．奇数； C．9； D．10．
20、下列关系中能构成函数的是（ ）。
A． B．
C． D．
二、填空题（20小题，每空1分，共20分）
得分
1、在偏序集中，，≤是上的整除关系，则的极大元是 。
2、代数系统〈Z，+〉（Z为整数集，+为普通加法）中，Z关于“+”的幺元为 。
3、设，则A的幂集是 。
4、无向图G具有生成树，当且仅当___________________。
5、设=｛｛，｛｝｝｝，则×= 。其中表示集合的幂集．
6、在格中，对，当且仅当 。
7、为实数集合，运算*的定义为：对任意的有，则代数系统最强是 。
8、设表示“我去学校”， 表示“明天上午8点下雨”，则命题“只有当明天上午8点不下雨时我才去学校”符号化为 。
9、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除关系，则集合={2,3,4,6}的最小元是 。
10、设有33盏灯，拟公用一个电源，则至少需要5插头的接线板的数目为 。
11、代数系统〈Z，+〉（Z为整数集，+为普通加法）中，Z关于“+”的零元为 。
12、设集合Ａ＝｛ａ，ｂ，ｃ｝上的关系Ｒ＝｛〈ａ，ｂ〉，〈ａ，ｃ〉，〈ｃ，ｃ〉｝，ｔ（Ｒ）＝ 。
13、在格中，对，当且仅当 。
14、命题公式（ØP ®Q）®（Ø QÚ P）的主合取范式为 。
15、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除关系，则集合={2,3,4,6}的极小元是 。
16、命题公式的逆反式是 。
17、谓词公式 。
18、设图G=〈V，E〉，V＝｛,,,｝的邻接矩阵A(G) = ，则从到长度为２的路共有 条。
19、在偏序集中，其中={1,2,3,4,6,8,12,14}，≤是中的整除关系，则集合={2,3,4,6}的最大元是 。
20、无向图中有10条边，且每个结点的度数均为4，则结点数是 。
三、简答题（4小题，每小题6分，共24分）
得分
1、设={1,2,3,5,6,10,15,30} ， “／” 为集合上的整除关系。
(1)．〈，／〉是否为偏序集? 若是，画出其哈斯图；
(2)．〈，／〉是否构成格？为什么？
(3)．〈，／〉是否构成布尔代数？为什么？
2、为简单有向图，写出的邻接矩阵，算出，，且确定到有多少条长度为3的路? 到有多少条长度为2的路? 到自身长度为3和长度为4的回路各多少条?
3、对下图所给的偏序集，求下表所列集合的上确界，下确界，并将结果填入表中。
子 集
上确界
下确界
4、下图给出的赋权图表示八个城市及架起城市间直接通讯线路的预测造价，试给出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小造价。
四、证明题（2小题，每小题8分，共16分）
得分
1、设 定义为 ，证明：是双射，并求出其逆映射。
2、指出下面推理证明过程中的错误, 并给出正确的证明。
用谓词演算的推理规则证明：
证：(1) P (6) T(4) I
(2) US(1) (7) T(2),(5) I
(3) P (8) T(6),(7) I
(4) ES(3) (9) EG(8)
(5) T(4) I
一、单选题（20小题，每小题2分，共40分）
1、C
2、D
3、C
4、B
5、C
6、A
7、C
8、C
9、D
10、D
11、C
12、B
13、C
14、B
15、C
16、D
17、C
18、B
19、B
20、B
二、填空题（20小题，每空1分，共20分）
1、4，5，6
2、0
3、
4、图G连通
5、
6、
7、半群
8、
9、无
10、8
11、不存在
12、｛〈ａ，ｂ〉，〈ａ，ｃ〉，〈ｃ，ｃ〉｝
13、b
14、或PÚØ Q
15、2,3
16、
17、
18、1
19、无
20、5
三、简答题（4小题，每小题6分，共24分）
1、解：(1)．〈，／〉是偏序集。 其哈斯图为：
（3分）
(2)．〈，／〉构成格。因为其任意两个元素都有上确界和下确界。 （1分）
(3)．〈，／〉构成布尔代数。因为它是有界分配格，且其任意元素都有唯一补元素。 （2分）
2、解：邻接矩阵及，，如下：（2分）
=2，所以到长度为3的路有2条，它们分别是：和。
（1分）
=1，所以到长度为2的路有1条：。 （1分）
=0，到自身无长度为3的回路。 （1分）
=4，到自身有4条长度为4的回路，它们分别是：、、和。 （1分）
3、答：
子 集
上 确 界
下 确 界
无
无
4、解：该问题相当于求上图的最小生成树。按下图架起八个城市间直接通讯线路的造价最小．最小造价为：
W（T）=180+240+200+280+120+90+220=1330 （2分）
（4分）
四、证明题（2小题，每小题8分，共16分）
1、证明：
①
②
③
且是入射
根据①②③知f是双射
。
2、（1）该证明的错误在于: (1)、 (2) 与 (3)、 (4) 的顺序颠倒了，应该先指定存在后指定全称。 （2分）
（2）正确的证明是：（6分）
(1) P (6) T(2) I
(2) ES (1) (7) T(4),(5) I
(3) P (8) T(6),(7) I
(4) US (3) (9) EG(8)
(5) T(2) I
1 A 第 22 页 共 22 页
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
