北方工业大学离散数学期末试卷B

离散数学期末考试试题及答案离散数学期末考试试题及答案离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。

下面是小编整理的离散数学期末考试试题及答案，欢迎阅读参考！一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。

1、在由3个元素组成的集合上，可以有 ( ) 种不同的'关系。

[A] 3 [B] 8 [C]9 [D]272、设A1,2,3,5,8,B1,2,5,7,则AB( )。

[A] 3,8 [B]3 [C]8 [D]3,83、若X是Y的子集，则一定有( )。

[A]X不属于Y [B]X∈Y[C]X真包含于Y [D]X∩Y=X4、下列关系中是等价关系的是( )。

[A]不等关系 [B]空关系[C]全关系 [D]偏序关系5、对于一个从集合A到集合B的映射，下列表述中错误的是( )。

[A]对A的每个元素都要有象 [B] 对A的每个元素都只有一个象[C]对B的每个元素都有原象 [D] 对B的元素可以有不止一个原象6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为( )。

[A]p→q [B]q→p [C]┐q→┐p [D]┐p→q7、设A={a,b,c},则A到A的双射共有( )。

[A]3个 [B]6个 [C]8个 [D]9个8、一个连通G具有以下何种条件时，能一笔画出：即从某结点出发，经过中每边仅一次回到该结点( )。

[A] G没有奇数度结点 [B] G有1个奇数度结点[C] G有2个奇数度结点 [D] G没有或有2个奇数度结点9、设〈G,*〉是群，且|G|>1，则下列命题不成立的是( )。

[A] G中有幺元 [B] G中么元是唯一的[C] G中任一元素有逆元 [D] G中除了幺元外无其他幂等元10、令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为( )[A] p→┐q [B] p∨┐q[C] p∧q [D] p∧┐q11、设G=的结点集为V={v1,v2,v3},边集为E={,}.则G的割(点)集是( )。

精品文档. B 卷1． Show that ((p ∨q)∧⌝p) → q are tautologies. (10 scores)2. Suppose that f(x),g(x) and h(x) are functions such that f(x ) is Ω(g(x)) and g(x) is Ω (h(x)).Show that f(x) is Ω (h(x)).(10 scores)3. Let ⎥⎦⎤⎢⎣⎡=0312A and ⎥⎦⎤⎢⎣⎡=3221B .Find B t A t . (10 scores) 4. Find a compatible total ordering for the poset ({2,4,6,9,12,18,27,36,48,60,72},|).(10 scores) 5 . Let R be the relation on the set of ordered pairs of positive integers such that ((a,b),(c,d)) ∈ R if and only if a+d = b + c. Show that R is an equivalence relation. (15 scores)6. Use adjacency matrix to find the numbers paths between U 1 and U 5 in the graph in Figure1 of length 3, determine whether it is planar and if it is planar ,into how many regions does this graph split the plane? (10 scores)7. Suppose there are 7 finals to be scheduled so that no student has two exams at the same time. Suppose the courses are numbered 1 through 7. Suppose that the following pairs of courses have common students : 1 and 2, 1 and 3, 1 and 4, 1 and 5, 2 and 3, 3 and 4 ,4 and 5.Please schedule the final exams for this. (10 scores)8 . Use Prim ’s algorithm to find a minimum spannig tree in the followinggraph,then use Kruskal ‘s algorithm to find a minimum spannig tree in the same graph. (10 scores)9. Suppose T is an ordered rooted tree.And the inorder listing of T is h,d,b,i,e,j,a,f,c,k,gThe preorder listing of T is a,b,d,h,e,I,j,c,f,g,kPlease draw T and find the postorder listing of T. (15 scores)。

