当前位置:首页 >> 数学 >> 离散数学-2005`2006(2)-试卷A

离散数学-2005`2006(2)-试卷A


一、基础知识(40 分) 1.判断下列句子是否是命题,若是命题将其符号化。 (4 分) ①.李平虽然聪明,但不用功。 ②.除非你陪伴我或代我雇辆车子,否则我不去。 2.在一阶逻辑中将下列命题符号化。 (4 分) ①.任何自然数不是奇数就是偶数,偶数均能被 2 整除,奇数均不能被 2 整 除。 ②.任意实数的平方都不小于 0。 3.求下列集合的幂集。 (4 分) ①.A={φ,{φ

}} ②.B={{φ,a},{a}} 4.设 f,g,h∈RR,且有 f(x)=x+3,g(x)=2x+1,h(x)=x/2。 求 g?g,h?f,g?h,f?h,f?h?g.(6 分) 5.设集合 A={0,1,2,3,4},定义 A 上的二元关系 R 为: R={<x,y>?x,y?A?(x=y?x+y?A)},请写出二元关系 R 的集合表达式,并判 断 R 具有的性质。 (6 分) 6.已知图 G 中有 10 条边,4 个 3 度顶点,其余顶点的度数均小于等于 2,则 G 中至少有多少个顶点?(4 分) 7.在下面各图中,哪些是欧拉图,哪些是哈密尔顿图?(4 分)

8.设代数系统<A,*>,其中 A={a,b,c},A 上的二元运算*定义如下表:

请分析*运算的封闭性、交换性、等幂性。A 中关于*是否有幺元和零元?如 有幺元,每个元素是否有逆元?如有,求出逆元。 (8 分) 二、理解运用(30 分) 9.证明逻辑等价式 A?B? (A∧B)∨(┐A∧┐B)成立。 (6 分) 10. 求下列命题公式的主析取范式和所有成假赋值。
( p ? (q ? r )) ? ( p ? q ? r ) (6 分)

11. 求谓词公式

的前束范式。 (6 分)

12. 令 A={1,2,3,4,5,6}, 画出偏序集<A,整除>的哈斯图,并求 (1)集合 A 的最大元、最小元、极大元和极小元; (2)集合 B={2,3,6}的上界、下界、最小上界、最大下界。 (6 分) 13. 求带权图 1 的最小生成树及权(6 分)

图1

三、综合能力(30 分) 14. 用推理理论证明下面结论是否有效? 如果今天是星期三,那么我有一次离散数学或数字逻辑测验。如果离散 数学课老师有事,那么没有离散数学测验。今天是星期三且离散数学老 师有事。所以,我有一次数字逻辑测验。(10 分) 15. 某班有 25 个学生,其中 14 人会打篮球,12 人会打排球,6 人会打篮球和 排球,5 人会打篮球和网球,还有 2 人会打三种球。而 6 个会打网球的人都 会打另外一种球(指篮球或排球) ,求不会打这三种球的人数。 (10 分) 16. 设 7 个英语字母在通信中出现的频率如下: a:35%,b:20%,c:15,d:10%,e:10%,f:5%,g:5% 设计一个最佳 2 元前缀码。使通信中出现的二进制数字尽可能少,并计算 传输 104 个按上述比例出现的字母需要多少个二进制数字。 (10 分) 答案及评分参考(A 卷) 1.①是命题。(1 分)用 p 表示“李平聪明” ,q 表示“李平用功” ,则符号化为 p∧﹁q。(1 分) ②是命题。(1 分)可表示为(p∨q) ? r(1 分),其中 p:你陪伴我,q:你代我雇车,r:
我去

2.①设 O(x):x 是奇数,N(x):x 是偶数,E(x):x 是偶数,D(x):x 能被 2 整 除。则原句可符号化为:(2 分)
?x( N ( x) ? O( x) ? E ( x)) ? ?x( E ( x) ? D( x)) ? ?x(O( x) ? ?D( x))

②取论域为实数域, 可设 L(x,y):x 小于 y,f(x):x 的平方。则可符号化为:
?x?L( f ( x),0) (2 分)

3.①ρ(A)={φ ,{φ },{{φ }},{φ ,{φ }}}(2 分) ②ρ(B)={ φ ,{{φ ,a}},{{φ }},{{φ ,a},{a}}}(2 分) 4. g ? g(x)=g(g(x))=2(2x+1)+1=4x+3;(1 分) h ? f(x)=h(f(x))=1/2(x+3);(1 分) g ? h(x)=g(h(x))=2· x/2+1=x+1;(1 分)

f ? h(x)=f(h(x))=x/2+3;(1 分) f ? h ? g(x)=f(h(g(x)))=(2x+1)/2+3=x+7/2; (2 分) 5. R=IA?{<0,1>,<1,0>,<0,2>,<2,0>,<0,3>,<3,0>,<0,4>,<4,0>,<1,2>,<2,1>,<1,3>,<3,1>} (2 分) 易知,R 具有自反性(2 分)和对称性(2 分)。 6.图 G 中边数 m=10,由握手定理可知,G 中各顶点度数之和为 20,4 个 3 度 顶点占去 12 度,还剩 8 度,若其余全是 2 度顶点,还需要 4 个顶点来占用这 8 度,所以 G 至少有 8 个顶点。(4 分) 7. (3)为欧拉图(1 分);(2),(3),(4)是哈密尔顿图。(3 分) 8.*运算是封闭的,因为表中每个元素都属于 A。(1 分) *运算可交换,因运算表关于主对角线对称。(1 分) *运算不等幂,因运算表主对角线有的元素与所在行列表头元素不同。(1 分) *运算有零元 c,因为 c 所在行列中的元素都是与它相同。(1 分) *运算有幺元 a,因为 a 所在行列中的元素依次与表头行列一致。(2 分) a 和 b 均以自身为逆元,因为 a、b 所在行和列交汇处的元素为幺元。(2 分) 9.A?B?(A→B)∧(B→A)
?(┐A∨B)∧(┐B∨A) (2 分) ? (┐A∧┐B)∨(┐A∧A)∨(B∧┐B)∨(B∧A) (2 分) ? (A∧B)∨(┐A∧┐B) (2 分)

