《计算机数学基础(一)》网上教学活动文本

1、文档供参考，可复制、编制，期待您的好评与关注！ 计算机数学基础（一）网上教学活动文本顾静相：计算机前的同学们，下午好，现在是计算机数学基础（一）期末网上答疑时间，欢迎同学们参加此次活动。这次活动由中央电大冯泰教授和我一起解答问题，同时我们也给出一些复习要求和所要复习的内容。另外同学们在学习当中有什么问题想在这里得到解答，请及时提出。当然如果有一些问题现场没有及时解答的，请你留下联系方法，我们会尽快给你答复。冯泰：大家好，这门课程是为开放本科计算机科学与技术专业开设的必修课程，这学期有四编八章，这八章都是我们学习的内容。顾静相：一、关于期末考试1本学期的结业考核由形成性考核和期末考核构成。形成性

2、考核由平时作业成绩构成，占结业考核成绩的20%, 期末考核成绩占结业考核成绩的80%。 2期末考核实行全国统一考核，根据本课程考试说明，由中央电大统一命题，统一考核时间，制定统一评分标准。开办试点的地方电大组织考核。期末考核的考核内容和要求以考核说明为准；采用闭卷笔试，试卷满分100分；时限120分钟。试题类型及分数：单项选择题和填空题，分数约占25。解答与计算题，分数约占56；证明题，分数约占19。3考核试卷分数分布：第1编数理逻辑约30分，第2编集合论约30分，第3编图论约25分，第4编代数系统约15。4易、中、较难题目在试卷中占的比例是4：4：2。顾静相：二、各章重点考核内容 关于考核内

3、容与要求，在本课程的考核说明中，有详细的说明，以及中央电大杂志社编印的本课程的期末复习指导中，也都列出了。因时间关系，今天就不逐条念了。三、各章基本问题顾静相：第1章 命题逻辑1. 命题符号化，是否命题判断或求真值。2. 命题公式赋值，及类型判别。3. 命题公式等值判别或证明。方法有真值表法、等值演算法和主范式法. 4. 求范式和主范式。5. 蕴含式(推理理论)证明：方法有：真值表法、等值演算法、主析取范式法、构造证明法直接法、附加前提证明法和反证法。顾静相：第2章 谓词逻辑1. 命题符号化。2. 求辖域、约束变元、自由变元。3. 给定解释求谓词公式的真值(多为个体域有限的情形)。4. 判断谓

4、词公式是否重言式(用代换实例)、永假式？5. 求前束范式。顾静相：第章集合及其运算1. 求集合表达式(列举法或描述法)。2. 判断集合与元素、集合与集合的关系，用Î，Ï，Ì，Í，Ë？3. 求幂集。4. 包含或相等的化简或证明。5. 求笛卡儿积，或某些等式证明。顾静相：第章 二元关系与函数1. 求关系的表达式，关系矩阵、关系图，Dom(R),Ran(R).2. 验证或证明关系的性质。3. 关系计算：求È，Ç，Å4. 求复合关系、逆关系及其矩阵。 5. 求自反闭包或对称闭包。6. 验证或证明关系R是等价关系或偏序关系。

5、7. 作偏序关系的哈斯图，求极大(小)元、最大(小)元。8. 验证是否是函数，是满射、单射、双射？ 冯泰：第5章 图的基本概念1. 图G与G<V，E>互求。2. 判断简单图、多重图、完全图。3. 求子图或生成子图。4. 求结点度数或用握手定理求结点数，或判断是否度数序列。 5. 判断是否同构，主要用必要条件判断不同构。会作2或3个结点非同构的生成子图。 6. 用定理1(握手定理)或2以及推理进行推理或计算。7. 求图中通路、回路及其长度或通路、回路的数目(主要用定理8)8.判断是否连通、强连通、单侧连通或弱连通。 9. 求点割集、割点和边割集、割边(比较简单的图)。 10. 求有向

6、图的邻接矩阵和可达矩阵。顾静相：第6章 几种特殊的图1.判断或作欧拉图，求欧拉通路、回路。2. 判断或作哈密顿图，求哈密顿通路、回路，说明不是哈密顿图。3. 判断是否可平面图，将可平面图改画为平面图。 4. 求连通平面图的面、边界和次数。5. 用定理6，7作某些证明或计算。如求二元完全树中树叶个数与分支点数之关系。6. 判断是否树。7. 求树的结点与边的关系。8. 求最小生成树和权。 顾静相：第7章 群1. 验证代数运算f在A上封闭，即<A,f>是代数系统。 2. 验证代数运算有结合律，交换律等。 3. 验证代数运算f，g有无分配律，吸收律等。4. 求运算的单位元，逆元.。5. 判