离散数学期末试题及答案HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】326《离散数学》期末考试题(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 是欧拉图. 二．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 的面数为( ).三．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阶根树有( )棵.四、(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，求能组成四位数的个数.《离散数学》期末考试题(B)参考答案一、1. {{a , b }, a , b , ?}， {{a , b }, a , b }，16.2.92, 27.3.)()(x Q x P →, )()(y P y Q ⌝∧.4. 2, 4, 6, 12.5.4≤，奇数.二、1.22,2,m mn mn ., g , g . ,2,4.，不存在，不存在. 5.连通，3，10.三、1. }}{},,{},,{},{{c c b b a a B A =⋃，}}{{c B A =⋂，{)(=A P ?, {{a , b }}, {{c }}, {{a , b }, {c }}}.2.27933,3,3. 3.0)(↓∨q p .4.{-1，-2，-3，-6，1，2，3，6}. .四、证 对于任意A y x ∈,，若)()(y f x f =，则))(())((y f g x f g =，即))(())((y g f x g f =. 由于g f 是单射，因此y x =，于是f 是单射.例如取},,{},3,2,1(},,{γβα===C B b a A ，令)}2,(),1,{(b a f =，)},3(),,2(),,1{(ββα=g ，这时)},(),,{(βαb a g f = 是单射，而g 不是单射.五、解 1. R 的关系图R G 如下：2.(1)由于R b b ∉),(，所以R 不是自反的. (2)由于R a a ∈),(，所以R 不是反自反的.(3)因为R b d ∈),(，而R d b ∉),(，因此R 不是对称的. (4)因R a c c a ∈),(),,(，于是R 不是反对称的.(5)经计算知R c d a d c c b c a c c a b a a a R R ⊆=)},(),,(),,(),,(),,(),,(),,(),,{( ，进而R 是传递的.综上所述，所给R 是传递的.3.R 的关系矩阵⎪⎪⎪⎪⎪⎭⎫⎝⎛=0111011100000111R M .六、解 命题公式))(())((p q r r q p A →→↔→→=的真值表如下:由表可知，))(())((p q r r q p A →→↔→→=的主析取范式为A 的主合取范式为)()(r q p r q p A ⌝∨⌝∨∧∨⌝∨⌝=.七、证 不妨设G 的阶数3≥n ，否则结论是显然的. 根据推论1知，63-≤n m . 若G 的任意节点v 的度数均有5)deg(≥v ，由握手定理知n v m v5)deg(2≥=∑.于是m n 52≤，进而652363-⋅≤-≤m n m . 因此30≥m ，与已知矛盾. 所以必存在节点v 使得4)deg(≤v .八、解 设满足要求的r 位数的个数有a r 种，r = 0，1，2，…，则排列计数生成函数65432121211219619431x x x x x x ++++++=,因而38!412194=⋅=a .。

离散数学期末考试题及答案一、单项选择题（每题2分，共20分）1. 集合A={1,2,3}，集合B={2,3,4}，则A∩B等于多少？A. {1,2}B. {2,3}C. {3,4}D. {1,4}答案：B2. 命题“若x>0，则x^2>0”的逆否命题是？A. 若x^2≤0，则x≤0B. 若x^2>0，则x>0C. 若x≤0，则x^2≤0D. 若x≤0，则x^2>0答案：C3. 在图论中，一个图是连通的当且仅当？A. 存在一个顶点到所有其他顶点的路径B. 存在一个顶点到所有其他顶点的回路C. 图中没有孤立的顶点D. 图中至少有两个顶点答案：A4. 以下哪个选项是二元关系的自反性质？A. 对于所有元素x，(x, x)∉RB. 对于所有元素x，(x, x)∈RC. 对于所有元素x，y，(x, y)∈R且(y, x)∈RD. 对于所有元素x，y，z，(x, y)∈R且(y, z)∈R则(x, z)∈R5. 以下哪个命题是真命题？A. 所有的马都是白色的B. 有些马是白色的C. 没有马是白色的D. 所有的马都不是白色的答案：B6. 以下哪个选项是等价命题？A. p∧q和p∨qB. p∧q和¬p∨¬qC. p∧¬q和¬p∨qD. p∧q和¬p∧¬q答案：D7. 在集合论中，以下哪个操作是幂集？A. 并集B. 交集C. 对称差D. 包含所有子集的集合答案：D8. 以下哪个选项是图的路径？A. 一条边B. 一个顶点C. 一系列顶点和边，使得每对连续的顶点由一条边连接D. 一个环答案：C9. 以下哪个选项是命题逻辑中的合取？B. p∧qC. ¬pD. p→q答案：B10. 以下哪个选项是图的连通分量？A. 一个顶点B. 一条边C. 图的一个极大连通子图D. 图的一个极大不连通子图答案：C二、填空题（每题2分，共20分）1. 集合{1,2,3}的子集个数为__7__。

离散期末考试题及答案离散数学期末考试题及答案一、选择题（每题2分，共20分）1. 在集合论中，以下哪个符号表示属于关系？A. ∈B. ∉C. ⊆D. ⊂答案：A2. 有限集合A和B的并集，其元素个数最多是A和B元素个数之和，这个性质称为：A. 德摩根定律B. 幂集C. 并集原理D. 子集原理答案：C3. 命题逻辑中，以下哪个命题是真命题？A. (p ∧ ¬p) ∨ qB. (p ∨ ¬p) ∧ qC. (p ∨ q) ∧ ¬pD. (p ∧ q) ∨ ¬p答案：B4. 在图论中，一个无向图的边数至少是顶点数的多少倍才能保证图中至少存在一个环？A. 1B. 2C. 3D. 4答案：B5. 以下哪个算法用于生成一个集合的所有子集？A. 欧拉回路B. 哈密顿回路C. 深度优先搜索D. 子集生成算法答案：D6. 在关系数据库中，以下哪个操作用于删除表中的行？A. SELECTB. INSERTC. UPDATED. DELETE答案：D7. 以下哪个是有限自动机的状态？A. 初始状态B. 终止状态C. 转移状态D. 所有选项答案：D8. 以下哪个是图论中的一个基本定理？A. 欧拉定理B. 哈密顿定理C. 狄拉克定理D. 所有选项答案：D9. 在命题逻辑中，以下哪个是德摩根定律的逆命题？A. ¬(p ∨ q) ≡ ¬p ∧ ¬qB. ¬(p ∧ q) ≡ ¬p ∨ ¬qC. ¬(p ∨ q) ≡ ¬p ∨ ¬qD. ¬(p ∧ q) ≡ ¬p ∧ ¬q答案：B10. 在集合论中，以下哪个操作表示集合的差集？A. ∩B. ∪C. -D. ×答案：C二、填空题（每空3分，共30分）11. 集合{1, 2, 3}的幂集包含________个元素。

离散数学期末考试试卷一、选择题（每题3分，共30分）1. 集合A={1,2,3}，B={2,3,4}，则A∩B等于：A. {1,2}B. {2,3}C. {3,4}D. {1,4}2. 命题“若x>0，则x^2>0”的逆否命题是：A. 若x^2≤0，则x≤0B. 若x^2>0，则x>0C. 若x≤0，则x^2≤0D. 若x^2≤0，则x<03. 函数f: X→Y是单射的，当且仅当：A. 对于任意x1≠x2∈X，有f(x1)=f(x2)B. 对于任意x1≠x2∈X，有f(x1)≠f(x2)C. 对于任意x1≠x2∈X，有f(x1)=f(x2)或f(x1)≠f(x2)D. 对于任意x1≠x2∈X，有f(x1)≠f(x2)或f(x1)=f(x2)4. 以下哪个图是连通图？A. 一个孤立点B. 两个不相连的点C. 一条线段D. 两个不相连的三角形5. 有限集合A的基数为n，集合A的幂集的基数为：A. nB. 2nC. n^2D. 2^n6. 以下哪个是二元关系R在集合A上的自反性质？A. 对于所有a∈A，(a,a)∉RB. 对于所有a∈A，(a,a)∈RC. 对于所有a∈A，(a,a)=RD. 对于所有a∈A，(a,a)⊆R7. 以下哪个命题是正确的？A. 所有命题都是真命题B. 所有命题都是假命题C. 存在真命题也存在假命题D. 以上都不对8. 以下哪个是图的生成树？A. 包含图中所有顶点的最小连通子图B. 包含图中所有边的最小连通子图C. 包含图中所有顶点的最小生成树D. 包含图中所有边的最小生成树9. 以下哪个是布尔代数的基本运算？A. 交集B. 并集C. 补集D. 以上都是10. 以下哪个是图的哈密顿路径？A. 经过图中所有顶点的路径B. 经过图中所有边的路径C. 经过图中所有顶点恰好一次的路径D. 经过图中所有边恰好一次的路径二、填空题（每题4分，共20分）1. 集合{1,2,3}的子集个数为______。

大学离散数学期末考试题库和答案一、单项选择题（每题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=______。

冑散数学试题(B卷篆亲U一、证明题(10分)1)(「P/\ J Q/\R) ) V (Q/\R) V (PAR)oRiW：左端n(-P/\-QAR) V((QVP) AR)<^>((_PA-fi)AR))V( (QVP) AR)o(-1(PVQ)AR)V((QVP)AR)o(-WQ)V(QVP))ARoJGVQ)\/(P\/Q))ARoTAR(l^)62)3x (A(X)T B(X))O V X A(X)^3X B(X):3X(A(X)T B(X))U3X(-A(X) VB(x))<^x-A(x) V2xB(x)<^=>-iVxA(x) \/3}£(x)oVxA (x)—>3xB (x)二、求命题公式(PV(QAR))^(PAQAR)的主析取范式和主合取范式(10分)。

