《离散数学》2015期末试题及答案

离散数学期末试题及答案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 .。

最新国家开放大学电大《离散数学》期末题库及答案《离散数学》题库及答案一一、单项选择题（每小题3分，本题共15分）1.若集合A = （l,2,3,4）,则下列表述不正确的是（）•A.16AB. {1,2,3}CAC. （1.2.3J6AD. 0UA2.若R和R?是A上的对称关系，则中对称关系有（〉个・A. 1B. 2C. 3D. 43.设G为连通无向图，则］）时,G中存在欧拉回路・A. G不存在奇数度数的结点B. G存在偶数度数的结点C. G存在一个奇数度数的结点D. G存在两个奇数度数的结点4.无向图G是棵树，边数是10,则G的结点度数之和是（）.A.20B. 9C. 10D. 115.设个体域为整数集，则公式V z3y（x+y = 0）的解释可为（）.A-存在一整数z有整数丁满足x+y = 0B.对任意整数z存在整数財满足x+y = 0C.存在一整数z对任意整数'满足工+y・0D.任意整数工对任意整数，满足x+y=0得分评卷人--------------- 二、填空題（毎小通3分，本題共15分）6.设集合A = {1.2,3),B = (2,3,4}.C=(3.4.5，则A (J (C - B )等于7-设 A = （2,3},B-{l,2}.C-{3,4}.从 A 到 B 的函ft/-{<2,2>,<3,1>}.从 B 到C 的函数R = <V1.3>,V2.4>）,则Dom（g"）等于.8.已知图G中共有】个2度结点,2个3度结点,3个4度结点，则G的边数是・9.设G是连通平面分别衰示G的結点数.边数和面数，u值为5/值为4,则r的值为・-10-设个体域D = （1.2.3,4hA（x）为七大于5”，则调词公式（Vz）AGr）的真值为11. 将语句“学生的主要任务是学习”翻译成命题公式. 12.将语句“今天天暗，昨天下雨.”翻译成命题公式.四、判斷说明題（判断各题正误，并说明理由.每小题7分，本题共1413. 空集的圳:集是空集. 14.完全图K,不是平面图.15.设集合A = <1,2,3,4｝上的关系：R-«1.2>.<2.3>.<3,4>}.S = (<1.1>,<2,2>,<3,3>), 试计算(DR • S t (2)7? (3)r(J?nS).16.图 G=<V,E>.其中 V=S ，6,c,d}.E=((a,6),S,c),(a,d),(5,c),0,d),(c,d)},对应边的权值依次为2、3、4、5、6及7,试（1）画出G 的图形, （2）写岀G 的邻接矩阵;（3）求出G 权最小的生成树及其权值. 17.求PTQPR ）的析取范式与主合取范式.18.试证明：r -1 (P-*Q) An R A(QfR)=>i P.试题答案及评分标准仅供參考一、单项选择题（毎小题3分,本题共15分）l.C2.D3. A4. A5. B2OZZ«r-2O23^ttM三、逻辑公式翻译（毎小題6分，本题共】2分）分）五、计鼻16（每小JS 12分，本贓共36分）六、证明85（本楚共8分）2022集・2U23年股*二、壊空題（每小题3分，本题共15分）6. {1,2,3,5)7. {2,3}(或 A)8.109.110. 假（或F,或0）三、逻辑公式B!译（毎小题6分，本題共12分）11.设P ：学生的主要任务是学习. 则命题公式为:P.12.设今天夭晴，Q ：昨天下雨. 则命题公式为:PAQ.四、判断说明題（每小題7分，本题共14分）13.借误.空集的專集不为空集，为{0}. 14. 错误.完全图K,是平面图， 如K,可以如下图示嵌入平面.五、计算题（每小题12分，本題共36分）15. 解：(!)/? • S = (V1,2>,V2,3>* (2)J?-* = «2,1>,<3,2>,<4,3>}» (3)r(RnS)={Vl,l>,V2,2>,V3,3>,V4,4>} 16. 解.（DG 的图形表示为:《7分）（2）邻接矩阵:（3分）（6分）（2分）（6分） （2分） （6分）（3分）（4分） （8分）2022 集-2U23 年股*(3)粗线与结点表示的是最小生成树,(10 分)权值为9 (12分)17.解:P-(QAR)PV(QAR) 析取范式(2分)PVQ)A(q PVR) (5 分)g PVQ〉V(RA")A("VR) (7 分)PVQ)V(R A-i R)A(i PVR)V(QAr Q) (9 分)«(n PVQVR) A("VQV")A(i P VRVQ)A("VRVr Q)⑴分)PVQVR) A(i PVQV-i R) A(n P Vn QVR) 主合取范式 (12 分)六、证明JH(本■共8分)18.证明：(1)n □ (P-*Q) P(1 分)(2)P-*Q T(1)E (3 分)(3)(Q々) P(4 分)(On R P(5 分)(5>-| Q T(3)(4)7 (6 分)(6)n P T(2)(5)r (8 分)说明：(1)因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得.出有效结论得1或2分，最后得岀靖论得2或1分.(2)另，可以用真值表验证.《陽散数学〉题库及答案二的关系R = {<=，3>M£A，3£B,且工+ » = 5}.则R=( ).A・(V1,2>,V1,3>,V2,3>} B. (VI,4>,V2,3>,V3,2>}C. (<1,1>,<2,2>,<3,2>}D. (<3.2>,<2,4>,<3,4»2.若集合A = {a,6,c,d},则下列表述正确的是( )•B. (a}£AD・("匕A2DZZ 邮-2023 邮3.设个体域为整数集期公式（七）（功）（工一，・2）的解释可为（）•A.存在一整数1有整数，満足工一》=2R存在一整散工对任意整數：，満足工一>・2G对任一整数工存在整数:y满足上一y=2D.任一整数］对任意幣数》满足x-y-24.”阶无向完全图K.的边數及每个结点的度数分别是（）・A. n（n —1）与mB. n（n —1）与C.n — 1 与nD. n（n —1）/2 与“一】5.设G为连通无向ffl.MC 〉时,G中存在欧拉回路•A.G不存在奇数度数的靖点B・G存在一个奇数度數的靖点C.G存在两个奇数度数的结点D.G存在偶数度数的结点得分|评卷人二、壊空順（毎小H 3分.本顕共15分）6.设集合A = {x|x是小于4的正整数）.用集合的列挙法A=・7.设 A = U,2）,B-{a.6}.C-{l,2）.从 A 到 B 的函»/= {<1 .a>.<2,6>）.从 B 到C的函数g-«a.2>,<6,l>）,则复合函数g./- ・8.设G = <V,E>是一个图，结点度数之和为30,MG的边数为・9.设G是具有r,个結点责条边4个面的连通平面图.JRn+4-2-・10.设个体域D-（2,3.4},A（x ）为—小于3■，则调词公式< Vx）A（x>的真值为得分评卷人三、遂梅公式翻译（毎小題6分，本■共12分）11-将语句•如果今天下頂•那么明天的比賽就要延期译成命，公式.12.将语句•地球是圆的，太阳也是圆的.”翻洋成命題公式.得分呼卷人----- 四、判断说明題（判斷各IH正讓•井说明理由.毎小願7分.本■共 14 分）13.设A = {a,6.c.</}.R-«a.6>,<6,a>,<a ,a>,<b,b> ,<（.€>}.则R是等价关系.2OZZ«r-2O23^ttM14.<Vz)(P(x)AQ(y»-R(x)中量伺V 的辖域为(PGr〉AQ(y)).得分评卷人-------------- 五、计算题(每小題12分，本題共36分)15.设集合A^{a,b,c}t B^{b t c,d}t试计算(DAUB; (2) A-Bi(3MXB.16.设G = VV,E>,V= {vi. v a. vj»v4).E =* ((vi»)» (vi»v s)» (t>i»v4). (v,,v>)»(V1 ,。

