当前位置:首页 >> 其它课程 >>

离散数学(第29讲半期考试讲评)


冯伟森
Email:fws365@scu.edu.cn
Tel: 13808192275

2014年1月20日星期一

主要内容

2014-1-20

计算机学院

2

第一大题
1、只有不怕困难,才能战胜困难; 解: p

:怕困难, q:战胜困难 q→?p or p→?q 完全答对: 37人 基本答对: 7人 完全答错:0

原因分析: 分不清楚命题和逻辑谓词之间表示的 区别。

2014-1-20

计算机学院

3

2、整数n 是偶数当且仅当n能被2整除.; 解:p:整数n是偶数,q:整数n能被2整除 p? q 完全答对: 26人 基本答对: 17人 完全答错:1

原因分析: 分不清楚命题和逻辑谓词之间表示的 区别,没有注意到当且仅当是双条件命题。

2014-1-20

计算机学院

4

3 、发明家都是聪明的并且是勤劳的,王前进是 发明家,所以王前进是聪明的并且是勤劳的; 解: F(x):x是发明家,G(x):x是聪明的,H(x) :x是勤劳的,a:王前进 (?x(F(x)→(G(x)∧H(x))) ∧F(a)?G(a)∧H(a) 完全答对: 7人 基本答对: 31人 完全答错:5

原因分析: 逻辑谓词的全称量词没有写,或者

逻辑混淆。
2014-1-20 计算机学院 5

4、若x与y都是实数,且 x>y,则 x+2>y+2; 解: F(x):x是实数,H(x,y):x>y ?x?y(F(x)∧F(y)∧H(x,y)→H(x+2,x+2)) 完全答对: 20人 基本答对: 22人 完全答错:2 原因分析: 逻辑谓词的全称量词没有写。

2014-1-20

计算机学院

6

5、不存在最大的自然数。 解: F(x):x是实数,H(x,y): x>y ??x (F(x)∧?y(F(y)→H(x,y))) 或 ?x(F(x) →?y(F(y)∧?H(x,y))) 完全答对: 5人 基本答对: 24人 完全答错:15 原因分析: 逻辑谓词的存在量词和全称量词没

有写,对这句话理解很多人不是很清楚。
2014-1-20 计算机学院 7

第二大题
1 、用等价变换法求下列公式的主析取范式和主 合取范式
(( p ? q ) ? ( p ? q )) ? (q ? p)
? (( p ? q ) ? (?p ? q )) ? (q ? p) ? q ? (q ? p ) ? (q ? (q ? p)) ? (( q ? p) ? q ) ? ( p ? ?q ) ? q ? (p ? q) 主析取式 主合取式 ? ( p ? ?q ) ? ( q ? ( ?p ? p ) ? ( p ? ?q ) ? ( q ? ?p ) ? ( q ? p )

2014-1-20

计算机学院

8

完全答对: 27人 基本答对: 5人 完全答错:12 原因分析:对命题公式不熟悉,计算错误。

2014-1-20

计算机学院

9

2、求2A,其中A={?,a,{b}}; 解:2A= {?,{?},{a},{{b}},{?,a},{?,{b}},{a,{b}},A}

完全答对: 35人 基本答对: 0人 完全答错:9 原因分析:典型错误是少写一个?,或{?}。

2014-1-20

计算机学院

10

3、假设R的关系图如图所示,试给出r(R)、s (R)、t(R)的关系矩阵 M(r(R))、M (s(R))、M(t(R))。
a b c
0 0 1 0 0

d
0? ? 1? 0? ? 0? 1? ?

e

?0 1 0 ? ?0 0 1 R ? ?0 0 0 ? ?0 0 1 ?0 0 0 ?
2014-1-20

计算机学院

11

?1 1 ? ?0 1 M ( r ( R )) ? ? 0 0 ? ?0 0 ?0 0 ?

0 1 1 1 0

0 0 1 1 0

?0 1 ? ?0 0 M ( t ( R )) ? ? 0 0 ? ?0 0 ?0 0 ?
2014-1-20

1 1 1 1 0

?0 ? ?1 M (s( R )) ? ? 0 ? ?0 ?0 ? 1 1 ? ? 1 1 ? 1 0? ? 1 0? 0 1? ?
计算机学院

0? ? 1 ? 0? ? 0? 1? ?

1 0 0 1 1 0 0 1 1 0

0 0 1 0 0

0? ? 1 ? 0? ? 0? 1? ?

12

完全答对: 14人 基本答对: 26人 完全答错:4 原因分析:没有根据图写出关系或关系矩阵 R, 对 r ( R )和 s ( R )错误较少, t ( R )错误较 多,可能是对warshall算法不了解或不熟悉。

2014-1-20

计算机学院

13

4、如图是偏序集 ? X , ?? 的哈斯图,求X和≤的集 合表达式, 并指出该偏序集的极大元、极小
e f

元、最大元、最小元。

b

c a

d

? 解:X={a,b,c,d,e,f} ? ≤={〈a,b〉, 〈a,c〉, 〈a,d〉, 〈a,e〉, 〈a,f〉, 〈b,e〉, 〈c,e〉, 〈c,f〉, 〈d,f〉}∪IX

极大元e,f;极小元a;最大元不存在,最小元a;
2014-1-20 计算机学院 14

? 完全答对: 6人 基本答对: 33人 ? 完全答错:5 ? 原因分析:偏序关系写对的人很少,大部分写 的是 ? ≤={〈a,b〉, 〈a,c〉, 〈a,d〉, 〈a,e〉, 〈a,f〉, 〈b,e〉, 〈c,e〉, 〈c,f〉, 〈d,f〉}缺少Ix

2014-1-20

计算机学院

15

? 5、设 ? : R ? R, ? ( x) ? ? x 2 , x ? 3 ,? : R ? R,? ( x) ? x ? 2 ? ??2, x ? 3 ? ? 求 ? ?? ,? ??

?( x ? 2) , x ? 1 ? ? ?( x ) ? ? x ?1 ?? 2,
2

?x ? 2, x ? 3 ? ? ?( x ) ? ? x?3 ?0,
2
2014-1-20 计算机学院 16

? 完全答对: 32人 基本答对: 5人 ? 完全答错:7 ? 原因分析:如果按函数的算对的比较多,按关 系的有一个,其他的错误是按函数算,但定义 域没写对。

2014-1-20

计算机学院

17

第三大题
? 1、用CP规则证明下面推理 前提: ?p ? (q ? r ), s ? p, q 结论: ?r ??s

1)?r 2) q 3)?r ? q 4)?( r ? ?q ) 5)?(q ? r ) 6) ? p ? ( q ? r )
2014-1-20 计算机学院

