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

声明：该份试题解析是本人自己做的，再根据教材理论来完成本文编写，符号太多编写工作量大，如发现答案有错误或者不够准确请及时给我留言，如需转载请表明出处。（3月底开始更新2020年试题）

一、用逻辑符号表达下列语句（论域为包含一切事物的集合）

1）过平面上的两个点，有且只有一条直线通过

解析： （仅供参考） $P_{（x，y）}$ ： x，y是平面上的两个点， $Q_{（x,y,z）}$ : z是过x和y的直线， $R_{（x，y）}$ ：x与y相同

$\forall x\forall y\forall z\exists w P_{（x，y）}\land Q_{（x，y，z）} \land Q_{（x，y，w） } \rightarrow R_{（z，w）}$

2）并不是所有的士兵都想当将军，而且不想当将军的士兵未必不是好士兵（一种形式，包含全称量词和存在量词）

解析：（仅供参考） $P_{（x）}$ ：x是士兵, $Q_{（x）}$ :x 想当将军， $R_{（x）}$ x是好士兵；

﹁ $\forall x P_{（x）} \rightarrow Q_{（x）} \land \exists x ( ┐Q_{（x）} \land R_{（x）})$

二、填空题

1.集合A={1,2,3,4,5,6,7}, A上的一个划分R={{1,2},{3,4,5}, {6,7}}. 那么所对应的等价关系R包含的有序对的个数是（17）个.定义偏序关系为集合A上的整除关系,则这个偏序关系上含有的有序对个数是（ 16 ）个.集合A上有（ 128 ）个既是对称又是反对称的关系。

解析： 第1空：用笛卡尔积的方法 2X2 + 3X3 +2X2 = 17；

第2空：整除偏序关系有<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<7,7>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<1,7>,<2,4>,<2,6>,<3,6>，因此是16个;

第3空：既是对称又是反对称，用矩阵来表示，即对角线上的数字有0和1组成，其他值都为0. 因此有 $2^7$ = 128 个。

2.已知集合A={a,b,c,d}上的两个关系 $R_{1}$ ={<a,a>,<a,b>,<b,c>}, $R_{2}$ ={<a,b>,<b,c>,<c,d>,<d,b>}.则 $R_{2}^2$ = {<a,c>,<b,d>,<c,b>,<d,c>} , $R_{2}\circ R _{1}$ = {<a,b>,<a,c>,<b,d>}

解析： 该题用矩阵的方法最简单，矩阵乘法就能解决，答案已经在题中斜体字部分。根据公式 $M（R_{2}\circ R _{1}） = M（R _{1}） * M（ R _{2}）$ 代入矩阵，用矩阵乘法可得，如下图所示。

矩阵乘法

3. 一个商店提供了3种不同的钢笔, 假设顾客小王进店时, 每种钢笔至少有5支.则小王选5支钢笔的方式有( 21 )种.

解析： 用S是有k种类型对象的多重集合，每种元素具有无限的重复数，那么S的r组合的个数为 $C_{(r+k-1,r)}$ ,因此本题的答案为 $C_{(7,5)}$ = $C_{(7,2)}$ = 21。

4.设Km,n是两部分分别有m和n个顶点的完全二部图, 则Km,n的着色数是( 2 )

解析： 【定理一】图G是2-可着色的当且仅当G是二部图；因此可知该二部图的着色数位为2。

【定理二】奇圈和奇数阶轮图都是3-色图，而偶数阶轮图都是4-色图。

5.设树T的顶点集合为V={v1, v2, ..., vn}, T的平均度为 $D=\frac{1}{n} \sum\nolimits_{i=1}^nv_{i}$ ,请用D表示出树T的顶点个数n=（ 2/(2-D) ）

解析： 由平均度D可知该树的总度数为 nD，而树的顶点数n与边数k的关系为 k = n-1, 则有 k = nD/2, 因此有等式 nD/2 = n-1，化简得 n = 2/(2-D) .

三、计算题

1.个体域为{a,b,c},将下列公式写成命题逻辑公式 $(\forall x) P_{(x)} \rightarrow (\exists y) Q_{(y)}$

