2离散数学模拟题

一、填空1．不能再分解的命题称为____________，至少包含一个联结词的命题称为____________。

2．一个命题公式A(P, Q, R)为真的所有真值指派是000, 001, 010, 100，则其主析取范式是__________________，其主合取范式是_________________。

3．设A={a,b,c}，B={b,c,d,e}，C={b,c}，则( A ⋃ ⊕＝____________。

4．幂集P(P(∅)) ＝________________。

5．设A为任意集合，请填入适当运算符，使式子A________A=∅；A________A’=∅成立。

6．设A={0，1，2，3，6}，R={〈x,y〉|x≠y∧(x,y∈A)∧y≡x(mod 3)}，则D(R)=____________，R(R)=____________。

7．称集合S是给定非空集合A的覆盖：若S={S1，S2，…，S n}，其中S i⊆A，S i≠Ø，i=1，2，…，n，且______ _____；进一步若_____ _______，则S是集合A的划分。

8．两个重言式的析取是____ ____式，一个重言式和一个永假式的合取式是式。

9．公式┐(P∨Q) ←→(P∧Q)的主析取范式是。

10. 已知Π={{a}{b,c}}是A={a,b,c}的一个划分，由Π决定的A上的一个等价关系是。

二、证明及求解1．求命题公式（P→Q）→（Q∨P）的主析取范式。

2．推理证明题1）⌝P∨Q，⌝Q∨R，R→S⇒P→S。

2) (∀x)(P(x)→Q(y)∧R(x))，(∃x)P(x)⇒Q(y)∧(∃x)(P(x)∧R(x))x)}，S={〈x,y〉|x,y∈A∧（x=y+2）}。

