离散数学 练习题五

___ 离散数学 练习题五 ：号座_______________ _：题 号 学 _ _ _ __答_ _ _ _ _ _ ： 名要姓 级 班不 _ _ _ _ _ _ _ __内_ _ _ _ _ _ _ 业 专线 _ _ _ __封_ _ _ _ _ 密 院学_______________—— —— —题 号 一 二 三 四 总分 ——得 分 ——阅卷人 —— — 线—得 分 一、单项选择题（每小题2分，共40分）

— — —6. 令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为什么。 ——1. 无向图G中有16条边，且每个结点的度数均为2，则结点数是多少。 （ ） A．p→┐q B．p∨┐q

（ ）

—— A.8 B.16 C.4 D.32 C．p∧q D．p∧┐q

———2. 设A={b,e,f}，则下列哪个是集合A的划分。 （ ） 7. 在个体域D={a,b}中，指出与公式(?x)A(x)等价又不含量词的公式。 （ ）

——— A.{b,e,f} B.{{b,e},{b,f}} C.{{b},{e ,f}} D.{b,{e,f}} A.A(a)∧A(b) B.A(a)→A(b) C.A(a)∨A(b) D.A(b)→A(a) —封—3.设集合X={0,1,2,3}R是X上的二元关系，R={<0,0>,<0,2>,<1,2>,<1,3>,<2,0>,<2,1>,<3,3,>}，8. 指出下列是命题的句子。

（ ） ——则哪个是R的关系矩阵MR。 （ ） A.今天出太阳了吗? B.Y>3.14

——?010?1??10? C.再过8000年，地球上就没生命了。 D.我在说谎话。

—?1010??—A．?1100?011???0000??11011?—?1? B.??1100?? C. ?101?01?? D. ?0?001?? 9. 给定算式: (((a＋(b＊c))＊d－e)÷(f＋g))＋((h＊i)＊j)找出与此算式对应的波兰符号表示—?000??1 0—?0011????0001???01?1110???0?1010??式。

（ ）

———4. 下列说法错误的是。 （ ） A.－＊＊a＋bc＋def－g＊hij＊＊ B.abc＊＋d＊e－fg＋÷hi＊j＊－ ——密 A．{?}??(?) B．???({?}) C.＋÷－＊＋a＊bcde＋fg＊＊hij D.ab＋c＊de＋＊fgh＊－＋ij＊－

——— C．?(?)?{?} D．?(?)??({?}) 10．设N是自然数集，函数 f: N→N×N. f(n)＝﹤n,n＋1﹥,f({6})是什么。 （ ） — A．满射函数 B．单射函数 C．{<6,7>} D．双射函数

——5. 从下列图中找出欧拉图。 （ ） 11. 已知(p→q)←→r的主合取范式是M0∧M2∧M5∧M6，指出与其对应的主析取范式。 —— — A．m1∧m2∧m5∧m7 B．m1∨m3∨m4∨m7 （ ）

—— C．M0∧M3∧M5∧M6 D．M1∨M3∨M5∨M6

第 1 页 共 4 页

___ 12. 设T(x)：x具有性质T，S(y)：y具有性质S。命题“对于任意的x，若x有性质T，则19. 设有集合A={a,b,c},?为空集，则下列哪一个表示是正确的。

（ ）

：号座_______________ _：题 号 学 _ _ _ __答_ _ _ _ _ _ ： 名要姓 级 班不 _ _ _ _ _ _ _ __内_ _ _ _ _ _ _ 业 专线 _ _ _ __封_ _ _ _ _ 密 院学_______________———x有性质S“的符号化形式是什么。

（ ）

——— A. ?x (T(x)→S(x)) B. ?x T(x)→?y S(y) ——— C .

?x (T(x)∧S(x)) D .?xT(x)→?y? S(y)

———13. 判断下列各非负整数列哪个不是可图化的。

（ ）

线— A .(5,5,4,4,2,3) B. (4,4,2,1,3) C .(5,4,3,2,2) D .(3,3,1,1)

———14. 设Z,N分别为整数和自然数集，函数g: Z→N, g(x)＝|2x|, g是什么函数。（ ）———A．双射函数 B．满射非单射 C．单射非满射 D． 以上答案都不对 ——15. 设V={a,b,c,d}，则与V能构成强连通图的边集合是下面4个中哪一个。 （ ）——A．E={（a,d）,(b,a),(b,d),(c,b),(d,c)} ———B．E={ (a,d),(b,a),(b,c),(b,b),(d,c)} —封C．E={ (a,c),(b,a),(b,c),(d,a),(d,c)} ——D．E={ (a,d),(a,c),(a,d),(b,d),(c,d)}