P (附加前提) P T1 ) 2 )I (De Morgan) T4)E P
18

7 )?p 8)s ? p 9) ? s 10)?r ? ?s

T5)6)I( 基本等价式、拒取式) P T7) 8 )I( 拒取式) CP 规则

? 完全答对: 27人 基本答对: 11人 ? 完全答错:6 ? 原因分析:采用 CP规则推理时,没有严格的按 逻辑推理,有些关键步骤被省略,对推理中使 用的规则使用不当。有些不了解CP规则。
2014-1-20 计算机学院 19

? 2、用反证法证明下面推理 ? 前提: p ? (q ? r ), p ? q ? 结论: r ? s
1)?( r ? s ) 2) ? r ? ? s 3) p ? q 4) p 5) p ? (q ? r ) 6) q ? r
2014-1-20

P(附加前提) T1 )E P P

T3 )I(简化法则)

T4 ) 5 )I (假言推理)
计算机学院 20

7 )q 8)r 9)?r 10)F(矛盾式)

T3 )I(简化法则) T6) 7 )I (假言推理) T2)I(简化法则)

? 完全答对: 22人 基本答对: 20人 ? 完全答错:2 ? 原因分析:没有严格的按逻辑推理,有些关键 步骤被省略。
2014-1-20 计算机学院 21