(注:此题证法不唯一,用其他方法也可) 10.解 把原命题公式记为 A,则

(2 分)

。(2 分)

A 的所有成假赋值为 011,100,101,110。(2 分)

11.

??xF ( x) ? ?yG( x, y) ? ?(??xF ( x)) ? ?yG( x, y) ? ?x?F ( x) ? ?yG( x, y)

(3 分)
? ?x?F ( x) ? ?yG( z, y) ? ?x?y(?F ( x) ? G( z, y)) (3 分) 12.哈斯图如下:

(2 分) (1)集合 A 无最大元,最小元是 1,极大元是 4、5、6,极小元是 1。(2 分) (2)集合 B 的上界是 6,下界是 1,最小上界是 6,最大下界是 1。(2 分) 13.所求最小生成树如下图所示

(4 分)

图2

W(T)=18 (2 分) 14. 证明:设 p:今天是星期三。q:我有一次离散数学测验。 r:我有一次数字逻辑测验。s:离散数学课老师有事。 该推理就是要证明:p→(q∨r),s→?q,p∧s?r (2 分) ⑴p∧s P (1 分) ⑵p T⑴化简律(1 分) ⑶s T⑴化简律(1 分) ⑷s→?q P(1 分) ⑸?q T⑶⑷假言推理(1 分) ⑹p→(q∨r) P(1 分) ⑺q∨r T⑵⑹假言推理(1 分) ⑻r T⑸⑺析取三段论(1 分) 15.设会打排球、网球、篮球的学生集合分别为 A,B 和 C,则 |A|=12,|B|=6,|C|=14,|S|=25,|A∩C|=6,|B∩C|=5,|A∩B∩C|=2。 |A∩B|=3(5 分) (5 分) 16.解:将所有的频率都乘 100,所得结果按从小到大顺序排列:(2 分) , , , , , , 。

以以上各数为权,用 Huffman 算法求一棵最优树,见下图所示。(2 分)

对照各个权可知各字母的前缀码如下:(4 分) a:10,b:01,c:111,d:110,e:001,f:0001,g:0000, 于是,a,b 的码长为 2,c,d,e 的码长为 3,f,g 的码长为 4。 (各分支点的权之和), 用的二进制数,因而传输 二进制数字。(2 分) 是传输 100 个按给定频率出现的字母所 个

个按上述频率出现的字母要用


更多相关文档:

...2006学年第二学期《离散数学》期末考试试卷(A卷)

2005安徽大学 2005-2006 学年第二学期 离散数学》期末考试试卷( 《离散数学》期末考试试卷(A 卷)一、选择题(每小题 2 分,共 20 分) 1.在自然数集 N 上...

《离散数学A》试卷

《离散数学》试卷A&答案 7页 2下载券 离散数学期末试卷(A) 9页 2下载券 离散数学(二)试卷A 4页 1下载券 离散数学-2005`2006(2)-... 2页 2下载券喜欢...

05-06(2)《离散数学》期末考试试卷(A)

北 京交通大学 2005 -2006 学年第二学期《离散数学(B)》期末考试试卷 学年第学期《离散数学( ) 期末考试试卷 考试试卷(A) 一、判断题(每题 1.5 分) (...

2006离散数学a(答案)

离散数学-2005`2006(2)-... 2页 2下载券 2006-2007《离散数学》期... 5...2006 年下半年《离散数学》 (闭卷)70 学时 离散数学( 离散数学(A卷)闭卷...

05-06(1)《离散数学》期末考试试题(A)

北 京交通大学 2005-2006 学年第一学期《离散数学》期末考试试卷(A) 学年第一学期《离散数学》期末考试试卷 考试试卷( )一、填空题(共 16 分,每空 2 分)...

06-07(2)《离散数学》期末考试试题(A)

06-07(2)离散数学》期末考试试题(A) 北京交通大学的离散数学考试试卷北京交通大学的离散数学考试试卷隐藏>> 北 京交通大学 2006-2007 学年第二学期 软件学院 ...

《离散数学》期末考试卷05-06(2)

安徽大学 2005-2006 学年第二学期 《离散数学》期末考试试卷(A 卷)(时间 120 分钟) 年级 院系专业 姓名 学号 座位号 题号 得分 一 二 三 四 五 六 七 ...

VFP试卷2005-2006-2(A)

2005-2006第二学期试卷A 6页 免费 2005—2006学年度第二学期... 3页 10财富值 离散数学-2005`2006(2)-试... 3页 5财富值喜欢此文档的还喜欢 ...

04-05(2)《离散数学》期末考试试卷(A)

离散数学期末考试试卷(A卷... 6页 免费 离散数学-2005`2006(2)-试... 2...北京交通大学的离散数学考试试卷北京交通大学的离散数学考试试卷隐藏>> 北京交通大学...

2005-2006(1A)离散数学期末试卷答案

安徽大学 2005-2006 学年第一学期 离散数学》期末考试试卷( 卷答案) 《离散数学》期末考试试卷(A 卷答案)一、选择题(2 × 10=20 分) 3. {φ , {φ ,...
更多相关标签:
离散数学试卷 | 离散数学试卷及答案 | 广工离散数学试卷 | 离散数学期末试卷 | 南昌大学离散数学试卷 | 2015离散数学期末试卷 | 离散数学试卷分析 | 大学离散数学试卷 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com