【免费】同等学力_在职研究生考研_离散数学&组合数学2007-201805真题及答案.pdf_离散数学与组合数学pdf

需积分: 0 111 浏览量更新于2023-05-17 4 收藏 2.6MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

1 / 28

数学基础课程-同等学力计算机综合真题及答案

（2004-2006、2007-2014、2017）

2004 年数学

第一部分数学基础课程

（共 40 分）

一、形式化下列语句（共 3 分，第 1 题 1 分，第 2 题 2 分）

1．有些人勤奋，但并非所有人都勤奋。

答：设 M(x): x 是人； R( x): x 勤奋； N(x, y)：x 与 y 不相同，则原语句可表示为：

xy (N(x,y)∧M(x)∧M(y)∧R(x) ∧R(y))

2．不管白猫黑猫，抓住老鼠就是好猫。

答：设 G(x): x 是猫；Y( x): x 是白猫；H(x): x 是黑猫；M(x): x 能抓老鼠；N(x): x 是好猫；则原语句可表示为：

x (G(x)∧(Y(x)∨H(x))∧M(x) →N(x))

二、填空（共 3 分，每空 1 分）

1、设 A={a,b,c}，B={1,2,3,4}，从 A 到 B 不同的二元关系共有（ 



）个。

答：|A|=3 ,|B|=4 ,因此二元关系共有







个。

2、设 A={a,b,c}，B={1,2,3,4}，从 A 到 B 不同的函数共有（ 



）个。

答：|A|=3 ,|B|=4 ,因此共有







个。

3、设集合 A 的基数|A|为 n，在 A 上有（ 







）个不同的自反关系。

答：设集合 A 的基数|A|为 n，在 A 上有 







个不同的自反关系，有 

󰇛󰇜



个不同的对称关系。

解析：A 上的关系可以用一个 nn 的关系矩阵表示，自反关系只要求对角线上的元素为 1，其他位置上的元素任意，

可以 0 或 1，因此 A 上的自反关系个数为







种。A 上的对称关系个数为









种。

三、证明（共 6 分，每题 3 分）

1、下列等值式是否正确，如正确请证明，如错误请举出反例。

󰇛󰇜

󰇛



󰇜



󰇛



󰇜

󰇛󰇜󰇛󰇜󰇛󰇜󰇛󰇜

2、用等势定义证明(1,2](a,b], (a,bR,ab,R 为实数集)。

T 答：y=kx+l 过点（1，a）（ 2，b）

󰇫

则  

则   

得 k=b-a l=a-k=2a-b

∴y=(b-a)x+2a-b

原答：

3 / 28

2005 年数学

第一部分数学基础课程

（共 40 分）

一、形式化下列语句（共 3 分）

1.（1 分）有且有一个太阳

S 答：全域：全部天体 P(x)表示 x 为太阳； Q(x,y) 表示 x 与 y 相等，则：xy(P(x)

∧(P(y)→Q(x,y)))

原答： P∧q，其中，p：有太阳，q：有一个太阳

2.（2 分）任意两个相异实数 x,y 之间必可找到另一个实数 z.

·S 答：全域：全体实数 R(x): x 为实数则原句可形式化为：

󰇛󰇛󰇜  󰇛󰇜   →z(R(z) ∧(x<z<y∨y<z<x))

或设 R(x): x 为实数 N(x,y): G(x,z,y): x<z<y 则原句可形式化为：

󰇛󰇛󰇜  󰇛󰇜 󰇛󰇜 →z(R(z) ∧(G(x,z,y)∨G(y<z<x)))

原答：R(x):x 是实数 E(z,y):x=y L(x,y):x>y

xy(R(x) ∧ R( y) ∧ ¬E(x, y)) → z((R(z) ∧ L(x, z) ∧ L(z, y)) ∨ (R( z) ∧ L( y, z) ∧ L(z, x)))

二、填空题（共 9 分）

1、（ 2 分）设 A=[1，2，3，4]，则在 A 上的二元关系共有 



个；其中有 15 个是等价关系。

答：



； 15

1）集合 A 元素个数|A|=4，所以 A 上二元关系的个数为



=



65536 个。

2）因为等价关系与集合划分一一对应，所以找出集合 A 的所有划分，每一个划分对应一个等价关系，共 15 个

划分的子集对应于等价关系的等价集

划分成一个等价集(1 个等价关系):{1,2,3,4}

