广东工业大学2019年《2027离散数学及其应用》考博专业课真题试卷

仰恩大学试卷2018-2019学年第1学期课号课程名称离散数学（期末;闭卷）适用班级（或年级、专业）考试时间120分钟班级学号姓名题号一二三四五六七八九成绩满分201010101010101010100得分一、设集合完成下列各小题。

（第1小题2分，第2小题5分，第3小题3分，第4小题10分，共20分）1、求S 的幂集()P S 。

2、证明(),P S <⊆>是偏序集。

3、画出偏序集(),P S <⊆>的哈斯图。

4、在()P S 上定义两个二元运算∧和∨：对任意,()A B P S ∈，A B A B ∧=⋂，A B A B ∨=⋃。

请填空（在横线上填是或不是并回答为什么）：①代数系统(),P S <⊆>格，因为。

②代数系统(),P S <⊆>有界格，因为。

③代数系统(),P S <⊆>有补格，因为。

④代数系统(),P S <⊆>分配格，因为。

⑤代数系统(),,,~P S <⋂⋃>布尔代数，因为。

二、计算（10分）设 123122323(,,)()()()E x x x x x x x x x =∧∨∧∨∧是布尔代数{0,1},,,<∨∧> 上的一个布尔表达式。

试写出123(,,)E x x x 的析取范式和合取范式（用列函数表的方法）。

三、回答问题(共10分)。

完全图n K 是否是欧拉图？是否是哈密尔顿图？为什么？{},,S a b c =四、画图（10分）对于下图，利用克鲁斯克尔算法求一棵最小生成树。

五、计算（10分）一棵树有两个结点度数为2，1个结点度数为3，3个结点度数为4，其余结点度数为1。

问该树有几个度数为1的结点。

六、证明（10分）(,)G V E =图是无向简单图，其中||||V n E m ==，，证明：2)1(-≤n n m 。

证明因为G 是简单图，所以图G 中没有环和平行边，任意两结点间最多有一条边，故2(1)2n n n m C -≤=。

全国2002年4月离散数学试题课程代码：02324一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( )A. 汉密尔顿回路B.欧拉回路C. 汉密尔顿通路D.初级回路2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( )A.10B.12C.16D.143.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( )A.b∧(a∨c)B.(a∧b)∨(a’∧b)C.(a∨b)∧(a∨b∨c)∧(b∨c)D.(b∨c)∧(a∨c)4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是()A.<{1}, ·>B.〈{-1}, ·〉C.〈{i}, ·〉D.〈{-i},·〉5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交运算，下列系统中是代数系统的有()A〈.Z，+，/〉 B.〈Z，/〉C〈.Z，-，/〉 D.〈P(A)，∩〉6.下列各代数系统中不含有零元素的是() A.〈Q，*〉Q是全体有理数集，*是数的乘法运算B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算C.〈Z，Z是整数集，定义为x xy=xy, x,y∈ZD.〈Z，+〉，Z是整数集，+是数的加法运算7.设A={1,2,3}，A上二元关系R的关系图如下：R具有的性质是A.自反性B.对称性C.传递性D.反自反性8.设A={a,b,c} ，A 上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( )A.R∪IAB.RC.R∪{〈c,a〉}D.R ∩IA9.设X={a,b,c},Ix 是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的等价关系，R应取( )A. ｛〈c,a 〉，〈a,c 〉｝B.{〈c,b〉，〈b,a〉}C.{ 〈c,a 〉，〈b,a 〉}D.{〈a,c〉，〈c,b〉}10.下列式子正确的是()A. ∈B.C.{ }D.{ }∈11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x<y. 下列公式在R下为真的是( )A.( x)( y)( z)(A(x,y)) →A(f(x,z),f(y,z))B.( x)A(f(a,x),a)C.( x)( y)（A(f(x,y),x))D.( x)( y)(A(x,y) →A(f(x,a),a))12.设B是不含变元x的公式，谓词公式(x)(A(x)→B)等价于()A.( x)A(x)→BB.( x)A(x)→BC.A(x)→BD.( x)A(x)→( x)B13. 谓词公式( x)(P(x,y)) →(z)Q(x,z)∧(y)R(x,y)中变元x()A.是自由变元但不是约束变元B.既不是自由变元又不是约束变元C.既是自由变元又是约束变元D.是约束变元但不是自由变元14.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为()A.P∨QB.P∧┐QC.P→┐QD.P ∨┐Q15.以下命题公式中，为永假式的是( )A.p→(p∨q∨r)B.(p→┐p)→┐pC.┐(q→q)∧pD.┐(q∨┐p)→(p∧┐p)二、填空题(每空1分，共20分)16.在一棵根树中，仅有一个结点的入度为______，称为树根，其余结点的入度均为______。

