离散数学试卷

诚信应考,考试作弊将带来严重后果！华南理工大学期末考试 《离散数学》试卷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={,,},g={,,}，则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={，，，}，则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={，，，，，}，求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分）

离散数学试卷2

离散数学试卷1

离散数学试卷二十三试题与答案

离散数学试题

离散 2

离散心得体会

离散数学论文

离散数学试题A卷

离散数学考试范围

离散数学考试大纲

《离散数学试卷.doc》

将本文的Word文档下载到电脑，方便编辑。

推荐度：

点击下载文档