浙江农林大学暨阳学院 2016 - 2017 学年第 二 学期考试卷答案
课程名称： 离散数学 课程类别： 必修 考试方式： 闭卷 适用专业： 计算机151-152
注意事项：1、本试卷满分100分。

2、考试时间 120分钟。

一、单项选择题（在每小题的四个备选答案中，选出一个正确答案， 并将正确答案的选项填在题后的括号内。

每小题2分，共8分） 1. 公式q p p ⌝→⌝→)(的类型是 ( C ) A. 重言式 B. 矛盾式
C. 非重言式的可满足式
D. 以上均不对
2. |A |=n , |B |=m , 且m , n >0, 则|B A |= ( D )
A.m 2
B. 2n
C. n m
D. m n
3. 集合的广义并}},{},,,{},,,{{d a d c a c b a ⋃= ( B )
A.},,{c b a
B.},,,{d c b a
C.},,{d c a
D.}{a
4. f ：R→R, f (x )=-x 2+2x -1，则f 是 ( D ) A. 单射 B. 满射
C. 双射
D. 以上均不对
系（部）
： 专业班级： 姓名： 学号： 装 订 线 内 不 要 答 题
二、填空题（每小题3分，共36分）
1. 令p:吴颖用功, q:吴颖聪明，吴颖既用功又聪明符号化为__q p ∧_____
2. 如果2 <1,则23≥的真值为___1___
3. (q →p ) ∧q →p 的成真赋值为 ___00,01,10,11_ __
4. (p →⌝q)→r ⇔ 13567m m m m m ∨∨∨∨的成假赋值为__000,010,100_
5. 设A 有3个命题变项, 且已知A=
m 2∨m 4∨m 5∨m 6，A 的主合取范式为 ___7310M M M M A ∧∧∧=
6. 设D 为人类集合，G(x)：x 用左手写字，则一阶逻辑中命题有人用左手写字符号 化为__)(x xG ∃__ _
7. 给定解释 I 如下：
(a) 个体域 D=R (b) 0a =
(c) (,),(,)f x y x y g x y x y =+=⋅ (d) (,):F x y x y = 则公式∀xF (g (x ,y ),a ) 在I 下的解释为__)0(=⋅∀y x x _____ 8. R = {<1,2>, <2,3>, <1,4>, <2,2>}，S = {<1,1>, <1,3>, <2,3>, <3,2>, <3,3>}， 则S ︒R = __{1,2,1,4,3,3,3,2}<><><><>__
9. 设R={<1,2>,<1,3>,<2,2>,<2,4>,<3,2>}, 则R ↾{2} = ___}4,2,2,2{><><___ 10. 设R 为A 上的关系, 则有R 的对称闭包s(R)=__ 1-⋃R R ____ 11. 设G=<V ,E>为任意无向图，V={v 1,v 2,…,v n }, |E|=m, 则 _m 2___
12. 无向图G 是欧拉图当且仅当__ G 是连通图且无奇度顶点
三、名词解释（每小题3分，共18分）
1. R 为 A 上递推关系的定义为： 设R 为A 上的关系,若
),,,,,(R z x R z y R y x A z y x z y x >∈→<>∈<∧>∈<∧∈∀∀∀
则称R 为A 上的传递关系
2. R 为A 上的偏序关系的定义为：
如果R 是自反的、反对称的和传递的，则称R 为A 上的偏序关系
3. F 为单射函数的定义为：
=∑=n
i i v d 1
)(
若ranF y ∈∀都存在唯一的A x ∈使得y x F =)(，则称B A F →:是单射的
4. 简单图的定义为：
既不含平行边也不含环的图称为简单图 5. 欧拉通路的定义为：
通过图（无向图或有向图）中所有边一次且仅一次行遍所有顶点的通路称为欧拉图 6. 哈密顿回路的定义为：
经过图中所有顶点一次且仅一次的回路称作哈密顿回路
四、证明题（每小题5分，共20分） 1. 用等值演算法证明0)(⇔→∧⌝q q p
解:))(()(q q p q q p ∨∧⌝⌝⇔→∧⌝ （蕴含等值式）
))(q q p ⌝∧∧⇔ （德摩根律） )(q q p ⌝∧∧⇔ （结合律） 0∧⇔p （矛盾律）
0⇔ （零律）
2. 用附加前提证明法去构造下面推理的证明： 如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。

所以，当小赵去看电影时，小李也去。

证明：设p ：小张去看电影q ：小王去看电影 r ：小李去看电影 s ：小赵去看电影 前提：r q p →∧)(，p s ∨⌝，q
结论: r s → 用附加前提证明法
① s 附加前提引入 ② p s ∨⌝ 前提引入 ③ p ①②析取三段论 ④ r q p →∧)( 前提引入 ⑤ q 前提引入 ⑥ q p ∧ ③⑤合取引入 ⑦ r ④⑥假言推理
3. 证明 A -B = A ⋂~B 证明：对于任意的x ，有
B x A x B A x ∉∧∈⇔-∈ B x A x ~∈∧∈⇔ B A x ~⋂∈⇔ 所以A -B = A ⋂~B
4. 设F 是任意的关系, 证明F F =--11)( 证明：任取><y x ,,由逆的定义有
F y x F x y F y x >∈⇔<>∈⇔<>∈<---,)(,)(,111
所以有F F =--11)(
五、计算题（每小题6分，共18分） 1. 求公式 A=(p →⌝q)→r 的主合取范式 解：(p →⌝q )→r
⇔ (p ∨r )∧(q ∨r ) （合取范式） ①
p ∨r
⇔ p ∨(q ∧⌝q )∨r
⇔ (p ∨q ∨r )∧(p ∨⌝q ∨r )
⇔ M 0∧M 2 ②
q ∨r
⇔ (p ∧⌝p )∨q ∨r
⇔ (p ∨q ∨r )∧(⌝p ∨q ∨r )
⇔ M 0∧M 4 ③ ②③代入① 得 (p →⌝q )→r ⇔ M 0∧M 2∧M 4 （主合取范式）
2. 有向图D 如图所示，试求D 中长度为2的通路各有多少条?其中回路分别为多少条?
解：D 的邻接矩阵为
⎪⎪⎪⎪⎪⎭⎫
⎝
⎛=01
00100101000021A ,⎪⎪⎪⎪
⎪⎭
⎫ ⎝
⎛=10
010*********
212
A 分
从D 的邻接矩阵的2次幂可以看出，D 中长度为2的通路共有13条 其中回路有3条
3. 对于集合A=}24,12,8,6,4,3,2,1{与整除关系写出偏序关系并画出相应的哈斯图 解:偏序关系为：
A
I ⋃><><><><><><><><><><><><><><><><><><><><><><}24,12,24,8,24,6,12,6,24,4,12,4,8,4,24,3,12,3,6,3,24,2,12,2,8,2,6,2,4,2,24,1,12,1,8,1,6,1,4,1,3,1,2,1{
哈斯图为:
…………6分
1
2
3
6
4
12
8
24。