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

安徽大学《离散数学》期末考试试卷（B 卷）（时间120分钟）开课院（系、部） 姓名 学号 .一、选择题（每小题2分，共20分）1．设522:=⨯P ，:Q 雪是黑的，842:=⨯R ，:S 太阳从东方升起，下列命题中真值为T 的是（ ） A 、R Q P ∧→； B 、S P R ∧→；C 、R Q S ∧→；D 、)()(S Q R P ∧∨∧。

2．下列命题公式中，为重言式的是（ ）A 、)(R Q P ∨→；B 、)()(Q P R P →∧∨；C 、)()(R Q Q P ∨↔∨；D 、))()(())((R P Q P R Q P →→→→→→。

3．设x x L :)(是演员，x x J :)(是老师，x y x A :),(钦佩y ，命题“所有演员都钦佩某些老师”符号化为（ ）A 、)),()((y x A x L x →∀；B 、))),()(()((y x A y J y x L x ∧∃→∀；C 、)),()()((y x A y J x L y x ∧∧∃∀；D 、)),()()((y x A y J x L y x →∧∃∀。

4．设}{φ=A ， ))((A B ρρ=，以下各小题中不正确的有（ ）A 、B ∈}}{{φ； B 、B ∈}}}{{,{φφ ；C 、B ⊆}}}{{,{φφ；D 、B ⊆}}}{,{},{{φφφ。

5．设φ=A ， }}{,{φφ=B ，则A B -是（ ）。

A 、 }}{{φ； B 、}{φ ； C 、 }}{,{φφ； D 、 φ。

6．设},,{c b a A =，R ,S ,T 是集合)(A ρ上的二元关系。

其中，}|,{y x y x R ⊂><=，}|,{φ=><=y x y x S ，}|,{A y x y x T =><= 。

下列哪些命题为真？（ ） I.R 是反自反、反对称和传递的 II.S 是反自反和对称的 III.T 是反自反和对称的A 、仅I ；B 、仅II ；C 、I 和II ；D 、全真。

离散数学期末考试试题及答案一、选择题（每题3分，共30分）1. 设集合A={1, 2, 3, 4, 5}，B={2, 4, 6, 8}，则A∩B是（）A. {1, 2, 3, 4, 5}B. {2, 4}C. {1, 3, 5}D. {2, 4, 6, 8}2. 下列关系中，哪个是等价关系？（）A. 小于关系B. 大于等于关系C. 模2同余关系D. 整除关系3. 设P(x)是谓词逻辑公式，下列哪个命题与∀xP(x)等价？（）A. ∃x¬P(x)B. ¬∀xP(x)C. ¬∃xP(x)D. ∃x¬P(x)4. 一个图的欧拉回路是指（）A. 经过每一条边的路径B. 经过每一个顶点的路径C. 经过每一条边的环D. 经过每一个顶点的环5. 设G是一个无向图，下列哪个说法是正确的？（）A. G的每个顶点的度数都相等B. G的每个顶点的度数都不相等C. G的任意两个顶点之间都有一条边D. G的任意两个顶点之间都不一定有边6. 下列哪个图是哈密顿图？（）A. K3,3B. K5C. K4,4D. K67. 设G是一个具有n个顶点的连通图，则G的最小生成树至少包含（）A. n个顶点B. n-1条边C. n+1条边D. 2n条边8. 下列哪个算法可以用来求解最短路径问题？（）A. Dijkstra算法B. Kruskal算法C. Prim算法D. Floyd算法9. 设P和Q是两个命题，下列哪个命题与(P→Q)∧(Q→P)等价？（）A. P∧QB. P∨QC. P↔QD. ¬P∨¬Q10. 设A是一个有限集合，A的幂集是指（）A. A的所有子集B. A的所有真子集C. A的所有非空子集D. A的所有非空真子集二、填空题（每题3分，共30分）11. 设集合A={1, 2, 3, 4, 5}，B={2, 4, 6, 8}，则A-B=______。

12. 设P(x)是谓词逻辑公式，∃xP(x)表示“存在一个x使得P(x)成立”，那么∀x¬P(x)表示“______”。

最新国家开放大学电大《离散数学》期末题库及答案《离散数学》题库及答案一一、单项选择题（每小题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 ,。

A. B. C. D.
参考答案： B
6、 设 A. 代数系统 B. 半群 C. 群
,*为普通乘法,则<S,*>是( )
D. 都不是
参考答案： A
7、 设S={0,1},*为普通乘法,则< S , * >是( ) A. 半群,但不是独异点 B. 只是独异点,但不是群 C. 群 D. 环,但不是群
参考答案： B
A. B. C. D.
参考答案： B
3、 命题“有的人喜欢所有的花”的逻辑符号化为( ) 设D:全总个体域,F(x):x是花,M(x) :x是人,H(x,y):x喜欢y
A. B. C. D.
参考答案： D
4、 下列等价式成立的有( )
A. B. C. D.
参考答案： D
5、 下列公式是重言式的有( )
5、 ( )设S={1,2},则S在普通加法和乘法运算下都不封闭。 参考答案： 正确
8、 谓词公式
中的x是( )
A. 自由变元
B. 约束变元
C. 既是自由变元又是约束变元
D. 既不是自由变元又不是约束变元
参考答案： C
9、 设
是一个有界格,如果它也是有补格,只要满足( )
A. 每个元素都至少有一个补元
B. 每个元素都有多个补元
C. 每个元素都无补元
D. 每个元素都有一个补元
参考答案： A
10、 一棵无向树T有4度、3度、2度的分枝点各1个,其余顶点均为树叶,则T中有( )片树叶
A. 3 B. 4 C. 5 D. 6
参考答案： C
11、 设
A. {{1,2}} B. {1,2 } C. {1} D. {2}
参考答案： A
,则有( )