2020-2021《离散数学》期末课程试卷A1专业： 考试日期： 时间： 总分： 分 闭卷一大题：选择题（共10小题，每小题2分，共20分）1．下列是两个命题变元P ，Q 的小项是（ ）A ．P ∧┐P ∧QB ．┐P ∨QC ．┐P ∧QD ．┐P ∨P ∨Q 2．令P ：今天下雪了，Q ：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ）A ．P →┐Q B ．P ∨┐Q C ．P ∧Q D ．P ∧┐Q 3．下列等值式不正确的是（ ） A ．┐(∀x )A ⇔(∃x )┐AB ．(∀x )(B →A (x ))⇔B →(∀x )A (x )C ．(∃x )(A (x )∧B (x ))⇔( ∃x )A (x )∧(∃x )B (x )D ．(∀x )( ∀y )(A (x )→B (y ))⇔(∃x )A (x )→(∀y )B (y ) 4．设R 为实数集，函数f ：R →R ，f (x )=2x ，则f 是（ ）A ．满射函数B ．入射函数C ．双射函数D ．非入射非满射 5．设A ={a ,b ,c ,d }，A 上的等价关系R ={<a ,b >,<b ,a >,<c ,d >,<d ,c >}∪I A ，则对应于R 的A 的划分是（ ）A ．{{a },{b ,c },{d }}B ．{{a ,b },{c },{d }}C ．{{a },{b },{c },{d }}D ．{{a ,b },{c ,d }}6．设X ，Y ，Z 是集合，“-”是集合相对补运算，下列等式不正确的是（ ） A ．(X -Y )-Z =X -(Y ∩Z ) B ．(X -Y )-Z =(X -Z )-Y C ．(X -Y )-Z =(X -Z )-(Y -Z ) D ．(X -Y )-Z =X -(Y ∪Z )7．设*是集合A 上的二元运算，称Z 是A 上关于运算*的零元，则（ ） A ．对所有x 属于A ，有x *Z =Z *x =ZB ．Z 属于A ，且对所有x 属于A ，有x *Z =Z *x =ZC ．Z 属于A ，且对所有x 属于A ，有x *Z =Z *x =xD ．Z 属于A ，且存在x 属于A ，有x *Z =Z *x =Z8．在自然数集N 上，下列定义的运算“*”中不可结合的只有（ ） A ．a *b =min (a ,b ) B ．a *b =a +b C ．a *b =a b ⋅ D ．a *b =a/b 9．下列说法正确的是（ ）A ．整环必为域B .交换环必为整环C ．整环必为交换环D .交换环必为含幺环10．下列各图是欧拉图的是（ ）A.B.C.D.二大题：填空题（共10空，每空 2分，共20分）1．“如果雪是黑的，太阳从西边出”是 命题。

2020-2021《离散数学》期末课程考试试卷B一、选择题（在下列各题的括号处选择一最恰当的答案，共5小题，每小题3分，共15分）1．设S 表示二年级大学生的集合,R 表示计算机科学系学生的集合,T 表示选修离散数学的学生的集合,G 表示星期一晚上参加音乐会的学生的集合，则命题“听离散数学课的学生都没有参加星期一晚上的音乐会。

”可表示为 （ ）。

A 、T ⊆GB 、T ∩G=φC 、G ⊆TD 、(R ∩T)⊆G2．下列推理错误的是（ ）（1）如果今天是1号，则明天是5号。

今天是1号，所以明天是5号。

（2）如果今天是1号，则明天是5号。

明天是5号，所以今天是1号。

（3）如果今天是1号，则明天是5号。

明天不是5号，所以今天不是1号。

（4）如果今天是1号，则明天是5号，今天不是1号，所以明天不是5号。

