离散数学模拟题(开卷)

离散数学模拟试题填空题30分1. 数理逻辑研究的中⼼问题是推理，命题必须具备：其⼀，语句是_______；其⼆，语句有_______。

命题的真值就是命题的逻辑取值。

若⼀个命题是真命题，其真值为____ ；若⼀个命题是假命题，其真值为___ 。

2. 基本的逻辑联结词包括 ____、____、____、____、____。

含有n 个命题变项的公式A 共有____个赋值。

n 个命题变项只能⽣成____个真值不同的公式。

3. 在⼀阶逻辑中，简单命题被分解成_______和_______。

命题中常出现的量词有_______和_______。

4. 集合是⼀些事物汇集到⼀起组成的⼀个整体，不含任何元素的集合叫做_____，它是所有集合的⼀个⼦集。

设集合}b ，a { A ，它的全体⼦集构成的集合叫做A的_____，P （A ）=_______________________________________________。

5. ⼏个集合之间的关系和运算可以⽤⽂⽒图给与形象的描述。

⽤公式表⽰下列阴影部分的集合1=_________________，2=_________________1 .2 .6. ⼀个⾮空集合，且它的元素都是有序对或者集合是空集，则称该集合为⼀个⼆元关系。

任何集合都有三个特殊的⼆元关系________、________、________。

7.关系的运算中R 的逆关系R -1=____________,关系的性质有_____________________________。

如果}a a,,c a,，b ，a {><><><=F ,},c b,，b ，c ,b b,,c c,,a a,，b ，a {><><><><><><=H ，则F?H=____________________________ 8.图论中所说的图是描述事物之间关系的⼀种⼿段，许多事物之间的关系可抽象成点及它们之间的连线，集合论中⼆元关系的关系图就是简单的图。

离散模拟答案11命题符号化（共6小题，每小题3分，共计18分）1.用命题逻辑把下列命题符号化a)假如上午不下雨，我去看电影，否则就在家里读书或看报。

b)我今天进城，除非下雨。

c)仅当你走，我将留下。

2.用谓词逻辑把下列命题符号化a)有些实数不是有理数b)对于所有非零实数x，总存在y使得xy=1。

c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b.一、简答题（共6道题，共32分）1.求命题公式(P→(Q→R))↔(R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋值。

（5分）2.设个体域为{1,2,3}，求下列命题的真值（4分）a)∀x∃y(x+y=4)b)∃y∀x (x+y=4)3.求∀x(F(x)→G(x))→(∃xF(x)→∃xG(x))的前束范式。

（4分）4.判断下面命题的真假，并说明原因。

（每小题2分，共4分）a)（A⋃B）－C=(A-B) ⋃(A-C)b)若f是从集合A到集合B的入射函数，则|A|≤|B|5.设A是有穷集，|A|=5，问（每小题2分，共4分）a)A上有多少种不同的等价关系？b)从A到A的不同双射函数有多少个？6.设有偏序集<A,≤>，其哈斯图如图1，求子集B={b,d,e}的最小元，最大元、极大元、极小元、上界集合、下界集合、上确界、下确界，(5分)f g图17.已知有限集S={a1,a2,…,a n},N为自然数集合，R为实数集合，求下列集合的基数S;P(S);N,N n;P(N);R,R×R,{o,1}N（写出即可）(6分)二、证明题（共3小题，共计40分）1.使用构造性证明，证明下面推理的有效性。

（每小题5分，共10分）a)A→(B∧C),(E→⌝F)→⌝C, B→(A∧⌝S)⇒B→Eb)∀x(P(x)→⌝Q(x)), ∀x(Q(x)∨R(x))，∃x⌝R(x) ⇒∃x⌝P(x)2.设R1是A上的等价关系，R2是B上的等价关系，A≠∅且B≠∅，关系R满足：<<x1,y1>,<x2,y2>>∈R，当且仅当< x1, x2>∈R1且<y1,y2>∈R2。

数理系离散数学模拟试卷一．选择题（每题1分，共10分）1．判断下列语句哪一个是命题：（）。

A．请把门关上！ B．你喜欢鲁迅的作品吗？C．我在说谎 D．雪是黑色的。

2．命题公式P→(Q→P)为（）。

A．重言式 B．可满足式 C．矛盾式 D．等价式3．若个体域为整数域，下列公式中（）为假。

A．∀x∃y(x+y=0) B．∃y∃x(x+y=0)C．∀x∀y(x+y=0) D．┐∃y∀x(x+y=0)4．设A，B，C为任意三个集合，下列命题正确的是（）。

