离散数学试卷（共五则范文）

第一篇：离散数学试卷

诚信应考,考试作弊将带来严重后果！华南理工大学期末考试 《离散数学》试卷A 注意事项：1.考前请将密封线内填写清楚；2.所有答案请直接答在试卷上；3．考试形式：闭卷；4.本试卷共五大题，满分100分，考试时间120分钟

一、填空题(本大题共12小题，每小题2分，共24分)1．求合式公式xP(x)→xQ(x,y)的前束范式________________。2．设集合A={a, b, {a,b}, }, B = {{a,b}, }，求B-A=_____________． 3．设p与q的真值为0,r,s的真值为1则命题(s(q(rp)))(rp)的真值是__________.4．设R是在正整数集合Z上如下定义的二元关系Rx,y(x,yZ)(xy1，0)则它一共有个有序对，且有自反性、对称性、传递性、反自反性和反对称性各性质中的性质。5．公式x(P(x)→Q(x,y))→S(x)中的自由变元为________________，约束变元为________________。6．设有命题T(x): x 是火车，C(x): x是汽车，Q(x, y): x跑得比y快，那么命题“有的汽车比一些火车跑得快”的逻辑表达式是______________________.7．设G是n阶m条边的无向图，若G连通且m=__________则G是无向树.8．设X={1，2，3}，f：X→X，g：X→X，f={<1, 2>,<2,3>,<3,1>},g={<1,2>,<2,3>,<3,3>}，则f-1g=________________，gf=________________。9.不能再分解的命题称为________________，至少包含一个联结词的命题称为《离散数学》试卷A

________________．

10.连通无向图G含有欧拉回路的充分必要条件是 11．设集合A={,{a}}，则A的幂集P(A，|P(A)|=_____________________________。

12.设G = , G’ = 为两个图(同为无向图或有向图), 若E’  E且_______________, 则称G’是G的子图, 若E’  E且_______________, 则称G’是G的生成子图。

二、单选题(本大题共12小题，每小题2分，共26分)

1．下列命题公式为重言式的是（）

A.(p∨┐p)→q．B．p→(p∨q)C．q∧┐qD．(p→p)→q

2．下列语句中为命题的是()

A．你好吗？

B．人有6指.C．我所说的是假的.D．明天是晴天.3.设D=为有向图，V={a, b, c, d, e, f}, E={, , , ,}是（）

A．强连通图

C．弱连通图 B．单向连通图 D．不连通图

4．集合A＝{a，b，c}上的下列关系矩阵中符合偏序关系条件的是()

10

1011A．

001

11001011011110 B．010C．110D．010 11010010111

5．设A={1，2，3}，A上二元关系S={<1，1>，<1，2>，<3，2>，<3，3>}，则S是（）

A．自反关系 B．传递关系C．对称关系D． 反自反关系

6.设A={a,b,c,d}，A上的等价关系R={, , , }∪IA，则对应于R的A的划分是（）

A．{{a},{b, c},{d}}

C．{{a},{b},{c},{d}} B．{{a, b},{c}, {d}} D．{{a, b}, {c,d}}

7.以下非负整数列可简单图化为一个欧拉图的是()

A.{2, 2, 2, 2, 0}B.{4, 2, 6, 2, 2}

C.{2, 2, 3, 4, 1}D.{4, 2, 2, 4, 2}

8.设论域D＝{a，b }，与公式xA(x)等价的命题公式是()

A．A(a)∧A(b)B．A(a)→A(b)C．A(a)∨A(b)D．A(b)→A(a)

9.一棵树有3个4度顶点，4个2度顶点其余都是树叶，求这棵树有多少个树叶顶点()

A.12B.8C.10D.1

310.有ABC三个人猜测甲乙丙三个球队中的冠军.各人的猜测如下:

A: 冠军不是甲,也不是乙.B: 冠军不是甲,而是丙.C: 冠军不是丙,而是甲.已知其中有一个人说的完全正确.一个人说的都不对,而另外一人恰有一半说对了.据此推算,冠军应该是()

A．甲B.乙C.丙D.不确定

11．如第11题图所示各图，其中存在哈密顿回路的图是()

12．设C(x): x是国家级运动员，G(x): x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为()

(A)x(C(x)G(x))(B)x(C(x)G(x))

(C)x(C(x)G(x))(D)x(C(x)G(x))

三．计算题(30分)

1．用等值演算法求取求下列公式：(PQ)(P∨Q)的合取范式（5分）

2．图G如下图所示，求图G的最小生成树.（5分）

3．有向图D如图所示，求D的关联矩阵M(D)（5分）

4.化简表达式(((A(BC))

A)(B(BA)))(CA)（7分）

5．设R={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)和s(R)，并作出它们及R的关系图(8分)

五．证明题(22分)

1．构造下面推理的证明(5分)

前提：pq，pr，st，sr，t

结论：q

2．设A={1, 2, 3, 4}, 在AA定义的二元关系R，u,v,x,yAA, uRxuy +xv

证明R是AA上的等价关系。(5分)

3．已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C)（6分）