? 3、构造下面推理的证明 ? 前提: ?x(F(x)→?y(G(y)∧H(x))) , ?xF(x) ? 结论: ?x(F(x)∧G(x)∧H(x)) ? 解:1)?xF(x) ? 2) F(c) 前提引入 1)EI 前提引入 3)辖域扩张 4)UI 5)UI
22

? 3) ?x(F(x)→?y(G(y)∧H(x))) ? 4) ?x?y (F(x)→ (G(y)∧H(x))) ? 5) ?y (F(c)→ (G(y)∧H(c))) ? 6) F(c)→ (G(c)∧H(c))
2014-1-20 计算机学院

? 7) G(c)∧H(c) ? 8) F(c)∧G(c)∧H(c) ? 9) ?x(F(x)∧G(x)∧H(x))

2)6)假言推理 2)7)合取 8)EG

? 完全答对: 13人 基本答对: 10人 ? 完全答错:21 ? 原因分析:对含有谓词公式的推理,错的人比 较多,主要是对规则的不熟悉,规则使用时应 该注意的条件没有注意。
2014-1-20 计算机学院 23

? 4、设R是A 上的自反和传递关系,如下定义A 上的关系T,使得?x,y∈A ? <x,y>∈T?<x,y>∈R∧<y,x>∈R ? 证明T是A上的等价关系。 ? 证明:1)∵R是自反的 , ∴<x,y>∈R ,即 <x,y>∈T,T是自反的 ? 2) 显然,T是对称的 ? 3 ) 设 <x,y> ∈ T , <y,z> ∈ T, 由 T 的 定 义 有 <x,y>∈R∧<y,x>∈R
2014-1-20 计算机学院 24

? <y,z> ∈ R ∧ <z,y> ∈ R , 由 R 的 传 递 性 , 有 <x,z>∈R∧<z,x>∈R ? 即<x,z>∈T,T是传递的 故T是A上的等价关系 完全答对: 24人 基本答对: 9人 完全答错:11 原因分析:这道题的正确率比较高,错的人主要 是传递性证明出错,对传递性的定义不了解。

2014-1-20

计算机学院

25

? 5、设f:A → B 为单射函数, 在f 下的像。证明 G也是单射的。 ? 解:假设 A1,A2 ?2A ,A1?A2, ? 不妨设存在x使得x?A1∧x?A2, ? 所以 f(x)?f(A1) 且f(x)?f(A2) ? 于是 f(A1)?f(A2) ? 故 G(A1)?G(A2)

为X

2014-1-20

计算机学院

26

? 完全答对: 6人 基本答对: 15人 ? 完全答错:23 ? 原因分析:这道题错误率比较高,对 G ( X ) 为X在f下的像理解不清楚,没有注意到, f(x)?f(A1) 且f(x)?f(A2)。

2014-1-20

计算机学院

27

第四大题
? 在一个道路网络上连接有8个城市,分别标记为 a,b,c,d,e,f,g,h ;城市之间的直接连接的道路有 a→b,a→c,b→g,g→b,c→f,f→e,b→d,d→f。对每 个城市求出从它出发能够到达的所有其它城市 。 ? 解:令 S={a,b,c,d,e,f,g,h} 定义S上的关系R 如 下:〈x,y〉?R ? 从a到b有一条直接的道路

2014-1-20

计算机学院

28

R={〈a,b〉,〈a,c〉, 〈b,g〉, 〈g,b〉, 〈c,f〉, 〈f,e〉, 〈b,d〉, 〈d,f〉}, 求出R的传递闭包t(R) 即可获得问题的解。
?0 ? ?0 ?0 ? MR ? ?0 ?0 ? ?0 ? ?0
2014-1-20

1 1 0 0 0 0? ? 0 0 1 0 0 1? 0 0 0 0 1 0? ? 0 0 0 0 1 0? 0 0 0 0 0 0? ? 0 0 0 1 0 0? ? 1 0 0 0 0 0?