解析： 个体域{a,b,c} 对于逻辑命题量词 $\forall x$ 即是个体域做合取计算，而 $\exists y$ 则是对个体域做析取运算。因此得 $P_{a} \land P_{b} \land P_{c} \rightarrow Q_{a} \lor Q_{b} \lor Q_{c}$

2. 计算下式的主析取范式和主合取范式 $(┐ P \lor Q) \rightarrow (Q \land ┐ R)$ ,写出求解步骤，结果用极小项和极大项数字表示简洁形式。

解析： 该题有两种方法可解，一种是利用真值表，一种是公式转换。

方法一：先用真值表来解题：

真值表图

则主析取范式为 $(┐ P \lor Q) \rightarrow (Q \land ┐ R) \Leftrightarrow m_{2}\lor m_{4}\lor m_{5}\lor m_{6}$

主合取范式为 $(┐ P \lor Q) \rightarrow (Q \land ┐ R) \Leftrightarrow M_{0}\land M_{1}\land M_{3}\land M_{7}$

方法二：公式推导

$(┐ P \lor Q) \rightarrow (Q \land ┐ R) \Leftrightarrow ┐(┐ P \lor Q) \lor (Q \land ┐ R)$

$\Leftrightarrow (P \land ┐ Q) \lor (Q \land ┐ R)$

$\Leftrightarrow ((P \land ┐ Q) \land (R \lor ┐R) )\lor ((P \lor ┐P) \land(Q \land ┐ R))$

$\Leftrightarrow ((P \land ┐ Q \land R) \lor (P \land ┐ Q \land ┐R) )\lor ((P \land Q \land ┐ R) \lor (┐P \land Q \land ┐ R))$

$\Leftrightarrow (P \land ┐ Q \land R) \lor (P \land ┐ Q \land ┐R) \lor (P \land Q \land ┐ R) \lor (┐P \land Q \land ┐ R)$

得主析取范式为 $m_{(101)} \lor m_{(100)}\lor m_{(110)}\lor m_{(010)}$ = $m_{2} \lor m_{4}\lor m_{5}\lor m_{6}$

因此主合取范式为 $M_{0} \land M_{1}\land M_{3}\land M_{7}$

四、解答题

1. 写出集合A上的一种关系，它既是等价关系，又是偏序关系，并简要说明这种关系的特点。

解析：设集合A={a,b,c}, 等价关系满足的条件是：自反，对称，传递；而满足偏序关系的条件是：自反，反对称，传递。条件中A的关系R需满足等价和偏序关系，也就是R必须满足既是对称又是反对称关系。则 R = {<x,y>| x=y}即关系矩阵对角线上的数都为1,因此该关系为集合A上的每个元素自成环，无其他关系路径。

2.求满足递推关系 $h_{n} = h_{n-1} + 9h_{n-2} - 9h_{n-3}$ 中 $h_{n}$ 的表达式，其中 $n\geq 3$ ，初始条件 $h_{0} = 0，h_{1} = 1，h_{2}=2$ 。

解析：本题考的是常系数齐次递推关系。题中原式转化成 $h_{n} - h_{n-1} - 9h_{n-2} + 9h_{n-3} = 0$ ，因此该式特征方程为 $q^3 - q^2 - 9q + 9 = 0$ 。

$q^2（q - 1） - 9（q - 1） = 0$ $\Rightarrow$ $（q^2-9）（q - 1） = 0$ 。得到特征根 $q_{1} =-3，q_{2} =3，q_{3} =1$ 。三个特征无重根，则该 $h_{n}$ 的一般解为：

$H_{n} = C_{1}q_{1}^n + C_{2}q_{2}^n + C_{3}q_{3}^n$ 把三个特征根代入式子中可得 $H_{n} = C_{1}（-3）^n + C_{2}（3）^n + C_{3}（1）^n = C_{1}（-3）^n + C_{2}3^n + C_{3}$ 。把 $h_{0} = 0，h_{1} = 1，h_{2}=2$ 代入 $H_{n}$ 得到三个等式 $H_{0} = C_{1} + C_{2} + C_{3} = 0 ；H_{1} = -3C_{1} +3 C_{2} + C_{3} = 1； H_{2} = 9C_{1} +9 C_{2} + C_{3} = 2.$