4． 无向图G = ，且|V|=n, |E|=m, 试证明以下两个命题是等价命题

1）G中每对顶点间具有唯一的通路，2）G连通且n=m+1。（6分）

第二篇：离散数学试卷1（范文）

离散数学试题（1）

一、单项选择题（本大题共15小题，每小题1分，共15分）

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1．下列是两个命题变元p，q的小项是（）

A．p∧┐p∧qB．┐p∨q

C．┐p∧qD．┐p∨p∨q

2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）

A．p→┐q

C．p∧q

B．p∨┐q D．p∧┐q B．x+y=10 D．x mod 3=2 3．下列语句中是命题的只有（）A．1+1=10C．sinx+siny<0

4．下列等值式不正确的是（）

A．┐(x)A(x)┐A

B．(x)(B→A(x))B→(x)A(x)

C．(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)

D．(x)(y)(A(x)→B(y))(x)A(x)→(y)B(y)

5．谓词公式(x)P(x,y)∧(x)(Q(x,z)→(x)(y)R(x,y,z)中量词x的辖域是（）

A．(x)Q(x,z)→(x)(y)R(x,y,z))

B．Q(x,z)→(y)R(x,y,z)

C．Q(x,z)→(x)(y)R(x,y,z)

D．Q(x,z)

6．设R为实数集，函数f：R→R，f(x)=2x，则f是（）

A．满射函数

C．双射函数B．入射函数 D．非入射非满射

7．设A={a,b,c,d}，A上的等价关系R={,,,}∪IA，则对应于R的A的划

分是（）

A．{{a},{b,c},{d}}B．{{a,b},{c},{d}}

C．{{a},{b},{c},{d}}D．{{a,b},{c,d}}

8．设A={Ø}，B=P(P(A))，以下正确的式子是（）

A．{Ø,{Ø}}∈B

C．{{Ø},{{Ø}}}∈BB．{{Ø,Ø}}∈B D．{Ø,{{Ø}}}∈B

9．设X，Y，Z是集合，一是集合相对补运算，下列等式不正确的是（）

A．(X-Y)-Z=X-(Y∩Z)

B．(X-Y)-Z=(X-Z)-Y

C．(X-Y)-Z=(X-Z)-(Y-Z)

D．(X-Y)-Z=X-(Y∪Z)

10．设*是集合A上的二元运算，称Z是A上关于运算*的零元，若（）

A．xA,有x*Z=Z*x=Z

B．ZA，且xA有x*Z=Z*x=Z

C．ZA，且xA有x*Z=Z*x=x

D．ZA，且xA有x*Z=Z*x=Z

离散数学试题（1）

11．在自然数集N上，下列定义的运算中不可结合的只有（）

A．a*b=min(a,b)

B．a*b=a+b

C．a*b=GCD(a,b)(a,b的最大公约数)

D．a*b=a(mod b)

12．设R为实数集，R={x|x∈R∧x>0}，*是数的乘法运算，是一个群，则下列集

合关于数的乘法运算构成该群的子群的是（）

A．{R中的有理数}

+C．{R中的自然数}

A．是交换群 +++

B．{R中的无理数} D．{1，2，3} B．是加法群 D．*对是可分配的 +13．设是环，则下列正确的是（）C．对*是可分配的14．下列各图不是欧拉图的是（）

15．设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（）

A．2个面B．3个面

C．4个面D．5个面

第二部分非选择题（共85分）

二、填空题（本大题共10小题，每空1分，共20分）

请在每小题的空格中填上正确答案。错填、不填均无分。

16．一公式为之充分必要条件是其析取范式之每一析取项中均必同时包含一命题变元及其否定；一公式为之充分必要条件是其合取范式之每一合取项中均必同时包含 一命题变元及其否定。

17．前束范式具有形式(Q1V1)(Q2V2)„(QnVn)A，其中Qi(1≤i≤n)为，A为的谓词公式。

18．设论域是{a,b,c}，则(x)S(x)等价于命题公式；(x)S(x)等价于命题公式。

19．设R为A上的关系，则R的自反闭包。

20．某集合A上的二元关系R具有对称性，反对称性，自反性和传递性，此关系R，其关系矩阵是。

21．设是一个偏序集，如果S中的任意两个元素都有和，则称S关于≤

构成一个格。

22．设Z是整数集，在Z上定义二元运算*为a*b=a+b+a·b，其中+和·是数的加法和乘法，则代数系统的幺元是，零元是。

23．如下平面图有2个面R1和R2，其中deg(R1)=，deg(R2)=。

24．无向图G具有一条欧拉回路，当且仅当G是。

25．在下图中，结点v2的度数是，结点v5的度数是。

