搜索
严禁用于商业用途1/34第二版前言：加入2010年试题。并将有把握的2009年的试题答案予以补充。2010年答案由于不能确保正确性，故不予给出。学习离散数学，正如冷城学长所言，入门容易，深入难。希望大家在学习的过程中，能够静下心来，耐住性子认真复习。对于一些特别复杂，刁钻的问题就不要深究了。掌握好基础概念、基本的证明是最关键的。特别感谢冷城学长提供原始文档。希望大家能够南大CS金榜题名！Zyszys32010年8月19日严禁用于商业用途2/34前言本文收集了1997、1998年和2001年到2007年和2009年南京大学研究生入学考试科目《离散数学》的试卷以及相应试卷答案。2008年试题未找到，1997年到2007年试题给出本人所做的答案，因为离散数学难度大，很多答案问过原来教我们离散数学的老师，老师也只能给出部分答案，所以不能保证全部答案的正确性，2009年试题答案未与同学核对，同样不能确保答案正确性，故不在此给出。部分答案有更优解，需要同学们自己开发。南京大学从2005年开始把《离散数学》作为复试科目，满分为80分，与《编译原理》同为笔试项目，总分150分。主要考试部分为数理逻辑、集合论、代数结构和图论。推荐复习时候以南大课件为主，课件在网上可以查到，有宋方敏和陈道旭两种版本。通过真题发现，很多题目都是课件上证明题的原题，而且考试重点与课件也吻合。离散数学特点就是难度大，上手容易深入难。代数系统和图论两章难度非常大，所以复习好离散数学要有一定的耐心和钻研精神。相信天下无难事，只怕有心人。祝愿所有有志考南大CS的同学金榜提名。冷城2009年7月严禁用于商业用途3/341996年一．试证：a.自然数集为无限集中势最小者。b.不存在最大的势。二．任给无向图G，其联结矩阵为A=[aij]，（即若存在边(vi,vj)则aij=1否则aij=0）试定义矩阵运算并给出关于A的矩阵的表达式，B=E(A)，使得矩阵B=[bij]满足：对于G中的任意两结点vi,vj若其间存在通路则bij=1否则bij=0。三．任给无向图G，对G中的边赋予方向得图G’，试证：存在G满足对任意两点v1,v2∈G’，不论从哪点为始终端均有有向通路到达另一点的充分条件是原图G连通且不存在割边。四．试分别用永真推理过程和假设推理过程证明：(α→(β→γ))→((α∧β)→γ)五．试给出下式的析合范式和合析范式：(p→q)→(p→r)六．试用谓词演算公式来描述一个代数系统(A,*)为一个群。七．任给一个集合S，S到自身的一一对应的映射成为S上的置换，试证：S上置换的全体关于置换的复合运算构成群。严禁用于商业用途4/341996年答案一．证明：a.∀无限集A，将A中元素按照某种次序（任意规则）排序，以0,1,2,……,n来表示A中某元素排列的位置，所以存在自然数集N到集合A的单射，∴N⋖=A。得证。b.∀无限集A，∃元素α∉A，设B=A∪{α}，则A到B有单射关系”=”，∴α∉A，∴A≠B。∴A⋖B，∴∃比A势更大的集合。因为对任一集合均有比其更大的势的集合。得证。二．B=E(An)，其中An=An=1时运算定义为：两矩阵相乘An–1∘An1时E为An运算收敛后若元素不为0，则将其置为1三．证明：1.对于G中任一条边，先证其必在一个圈中：设存在边e，e不在一个圈中，e的两个断点记为u，v。若去掉边e，∵u,v不在一个圈中，∴u，v间无通路，即P(G–e)P(G)。∴e为桥，与题设矛盾。得证。2.再证不存在桥的连通图G赋予边以方向后，G’为强连通图。设不存在这样的圈，则存在对两个顶点u,v没有经过它们的圈。∴G是连通的，∴u到v有通路，设通路上的点为u,v1,v2,……,vn，v对于与u,v相关联边，必有圈，v1,v2间必有圈，则可将两圈合并，得到必有u到v2的圈，同理可得u到v3的圈，以此类推可得到u到v的圈，与假设不成立。∴必存在将所有顶点连接的圈，将其以逆时针赋予方向后得经过每个点至少一次的回路，∴G为强连通图。得证。四．证明：永真推理：(α→(β→γ))→((α∧β)→γ)⟺൫α→൫﹁β∨γ൯൯→(﹁(α∧β)∨γ)⟺൫﹁α∨﹁β∨γ൯→(﹁α∨﹁β∨γ)⟺1假设推理：前提引入α→(β→γ)结论(α∧β)→γ结论否定引入﹁((α∧β)→γ)(α→(β→γ))∧﹁((α∧β)→γ)⟺൫﹁α∨﹁β∨γ൯∧(﹁α∨﹁β∨γ)⟺0五．(p→q)→(p→r)⟺(﹁p∨q)→(﹁p∨r)⟺﹁(﹁p∨q)∨(﹁p∨r)⟺(p∨﹁q)∨﹁p∨r⟺((p∨﹁p)∧(﹁q∨﹁p)∨r⟺﹁p∨﹁q∨r⟺M6严禁用于商业用途5/34⟺m0∨m1∨m2∨m3∨m4∨m5∨m7六．群的定义：(1)、(A,*)是代数系统；(2)、*为二元运算；(3)、存在关于*的单位元；(4)、∀a∈A，∃a–1∈A。P(x,y)：x与y构成代数系统；H(x,y)：x∈y；F(x)：x是二元运算；I(x,y)：x是y的逆；R(x,y)：x是关系y的单位元。P(A,∗)∧F(∗)∧∃eR(e,∗)∧∀a(H(a,A)→∃b(I(b,a)∧H(b,A)))七．证明：【置换群问题，答案略】严禁用于商业用途6/341997年一．R1、R2分别是集合S、T上的关系，定义S×T上的关系R3：s1,t1R3s2,t2当且仅当s1R1s2，t1R2t2。证明：(1)若R1、R2为等价关系，则R3为等价关系。(2)若R1、R2为偏序，则R3也是偏序。二．证明：S是无限集当且仅当存在S的真子集S’：满足S与S’等势。三．图G=(VG,EG)，R1是定点集VG上的相邻关系，即对任意u,v∈VG，uR1v当且仅当u,v∈EG。R2是VG上的可达关系，即uR2v当且仅当在G中存在vu-通路。证明R2是R1的传递闭包。四．(1)T是树，e是T中任意一条边，证明：T’=T-{e}是连通分支数为2的森林。(2)图G=(VG,EG)，|VG|=n，|EG|=m，G连通且恰好含一个回路的充分必要条件是下列三项中的任意两项成立。(i)G连通，(ii)G恰好含一个回路，(iii)m=n。五．(1)若G是奇数阶有限群，证明对任意a∈G，方程x2=a有解。(2)若在有限群G中，对任意a，x2=a有唯一解，则|G|必为奇数。六．Zm、Zn分别是m、n阶剩余加群。定义代数系统(Zm×Zn,*)：对任意x1,x2∈Zm，y1,y2∈Zn，(x1,y1)*(x2,y2)=(x1+mx2,y1+ny2)。证明：若m、n互质，Zm×Zn是循环群，生成元为(1,1)。证明：（1）封闭性（2）可结合性（3）幺元（0,0）（4）逆元显然，对于任意（a,b）∈Zm×Zn,有（a-1,b-1）综上所述，对于任意的m、n，（Zm×Zn,*）都是群。显然，若m与n互质，Zm×Zn是循环群，生成元为(1,1)。七．试讨论在一给定公理系统的公理系统集合中添加或删除元素，对系统的性质可能产生什么影响。（提示：在添加元素的情况下，要考虑所加公式在原系统中是否可证。）八．给下列命题：(1)参加展览的人中，每个N大学的男生都背K牌书包。(2)参观展览的人中，每个背K牌书宝的都是来自N大学的男生。(3)每个背K牌书包的N大学男生都参观了该展览。写出相关的谓词逻辑表达式，证明：(1)(2)不能推出(3)。严禁用于商业用途7/341997年答案一．证明：1.①∵R1与R2都是等价关系，∴∀S1∈S∴∀t1∈T，有S1R1S1与t1R1t1。∴∀S1,t1∈S×t。有S1,t1R3S1,t1，∴R3满足自反性。②对于∀S1R1S2，必有S2R1S1，同样∀t1R2t2必有t2R2t1。∴S1,t1R3S2,t2⇒S1R1S2∧t1R2t2⇒S2R1S1∧t2R2t1⇒S2,t2R3S1,t1∴R3满足对称性。③∀S1,t1R3S2,t2∧S2,t2R3S3,t3⟺(S1R1S2∧t1R2t2)∧(S2R1S3∧t2R2t3)⟺(S1R1S2∧S2R1S3)∧(t1R2t2∧t2R2t3)⟺S1R1S3∧t1R2t2⟺S1,t1R3S3,t3∴R3满足传递性。2.自反性与传递性同1。证明反对称性：∀S1,t1R3S2,t2∧S1,t1≠S2,t2⟹(S1R1S2)∧(t1R2t2)∧S1≠S2∧t1≠t2⟹(S2R1S1)∧(t2R2t1)∧S1≠S2∧t1≠t2⟹S2,t2R3S1,t1∧S1,t1≠S2,t2∴R3满足反对称性，∴R3也是偏序关系。二．证明：1.充分性：S≈S，将S中去掉一个元素x，并将S→S的映射从元素x开始指向原来的下一个元素。∵S是无限集，S’也是无限集，∴S到S’仍然存在双射，∴∃S'⊂S∧S≈S'。2.必要性：∴S'⊂S∧S≈S'若S不是无限集，则S’中必比S中少元素，则不可能有S’→S的单射，这与S≈S'矛盾，∴S必是无限集。三．证明：1.对于任意ݑ,ݒ,ݒ,ݎ⊂R’，u到v有通路，v到r有通路，则u到r必有通路，∴ݑ,ݒ∈ܴ'，∴R'是传递的。2.∀u,v∈Ea，则u到v必有通路，∴ݑ,ݒ∈ܴ'，∴R⊆R'。3.对∀ݑ,ݒ∈ܴ'，u与v必是n条边关联的通路，即有ݑ,݊1∈ܴ、ݑ,݊2∈ܴ……݊݅,ݒ∈R，∴对于包含R的传递关系R’’，必有ݑ,ݒ∈ܴ''，∴R'⊆R''。四．证明：1.∵树中每条边都是桥，∴去掉一条边后连通分支数加1，∴T’=T–{e}为连通分支数为2的森林。2.(i)，(ii)成立，则结果显然成立。(i)，(iii)成立，则对于G中的某一生成树，n=m+1，∵n=m，∴对于这个生成树任加一条边，根据树的性质可得生成的图仅含一个回路，得证。(ii)，(iii)成立，∵G中恰含一条回路，则去掉回路一条边得G中无回路，此时n=m+1。对于G各个连通分量，均有vi=ei+1，∴v=v1+v2+…+vn’=e1+e2+…+en+n’=e+n’。∵n=m+1，∴nᇱ=1。∴G中只有一个连通分量，即G是连通的。五．1.证明：因为G的阶为奇数，故无偶数因子，严禁用于商业用途8/34所以任意一个元素a的阶也是奇数，不妨设为2k+1。即有：a2k+1=e（幺元）而且aj≠e.因此方程x2=a有解如下：x=ak+1事实上（ak+1)2=a2k+1a=ea=a2.证明：∀x，x2=a有唯一解，有e°e=e。∴a∈G且a≠e，有a°a-1=e且a≠a-1。∴a与a-1成对出现。∴非e元素有偶数个，∴元素数为奇，即|G|必为奇数。六．证明：1.∵代数系统Zm×Zn,*中*是二元运算关系，∀x1,x2,x3∈Zm，y1,y2,y3∈Zn。x1,y1*x2,y2*x3,y3=x1+mx2+mx3,y1+my2+my3=x1,y1*(x2,y2*x3,y3)满足结合律。∵x,y*0,0=x,y，0,0*x,y=x,y，∴存在幺元0,0。∴Zm×Zn是群。2.设x,y=1,1t证明x+1,y=1,1t1，x,y+1=1,1t2(t,t1,t2为整数)。根据一次同余方程定理，∵gcd(n,m)|1，∴∃α使nα≡m(α为整数)。∴∃t1=t+nα，∴1,1t+nα=x+1,y。同理可得1,1t+mα=x,y+1∴∀ݔ,ݕ∈Zm×Zn均有x,y=1,1t存在，即Zm×Zn=1,1，1,1是生成元。七．【略】八．设F(x)，x参观了展览。(1)∀x(F(x)∧N(x)∧M(x)→K(x))N(x)，x来自N大学。(2)∀x(F(x)∧K(x)→N(x)∧M(x))M(x)，x是男生。(3)∀x(K(x)∧N(x)∧M(x)→F(x))K(x)，x背k牌书包。前提：∀x(F(x)∧N(x)∧M(x)→K(x))；∀x(F(x)∧K(x)→N(x)∧M(x))结论：∀x(K(x)∧N(x)∧M(x)→F(x))∀x(F(x)∧N