M t (R )

?0 ? ?0 ?0 ? ? ?0 ?0 ? ?0 ? ?0

1 1 1 1 1 1 ? ? 1 0 1 1 1 1 ? 0 0 0 1 1 0 ? ? 0 0 0 1 1 0 ? 0 0 0 0 0 0? ? 0 0 0 1 0 0? ? 1 0 1 1 1 1?
29

计算机学院

? ? ? ? ? ? ? ?

2014-1-20

(t(R)-IS)[{a}]={b,c,d,e,f,g} (t(R)-IS)[{b}]={d,e,f,g} (t(R)-IS)[{c}]=(t(R)-IS)[{d}]={ e,f } (t(R)-IS)[{f}]={e} (t(R)-IS)[{g}]={b,d,e,f} 完全答对: 3人 基本答对: 37人 完全答错:4人 原因分析:失分的主要原因是解题时,没有从 关系矩阵的传递闭包角度来解答,只写出结果 值,没有写出关系矩阵和采用warshall方法来计 算传递闭包矩阵。
计算机学院 30


相关文章:
第29讲 行程问题(一)
第29讲 行程问题(一)_学科竞赛_小学教育_教育专区。四年级奥数 第29 周 行程问题(一) 一、知识要点 我们把研究路程、速度、时间这三者之间关系的问题称为行程...
小学奥数第29讲 实践与实际操作(含解题思路)
小学奥数第29讲 实践与实际操作(含解题思路)_学科...(第四届《从小爱数学》邀请赛试题)讲析:解题的...
离散数学部分作业讲评
离散数学部分作业讲评离散数学部分作业讲评隐藏>> 集合...(4) 未清楚为什么{{a}}是 P(A)的真子集. ...网上形考作业 4:关系的性质(分组讨论) 第一组讨论...
离散数学图论部分形成性考核书面作业讲评
​性​考​核​书​面​作​业​讲...作业讲评 离散数学图论部分形成性考核书面作业讲评 ...29,31,试(1)画出相应的最优二叉树; (2)计算...
第29讲 运筹学初步(三)
第8讲 比和比例 第10讲 商业中的数学 第11讲 圆与扇形 第12讲 圆柱与圆锥...第一轮模拟考试《计算机应... 8页 1财富值如要投诉违规内容,请到百度文库投诉...
2012环评考试案例分析课件第29讲
2012环评考试案例分析课件第29讲 隐藏>> 三、水库、水坝建设 1.评价范围、期限...5.此类项目对生态环境的影响主要集中在施工期,如对原生植被、生物多样、土壤侵蚀...
离散数学第三讲
离散数学第三讲_数学_自然科学_专业资料。离散数学 二、容斥原理与鸽巢原理 1、 容斥原理(§1。3。) (计数原理、包含排斥原理) 容斥原理(包含排斥原理) :设 ...
离散数学第一讲
离散数学第一讲_理学_高等教育_教育专区。引 1、 ...从 1874 年开始, 岁的德国数学家康托 29 (GEORG ...条条大路通罗马,信计专业学生只有考 研才是最好的...
维修内部培训试卷_讲评_2011.10.29
维修内部培训试卷_讲评_2011.10.29_从业资格考试_资格...②对于带同样电量的电容器来,电容越大,两板的...由于各级的放大作用,第一级的微弱变化,会使输出级...
离散数学(第四版)讲义2
离散数学讲义-第14讲(7.1-... 84页 2财富值 离散数学标准讲义sy第2章 96页 5财富值喜欢此文档的还喜欢 离散数学(第四版)讲义1 17页 免费 第7章 图论 ...
更多相关标签:
两学一做半年点评讲评 | 时滞微分方程 半离散 | 半离散 | 半离散化 | 29天半 电视剧 | 捷克zh 29半自动步枪 | 29天半 | 29天半电视剧全集 |