中大信科院计算机复试专业课离散数学.pdfVIP

version2.0 version2.0 中大信科院复试离散数学真题vveerrssiioonn22..00 2013 2013 1.用等值演算法证明(¬p∧(¬q∧r))∨(p∧r)∨(q∧r)⇔ r 2.判断(∀xF(x)→ ∀xG(x))→(∃xF(x)→ ∃xG(x))是否为真命题,若为真请证明,假的话请举反例 3.求下面等式成立的充分必要条件 �A-B=B-A,�P(A∪B)=P(A)∪P(B) 4考查容斥原理,求三个都选的人数. 5.给出一个有向图,求邻接矩阵,然后用warshall 法求可达矩阵 2012 2012 1.求析取范式成真赋值。（这一题似乎是书上的课后习题，我感觉做过。不过也没有关系，比较简单） 2.求前束范式（这是历年都没有考过的，不过很简单，似乎是书上习题，只要看了书）。 3.给了两个等式（A-B）*(C-D)=(A*B)-(C*D).第二个等式不记得了。求它们成立的充分条件并说明理由。这一 题完全不知道做。随便写了一下。 4.是关系闭包（对称闭包，传递闭包）的等式证明。具体不记得了，这一题也是以前没有考过的。我只知道第 一问，证明对称闭包的等式，我觉得这一问大家都能做出来。 5.图的证明。这是书上的课后习题。很简单。证明一个图含有两个奇度顶点一定连通。（用握手定理，反证法就 能证出了） 整个离散，还是比较难的。因此，大家都差不多，都是３０几分。 2011 2011 1 求((p V q) → r) → q的主析取范式，主合取范式，真值表 2 定义了循环关系：对于A上的关系R，若对任意x,y∈R 且y,z∈R，则z, x∈R。然后证明：R 是自反 和循环关系当且仅当R 是等价关系。 3具体题目忘了，考的是容斥原理。和书本上的例题很像，不过求的是三个都选的人数。 4 最短路径，会例题就会这题 5 书上的原题，图论那节最后一题。 2010 2010 1.求1--300间（含1、300） 可被3 且5 且7 整除的数的个数 可被3 且5，但不能被7整除的个数 不能被3 且5 且7 整除的数的个数 （还有两问也就是这种类型的问题，300/最小公倍数，画文氏图求解，书上有例题，连续两年考了这种题） 2.给出一个有向图，要你求邻接矩阵；长度为3的通路、回路数；可达矩阵（书上的例题几乎是一摸一样） -1 -1 3.证F。（G。H）=(F。G)。H，证（F。G） =G-1。F （书上定理证明） 4.画一个极简单的无向图的生成树（他只说了画生成树，但我觉得还是把所有非同构的画出来保险，我就只画 了一个，交卷才反应过来，貌似扣分了） 5.证明一个n 阶图有n-1 条边，那么它至少有一个节点度数大于1。（反证法，握手定理，非常简单，貌似是课 后的一道习题） 2009 2009 1.通过文示图来求解 2.画关系图 3.写出生成树 4.图的矩阵(可达矩阵,通路,回路数) 5.有关图的证明. 这五道题比较简单,只要认真以前复试过的题目以及课本上基本的例题都会做.这里我就不去回忆具体的题目啦 2008 2008 1. 1. 11..在1 到300 间(不含)整数集合中，求满足以下条件的数的个数: 1)、能被3 5 和7 整除; 2)、不能被3 5 和7 整除; 3)、(记不得了，但基本上会做前两个，后面都会做) 2.f:A→B; g:B→P(A) g(b)={x| x∈A ∧ f(x)=记不住了}若f 是满射，证g 是单射.(了解题型即可) 3.给定一图，求其邻接矩阵，可达矩阵，由邻接矩阵求通路数。 2007 2007 1.证明等价关系 2.哈夫曼树 2006 2006 3道证明题，比较难，具体题目实在想不起来了。内容大概是关于群、半群、格、范式等。 2005 2005 1.一阶逻辑推理问题。 2.对于集合A={1，2，3} 1)构造关于A 的关系R，使得R 不是反自反，不是自反，不是反对称，不是对称，不是传递的，并说明原 因。（课后题） 2)