资源描述
^.
离散数学期末复习题
第一章集合论
一、判断题
(1)空集是任何集合的真子集. ( 错 )
(2)是空集. ( 错 )
(3) ( 对 )
(4)设集合. ( 对 )
(5)如果,则或. ( 错 )
解 则,即且,所以且
(6)如果A∪ ( 对 )
(7)设集合,,则
( 错 )
(8)设集合,则是到的关系. ( 对 )
解 ,
(9)关系的复合运算满足交换律. ( 错 )
(10) ( 错 )
(11)设 ( 对 )
(12)集合A上的对称关系必不是反对称的. ( 错 )
(13)设为集合上的等价关系, 则也是集合上的等价关系( 对 )
(14)设是集合上的等价关系, 则当时, ( 对 )
(15)设为集合 上的等价关系, 则 ( 错 )
二、单项选择题
(1)设为实数集合,下列集合中哪一个不是空集 ( A )
A. B.
C. D.
(2)设为集合,若,则一定有 ( C )
A. B. C. D.
(3)下列各式中不正确的是 ( C )
A. B. C. D.
(4)设,则下列各式中错误的是 ( B )
A. B. C. D.
(5)设,,,则为 ( B )
A. B.
C. D.
(6)设,,则的恒等关系为 ( A )
A. B.
C. D.
(7)设上的二元关系如下,则具有传递性的为 ( D )
A.
B.
C.
D.
(8)设为集合上的等价关系,对任意,其等价类为 ( B )
A. 空集; B.非空集; C. 是否为空集不能确定; D. .
(9)映射的复合运算满足 ( B )
A. 交换律 B.结合律 C. 幂等律 D. 分配律
(10)设A,B是集合,则下列说法中( C )是正确的.
A.A到B的关系都是A到B的映射
B.A到B的映射都是可逆的
C.A到B的双射都是可逆的
D.时必不存在A到B的双射
(11)设A是集合,则( B )成立.
A.
B.
C.
D.
(12)设A是有限集(),则A上既是又是~的关系共有( B ).
A.0个
B.1个
C.2个
D.个
三、填空题
1. 设,则____________.
填
2.设,则= . 填
3.设集合中元素的个数分别为,,且,
则集合中元素的个数 .3
4.设集合,
,则中元素的个数为 .40
5.设 , 是 上的包含于关系,,则有
= .
6.设为集合 上的二元关系, 则 .
7.集合上的二元关系为传递的充分必要条件是 .
8. 设集合及集合A到集合的关系{|∩___________________.
填
四、解答题
1. 设 上的关系
(1)写出的关系矩阵;
(2)验证是上的等价关系;
(3)求出的各元素的等价类。
解 (1)的关系矩阵为
(2)从的关系矩阵可知:是自反的和对称的。
又由于
或满足
所以是传递的。
因为是自反的、对称的和传递的,所以是上的等价关系。
(3) ,
2. 设集合,是上的整除关系,
(1) 写出的关系矩阵;
(2) 画出偏序集的哈斯图;
(3) 求出的子集的最小上界和最大下界。
解:(1)
(2)
(3)lubB=6, glbB=1
五、证明题
1. 设为集合上的等价关系, 试证也是集合上的等价关系。
证明:由于是自反的,所以对任意,, 因而,即是自反的。
若,则,由于是对称的,所以, 从而,即是对称的。
若,则 ,由于是传递的,所以, 从而,即是传递的。
由于是自反的、对称的和传递的,所以是等价关系。
第二章 代数系统
一、判断题
(1)集合A上的任一运算对A是封闭的. ( 对 )
(2)代数系统的零元是可逆元. ( 错 )
(3)设A是集合,,,则是可结合的. ( 对 )
(4)设是代数系统的元素,如果是该代数系统的单位元),则 ( 对 )
(5)设 ( 错 )
(6)设是群.如果对于任意,有 ,则是阿贝尔群. ( 对 )
(7)设 ( 对 )
(8)设集合,则是格. ( 对 )
(9)设是布尔代数,则是格. ( 对 )
二、单项选择题
(1)在整数集上,下列哪种运算是可结合的 ( B )
A. B.
C. D.
(2)下列定义的实数集R上的运算 * 中可结合的是. ( C )
A.
B.
C.
D.
其中,+,,︱ ︱分别为实数的加法、乘法和取绝对值运算.
(3)设集合,下面定义的哪种运算关于集合不是封闭的
( D )
A.
B.
C. ,即的最大公约数
D. ,即的最小公倍数
(4)下列哪个集关于减法运算是封闭的 ( B )
A. (自然数集); B.;
C. ; D. .
(5)设是有理数集,在定义运算为,则的单位元
为 ( D )
A. ; B.; C. 1; D. 0
(6)设代数系统A,,则下面结论成立的是. ( C )
A.如果A,是群,则A,是阿贝尔群
B.如果A,是阿贝尔群,则A,是循环群
C.如果A,是循环群,则A,是阿贝尔群
D.如果A,是阿贝尔群,则A,必不是循环群
(7)循环群的所有生成元为 ( D )
A. 1,0 B.-1,2 C. 1,2 D. 1,-1
三、填空题
1. 设为非空有限集,代数系统中,对运算的单位元为 ,零元为 .填
2.代数系统中(其中为整数集合,+为普通加法),对任意的,其 .填
3.在整数集合上定义运算为,则的单位元为 .
解 设单位元为,,所以,
又,所以单位元为
4.在整数集合上定义运算为,则的单位元为 .
解设单位元为,,,所以
5.设是群,对任意,如果,则 .填
6.设是群,为单位元,若元素满足,则 .填
四、解答题
1.设为实数集上的二元运算,其定义为
,对于任意
求运算的单位元和零元。
解:设单位元为,则对任意,有,
即 ,由的任意性知 ,
又对任意,;
所以单位元为0
设零元为,则对任意,有,
即 ,由的任意性知
又对任意,,
所以零元为
2. 设为集合上的二元运算,其定义为
,对于任意
(1) 写出运算的运算表;
(2) 说明运算是否满足交换律、结合律,是否有单位元和零元、如果有请指出;
(3) 写出所有可逆元的逆元
解:(1)运算表为
0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1
(2)运算满足交换律、结合律,有单位元,单位元为1,有零元,零元为0;
(3)1的逆元为1,2的逆元为3,3的逆元为2,4的逆元4,0没有逆元
五、证明题
1. 设 是一个群,试证 是交换群 当且仅当对任意的 ,有
.
证明:充分性
若在群中,对任意的 ,有 .
则
从而 是一个交换群。
必要性
若 是一个交换群,对任意的 ,有,则
即.
2. 证明代数系统是群,其中二元运算定义如下:
:,
(这里,+,-分别是整数的加法与减法运算.)
证明 (1)运算满足交换律
对任意Z,由
满足结合律;
(2)有单位元 3是单位元;
(3)任意元素有逆元
对任意Z,Z,是群.
第三章 图论
一、判断题
(1)n阶完全图的任意两个不同结点的距离都为1. ( 对 )
(2)图G的两个不同结点连接时一定邻接. ( 错 )
(3)图G中连接结点 ( 错 )
(4)在有向图中,结点到结点的有向短程即为到的有向短程.
( 错 )
(5)强连通有向图一定是单向连通的. ( 对 )
(6)不论无向图或有向图,初级回路一定是简单回路. ( 对 )
(7)设图G是连通的,则任意指定G的各边方向后所得的有向图是弱连通的.
( 对 )
(8)有生成树的无向图是连通的. (对)
(9)下图所示的图是欧拉图. ( 错 )
(10)下图所示的图有哈密尔顿回路. ( 对 )
二、单项选择题
(1)仅由孤立点组成的图称为 ( A )
A. 零图; B.平凡图; C. 完全图; D. 多重图.
(2)仅由一个孤立点组成的图称为 ( B )
A. 零图; B.平凡图; C.多重图; D. 子图.
(3)在任何图中必有偶数个 ( B )
A. 度数为偶数的结点; B.度数为奇数的结点;
C. 入度为奇数的结点; D. 出度为奇数的结点.
(4)设为有个结点的无向完全图,则的边数为 ( C )
A. B. C. D.
(5)在有个结点的连通图中,其边数 ( B )
A. 最多条; B.至少条;
C. 最多条; D. 至少条.
(6)任何无向图中结点间的连通关系是 ( B )
A. 偏序关系; B.等价关系;
C. 既是偏序关系又是等价关系; D. 既不是偏序关系也不是等价关系.
(7)对于无向图,下列说法中正确的是. ( B )
A.不含平行边及环的图称为完全图
B.任何两个不同结点都有边相连且无平行边及环的图称为完全图
C.具有经过每条边一次且仅一次回路的图称为哈密尔顿图
D.具有经过每个结点一次且仅一次回路的图称为欧拉图
(8)设D是有向图,则D强连通的充分必要条件为. ( C )
A.略去D中各边方向后所得到的无向图是连通的
B.D是单向连通图,且改变它的各边方向后所得到的有向图也是单向连通图
C.D的任意两个不同的结点都可以相互到达
D.D是完全图
(9)对于无向图G,以下结论中不正确的是. ( A )
A.如果G的两个不同结点是连接的,则这两个结点之间有初级回路
B.如果G的两个不同结点是连接的,则这两个结点之间至少有一条短程
C.如果G是树,则任何两个不同结点之间有且仅有一条初级通路
D.如果G是欧拉图,则G有欧拉回路
三、填空题
1. 设树T中有7片树叶,3个3度结点,其余都是4度结点,则T中有 个4度结点.
解 用握手定理和树的性质列出方程求解,设有个4度结点,
,
2.设为树,中有4度,3度,2度分支点各1个,问中有 片树叶。
解 与上题解法相同,设有片树叶,,
3.n阶完全图的任意两个不同结点的距离都为 .1
4.图为阶无向完全图,则共有 条边。
5.设为图,则图中结点度数的总和为 。
6. 图G为欧拉图的充分必要条件是_____________________. G为无奇度结点的连通图
四、解答题
1. 对下图所示的图G,求
(1)G的邻接矩阵;
(2)G的结点之间长度为3的通路;
(3)G的连接矩阵;
(4)G的关联矩阵。
解 (1) A=
(2) 因为
A2= A3=
所以,结点之间长度为3的通路共有7条,它们是
(3)由于图G是连通的,所以
C=
(4)
M=
2. 在下面的有向图中,回答下列问题
(1)写出图的邻接矩阵;
(2)写出结点到结点的长度为3的所有有向通路;
(3)写出结点到自身的长度为3的所有有向回路;
解:(1)
(2)
所以结点到结点的长度为3的所有有向通路只有一条:
(3)结点到自身的长度为3的所有有向回路只有一条:
3.在下面的无向图中,回答下列问题
(1)写出之间的所有初级通路;
(2)写出之间的所有短程,并求;
(3)判断无向图是否为欧拉图并说明理由。
解(1)之间的所有初级通路共有7条,分别为
,,,,,,
(2)之间的长度最短的通路只有1条,即,因而它是之间
唯一的短程,
(3)由于无向图中有两个奇度顶点,所以无向图没有欧拉回路,因而不是欧拉图。
第四章 数理逻辑
一、判断题
(1)“如果8+7>2,则三角形有四条边”是命题. ( 对 )
(2)设都是命题公式,则也是命题公式. ( 错 )
(3)命题公式的真值分别为0,1,则的真值为0
(以上是在对所包含的命题变元的某个赋值下). ( 错 )
(4)设他生于1964年,则命题“他生于1963年或1964年”可以符号化为 ( 对 )
(5)设P,Q都是命题公式,则( 对 )
(6)逻辑结论是正确结论. ( 错 )
(9)设都是命题公式,则
也是命题公式. ( 对 )
(10)命题公式的真值分别为0,1,则的真值为0
(以上是在对所包含的命题变元的某个赋值下). ( 对 )
二、单项选择题
(1)下面哪个联结词不可交换 ( B )
A. ; B.; C.; D. .
(2)命题公式是 ( C )
A. 永假式; B.非永真式的可满足式;
C. 永真式; D. 等价式.
(3)记他懂法律,他犯法,则命题“他只有懂法律,才不会犯法”可符号化为( B ).
A.
B.
C.
D.
(4)下列命题中假命题是( B ).
A.如果雪不是白的,则太阳从西边出来
B.如果雪是白的,则太阳从西边出来
C.如果雪不是白的,则太阳从东边出来
D.只要雪不是白的,太阳就从西边出来
(5)设A,B都是命题公式,则A→B为可满足式是的( B ).
A.充分而非必要条件
B.必要而非充分条件
C.充分必要条件
D.既非充分又非必要条件
三、填空题
1.设 天气很冷,老王还是来了,则命题“虽然天气很冷, 但老王还是来了”符号化为 .
2.设天下雨, 我骑自行车上班,则命题“如果天不下雨, 我就骑自行车上班”符号化为 .
3. 设的真值为0,的真值为1,则命题公式的真值为 .0
4.设的真值为0,的真值为1,则命题公式的真值为 .0
展开阅读全文
相关搜索