下载文档原格式
离散数学期末试题（A）（满分100分）一、单项选择题（共40分，每题4分）1、设集合A=｛3｛4｝5 6｝选择下列所给答案正确的是（）A、｛5｝∈AB、｛｛4｝，5，6｝≤AC、｛3 4 5 6｝≤AD、Φ≤｛3｛4｝｝2、由集合运算定义，下列各式正确的是（）A、X ≥X U YB、X ≤X n YC、X ≤X U YD、Y ≤X n Y3、设R、R1、R2是集合A、B上的二元关系，则下列表达式正确的是（）A、若R1≤R2则R-11≤R-12B、（R1V R2）-1 = R-11n R-12C、（～R）-1 = R-1D、（R1- R2）-1 = R-11+R-124、设集合｛1 2 3 4 ｝，A上的关系R=｛（1 1）（2 3）（2 4）（3 4）｝则R具有（）A、自反性B、传递性C、对称性D、以上答案都不对5、设命题公式G = （P Q）H = P （Q P）则G与H的关系是（）A、G =﹥HB、H =﹥GC、G = HD、以上都不是6、设G、H是一阶逻辑式P是一个谓词G = xp（x）H = xp（x）则一阶逻辑公式G H是（）A、恒真的B、恒假的C、可满足的D、前束范式7、下面代数系统中（G、＊）中（）不是群A、G为整数集合＊为加法B、G为偶数集合＊为加法C、G为有理数集合＊为加法D、G为有理数集合＊为乘法8、设б1、б2、б3是三个置换，其中б1=（1 2）（2 3）（1 3）б2 =（2 4）（1 4）б3= （1 3 2 4）则б3=（）A、б12B、б1б2C、б22D、б2б19、下列半序集中哪个不是格（）A B C D10、G是连通平面图，有5个顶点、6个面，则G的边数为（）A、6B、5C、11D、9二、填空题（共20分，每空4分）1、无孤立点的有限有向图有欧拉路的充要条件是。
2、设CB，·，+，－，0，1﹥是布尔代数，a，b，c是集合B中任意元素，则（a，b）+（a，b，c）+ （a , b , c）+ （a , b , c）= 。
离散数学期末考试试题及答案离散数学期末考试试题及答案离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。
下面是小编整理的离散数学期末考试试题及答案，欢迎阅读参考！一、【单项选择题】(本大题共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的割(点)集是( )。
第 1 页 共 4 页4. 在如下各图中（ ）欧拉图。
5. Z 为整数集合，*是Z 上定义的二元运算，2*,,-+=∈∀y x y x Z y x ，则Z 关于*运算构成（ ）。
A. 代数系统，但不是半群B. 半群，但不是独异点C. 是独异点，但不是群D. 群 二、填空题（每空1分，共13分）1. 若P 表示“小李学习努力”，Q 表示“小李取得好成绩”，则“只要小李努力学习，他就能取得好成绩”以及“虽然小李努力学习，可他没能取得好成绩”的命题逻辑符号化表示分别为（ ）和（ ）。
2. 设A={1,2,3,5},B={2,4},则A-B=( )。
3. 设集合A={1,2}，则A 的幂集为（ ）。
4. 集合A={a,b,c}，A 上的二元关系R={<a,b>,<a,c>,<c,c>}。
则R 的自反闭包为（ ），R 的对称闭包为（ ）， R 2=（ ）。
5. 无向图G 是欧拉图当且仅当G 连通且（ ）。
6. 若无向树T 有8个结点，则T 有（ ）条边。
7. n 阶无向完全图Kn 的边数为（ ）。
第 2 页 共 4 页8. 如果连通平面图G 有n 个顶点，m 条边，则G 有（ ）个面。
9. 设在有理数集合Q 上定义二元运算*，∀x,y ∈Q 有x*y=x+y-xy ，则2*(-5)=（ ），关于*运算的单位元是（ ）。
三、计算题（共27分）1. 求命题公式)()()(R P R Q Q P ∨⌝∧∨∧∨的主合取范式和主析取范式。
（8分）2. 设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}，请画出R 的关系图，并用warshall 算法求R 的传递闭包t(R)。
（7分）3. （G ，*）是群，a ，b 是集合G 中的元素，求满足a*x=b 的x 的值及满足y*a=b 的y 的值。
诚信应考 考出水平 考出风格浙江大学城市学院2011 — 2012 学年第 二 学期期末考试试卷《 离散数学 》开课单位： 计算分院 ；考试形式：闭卷；考试时间：_2012_年_6_月_12_日； 所需时间： 120 分钟一．选择题 (本大题共10题，每题2分，共20分。
选择题答案请填到下面表格的相应栏中)1．下列式子中是永真式的为（ ）。
A ．)B A (A ∧∨ B ．)B A ()B A (∧⌝∨∧C ．))B B (A (A ⌝∧∨⌝∨D ．B A ⇔ 2．命题公式Q Q →→∧))P (P (是（ ）。
A ．矛盾式B ．蕴含式C ．重言式D ．等价式3．设R(x)：x 是实数；Q(x)：x 是有理数。
命题“所有有理数是实数”可以符号化为（ ）。
A ．))(R )(Q )((x x x ∧∀ B ．))(R )(Q )((x x x →∀ C ．))(R )(Q )((x x x ∧∃D ．))(R )(Q )((x x x →∃ 4．设A={1，2，3}，则A 上的二元关系有（ ）个。
A ． 23 ； B ． 32 ； C ． 332⨯； D ． 223⨯。
5．设A={1，2，3}，如右图所示关系图表示的二元关系具有 ( ) 。
A ． 自反性 B ． 对称性 C ． 传递性 D ． 反对称性 6．设A={Φ，{1}，{1，3}，{1，2，3}}则A 上包含关系“⊆”的哈斯图为（ ）7．对于集合A={x ∣-10<x<10}，下列哪种运算是封闭的（ ）。
A ．+；B ．—；C ．∣x-y ∣；D ．∣x ∣。
8．设R 是实数集合，“⨯”为普通乘法，则代数系统<R ，×> 不是（ ）。
A ．群； B ．独异点； C ．半群 ； D ．广群。
9．设E V G ，=为无向图，5V =，13E =，则G 一定是（ ）。
A ．完全图； B ．补图； C ．简单图； D ．多重图。
--北京工商大学离散数学试卷(A)答案及评分标准题号 一 二三 四 五 六 七总分得分一、（30分）设A ={1,2,3,4}，给定A 上二元关系R 如下：R ={<1,1>, <1,2>, <2,3>, <3,3>, <4,4>}请回答以下各问题：1.写出R 的关系矩阵. （3分）2.画出R 的关系图. （3分）3.求包含R 的最小的等价关系，并写出由其确定的划分. （6分）4.分别用关系矩阵表示出R 的自反闭包r (R )、对称闭包s (R ). （6分）5.求传递闭包t (R ).（写出计算步骤）（6分）6.求R 2的关系矩阵. （3分）7.集合A 上最多可以确定多少个不同的二元关系？说明理由。
（3分）[解] (1)⎪⎪⎪⎪⎪⎭⎫⎝⎛=1000010001000011R M 。
……（3分）（2） ……（3分）(3)法一：直接由等价关系与划分之间的一一对应可知，包含R 的最小等价关系为: {<1, 2>, <1, 3>, <2, 1>,<2, 3>, <3, 1> <3, 2>}∪I A , ……（3分） 对应的划分为{{1, 2, 3},{4}}. ……（6分） 法二：包含R 的最小的等价关系就是tsr (R ), 计算过程如下：⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫⎝⎛=+=100001000110001110000100001000011000010001000011)(E M M R R r,100001100111001110000110001100011000010001100011][)()()(⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=+=T R r R r R sr M M M ,3,10001110111011110000110011100111000011001110011)]([)()()]([2≥=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛⨯⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⨯=k M M M M k R sr R sr R sr R sr 从而,10000111011101111000011101110111100001110111011110000111011101111000011001110011432)]([)]([)]([)()(⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=+++=R sr R sr R sr R sr R tsr M M M M M即}2,3,1,3,3,2,1,2,3,1,2,1{)(><><><><><><⋃=A I R tsr =包含R 的最小的等价关系， ……（3分） 故其对应的划分为{{1, 2, 3},{4}}. ……（6分） 法三：由于4=A ，包含R 的最小的等价关系就是4131211)()()()()()(----⋃⋃⋃⋃⋃⋃⋃⋃==R R R R R R R R I R rts R tsr A ,计算过程如下：⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛+⎪⎪⎪⎪⎪⎭⎫⎝⎛=+=-⋃100001100101001110000110000100011000010001000011][1TR R R R M M M ⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛=+=-⋃10000111011101111000011001010011)][(22)(21T R R R R M M M412131)()(33)(10000111011101111000011001010011)][(---⋃⋃⋃==⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛=+=R R R R T R R R R M M M M M 考试纪律承诺本人自愿遵守学校考试纪律，保证以诚信认真的态度作答试卷。
2011-2012 2 离散数学（A 卷） 高密校区2011级计专、软专（答案写在答题纸上，写在试题纸上无效）一、单项选择题（每小题2分，共20分）1．下列为两个命题变元ｐ，ｑ的最小项的是（ ）A ．ｐ∧ｑ∧⎤ ｐB ．⎤ ｐ∨ｑC ．⎤ ｐ∧ｑD ．⎤ ｐ∨ｐ∨ｑ2．下列语句中是真命题的是（ ）A ．我正在说谎B ．严禁吸烟C ．如果1+2=3，那么雪是黑的D ．如果1+2=5，那么雪是黑的3．在公式x ∀F （x ，y ）→∃ y G （x ，y ）中变元x 是（ ）A ．自由变元B ．约束变元C ．既是自由变元，又是约束变元D ．既不是自由变元，又不是约束变元4．集合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 ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001110101 B ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡101100001C ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001100100 D ．⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001010101课程考试试题学期 学年 拟题学院（系）: 适 用 专 业:7. 在自然数集N 上，下列运算是可结合的是（ ）A b a b a 2*-=B ．},min{*b a b a =C b a b a --=*D b a b a -=*8．.设A 是奇数集合，下列构成独异点的是( )A.<A ，+>B.<A ，->C.<A ，×>D.<A ，÷>9. 右图的最大入度是( )A ．0B ．1C ．2D ．3第9题图10. 设G 为有n 个结点的简单图，则有（ ）A ．Δ(G)＜nB ．Δ(G)≤nC ．Δ(G)＞nD ．Δ(G)≥n二、填空题(每空2分，共20分)1．设A ={1，2，3，4}，B ={2，4，6}，则A -B =________，A ⊕B =________。
诚信应考 考出水平 考出风格 浙江大学城市学院 2011 — 2012 学年第 一 学期期末考试试卷 《 离散数学 》 开课单位： 计算分院 ；考试形式：闭卷；考试时间：_2012_年_1_月_7_日； 所需时间： 120 分钟 题序 一 二 三 四 总 分 得分 评卷人 一．选择题 (本大题共10题，每题2分，共20分。
选择题答案请填到下面表格的相应栏中) 题号 1 2 3 4 5 6 7 8 9 10 答案 1．设P ：我将去镇上；Q ：我有时间。
命题“我将去镇上，仅当我有时间”可符号化为（ ）。
A ．Q P → B ．P Q → C ．Q P ↔ D ．P Q ⌝∨⌝ 2．下列语句中是真命题的为（ ）。
A ．我正在说谎。
B ．如果1+2=3，那么雪是黑的。
C ．如果1+2=5，那么雪是黑的。
D ．严禁吸烟。
3．命题公式Q Q →→∧))P (P (是（ ）。
A ．矛盾式 B ．蕴含式 C ．重言式 D ．等价式 4．设C(x):x 是模特；G(x):x 是美丽的。
命题“没有一个模特不是美丽的”可以符号化为（ ）。
A ．))()()((x G x C x ⌝∧∀⌝ B ．))()()((x G x C x ⌝→∀⌝ C ．))()()((x G x C x ⌝∧∃⌝ D ．))()()((x G x C x ⌝→∃⌝得分 年级：_____________专业：_____________________班级：_________________学号：_______________姓名：__________________ …………………………………………………………..装………………….订…………………..线………………………………………………………5．设A={1，2，3}，则A 上的二元关系有 ( ) 个。
A ． 23B ． 32C ． 332⨯D ． 223⨯6．设12,R R 是非空集合A 上的等价关系，下面哪个是等价关系。
电子科技大学2011 -2012学年第 2学期期 末 考试 A 卷课程名称： 离散数学 考试形式： 闭卷 考试日期： 2012 年 6 月 日 考试时长：120分钟 课程成绩构成：平时 10 %， 期中 20 %， 实验 0 %， 期末 70 % 本试卷试题由____ _部分构成，共_____页。
I.Multiple Choice (15%)1. (⌝p ∧q)→(p ∨q) is logically equivalent toa) T b) p ∨q c) F d) ⌝ p ∧q （ ） 2. If P(A) is the power set of A, and A = , what is |P(P(P(A)))|?a) 4 b) 24 c) 28 d) 216（ ） 3. Which of these statements is NOT a proposition?a) Tomorrow will be Friday. b) 2+3=4.c) There is a dog. d) Go and play with me.（ ）4. The notation K n denotes the complete graph on n vertices. K n is the simple graph thatcontains exactly one edge between each pair of distinct vertices. How many edges comprise a K 20?a) 190 b) 40 c) 95 d) 380（ ）5. Suppose | A | = 5 and | B | = 9. The number of 1-1 functions f : A → B isa) 45 b) P (9,5). c) 59 d) 95（ ）6. Let R be a relation on the positive integers where xRy if x divides y . Whichof the following lists of properties best describes the relation R ?a) reflexive, symmetric, transitive b) reflexive, antisymmetric, transitive c) reflexive, symmetric, antisymmetric d) symmetric, transitive （ ）7. Which of the following are partitions of }8,7,6,5,4,3,2,1{=U ?a) }8,7,6,5,4,3{},3,2,1{},1{ b) }8,7,6,5,4,3{},3,2{},1{c) }8,6,5{},3,2{},7,4,1{ d) }8,7,6,5,4{},3,2{},2,1{（ ） 8. The function f(x)=3x 2log(x 3+21) is big-O of which of the following functions? a) x 3 b) x 2(logx)3 c) x 2logx d) xlogx （ ） 9.In the graph that follows, give an explanation for why there is no path from a back to a that passes through each edge exactly once.a) There are vertices of odd degree, namely {B,D}. b) There are vertices of even degree, namely {A,C}. c) There are vertices of even degree, namely {B,D}. d) There are vertices of odd degree, namely {A,C}.（ ） 10. Which of the followings is a function from Z to R ?a) )1()(-±=n n f . ` b) 1)(2+=x x f . c) x x f =)( d) 11)(2-=n n fII. True or False (10%)（ ） 1. If 3 < 2, then 7 = 6. （ ） 2. p ∧ (q ∨ r)≡ (p ∧ q) ∨ r（ ） 3. If A , B , and C are sets, then (A -C )-(B -C )=A -B . （ ） 4. Suppose A = {a ,b ,c }, then {{a }} ⊆ P (A ).（ ） 5. ()100h x x =+is defined as a function with domain R and codomain R.（ ） 6. Suppose g : A → B and f : B → C , where f g is 1-1 and f is 1-1. g must be 1-1? （ ） 7. If p and q are primes (> 2), then p + q is composite .（ ） 8.If the relation R is defined on the set Z where aRb means that ab > 0, then R is an equivalence relation on Z .（ ） 9. Every Hamilton circuit for W n has length n .（ ） 10. There exists a simple graph with 8 vertices, whose degrees are 0, 1, 2, 3, 4, 5, 6, 7.III. Fill in the Blanks (20%)1. Let p and q be the propositions “I am a criminal” and “I rob banks”. Express in simple English the propositi on “if p then q”: .2. P (x ,y ) means “x + 2y = xy ”, where x and y are integers. The truth value of ∃x ∀yP (x ,y ) is .3. T he negation of the statement “No tests are easy.” is .4. If 11{|}i A x x R x i i =∈∧-≤≤ then 1i i A +∞=is .5. Suppose A = {x , y }. Then ()P A is .6. Suppose g : A →A and f :A →A where A ={1,2,3,4},g = {(1, 4), (2,1), (3,1), (4,2)} andf ={(1,3),(2,2),(3,4),(4,2)}.Then fg = . 7.The sum of 2 + 4 + 8 + 16 + 32 + ... + 210 is .8. The expression of gcd(45, 12) as a linear combination of 12 and 45 is .9.There are permutations of the seven letters A,B ,C ,D ,E ,F have A immediately to the left of E .10. If G is a planar connected graph with 18 vertices, each of degree 3, then G has _ __regions. IV. Answer the Questions (32%)：1. Determine whether the following argument is valid: p → r q → r q ∨ ⌝r ________∴ ⌝p2. S uppose you wish to prove a theorem of the form “if p then q ”. (a) If you give a direct proof, what do you assume and what do you prove? (b) If you give an indirect proof, what do you assume and what do you prove? (c) If you give a proof by contradiction, what do you assume and what do you prove?3. Prove that A B A B ⋂=⋃ by giving a proof using logical equivalence.4.Suppose f:R→R where f(x) =⎣x/2⎦.(a) If S={x| 1 ≤x≤ 6}, find f(S).(b) If T={3,4,5}, find f-1(T).e the definition of big-oh to prove that5264473n nn+--is O(n3).6.Solve the linear congruence 5x≡ 3 (mod 11).e the Principle of Mathematical Induction to prove that131 1392732nn+-++++...+=for alln≥ 0.8.Draw the directed graph for the relation defined by the matrix1111 0111 0011 0001⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦.V. (6%) Without using the truth table, show that the following are tautologiesa) [⌝p ∧(p ∨q)]→q b) [p ∧(p →q)]→qVI. (6%) Devise an algorithm which will find the minimum of n integers. What is the worst casetime complexity of this algorithm?VII. (5%) Give the definition of a transitive relation, and Prove or disprove that the union oftwo transitive relations is transitive.VIII.(6%) The pseudo-code of Prim’s algorithm is given as following:Procedure Prim(G: connected weighted undirected graph with n vertices)T := a minimum-weight edgefor i := 1 to n 2begine := an edge of minimum weight incident to a vertex in T and notforming a simple circuit in T if added to TT := T with e addedPrint eend {T is a minimum spanning tree of G}(a)Find a minimum spanning tree using Prim’s algorithm given above. For every iterative in for-loop, list theresult for “Print e” statement.(b)Compute the total weight of the spanning tree.。