三、计算题（本大题共6小题，第26—27小题每小题4分，第28、30小题每小题5分，第29、31小题每小题6分，共30分）

26．（4分）求出从A={1,2}到B={x,y}的所有函数，并指出哪些是双射函数，哪些是满射函

数。

27．（4分）如果论域是集合{a,b,c}，试消去给定公式中的量词：(y)(x)(xy0)。

28．（5分）设A={a,b,c }，P（A）是A的幂集，是集合对称差运算。已知

是群。

在群

中，①找出其幺元。②找出任一元素的逆元。③求元素x使满足{a}x={b}。

29．（6分）用等值演算法求公式┐(p→q)

(p→┐q)的主合取范式

30．（5分）画出5个具有5个结点5条边的非同构的无向连通简单图。

31．（6分）在偏序集中，其中Z={1,2,3,4,6,8,12,14}，≤是Z中的整除关系，求集合D={2,3,4,6}的极大元，极小元，最大元，最小元，最小上界和最大下界。

四、证明题（本大题共3小题，第32~33小题每小题6分，第34小题8分，共20分）

32．（6分）用等值演算法证明((q∧s)→r)∧(s→(p∨r))(s∧(p→q))→r

33．（6分）设n阶无向树G=中有m条边，证明m=n-1。

34．（8分）设P={Ø,{1},{1,2},{1,2,3}}，是集合P上的包含关系。

（1）证明：

是偏序集。

（2）在（1）的基础上证明

是全序集

五、应用题(15分）

35．（9分）在谓词逻辑中构造下面推理的证明：每个在学校读书的人都获得知识。所以如

果没有人获得知识就没有人在学校读书。（个体域：所有人的集合）

第三篇：离散数学试卷2

离散数学试题（2）

一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条()

A.汉密尔顿回路B.欧拉回路

C.汉密尔顿通路D.初级回路

2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是()

A.10B.12C.16D.1

43.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是()

A.b∧(a∨c)

B.(a∧b)∨(a’∧b)

C.(a∨b)∧(a∨b∨c)∧(b∨c)

D.(b∨c)∧(a∨c)

4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是()

A.<{1},·>B.〈{-1},·〉

C.〈{i},·〉D.〈{-i},·〉

5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交

运算，下列系统中是代数系统的有()

A.〈Z，+，/〉B.〈Z，/〉

C.〈Z，-，/〉D.〈P(A)，∩〉

6.下列各代数系统中不含有零元素的是()

A.〈Q，*〉Q是全体有理数集，*是数的乘法运算

B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算

C.〈Z，〉，Z是整数集，定义为xxy=xy,x,y∈Z

D.〈Z，+〉，Z是整数集，+是数的加法运算

7.设A={1,2,3}，A上二元关系R的关系图如下：

R具有的性质是

A.自反性

B.对称性

C.传递性

D.反自反性

8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉〈,a,c〉}，则关系R的对称闭包S(R)是()

A.R∪IAB.RC.R∪{〈c,a〉}D.R∩IA

9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的等价关系，R应取()

A.｛〈c,a〉，〈a,c〉｝B.{〈c,b〉，〈b,a〉}

C.{〈c,a〉，〈b,a〉}D.{〈a,c〉，〈c,b〉}

10.下列式子正确的是()

A.∈B.C.{}D.{}∈

11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x

()

A.( x)(y)(z)(A(x,y))→A(f(x,z),f(y,z))

离散数学试题（2）

B.(x)A(f(a,x),a)

C.(x)(y)（A(f(x,y),x))

D.(x)(y)(A(x,y)→A(f(x,a),a))

12.设B是不含变元x的公式，谓词公式(x)(A(x)→B)等价于()

A.(x)A(x)→BB.(x)A(x)→B

C.A(x)→BD.(x)A(x)→(x)B

13.谓词公式(x)(P(x,y))→(z)Q(x,z)∧(y)R(x,y)中变元x()

A.是自由变元但不是约束变元

B.既不是自由变元又不是约束变元

C.既是自由变元又是约束变元

D.是约束变元但不是自由变元

14.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为()

A.P∨QB.P∧┐QC.P→┐QD.P∨┐Q

15.以下命题公式中，为永假式的是()

A.p→(p∨q∨r)B.(p→┐p)→┐p

C.┐(q→q)∧pD.┐(q∨┐p)→(p∧┐p)

二、填空题(每空1分，共20分)

16.在一棵根树中，仅有一个结点的入度为______，称为树根，其余结点的入度均为______。

17.A={1,2,3,4}上二元关系R={〈2，4〉，〈3，3〉，〈4，2〉}，R的关系矩阵MR中

m24=______,m34=______。

18.设〈s,*〉是群，则那么s中除______外，不可能有别的幂等元；若〈s,*〉有零元，则|s|=______。

19.设A为集合，P(A)为A的幂集，则〈P(A)，是格，若x,y∈P(A),则x,y最大下界是______，〉

最小上界是______。