离散数学试题(B卷答案1〕一、证明题〔10分〕1)(P∧(Q∧R))∨(Q∧R)∨(P∧R)R证明:左端(P∧Q∧R)∨((Q∨P)∧R)((P∧Q)∧R))∨((Q∨P)∧R)((P∨Q)∧R)∨((Q∨P)∧R)((P∨Q)∨(Q∨P))∧R((P∨Q)∨(P∨Q))∧RT∧R(置换)R2)x(A(x)B(x))xA(x)xB(x)证明：x(A(x)B(x))x(A(x)∨B(x))xA(x)∨xB(x)xA(x)∨xB(x)xA(x)xB(x)二、求命题公式(P∨(Q∧R))(P∧Q∧R)的主析取X式和主合取X式〔10分〕。

证明：(P∨(Q∧R))(P∧Q∧R)(P∨(Q∧R))∨(P∧Q∧R))〔P∧(Q∨R)〕∨(P∧Q∧R)(P∧Q)∨(P∧R))∨(P∧Q∧R)(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R))∨(P∧Q∧R))∨(P∧Q∧R)m0∨m1∨m2∨m7M3∨M4∨M5∨M6三、推理证明题〔10分〕1〕C∨D，(C∨D)E，E(A∧B)，(A∧B)(R∨S)R∨S证明：(1)(C∨D)EP(2)E(A∧B)P(3)(C∨D)(A∧B)T(1)(2)，I(4)(A∧B)(R∨S)P(5)(C∨D)(R∨S)T(3)(4)，I(6)C∨DP(7)R∨ST(5)，I2)x(P(x)Q(y)∧R(x))，xP(x)Q(y)∧x(P(x)∧R(x))证明(1)xP(x)P(2)P(a)T(1)，ES(3)x(P(x)Q(y)∧R(x))P(4)P(a)Q(y)∧R(a)T(3)，US(5)Q(y)∧R(a)T(2)(4)，I(6)Q(y)T(5)，I(7)R(a)T(5)，I(8)P(a)∧R(a)T(2)(7)，I(9)x(P(x)∧R(x))T(8)，EG(10)Q(y)∧x(P(x)∧R(x))T(6)(9)，I四、某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5 人会打篮球和网球，还有2人会打这三种球。

