2023年7月19日发(作者：)

网络学院离散数学模拟试题1

考试时间 120 分钟 考试方式： 开卷

专业 年级 姓名 学号

一、选择填空题(每个空格3分,共30分)

1． 设A，B是集合，且AB，则_____必定成立。D

A．A=B B．BA C．A∩B= D．AB

2． {,{}}－=_____;C

Ａ.

 B. {} C. {,{}} D. {{}}

3．

设集合A={{0}}，则P(A) =_____。D

A. P(P({0}))

B.

P({0})∪ C.

P({0})∪{{0}} D.

{,{{0}}}

4． 设有集合A={1,2,3,4}，则从A到{0,1}的不同的函数有____个。E

A．0 B．1 C．4 D．12 E. 16 F. 24 G. 32

5． 设G=(a)为12阶循环群，则G没有____阶子群。E

A．1 B．2 C．3 D．4 E. 5 F. 6

6．

凡_____都满足消去律。D

A. 代数系统 B. 半群 C.

独异点 D. 群

7． 从无向完全图K5中至少删除____条边后，所得的图将成为平面图。B

A．0 B．1 C．2 D．3

8． 若无向图G是有99个结点，9个连通分量，则G中的边数必_____。C

A. ≤90 B. =90 C. ≥90 D. =100 E. ≥100

9． 下列句子中为命题的是_____。A

A．今天不是星期六。 B．考场内禁用手机！

C．今天是周末吗？ D．今天真冷呀！

10． 任意两个不同极大项的析取式必为______。A

A. 永真公式 B. 可满足公式 C. 永假公式 D. 等值公式

二、求出谓词公式uvF(u,v)wG(u,v,w)的前束范式。(10分)

解：uvF(u,v)wG(u,v,w)

u1u1F(u1,v1)wG(u,v,w)

u1v1F(u1,v)wG(u,v,w)

u1y1F(u1,v1)wG(u,v,w)

（F(u1,v1)G(u,v,w)）

u1v1w

三、用形式证明的方法证明下列论证的有效性：“本班有些同学是有经验的C++程序员，任何C++程序员都知道对象的概念。因此，本班有人知道对象的概念。” (10分)

解：D（x）：x是C++程序员

C（x）：x知道对象的概念

论域由本班学生组成

x D（x），x（D（x）→C（x））x C（x）

（1）

x D（x） P

（2） D（c） ES（2）

（3）x（D（x）→C（x）） P

（4） D（c）→C（c） US（3）

（5） C（c） T（2）（4）

（6）

x C（x） EG（5）

四、设A和B是集合，且B=A∪{b}，其中bA。证明：P(B)=P(A)∪{X∪{b}X∈P(A)}。(10分)

证明：①∵右边的每个元素都是B的子集

左右

②Y∈左

若Y∈P(A)，则显然Y∈右

若YP(A)，则显然b∈Y，从而X∈P(A)，使Y=X∪{b}，Y∈右

左右

综合①和②，左=右

五、设R和S是集合Ｘ上的部分序关系，证明RS必定也是Ｘ上的部分序关系。(10分) 证：①∵R和S是部分序关系，从而是自反的，IXR，IXS

 IXRS，RS也是自反的

②x,yX，若RS，且< y,x >RS

则R，且< y,x >R

又∵R是部分序关系，因而是反对称的

 x=y

由此，RS是反对称的

③x,y,zX

RSy,zRS

x,yRy,zR,xyS,yz

S

x,zRx,zS(∵R是部分序关系，从而是是传递的)

x,zRS

RS是传递的

综合上述①、②、③，RS是Ｘ上的部分序关系。

六、在实数集R上定义二元运算ab，“－”，“·”分别为普通的abab，其中“+”加法、减法和乘法。证明：R关于构成独异点，但不构成群。(10分)

证：①关于R的封闭性显然

②的结合律成立

③单位元是0

④1没有逆元

七、无向图G如下图所示，求出G中长度为3的不同的通路的数目。(10分)

解：①写出邻接矩阵A

②计算A3

③计算出A3的各元素之和，即为所求

