《离散数学》教学大纲.docxVIP

“离散数学”课程教学大纲 课程英文名称：Discrete Methemetics 课程编号 课程类型：专业核心课 总学时：64 学 分：4 使用对象：信息与系统工程学院计算机专业(民、汉本) 选修课程：高等数学、线形代数、C语言 使用教材及参考书 教 材：《离散数学》，耿素云、屈婉玲编著，高等教育出版社，2004年1月，面向21世纪教材。 参考书：《离散数学》，左孝凌，刘永才编著，上海科学技术出版社，1988年2月 — 课程性质、目的和任务 离散数学是计算机科学的理论基础，对于培养学生的逻辑思维和分析问题、解决问题的能力起着重要作用。通过离散数学的教学，不仅能为学生的专业课学习及将来从事的软、硬件开发和应用研究打下坚实的基础，同时也能培养他们抽象思维和严格逻辑推理能力。 二、教学基本要求 离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。它以研究离散量的结构和相互之间的关系为主要目标，其研究对象一般是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。 本课程包括数理逻辑、集合论、代数结构，图论等四个内容。考虑到教学时数，要求学生掌握只选数理逻辑、集合论、图论等内容。 三、教学内容及要求 第一部分：数理逻辑 第一章 命题逻辑基本概念 1．分清简单命题(既原子命题)与复合命题。 2．深刻理解5种常用联结词的涵义，并能准确地应用它们将基本复合命题及复合命题符号化。 3．分清“相容或”与“排斥或”。 4．深刻理解命题公式的赋值、成真赋值、成假赋值，从而准确地判断出公式的类型。 第二章 命题逻辑等值演算 1．深刻理解等值式的定义，知道公式之间的等值关系具有自反性、对称性、传递性。 2．牢记基本等值式的名称及它们的内容。 3．熟练地应用基本等值式及置换规则进行等值演算。 4．了解文字、简单析取式、简单合取式、析取范式，合取范式等概念。 5．深刻理解极小项、极大项的定义，名称、下角标与成真赋值的关系，主析取范式与主合取范式。 6．熟练掌握求主析取(主合取)范式的方法。 7．会用主析取范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值。 8．会将任何命题公式等值地化成某联结词完备集中的公式。 第三章 命题逻辑的推理理论 1． 理解并记住推理形式结构的以下两种形式． (1)(A1∧A2∧…∧Ak) →B (2)前提：A1A2．．．Ak结论：B 2．熟练掌握判断推理是否正确的不同方法，如真值表法、等值演算法、主析取范式法等。 3．牢记P系统中各条推理规则的内容及名称。 4．熟练掌握在P系统中构造证明的直接证明法、附加前提证明法、归谬法。 5．会将日常生活中、社会活动中、科学领域中的某些推理形式化，即写出符号化形式的前提、结论，并能判断推理是否正确，对于正确的推理能在P系统中给出证明。 第四章：一阶逻辑基本概念 1．准确地将给定命题符号化：分清在4．1节中给出(1)一(7)或更多种的符号化形式，特别 注意两个基本公式中量词与联结词的搭配情况，其实(5)、(6)、(7)等都是两个基本公式(3)与(4)的应用。 2．深刻理解永真式、矛盾式、可满足式的概念及其判别方法：准确写出公式的真值表。 3．深刻理解闭式的概念及闭式的性质(闭式在任何解释下都是命题)。 4．对于给定的解释会判断给定公式是否成为命题，对是命题的能判断出是真命题，还是假命题。 第五章 一阶逻辑等值演算与推理 1．深刻理解并牢记一阶逻辑中的重要的等值式，并能准确而熟练地应用他们 2．熟练又正确地使用置换规则、换名规则、代替规则 3．准确地求出给定公式的前束范式 4．深刻理解自然推理系统F的定义，牢记F中的各条推理规则，特别是要正确使用UI、UG、EG、EI 4条推理规则，使用中应注意以下几点： (1)一定对前束范式才能使用UI、UG、EG、EI规则．对不是前束范式的公式要使用它们，一定先求出公式的前束范式； (2)记住UI、UG、EG、EI各自使用的条件； (3)在同一个推理的证明中，如果既要使用UI规则，又要使用EI规则，一定先使用EI规则，后使用UI规则，而且UI规则使用的个体常项一定是EI规则中使用过的。 (4)对A(c)不能使用UG规则，其中c为特定的个体常项。 5．对于给定的推理，要求正确地给出它的证明。 第二部分：集合论 第六章：集合代数 1．熟练掌握集合的两种表示法。 2．能够判别元素是否属于给定的集合。 3．能够判别两个集合之间是否存在包含、相等、真包含等关系。 4．熟练掌握集合的基本运算(幂集运算，普通运算和广义运算)并能化简集合表达式。 5．掌握有穷集合的计数方法。 6．掌握证明集合等式