2010年同等学力申硕计算机综合试题解析--数学基础

声明：本套试题的填空题和计算题第二题的第二种解法解析是本人自己做的，其他的答案来自原题评分标准，如发现答案有错误或者不够准确请及时给我留言，如需转载请表明出处。感谢所有提出意见和建议，以及帮助过我的朋友。如果觉得还行，欢迎点赞转发，谢谢！

第一部分数学基础课程

（共40 分）

一、用逻辑符号表达下列语句（每小题2 分，共4 分）

1. 猫必捕鼠。

解：设 C(x): x 是猫；M( y): y 是老鼠；S(x, y)：x 捕 y。原句可形式化：

$\forall x \forall y (C(x)∧M(y) \rightarrow S(x, y))$

评分说明：设的符号形式可以不同，但必须设 3 项。如缺少设置或逻辑符号使用有错

误则只给 1 分（如 S(x, y)之前用的是∧）。

2. 任意两个不同的实数之间必存在另一个实数。

解：设 R(x)：x 是实数，则原句可形式化为：

（1） $\forall x \forall y (R(x)∧R(y)∧x≠y \rightarrow \exists z(R(z)∧(x<z<y∨y<z< x)))$

或设 R(x)：x 是实数；N(x, y)：x≠y；G(x, z, y): x<z<y, 则原句可形式化为：

（2） $\forall x \forall y (R(x)∧R(y)∧N(x, y) \rightarrow \exists z(R(z)∧(G(x, z, y)∨G(y, z, x))))$

评分说明：形式化结果不能缺项，如蕴含词前面的部分书写正确可给 1 分，后面的部

分，析取词两端的内容必须完整，否则需扣 1 分。

二、填空题（每小题2 分，共6 分）

1．设 $K_n$ 是个 n 顶点(n 为正整数)的完全图，对 $K_n$ 的每条边进行红、蓝两种颜色任意着色，都至少存在一个红色边三角形或蓝色边三角形，则最小的 n 是 ( 6 ) 。

解析：考的是鸽巢原理，假设 $v_1，v_2，v_3,...,v_n$ 个顶点，每个顶点都有n-1条边，设每个点到其他任意点的边涂成红色或蓝色即有n-1边，根据鸽巢原理，当n=6时，n-1=5才能保证与 $v_1$ 关联的边中有3条边同色，不妨设这三条边为 $(v_1,v_2),(v_1,v_3),(v_1,v_4)$ 若这三条边为红色，当 $v_2,v_3,v_4$ 之间有一条是红色，比方 $(v_2,v_3)$ , $v_1,v_2,v_3$ 构成一个红色三角形，当 $v_2,v_3,v_4$ 没有红边，则 $v_2,v_3,v_4$ 构成一个蓝色三角形。得证。

2. $(_{0}^n )-(_{1}^n )+(_{2}^n )-(_{3}^n )+...+(-1)^n (_{n}^n ) =$ （0） 。其中 $(_{0}^n )$ 表示从n 个不同元素中取k 个的组合数。

解析：这个考的是牛顿二项式的展开式， $(1-x)^n = \sum_{k=0}^n (-1)^k(_{k}^n) x^k$ ,当x=1时，就得到题干了， $(_{0}^n )-(_{1}^n )+(_{2}^n )-(_{3}^n )+...+(-1)^n (_{n}^n ) = 0$

3．设G 是有n 个顶点的简单图，除其中一个顶点外，其余顶点的度（次）均为奇数。在G 的补图中有 （ n-1 ） 个度为奇数的顶点。

解析：简单图的补图合起来是一个完全图，完全图的总度数为偶数，题干中简单图中奇度点的个数为n-1，因此相对应的补图的奇度点的个数也为n-1。

三、计算题（共16 分）

1．（3 分）计算∀xP(x) → ∃yP(y) 的否定式。 否定式中仅可使用{¬,∨,∧}中的联结词，且否定词“¬”不能出现在量词的前面。

解：记原式为 $A = \forall xP(x) \rightarrow \exists yP(y)$ 。题目要求计算┐A。

为书写简便，设 $B = \forall xP(x)$ ， $C = \exists yP(y)$ （1）

则原式可化为 $A = (B\rightarrow C)$ 。

$┐A$

$= ┐(B\rightarrow C)$

$= ┐( ┐B∨C)$

$= B∧┐C$

$= \forall xP(x)∧┐\exists yP(y)$ 代入式（1）得到此步的结果给2分

$= \forall xP(x)∧\forall y ┐ P(y)$ （根据题目要求将量词前面的否定词挪到后面）

故 $\forall xP(x) \rightarrow \exists yP(y)$ 的否定式为 $\forall xP(x)∧\forall y ┐ P(y)$ 。

2．（5 分）求方程 $x_1 + x_2 + x_3 + x_4 = 10$ 正整数解的个数。

解：令 $y_1 = x_1 -1, y_2 = x_2 -1, y_3=x_3 -1, y_4 = x_4 -1$ ，则此问题等价于求满足方程 $y_1 + y_2 + y_3 + y_4 = 6$ 的非负整数解的个数 ------------------3 分

而 $y_1 + y_2 + y_3 + y_4 = 6$ 非负整数解的个数等价于从 6＋4－1 个中取出 3 个的组合数，即 $C_{(6+4-1,3)} = C_{(9,3)} = (9*8*7)/(2*3) = 84$ ------------------2 分

评分说明：如果算出非负整数解的个数 $C_{(10+4-1,3)} = C_{(13,3)} = (13*12*11)/(2*3) = 286$ ,给3分。

这题建议使用母函数计算：要求正整数数，即0是整数，但并不是正整数。正整数，为大于0的整数，也是正数与整数的交集.这母函数可以表示为：

$G(x) = (x+x^2+x^3 + ...)^4 =x^4{ (\frac{1}{1-x}) }^4 =x^4 * (1-x)^{-4}=x^4 * \sum\nolimits_{k=0}^ ∞ C_{(k+4-1,k)}x^k$

则要求满足4+k = 10，k = 6，此时系数为 $C_{(6+4-1,6)} = C_{(9,3)} = 84$

3．（8 分）设 n 个人的包事先存放在会议寄存处，且寄存处只存有这 n 个包。会后，这 n 个人随机进入这间黑暗的寄存处，每人随意取回一个包。试问所有人都拿错包的概率是多少？

解：求所有人都拿错包的方法数 $D_n$ 等价于求 n个数1,2,3,...,n 的错排数目问题 ----2 分

设 $A_i (i = 1,2,3,...,n)$ 是第 i 个人拿回自己包的结果集合，则取回包的总方法数为 $n!$ ,

$|A_i| = (n-1)! ,|A_i \cap A_j| =(n-2)!, ,|A_{i_1} \cap A_{i_2} \cap A_{i_3} \cap ... \cap A_{i_k} | =(n-k)!$ 利用容斥原理， $D_n = | \frac{}{ A } _1 \cap \frac{}{ A } _2 \cap \frac{}{ A } _3 \cap ... \cap \frac{}{ A } _n | = n! - C_{(n,1)}(n-1)! +C_{(n,2)}(n-2)! - C_{(n,3)}(n-3)! +...+(-1)^nC_{(n,n)} = n!(1-1+\frac{1}{2!}- \frac{1}{3!} + ... +(-1)^n \frac{1}{n!} )$