八、证明：若一次网上聊天只能在两个人之间进行，则与奇数个人在网上聊过天的人一定有偶数个。(10分)

证：建立图的模型，用顶点表示人，若某两人聊过天，则在相应的顶点之间画一条边。由握手定理的推论，度为奇数的顶点的个数为偶数，所以结论成立。

网络学院离散数学模拟试题2

考试时间 120 分钟 考试方式： 开卷

专业 年级 姓名 学号

二、 选择填空题(每个空格3分，共30分。答案写在答题纸上。)

1． {,{}}－{{}}=_____。B

Ａ.

 B. {} C. {,{}} D. {{}}

2． 若集合P、Q满足PQP，则_____必成立。C

A．QP B．QP C．PQ D．QP

3． 设X{a,b,c,d},Y{1,2,3},f{a,1,b,2,c,3}，则f是_____。D

A．从X到Y的双射

B．从X到Y的满射，但不是单射

C．从X到Y的映射，但不是满射，也不是单射的

D．从X到Y的二元关系，但不是从X到Y的映射

4． 设集合Ｘ=｛1,2,3｝，Ｒ是Ｘ上的关系，Ｒ={(1,2),(1,3),(3,1)}，则Ｒ是_____的。B

Ａ. 自反 B. 反自反 C. 对称 D. 反对称 E. 传递

5． 设有部分序集(B, R)，其中A={1,2,3,4,5,6,8,10,24,36}，R是Ａ上的整除关系。子集Ｂ＝{2,3,4}，Ｂ的下确界是_____。D

A. 不存在 B. 36 C. 10 D. 1 E. 2 F. 6

6． 设有集合A，则代数系统是____。B

Ａ. 半群但不是独异点 B. 独异点但不是群 C. 群但不是循环群 D. 循环群

7． n阶有向简单图G至多有_____条边。E

A. n-1 B. n C. 2n D. n(n-1)/2 E.

n-n F.

n

8． 完全图K8是_____。B

A．欧拉图 B．哈密尔顿图 C．平面图 D．树

22 9． 下列命题公式中， 是永假公式。A

A．(qp)p B．(pq)p C．(pq)q D．(qp)p

10． 设有谓词：F(x):x为实数；G(x):x为有理数。命题“实数都是有理数”可符号化为______。A

A．(x)(F(x)G(x)) B．(x)(F(x)G(x))

C．(x)(F(x)G(x)) D．F(x)(x)G(x)

三、 写出命题公式bca的主合取范式。(10分)

解：(abc)

四、 请给出与谓词公式((x)F(x)(y)G(y))(F(x)(z)H(z))等值的前束范式。(10分)

解：((x)F(x)(y)G(y))(F(x)(z)H(z))

((x)F(x)(y)G(y))（F(x)(z)H(z))

（F(x)(z)H(z))

((x1)F(x1)(y)G(y))（F(x)(z)H(z))

((x1)F(x1)(y)G(y))（F(x)H(z))

(x1)(y)(z)(F(x1)G(y))

五、 设A和B是集合，且P(A)=P(B)。问A＝B是否一定成立？若是，则请证明你的结论；若不是，则请说明原因。(10分)

解：是。

aA

 {a} A

{a}P(A)

{a} P(B) （P(A)=P(B)）

 {a} B

aB

∴AB

同理，B A

所以 A=B

六、 设集合Ａ={1,2,3,4,5,6}，Ａ的一个划分={{1,2},{3,4},{5,6}}，请写出所对应的等价关系。(10分)

解：{(1,1), (2,2), (3,3), (4,4), (5,5), (6,6) (1,2), (2,1), (3,4), (4,3), (5,6), (6,5)}

七、 有理数集关于普通加法是否构成群？若是，则请证明你的结论；若不是，则请说明原因。(10分)

解：是。

有理数集Q关于普通加法+封闭

Q上的+运算满足结合律

0是Q上的+运算的幺元

xQ，-x是其逆元

 Q关于+构成群

八、 完全图Kn是偶图吗？请证明你的结论。(10分)

解：当n=2时，Kn显然是偶图。