——16. 设G是连通平面图，G中有6个顶点8条边，则G的面的数目是多少。 （ ） ——— A. 2个面 B. 3个面 C. 4个面 D. 5个面

——17. 设A={a,b,c,d}，B={1,2,3,4}，以下哪一个关系是从A到B的双射函数。（ ） ———

——— A．f={,,,} B．f={,,,} 密— C．f={,,,} D．f={,}

———18. 设P：2是素数，Q：3是素数，R：2是有理数，下列复合命题中假命题为哪

———一个。 （ ）

——A．（P∨Q）→R B． R→（P∨Q） ——C．（P∧Q）→P D．（R∨P）?Q

A．{a}∈A

B．{a} ? A

C．a ? A

D．?∈A

20. 称由前提A1，A2,….. Ak推出结论B的推理正确，则A1∧A2∧….. ∧Ak→B应为下列表述中的哪一个。

（ ）

得 分 A．重言式或可满足式 B．可满足式 C．矛盾式 D．重言式

二、填空题（每空2分，共20分）

1. ┐(┐p→(q∨r))的成真赋值为 。 2. (p∧q)→r的主合取范式为 。

3. 设A={2,3,6,12},≤是A上的整除关系，则偏序集〈A，≤〉的最大元是_______。 4. 设A={φ,{φ}},B={0,1},从A到B的双射函数有________个。

5. 设G是完全二叉树，G有15个点，其中8个叶点，则G的分枝点数为________________ 。 6. 一棵无向树有2个4度顶点，3个3度顶点，其余的都是树叶，则该树有 片树叶。 7．设A={a,b,c}，B={1,2,3}，则A到B共可产生_____________个不同的双射函数。 8. 某公司有销售人员82人，维修人员191人，既做销售又搞维修的人员20人，既非销售

人员又非维修人员有912人，则该公司总人数为______。

9. 下图中结点V1的度数为____。

V2 V3 V1 V6 V5 V4 10．设个体域是{a,b,c}，则(?x)S(x)等价于命题公式__________

第 2 页 共 4 页

___：号座_______________ _：题 号 学 _ _ _ __答_ _ _ _ _ _ ： 名要姓 级 班不 _ _ _ _ _ _ _ __内_ _ _ _ _ _ _ 业 专线 _ _ _ __封_ _ _ _ _ 密 院学_______________ —得 分

— —三、计算与应用题（6小题，共26分）

—— 1. 在偏序集中，其中Z={1,2,3,4,6,8,12,24}，≤是Z中的整除关系。 ——(1). 求集合D={2,3,4,6}的极大元，极小元；（2分） ——— —— 线— —— ———(2). 求集合D={2,3,4,6}的最大元，最小元；（2分） —— —— —— —— —封— ——(3). 求集合D={2,3,4,6}的最小上界和最大下界。 (2分)

—— ——

— —— — —— ——2. 有向图D如下图所示，写出D的邻接矩阵（2分）。 密—— —— — v4v3—— — — —v5— v1v23．设7个字母在通信中出现的频率如下: a: 35%, b: 20%, c: 15%, d: 10%, e: 10%, f: 5%, g: 5%.

(1). 编一个最佳2元前缀码。 (3分)

(2). 在这个前缀码中,a,b,c,d,e,f,g的码长分别是多少? (1分)

(3). 传输10000个按上述比例出现的字母需要多少个二进制数字。(2分)

4. S={ 1，2，…，10 }，定义S上的关系R={ | x,y∈S ∧ x+y=10 }， 试列举出R中的所有有序对，并分析说明R具有哪些性质。（4分）

第 3 页 共 4 页

_____座号：___ ————— 5. 求公式?(?(p→q))∨(?q→?p)的主合取范式。（4分）

得 分 四、证明题（2小题，共14分）

1. 设f:A→B,g:B→C是两个函数，证明： 若f⊙g是满射且g是单射，则f是满射。（6分） __________ _：题 号 学 _ _ _ __答_ _ _ _ _ _ ： 名要姓 级 班不 _ _ _ _ _ _ _ __内_ _ _ _ _ _ _ 业 专线 _ _ _ __封_ _ _ _ _ 密 院学_______________—— —— —— —线 ——— —— —— —— —— ——— —封6. 判断推理是否正确（4分）

—— 若小李是文科学生，则他爱看电影。小李不是文科学生。所以，他不爱看电影。—— — —— — —— — —— — —密 — —— — —— — —— — —

2.

第 4 页 共 4 页

在自然推理系统P中，用归谬法证明下面推理。（8分）前提：p→(q→r),p∧q 结论：r∨s