解这三个三元一次方程组得： $C_{1} = - \frac{1}{12} ， C_{2} = \frac{1} {3} ， C_{3} = -\frac{1} {4}$ 代入得解 $H_n = -\frac{1}{12} *(-3)^n + \frac{1}{3}* 3^n -\frac{1}{4} = \frac{1}{4}* (-3) ^ { (n-1)} + 3^{(n-1)} - \frac{1}{4}$

3. 设序列 $\{a_{i}\}$ 的母函数是 $A_{（x）}$ ，序列 $\{b_{i}\}$ 的母函数是 $B_{（x）}$ ，如果 $b_{k} = \sum\nolimits_{i=0}^k a_{i}$ ，且 $B_{（x）} =f_{（x）} A_{（x）}$ ，求 $f_{（x）}$ 。

解析：有题可知 $A_{（x）} = \sum\nolimits_{i=0}^∞ a_{i} x^i$ ，且 $b_{k} = \sum\nolimits_{i=0}^k a_{i}$ ，得 $B_{（x）} = \sum\nolimits_{i=0}^∞ ( \sum\nolimits_{j=0}^i a_{（j）} ) x^i$ = $a_{0} x^0 + (a_{0} x^1+a_{1} x^1) + (a_{0} x^2+a_{1} x^2+a_{2} x^2) + ...+(a_{0} x^n+a_{1} x^n+...+a_{n} x^n) + ...$

$= a_{0}(x^0+...+ x^n + ....) + a_{1}x((x^0+ x^1 + ...+ x^n + ...) + a_{2}x^2 ( x^0+ x^1+...+ x^n+ ...) + ...$ $= a_{0} \frac{1}{1-x} + a_{1}x \frac{1}{1-x} + a_{2} x^2 \frac{1}{1-x} + ... = = \frac{1}{1-x} *( a_{0} + a_{1}x+ a_{2} x^2 + ...)$

= $A_{(x)}\frac{1}{1-x}$ ，又由于 $B_{（x）} =f_{（x）} A_{（x）}$ ， $f_{（x）} =\frac{1 }{1-x}$

五、证明题

证明下面恒等式： $C_{(n,k)} + C_{(n+1,k)} + C_{(n+2,k)} +...+C_{(n+m,k)} = C_{(n+m+1,k+1)} -C_{(n,k+1)}$ , $C_{(n,i)}$ 表示n元素中取i个组合数。

证明：证明原式 $C_{(n,k)} + C_{(n+1,k)} + C_{(n+2,k)} +...+C_{(n+m,k)} = C_{(n+m+1,k+1)} -C_{(n,k+1)}$

$\Leftrightarrow C_{(n,k+1)} + C_{(n,k)} + C_{(n+1,k)} + C_{(n+2,k)} +...+C_{(n+m,k)} = C_{(n+m+1,k+1)}$ 。

$C_{(n,k+1)} = C_{(n-1,k)} + C_{(n-1,k+1)}$ 该等式恒成立，即在n个元素中取k+1个方法可以分成两个部分，一部分选择部分包含1个特定元素a，一部分选择部分一个不包含a。

因此 $C_{(n,k+1)} + C_{(n,k)} + C_{(n+1,k)} + C_{(n+2,k)} +...+C_{(n+m,k)}$

$= C_{(n+1,k+1)} + C_{(n+1,k)} + C_{(n+2,k)} +...+C_{(n+m,k)}$

$= C_{(n+2,k+1)} + C_{(n+2,k)} +...+C_{(n+m,k)}$

以此类推：

$C_{(n,k+1)} + C_{(n,k)} + C_{(n+1,k)} + C_{(n+2,k)} +...+C_{(n+m,k)} =C_{(n+m+1,k)} +C_{(n+m,k)} = C_{(n+m+1,k+1)}$

$\Leftrightarrow C_{(n,k)} + C_{(n+1,k)} + C_{(n+2,k)} +...+C_{(n+m,k)} = C_{(n+m+1,k+1)} - C_{(n,k+1)}$

得证。