内容发布更新时间 : 2024/11/17 7:40:16星期一 下面是文章的全部内容请认真阅读。

《离散数学》课程教学大纲

英文名称: Discrete Mathematics 课程编码：01116-4

课内教学时数：64学时，其中课堂讲授64学时，实验（上机）0学时。 学分：4学分

适用专业：计算机科学与技术、软件工程、电子商务（本）等 开课单位：计算机工程学院 撰写人：孙兵 审核人：王爱平

制定（或修订）时间：2017年5月

一、课程的性质和任务

《离散数学》课程是计算机科学与技术专业高等教育的专业基础课程。是现代数学的一个重要分支，是学习计算机科学与技术专业理论必不可少的数学工具。本课程主要研究离散对象的结构及相互关系，对提高学生的抽象思维与逻辑推理能力有重要作用。

《离散数学》课程主要为了培养学生的数学思维能力，使学生得到良好的数学训练，提高学生的抽象思维和逻辑推理能力，并使学生掌握处理离散结构所必须的描述工具和方法，为其从事计算机的应用提供坚实的理论基础。

二、课程教学内容的基本要求、重点和难点

第一单元 数理逻辑

㈠ 基本要求 理解命题、联结词、命题公式、（主）析/合取范式、个体、谓词、量词、谓词公式、指派等概念；掌握（主）析/合取范式的计算、命题演算和谓词演算的推理规则和证明方法；熟练掌握公式真值表的构造及命题符号化方法、常用的基本等值式及其应用、常用的永真蕴涵式及其在逻辑推理中的应用。

㈡ 教学重点 各个概念、公式演算和推理方法。 ㈢ 教学难点 谓词符号化；应用公式进行逻辑推理。 ㈣ 教学内容 1、命题 ⑴ 命题的概念。

⑵ 命题联结词及其真值表。

⑶ 命题符号化。

⑷ 命题变元和命题公式的概念。 2、重言式

⑴ 指派、重言式、逻辑恒等式、永真蕴含式等基本概念。 ⑵ 常见的逻辑恒等式和永真蕴含式。 ⑶ 逻辑恒等式和永真蕴含式的基本性质。 ⑷ 命题演算的基本规则：代入规则、替换规则。 ⑸ 命题演算中的对偶原理。 3、范式

⑴ 基本积与基本和的概念。

⑵ 析取范式与合取范式的概念及计算。 ⑶ 极小项与极大项的概念。

⑷ 主析取范式与主合取范式的概念及计算。 4、联结词的扩充与归约

⑴ 与非、或非、异或(排拆或)、蕴含否定的定义。 ⑵ 与非、或非、异或(排拆或)、蕴含否定的基本性质。 ⑶ 联结词完备集的概念。 ⑷ 联结词完备集的判定。 5、推理规则和证明方法 ⑴ 推理的有效性的概念。

⑵ 推理规则：T 规则（前提引入）、P 规则（结论引入）等。 ⑶ 形式推理的表上作业。

⑷ 证明方法：演绎法、归谬法等。 6、谓词和量词 ⑴ 谓词的概念。

⑵ 全称量词和存在量词的概念。 ⑶ 谓词符号化。

⑷ 量化断言与命题的关系。 ⑸ 谓词公式的概念。

⑹ 自由变元与约束变元的概念。 ⑺ 谓词公式中的改名规则。 7、谓词演算的永真公式 ⑴ 谓词公式的解释。 ⑵ 谓词演算的基本永真公式。

⑶ 谓词演算的几条规则：代入规则、替换规则和对偶原理。 8、谓词演算的推理规则

⑴ 术语“A(x)对y 是自由的”的意义。 ⑵ 全称指定规则（US）（全称量词消去规则）。 ⑶ 存在指定规则(ES)（存在量词消去规则）。 ⑷ 存在推广规则(EG)（存在量词引入规则）。 ⑸ 全称推广规则（UG）（全称量词引入规则）。

第二单元 集合

㈠ 基本要求 了解自然数的归纳定义；理解数学归纳法第一原理及第二原理；掌握集合的有限集的计数方法、集合的归纳定义、n 元组和笛卡儿乘积等概念和性质；熟练掌握集合的基本概念、基本运算的相关性质和文氏图表示、幂集的概念。

㈡ 教学重点 集合的基本概念；集合的运算；集合的归纳定义；笛卡儿乘积。 ㈢ 教学难点 集合的交和并运算的推广；自然数的归纳定义。 ㈣ 教学内容

1、集合论的基本概念

⑴ 集合的基本概念及表示方法。 ⑵ 罗素悖论。 ⑶ 集合间的包含关系。 2、集合上的运算

⑴ 集合上的交、并、差、补、环和与环积等运算的定义和性质。 ⑵ 集合上的文氏图表示及交、并运算的扩展。 ⑶ 幂集合的概念。

⑷ 有限集的基数公式及应用。 3、归纳法和自然数 ⑴ 集合的归纳定义法。

⑵ 自然数的归纳定义和皮亚诺(Peano)公设。 ⑶ 数学归纳法第一原理和第二原理。 4、集合的笛卡儿乘积 ⑴ 序偶和n 重组的概念。

⑵ 集合的笛卡儿乘积的概念及性质。

第三单元 二元关系

㈠ 基本要求 理解关系的合成及逆关系的概念、等价关系和划分的联系；掌握偏序关系及其哈斯图表示、等价关系和等价类的概念和性质、划分的概念；熟练掌握关系的基本概念、二元关系的关系矩阵和关系图表示、关系的特性、关系的闭包运算。