证明：(PV(QAR))^(PAQAR)<»-(PV(QAR))V(PAQAR))O (^PA(-nQV^R)) V(PAQAR)o JP/\「Q)v (-PA^R)) V (PAQAR)o(「P/\「QAR)v (-nPA-QA^R) V (-nP AQ A-R)) V (-.PA-nQ A^R)) V (PAQAR)<=>moVmi VmzVmT^M O VM^VM B VM G三、推理证明题(10分)1) CVD, (CVD)T「E, 「E T(A/\「B), (AA-nB)-^(RVS)=>RVS证明：(1) (CVD)T「E P(2)「E T(A/UB) P(3) (CVD)^(AA-nB) T(l)(2), I(4) (AA^B)^(RVS) p(5) (CVD)T(RVS) T⑶⑷，I(6) CVD p(7) RVS T(5), I2) Vx(P(x)TQ(y) AR(x)), 3xP (x) =>Q (y) A 3x (P (x) A R (x))证明(l)3xP(x) P(2)P(a)(3)Vx(P(x)TQ(y)AR(x))(4)P(a)^Q(y) AR(a)(5)Q(y) AR(a)(6)Q(y)(7)R(a)(8)P(a) AR(a)(9)3x(P(x)AR(x))(10)Q(y) A3x(P(x) AR(x)) T ⑴,ESPT(3), UST⑵⑷，IT(5), IT(5), IT(2) (7), IT(8), EGT(6) (9), I四、某班有25需学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5 人会打篮球和网球，还有2人会打这三种球。