A 、（3） B 、（1）（2）（4） C 、（2）（4） D 、（2）（3） 3．n 阶无向完全图K n 的边数m 是多少？（ ）A 、nB 、n 2C 、n(n-1)D 、2)1(-n n4．设有序对<2x+3,8>=<9,2x+y>则x 与y 分别是（ ）。

A 、3，2B 、-3，2C 、-3，-2D 、3，-25．已知n 阶无向简单图G 有m 条边，则G 的补图G 有( )条边。

A 、21)-n(n B 、n(n-1) C 、m n n --2)1( D 、m二、在命题逻辑中将下列命题符号化（共2小题，每小题3分，共6分）1．只有6能被2整除，6才能被4整除。

2．除非你努力，否则你将失败。

三、在一阶逻辑中将下列命题符号化（共2小题，每小题5分，共10分）1．没有不能表示成分数的有理数。

2．在北京卖菜的人不全是外地人。

四、设A={a ，b ，c ，d}，R={<a ，b>，<b ，a>，<b ，c>，<c ，d>}，求R 4。

广东工业大学试卷用纸，共 6 页，第 1 页广东工业大学试卷用纸，共 6 页，第2 页课程名称: 离散数学B卷标准答案考试时间:第 21 周星期五 ( 2007年1月 26日)一、单项选择题(本大题共8小题，每小题2分，共16分)二、填空题(本大题共8小题，每空3分，共24分)1.重言、永假2. (P ∧￢Q) ∨ (￢P∧ Q)3. ∅,{∅}4. P(x) ∨ (∃y)R(y)5. 66. {∅,{a}, {b}, {a, b}}7. {<a,a>, <b, b>, <c, c>, <b, c>, <c, b>}8. 4三、(8分)解：设做对A题的学生构成集合A，做对B题的学生构成集合B ，做对C题的学生构成集合C，由题意有：︱A︱＝48；︱B︱＝56；并可求得：|A∩B∩C︱＝12； 1分︱A∩B︱＝20； 1分︱A∩C︱＝16， 1分︱B∩C︱＝28， 1分︱A∪B∪C︱＝16； 1分︱A∪B∪C︱＝120－16＝104； 1分由容斥原理可知：︱A∪B∪C︱＝︱A︱＋︱B︱＋︱C︱－︱A∩B︱－︱A∩C︱－︱B∩C︱＋︱A∩B∩C︱1分故：︱C︱＝20＋16＋28＋104－12－48－56＝52 1分四、(10分)证明：①n阶无向简单图的顶点度数只可能为0, 1, 2, ……, n –1中的某个值。

2分②当存在度数为0的顶点时，不可能存在度数为n – 1的顶点，顶点度数只可能为0, 1, 2, ……, n– 2，共n – 1种可能； 1分因为有n个顶点，有n – 1种情况，所以由鸽洞定理得，必有2个或2个以上的顶点度数相同。

2分③当存在度数为n – 1的顶点时，不可能存在度数为0的顶点，顶点度数只可能为1, 2, ……, n –1，共n – 1种可能； 1分因为有n个顶点，有n – 1种情况，所以由鸽洞定理得，必有2个或2个以上的顶点度数相同。

20202021某大学离散数学期末课程考试试卷合集含答案离散数学是一门重要且基础的数学课程，它主要研究离散对象及其结构、关系和操作等基础概念和方法。

为了帮助同学们更好地复习离散数学课程，本文提供了20202021学年度某大学离散数学期末考试试卷合集，包含试卷以及对应的答案，供同学们参考。

第一套试卷：一、选择题（共10题，每题2分，共20分）1. 设A = {1, 2, 3, 4}，B = {2, 4, 6, 8}，则集合A与B的交集为________。

2. 若A = {1, 2, 3}，B = {3, 4, 5}，则集合A与B的并集为________。

3. 若A = {1, 2, 3}，B = {3, 4, 5}，则集合A与B的差集为________。

4. 设关系R为集合A = {1, 2, 3}到集合B = {4, 5, 6}的映射，若(1, 4) ∈ R，则R的值域为________。

5. 若集合A = {1, 2, 3}，B = {3, 4, 5}，C = {5, 6, 7}，则(A ∩ B) ∪ C = ________。

6. 若A = {1, 2, 3}，B = {4, 5, 6}，C = {7, 8, 9}，则(A ∪ B) ∪ C =________。

7. 设A = {1, 2, 3}，B = {2, 3}，C = {1, 2}，则(A ∩ B) ∩ C =________。

8. 若A = {1, 2, 3}，B = {3, 4, 5}，C = {5, 6, 7}，则(A ∩ B) ∩ C = ________。

9. 若A = {1, 2, 3}，B = {3, 4, 5}，C = {5, 6, 7}，则(A ∪ B) ∪ C = ________。

10. 设A = {1, 2, 3}，B = {3, 4, 5}，C = {5, 6, 7}，则A × (B ∪ C) = ________。

广东工业大学2019年博士学位研究生招生考试试题考试科目（代码）名称：（2003）材料微观研究方法满分100分一、解释下列名词（每小题3分，共18分）I.X射线的波粒二相性2.电子。

T射基本公式3透射电镜分辨率4.特征X射线5.扫描隧道显微镜（STM)6.电磁透镜的景深／二、简答题（每小题7分，共28‘分）， ， ， I.简述透射电子显微镜的金属样品制作过程。

〈苦、气42.可以采用什么方法测量金属锡的熔化潜热？为什么？3.试述扫描电镜成像宁的原子序数衬度的原理及其应用。

4.给出非晶样品的电子衍射花样，井画出相应的示意图及文字说明。

三、问答题（共40分）I.何谓俄歇电子能谱仪？它有何特点。