20.设函数f:X→Y,如果对X中的任意两个不同的x1和x2，它们的象y1和y2也不同，我们说f

是______函数，如果ranf=Y，则称f是______函数。

21.设R为非空集合A上的等价关系，其等价类记为〔x〕R。x,y∈A，若〈x,y〉∈R，则 〔x〕R与〔y〕R的关系是______，而若〈x,y〉R，则〔x〕R∩〔y〕R=______。

22.使公式(x)(y)(A(x)∧B(y))(x)A(x)∧(y)B(y)成立的条件是______不含有y，______不含有x。

23.设M(x):x是人，D(s):x是要死的，则命题“所有的人都是要死的”可符号化为(x)______,其中量词(x)的辖域是______。

24.若H1∧H2∧„∧Hn是______，则称H1,H2,„Hn是相容的，若H1∧H2∧„∧Hn是______，则称H1,H2,„Hn是不相容的。

25.判断一个语句是否为命题，首先要看它是否为，然后再看它是否具有唯一的。

三、计算题(共30分)

26.(4分)设有向图G=(V,E)如下图所示，试用邻接矩阵方法求长度为2的路的总数和回路总数。

27.(5)设A={a,b},P(A)是A的幂集，是对称差

运算，可以验证

是群。设n是正整数，求({a}-1{b}{a})n{a}-n{b}n{a}n

28.(6分)设A={1,2,3,4,5},A上偏序关系

R={〈1，2〉，〈3，2〉，〈4，1〉，〈4，2〉，〈4，3〉，〈3，5〉，〈4，5〉}∪IA;

(1)作出偏序关系R的哈斯图

(2)令B={1,2,3,5}，求B的最大，最小元，极大、极小元，上界，下确界，下界，下确界。

29.(6分)求┐(P→Q)(P→┐Q)的主合取范式并给出所有使命题为真的赋值。

30.(5分)设带权无向图G如下，求G的最小生成树T及T的权总和，要求写出解的过程。

31.(4分)求公式┐((x)F(x,y)→(y)G(x,y))∨(x)H(x)的前束范式。

四、证明题(共20分)

32.(6分)设T是非平凡的无向树，T中度数最大的顶点有2个，它们的度数为k(k≥2),证明T

中至少有2k-2片树叶。

33.(8分)设A是非空集合，F是所有从A到A的双射函数的集合，是函数复合运算。证明：〈F, 〉是群。

34.(6分)在个体域D={a1,a2,„，an}中证明等价式：

(x)(A(x)→B(x))(x)A(x)→(x)B(x)

五、应用题(共15分)

35.(9分)如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而

且学过C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。

36.(6分)一次学术会议的理事会共有20个人参加，他们之间有的相互认识但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人?根据是什么?

参考答案

一、单项选择题(本大题共15小题，每小题1分，共15分)

1.B2.D3.A4.A5.D

6.D7.D8.C9.D10.B

11.A12.A13.C14.B15.C

二、填空题

16.0

117.10

18.单位元1

19.x∩yx∪y

20.入射满射

21.［x］R=［y］R

22.A(x)B(y)

23.(M(x)→D(x))M(x)→D(x)

24.可满足式永假式(或矛盾式)

25.陈述句真值

三、计算题

1100

26.M=1010

1011



0011

2110

M2=2111

2121



1011

4M2ij18,i4Mij26 1j1i

1G中长度为2的路总数为18，长度为2的回路总数为6。

27.当n是偶数时，x∈P(A),xn=

当n是奇数时，x∈P(A),xn=x

于是：当n是偶数，(｛a｝-1｛b｝｛a｝)n｛a｝-n｛b｝n｛a｝n

=(｛a｝-1)n｛b｝n｛a｝n=

当n是奇数时，(｛a｝-1｛b｝｛a｝)n｛a｝-n｛b｝n｛a｝n

=｛a｝-1｛b｝｛a｝(｛a｝-1)n｛b｝n｛a｝n

=｛a｝-1｛b｝｛a｝｛a｝-1｛b｝｛a｝=

28.(1)偏序关系R的哈斯图为

(2)B的最大元：无，最小元：无；

极大元：2，5，极小元：1，3下界：4，下确界4；

上界：无，上确界：无

29.原式(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q))

((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q))

(┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q))

(┐(P∧┐Q)∨(P∧┐Q))

(P∧Q)∨(P∧┐Q)

P∧(Q∨┐Q)

P∨(Q∧┐

Q)

(P∨Q)∧(P∨┐Q)

命题为真的赋值是P=1,Q=0和P=1,Q=1

30.令e1=(v1,v3),e2=(v4,v6)

e3=(v2,v5),e4=(v3,v6)

e5=(v2,v3),e6=(v1,v2)

e7=(v1,v4),e8=(v4,v3)

e9=(v3,v5),e10=(v5,v6)

令ai为ei上的权，则

a1

