离散数学期末模拟题

《离散数学》期末考试题(A)一、填空题(每小题3分，共15分)1.设}}{},,{{c b a A =，}}{},,{},{{c c b a B =，则)(=⋃B A ，)(=⋂B A ，)()(=A P .2.集合},,{c b a A =，其上可定义( )个封闭的1元运算，( )个封闭的2元运算，( )个封闭的3元运算.3.命题公式1)(↑∧q p 的对偶式为( ).4.所有6的因数组成的集合为( ).5.不同构的5阶根树有( )棵.二、单选题(每小题3分，共15分)1.设A , B 是集合，若A B A =-，则(A)B = ∅ (B) A = ∅ (C)=⋂B A ∅ (D)A B A =⋂2.谓词公式)())()((x R y yQ x P x ∧∃→∀中量词x ∀的辖域为(A))())()((x R y yQ x P x ∧∃→∀ (B))()(y yQ x P ∃→(C))())()((x R y yQ x P ∧∃→ (D))()(y yQ x P ∃→和)(x R3.任意6阶群的子群的阶一定不为(A)4 (B)6 (C)2 (D)34.设n 是正整数，则有限布尔代数的元素个数为(A)2n (B)4n (C)n 2 (D)2n5.对于下列序列，可构成简单无向图的度数序列为(A)3, 3, 4, 4, 5 (B)0, 1, 3, 3, 3 (C)1, 1, 2, 2, 3 (D)1, 1, 2, 2, 2三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”.1. 设N N N :⨯→f ，)1,()(+=x x x f ，则f 是满射. () 2. 5男5女圆桌交替就座的方式有2880种. () 3. 设),(≤L 是格，对于L z y x ∈,,，若z x y x ⋅=⋅且z x y x +=+，则z y =. () 4. 任何树都至少2片树叶. ()5. 无向图G 有生成树的充要条件是G 为连通图. ( )四、(10分)设C B A ,,和D 是集合，证明)()()()(D B C A D C B A ⨯-⨯⊆-⨯-，并举例说明上式中不能将⊆改为 = .五、(15分)设N 是自然数集合，定义N 上的关系R 如下：y x R y x +⇔∈),(是偶数，1.证明R 是N 上的等价关系.2.求出N 关于等价关系R 的所有等价类.3.试求出一个N 到N 的函数f ，使得)}()(,N ,|),{(y f x f y x y x R =∈=.六、(10分)在实数集合R 中证明下列推理的有效性:因为R 中存在自然数，而所有自然数是整数，所以R 中存在整数.七、(10分)设R 是实数集合，令}0,R ,|),{(≠∈=a b a b a G ，定义G 上的运算如下: 对于任意G d c b a ∈),(),,(，),(),(),(b ad ac d c b a +=⋅，证明),(⋅G 是非Abel 群.八、(10分)若简单平面图G 的节点数7=n 且边数15=m ，则G 是连通图，试证明之.《离散数学》期末考试题(B)一、填空题(每小题3分，共15分)1.设,,},,{{b a b a A =∅}，则-A ∅ = ( )，-A {∅} = ( )，)(A P 中的元素个数=|)(|A P ( ).2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数.3.谓词公式))()(())()((y P y Q y x Q x P x ⌝∧∃∧→∀中量词x ∀的辖域为( ), 量词y ∃的辖域为( ).4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元.5.当n ( )时，n 阶完全无向图n K 是平面图，当n 为( )时，n K 是欧拉图.二、单选题(每小题3分，共15分)1.设R 是集合A 上的偏序关系，1-R 是R 的逆关系，则1-⋃R R 是A 上的(A)偏序关系 (B)等价关系 (C)相容关系 (D)以上结论都不成立2.由2个命题变元p 和q 组成的不等值的命题公式的个数有(A)2 (B)4 (C)8 (D)163.设p 是素数且n 是正整数，则任意有限域的元素个数为(A)n p + (B)pn (C)n p (D)pn4.设R 是实数集合，≤是其上的小于等于关系，则(R, ≤)是(A)有界格 (B)分配格 (C)有补格 (D)布尔格5.3阶完全无向图3K 的不同构的生成子图有(A)2 (B)3 (C)4 (D)5 三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”.1.若一个元素a 既存在左逆元l a ，又存在右逆元r a ，则r l a a =. ( )2.命题联结词→不满足结合律. ( )3.在Z 8 = {0，1，2，3，4，5，6，7}中，2关于“⋅8”的逆元为4. ( )4.整环不一定是域. ( )5.任何),(m n 平面图的面数2+-=n m r . ( )四、(10分)设B A f →:且C B g →:，若g f 是单射，证明f 是单射，并举例说明g 不一定是单射.五、(15分)设},,,{d c b a A =,A 上的关系)},(),,(),,(),,(),,(),,(),,(),,(),,{(c d b d a d c c b c a c c a b a a a R =,1.画出R 的关系图R G .2.判断R 所具有的性质.3.求出R 的关系矩阵R M .六、(10分)利用真值表求命题公式))(())((p q r r q p A →→↔→→=的主析取范式和主合取范式.七、(10分) 边数30<m 的简单平面图G ，必存在节点v 使得4)deg(≤v .八、(10分) 有六个数字，其中三个1，两个2，一个3，求能组成四位数的个数.《离散数学》期末考试题(C)一、填空题(每小题3分，共15分)1. 若n B m A ==||,||，则=⨯||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个.2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3,1)}，则( )是单射，( )是满射，( )是双射.3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号).(1)q q p p →→∧)(；(2))(q p p ∨→；(3))(q p p ∧→；(4)q q p p →∨∧⌝)(；(5)q q p →→)(.4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ).5. 设G 是(7, 15)简单平面图，则G 一定是( )图，且其每个面恰由( )条边围成，G 的面数为( ).二、单选题(每小题3分，共15分)1. 设A , B , C 是集合，则下述论断正确的是( ).(A)若A ⊆ B ， B ∈ C ，则A ∈ C . (B)若A ⊆ B ， B ∈ C ，则A ⊆ C .(C)若A ∈ B ， B ⊆ C ，则A ∈ C . (D)若A ∈ B ， B ⊆ C ，则A ⊆ C .2. 设R ⊆ A ⨯ A ，S ⊆ A ⨯ A ，则下述结论正确的是( ).(A)若R 和S 是自反的，则R ⋂ S 是自反的.(B)若R 和S 是对称的，则S R 是对称的.(C)若R 和S 是反对称的，则S R 是反对称的.(D)若R 和S 是传递的，则R ⋃ S 是传递的.3.在谓词逻辑中，下列各式中不正确的是( ).(A))()())()((x xB x xA x B x A x ∀∨∀=∨∀(B))()())()((x xB x xA x B x A x ∀∧∀=∧∀(C))()())()((x xB x xA x B x A x ∃∨∃=∨∃(D)),(),(y x xA y y x yA x ∀∃=∃∀4. 域与整环的关系为( ).(A)整环是域 (B)域是整环 (C)整环不是域 (D) 域不是整环5.设G 是(n , m )图，且G 中每个节点的度数不是k 就是k + 1，则G 中度数为k 的节点个数为( ). (A)2n . (B)n (n + 1). (C)nk . (D)m k n 2)1(-+. 三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”.1.设f : Z → Z ，x x x f 2||)(-=，则f 是单射. ( )2.设ϕ是群G 1到群G 2的同态映射，若G 1是Abel 群，则G 2是Abel 群. ( )3.设),(≤L 是格，对于L z y x ∈,,，若z x y x ⋅=⋅且z x y x +=+，则z y =. ( )4.元素个数相同的有限布尔代数都是同构的. ( )5.设G 是n (n ≥ 11)阶简单图，则G 或G 是非平面图. ( )四、(15分)设A 和B 是集合，使下列各式(1)A B A =⋂； (2)A B B A -=-；(3)A A B B A =-⋃-)()(成立的充要条件是什么，并给出理由.五、(10分) 设S 是实数集合R 上的关系，其定义如下∈=y x y x S ,|),{(R 且是3y x -是整数}， 证明: S 是R 上的等价关系. 六、(10分) 求谓词公式)))()(()(()(x xD y yC y B x xA ∀→∃⌝→→∃的前束范式.七、(10分) 若n 个人，每个人恰有3个朋友，则n 必为偶数，试证明之.八、(10分) 利用生成函数求解递归关系⎩⎨⎧=-+=-2)1(211a n a a n n .《离散数学》期末考试题(D)一、填空题(每小题3分，共15分)1. 设|A | = 5, |B | = 2, 则可定义A 到B 的函数( )个，其中有( )单射，( )个满射.2. 令G (x ): x 是金子，F (x ): x 是闪光的，则命题“金子都是闪光的，但闪光的未必是金子”符号化为( ).3. 设X 是非空集合，则X 的幂集P (X )关于集合的⋃运算的单位元是( )，零元是( )，P (X )关于集合的⋂运算的单位元是( ).4. 不同构的5阶无向树有( )棵.5. 对于n 阶完全无向图K n , 当n 为( )时是Euler 图，当n ≥ ( )时是Hamilton 图，当n ( )时是平面图.二、单选题(每小题3分，共15分)1. 幂集P (P (P (∅))) 为( )(A){{∅}, {∅, {∅}}}. (B){∅, {∅, {∅}}, {∅}}.(C){ ∅, {∅, {∅}}, {{∅}}, {∅}} (D){ ∅, {∅, {∅}}}.2. 设R 是集合A 上的偏序关系，则1-⋃R R 是( ).(A)偏序关系 (B)等价关系 (C)相容关系 (D)以上答案都不对3. 下列( )组命题公式是不等值的.(A))(B A →⌝与B A ⌝∧. (B) )(B A ↔⌝与)()(B A B A ∧⌝∨⌝∧.(C))(C B A ∨→与C B A →⌝∧)(. (D))(C B A ∨→与)(C B A ∨∧⌝.4.下列代数结构(G , *)中，( )是群.(A)G = {0, 1, 3, 5}, “*”是模7加法. (B) G = Q , “*”是数的乘法.(C)G = Z , “*”是数的减法. (D) G = {1, 3, 4, 5, 9}, “*”是模11乘法.5.4阶完全无向图4K 中含3条边的不同构的生成子图有(A)3 (B)4 (C)5 (D)2三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”.1.函数的复合运算“ ”满足结合律. ( )2. {→⌝,}是最小功能完备联结词集合. ( )3. 实数集R 关于数的乘法运算“⋅”阿贝尔群. ( )4. 任意有限域的元素个数为2n . ( )5. 设G 是n (n 为奇数)简单图，则G 与G 中度数为奇数的节点个数相同. ( )四、(10分)设A 和B 是集合，使B B A =-成立的充要条件是什么，并给出理由.五、(10分) 设R 和S 是集合A 上的对称关系，证明S R 对称的充要条件是R S S R =.六、(15分)分别利用(1)等值演算法和(2)真值表求命题公式))(())((r q p p q r A ∨→→→∨⌝=的主析取范式和主合取范式.七、(10分) 设G 是(n , m )无向图，若n m ≥，证明G 中必存在圈.八、(10分) 在初始条件f (1) = c 下，求解递归关系bn n f n f +⎪⎭⎫ ⎝⎛=22)(，其中b ，c 为常数且kn 2=，k 为正整数.《离散数学》期末考试题(E)一、填空题(每小题3分，共15分)1.设A = {2, {3}, 4, a }, B = {1, 3, 4, {a }}, 则{3}( )A ，{a }( )B ，{{a }}( )B .2. 设A = {1, 2, 3, 4, 5}上的关系R = {(1, 2), (3, 4), (2, 2)}, S = {(4, 2), (2, 5), (3, 1), (1, 3)}, 则=S R { }, =R S { }, =R R { }.3. gcd(36, 48) = ( )，lcm(36, 48) = ( ).4.任意有限布尔代数)1,0,,,,(⋅+B 均与集合代数( )同构，其元素个数为( ).5. 不同构的5阶无向树有( )棵，不同构的5阶根树有( )棵.二、单选题(每小题3分，共15分)1. 在有理数集合Q 上定义运算“*”如下：对于任意x , y ∈ Q ，y x * = x + y – xy ，则Q 关于*的单位元是( ).(A)x . (B)y . (C)1. (D)0.2. 设A = {1, 2, 3}, 下图分别给出了A 上的两个关系R 和S ，则S R 是( )关系.(A)自反. (B)对称. (C)传递. (D)等价.3.令T (x ): x 是火车，B (x ): x 是汽车，F (x , y ): x 比y 快，则“某些汽车比所有的火车慢”符号化为( ).(A)()()),()()(y x H x T x y B y →∀∧∃.(B)()()),()()(y x H x T x y B y ∧∀→∃.(C)()()),()()(y x H x T y B y x ∧→∃∀.(D)()()),()()(y x H x T x y B y →∀→∃.4. 整数集合Z 关于数的加法“+”和数的乘法“⋅”构成的代数结构(Z, +, ⋅)是( ). 1 1 22 3 3G S G R(A)域(B)域和整环(C)整环(D) 有零因子环G≅，则称G为自补图. 5阶不同构的自补图5.设G是简单图，G是G的补图，若G个数为( ).(A)0. (B)1. (C)2. (D)3.三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”.1. { ∅, {∅}} ∉P(P({∅})). ( )2. 非空1元及2元联结词集合的个数为29-1. ( )3. 群可分为Abel群和非Abel群. ( )4. 元素个数相同的有限域都是同构的. ( )5. 设G是简单图，则G或G是连通图. ( )四、(15分)设C,:, 若gf 是单射，证明f是单射，并举例说明g→:f→gBBA不一定是单射.五、(10分)设A = {a, b, c, d}上的关系R = {(a, b), (b, d), (c, c), (a, c)}, 画出R的关系图，并求出R的自反闭包r(R)、对称闭包s(R)和传递闭包t(R).六、(10分)用CP规则证明下列推理.⌝∨→∨(.⇒),(⌝),→pqssrqrqp→七、(10分)求谓词公式))xyByAxA∀→∨∀∧⌝∃的前束范式.zC((x()))(z(()八、(10分)任意6个人中，一定有3个人彼此认识或有3个人彼此不认识.《离散数学》期末考试题(F)一、填空题(每小题3分，共15分)1. 设A = {1, 2, 3, {1, 2}, {3}}, B = {2, {2,3}, {1}} , 则A–B = { }, B–A = { }, A⊕B = { }.2. 实数集合R关于加法运算“+”的单位元为( ), 关于乘法运算“⋅”的单位元为( ), 关于乘法运算“⋅”的零元为( ).3. 令Z(x): x是整数，O(x): x是奇数，则“不是所有整数都是奇数”符号化为( ).4. 有限域的元素个数为( ), 其中( )且( ).5. 设G 是(7, 15)简单平面图，则G 一定 ( )连通图，其每个面恰由( )条边围成，G 的面数为( ).二、单选题(每小题3分，共15分)1. 函数的复合运算“ ”满足( )(A)交换律. (B)结合律. (C)幂等律. (D)消去律.2. 设集合A 中有4个元素，则A 上的等价关系共有( )个.(A)13 (B)14 (C)15 (D)163.下列代数结构(G , *)中，( )是群.(A)G = {0, 1, 3, 5}, “*”是模7加法. (B) G = Q , “*”是数的乘法.(C)G = Z , “*”是数的减法. (D) G = {1, 3, 4, 5, 9}, “*”是模11乘法.4. 下列偏序集，( )是格.5. 不同构的(5, 3)简单无向图有( )个.(A)4 (B)5 (C)3 (D)2三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”.1. 设A ，B ，C 是集合，若C A B A ⊕=⊕, 则B = C . ( )2. 逻辑联结词“→”满足结合律. ( )3. 设 (L , ≤)是偏序集，若L 的任意非空子集均存在上确界和下确界，则(L , ≤)是格.( )4. 在同构意义下，有限布尔代数只有,,,),((⋂⋃X P ∅, X ). ( )5. 设G 是简单图，则G 与G 中度数为奇数的节点个数相同. ( )四、(15分) 设C B g B A f →→:,:, 若g f 是满射，证明g 是满射，并举例说明f 不一定是满射.五、(10分) 在整数集合Z 上定义关系R 如下：对于任意∈y x , Z ，y y x x R y x +=+⇔∈22),(.判断R 是否具有自反性、反自反性、对称性、反对称性及传递性.六、(10分)利用真值表求命题公式)())(q p q p A ⌝→↔→⌝=的主析取范式和主合取范式.七、(10分)证明：在至少两个人的人群中，必有两个人有相同个数的朋友.八、(10分)将6阶完全无向图K 6的边随意地涂上红色或蓝色，证明：无论如何涂法，总存在红色的K 3或蓝色的K 3.(ps ：答案见离散数学期末复习题（6套）答案文档)。

一、单项选择题（每小题3分，共30分）1．下列为两个命题变元ｐ，ｑ的最小项的是（ ） A ．ｐ∧ｑ∧⎤ ｐB ．⎤ ｐ∨ｑC ．⎤ ｐ∧ｑD ．⎤ ｐ∨ｐ∨ｑ 2．下列句子不是命题的是（ ） A ．中华人民共和国的首都是北京 B ．张三是学生 C ．雪是黑色的D ．太好了！3．对于公式(∀x ) (∃y )(P (x )∧Q (y ))→(∃x )R (x ,y )，下列说法正确的是（ ） A ．y 是自由变元 B ．y 是约束变元C ．(∃x )的辖域是R(x , y )D ．(∀x )的辖域是(∃y )(P (x )∧Q (y ))→(∃x )R (x ,y )4．7．集合A={1，2，…，10}上的关系R={（x ，y ）|x +y =10，x ∈A ，y ∈A}，则R 的性质是（ ）A ．自反的B ．对称的C ．传递的、对称的D ．反自反的、传递的 5．设论域为{l ，2}，与公式)(x xA ∃等价的是( ) A.A (1)∨A (2)B. A (1)→A (2)C.A (1)D. A (2)→A (1)6. 下列关系矩阵所对应的关系具有反自反性的是（ ） A ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001110101B ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡101100001 C ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001100100D ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡0010101017. 下列运算不满足．．．交换律的是（ ） A ．a *b =a+2bB ．a *b =min(a ,b )C ．a *b =|a -b |D ．a *b =2ab8．.设A 是奇数集合，下列构成独异点的是( ) A.<A ，+> B.<A ，-> C.<A ，×> D.<A ，÷> 9. 右图的最大入度是( ) A ．0 B ．1 C ．2D ．3第9题图拟题学院（系）： 高密校区 适用专业： 学年 2学期 离散数学 （Ｂ卷） 试题标准答案10. 设有向图D 的节点数大于1，D=（V ,E ）是强连通图，当且仅当（ ） A. D 中至少有一条通路 B. D 中至少有一条回路C. D 中有通过每个结点至少一次的通路D. D 中有通过每个结点至少一次的回路 二、填空题(每空3分，共30分)1．设A ={1，2，3，4}，B ={2，4，6}，则A -B =________，A ⊕B =________。

一、选择题（每题2分，共20分）1. 下列命题中，正确的是（）A. 逻辑真命题一定是逻辑假命题B. 逻辑假命题一定是逻辑真命题C. 逻辑真命题和逻辑假命题都是存在的D. 逻辑真命题和逻辑假命题都不存在2. 设A和B是两个集合，则下列命题中正确的是（）A. A∩B = A∪BB. A∩B = A-BC. A∪B = A∩BD. A-B = A∩B3. 设A和B是两个集合，则下列命题中正确的是（）A. A⊆B当且仅当A∩B = AB. A⊆B当且仅当A∩B = BC. A⊆B当且仅当A-B = ∅D. A⊆B当且仅当A∪B = B4. 下列命题中，不是逻辑等价命题的是（）A. A→B与¬A∨BB. A∧B与A→BC. A∨B与B→AD. A→B与¬B∨A5. 设R是一个关系，下列命题中正确的是（）A. R是等价关系当且仅当R是自反的、对称的和传递的B. R是等价关系当且仅当R是自反的、非对称的和传递的C. R是等价关系当且仅当R是非自反的、对称的和传递的D. R是等价关系当且仅当R是非自反的、非对称的和传递的6. 设P和Q是两个命题，则下列命题中正确的是（）A. P∧Q的否定是P∨QB. P∧Q的否定是P∧QC. P∨Q的否定是P∧QD. P∨Q的否定是P∧Q7. 设R是一个偏序关系，下列命题中正确的是（）A. R是自反的、反对称的和传递的B. R是自反的、对称的和传递的C. R是自反的、非对称的和传递的D. R是非自反的、对称的和传递的8. 设R是一个全序关系，下列命题中正确的是（）A. R是自反的、反对称的和传递的B. R是自反的、对称的和传递的C. R是自反的、非对称的和传递的D. R是非自反的、对称的和传递的9. 设R是一个函数，下列命题中正确的是（）A. R是单射当且仅当R是满射B. R是单射当且仅当R是自反的C. R是满射当且仅当R是自反的D. R是单射当且仅当R是反对称的10. 设R是一个关系，下列命题中正确的是（）A. R是等价关系当且仅当R是自反的、对称的和传递的B. R是等价关系当且仅当R是自反的、非对称的和传递的C. R是等价关系当且仅当R是非自反的、对称的和传递的D. R是等价关系当且仅当R是非自反的、非对称的和传递的二、填空题（每题2分，共20分）1. 在集合A={1, 2, 3}中，A的子集个数是______。

2 离散数学（A 卷） 王军东（答案写在答题纸上，写在试题纸上无效）一、单项选择题（每小题3分，共30分）1．设A , B 是集合，若A B A =-，则(A) B = ∅ (B) A = ∅ (C) =⋂B A ∅ (D) A B A =⋂2．在有理数集合Q 上定义运算“*”如下：对于任意x , y ∈ Q ，y x * = x + y – xy ，则Q 关于*的单位元是( ).(A)x . (B)y . (C)1. (D)0.3．谓词公式)())()((x R y yQ x P x ∧∃→∀中量词x ∀的辖域为(A))())()((x R y yQ x P x ∧∃→∀ (B))()(y yQ x P ∃→(C))())()((x R y yQ x P ∧∃→ (D))()(y yQ x P ∃→和)(x R4．设p ：我们划船，q ：我们跑步, 则有命题“我们不能既划船又跑步”符号化为( )(A) ⌝ p ∧⌝ q (B) ⌝ p ∨⌝ q (C) ⌝ (p ↔ q ) (D) ⌝ (⌝ p ∨⌝ q ).5．设Z +是正整数集，R 是实数集，f :Z +→R , f (n )=log 2n ,则f （ ）A ．仅是单射B ．仅是满射C ．是双射D ．不是函数6. 设集合A = {1, 2, 3, 4, 5}上的关系R = {(x , y )|x , y ∈ A 且x + y = 6}，则R 的性质是( ).(A) 自反的. (B) 对称的. (C) 对称的、传递的. (D) 反自反的、传递的.7. 下列联结词中，不满足交换律的是( ).(A)∧. (B)∨. (C)⊕. (D) →.8．.设G 是n 阶简单无向图，则其最大度)(G ∆( ).(A) > n (B) ≤ n . (C) < n . (D) ≥ n .9. 下列所示的哈斯图所对应的偏序集中能构成格的是（ ）A ．B ．C ．D ．课程考试试题学期 学年 拟题人:校对人:拟题学院（系）: 适 用 专 业:10. 设G 是(n , m )图，且G 中每个节点的度数不是k 就是k + 1，则G 中度数为k 的节点个数为( ). (A)2n . (B)n (n + 1). (C)nk . (D)m k n 2)1(-+. 二、填空题(每空3分，共30分)1．设A={1，2}，B={2，3}，则A-B=_______， A ⊕B=________，2．设A={2,3 }，R ⊆A ×A ，R={(2,3)， (2,2)}，则R 的自反闭包r(R)=__________,对称闭包s(R)=__________。

《离散数学》模拟题北航10秋学期《离散数学》模拟题⼀⼀、单项选择题（本⼤题共15⼩题，每⼩题2分，共30分）1.∑中所有有限长度的串形成的集合记为∑* ，容易证得∑*上的连接运算不满⾜交换律，但满⾜（ A ） A ．结合律 B ．分配律 C ．幂等律 D ．吸收律 2.Klein 群中元素a,b,c 的阶为（ B ）。

A ．1B ．2C ．3D ．4 3.群G 的元素x 的所有幂的集合为G 的⼦群,称由x ⽣成的⼦群。

记为（ A ）. A ． B ．(x) C ．x D ．[x] 4.交换环是指乘法满⾜（ A ）。

A ．交换律B ．结合律C ．分配律D ．吸收律 5.⾄少有（ B ）元素的含单位元、⽆零因⼦环称为除环。

A ．⼀ B ．⼆ C ．三 D ．四 6.∨,∧满⾜( C )的格称为分配格A ．交换律B ．结合律C ．分配律D ．幂等律 7.若L 为有限布尔代数,则（ B ）正整数n ，L 与含有n 个元素的集合A 的幂集同构。

A ．不存在 B ．存在 C ．有可能存在 8.有向图D 的顶点v 作为边的始点的次数之和称为v 的出度，记为d +(v)， v 作为边的终点的次数之和称为v 的⼊度，记为d -(v)，v 的度数d(v)= ( A )。

A ．d +(v)+d -(v)B ．d +(v)C ．d -(v)D ．d +(v)*d -(v) 9.若通路Г=v 0e 1v 1e 2…e 1v 1 中所有顶点互不相同(所有边⾃然互不相同)时称为（ B ） A ．初级回路 B ．路径 C ．复杂通路D ．迹 10.在n 阶图中，若⼀顶点存在到⾃⾝的回路，则必存在从该顶点到⾃⾝的长度不超过( B )的回路。

A ．n-1 B ．n C ．n+1 D ．2n 11.“⼈总是要死的”谓词公式表⽰为（ C ）。

（论域为全总个体域）M(x)：x 是⼈；Mortal(x)：x 是要死的。

A ．)()(x Mortal x M →； B ．)()(x Mortal x M ∧C ．))()((x Mortal x M x →?； D ．))()((x Mortal x M x ∧?12. 公式))()((x Q x P x A →?=的解释I 为：个体域D={2}，P(x)：x>3, Q(x)：x=4则A 的真值为（ A ）。

离散数学期末考试模拟题１一、单项选择题（每小题1分，共15分。

四选一）1、设Φ是一个空集，则下列之一哪一个不成立（）。

⊆Φ③、Φ∈{Φ} ④、Φ⊆{Φ}①、Φ∈Φ②、Φ2、如果命题公式G=P∧Q，则下列之一哪一个成立（）。

①、G=⌝(P→Q) ②、G=⌝(P→⌝Q) ③、G=⌝(⌝P→Q) ④、G=⌝(⌝P→⌝Q)3、设X、Y是两个集合|X|＝n，|Y|＝m，则从X到Y可产生（）个二元关系。

①、n m②、m n③、m×n ④、2m×n*，⊕>中，∀a,b∈L，a≤b当切仅当下列（）成立。

4、在有补分配格<L，*b＝b ②、a⊕b＝a ③、a＇*b＝0 ④、a＇⊕b＝1①、a5、若<G,*>是一个群，则运算“*”一定满足（）。

①、交换律②、消去律③、幂等律④、分配律6、量词的约束范围称为量词的（）。

①、定义域②、个体域③、辖域④、值域7、下列公式中，（）是析取范式。

①、⌝(P∧Q) ②、⌝(P∨Q) ③、(P∨Q) ④、(P∧Q)8、设G是一个12阶循环群，则该群一定有（）个不变子群。

①、2 ②、4 ③、6 ④、89、图的构成要素是（）。

①、结点②、边③、结点与边④、结点、变和面10、下列图中，（）是平面图。

①②③④11、每个非平凡的无向树至少有（）片树叶。

①、1 ②、2 ③、3 ④、412、每个无限循环群有（）个生成元。

①、1 ②、2 ③、3 ④、413、设R是集合A＝{1,2,3,4}上的二元关系，R＝{<2,1>,<2,3>,<1,3>},则下列（）不成立。

①、R是自反关系②、R是反自反关系③、R是反对称关系④、R是传递关系14、设G是一个24阶群，a是G中任意一个元素，则a的周期一定不是（）。

①、2 ②、8 ③、16 ④、2415、下列命题中，（）不是真命题。

①、海水是咸的当切仅当蝙蝠是瞎子②、如果成都是直辖市，那么北京是中国的首都③、若太阳从西边落下，则2是奇数④、夏天冷当切仅当冬天热二、多项选择题（每小题1分，共10分。

大学离散数学期末考试题库和答案一、单项选择题（每题2分，共20分）1. 在集合论中，以下哪个符号表示“属于”？A. ∈B. ∉C. ⊆D. ⊂答案：A2. 如果A和B是两个集合，那么A∪B表示什么？A. A和B的交集B. A和B的并集C. A和B的差集D. A和B的补集答案：B3. 以下哪个命题是真命题？A. ∀x∈N, x^2 > xB. ∃x∈N, x^2 = x + 1C. ∀x∈N, x^2 ≥ xD. ∃x∈N, x^2 < x答案：C4. 在图论中，一个无向图的边数为E，顶点数为V，那么这个图的生成树的边数是多少？A. EB. V-1C. VD. E-1答案：B5. 以下哪个算法是用于解决旅行商问题（TSP）的？A. 动态规划B. 贪心算法C. 分支限界法D. 回溯法答案：D6. 在逻辑中，以下哪个符号表示“蕴含”？A. ∧B. ∨C. →D. ↔答案：C7. 以下哪个是二进制数？A. 1010B. 2A3C. 12BD. ZYX答案：A8. 在关系数据库中，以下哪个操作用于删除表中的行？A. SELECTB. INSERTC. UPDATED. DELETE答案：D9. 以下哪个是布尔代数的基本运算？A. 并集B. 交集C. 差集D. 所有以上答案：D10. 在离散数学中，以下哪个概念用于描述两个集合之间的关系？A. 函数B. 映射C. 序列D. 所有以上答案：D二、多项选择题（每题3分，共15分）11. 以下哪些是集合的基本运算？A. 并集B. 交集C. 差集D. 补集答案：ABCD12. 在图论中，以下哪些是图的基本类型？A. 无向图B. 有向图C. 完全图D. 二分图答案：ABCD13. 在逻辑中，以下哪些是命题逻辑的基本连接词？A. 与（∧）B. 或（∨）C. 非（¬）D. 蕴含（→）答案：ABCD14. 在关系数据库中，以下哪些是SQL的基本操作？A. SELECTB. INSERTC. UPDATED. DELETE答案：ABCD15. 在离散数学中，以下哪些是组合数学的基本概念？A. 排列B. 组合C. 二项式系数D. 图论答案：ABC三、填空题（每题3分，共30分）16. 如果集合A={1, 2, 3}，集合B={2, 3, 4}，那么A∩B=______。

离散数学期末考试模拟题１一、单项选择题（每小题1分，共15分。

四选一）1、设Φ是一个空集，则下列之一哪一个不成立（）。

⊆Φ③、Φ∈{Φ} ④、Φ⊆{Φ}①、Φ∈Φ②、Φ2、如果命题公式G=P∧Q，则下列之一哪一个成立（）。

①、G=⌝(P→Q) ②、G=⌝(P→⌝Q) ③、G=⌝(⌝P→Q) ④、G=⌝(⌝P→⌝Q)3、设X、Y是两个集合|X|＝n，|Y|＝m，则从X到Y可产生（）个二元关系。

①、n m②、m n③、m×n ④、2m×n*，⊕>中，∀a,b∈L，a≤b当切仅当下列（）成立。

4、在有补分配格<L，*b＝b ②、a⊕b＝a ③、a＇*b＝0 ④、a＇⊕b＝1①、a5、若<G,*>是一个群，则运算“*”一定满足（）。

①、交换律②、消去律③、幂等律④、分配律6、量词的约束范围称为量词的（）。

①、定义域②、个体域③、辖域④、值域7、下列公式中，（）是析取范式。

①、⌝(P∧Q) ②、⌝(P∨Q) ③、(P∨Q) ④、(P∧Q)8、设G是一个12阶循环群，则该群一定有（）个不变子群。

①、2 ②、4 ③、6 ④、89、图的构成要素是（）。

①、结点②、边③、结点与边④、结点、变和面10、下列图中，（）是平面图。

①②③④11、每个非平凡的无向树至少有（）片树叶。

①、1 ②、2 ③、3 ④、412、每个无限循环群有（）个生成元。

①、1 ②、2 ③、3 ④、413、设R是集合A＝{1,2,3,4}上的二元关系，R＝{<2,1>,<2,3>,<1,3>},则下列（）不成立。

①、R是自反关系②、R是反自反关系③、R是反对称关系④、R是传递关系14、设G是一个24阶群，a是G中任意一个元素，则a的周期一定不是（）。

①、2 ②、8 ③、16 ④、2415、下列命题中，（）不是真命题。

①、海水是咸的当切仅当蝙蝠是瞎子②、如果成都是直辖市，那么北京是中国的首都③、若太阳从西边落下，则2是奇数④、夏天冷当切仅当冬天热二、多项选择题（每小题1分，共10分。