当n≠2时，Kn不是偶图。当n=1时，Kn只有一个顶点，无法将Kn的顶点分为两个不交的非空子集。当n>2时，无论怎么把Kn的顶点分为两个不交的非空子集，总有一个子集中含多个顶点，由Kn的定义，它们之间有边。

九、 证明：若无向图G是连通图，且其中只有e条边，那么G最多只有e+1个顶点。(10分)

解：设连通图G有e条边，n个顶点。∵在顶点个数相同的前提下，树是含边最少的连通图，而有n个顶点的树含n-1条边，∴e≥n-1，从而n≤e+1，即G最多只有e+1个顶点。

网络学院离散数学试题3

2006.7

专业 年级 姓名 学号

考试时间 120 分钟 考试方式： 开卷

一、单选题(每小题2分，共10分) 、

1. 设a，b，c各不相同，下面哪个等式成立？A

(A) {a,b,a}={b,a} (B) {{a},{b}}={{a,b}}

(C) {{a,b},c,}={{a,b},c} (D) {,{},a,b}={{,{}},a,b}

2. 设有命题p：3是素数，q：5是素数，r：2是有理数。下列命题中哪个为假命题？B

(A) r→(pq) (B) (pq)→r (C) r→(pq) (D) (pr)↔q

3. 无向完全图Kn(n5)中共有多少条不同的哈密尔顿回路？D

(A) 0 (B) 1 (C) 2 (D) 以上答案都不对

4. 设R和S为非空集合A上的反对称关系，则下列哪个关系可能不是A上的反对称关系？A

(A) R∪S (B) R∩S (C) R-S (D)以上答案都不对

5. 设部分序集X的哈斯图如下图所示，则下列结论中哪个是正确的？B

2

1

(A)

X中极大元只有2，极小元只有1

3

(B)

X中极大元只有2和3，极小元只有1和3

(C)

X中极大元只有2，极小元只有1和3

(D)

X中极大元只有2，没有极小元

二、填空题(每小题3分，共15分)

1． 设有命题p：我怕困难，q：我取得好成绩。命题“只要我不怕困难，我就能取得好成绩”可符号化为（ ）。 ┐p→q

2． 命题公式(q→┐(p→rp))→r的主析取范式中有（ ）个极小项。6

3． 对称关系的矩阵一定是（ ）矩阵。对称

4． 设G=(a)为12阶循环群，则G的3阶子群是（ ）。 (a4)={a4,a8,e}

5． 设G为有50个顶点、3个连通分支的森林，则G的色数为（ ）。2

三、简答题(每小题5分，共25分)

1． 设集合A={1，2，3，4}的一个划分={{1}，{2}，{3，4}}。请给出与相对应的等价关系。

答：{(1, 1), (2, 2), (3, 3), (4, 4), (3, 4), (4, 3)}

2． 设S={a，b，c}，R={{a，b)，{c，b)}，则R具有关系的5种性质中的哪几种性质？

答：反自反、反对称、传递

3． 无向树T有7片树叶(即1度顶点)，3个3度顶点，其余顶点的度数均为4，求T的阶数。

答：设T的4度顶点有x个，则

N=3+7+x=10+x， m=9+x

由握手定理可知

2m=18 + 2x =7* 1 + 3*3 + 4x=> x=1.

所以，n=7+3+1=11

4． 对于下面的映射f，判断它们是否为单射和满射。如果不是单射，则给出x1和x2，使得x1≠x2，但f(x1)=f(x2)；如果不是满射，则计算ranf。

(1)设R为实数集，f：R→R，f(x)=x3+x．

(2)设Q为有理数集f：Q→Q，f(x)=x2．

答：(1)单射，满射，双射．

(2)不是单射，f(—1)=f(1)；不是满射，ranf={x|xQx≥0

5． 设集合X={1,0,−1}，X关于普通加法是否构成群？为什么？

答：不构成代数系统，当然也不构成群，因为不封闭。

xQ }．

四、证明题(每小题10分，共50分)

