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

admin

第 1 页 （共 4 页）
学习中心/函授站_
姓 名 学 号
西安电子科技大学网络与继续教育学院
2021 学年上学期
《离散数学》期末考试试题
（综合大作业）
题号 一 二 三 四 总分
题分 20 20 40 20
得分
考试说明：
1、大作业试题于 2021 年 4 月 23 日公布：
（1）学生于 2021 年 4 月 23 日至 2021 年 5 月 9 日在线上传大作业答卷；
（2）上传时一张图片对应一张 A4 纸答题纸，要求拍照清晰、上传完整；
2、考试必须独立完成，如发现抄袭、雷同均按零分计；
3、资料须用《西安电子科技大学网络与继续教育学院标准答题纸》手写完成，要
求字迹工整、卷面干净。
一、 填空题（每空 2 分，合计 20 分）
1. 设 个 体 域 为 D  {2,3,6}, F(x): x  3 ， G(x): x  0 。 则 在 此 解 释 下 公 式
(x)(F(x)  G(x)) 的真值为______。
2. 设 p :我是大学生， q :我喜欢数学。命题“我是喜欢数学的大学生”为可符合化
为 。
3. 设 A  {1,2,3,4}， B  {2,4,6}，则 A B =________， A B =________。
4. 合式公式(Q  P)  P 是永______式。
5. 给定集合 A  {1,2,3,4,5}，在集合 A 上定义两种关系：
R  {1,3 , 3,4 , 2, 2 }, S  { 4,2 , 3,1 , 2,3 }，
第 2 页 （共 4 页）
则 R  S  _______________ ，S R  _______________ 。
6. 设e 是群G 上的幺元，若 aG 且 a
2  e ,则 a
1
=____ , a
2
=__________。
7． 公 式 (P  Q)  (P  (Q  S)) 的 对 偶 公 式
为 。
8. 设 A  {2,3,6,12},  是 A 上的整除关系，则偏序集 A, 的最大元是________，极小
元是_ _。
9. 一棵有 6 个叶结点的完全二叉树，有_____个内点；而若一棵树有 2 个结点度数为 2，一
个结点度数为 3，3 个结点度数为 4，其余是叶结点，则该树有_____个叶结点。
10. 设图G V,E , V {v1
, v2
, v3
, v4}，若 G 的邻接矩阵 ，




 
1 0 0 0
1 1 0 0
1 0 1 1
0 1 0 1
A
则 deg (v1 ) =________, =____________。 
4 deg (v )

二、选择题（每题 2 分，合计 20 分）
1．下列各式中哪个不成立（ ）。
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 。
2．谓词公式x(P(x)  yR( y))  Q(x) 中的 x 是（ ）。
A、自由变元； B、约束变元；
C、既是自由变元又是约束变元； D、既不是自由变元又不是约束变元。
3．集合的以下运算律不成立的是( )。
A． A B  B  A B． A B  B  A
C． A B  B  A D． A B  B  A
4. 公式xy(P(x, y)  Q( y,z))  xP(x, y) 换名（ ）。
A. xu(P(x,u)  Q(u,z))  xP(x, y)
B. xy(P(x,u)  Q(u,z))  xP(x,u)
C. xy(P(x, y)  Q( y,z))  xP(x,u)
第 3 页 （共 4 页）
D. uy(P(u, y)  Q( y,z))  uP(u, y) 。
5. 设集合 A ， B 是有穷集合，且 A  m , B  n ，则从 A 到 B 有（ ）个不同的双射函数。
A、 n ； B、 m ； C、 n! ； D、 m! 。
6．设 A  {a,b,c,d}， A 上的等价关系
R  { a,b , b,a , c,d , d,c }，
则对应于 R 的 A 的划分是（ ）
A．{{a},{b,c},{d}} B．{{a,b},{c},{d}}
C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}
7. 设 A  {1,2,3,4}，则 A 上的二元关系有（ ）个。
A． B. C． D． 4 2
2 4
4 4 2
 2 2 4

8．下面集合（ ）关于减法运算是封闭的。
A、N ； B、{2x x  I} ； C、{2x 1 x  I} ； D、{x x是质数}。
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 ，如果它的所有结点的度数都是偶数，那么它具有一条( )
A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路
三、计算题（每题 8 分 合计 40 分）
1． 写出命题公式( p  q)  (p  q)的真值表。
2． 集 合 A &#61501; {2 , 3 , 6 , 12 , 24 , 36}上 的 偏 序 关 系 |为 整 除 关 系 。 设 B &#61501; { 6 , 12}， C &#61501; { 2 , 3 , 6}，试画出<A, |>的哈斯图，并求集合 B 和 C 中关于|的极大元、最大元、
第 4 页 （共 4 页）
下界和下确界。
3. 求命题公式&#61656;(P &#61657; Q) &#61611; &#61656;(&#61656 &#61614; R) 的主析取范式。
4.求下图所示的边赋权图的一棵最小生成树。
5. 已知某有向图的邻接矩阵如下： 试求： 到 的长度为 4 的有
1
2
3
4
0 0 1 0
0 0 1 1
1 1 0 1
0 1 1 1
v
v
A
v
v
&#61670; &#61686;
&#61671; &#61687; &#61501;
&#61672; &#61688;
3 v 1 v
向路径的条数。
四 证明题（每题 10 分， 合计 20 分）
1. 设论域 D 为全总个体域，谓词 G(x)：x 是研究生，T(x)：x 是推荐免试者，K(x)：x 是统
考选拔者。在谓词逻辑中符号化下列各命题，推证结论的有效性。
“所有的研究生或者是推荐免试者或者是统考选拔者；并非所有的研究生都是推荐免试
者。结论：有些研究生是统考选拔者。”
2. &#61500; G,* &#61502; 是一个群, u &#61646;G ，定义G 中的运算“ &#61508; ”为 a&#61508;b &#61501; a *u &#61485;1*b ，对任意 a,b&#61646;G ，
求证：&#61500; G,&#61508; &#61502; 也是个群。