取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，T的总权和=1+2+3+4+5=1

531.原式┐(x1F(x1,y)→y1G(x,y1))∨x2H(x2)(换名)

┐x1y1(F(x1,y)→G(x,y1))∨x2H(x2)

x1y1┐(F(x1,y1)→G(x,y1))∨x2H(x2)

x1y1x2(┐(F(x1,y1)→G(x,y1))∨H(x2)

四、证明题

32.设T中有x片树叶，y个分支点。于是T中有x+y个顶点，有x+y-1 条边，由握手定理知

T中所有顶点的度数之的xy

d(vi)=2(x+y-1)。

i

1又树叶的度为1，任一分支点的度大于等于

2且度最大的顶点必是分支点，于是

xy

d(vi)≥x·1+2(y-2)+k+k=x+2y+2K-

4i1

从而2(x+y-1)≥x+2y+2k-4

x≥2k-2

33.从定义出发证明：由于集合A是非空的，故显然从A到A的双射函数总是存在的，如A

上恒等函数，因此F非空

(1)f,g∈F,因为f和g都是A到A的双射函数，故fg也是A到A的双射函数，从而集

合F关于运算是封闭的。

(2)f,g,h∈F,由函数复合运算的结合律有f(gh)=(fg)h故运算是可结合的。

(3)A上的恒等函数IA也是A到A的双射函数即IA∈F,且f∈F有IAf=fIA=f,故IA是〈F，〉中的幺元

(4)f∈F,因为f是双射函数，故其逆函数是存在的，也是A到A的双射函数，且有ff-1=f-1

f=IA,因此f-1是f的逆元

由此上知〈F，〉是群

34.证明(x)(A(x)→B(x)) x(┐A(x)∨B(x))

(┐A(a1)∨B(a1))∨(┐A(a2)∨B(a2))∨„∨(┐A(an)∨B(an)))(┐A(a1)∨A(a2)∨„∨┐A(an)∨(B(a1)∨B(a2)∨„∨(B(an))┐(A(a1)∧A(a2)∧„∧A(an))∨(┐B(a1)∨B(a2)∨„∨(B(an))┐(x)A(x)∨(x)B(x)(x)A(x)→(x)B(x)

五、应用题

35.令p：他是计算机系本科生

q：他是计算机系研究生

r：他学过DELPHI语言

s:他学过C++语言

t:他会编程序

前提：(p∨q)→(r∧s),(r∨s)→t

结论：p→t

证①pP(附加前提)

②p∨qT①I

③(p∨q)→(r∧s)P(前提引入)

④r∧sT②③I

⑤rT④I

⑥r∨sT⑤I

⑦(r∨s)→tP(前提引入)

⑧tT⑤⑥I

36.可以把这20个人排在圆桌旁，使得任一人认识其旁边的两个人。根据：构造无向简单图G=,其中V={v1,v2,„，V20}是以20个人为顶点的集合，E中的边是若任两个人vi和vj相互认识则在vi与vj之间连一条边。Vi∈V,d(vi)是与vi相互认识的人的数目，由题意知vi,vj∈V有d(vi)+d(vj)20,于是G

中存在汉密尔顿回路。

设C=Vi1Vi2„Vi20Vi1是G中一条汉密尔顿回路，按这条回路的顺序按其排座位即符合要求。

第四篇：离散数学试卷二十三试题与答案

试卷二十三试题与答案

一、单项选择题：（每小题1分，本大题共10分）

1．命题公式P(QP)是（）。

A、矛盾式；B、可满足式；C、重言式；D、等价式。

2．下列各式中哪个不成立（）。

A、x(P(x)Q(x))xP(x)xQ(x)；

B、x(P(x)Q(x))xP(x)xQ(x)；

C、x(P(x)Q(x))xP(x)xQ(x)；

D、x(P(x)Q)xP(x)Q。

3．谓词公式x(P(x)yR(y))Q(x)中的 x是（）。

A、自由变元；B、约束变元；

C、既是自由变元又是约束变元；D、既不是自由变元又不是约束变元。

4．在0 之间应填入（）符号。

A、=；B、；C、；D、。

5．设< A， > 是偏序集，BA，下面结论正确的是（）。

A、B的极大元bB且唯一；B、B的极大元bA且不唯一；

C、B的上界bB且不唯一；D、B的上确界bA且唯一。

6．在自然数集N上，下列（）运算是可结合的。

（对任意a,bN）

A、abab；B、abmax(a,b)；

C、aba5b；D、abab。

7．Q为有理数集N，Q上定义运算*为a*b = a + b – ab ,则的幺元为（A、a；B、b；C、1；D、0。

8．给定下列序列，（）可以构成无向简单图的结点度数序列。

A、（1，1，2，2，3）；B、（1，1，2，2，2）；

C、（0，1，3，3，3）；D、（1，3，4，4，5）。

9．设G是简单有向图，可达矩阵P(G)刻划下列（）关系。

A、点与边；B、边与点；C、点与点；D、边与边。

10．一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（A、5；B、7；C、9；D、8。

。）。）

二、填空：（每空1分，本大题共15分）

1．在自然数集中，偶数集为N1、奇数集为N2，则N1N2=；

N1N2 =。

2．设X{1,2,3,4},R{1,2,2,4，3,3}，则

r(R)=；s(R)= ；t(R)=。

3．设R为集合A上的等价关系，对aA，集合[a]R=，称

为

元

素

a

形

成的R

等

价

类，[a]R，因

为。

4．任意两个不同小项的合取为，全体小项的析取式为。

5．设Q(x):x为偶数，P(x):x为素数，则下列命题：（1）存在唯一偶素数；（2）至多有一个偶素数；分别形式化：（1）；

（2）。

6．设T为根树，若，则称T为m元树；

若则称T为完全m叉树。

7．含5个结点，4条边的无向连通图（不同构）有 个，它们是。

三、判断改正题：（每小题2分，本大题共20分）

1．命题公式(A(AB))B是一个矛盾式。（）2．任何循环群必定是阿贝尔群，反之亦真。（）3．根树中最长路径的端点都是叶子。（）4．若集合A上的关系R是对称的，则R



1也是对称的。（）

5．数集合上的不等关系（≠）可确定A的一个划分。（）6．设集合A、B、C为任意集合，若A×B = A×C，则B = C。（）7．函数的复合运算“。”满足结合律。（）8．若G是欧拉图，则其边数e合结点数v的奇偶性不能相反。（）9．图G为（n , m）图，G的生成树TG必有n个结点。（）10．使命题公式P(QR)的真值为F的真值指派的P、Q、R值分别是T、F、F。（）

四、简答题（每小题5分，本大题共25分）

1．设H,和K,都是群G,的子群，问HK,和HK,是否是

G,的子并说明理由。

3，4，9}，B{2，4，7，10,12}，从A到B的关系 2．设A{2，R{a,baA,bB,且a整除b}，试给出R的关系图和关系矩阵，并说明此

关系是否为函数？为什么？

3．设S,是半群，OL是左零元，对任xS,xOL是否是左零元？为什么？

4．某次会议有20人参加，其中每人至少有10个朋友，这20人拟围一桌入席，用图论知识说明是否可能每人邻做的都是朋友？（理由）

5．通过主合取范式，求出使公式(PQ)R的值为F的真值指派。

五、证明题：（共30分）

1．设R为集合A上的二元关系，如果R是反自反的和可传递的，则R一定是反对称的。

2．试证明若G,是群，HG，且任意的aH，对每一个xG，有axxa，则H,是G,的子群。

3．设G是每个面至少由k（k3）条边围成的连通平面图，试证明为结点数，e为边数。

4．符号化下列各命题，并说明结论是否有效（用推理规则）。任何人如果他喜欢美术，他就不喜欢体育。每个人或喜欢体育，或喜欢音乐，有的人不喜欢音乐，因而有的人不喜欢美术。答案

e

k(v2)k

2，其中v

一、单项选择题：

1．N

2;

。r(R){1,2,2,4,3,3,1,1,2,2,4,4}，2．

s(R){1,2,2,4,3,3,2,1,4,2}，RRR{1,4,3,3}，RRR{3,3}，RRR{3,3}，所以，t(R){1,2,2,4,3,3,1,4}。

3．[a]R{xxA,aRx}；a[a]R。4．永假式（矛盾式），永真式（重言式）。5．（1）x((Q(x)P(x))y(Q(y)P(y)xy))。（2）xy(Q(x)P(x)Q(y)P(y)xy)。

6．每个结点的出度都小于等于m；除叶子外，每个结点的出度都等于m。7．3。

三、判断改正题：

1．×命题公式(A(AB))B是一个重言式。2．×任何循环群必定是阿贝尔群，但反之不真。3．×根树中最长路径的端点不都是叶子。

4．√5．×≠不能确定A的一个划分。6．√7．√

8．×欧拉图其边数e和结点数v的奇偶性可以相反。9．√10．√

四、简答题

1．解：HK,是 G,的子群，HK,不一定是G,的子群。a,bHK,则的子群，a,bH,a,bK,由

H,和K,都是G,



ab



1H且ab

1

K,ab

1

HK,HK,是G,的子群。

如：G = {1，5，7，11}，：模12乘，则G,为群。且H = {1，5}，K = {1，7}，H,和K,皆为G,的子群，但HK{1,5,7}，HK,不是G,的子群。因为 5711HK，即运算不封闭。

2．解：R{2,2,2,4,2,10,2,12,3,12,4,4,4,12}则R的关系图为： R的关系矩阵为

10

00

1010

0000

1000

1110

M

R

关系R不是A到B的函数，因为

元素2，4的象不唯一（或元素9无象）

3．解：xOL仍是左零元。因为yS，由于OL是左零元，所以，OLyOL，又S,为半群，所以*可结合。

所以，(xOL)yx(OLy)xOL，所以，xOL仍是左零元。

4．解：可能。将人用结点表示，当两人是朋友时相应结点间连一条边，则得一个无向图

GV,E，20人围一桌，使每人邻做都是朋友，即要找一个过每个点一次且仅

一次得回路。由题已知，u,vV,deg(u)10,deg(v)10，deg(u)deg(v)20，由判定定理，G中存在一条汉密尔顿回路。即所谈情况可能。

5．解：

原式(PQ)R(PQ)R(PR)(QR)

(PQR)(PQR)(PQR)(PQR)M100M110M

010

∴使公式(PQ)R的值为F的真值指派为：

P:1



Q:0R:0；

P:1



Q:1R:0；

P:0



Q:1R:0。

五、证明题：

1．证明：假设R不是反对称的，则 x,yR,性，∴ x,xR 此与R反自反矛盾，∴R反对称。

y,xR,xy 由R的传递

2．证明：（1）设群G,的幺元为e，则xG有 xeex，∴eH即H非空。（2）a,bH，则 xG 有 axxa,bxxb，从而

(ab

1)x(ab

1

11)x(bb

1)

a(bb)xb

1

(ax)b

1

1

x(ab),abH

故 H,是G,的子群。

3．解：设连通平面图G有t个面：r1,r2,,rt则有 ver2，deg(ri)k,2k



tt

又有题意，deg(ri)kt

i1

又

e

deg(r)2e

i

i1，∴2ekt，teve

2k

e2

kk2

(v2)

。从而，∴。

4．解：设P(x)：x喜欢美术，Q(x)：x喜欢体育，R(x)：x喜欢音乐。论域：人。

命题形式化为：前提：x(P(x)Q(x))，x(Q(x)R(x))，xR(x)结论：xP(x)。证明：（1）xR(x)P(2)R(a)ES(1)(3)x(Q(x)R(x))P(4)Q(a)R(a)US(4)(5)Q(a)T(2)(4)I(6)x(P(x)Q(x))P(7)P(a)Q(a)US(6)(8)P(a)T(5)(7)I(9)xP(x)EG(8)∴ 结论有效。

第五篇：离散心得体会

离散数学心得体会

在学习离散数学之前，就听学过的学长学姐说：“离散数学特别难，老师上课用Ppt，一学期下来感觉会像天书一般被逻辑推理、各种关系公式以及图论彻底弄糊涂，但是这门课有特别重要尤其是对于计算机专业，所以要好好学习。”对于刚刚学过难懂的高数的我，心中很是没有底气学习这门学科，但是在这学期对于离散数学的学习之后，感觉与学长学姐所说的还是有相当大的差异。

离散数学本身对绝大多数学生来说是一门十分困难的课程，这个不可否认，但是通过这一学期的学习，我对这门课程有一些初步的了解，现在的心情和当初也很不相同。对于所有的学科而言都不会是很容易就能够很轻松的学懂并掌握，因此难于不难也是因人而异的。这其中很大一部分决定性原因则是在于对于一门学科的努力程度与投入时间的相对比例，在离散数学中概念绝对性的多，也非常的抽象难以理解，所以不经过多次反复的练习与巩固知识点，想在短时间内有飞速的提高是比非常还困难的。我认为离散数学的学习就应该按照预习听课复习并多次回顾的流程学习的基础上面，掌握一定的学习技巧和认真听取老师讲解时总结的方法，这样脚踏实地，离散数学也一定会学好，这门对记忆力、理解力和能力高度挑战的学科也自然会被更多的人喜爱。

通过这学期的学习，我对于离散数学的几点小总结是，离散数学一定要带着问题进行概念的学习和理解，这就有别于其他学科可以不预习直接听课，也会达到一定的学习效果，但是离散数学其中的概念如果不事先进行预习熟悉，直接上课听讲，一定会被弄的晕头转向，犹如老虎吃天无从下口，自然不会达到认真听讲的作用，所以预习是必不可少的对于离散数学；就像数理逻辑这部分的抽象知识一样，如果仅仅是上课听一下老师的讲解，然后置之不理，所学的知识点没有几天就会全部还给课本，这主要在于我们没有掌握离散数学中一些概念定理的实质，因此我们应该在听课的同时反复斟酌课本中的例子，再结合概念定理进行理解，这样才会做到知识的深入理解和较长期的记忆；离散数学学习中也一定要积极思考问题，尤其是在老师停下课程，让大家进行思考或者做练习时，这不仅说明这个知识点需要做更进一步的理解或者这个知识点的重要性，而更重要的是要锻炼培养我们的课堂思维能力，因此我们一定要认真仔细的跟着老师的引导积极思考；温故而知新，最后一定要有条理的进行定期总结回顾，这样不仅可以复习前面学习过可能忘记的知识点，还可以做到新旧知识点的融合，能够加深对于前面遗留问题的解决且为新知识的理解铺路；另一方面，我觉的我们学生必须掌握离散数学这门课程的重点和难点，一门课程肯定有其重难点，只有明确了重难点，我们才能更好的掌握该门课程。这仅仅是我一学期以来学习离散数学的几个属于自己的小总结，但是我认为在业精于勤荒于嬉是永远的真谛的同时，我们更应该加强现在学科方法的总结与思考里的锻炼。

我认为对于离散数学的学时确实有点少，高数课程一周要学习三节课，然而学习难度更胜一筹的离散数学却一周仅有两节课，大量的新知识点在有限的时间内全部抛出，让本来就对离散数学感觉恐慌的同学更加无法接受，自然学习的效果会有所降低，教学的目的在一定程度上面也不会达到。总之，这样相对较少的学时安排繁重的教与学的任务，不仅使老师增加授课压力，也使大多数同学们感觉学习离散数学的挑战性更大，也更加害怕学习，但是离散数学作为一门很重要的学科，如果学习不好，会对以后其他学科的学习造成一些隐性的阻碍。

对于我们的教材选用，我认为还是非常的好，但有点小问题就是例题太少，这也可能会减少授课时的学时，但对于部分难理解的章节，还是希望有更多的例题作为大家学习的引导，这样对于大家的课前预习与下课后的自主学习可能会好点，然后结合后面的作业题，大家反复练习可能会更容易理解与学习。

张老师手写板书为主、电子教案为辅的教学方式非常适用于离散数学这门课。在上了这学期的课之后，再重新与学长学姐的话进行对比，我认为像离散数学这门概念既多又抽象的学科，采取这种的教学方式，大家都更加容易理解知识点，能够更的上老师的讲课节奏、有思考的时间，更容易让大家产生学习兴趣。离散数学是我们计算机学科的一门很重要的专业基础课程,它在计算机科学中有着广泛的应用。面对学习离散数学概念较多，理论性强，定义、定理比较多,一时难以理解和记忆,不过张老师总能用容易能使学生接受的定义方式,对不同的定义、定理找出它们之间的相互联系，便于我们理解。兴趣是学习之母,学习任何一门科学,都需要有兴趣。有了兴趣,自然也就有了动力。张老师的教学，让我们在学习的同时也培养了我们的学习兴趣，有利于我们更好的理解概念定理。另外，离散数学概念繁杂，学起来难免有些枯燥，张老师也适当穿插介绍一些知识点在计算机学科专业中的应用,具有非常大的启发性。可以让我们了解离散数学的实际应用，增加学习兴趣。学习好一门课要老师和学生的配合，老师可以多多了解我们的学习状况，多多互动，活跃课堂气氛，有利于我们更好的相关知识定理。总之，学好离散数学课要双方的努力，更要双方的配合。张老师这次让全班同学都写建议，就是一个很好的互动，相信以后学习离散数学课的同学们会感觉到更加精彩的离散数学教学方式。

在这学期学习了离散数学这门课程，对于一个爱好数学的我来说，我是非常受益的。同时，离散数学作为一门与计算机学科相关的专业基础课，对我学专业知识也有很大的帮助。学习离散数学，可以培养我们的逻辑思维方式，对于我们学习计算机方向的学生来说是非常有用的。尤其是在计算机编程方面对逻辑思维就有一定的要求。离散数学这门课程，是一门比较难学的课程，它有太多的概念、定义，需要我们有很好的记忆力，但是要完全记住这么多的概念、定义是非常困难的。所以说我们在有好的记忆力之外，还要运用理解记忆的方法来解决，这样我们就不必花费过多的时间和精力去记忆这么多的概念和定义了。离散数学作为一门理科学科，在我看来最好的学习方法就是多动手、多做题，在做题得过程中，慢慢积累做题得经验，同时也可以对概念和定义有一个更深层次的理解。学习各个学科都有其各自的学习方法与思维方式，只有运用对了学习方法才能更好的学习这门课程。学习一门课程都是为了解决实际问题，学习离散数学也不例外。学通了一门课程才能在解决问题的时候不会走弯路。离散数学是一门比较难学的课程，在学习的过程中，也肯定会遇到许多的问题，但是通过反复的理解概念及做练习题和与其他同学的交流，最后还是会解决这些问题。学习离散数学的过程中，也有许多的乐趣。但在轻松学习的过程中，还得从中学到东西，学到道理。我在学习这门课程之后，对我的专业知识方面有了很大的帮助，让我的思维有了进一步的发散，使我在其他的学科中受益匪浅。

总之，通过这学期张老师讲解的离散数学课程，使我思考抽象问题的思维方式又得到了锻炼，能力有所提高，而且为以后专业课程的学习打下了良好的基础，最后非常感谢张老师这一学期的辛勤教学。