3．设A={0，1，2，3}，R={〈x,y〉|x,y∈A∧(y=x+1∨y=2试求R S R。

4．证明：R是传递的⇔R*R⊆R。

5．设R是A上的二元关系，S={<a, b>| 存在c∈A，使<a, c>∈R，且<c, b>∈R}。

离散数学练习题一、选择题1、G是一棵根树，则（A ）。

A、G一定是连通的B、G一定是强连通的C、G只有一个顶点的出度为0D、G只有一个顶点的入度为12、下面哪个语句不是命题（C ）。

A、中国将成功举办2008年奥运会B、一亿年前地球发生了大灾难C、我说的不是真话D、哈密顿图是连通的3、设R是实数集合，在上定义二元运算*：a，b∈R，a*b=a+b-ab，则下面的论断中正确的是（C ）。

A、0是*的零元B、1是*的幺元C、0是*的幺元D、*没有等幂元4、设G是群，当G有（D ）个元素时，不能肯定G是交换群。

A.4B.5C.6D.75、无向完全图K3的不同构的生成子图有（ D ）个。

A. 6B.5C. 4D. 36、在自然数N上定义的二元运算∙，满足结合律的是( C )。

A.a∙b=a－bB. a∙b=a+2bC. a∙b=max{a,b}D. a∙b=∣a－b∣7、设集合A＝{{1,2,3},{4,5},{6,7,8}}，则下列各式为真的是( D )。

A.1∈AB.{{4,5}}⊂AC. {1,2,3}⊆AD.∅∈A8、由5个结点可构成的根树中，其叉数m最多为( D )。

A.2B.3C.5D. 49、设集合A={1,2,3,…,10}，下面定义的哪种运算关于集合A是不封闭的？（D ）A、x*y=max{x,y}B、x*y=min{x,y}C、x*y=GCD(x,y)，即x,y的最大公约数D、x*y=LCM(x,y)，即x,y的最小公倍数10、仅有一个孤立结点的图称为( B )。

A.零图B.平凡图C.补图D.子图11. 下列各组数中，哪个可以构成无向图的度数列（B ）。

A.1，1，1，2，2B.2，2，2，2，3C.1，2，2，4，6D.2，3，3，312. *是定义在Z上的二元运算，y*=∈+,，则*的幺元和零元分别是（D ）。

∀,xyyxxZyx-A.不存在，0B.0，1C.1，不存在D.不存在，不存在 13. 设N N N f ,:→为自然数，且⎪⎩⎪⎨⎧=为偶数若为奇数若x xx x f 21)(则})0({)0(f f 和分别是（B ）。

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

请监考老师负责监督。

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

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

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

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

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

[A] 3[B] 8[C]9[D]272、设{}{}1,2,3,5,8,1,2,5,7A B 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，则下列命题不成立的是（）。

《离散数学》模拟题（补）一．单项选择题1．下面四组数能构成无向图的度数列的有( )。

A、 2,3,4,5,6,7；B、 1,2,2,3,4；C、 2,1,1,1,2；D、 3,3,5,6,0。

2．图的邻接矩阵为( )。

A、；B、；C、；D、。

3.设S1={1，2，…，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}，S5={3，5}，在条件下X与（）集合相等。

A、X=S2或S5 ；B、X=S4或S5；C、X=S1，S2或S4；D、X与S1，…，S5中任何集合都不等。

4．下列图中是欧拉图的有( )。

5.下述命题公式中，是重言式的为（）。

A、；B、；C、；D、。

6.的主析取范式中含极小项的个数为（）。

A 、2； B、 3； C、5； D、0⎪⎪⎪⎪⎪⎭⎫⎝⎛1111111⎪⎪⎪⎪⎪⎭⎫⎝⎛1111111111111111⎪⎪⎪⎪⎪⎭⎫⎝⎛1111111⎪⎪⎪⎪⎪⎭⎫⎝⎛111111131SXSX⊄⊆且)()(qpqp∨→∧))())(()(pqqpqp→∧→↔↔qqp∧→⌝)(qpp↔⌝∧)(rqpwff→∧⌝)(7.给定推理① P ② US ① ③ P ④ ES ③ ⑤ T ②④I ⑥ UG ⑤推理过程中错在（ ）。

A 、①->②;B 、②->③;C 、③->④;D 、④->⑤8.设S 1={1，2，…，8，9}，S 2={2，4，6，8}，S 3={1，3，5，7，9}，S 4={3，4，5}， S 5={3，5}，在条件下X 与（ ）集合相等。

A 、X=S 2或S 5 ；B 、X=S 4或S 5；C 、X=S 1，S 2或S 4；D 、X 与S 1，…，S 5中任何集合都不等。

9.设R 和S 是P 上的关系，P 是所有人的集合，，则表示关系 （ ）。

A 、；B 、；C 、 ；D 、。

10.下面函数（ ）是单射而非满射。

A 、； B 、；C 、；D 、。

《离散数学》模拟题北航10秋学期《离散数学》模拟题⼀⼀、单项选择题（本⼤题共15⼩题，每⼩题2分，共30分）1.∑中所有有限长度的串形成的集合记为∑* ，容易证得∑*上的连接运算不满⾜交换律，但满⾜（ A ） A ．结合律 B ．分配律 C ．幂等律 D ．吸收律 2.Klein 群中元素a,b,c 的阶为（ B ）。

A ．1B ．2C ．3D ．4 3.群G 的元素x 的所有幂的集合为G 的⼦群,称由x ⽣成的⼦群。

记为（ A ）. A ． B ．(x) C ．x D ．[x] 4.交换环是指乘法满⾜（ A ）。

A ．交换律B ．结合律C ．分配律D ．吸收律 5.⾄少有（ B ）元素的含单位元、⽆零因⼦环称为除环。

A ．⼀ B ．⼆ C ．三 D ．四 6.∨,∧满⾜( C )的格称为分配格A ．交换律B ．结合律C ．分配律D ．幂等律 7.若L 为有限布尔代数,则（ B ）正整数n ，L 与含有n 个元素的集合A 的幂集同构。

A ．不存在 B ．存在 C ．有可能存在 8.有向图D 的顶点v 作为边的始点的次数之和称为v 的出度，记为d +(v)， v 作为边的终点的次数之和称为v 的⼊度，记为d -(v)，v 的度数d(v)= ( A )。

A ．d +(v)+d -(v)B ．d +(v)C ．d -(v)D ．d +(v)*d -(v) 9.若通路Г=v 0e 1v 1e 2…e 1v 1 中所有顶点互不相同(所有边⾃然互不相同)时称为（ B ） A ．初级回路 B ．路径 C ．复杂通路D ．迹 10.在n 阶图中，若⼀顶点存在到⾃⾝的回路，则必存在从该顶点到⾃⾝的长度不超过( B )的回路。

A ．n-1 B ．n C ．n+1 D ．2n 11.“⼈总是要死的”谓词公式表⽰为（ C ）。

（论域为全总个体域）M(x)：x 是⼈；Mortal(x)：x 是要死的。

A ．)()(x Mortal x M →； B ．)()(x Mortal x M ∧C ．))()((x Mortal x M x →?； D ．))()((x Mortal x M x ∧?12. 公式))()((x Q x P x A →?=的解释I 为：个体域D={2}，P(x)：x>3, Q(x)：x=4则A 的真值为（ A ）。

《离散数学》模拟试卷二答案一、【单项选择题】(本大题共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页。

离散数学模拟试题2一、单选题（本大题共8小题，每小题2分，共16分）1．设p：天下大雨，q：我们乘公共汽车。

命题“除非天下大雨，否则我们不乘公共汽车。

”符号化为（）A. p→qB. q→pC. p∧qD.⌝q →⌝ p 2．设F(x)：x是兔子，G(y)：y是乌龟，H(x,y)：x比y跑得快。

命题“有的兔子比所有的乌龟跑得快”符号化为（）A.∀x(F(x)→∃y(G(y)∧H(x,y)))B.∀x∃y((F(x)∧G(y))→H(x,y))C.∀x∃y(F(x)→(G(y)→H(x,y)))D. ∃x(F(x)∧∀y(G(y)→H(x,y))) 3．设集合A=｛∅，a｝，下面四个命题为真的是（）A. a⊆AB.∅⊆AC.｛∅｝∈ AD.｛a｝∈ A 4．设集合A=｛a,b,c,d｝,A上的关系R=｛〈a,b〉,〈b,a〉, 〈c,d〉,〈d,c〉｝∪I A，则下面命题为真的是（）A. R是A上的等价关系B. R是A上的偏序关系C. R是A上的全序关系D. R是A上的全域关系5．设V=〈N，+〉，其中N为自然数集合，+为数的普通加法。

令φ:N→N，φ（x）=2x。

下面四个命题为真的是（）A.是满同态B.是单自同态C.是自同构D.是V到自身的映射，但A，B，C都不是6．设Z是整数集合，∩是Z的幂集P（Z）上的交运算。

令V=〈P（Z）；∩〉，则V是（）A.循环群 B. 有限群 C. 无限群 D. 含幺半群7．设G是有n个顶点m条边的无向简单图,并且m=n－1,则有结论（）A. G一定是树 B. G不一定是树 C.G一定不是树 D.G是森林8．完全图K4是（）A. 欧拉图B.二部图C.平面图D.非平面图二、填空题（本大题共8小题，每小题3分，共24分）1．含n个命题变项的矛盾式的主析取范式为。

2．设个体域为自然数集合N，命题∀x∃y(x+y=1)的真值为。

3．设A=｛a,b｝，IA 是A上的恒等关系，则商集A/IA= 。

离散数学单元训练模拟题编者：金鹏时间：2008-5-6目录离散数学模拟题一 (3)离散数学模拟题二 (8)离散数学模拟题三 (15)离散数学模拟题四 (20)离散数学模拟题五 (27)离散数学模拟题六 (32)离散数学模拟题七 (36)离散数学模拟题八 (42)离散数学模拟题九 (45)离散数学模拟题十 (49)离散数学模拟题十一 (52)离散数学模拟题十二 (59)离散数学模拟题十三 (62)离散数学模拟题十四 (67)离散数学模拟题十五 (74)离散数学模拟题十六 (78)离散数学模拟题十七 (90)离散数学模拟题一一、判断题（共 12 分，每小题 1 分）( ) 1、（ØpÚØq）®(p®Øq)不是重言式。

( )2、在命题逻辑中，任何命题公式的主合取范式都是存在的，并且是唯一的。

( ) 3、命题函数是命题。

( ) 4、设 A，B，C 是 Q的子集，则有 A´(BÅC)¹（A´B）Å（A´C）。

( )5、设 A、B为集合，若 B≠Φ，则 A-B包含于 A。

( ) 6、若 R 为集合 A 上的非对称关系，则R 2 亦然。

( )7、存在一种建立在某个集合上的关系，它可以是对称的、反对称的、自反的、反 自反和可传递的。

( )8、设〈G，*〉是群，对于 G 中的任意元素 a，b 有：（a× b）-1=b-1× a-1。

( )9、在一个代数系统中，某个元素有多个左逆元，就不可能有右逆元。

( )10、设是非连通平面图 G的对偶图中的顶点数，边数和面数，则它们之间不满足欧 拉公式；( )11、设无向图 G 具有割点，则G 中一定不存在汉密尔顿回路；( )12、有向图G 是单侧连通；（G）二、求出下列命题公式的主析取范式和主合取范式。

（10 分）(P®(QÙR))Ù(ØP®(ØQÙR))三、逻辑推证（10 分）（1）Ø（P®Q）®Ø (RÚS)，((Q®P)ÚØR) ，Ø(R®P)Þ P®Q四、用谓词推理理论来论证下述推证（10 分）任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或喜欢乘汽车，或喜欢骑自行车（可 能这两种都喜欢）。

《离散数学》期末考试考点及模拟题答案一、考试题型及分值各种题型所占的比例：填空题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.设：。