离散数学期末考试题及答案1.选择题（每题3分，共30分）1. 下列命题中，属于复合命题的是：A. 3是一个奇数，且2是一个偶数B. 如果2是一个素数，那么4也是一个素数C. 不是所有奇数都是素数D. 存在一个整数x，使得x>5且x是一个偶数答案：D2. 已知命题p：草地是绿的，命题q：天空是蓝的。

下列表述可以表示p ∧ ¬q 的是：A. 草地是绿的，天空是蓝的B. 草地不是绿的，天空是蓝的C. 草地是绿的，天空不是蓝的D. 草地不是绿的，天空不是蓝的答案：B3. 设命题p表示“这个数是偶数”，q表示“这个数大于10”。

那么“这个数既是偶数又大于10”可以表示为：A. p ∧ qB. p ∨ qC. ¬p ∧ qD. ¬p ∨ q答案：A4. 下列以下列集合的方式描述，其中哪个是空集∅：A. {x | 0 ≤ x ≤ 1}B. {x | x是一个自然数，x > 10}C. {x | x是一个正偶数，x < 2}D. {x | x是一个负整数，x < -1}答案：C5. 设A = {a, b, c}，B = {c, d, e}，C = {a, c, e}。

则(A ∪ B) ∩ C等于：A. {a, b, c, d, e}B. {a, c, e}C. {c}D. 空集∅答案：B6. 假设U是全集，A、B、C是U的子集。

则(A ∪ B) ∩ C 的补集是：A. A ∩ B ∩ C的补集B. (A ∪ B) ∩ C的补集C. A ∪ (B ∩ C)的补集D. (A ∩ C) ∩ (B ∩ C)的补集答案：D7. 若关系R为集合A到集合B的一种映射，且|A| = 7，|B| = 4，则R包含的有序对数目为：A. 4B. 7C. 11D. 28答案：D8. 设A={1,2,3}，B={4,5,6}，则从A到B的映射总数为：A. 3B. 9C. 6D. 18答案：C9. 设A={a,b,c,d,e}，则集合A的幂集的元素个数是：A. 2B. 5C. 10D. 32答案：D10. 若f：A→B为满射且g：B→C为单射，则(g ∘ f)：A→C为：A. 双射B. 满射C. 单射D. 非单射且非满射答案：A2.简答题（每题10分，共20分）1. 请简要解释什么是关系R的自反性、对称性和传递性。