.
离散数学综合练习题一
一、单项选择题（每题2分 ）16 %
设P：王强是南方人，Q：他怕热．命题“王强不怕热是因为他是南方人”符号化为 ( )
(A)P?Q(B)P??Q(C)Q?P(D)?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且f(x)?3x，则f是 ( )
(A) 单射，非满射 (B) 满射,非单射 (C) 双射 (D) 非单射，非满射 6. 设E为全集, A, B为非空集，且B?A，则空集为（ ）
(A) AIB (B) :AIB (C) AI:B (D) :AI:B 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. 无向图K3,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))的消去量词后为
。
.
.
?1?
3. 设有向图D＝
?0??0210?010??，那么|E|= 。 001?
?
010?
4. n阶m条边的无向连通图G，要确定G的一棵生成树T必须删去G中的边数是 。
5. 设集合A={a,b,c}，R为A上的关系，R={
6.设G是n阶无向简单哈密顿图,则对于任意不相邻的顶点vi,vj均有d(vi)?d(vj)?n, 此结论正确吗? 答 。
7. 设X?{1,2,3,4},Y?{a,b,c},f?{?1,a?,?2,b?,?3,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，画出偏序集
4. （10分）已知有向图D如右图所示，求（1）邻接矩阵A (D)；（2）D是哪类连通图, 为什么?（2）D中从v3到v2长度是2的通路数；（3）D中从v2到v2长度是3的回路数。
jibcgfdv3v4ahev1v25. （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)原式=(?p??q?r)?(?p?q?r)?(p??q??r)?(p??q?r)?M2?M3?M4?M6 成假赋值为：010，011，100，110
2. (6分)解：设3度顶点为x个，则阶数n?8?2?x?10?x，边数m?n?1?9?x，由握手定理得2m?18?2x??ni?1d(vi)?1?8?3?2?3?x?14?3x，解得x?4，于是
n?8?2?4?14。
3. (8分)解：哈斯图如下图，极大元：18,60 极小元：2,3,5；最大元和最小元均无。
6018126420910325?2211??2543??1211?3
??2
??, A(D)= A ×A= ?2432? ?1221??3533??????0111??2211?
从矩阵A(D)和A2(D)中可知， 从v3到v2长度等于2的通路数有2条, 从v2到v2长度等于3的回路数有4条。
强连通图, 因为存在经过每个顶点至少一次的回路.
?0?
4. 解：A(D)=?0
?1??1
111?
2110??，A(D)= A ×A=
101?
?
000?
.
.
5．(10分)解：树枝有5条，分别是a,b,e,f,h，基本割集系统{S1,S2,S3,S4,S5}
S1={a,c,i,j}, S2={b,c,i}, S3={e,c,d,i,j}, S4={f,c,d,g}, S5={h,g,i,j}
6．(10分) 解： 设1到1000的整数构成全集U，用ABC分别表示能被5，6，8整除的数构成的集合，
如左面文氏图所示：则有S?{xx???1?x?1000}，
AB15025100A?{xx?S?x 能被5整除}， 1783367B?{xx?S?x 能被6整除}CC?{xx?S?x 能被8整除}
A?1000/5?200，B?1000/6?166，C?1000/8?125， AIB?1000/lcm(5,6)?33，AIC?1000/lcm(5,8)?25， BIC?1000/lcm(6,8)?41，AIBIC?1000/lcm(5,6,8)?8 AIBIC?S?A?B?C?AIB?AIC?BIC?AIBIC
?1000?200?166?125?33?25?41?8?600 四、证明题（共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 ⑥⑦析取三段论
.
，
离散数学期末考试含答案