A．若A∪B=A∪C，则B=C B．若A∩B=A∩C，则B=CC．若~A∪B=E，则A⊆B D．若A－B=∅，则A=B5．设R和S是集合A上的关系，若R和S是传递的，则（）。

A．R∩S是传递的 B．R∪S是传递的C．R·S是传递的 D．以上都不对6．若f•g是满射，则（）。

A．g必是满射 B．f必是单射C．f必是满射 D．g必是单射7．设G是6个元素的循环群，a是生成元素，则下列为G的子群的是（）。

A．{a} B．{e,a3} C．{e, a} D．{e, a ,a2}8．判断下列集合中对所给的二元运算不封闭的是（）。

A．整数集合Z上的普通加法运算；B．非零整数集合上的普通除法运算；C．设A={a1,a2,…,an}，n≥2，∀a,b∈A，a*b=b；D．设A ={2n│n∈Z}，集合A上的普通加法和乘法运算。

9．n阶k度正则图的边数应为（）。

A．n(n-1)/2 B．n C．n(n+1) D．nk/210．设G是有n个顶点，m条边的无向简单图，并且m=n-1，则下列（）是正确的。

A．G一定是树 B．G不一定是树C．G一定不是树 D．以上说法都不对二．填空题（每空2分，共30分）1．设P：王华是一班的学生；Q：王华是二班的学生。

则：命题“王华要末是一班的学生要末是二班的学生”符号化为____________。

2．谓词公式∀xP(x)→∀xQ(x)∨∃yR(y)的前束范式为：______________________________。

模拟试题 3一. 有两个小题1．分别说明联结词、∧、∨、→以及的名称，以及在自然语言中表示什么含义。

2．分别列出P Q、P Q、P Q、P Q的真值表(填下表)。

P Q P Q P Q P Q P Q二．有三个问题1.先说明什么叫永真式(也叫重言式)。

2.指出下面的命题公式中哪些是永真式(只写题号即可)。

(1). (P∨Q)→P (2). P→(P∨Q)(3). (P∧(P→Q))→Q (4). (P∧Q)→Q3.然后对上面的永真式任选其中一个给予证明(方法不限)。

三．判断下面命题的真值。

对你的回答，给予证明或者举反例。

(1)．如果A∈B，B C，则 A C 。

(2)．空集是唯一的。

四．R是实数集合，给定R上的五个关系如下:R1={<x,y>|x=y2} R2={<x,y>|y=x+6}R3={<x,y>|y=(x+1)-1} R4={<x,y>|y=2x}R5={<x,y>|x2+y2=4}上述五个关系中，哪些不是从R到R的函数，为什么如果是函数，则哪些是从R到R的入射函数哪些是从R到R的双射函数五．用谓词逻辑推理的方法证明下面推理的有效性。

要求按照推理的格式书写推理过程。

xP(x), x(Q(x) R(x)), x(P(x) R(x))x Q(x)六．给定集合A={1,2,3},定义A上的关系如下：R={<1,1>,<1,2>,<1,3>,<3,3>}S={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}T={<1,1>,<2,1>,<2,2>,<2,3>,<3,3>}M=Ф(空关系)N=A×A(完全关系（全域关系）)1.分别画出上述各个关系的有向图。