1． 设有限集合S中有n（n≥1）个元素。证明形如f：S×SS的不同的映射共有nn2个。 证明：S×S =S=n，而函数f(x,y)的取值有n（S=n）个选择，所以，由乘法原理，共有n×nׄ×n=nn222个。

2． 给出下列推理形式的形式证明：

前提：

x( (┐G(x)F(x))，x(G(x)H(x))．

结论：x(F(x)H(x))．

证明：

①x(G(x)H(x)) P

②G(c)

H(c) ①ES

③x( (┐G(x)F(x)) P

④┐G(c) V F(c) ④US

⑤G(c) →F(c) T④

⑥G(c) T②化简

⑦F(c) T⑤⑥

⑧H(c) T②化简

⑨H(c)F(c) T⑦⑧

⑩x(H(x)

F(x)) ⑨EG

3． 证明完全图K6不是欧拉图。

证明：完全图K6每个顶点的度均为5，不是奇数，所以K6不是欧拉图。

4． 证明：若无向简单图G有7个结点，17条边，则G必为哈密顿图。

证明：G的每对不相邻的顶点的度之和至少7。否则，若有一对不相邻的顶点的度之和小于7，则删除这两个顶点后，在剩下的图中，至少有11条边，这在有5个顶点的简单图中是不可能的。

5． 设G为群，f：G→G为满射，并且满足x,yG，有f(xy)=f(x)f(y)。证明：xG，有 (f(x))-1=

f(x-1)。

证明：

yG，因为f为满射，所以xG，使f(x)=y

从而，f(e)y=f(e)f(x)=f(ex)= f(x)=y

同理，yf(e)=y

所以，f(e)是单位元，f(e)=e

xG，有

f(x)f(x-1)= f(xx-1)= f(e)=e

类似地，f(x-1)f(x)=e

所以，(f(x))-1= f(x-1)。

网络学院离散数学模拟试题4

考试时间 120 分钟 考试方式： 开卷

专业 年级 姓名 学号

一、单选题(每小题2分，共20分)

6. 集合A={a,3,4,2}，下列哪个命题是错误的？D

(A) { }A (B) {a}A (C) {a,3,4,2}A (D) {a}A

7. 设A、B、C、D为任意四个集合，下列哪个命题是不正确的？D

(A)

(BC)A(BA)(CA)

(B)

(BC)A(BA)(CA)

(C)

(BC)A(BA)(CA)

(D)

(AB)CA(BC)

8. 下列哪个句子是真命题？C

(A) 本句话是假的. (B) 如果火星上有生命，则雪是白色的..

(C) 如果地球上有生命，则雪是黑色的 (D) 今天是7月29日吗?

9. 谓词公式x(P(x) →Q(x,y)z R(w,z)) →S(x)中有几个自由变元？D

(A) 0个 (B) 1个 (C) 2个 (D) 3个

10. 下列哪个关于图的色数的结论是正确的？A

(A) 任何无向树的色数均不超过2 (B) 任何偶数阶欧拉图的色数均为2

(C) 任何偶数阶哈密顿图的色数均为2 (D)任何简单无向图的色数均不超过4

11. 下列哪个关于连通图的结论是不正确的？B

(A) 欧拉图中必没有割边 (B) 欧拉图中必没有割点

(C) 哈密顿图中必没有割边 (D) 哈密顿图中必没有割点

12. 设R和S为非空集合A上的部分序关系，则下列哪个关系也是A上的部分序关系？B

(A) R∪S (B) R∩S (C) R-S (D)以上都不是

13. 设集合A={a,b,c,d}，A上的二元关系R={(a,a), (a,c),(b,c)}.，则关系R2=等于什么？C

(A) {(a,a)} (B) {(a,c)) (C) {(a,a),(a,c)} (D) {(a,a),(a,c),(b,d)} 14. 设集合A={1,2,3,4}，A上的二元关系R={(1,1), (2,2), (2,3), (4,4)}，S={(1,1), (2,2), (2,3),

(3,2), (4,4)}，则S是R的什么闭包？B

(A) 自反 (B) 对称 (C) 传递 (D)以上都不是

15. 设集合A={1，2，„，10}，≤是A上的整除关系，则元素10是部分序集 (A, ≤)的什么元素？C

(A) 不是极大元，也不是最大元 (B) 是最大元但不是极大元

(C) 是极大元但不是最大元 (D) 是最大元，也是极大元

二、填空题(每小题3分，共15分)

6． 设有谓词F(x)：X是人，G(x)：x爱唱歌。命题“有的人不爱唱歌”可符号化为（

）x (F(x)┐G(x))

7． 谓词公式xP(x)y┐P(y)的类型是（ ）。矛盾公式

8． 图G有21条边、3个四度结点，其余均为三度结点，则G有（ ）顶点。13

9． 若G为含12条边的6阶简单连通平面图，则G有（ ）个面。8

10． 有限集合上的二元关系可以表示为有向图，若该二元关系是反自反关系，则相应的有向图一定是（ ）的。简单的、无环的

三、简答题(每小题5分，共25分)

1． 设A,B,C是任意的三个集合，若A∪C=B∪C，则A=B是否一定成立？请说明理由。

答：不一定成立。如A={1}，B={2}，C={1，2}

2． 对任意集合A和B，P(A)∪P(B)= P(A∪B)是否一定不成立？为什么？

答：不一定，当A和B中有一个为空集时等式成立

3． 设集合A={a,b}，B={1，2}，请给出形如f：A→B的所有映射，并指出其中哪些为双射。

答：f1a,1,b,1,f2a,2,b,2,f3a,21,b,2,f4a,2,b,1;f3,f4

4． 求命题公式(q (q→┐(p→rp)))→r的主合取范式，并以此判断原命题公式的类型。

答：主合取范式：(q (q→┐(p→rp)))→rrM0M2M4M6

该公式为非重言式的可满足式

5． 含n个顶点的连通图至少有几条边？为什么？

答：n-1条边。因为含n个顶点的树至少有n-1条边，而树是边最少的连通图。

四、证明题(每小题10分，共40分)

6． 证明完全偶图K4,4不是平面图。

证明：K4,4中含有与K3,3同构的子图，所以K4,4不是平面图。

7． 假设下列陈述都是正确的：

(1)凡工作效率不高的人都喜欢闲聊；

(2)凡喜欢闲聊的人不可能是工作狂。

问工作狂的工作效率是否都很高？请将上述陈述和你的结论符号化(可取个体域为所有的人所构成的集合)，并对你的结论给出形式证明。

证明：

结论：工作狂的工作效率都很高

符号化：

D（x）：x工作效率高

C（x）：x喜欢闲聊

B（x）：x是工作狂

论域由本班学生组成

x（D（x）→C（x）），x（C（x）→B（x））x（B（x）→D（x））

形式证明：

（1）

x（D（x）→C（x）） P

（2） D（x）→C（x） US（2）

（3）x（C（x）→B（x）） P

（4）C（x）→B（x） US（3）

（5）B（x）→C（x） T（4）

（6） C（x）→D（x） T（2）

（7）B（x）→D（x） T（5）（6）

（8）x（B（x）→D（x）） UG（7）

8． 设A={1,2,3}，R为AA上的关系，((a,b), {c,d)}∈R当且仅当a-b=c-d。证明R为AA上的等价关系，并求出R所对应的划分。

证明：关系R显然是自反、对称和传递的，所以是等价关系。

划分：{{<1，2>，<2，3>}， {<2，1>，<3，2>}， {<1，1>， <2，2>，<3，3>}， {<1，3>， {<3，1>}}．

9． 在整数集Z上定义二元运算*，x*y=x+y-4。证明Z关于运算*构成群。

证明：

（1） 显然，运算*关于Z封闭。

（2） (x*y)*z=(x+y-4)*z= x+y-4+z-4=x+y+z-8 x*(y*z)= x*(y+z-4)=x+y+z -4-4=x+y+z-8

所以(x*y)*z= x*(y*z)，运算*满足结合律

（3） x*4=4*x=x

所以，4是单位元

（4） x，x*(8—x)= (8—x)*x=4

所以，x有逆元8—x

综上所述，Z关于运算*构成群。