106级离散数学期末试题B 答案一、计算题（共20分，每小题5分）1、 设A={}b a ,，B={}2,1,0，求笛卡尔乘积A ×B 和A 的幂集P(A)。

解 A ×B={<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2.>} P(A)={Φ,{a},{b},{a.b}} 2、 设A={1,2,3,4},A 上的关系R={‹1,1›,‹1,2›,‹2,4›,‹3,1›,‹4,3›},求domR 、ranR 、R –1。

解 domR={1,2,3,4}, ranR={1,2,3,4}, R –1 ={‹1,1›,‹2,1›,‹4,2›,‹1,3›,‹3,4›}3、 画出集合{2, 3, 4, 8, 9, 10, 11}上整除关系的哈斯图，并求它的最大元、最小元、极大元、极小元。

解 它的最大元、最小元都不存在；极大元为8, 9, 10, 11；极小元为2, 3, 11。

4、 设f ：N N N →⨯（N 为自然数集合），22),(y x y x f +=><，说明f 是否为单射、满射的？计算})0({1-f 。

解 })0({1-f ={<0,0>} 不是单射 ,是满射的二、判断题（共10分，每小题5分）1、设A={}8,5,4,3,2,1，R 是A 上的“模3同余”关系。

问R 是否为A 上的等价关系？若是，给出其等价类，并画出R 的关系图。

解 R 是A 上的等价关系，等价类为 [1]=[4]={1,4} [2]=[5]=[8]={2,5,8} [3]={3}R 的关系图如下：2、下列语句中哪些是命题？是命题的句子中哪些是复合命题？并将复合命题符号化。

（1）小张与小刘住一个寝室。

（2）只要天气好，飞机就能正常降落。

（3）请上楼！解 （1）是命题，不是复合命题； （2）是复合命题；设P ：天气好,q ：飞机能正常降落，p →q ；（3）不是命题；三、（共10分，每小题5分）1、某电路中有1个灯泡和3个开关A 、B 、C 。

离散数学期末考试题及答案一、选择题（每题2分，共20分）1. 在集合论中，表示两个集合A和B的并集的符号是：A. ∩B. ∪C. ⊂D. ⊆2. 以下哪个命题逻辑表达式是真命题，当P为真，Q为假时？A. ¬PB. P ∧ QC. P ∨ QD. P → Q3. 如果函数f: A → B是一个单射，那么它不能是：A. 满射B. 双射C. 恒等函数D. 逆函数4. 在图论中，一个图G是连通的，当且仅当：A. G是无向图B. G是简单图C. G是完全图D. 对于任意两个顶点，都存在一条路径5. 以下哪个不是组合数学中的计数原理？A. 加法原理B. 乘法原理C. 排列D. 组合二、简答题（每题10分，共30分）6. 解释什么是二元关系，并给出一个例子。

7. 描述什么是有向图和无向图的区别。

8. 什么是等价关系，它有哪些性质？三、计算题（每题15分，共30分）9. 给定集合A = {1, 2, 3, 4}，B = {a, b, c}，定义函数f: A → B，其中f(1) = a, f(2) = b, f(3) = c, f(4) = a。

判断f是否是单射、满射或双射，并给出理由。

10. 计算以下命题逻辑表达式的真值表：(P ∧ Q) → (¬P ∨ R)，其中P、Q、R是命题变量。

四、证明题（每题20分，共20分）11. 证明：如果一个图G是连通的，那么它的任意子图也是连通的。

答案一、选择题1. B2. C3. A4. D5. D二、简答题6. 二元关系是定义在两个集合上的一个关系，它将第一个集合中的每个元素与第二个集合中的元素相关联。

例如，如果A是人名的集合，B是年龄的集合，关系R可以是“比...年长”，那么(Alice, 30) ∈ R表示Alice比30岁年长。

7. 有向图由顶点和有向边组成，每条边都有一个方向，表示从一个顶点指向另一个顶点。

无向图由顶点和无向边组成，边没有方向。