离散数学21秋西电模拟题答案一
西安电子科技大学网络教育2010学年上学期期末考试试题
课程名称：__离散数学 考试形式： 闭 卷
学习中心：_________ 考试时间：90分钟
姓 名：_____________ 学 号：
一 填空题（每空2分，合计20分）
1. 合式公式 是永______式.
2.设 ：它占据空间， ：它有质量， ：它不断运动， ：它叫做物质。命题“占据空间的，有质量的而且不断运动的叫做物质”的符号化为 。
3. 设个体域为 ， ， 。则谓词公式 的真值为______。
4.公式 的对偶公式为 。
5. 命题公式 的成假赋值为__________。
6. 给定集合 ，在集合 上定义两种关系：
,，
则 ， 。
7.若 是函数，则当 是 的 ， 是 的逆函数。
8.若连通平面图 共有 个面，其中 ，则它满足的Euler公式为 。
9.命题公式 的主合取范式为 ，其编码表示为 。
二 选择（每题2分，合计20分）
1. 下列结果正确的是（ ）。
A、 ；B、 ；C、 ；
D、 。
2. 在（ ）下有 。
A、 ；B、 ；C、 ；D、
3. 若公式 的主析取范式为则它的主合取范式为（）
A． ； B. ；
C. ； D. 。
4. 命题“尽管有人聪明，但未必一切人都聪明”的符号化
（ ： 是聪明的， ： 是人）（）
A.
B.
C.
D.
5. 设集合 ， 是有穷集合，且 ，则从 到 有（）个不同的双射函数。
A、；B、； C、； D、。
6．设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是（ ）
A．3 B．4 C．5 D．6
7．连通非平凡的无向图G有一条欧拉回路当且仅当图G ( )。
A、只有一个奇度结点；B、只有两个奇度结点；
C、只有三个奇度结点；D、没有奇度结点。
8．设无向图 是连通的且若（）则G是树。
A、M=N+1 ； B、n=m+1 ； C、； D、。
9．n个结点的无向完全图 的边数为（）。
A、； B、； C、； D、 。
10．下列图中（）是根树。
A、；
B、；
C、；
D、。
三 计算（每题8分， 合计40分）
1．设A={1，2，3，4，5}，A上的偏序关系如下图所示，求A的子集{3，4，5}和{1，2，3}，的上界，下界，上确界和下确界。
2.求 的主合取范式。
3.求图中的一个最小生成树。
4. 将公式 划为只含有联结词 的等价公式。
5. 已知某有向图的邻接矩阵如下： 试求： 到 的长度为4的有向路径的条数。
四 证明题（每题10分， 合计20分）
1.令 ，定义映射g： 为 ，试证：g是 到 的自同构映射。
2.用CP规则证明 ， ， 。
西安电子科技大学网络教育
2010学年上学期期末考试答题纸
课程名称：__离散数学 考试形式： 闭 卷
学习中心：_________ 考试时间：90分钟
姓 名：_____________ 学 号：
题号 一 二 三 四 总分
题分 20 20 40 20
得分
一 填空题（每空2分，合计20分）
1 0 2 3 0 4
5 1,1 6 7 双射 8
9 ；
二 选择（每题2分，合计20分，在正确答案上划√）
1 A √ C D 2 A B C √ 3 A √ C D
4 A B √ D 5 A B C √ 6 A √ C D
7 A B C √ 8 A √ C D 9 A B C √
10 A B √ D
三 计算（每题8分 合计40分）
1．
{3，4，5}：上界：1，3；上确界：3；下界：无；下确界：无；
{1，2，3}：上界：1；上确界：1；下界：4；下确界：4。
2.
3. 用Kruskal算法，选一条权最小的边，逐一选取剩余的边中与已知边未构成回路且权数最小的边 ，每次选出的边记入T,其权加入T的成本。
T的边 T的成本
2
2+2
2+2+2
2+2+2+2
2+2+2+2+3
2+2+2+2+3+3
4.
原式
。
5.
，，，
，由 到 长度为4的有向路径的条数为3条。
四 证明题（每题10分 合计20分）
1.
①是<R ，+ >上的同态映射 ，
②是<R ，+ >上的满射，使所以g是<R ，+ >上的满射。
③是<R ，+ >上的单射，，且则 ，如果
则这与矛盾。
故。 由①，②，③知g是从<R ，+ >到<R ，+ >的自同构映射。
2.
（1）B P(附加前提)
（2） P
(3) T(1)(2)I
(4)A T(3)I
(5) P
(6) T(4)(5)I
(7)C T(6)I
(8) P
(9) T(7)(8)I
(10) T(9)E
(11)E T(10)I
(12) CP
页:
[1]