离散数学综合练习题一
一、单项选择题（每题2分 ）16 %
设P ：王强是南方人，Q ：他怕热．命题“王强不怕热是因为他是南方人”符号化为 ( ) (A)(B)()(D)P Q P Q C Q P Q P →→⌝→⌝→
2 设F (x )：x 是熊猫，G (y )：y 是竹子，H (x ,y )：x 喜欢y. 那么命题“有些熊猫喜欢各种的竹子”符号化为 ( )
(A) (()(()(,)))x F x y G y H x y ∃→∀∧ (B) (()(()(,)))x F x y G y H x y ∃→∀→ (C) (()(()(,)))x F x y G y H x y ∃∧∀→ (D) (()(()(,)))y x F x G y H x y ∀∃→∧
3. 命题公式()p q p →∧⌝是 ( )
(A) 重言式 (B) 矛盾式
(C) 可满足式 (D) 以上3种都不是
4. 设集合A ＝{a,b,{c,d,e}}则下列各式为真的是 ( )
(A) ∈A (B) c ∈A (C) {c,d,e} A (D) {a,b}A
5. 设函数 :f N N →且()3x f x =，则f 是 ( )
(A) 单射，非满射 (B) 满射,非单射 (C) 双射 (D) 非单射，非满射
6. 设E 为全集, A , B 为非空集，且BA ，则空集为（ ）
(A) A B I (B) A B :I (C) A B I : (D) A B :I :
7. 设A ={0,1,2,3}，A 上的关系R ={<0,1>,<0,2>,<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}，则R 是 ( )
（A ）自反的 （B ）对称的 （C ）反对称的 （D ）可传递的
8. 无向图K 3,3是（ ）
（A ）哈密顿图 （B ）欧拉图 （C ）完全图 （D ）平面图
二、填空题（每空2分）18 %
1. 设():F x x 是火车，():G y y 是汽车，H (x,y )：x 比y 快，则命题“说所有火车比有的汽车快是不对的”符号化是 ，
其另一种等值形式为 。

2. 设个体域D ={a,b },公式 (()(())x F x y G y ∃∧∀的消去量词后为。

3. 设有向图D ＝<V ,E >的邻接矩阵为A (D )=12100
010********⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦
，那么|E |= 。

4. n 阶m 条边的无向连通图G ，要确定G 的一棵生成树T 必须删去G 中的边数是 。

5. 设集合A ={a ,b ,c }，R 为A 上的关系，R ={<a ,b >,<b ,a >,<c ,c >}，则R 的传递闭包()t R 是 。

6.设G 是n 阶无向简单哈密顿图,则对于任意不相邻的顶点i v ,j v 均有()()i j d v d v n +≥, 此结论正确吗 答 。

7. 设{1,2,3,4},{,,},{1,,2,,3,}X Y a b c f a b c ===<><><>，则“f 是从X 到Y 的函数”的真值为 。

8. 命题“整数列（2,2,3,3,4,4）可简单图化”的真值为 。

三、化简计算题 56 %
1. （12分）用等值演算法求公式()()p q p r ∨→∧的主合取范式，并求成假赋值。

2. （6分）一棵无向树T 有8片树叶，2个3度支点，其余的分支点都是小于4度顶点，问T 至少有几个顶点。

3. （8分）对于集合A ＝{2,3,4,5,6,9,10,12,18,20,60}与整除关系R ，画出偏序集<A,R >的哈斯图，并求A 的极大元、极小元、最大元、最小元。

4. （10分）已知有向图D 如右图所示，求（1）邻接矩阵A (D )；（2）D 是哪类连通图, 为什么（2）D 中从v 3到v 2长度是2的通路数；（3）D 中从v 2到v 2长度是3的回路数。

5. （10分）右图所示无向图G 中，实线边所示子图为G 的一棵生成树T ，求G 对应T 的基本割集系统。

6. （10分）求在1和1000之间(包含1和1000在内)不能被5或6整除, 也不能被8整除的数的个数。

(必须写出解题过程)
四、证明题 10 %
（10分）在自然推理系统中构造下面推理的证明:
若张超和李志都是计算机系学生，则王红是中文系学生；若王红是中文系学生，则她爱看小说；可是王红不爱看小说；张超是计算机系学生；所以李志不是计算机系的学生。

离散数学综合练习题一（答案）
一、 单项选择题（每题2分，共16分）
（1）B （2）C （3）C （4）D （5）A （6）B （7）D （8）A
二、 填空题 （每空2分，共18分）
1．(()(()(,)))x F x y G y H x y ⌝∀→∃∧，(()(()(,)))x F x y G y H x y ∃∧∀→⌝
2． (()())()()F a F b G a G b ∨∧∧ 3． 7 4．m-n+1
5．{,,,,,,,,,,}a b b a a a b b c c <><><><><>
6．不正确 7． 0 （或假） 8． 1 （或真）
三、化简计算题（共56分）
1.(10分)解：主合取范式：
)()()()()()()()()()()()()p q p r p q p r p q p r p p p r q p q r p r p q q r ∨→∧⇔⌝∨∨∧⇔⌝∧⌝∨∧⇔⌝∨∧⌝∨∧⌝∨∧⌝∨⇔⌝∨∧∨⌝∧⌝∨（ ()()()
()()()()()()
p r p q q r p q r p q r p q p q r r p q r p q r q r p p q r p q r p q r ⌝∨⇔⌝∨⌝∧∨⇔⌝∨⌝∨∧⌝∨∨∨⌝⇔∨⌝∨⌝∧⇔∨⌝∨⌝∧∨⌝∨⌝∨⇔⌝∧∨⌝∨⇔⌝∨⌝∨∧∨⌝∨
原式=2346()()()()p q r p q r p q r p q r M M M M ⌝∨⌝∨∧⌝∨∨∧∨⌝∨⌝∧∨⌝∨=∧∧∧ 成假赋值为：010，011，100，110
2. (6分)解：设3度顶点为x 个，则阶数8210n x x =++=+，边数19m n x =-=+，由握手定理得12182()18323143n
i i m x d v x x ==+=≤⨯+⨯+⨯=+∑，解得4x =，于是
82414n =++=。