划分成两个等价集(7 个等价关系):{1,2,3},{4} {1,2,4},{3} /{1,3,4},{2} /{2,3,4},{1} /{1,2},{3,4} /{1,3},{2,4} /{1,4},{2,3}

划分成三个等价集(6 个等价关系):{1,2},{3},{4} /{1,3},{2},{4}/{1,4},{2},{3}/{1},{2,3},{4}/{1},{2,4},{3} /{1},{2},{3,4}

划分成四个等价集(1 个等价关系):{1},{2},{3},{4}

（注：等价关系：设 R 是非空集合 A 上的二元关系，若 R 是自反的、对称的、传递的，则称 R 是 A 上的等价关系。）

2、（ 1 分）设︱A︱=n (即集合 A 的基数为 n), 则在 A 上有 

󰇛󰇜



个不同的对称关系。

答：设集合 A 的基数|A|为 n，在 A 上有 







个不同的自反关系，有 

󰇛󰇜



个不同的对称关系。

解析：A 上的关系可以用一个 nn 的关系矩阵表示，自反关系只要求对角线上的元素为 1，其他位置上的元素任意，

可以 0 或 1，因此 A 上的自反关系个数为







种。A 上的对称关系个数为









种。

3、（ 2 分）（    ）



的展开式经过合并同类项后有 C(6,4)=15 项。

原答：共





项 ( 



 



 



=4 的非负整数解 )

S 答：三项式可以将其中两项合成整体，用二项式定理来处理：󰇛 󰇜



=









 













  













  







󰇛󰇛  󰇜 󰇜



=





󰇛  󰇜



 





󰇛  󰇜







 





󰇛  󰇜







 









 







󰇛  󰇜



共 5 项

󰇛  󰇜



=









 













 





















共 4 项

󰇛  󰇜



共 3 项

󰇛  󰇜



共 项

共 5+4+3+2+1=15 项

4 / 28

4、（ 2 分）标有 1、2、3、4 的四张数字卡片，要求数 1 不排在千位上，数 2 不排在百位上，数 3 不排在十位上，

数 4 不排在个位上，那么用这四张卡片组成的满足要求的四位数共



个。

答：考完全错排 



󰇡 























󰇢󰇡

















󰇢

5、（ 2 分）以三种不同的颜色来给某房间的四个墙壁着色，房间的地面为长方形（如下图所示），每个墙壁只着

一种颜色，任何相邻的两个墙壁的颜色都不同，共有 18 种着色方案。

答：利用容斥原理





：表 和 同色，



：表 和 同色， 



：表 和 同色， 



：表 和 同色，

|



∩



∩



∩



|= |S|-|A∪B∪C∪D|=|S|-|A|-|B|-|C|-|D|+|A∩B|+|A∩C|+|A∩D|+|B∩C|+|B∩D|+|C∩D|-|A∩B∩C|-

|A∩B∩D|-|A∩C∩D|-|B∩C∩D|+|A∩B∩C∩D|





   



   



          

若不允许用 2 种颜色，要减去 6 种方案。

三、问答题（6 分）

有r 个正方形排成一行，今用红、黄、白、蓝四种颜色给这个r 个正方形染色，每个正方形只能染一种颜色，

如果要求染红、黄、白色的正方形分别至少出现一个，问有多少种不同的染法？

答：考指数型母函数





(x) = (1+





















 







) 󰇛





















 







󰇜







󰇛



 󰇜



= 



 



 



 





















-3



















 









































󰇛



 



   



 󰇜







方案数







 



   



 

5 / 28

四、证明（共 22 分）

1、（ 3 分）下列等值式是否正确，如正确请证明，如错误请举出反例。

( x)( y)(P(x) ∧ Q( y) → S(x, y)) = ( x)( y)(P(x) ∧ Q( y) ∧ S(x, y))

解：正确，推理如下

(x) (y) (P(x)∧P(y) Q(x,y))

=(󰇛x) (y) (P(x)∧P(y))) Q(x,y)) 量词辖域收缩等值式

=󰇛󰇛󰇜󰇛󰇜󰇛󰇛󰇜  󰇛󰇜󰇜󰇜 󰇛󰇜󰇜 蕴含等值式

=󰇛󰇛󰇜󰇛󰇜󰇛󰇛󰇜  󰇛󰇜󰇜󰇜 󰇛󰇜󰇜

=󰇛󰇛󰇜󰇛󰇜󰇛󰇛󰇜  󰇛󰇜󰇜󰇜 󰇛󰇜󰇜 德摩根等值式

（注：同 2011 年四-1）

