离散30-answer

江苏技术师范学院20 —20 学年第 学期 《离散数学》试卷（30）参考答案与评分标准

一、单项选择题（本大题共10道小题，每小题2分，共20分）

1. A,B,C是三个集合，下列推理正确的是（ A ）。

A. AB,BC => AC B. AB,BC => A∈B C. A∈B,B∈C => A∈C D. A∩B=A∩C => B=C

2. 设p：天下雨，q：我骑车上班；则命题“只有天不下雨，我才骑车上班”可符号化为（ C ）。

A. pq B. qp C. qp

D. pq

3. A={a,b,c},A上关系R={(a,a),(a,b),(c,a)}，R的自反闭包为（ B ）。

A. {(a,a),(a,b),(c,a)} B.{(a,a),(a,b),(c,a),(b,b),(c,c)} C. {(a,a),(b,b),(c,c)} D.{(a,a),(a,b),(c,a),(b,a),(a,c)} 4. 设A={a,{a}}，下列命题错误的是（ B ）。

A. {a}P(A) B. {a}P(A) C. {{a}}P(A)

D. {{a}}P(A)

5. 设M(x): x是人；F(x)：x会犯错误；则“人都会犯错误”可符号化为（ B ）。A. xM(x)F(x) B. x(M(x)F(x)) C. xM(x)F(x) D. x(M(x)F(x))

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

1．设Ea,b,c,d,e,f Aa,b Ba,c,d则～A∪～B= {b,c,d,e,f} 。

2．一个集合A上的关系R是偏序关系，如果R是自反的、反对称的 、传递的。 3.设T是树，T有10个结点，则T的总度数是 18 。

4.设F(x,y):x>y,G(x,y):x3，则3<4”符号化为 F(2,3)→G(3,4) 。5.设Z是整数集，在Z上定义二元运算*为a*b=a+b+a·b，其中+和·是数的加法和乘法，则代数系统的零元是 -1 。

《离散数学》试卷30答案 第 1 页 共 5 页

6．设有向图G(n,m)图是一完全图，则m n(n-1)/2 。 7．R是实数集合，代数系统的单位元是 0 。

8．谓词公式yx(P(x)→R(x,y))∧yQ(x,y)，x的辖域是 P(x)→R(x,y) 。 9．集合A={1,2,„,10}上的关系R为整除关系，则R为___偏序_______关系。 10. 设个体域为有理数集Q，则谓词公式yxxyx的真值是 。

三、判断题（本大题共10小题，每小题1分，共10分）

正确的打“√”，错误的打“×” 1. （×）下图是欧拉图。

2. （×）设A,B为无限集，则AB还是无限集。

3. （×）设A是有限集合,有n个元素,则其幂集P(A)有2n+1个元素。 4. （×）“本语句是假的”是命题。

5. （√）S={1,2,3,„,100}，S上关系R＝{∣xy(mod 3)且x,yA}，则R是等价关系。

6. （×）在自然数集N上，定义运算*：a*b=min(a,b)，运算*是不可结合的。 7. （×）对任何图，奇度结点的个数均为奇数。 8. （×）﹁x(A(x)∧B(x))x(A(x)→B(x))。 9. （√）命题公式P(QP)是重言式。 10. （×）群中的元素未必有逆元。

四、证明题（本大题共3小题，第1小题6分，第2-3小题各8分，共22分） 1.设A、B、C是三个集合，证明：A－(BC)＝(A－B)－C

证明：A－(BC)= ABC=A(BC)=(AB)C=(A-B)C=(A-B)-C （6分）

《离散数学》试卷30答案 第 2 页 共 5 页

2.在谓词逻辑中符号化下述命题，并推证之。 凡人都要呼吸，王瑞是人，所以王瑞要呼吸。

解：令 F(x): x是人, G(x): x要呼吸, a: 王瑞 （2分） 前提：x(F(x)G(x))，F(a)

结论：G(a) （2分） 证明：（1）F(a) 前提引入 （2）x(F(x)G(x)) 前提引入 （3）F(a)G(a) ②UI

（4）G(a) ①③假言推理 （4分）

3. Z上的二元运算*定义为：a,bZ，a*b=a+b-2。试证：为群。 证明：

（1）a,b,cZ，(a*b)*c=(a*b)+c-2=(a+b-2)+c-2=a+b+c-4, a*(b*c)=a+(b*c)-2=a+(b+c-2)-2=a+b+c-4，

故(a*b)*c=a*(b*c)，从而*满足结合律。 （2分） （2）记e=2。对aZ，a*2=a+2-2=a=2+a-2=2*a.。故e=2是Z关于运算*的单位元。

（2分）

（3）对aZ，因为a*（4-a）=a+4-a-2=2=e=4-a+a-2=(4-a)*a。故4-a是a关于运算*的逆元。 （2分） 综上所述，为群。 （2分）

五、计算、应用题（本大题共6小题，1-4，6小题各6分，第5小题8分，共38分）

1． 设有一棵树，它有两个结点度数为3，三个结点度数为2，一个结点度数为4，其余结点度数均为1，问它有几个结点度数为1？

解：设有x片树叶,2*3+3*2+1*4+x*1 =2*（2+3+4+x-1），28+x=16+2x 解得x=12，故T有12片树叶。（6分）

《离散数学》试卷30答案 第 3 页 共 5 页

2． 有十个人参加聚会，每个人都认识其中的7个，问能否安排坐在一个圆桌上，使每个人认识与坐在他两边的人是认识的？为什么？ 解：可以。（2分）

将每个人对应成相应的顶点，若两人认识，则对应的两个顶点间连上一条无向边，作出一个简单无向图。由已知，图中每个顶点的度数都等于7，故图中任两个不相邻的顶点的度数和14大于等于10，即顶点数。故这个图是一个哈密尔顿图，从而存在哈密尔顿回路。任取一条哈密尔顿回路，按回路经过的顶点的次序安排对应的人的座位，就可以了。（4分）

3． 求Q(Q→R)的主析取范式及主合取范式。 解：Q(Q→R)Q( Q R)(QQ)R

T(主合取范式)（3分）

(QR)(QR)(QR)(QR)（主析取范式）（3分）

4． 有100名程序员，其中47名熟悉C++语言，35名熟悉JAVA语言，23名熟悉这两种语言。问有多少人对两种语言都不熟悉？ 解：47+35-23=59，100-59=41。 （6分）

5． 设G是具有四个节点的有向图，它的邻接矩阵表示如下

00 001011010011 10（1） 画此图并说明该图共有几条边？（2分）

（2） G是单向连通还是强连通？（2分）

（3） 分别求出从v4到v4长度小于4的回路条数及从v1到v2、 从v1到v3、

v1到v4长度是3的通路数。（4分） 解：（1）图G如下：（1分）

《离散数学》试卷30答案 第 4 页 共 5 页

1 2 4 3

该图共有7条边。（1分） （2）G单向连通的 （2分） （3）2,2,1,2 （4分）

6． 求出下图的最小代价生成树，要求写出步骤。

解：

（6分）

《离散数学》试卷30答案 第 5 页 共 5 页