7、断是否半群、群、交换群、循环群，求生成元和循环群的子群。.6. 在群中进行计算、化简等。 7. 求复合置换、逆置换等。8. 证明群同态、同构，找同态(同构)映射。顾静相：第8章 其它代数系统1. 验证是否为环？2. 给出偏序集，判断是否为格？3. 在格中进行计算、化简或证明等。4. 布尔代数式的化简、求值或证明。四、 回答问题顾静相：第1章 命题逻辑问题1. 请解释一下蕴含联结词®冯泰：P®Q，其意义是如果P，则Q”；”必须P，以便Q”；”P仅当Q”；”Q每当P”；“只有Q，才P”. 即Q是P的必要条件，P是Q的充分条件. 例如 设P：天下雨，Q：他乘车上班。 命题“如果天

8、下雨，他就乘车上班”符号化为“P®Q”(若天不下雨，他乘车吗？)命题“只有天下雨，他才乘车上班” 符号化为“Q®P”(若天不下雨，他一定不乘车)顾静相：问题2. 用真值表求主析取(合取)范式，总是记不住是取0的项还是取1的项？冯泰：答：主析取范式极小项的析取，而极小项是合取式，只有每个变元或其否定都是1，极小项才是1. 故用真值表求主析取范式，应是1的项的析取.主合取范式极大项的合取，而极大项是析取式，只有每个变元或其否定都是0，极大项才是0. 故用真值表求主合取范式，应是0的项的合取.顾静相：问题3. 第1章的构造推理，学习起来感到困难，怎样才能学好？冯泰：第1，2章的构