2、（ 3 分）设 f: R×R→R , f(x,y)=x+y;

g: R×R→R, g (x,y)=xy

证明：(1) f 是满射的，但不是单射的。

(2) g 是满射的，但不是单射的。

证 1：

(1)对于任意的 b∈R，存在<0,b>∈R×R，满足 f(0,b)=0+b=b 因此 f 是满射的。但由于 f(0,1)= f(1,0)=1，因此 f 不是单射的。

(2)对于任意的 b∈R，存在<1,b>∈R×R，满足 g(1,b)=1b=b 因此 g 是满射的。但由于 g(0,1)=g(1,0)=0，因此 f 不是单射的。

证 2：（ 1）因为对于任意 B∈R，皆存在<x,y>∈R×R，使得 f<x,y>=x+y=B 成立，根据概念，f 是满射的。

但从 x+y=B 中，并不能确定唯一对应的<x,y>，故 f 不是单射的。

（2）因为对于任意 B∈R，皆存在<x,y>∈R×R，使得 f<x,y>=x×y=B 成立，根据概念，f 是满射的。

但从 x×y=B 中，并不能确定唯一对应的<x,y>，故 f 不是单射的。

3、（ 4 分）设 G 是一个有 n 个结点 m 条边的连通简单平面图，若 n≥3, 则 m≤3n－6.

证明：设 G 有 k(k≥1)个连通分支,若 G 为树或森林,则 m=n-k≤3n-6(n≥3)，若 G 不是树也不是森林，则 G 中必含圈，

又因为 G 是简单图,所以各圈的长度均大于或等于 3，因各面次数至少为 l (l≥3),又





 





在 l =3 时达到最大值.

4、（ 4 分）证明：任何连通简单平面图至少有一个结点的度数不超过 5。

证 1：假设每个结点度数都大于 6，则



󰇛



󰇜





，由握手定理可知：



󰇛



󰇜





。

因而 m≥3n，G 是简单平面图 m≤3n－6 即 m+6≤3n，与上题结论矛盾，问题得证。

证 2：若 G 的阶数 n≤6，结论显然成立，n≥7,若最小度δ≥6，由握手定理可知：



󰇛



󰇜





。

因而 m≥3n，与上题结论矛盾，问题得证。

5、（ 8 分）给定群< G,Ο>，且 a∈G,定义映射 f (x) = a Ο x Ο



，x∈G. 证明：f 是< G, Ο>到其自身的同构映射。

证 1：显然有 f:GG，下面证明 f 的满射性与单射性。

对任意 y∈G，存在



ΟyΟa 属于 G，使得 f(



ΟyΟa) =aΟ(



ΟyΟa) Ο



= y ，因此 f 是满射的。

假设 f(x)=f(y)，那么有



ΟxΟa = 



ΟyΟa，根据群的消去律，必有 x=y。因此 f 是单射的。

最后验证 f 为同态映射。对于任意 x,y 属于 G

f(xΟy) = a Ο(xΟy)



=aΟxΟy



=(aΟxΟ



)(aΟy



) = f(x) Οf(y)

证 2：对于 x, y∈G 有 f (x Ο y) = a Ο (x Ο y)



= (a Ο x Ο



) Ο (a Ο y Ο



) = f (x) Ο f ( y) 所以 f 是 G 的自同态。

任取 y∈G ，则



Ο y Οa∈G，且满足 f (



Ο y Οa) = a Ο(



Ο y Οa) Ο



= y 所以 f 是满射的。

假若 f(x)=f(y)，即



Ο x Οa = 



Ο y Οa，由 G 中的消去律必有 x=y，从而 f 是单射的。

综上所述， f 是< G, Ο>到其自身同构映射。

剩余27页未读，继续阅读

grantpanda

粉丝: 0
资源: 2

会员权益专享

同等学力_在职研究生考研_离散数学&组合数学2007-201805真题及答案.pdf

同等学力计算机统考离散数学大纲习题解答

组合数学（北大版）

离散数学与组合数学中文版

同等学力申硕离散数学 2015年考了哪些土木

同等学力的计算机数学专业

2004年同等学力计算机k

401 Unauthorized strict-origin-when-cross-origin

C# thread.sleep的作用

php strict-origin-when-cross-origin

同等学力计算机五选二该怎么选

flex 布局左图右文

strict origin when cross origin

kitti语义分割数据集

北工大计算机技术面试题

403 strict-origin-when-cross-origin

sched_priority

yolov5shufflenetv2网络结构

会员权益专享

最新资源