（10分）2材料的断口分析是SEM的重要应用，试问沿晶断口，延性断口应该用SEM中何种物理信号调制成像以及这两种断口的显微形貌特征？( 10分）3.表l为测试中心部分仪器设备一览表。

请从测试中心负责人的角度，说明应如何组织该中心的工作人员对表中仪器设备进行分类并管理，才能取得最好的效果？并请选择其I书3种你所熟悉的仪器设备，说明其工作原理及用遥。

（20分）四、计算题（共14分）I.若X射线营的额定功率为2.0kW，额定电流为IOOmA，则管电压为多少？若管电流不变，管电压从零开始逐渐增大，干射线谱将出现哪些现象？(6分）2. a -Fe属于体心立方点阵类型，点阵参数a=0.2866nm。

现用Cr Ka X射线（λ＝0.2291nm）进行辐照。

试判断（110）、（220）和（111这三个晶面是否可以发生衍射？若能发生衍射，请求出相应的掠射角（8分）表l仪器设备一览表’序号｜设备名称I ｜全自动快速比表面与孔隙度分析仪2 ｜显微共焦拉曼光谱仪3 ｜紫外可见近红外分光光度计4 ｜荧光分光光度计第l页共2页。

2019年整理离散数学期末考试试卷（A卷）.doc离散数学期末考试试卷(A卷)一、判断题：（每题2分，共10分）（1）（1）（2）对任意的命题公式, 若, 则（0）（3）设是集合上的等价关系, 是由诱导的上的等价关系，则。

（1）（4）任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价。

（0）（5）设是上的关系，分别表示的对称和传递闭包，则（0）二、填空题：（每题2分，共10分）(１) 空集的幂集的幂集为（）。

(２) 写出的对偶式（）。

（３）设是我校本科生全体构成的集合，两位同学等价当且仅当他们在同一个班，则等价类的个数为（），同学小王所在的等价类为（）。

（４）设是上的关系，则满足下列性质的哪几条：自反的，对称的，传递的，反自反的，反对称的。

（）(5)写出命题公式的两种等价公式( ）。

三、用命题公式符号化下列命题（１）（２）（３），用谓词公式符号化下列命题（４）（５）（６）。

（12分）（１）（１）仅当今晚有时间，我去看电影。

（２）（２）假如上午不下雨，我去看电影，否则就在家里读书。

（3）你能通你能通过考试，除非你不复习。

（４）（４）并非发光的都是金子。

（５）（５）有些男同志，既是教练员，又是国家选手。

（６）（６）有一个数比任何数都大。

四、设，给定上的两个关系和分别是（１）（１）写出和的关系矩阵。

（２）求及（1２分）五、求的主析取范式和主合取范式。

（１０分）六、设是到的关系，是到的关系，证明：（8分）七、设是一个等价关系，设对某一个,有，证明：也是一个等价关系。

（10分）八、（1０分）用命题推理理论来论证下述推证是否有效？甲、乙、丙、丁四人参加比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获胜，如果甲不获胜，则丁不失败。

所以，如果丙获胜，则丁不失败。

九、（１０分）用谓词推理理论来论证下述推证。

任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或喜欢乘汽车，或喜欢骑自行车（可能这两种都喜欢）。

离散数学复习资料试卷习题与答案27876896离散数学总复习资料一、鸽笼原理与容斥原理1．求证边长为1的正方形中放9个点，由这些点构成的三角形中，必有一个三角形面积小于18。

证：把该正方形均分成四个相同的小正方形，则由鸽笼原理知，必有一个小正方形内存在三个点，且这三个点构成的三角形面积小于18。

# 2．对一列21n +个不同整数，任意排列，证明一定存在长为1n +的上升子序列或下降子序列。

证：设此序列为：2121,,,,,k n a a a a +，从ka 开始上升子序列最长的长度为kx ，下降子序列最长的长度为k y ，每一个k a 2(1,2,,1)k n =+都对应了(,)k kx y 。

若不存在长为1n +的上升子序列或下降子序列，那么,k k xn y n ≤≤，形如(,)k k x y 的不同点对至多有2n 个，而k a 有21n +个，则由鸽笼原理知，必有,i j a a 2(11)i j n ≤<≤+同时对应(,)i i x y =(,)j j x y ，由于i j aa ≠，若i j a a <，则i x 至少比j x 大1，若i j a a >，则iy 至少比j y 大1，这均与(,)i i x y =(,)j j x y 矛盾。

故原命题成立。

#3．求}100,,2,1{ 中不被3、4、5整除的个数。

解： 设A 表示}100,,2,1{ 中被3整除的数的集合，B 表示}100,,2,1{ 中被4整除的数的集合，C 表示}100,,2,1{ 中被5整除的数的集合，则20,25,33===C B A 6,5,8=⋂=⋂=⋂A C C B B A ， 1=⋂⋂C B A ，进而有-⋂⋂-⋂+-+⋃C⋃=+A⋂⋂BBCABABCAACBC---++=+660158252033=故有40AB⋃C⋃UBCA⋃100=60=-=-⋃即},,2,1{ 中不被3、4、5整除的个数为40。

离散数学期末复习例题讲解一、考核说明考核对象：本课程考核说明适用于国家开放大学开放教育本科电气信息类计算机科学与技术专业的学生．考核依据：本考核说明是以本课程的教学大纲（2015年3月修改）和指定的参考教材为依据制定的．本课程指定的参考教材是由胡俊、顾静相编写，国家开放大学出版社出版的《离散数学（本科）》第2版．考核方式：本课程的考核实行形成性考核和终结性考核相结合的方式．其中终结性考核采用半开卷、笔试方式，试卷满分100分．半开卷考试允许考生携带指定的一张专用A4纸（统一印制），考生可以将自己对全课程学习内容的总结归纳写在这张A4纸上带入考场，作为答卷时参考．考试时间：90分钟．试题类型及结构：单项选择题的分数占15％，填空题的分数占15％，公式翻译题的分数占12％，判断说明题的分数占14％，计算题的分数占36％；证明题的分数占8％．二、例题讲解（一）集合论1．单项选择题（1）若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )．A．{a，{ a }}∈A B．{ a }⊆AC．{2}∈A D．∅∈A答：B（2）若集合A={a，b，{1，2 }}，B={1，2}，则（）．A．B⊂ A，且B∈A B．B⊄ A，且B∉AC．B ⊂ A，但B∉A D．B∈ A，但B⊄A答：D（3）设集合A = {1, a }，则P(A) = ( )．A．{{1}, {a}} B．{∅,{1}, {a}}C．{∅,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }}答：C（4）设集合A = {1，2，3，4，5，6 }上的二元关系R ={<a , b>⎢a , b∈A , 且a +b = 8}，则R具有的性质为（）．A．对称的B．自反的C．对称和传递的D．反自反和传递的答：A（5）设集合A={1 , 2 , 3 , 4}上的二元关系R = {<1 , 1>，<2 , 2>，<2 , 3>，<4 , 4>}，S = {<1 , 1>，<2 , 2>，<2 , 3>，<3 , 2>，<4 , 4>}，则S 是R 的（ ）闭包．A ．自反B ．传递C ．对称D ．以上都不对 答：C（6）设集合A = {1 , 2 , 3 , 4 , 5}上的偏序关系的哈斯图如图1所示,若A 的子集B = {3 , 4 , 5}， 则元素3为B 的（ ）．A ．最小上界B ．最大下界C ．下界D ．以上答案都不对 图1 答：A2．填空题（1）设集合A 有n 个元素，那么A 的幂集合P (A )的元素个数为 ． 答：2n（2）设集合A ={0,1,2},B ={0,2,4},R 是A 到B 的二元关系，},,{B A y x B y A x y x R ⋂∈∈∈><=且且则R 的集合表示式为 ． 答：{<0,0>, <0,2>, <2,0>, <2,2>}（3）设集合A =｛a ,b ,c ,d ｝，A 上的二元关系R ={<a , b >, <b , a >, <b , c >, <c , d >}，则R 的自反闭包是 ．答：r (R )= {<a , b >, <b , a >, <b , c >, <c , d >}∪I A（4）设A ={1, 2, 3, 4, 5, 6, 7, 8}，R 是A 上的整除关系，B ={2, 4, 6}，则集合B 的最大元、最小元、上界、下界依次为 ． 答：无、2、无、2（5）设集合A ={1, 2},B ={a , b }，那么集合A 到B 的不同函数的个数有 ． 答：4因为：f ：{<1, a >, <2, a >}, {<1, b >, <2, b >}{<1, a >, <2, b >}, {<1, b >, <2, a >}3．如果R 1和R 2是A 上的自反关系，判断结论：“R 1-1、R 1∪R 2、R 1⋂R 2是自反的”是否成立？并说明理由． 答：结论成立．因为R 1和R 2是A 上的自反关系，即I A ⊆R 1，I A ⊆R 2． 由逆关系定义和I A ⊆R 1，得I A ⊆ R 1-1；由I A ⊆R 1，I A ⊆R 2，得I A ⊆ R 1∪R 2，I A ⊆ R 1⋂R 2．所以，R 1-1、R 1∪R 2、R 1⋂R 2是自反的．注： R 1-R 2是自反的吗？4．若偏序集<A ，R >的哈斯图如图2所示，则集合 A 的最大元为a ；最小元不存在．答：错a 是集合A 的极大元，最大元不存在． 图2 5．设集合A ＝{a ,b , { a , b }}，B ={{a }, {b }, b }，求a f5（1）B ⋂A ； （2）A －B ； （3）A ⨯B ． 解：（1）B ⋂A ={a , b , { a , b }}⋂{{a }, {b }, b }={b } （2）A －B = {a , b , { a , b }}－{{a }, {b }, b }={a , { a , b }} （3）A ⨯B ＝{a , b , { a , b }}⨯{{a }, {b }, b }＝{<a , {a }>, <a , {b }>, <a , b >，<b , {a }>, <b , {b }>, <b , b >, <{ a , b }, {a }>, <{ a , b }, {b }>, <{ a , b }, b >}6．设A ={0，1，2，3，4}，R ={<x ，y >|x ∈A ，y ∈A 且x +y <0}，S ={<x ，y >|x ∈A ，y ∈A 且x +y ≤3}，试求R ，S ，R ︒S ，R -1，S -1，r (R )，s (R )，t (R )，r (S )，s(S )，t (S )．解：R =∅，S ={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>} R ︒S =∅，R -1=∅，S -1= S ；r (R )= I A ，s (R )= ∅，t (R )= ∅；r (S )=S ∪{<2,2>，<3,3>,<4,4>}，s (S )= S ；t (S )= S ∪{<1,3>，<2,2>,<2,3>,<3,1>，<3,2>,<3,3>} 7．试证明集合等式：A ⋃ (B ⋂C )=(A ⋃B ) ⋂ (A ⋃C )．证：若x ∈A ⋃ (B ⋂C )，则x ∈A 或x ∈B ⋂C ， 即 x ∈A 或x ∈B 且 x ∈A 或x ∈C ． 即x ∈A ⋃B 且 x ∈A ⋃C ， 即 x ∈T =(A ⋃B ) ⋂ (A ⋃C )，所以A ⋃ (B ⋂C )⊆ (A ⋃B ) ⋂ (A ⋃C )．反之，若x ∈(A ⋃B ) ⋂ (A ⋃C )，则x ∈A ⋃B 且 x ∈A ⋃C ， 即x ∈A 或x ∈B 且 x ∈A 或x ∈C ，即x ∈A 或x ∈B ⋂C ， 即x ∈A ⋃ (B ⋂C )，所以(A ⋃B ) ⋂ (A ⋃C )⊆ A ⋃ (B ⋂C )． 因此．A ⋃ (B ⋂C )=(A ⋃B ) ⋂ (A ⋃C )． 8．设R 是集合A 上的对称关系和传递关系，试证明：若对∀a ∈A ，∃b ∈A ，使得<a , b >∈R ，则R 是等价关系．证明：已知R 是对称关系和传递关系，只需证明R 是自反关系． ∀a ∈A ，∃b ∈A ，使得<a , b >∈R ，因为R 是对称的，故<b , a >∈R ； 又R 是传递的，即当<a , b >∈R ，<b , a >∈R ⇒<a , a >∈R ；由元素a 的任意性，知R 是自反的． 所以，R 是等价关系．（二）图论1．单项选择题（1）设图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101010010000011100000100则G 的边数为( )．A ．5B ．6C ．3D ．4 答：D（2）设图G ＝<V , E >，则下列结论成立的是 ( )．A ．deg(V )=2∣E ∣B ．deg(V )=∣E ∣C ．E v Vv 2)deg(=∑∈ D ．E v Vv =∑∈)deg(答：C（3）设有向图（a ）、（b ）、（c ）与（d ）如图3所示，则下列结论成立的是 ( )．图3A ．（a ）是强连通的B ．（b ）是强连通的C ．（c ）是强连通的D ．（d ）是强连通的答：A（4）给定无向图G 如图4所示，下面给出的结点集子集中，不是点割集的为（ ）． A ．{b , d } B ．{d }C ．{a , c }D ．{g , e } 答：A 图4（5）图G 如图5所示，以下说法正确的是( )． A ．{(a , d )}是割边B ．{(a , d )}是边割集C ．{(d , e )}是边割集D ．{(a, d ) ,(a, c )}是边割集答：C 图5 （6）设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )．A ．e －v ＋2B ．v ＋e －2C ．e －v －2D ．e ＋v ＋2 答：A2．填空题（1）已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 ．答：15 （1⨯1+2⨯2+3⨯3+4⨯4）/2（2）设无向图G ＝<V ,E >是汉密尔顿图，则V 的任意非空子集V 1，都有 ≤∣V 1∣． 答：W （G - V 1）（3）设无向图G 为欧拉图，则图G 连通且 ． 答：每个结点的度数为偶数（4）设图G =<V ,E >，其中|V |=n ,|E |=m ．则图G 是树当且仅当G 是连通的，且m = ． 答：n -1（5）连通无向图G 有6个顶点9条边，从G 中删去 条边才有可能得到G 的一棵生成树T ． 答：4οο οο (a )οο οο (b ) οοοο (c )οοοο(d )a gb d fc e οο ο οο οο ο a ο οο ο ο b c f d e（6）给定一个序列集合{1，01，10，11，001，000}，若去掉其中的元素 ，则该序列集合构成前缀码．答：1 3．给定图G （如图6所示）: （1）试判断它们是否为欧拉图？并说明理由． （2）若是欧拉图，请写出一条欧拉回路．答：（1）图G 是欧拉图，因为图G 是连通图且每个结点的度数是偶数．（2）欧拉回路为： v 1 e 1 v 2 e 2 v 3 e 3 v 4 e 5v 5 e 7 v 2 e 8v 6 e 6 v 4 e 4v 1 注意：回路是不惟一4．试判断“设G 是一个有5个结点、10条边的连通图，则G 为平面图”是否正确，为什么？答：错误．因为它不满足定理4.3.3，即“设G 是一个有v 个结点e 条边的连通简单平面图，若v ≥3，则e ≤3v -6．”5．设图G =<V ，E >，其中V ={a 1, a 2, a 3, a 4, a 5},E ={(a 1, a 2)，(a 2, a 4)，(a 3, a 1)，(a 4, a 5)，(a 5, a 2)}（1）试给出G 的图形表示； （2）求G 的邻接矩阵； （3）求出每个结点的度数； （4）画出其补图的图形． 解：（1）图G 是无向图，图形如图7所示：图7 （2）图G 的邻接矩阵如下：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=0101010010000011100100110)(G A（3）结点a 1, a 2, a 3, a 4, a 5的度数分别为：2，3，1，2，2． （4）图G 的补图的如图8所示：图86．图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 ),ο οο ο οa 1a 2 a 3a 4a 5v 1 v 2 v 3v 4 v 5v 6 e 1 e 2e 3 e 4 e 5 e 6e 7 e 8 οο ο ο ο ο图6 ο ο ο ο οa 1a 2 a 3a 4 a 5οο ο ο οa 1 a 2 a 3a 4a 5(d , f ), (e , f ) }，对应边的权值依次为5，2，1，2，6，1，9，3及8．（1）画出G 的图形； （2）写出G 的邻接矩阵；（3）求出G 权最小的生成树及其权值． 解：（1）G 的图形如图9所示：（2）邻接矩阵：⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡011000101111110010010001011001010110 图9（3）粗线表示最小的生成树（见图10）：最小的生成树的权为：1+1+5+2+3=12． 图107．设有一组权为2,3,6,9,13,15,试 （1）画出相应的最优二叉树； （2）计算它们的权值．解：最优二叉树如图11所示：图11 权值： 2⨯4+3⨯4+6⨯3+9⨯2+13⨯2+15⨯2 =8+12+18+18+26+30 =1128．设G 是一个n 阶无向简单图，n 是大于等于2的奇数．证明图G 与它的补图G 中的奇数度顶点个数相等．证明：设,G V E =<>，,G V E '=<>．则E '是由n 阶无向完全图n K 的边删去E 所得到的．所以对于任意结点u V ∈，u 在G 和G 中的度数之和等于u 在n K 中的度数．由于n 是大于等于2的奇数，从而n K 的每个结点都是偶数度的（ 1 (2)n -≥度），于是若u V ∈在G 中是奇数度结点，则它在G 中也是奇数度结点．故图G 与它的补图G 中的奇数度结点个数相等．οο ο ο οc a b e dοf1 5 22 61 9 38 ο ο ο ο οc a b ed οf 15 22 61 938 οοο οο ο ο ο ο32 9 135 6 1115 20 ο ο 48289．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加2k条边才能使其成为欧拉图．证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k 是偶数． 又根据定理4.1.1的推论，图G 是欧拉图的充分必要条件是图G 不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G 的所有结点的度数变为偶数，成为欧拉图．故最少要加2k条边到图G 才能使其成为欧拉图．（三）数理逻辑1．单项选择题（1） 下列命题公式是等价公式的为( )．A ．⌝P ∧⌝Q ⇔P ∨QB ．A →(⌝B →A ) ⇔⌝A →(A →B )C ．Q →(P ∨Q ⇔⌝Q ∧(P ∨Q )D ．⌝A ∨(A ∧B ) ⇔B 答：B 因为A →(⌝B →A ) ⇔ A →(B ∨A ) ⇔⌝A ∨(B ∨A ) ⇔ A ∨ (⌝A ∨B ) ⇔ A ∨ (A →B )⇔⌝A →(A →B )（2）下列公式 ( )为重言式．A ．⌝(⌝P ∨(P ∧Q )) ↔QB ．(B →(A ∨B )) ↔(⌝A ∧(A ∨B ))C ．A ∧⌝B ↔A ∨BD ．(P →(⌝Q →P ))↔(⌝P →(P →Q )) 答：D 因为(P →(⌝Q →P ))⇔⌝P ∨(Q ∨P )) ⇔1 (⌝P →(P →Q )) ⇔P ∨(⌝P ∨Q )) ⇔1 （3）命题公式⌝ (P →Q )的主析取范式是( )． A ．Q P ⌝∧ B Q P ∧⌝ C ．Q P ∨⌝ D ．Q P ⌝∨答：A 因为⌝ (P →Q ) ⇔⌝ (⌝P ∨Q ) ⇔P ∧⌝Q（4）设C (x ): x 是国家级运动员，G (x ): x 是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为 ( )A ．))()((x G x C x ⌝∧⌝∀B ．))()((x G xC x ⌝→⌝∀C ．))()((x G x C x ⌝→⌝∃D ．))()((x G x C x ⌝∧⌝∃答：D（5）表达式))(),(())(),((z zQ y x R y z Q y x P x ∀→∃∧∨∀中x ∀的辖域是( )． A ．P (x , y ) B ．P (x , y )∨Q (z ) C ．R (x , y ) D ．P (x , y )∧R (x , y ) 答：B2．填空题（1）命题公式()P Q P →∨的真值是 ． 答：1 因为()P Q P →∨⇔⌝P ∨(Q ∨ P ) ⇔1（2）含有三个命题变项P ，Q ，R 的命题公式P ∧Q 的主析取范式是 ． 答：(P ∧Q ∧⌝R )∨( P ∧Q ∧R )因为P ∧Q ⇔ P ∧Q ∧(⌝R ∨R ) ⇔(P ∧Q ∧⌝R )∨( P ∧Q ∧R )（3）设个体域D ＝{1,2},那么谓词公式)()(y yB x xA ∀∨∃消去量词后的等值式为 ． 答：(A (1) ∨A (2))∨(B (1) ∧B (2))（5）谓词命题公式(∀x )(P (x )→Q (x )∨R (x ，y ))中的约束变元为 ． 答：x3．请将语句翻译成命题公式： （1）今天不是天晴．（2）你去听课，他也去听课．（3）如果天下雪，则我明天就不去市里． （4）尽管他参加了考试，但他没有通过考试．解：（1）设P ：今天是天晴； 命题公式为： ⌝ P ．（2）设P ：你去听课，Q ：他去听课：命题公式为：P ∧Q ．（3）设P ：天下雪，Q ：我明天去市里； 命题公式为：P →⌝Q ．（4）设P ：他参加了考试，Q ：他没有通过考试； 命题公式为：P ∧⌝ Q ．4．请将语句翻译成谓词公式： （1）所有人都不去上课． （2）有人不去工作． 解：（1）设P (x )：x 是人，Q (x )：x 去上课．谓词公式为： (∀x )(P (x )→ ┐Q (x ))．（2）设P (x )：x 是人，Q (x )：x 去工作，谓词公式为： (∃x )(P (x) ∧┐Q (x ))． 5．判断下列各题正误，并说明理由．（1）公式((Q ∧⌝R )→P )∧(⌝P →Q ∨R )↔P ∨R 为永真式．（2）求命题公式(P ∧Q )∧(⌝P ∨⌝R )的真值表，并判断它的类型. 解：（1）该公式是永真式．因为 R P R Q P P R Q ∨↔∨→⌝∧→⌝∧)())((R P R Q P P R Q ∨↔∨∨∧∨∨⌝⇔)()( R P Q Q R P ∨↔∧⌝∨∨⇔)( 1⇔（2）6．判断下列各题正误，并说明理由．（1）公式))(),(()(x xP y x yG x xP ∀→∃→∀是逻辑有效式(永真式)．（2）下面的推理是否正确，请给予说明． ① P （a ） P ② （∀x ）P （x ） US ① 解：（1）该公式是永真式．因为 ))(),(()(x xP y x yG x xP ∀→∃→∀⇔))(),(()(x xP y x yG x xP ∀∨⌝∃∨⌝∀1)(),()(⇔∀∨⌝∃∨⌝∀⇔x xP y x yG x xP（2）错误．② 应为（∀x ）P （x ） UG ① 全称指定规则与全称推广规则不能混淆．7．求公式R Q P →∧)(的析取、合取、主合取\主合取范式． 解：R Q P R Q P ∨∧⌝⇔→∧)()(R Q P ∨⌝∨⌝⇔)(R Q P ∨⌝∨⌝⇔ （析取、合取、主合取范式）⇔(┐P ∧(┐Q ∨Q )∧(┐R ∨R ))∨((┐P ∨P )∧┐Q ∧(┐R ∨R )) ∨((┐P ∨P )∧(┐Q ∨Q )∧R )⇔(┐P ∧┐Q ∧┐R )∨(┐P ∧┐Q ∧R )∨(┐P ∧Q ∧┐R )∨(┐P ∧Q ∧R )∨(P ∧┐Q ∧┐R )∨(P ∧┐Q ∧R )∨(P ∧Q ∧R )（主析取范式）8．用列真值表的方法求命题公式R Q P →→)(的主析取范式．解：列真值表取真值为1的项，所求主析取范式为：(┐P ∧┐Q ∧R )∨(┐P ∧Q ∧R )∨(P ∧┐Q ∧┐R )∨(P ∧┐Q ∧R ) ∨(P ∧Q ∧R )9．试求谓词公式),()),(),()((y x B y x yG y x xH x S x ∨∃→∃∧∀中，∀x ，∃x ，∃y 的辖域，试问G (x , y )和B (x , y )中x ，y 是自由变元，还是约束变元？解：∀x 的辖域：)),(),()((y x yG y x xH x S ∃→∃∧ ∃x 的辖域：H (x ,y )∃y 的辖域：G (x ,y ) G (x , y )中的x ，y 是约束变量，B (x , y )中的x , y 是自由变量. 10．证明命题公式(P →(Q ∨⌝R ))∧⌝P ∧Q 与⌝（P ∨⌝Q ）等价． 证：(P →(Q ∨⌝R ))∧⌝P ∧Q ⇔(⌝P ∨(Q ∨⌝R ))∧⌝P ∧Q ⇔(⌝P ∨Q ∨⌝R )∧⌝P ∧Q⇔(⌝P ∧⌝P ∧Q )∨(Q ∧⌝P ∧Q )∨(⌝R ∧⌝P ∧Q ) ⇔(⌝P ∧Q )∨(⌝P ∧Q )∨(⌝P ∧Q ∧⌝R ) ⇔⌝P ∧Q （吸收律） ⇔⌝(P ∨⌝Q ) （摩根律）9．构造推理证明))()(()()(x Q x P x x xQ x xP →∀⇒∀→∃． 分析：前提：)()(x xQ x xP ∀→∃．结论：))()((x Q x P x →∀证：(1) )()(x xQ x xP ∀→∃ P(2) )()(x xQ x xP ∀∨⌝∃ T (1)E(3) )()(x xQ x P x ∀∨⌝∀ T (2) E (量词与否定的关系) (4) ))()((x Q x P x ∨⌝∀(5) ))()((x Q x P x →∀ T (4) E上面这些例题供大家复习参考．。