3. (8分)解：哈斯图如下图，极大元：18,60 极小元：2,3,5；最大元和最小元均无。

3
10
925
20 4. 解：A (D )=0111011011011000⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦，A 2(D )= A ×A = 2211121112210111⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦, A 3(D )= A 2 ×A = 2543243235332211⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦
从矩阵A (D )和A 2(D )中可知， 从v 3到v 2长度等于2的通路数有2条, 从v 2到v 2长度等于3的回路数有4条。

强连通图, 因为存在经过每个顶点至少一次的回路.
5．(10分)解：树枝有5条，分别是a,b,e,f,h ，基本割集系统{S1,S2,S3,S4,S5}
S 1={a,c,i,j}, S 2={b,c,i}, S 3={e,c,d,i,j}, S 4={f,c,d,g}, S 5={h,g,i,j}
6．(10分) 解： 设1到1000的整数构成全集U ，用ABC 分别表示能被5，6，8整除的数构成的集合，
如左面文氏图所示：则有{11000}S x x x =∈Z∧≤≤，{ }A x x S x =∈∧能被5整除， { }
B x x S x =∈∧能被6整除，
{ }C x x S x =∈∧能被8整除 1000/5200A ==，1000/6166B ==，1000/8125C ==， 1000/(5,6)33A B lcm ==I ，1000/(5,8)25A C lcm ==I ， 1000/(6,8)41B C lcm ==I ，1000/(5,6,8)8A B C lcm ==I I 10002001661253325418600
A B C S A B C A B A C B C A B C
=---+++-=---+++-=I I I I I I I
四、证明题（共10分）
（8分）设p ：张超是计算机系学生 q ：李志是计算机系学生 r ：王红是中文系学生 s ：王红爱看小说
前提：(),,,p q r r s s p ∧→→⌝ 结论： q ⌝
证明：① r s → 前提引入
② s ⌝ 前提引入
③ r ⌝ ①②拒取式
④ ()p q r ∧→ 前提引入
⑤ ()p q ⌝∧ ③④拒取式
⑥ p q ⌝∨⌝ ⑤置换
⑦ p 前提引入
⑧ q ⌝ ⑥⑦析取三段论。