专科《离散数学模拟》试题（一）姓名______________ 学号______________ 成绩______________一、填空（每小题5分，共25分）1．设}41,,3|{≤≤∈==K N k k x x A ，则用列举法表示A =_____________________。

2．设}2,{φ=A ，则A 的幂集=A 2________________________。

3．设)}1,2(),2,4(),3,1{(=ρ是A 到B 的关系，则ρ的逆关系=ρ~_______________。

4．下图G 的邻接矩阵A =__________________________5．设}},3,2{,3,2{φ=A ，则=-}}3,2{{A ____________________________。

二、选择题（将正确答案的编号填入相应题目后面的括号中，每小题5分，共20分） 1．设集合}3,2,1{=A ，A 上的关系)}1,1(),1,2(),1,3(),3,2{(=ρ，则ρ是（ ）。

A ．自反的B ．反对称的C ．可传递的2．设有函数Z Z Z f →⨯:（Z 表示非负整数集），定义为y x y x f +=),(，则f 是（ ）。

A ．满射B ．内射C ．双射3．设}4,3,2,1{=A ，则A 的分划有（ ）。

A ．}}3{},4,2{),1{(B ．}}4{},3,2{{C ．}}4{},3,2,1{{4．设简单图G 所有结点的度之和为12，则G 一定有（ ）。

A ．3条边 B ．4条边 C ．6条边4v 3v 2v 1v三、问答题（每小题6分，共42分）1．下图G 是否二部图？若是，找出它的互补结点子集。

2．设有命题公式)(Q P P F →⌝∨=，问F 是否求真公式？为什么？3．判断下图是否欧拉图，若是，找出一个欧拉回路。

v 2v 1v 53v 5v4．设1ρ和2ρ是集合A 上的偏序关系，问1ρ－2ρ是A 上的偏序关系吗？为什么？5．判断下述命题公式的等值关系是否成立P Q P Q P Q ∨⌝⇔→∧→)((6．将下一命题符号化。

北京语言大学网络教育学院《离散数学》模拟试卷一注意：1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。

请监考老师负责监督。

2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。

3.本试卷满分100分，答题时间为90分钟。

4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。

一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。

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

[A]3 [B]8 [C]9 [D]272、设A 1,2,3,5,8,B 1,2,5,7 ,则A B（）。

[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 [C]p →┐q ∧q [B]p [D]p ∨┐q∧┐q11、设图 G=<V,E>的结点集为 V={v1,v2,v3}, 边集为 E={<v1,v2>,<v1,v3>}.则G 的割 （点）集是（）。

《离散数学》模拟试卷二答案一、【单项选择题】(本大题共15小题，每小题3分，共45分)二、【判断题】(本大题共8小题，每小题3分，共24分)三、【解答题】（本大题共3小题，24、25每小题10分，26小题11分，共31分）24、一次学术会议的理事会共有20个人参加，他们之间有的相互认识但有的相互不认识。

但对任意两个人，他们各自认识的人的数目之和不小于20。

问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人?根据是什么?标准答案：解：可以把这20个人排在圆桌旁，使得任一人认识其旁边的两个人。

根据：构造无向简单图G=<V,E>,其中V={v1,v2,…，V20}是以20个人为顶点的集合，E中的边是若任两个人v i和v j相互认识则在v i与v j之间连一条边。

∀Vi∈V,d(v i)是与v i相互认识的人的数目，由题意知∀vi,v j∈V有d(v i)+d(v j)≥20,于是G中存在汉密尔顿回路。

设C=V i1V i2…V i20V i1是G中一条汉密尔顿回路，按这条回路的顺序按其排座位即符合要求。

复习范围或考核目标：考察无向图中的哈密尔顿图的应用，见课本211页。

25、图G=<V, E>，其中V={a, b, c, d, e, f }，E={(a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (d, e), (d, f), (e, f)}，对应边的权值依次为5，2，1，2，6，1，9，3及8．（1）画出G的图形；（2）写出G 的邻接矩阵。

标准答案：解：（1）因为V ={a , b , c , d , e , f } E ={(a , b ), (a , c ), (a , e ), (b , d ), (b , e ), (c , e ), (d , e ), (d , f ), (e , f )}， 权值依次为5，2，1，2，6，1，9，3及8 所以，G 的图形如右图所示：（2）分析：定义3.3.1 设G =<V ，E >是一个简单图，其中V ={v 1，v 2，…，v n }，则n 阶方阵A (G )=(a ij )称为G 的邻接矩阵，其中⎪⎩⎪⎨⎧==.1j i v v v v a j i j i ij 不相邻或与相邻与邻接矩阵：复习范围或考核目标：考察图的矩阵表示，见课本187页。

《离散数学》期末考试考点及模拟题答案一、考试题型及分值各种题型所占的比例：填空题10%,判断题10%,选择题20%,其它题型60%新出试卷按照如下各种题型所占的比例：填空题20%，判断题15%，选择题30%，其它题型35%二、考点1.命题逻辑熟练掌握命题及其表示；掌握常用联结词（「、八、V、f、）的使用；熟练掌握命题公式的符号化；熟练掌握使用真值表判别命题等价的方法；掌握使用等价公式判别命题等价的方法；掌握重言式与蕴含式的概念及其判别方法;了解其他联结词的使用；了解对偶的概念；掌握求命题范式的方法；熟练掌握命题演算推理的基本理论.2.谓词逻辑熟练掌握谓词的概念及其表示；熟练掌握量词的使用；掌握使用谓词公式翻译命题的方法；掌握变元的约束；掌握谓词演算中等价式与蕴含式的判别;了解前束范式的求法；熟练掌握谓词演算推理的基本理论.3.集合与关系熟练掌握集合的概念和表示法；掌握集合的基本运算；掌握序偶与笛卡尔积的概念；熟练掌握关系及其表示；掌握关系的基本性质；了解复合关系和逆关系的概念；掌握关系的闭包运算；了解集合的划分和覆盖；掌握等价关系与等价类的概念;了解相容关系的概念；掌握各种序关系的概念.4.函数熟练掌握函数的概念；掌握逆函数和复合函数的概念；了解基数的概念；了解可数集与不可数集；了解基数的比较.5.代数结构掌握代数系统的概念；掌握n元运算及其性质；掌握半群、群与子群的概念;了解阿贝尔群和循环群的概念；了解陪集与拉格朗日定理;了解同构与同态的概念；了解环与域的概念.6.图论掌握图的基本概念；掌握路与回路的概念；熟练掌握图的矩阵表示；掌握欧拉图和哈密顿图的概念；掌握平面图的概念；了解对偶图与着色；熟练掌握树与生成树的概念;了解根树及其应用.（一）参考教材与网上资料复习（二）随堂练习或作业题在在新出试卷里有较大比例提高三、模拟试卷附后（请参考学习资料，找到或者做出解答）一、考试对象计算机学科中计算机科学与技术、软件工程等专业本科生二、考试的性质、目的离散数学是随着计算机科学的发展而逐渐形成的一门学科，是近代数学的一个分支在计算机科学中，它主要应用于数据结构、操作系统、编译原理、数据库理论、形式语言与自动机、程序理论、编码理论、人工智能、数字系统逻辑设计等方面它是计算机科学各专业重要的专业基础课.本课程教学的目标是:①使学生掌握离散数学的基本理论和基本知识，为学习有关课程以及今后工作打好基础.②培养和提高学生的抽象思维与逻辑推理能力.四、考试方式及时间：考试方式：闭卷考试时间：120分钟五、课程综合评定办法1期末闭卷考试：占总成绩60%.2、平时成绩（作业、考勤情况等）：占总成绩40%3、试题难易程度：基础试题：中等难度试题：较难试题：难度较大的试题 =4： 3： 2： 1六、考试教材《离散数学》左孝凌、李为^、刘永才编著，上海科学技术文献出版社附：模拟试卷华南理工大学网络教育学院2012 - 2013学年度第一学期期末考试《离散数学》试卷(模拟卷)教学中心：专业层次：学号：姓名：座号：注意事项：1.本试卷共五大题，满分100分，考试时间120分钟，闭卷;2.考前请将以上各项信息填写清楚；3.所有答案直接做在试卷上,做在草稿纸上无效；4.考试结束，试卷、草稿纸一并交回.一.判断题(每题2分，共10分)1、设A, B都是合式公式，则A A B F「B也是合式公式.(J)2. P f Q o「P v Q ,(v)3、对谓词公式(V x) (P (y) V Q (x,y)) △R (x,y)中的自由变元进行代入后得到公lllllll !lllll式(V x) (P (z) V Q (x,z)) △R (x,y) . (x)4.对任意集合 A、B、C,有(A—B) —C = (A—C) - (B—C). (j)5. 一个结点到另一个结点可达或相互可达. (X )二.单项选择题(每题2分，共20分)1.设：。

离散数学考试试题及答案离散数学考试试题及答案离散数学是计算机科学和数学中的一门重要学科，它研究的是离散的结构和对象。

离散数学的理论和方法在计算机科学、信息科学、通信工程等领域具有广泛的应用。

下面将为大家提供一些离散数学考试试题及答案，希望对大家的学习和复习有所帮助。

1. 集合论题目(1) 设A={1,2,3,4,5}，B={3,4,5,6,7}，求A∪B的结果。

答案：A∪B={1,2,3,4,5,6,7}(2) 设A={1,2,3,4,5}，B={3,4,5,6,7}，求A∩B的结果。

答案：A∩B={3,4,5}(3) 设A={1,2,3,4,5}，B={3,4,5,6,7}，求A-B的结果。

答案：A-B={1,2}2. 图论题目(1) 给定一个无向图G，顶点集为V={A,B,C,D,E}，边集为E={(A,B),(A,C),(B,D),(C,D),(D,E)}，求该图的邻接矩阵。

答案：邻接矩阵为：A B C D EA 0 1 1 0 0B 1 0 0 1 0C 1 0 0 1 0D 0 1 1 0 1E 0 0 0 1 0(2) 给定一个有向图G，顶点集为V={A,B,C,D,E}，边集为E={(A,B),(B,C),(C,D),(D,E),(E,A)}，求该图的邻接表。

答案：邻接表为：A ->B ->C ->D ->E -> AB -> CC -> DD -> EE -> A3. 命题逻辑题目(1) 判断以下命题是否为永真式：(p∨q)∧(¬p∨r)∧(¬q∨¬r)。

答案：是永真式。

(2) 给定命题p：如果天晴，那么我去游泳；命题q：我没有去游泳。

请判断以下命题的真假：(¬p∨q)∧(p∨¬q)。

答案：是真命题。

4. 关系代数题目(1) 给定关系R(A,B,C)和S(B,C,D)，求R⋈S的结果。