9、造推理证明基本是相同的.第1章的推理证明中，已知条件往往是一环扣一环给出的，只要掌握教材P29的I或E，证明进行就会很顺利. 举个例子. 习题1：8(3)前提：R®ØQ,RÚS,S®ØQ,P®Q，结论：ØP证明(用三种方法证明)方法一： R®ØQ P S®ØQ P RÚS P ØQ ，I14(构造性二难) P®Q P ØP ，I12(拒取式) 方法二： R®ØQ P ØRÚØQ E16(蕴含等值式

10、) S®ØQ P ØSÚØQ E16(蕴含等值式)(ØRÚØQ)Ù(ØSÚØQ) ，I9(合取引入) Ø(RÚS)ÚØQ E6，E8(分配律、摩根律) RÚS P Ø(Ø(RÚS) E1(双重否定律) ØQ ，I10(析取三段论) P®Q P 11 ØP ，I12(拒取式) 方法三：反证法。P (否定结论) P®Q P Q ，I11(假言推理)S®

11、ØQ PØS ，I12(拒取式)R®ØQ P ØR ，I12(拒取式)Ø(RÚS) ，I9(合取引入)RÚS P Ø(RÚS)Ù(RÚS) ，I9(合取引入)顾静相：第2章 谓词逻辑问题1. 命题符号化时，全称量词“"”和存在量词“$”的使用有什么注意的地方？冯泰：答：在命题符号化时，使用全称量词“"”，特性谓词后用蕴涵联结词“®”；使用存在量词“$”，特性谓词后用合取联结词“Ù”。从实际逻辑运算要求，应该如此。设M(x)：x是人，H(

12、x)：x要呼吸。命题“人要呼吸”符号化为："x(M(x)®H(x)；等价于“没有不呼吸的人”符号化为：Ø$x(M(x)ÙØH(x)同样：Ø(Ø"x(M(x)®H(x)ÛØ$x(Ø(ØM(x)ÚH(x)ÛØ$x(M(x)ÙØH(x)M(x)就是特性谓词。它说明全总个体域中人这个真子集。说明："与®，$与Ù配在一起使用是合理的。顾静相：问题2. 谓词公式求值，只有在数的个体域才有意义，对吗？

13、冯泰：答：不对. 谓词公式，一旦个体变元取为常元后，它就是命题，命题的真值并不限于是数的个体域. 例如个体域D岳飞,文天祥,秦桧，谓词F(x)：x是民族英雄.求"xF(x)和$xF(x)的真值."xF(x)=F(岳飞)ÙF(文天祥)ÙF(秦桧)1Ù1Ù00 $xF(x)F(岳飞)ÚF(文天祥)ÚF(秦桧)1Ú1Ú01顾静相：第3章 集合及其运算问题1. 请讲一下Î和Í的用法.冯泰：答：Î表示集合与元素之间的关系，Í表示集合与集合之间的关系.如：Aa,b,c

14、,aÎA, aÍA, 而不能写作aÎA. 但是Æ有ÆÎÆ, ÆÍÆ. 前者表示Æ是元素，后者表示Æ是(空)集合.顾静相：问题2. 设A，B，C，D是任意集合，一定有(1) 若AÇB=AÇCÞB=C (2) AÈB=AÈCÞB=C吗？冯泰：答：两个式子一般都不成立。请注意集合运算与实数运算上的不同。(1) 当AÆ时，对任意B，C，都有AÇB=AÇCÆ；当A¹Æ

15、，如A=1,2，B1,2,3，C=1,2,3,4，有AÇB=AÇC，但 B¹C. 因此一般地，若AÇB=AÇC并不能得到B=C. 只有当AÊB，AÊC时，若AÇB=AÇC一定有B=C. (2) 同理，一般地，有AÈB=AÈC，得不到B=C；只有AÍB，AÍC时，若AÈB=AÈC必有B=C.顾静相：第4章 二元关系与函数问题1. 设集合Aa,b,c，如何判断A上关系R<a,b>有传递关系？冯泰：答：在关系的几个性质中，判断传递关系是困难

16、的。通常有两种方法：其一是定义；其二是充分必要条件：R是传递的ÛR·RÍR对于一些特殊的关系，用充分必要条件判断更好。如本例R·RÆÍR，故R是传递的。传递关系的定义：R是传递的Û"a,b,cÎA(<a,b>ÎRÙ<b,c>ÎR®<a,c>ÎR)对于这种特殊关系R<a,b>，从逻辑角度理解。如本例<a,b>ÎR，真值为1, 而<b,c>ÎR,真值为0(不存在)，则&

17、lt;a,c>ÎR，真值为0(不存在)，于是有1Ù0®0Û1，即<a,b>ÎRÙ<b,c>ÎR®<a,c>ÎR的真值为1，是永真式。可知R是传递的。又如R<a,a>,<b,b>是传递的，也可以通过逻辑解释。又如R<a,b>,<b,c>不是传递的，逻辑解释为：<a,b>ÎR，真值为1, 而<b,c>ÎR,真值为1而<a,c>ÎR，真值为0(不存在)，即&

18、lt;a,b>ÎRÙ<b,c>ÎR®<a,c>ÎRÛ1Ù1®0，是永假式。可知R不是传递的。顾静相：问题2. 如何求极大(小)元、最大(小)元？冯泰：答：求极大(小)元、最大(小)元最好先作哈斯图。需要记住：一个集合(或子集)的极大元或极小元可能有多个，而最大元或最小元可能没有；若有，是惟一的。哈斯图中的孤立点既是极大元，也是极小元。可见只有平凡图的极大元、极小元和最大元、最小元是相同的。 d b c a举两个例子.如哈斯图为： 极大元：c,d； 极小元：a d b c a e 最大元

19、：无 最小元：a又如 极大元：d,e 极小元：a,e 最大元，最小元：无 若只限于讨论Ba,b,c,d的极大元极小元最大元最小元，则极大元和最大元均为d;极小元和最小元均为:a4 65 2 3 1关于界的讨论，请看教材第124页图422，显然A1,2,3,4,5,6。若B1,2,3，那么，子集B的下界是1；最大下界也是1；B的上界和最小上界均为6。4不是B的上界，因为3和4不可比较。若B=1,2,则B的上界为2，4，最小上界是2。顾静相：第5章 图的基本概念问题1：设有向图D<V,E>,V=v1,v2,vn. D的邻接矩阵A(D)=aijn，结点vi的出度 ，结点vj的入度 .(一

20、个作业题)冯泰：答：结点vi的出度A(D)的第i行元素之和，结点vj的入度A(D)的第j列元素之和.顾静相：问题2：设D是有向完全图，则D的所有结点的入度平方和等于所有结点的出度平方和冯泰：证明：设D有n个结点对任意结点vkÎD, 有 d(vk)+d(vk)=2(n1) 对有向完全图，有于是， = 顾静相：第6章 几种特殊图问题1. “无奇数度结点的无向图一定是欧拉图”，对码？冯泰：答：不对。若无奇数度结点的连通无向图一定是欧拉图。顾静相：问题2. “完全图Kn一定是哈密顿图”，对吗？冯泰：答：不对。当n³3时，Kn一定是哈密顿图。顾静相：问题3. 设G是n个结点带权无向连

21、通图，各边的权均为a(a>0)。T是图G的一棵最小生成树，则T(W)= 冯泰：答：(n1)a。有n个结点，m条边的图G，那末G的生成树有n1条边。顾静相：问题4.设无向图G<V,E>连通无回路，则图G的每条边都是割边(桥)，对吗？冯泰：答：图G连通无回路，则G是树。由树的等价定义(5)，删去任何一条边，图G不再连通，可知任何边都是割边，即桥。顾静相：第7章 群问题1. 一个群能够同构于它的真子群吗？冯泰：答：可以。如(Z，+)是加法群，设Hx½x=3kÙkÎZ，Z是整数集。于是HÌZ。令f(x)=3x，则f：Z®H。是双射。ZH顾静相：五、答疑 问题1任意集合A，B，证明P(A)ÈP(B)ÍP(AÈB)(答张喜荣，wwwedu) 冯泰：证明 "xxÎ(P(A)ÈP(B)ÛxÎP(A)ÚxÎP(B)ÛxÍAÚxÍBÞxÍ(AÈB)ÛxÎP(AÈB)说明：集合有性质AÍAÈB，BÍAÈB。xÍAÍAÈB，x&#