西安电子科技大学网络与继续教育学院 2019 学年下学期 《离散数学》期末考试试题

admin

第 1 页 （共 4 页）

学习中心/函授站_



姓 名 学 号



西安电子科技大学网络与继续教育学院
2019 学年下学期
《离散数学》期末考试试题
（综合大作业）
题号 一 二 三 四 总分
题分 20 20 40 20
得分





考试说明：
1、大作业试题于2019 年10 月17 日公布，2019 年10 月18 日至2019 年11 月3 日
在线上传大作业答卷（最多上传10 张图片，一张图片对应一张A4 纸答题纸），要求拍照清晰、
上传完整；
2、考试必须独立完成，如发现抄袭、雷同均按零分计；
3、答案须用《西安电子科技大学网络与继续教育学院标准答题纸》手写完成，要
求字迹工整、卷面干净。



一 填空题（每小题 2 分，合计 20 分）
1. 合式公式(q  p)  p 的为真的赋值有_____ .
2. 谓词公式(x)(P(x, y)  Q(x, y))  P(y, x) ，则其约束变元是________，自由变元是
________。
3. 设 A  {1,2,3,4}，B  {2,4,6}，则 A  B =________， A B =________。
4.公式(P  R)  (S  R)   的主合取范式为 。
5. 设 f : R  R, f (x)  x  3 , g : R  R,g(x)  2x 1,则 复 合 函 数
( f  g)(x)  ____________ , (g f )(x)  __________________ 。
6. 设 A  {2,3,6,12},  是 A 上的整除关系，则偏序集 A, 的最大元是________，极小


第 2 页 （共 4 页）

元是________。
7. 设e 是群G 上的幺元，若a G 且a2  e ,则a1 =____ , a2 =__________。
8.设 <G,*>是 由 元 素 a  G 生 成 的 循 环 群 ， 且 |G|=n， 则 G
= 。
9. 一棵有 6 个叶结点的完全二叉树，有_____个内点；而若一棵树有 2 个结点度数为 2，一
个结点度数为 3，3 个结点度数为 4，其余是叶结点，则该树有_____个叶结点。
10.无向图 Km,n 是一个完全二部图，当且仅当满足 时，G 是一个欧拉图。
当满足 时，Km,n 是一个汉密尔顿图。
二 选 择（每题 2 分，合计 20 分）
1．下列语句中为命题的是（　　　）
A．这朵花是谁的？ B．这朵花真美丽啊！
C．这朵花是你的吗？ D．这朵花是他的。
2.设 p ：天下大雨, q ：他在室内运动,命题“除非天下大雨，否则他不在
室内运动”可符合化为（　　　）
A. p  q B. p  q C. p  q D. p  q
3．下列命题公式为重言式的是（　　　）
A．q  ( p  q) B． p  ( p  q)
C．( p  q)  p D．( p  q)  q
4．下列是两个命题变元 p，q 的极大项是（ ）
A． p  q  q B．p  q
C．p  q D．p  p  q
5．设M (x) ：x 是人；F(x) ：x 要吃饭。用谓词公式表达下述命题：所有的人都要吃饭，
其中错误的表达式是（　　　）
A．(x)(M (x)  F(x)) B．(x)(M (x)  F(x))
C．(x)(M (x)  F(x)) D．(x)(M (x)  F(x))
6．集合的以下运算律不成立的是( )。
A． A B  B  A B． A B  B  A
C． A B  B  A D． A  B  B  A
7. 设无向图中有 6 条边，有一个 3 度顶点和一个 5 度顶点，其余顶点度为 2，则该图的顶点
数是（　　　）
A．3 B．4 C．5 D．6
8．设 A  {a,b,c, d}， A 上的等价关系
R  { a,b , b, a , c, d , d,c }，


第 3 页 （共 4 页）

则对应于R 的 A 的划分是（　）
A．{{a},{b,c},{d}} B．{{a,b},{c},{d}}

C．{{a},{b},{c},{d}} D．{{a,b},{c, d}}
9． 设 集 合 X  {0,1, 2,3}， R 是 X 上 的 二 元 关 系 ，
R  { 0,0 , 0, 2 ,1,2 ,1,3 , 2,0 , 2,1 , 3,3 } ，则 R 的关系矩阵 MR 是
( )

A． B.
























0 0 1 1

0 0 0 1

1 1 0 0

1 0 1 0

























0 0 0 1

1 1 0 0

0 0 1 1

1 0 1 0

C. D.
























1 1 1 0

0 1 0 1

1 0 1 0

0 0 0 1

























1 0 1 0

0 0 0 1

0 0 1 1

1 1 1 0

10．连通图 G 是一棵树，当且仅当G 中（　）
A．有些边不是割边 B．每条边都是割边
C．无割边集 D．每条边都不是割边
三 计 算（每题 10 分 合计 40 分）
1．构造命题公式( p  q)  (p  q) 的真值表。
2. 求公式( p  q)  (q  r) 的主析取范式。
3. 设 A  {1,2,3,4}， A 上的等价关系 R  {1,2 , 2,1 , 3,4 , 4,3 } IA ，画出
R 的关系矩阵，并求出 A 中各元素的等价类。
4. 求下图的一颗最小生成树。


第 4 页 （共 4 页）



四 证明题（每题 10 分 合计 20 分）
1. 用谓词逻辑符号化以下命题，并推证结论的有效性。
“任何人如果他喜欢美术，他就不喜欢体育。每个人或喜欢体育，或喜欢音乐，有的人
不喜欢音乐，因而有的人不喜欢美术。”
2. 设 R 是集合 A 上的二元关系，如果对于任意的 a, b, c∈A，若 aRb 且 bRc，则有 cRa，那
么称 R 是循环的。
证明：R 是等价关系当且仅当 R 是自反的和循环的。