北方交通大学理学院

《北方交通大学理学院》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、北方交通大学理学院彭名书2003.2-2003.6mshpeng@center.njtu.edu.cnDiscreteMathematics离散数学讲义（电子版）1课程概况教材：《离散数学》，左孝凌等编著上海科学技术出版社，1982参考书：（1）《离散数学(第二版)》及其配套参考书《离散数学题解》作者：屈婉玲，耿素云，张立昂清华大学出版社（2）《DiscreteMathematicsAndItsApplication》（FourthEdition），KennethH.Rosen（中译本，机械工业出版社）2课程概况选修课/必修课：选修周学时：2（学时）上课

2、周：1－16周总学时：32（学时）班级教室人数上课时间运输0107-商务0103，…等中101（多媒体）195星期二1－2节3课程内容及学时安排第一篇数理逻辑（14学时）第一章命题逻辑（8）第二章谓词逻辑（6）第二篇集合论（10学时）第三章集合与关系（8）第四章函数（2）第四篇图论（8学时）第七章图论（8）4课程考核考核方式：小论文5课程要求（1）上课认真听讲（2）课后及时复习（3）独立、认真地完成作业（4）有问题及时提出，不要积累问题6什么是离散数学？是研究离散对象和它们之间的关系的现代数学。它为计算机科学中的数据结构、编译理论、操作系统、算法分析、

3、人工智能等提供了必要的数学知识。其内容较广，主要包括数理逻辑、集合论、图论、代数结构等四个基本部分。7什么是离散数学？离散数学将日常的概念、判断、推理用数学符号来表示，用数学方法进行思维。其目标是掌握严密的思维方法、严格证明的推理能力和演算能力，掌握处理各种具有离散结构的事物的描述工具与方法，适应学习其他专业课程的各种需要，为学习其它计算机课程提供必要的数学工具。8什么是离散数学？本课程将学习数理逻辑、集合论以及图论的部分内容。数理逻辑的重点是公式演算与推理证明；集合论的重点是关系理论与映射的描述；图论则着重于讨论结点之间的关系以及图论方法的各种实际应用

4、。9课程内容第一篇数理逻辑数理逻辑10第一篇数理逻辑数理逻辑是用数学方法来研究推理过程的科学。主要是指引进一套符号体系的方法，因此数理逻辑一般又叫符号逻辑。基本内容是：命题逻辑（演算）和谓词逻辑（演算）。11第一章命题逻辑命题演算是数理逻辑的基本组成部分，是谓词演算的基础。本章包括以下内容：1-1命题及其表示法1-2连结词1-3命题公式及翻译1-4真值表与等价公式1-5重言式与蕴涵式1-6其它连结词1-7对偶与范式1-8推理理论1-9应用12命题：能够表达判断（分辩其真假）的陈述语句。例：‘中国是一个国家’，‘9为素数’。原子命题：不能分解成更简单的陈述

5、语句的命题。复合命题：由连结词、标点符号和原子命题复合构成的命题。一般用字母“T”表示“真”，“F”表示“假”。1-1命题及其表示法13习惯上，命题用大写字母A，B，…，P，Q，R，…，或用带下标大写字母表示。例如：命题A：中国人们是伟大的。命题B：别的星球上有生物。命题C：1+101=102（在十进制或二进制数范围内）。命题P：今天下雨。命题Q：我去看电影。1-1命题及其表示法（续）14判断下列句子哪些是命题？地球是圆的。2+3=52+3=6你会讲英语吗？3-x=5是命题，真值为T是命题，真值为T是命题，真值为F不是命题（疑问句不是命题）。不是命题，它

6、的真值不确定。1-1命题及其表示法（续）15判断下列句子哪些是命题（续）？请关上门！除地球外的星球有生物。太阳明天会出来。不是命题，祈使句不是命题。是命题，它的真值是唯一确定的，只是目前人们不知道是命题，它的真值是唯一确定的，到明天就知道了。再次注意：命题是具有唯一真值的陈述句。1-1命题及其表示法（续）161-2联结词1、否定设P为一命题，则新命题“P是不对的”称为P的否定。记作：P如：P：2是常数。P：2不是常数。Q：今天是星期四。Q：今天不是星期四。P与P的真值关系：TFPFTP171-2联结词（续）2、合取设P，Q是两命题，新命题“P并

7、且Q”称为命题P，Q的合取。记作：P∧Q如：P：北京是中国的首都。Q：北京是一个故都。P∧Q：北京是中国的首都并且是一个故都。FFFFFTFTPQTFTTPQPQ的真值关系：181-2联结词（续）3、析取设P，Q为两个命题，则新命题“P或者Q”称为命题P，Q的析取。记作：P∨Q如：P：北京是中国的首都。Q：北京是一个故都。P∨Q：北京是中国的首都或者是一个故都。规定：P∨Q的真值为1当且仅当P，Q中至少有一个真值为1。P∨P的真值关系：FFFTFTTTP∨QTFTTPQ191-2联结词（续）注意：析取联结词∨与汉语中的“或”的意义不完全相同。汉语中的

8、“或”既可以表示“排斥或”，也可以表示“可兼或”。例如：P：今天晚上我在家看电视