离散数学期末考试试题(配答案)
一.填空题(每小题2分,共10分)
1. 谓词公式∀xP (x ) →∃xQ (x ) 的前束范式是__ ∃x ∃y¬P(x)∨Q(y) __________。 2. 设全集E ={1, 2, 3, 4, 5}, A ={1, 2, 3}, B ={2, 5}, 则A ∩=_{4,5}____,
=3. 设A ={a , b , c }, B ={a , b },则ρ(A ) -ρ(B ) =__ {{c},{a,c},{b,c},{a,b,c}} __________,
ρ(B ) -ρ(A ) =_____Φ_______。
4. 在代数系统(N ,+)中,其单位元是0,仅有有逆元。 5.如果连通平面图G 有n 个顶点,e 条边,则G 有___e+2-n____个面。 二.选择题(每小题2分,共10分)
1. 与命题公式P →(Q →R ) 等价的公式是( )
(A )(P ∨Q ) →R (B )(P ∧Q ) →R (C )P →(Q ∧R ) (D )P →(Q ∨R ) 2. 设集合A ={a , b , c },A 上的二元关系R ={, }不具备关系( ) 性质 (A ) (A)传递性 (B)反对称性 (C)对称性 (D)自反性 3. 在图G =中, 结点总度数与边数的关系是( ) (A)deg(v i ) =2E (B) deg(v i ) =E (C)
∑deg(v ) =2E (D) ∑deg(v ) =E
i
i
v ∈V
v ∈V
4. 设D 是有n 个结点的有向完全图, 则图D 的边数为( ) (A)n (n -1) (B)n (n +1) (C)n (n +1) /2 (D)n (n -1) /2 5. 无向图G 是欧拉图, 当且仅当( )
(A) G 的所有结点的度数都是偶数 (B)G的所有结点的度数都是奇数
(C)G 连通且所有结点的度数都是偶数 (D) G连通且G 的所有结点度数都是奇数。 三.计算题(共43分)
1. 求命题公式p ∧q ∨r 的主合取范式与主析取范式。(6分)
解:主合取方式:p ∧q ∨r ⇔(p∨q ∨r) ∧(p∨¬q ∨r) ∧(¬p ∨q ∨r)= ∏0.2.4
主析取范式:p ∧q ∨r ⇔(p∧q ∧r) ∨(p∧q ∧¬r) ∨(¬p∧q ∧r) ∨(¬p∧¬q∧r) ∨(p∧¬q∧r)= ∑1.3.5.6.7
⎛1 1
2. 设集合A ={a , b , c , d }上的二元关系R 的关系矩阵为M R =
0 0⎝
(10分)
r (R ), s (R ), t (R ) 的关系矩阵,并画出R ,r (R ), s (R ), t (R ) 的关系图。
000⎫
⎪
011⎪
, 求⎪000⎪
001⎪⎭
3 无向图G 有12条边,G 中有6个3度结点,其余结点的度数均小于3,问G 中至少有多少个结点?(10分)
解:∵G (V ,E ),| E |=V,d (Vi )8 故G 中至少有9个节点。
4 求下面两个图的最小生成树。(12分)
5. 试判断(z , ) 是否为格?说明理由。(5分)
解:(Z, ≤)是格,理由如下:
对于任意a ∈Z ,a ≤a 成立,满足自反性;
对于任意a ∈Z ,b ∈Z ,若a ≤b 且b ≤a ,则a=b,满足反对称性; 对于任意a ,b ,c ∈Z ,若a ≤b ,b ≤c ,则a ≤c ,满足传递性;
而对于任意a ,b ∈Z ,a ≤b ,b 为最小上界,a 为最大下界,故(Z ,≤)是格。
(注:什么是格?
四.证明题(共37分)
)
1. 用推理规则证明A →B , (⌝B ∨C ) ∧⌝C , ⌝(⌝A ∧D ) ⇒⌝D 。(10分)
证明: 编号 (1) (2) (3) (4) (5) (6) (7) (8)
公式 (¬B∨C )∧¬C ¬B∨C ,¬C ¬B A →B ¬A ¬(¬A∧D ) A ∨¬D ¬D 依据 前提 (1) (2) (3) (3)(4) 前提 (6) (5)(6)
2. 设R 是实数集,f :R ⨯R →R , f (a , b ) =a +b ,g :R ⨯R →R , g (a , b ) =ab 。求证:f 和g 都是满射,但不是单射。(10分)
证明:要证f 是满射,即∀y ∈R, 都存在(x1,x2)∈R ×R ,使f (x1,x2)=y,而f (x1,x2)=x1+x2,可取x1=0,x2=y,即证得;
再证g 是满射,即∀y ∈R ,, 都存在(x1,x2)∈R ×R ,使g (x1,x2)=y,而g (x1,x2)=x1x2,可取x1=1,x2=y,即证得;
最后证f 不是单射,f (x1,x2)=f(x2,x1)取x1≠x2,即证得,同理:g (x1,x2)=g(x2,x1),取x1≠x2,即证得。
3. 无向图G 有9个结点,每个结点的度数不是5就是6,求证:G 中至少有5个6度结点或6个5度结点。(10分)
证明:设G 中至多有4个6度结点且5个5度结点, ∴d (Vi )=49不是偶数, 故它不是一个图,矛盾。 (下面只供参考,个人答案)
4. 设平面上有100个点,期中任意两点间的距离至少是1,则最多有300对点距离恰好为1。(7分)
证明:设任意两点间的读书和恰好为1,则满足: ∑d (Vi )=2e d (Vi )≤6 ∴6×100≥2e e ≤300
故最多只有300条边,即300对点距离恰好为
1.
相关文章
- [离散数学]期末试题及答案
- 电大离散数学集合论部分期末复习题
- 传感器原理及应用期末试题3
- 郑州大学信息计量学期末考试整理答案
- 信息论基础]试卷(期末A卷
- 离散数学第五版 模拟试题 及答案
- 20**年超星尔雅慕课景观地学答案期末答案
- 统计学导论知识点归纳总计期末
- 浙江省教师招聘考试小学数学考试大纲
326<离散数学>期末考试题(B) 一.填空题(每小题3分,共15分) 1. 设A ={{a , b },a , b , ∅},则A -∅ = ( ) ,A -{∅} = ( ) ,P (A ) 中的元素个数|P (A ) |= ...
一.单项选择题 1.若集合A ={ a,{a },{1,2}},则下列表述正确的是( ) . A .{a ,{a }}∈A B .{1,2}∉A C .{a }⊆A D .∅∈A 正确答案:C 2.若集合A ={1,2},B ={1,2,{ ...
传感器原理及应用期末试题 一.判断题.(本题共10分,对则打"√",不对则打"×") 1.A/D转换就是把模拟信号转换成连续的数字信号.() 2.固有频率fn=400Hz的振动子的工作频率范围为f & ...
文献计量学: 1).洛特卡经验规律: a .是揭示文献著者与数量关系的基本定律. b .数字表达式为:f(x)=c/x的平方,x 表示科学工作者发表的论文数量,f(x)表示发表x 篇论文的著者出现的频率.上式也称倒数平方定律.发表一篇论文的 ...
试题编号: 重庆邮电大学2007/2008学年2学期 <信息论基础>试卷(期末)(A 卷)(半开卷) 一.填空题(本大题共10小空,每小空1分,共20分) 1. 按信源发出符号所对应的随机变量之间的无统计依赖关系,可将离散信源分 ...
<离散数学>模拟试题3 一. 填空题(每小题2分,共20分) 1. 已知集合A ={φ,1,2},则A 得幂集合p (A ). 2. 设集合E ={a , b , c , d , e }, A = {a , b , c }, B ...
景观地学 本试题与你的试题对不上怎么办?第 7 页有解决方案 同学请注意,所有超星慕课考试题最后 都是从以前做的课后练习中抽出来的, 所以就不要再找什么期末考试题了. 最 好的 办法就是将课后练习题全部下载下来, 考试的的时候再你懂的. * ...
第一章 1.统计学的定义: 统计学是一门关于数据的科学,是一门关于数据的收集.整理.分析.解释和推断的科学. 2.统计的三种含义: a.统计工作(又称统计实践)是搜集.整理.分析和提供关于社会经济现象的数字资料工作的总称. b.统计数据 是 ...
浙江省小学数学教师招聘考试说明 一.考试性质 浙江省教师招聘考试是为全省教育行政部门招聘教师而进行的选拔性考试, 其目的是 为教育行政部门录用教师提供智育方面的参考.各地根据考生的考试成绩,结合面试情况, 按已确定的招聘计划,从教师应有的素 ...