第二章谓词逻辑4学时
第三章基础数论及证明方法10学时
第四章序列与数学归纳法2学时
第五章集合论6学时
第六章计数与概率2学时
第七章函数8学时
第八章递归6学时
第九章关系6学时
第十章图与树4学时
（二）考核要求
1.成绩评价
平时成绩（含考勤、作业与测验）占30%，期末（卷面）成绩占70%。
2．命题说明
题型应多样化，设计适当的开放性问题。基本题(
4．学时安排：周学时3，总学时54
5．学分分配：3学分
（二）开设目的
离散数学是现代数学的一个重要分枝，是计算机科学基础理论的核心课程。离散数学形成于上世纪七十年代初期，它是随着计算机科学的发展而逐步建立的一门新兴的工具性学科。
离散数学以离散量的结构及其相互关系为主要研究目标，其研究对象一般的是有限或可数个元素，它与计算机科学中的数据结构、操作系统、编译理论、算法分析、逻辑设计、系统结构、容错诊断、机器定理证明、专家系统等课程联系紧密。通过本课程的学习，不仅为学习者打下坚实的专业理论基础，而且可以培养学习者的严密的逻辑推导、高度的抽象思维和慎密概括的能力。
掌握：掌握形式语言与非形式语言的转换；掌握对全称、存在命题的否定；掌握对全称条件命题的否定。
了解：了解证明谓词推论的有效性。
第三章基础数论与证明方法
教学目的
理解并掌握各种基本的证明方法。
主要内容
第一节直接证明与反例I：引言
第二节直接证明与反例II：有理数
第三节直接证明与反例III：整除性
第四节直接证明与反例IV：分情况证明与商－余数定理
教学要求
理解：理解集合的相关概念，理解布尔代数的相关概念。
掌握：掌握集合运算规律；掌握证明子集的方法；掌握证明集合之间关系的方法；掌握布尔代数的基本证明技巧。
了解：了解悖论与停机问题。
第六章计数与概率
教学目的
了解排列组合、概率的基本概念、基本原理，会基本公式；掌握带与不带重复的排
列与组合的计数公式。
了解：命题逻辑在加法电路中的应用
第二章谓词逻辑
教学目的
理解谓词、量词的概念，理解命题逻辑与谓词逻辑的区别与联系。掌握用量词描述
问题的方法，掌握处理谓词逻辑问题的技巧。
主要内容
第一节谓词与量词I
第二节谓词与量词II
第三节含多个量词的谓词逻辑
第四节谓词逻辑的推理
教学要求
理解：理解谓词的概念；理解全称与存在量词；理解全称条件命题的变形。
掌握：掌握证明集合等势的基本方法。
了解：了解可计算性的概念。
第八章递归
教学目的
理解递归的一般性定义，掌握解二阶常系数线性齐次递归问题的方法。
主要内容
第一节递归序列
第二节解递归关系的迭代法
第三节二阶常系数线性齐次递归
第四节一般递归的定义
教学要求
理解：理解递归的定义。
掌握：掌握求解二阶常系数线性齐次递归的方法
了解：了解一般回归的定义。
第九章关系
教学目的
理解关系的概念与性质；理解并掌握等价关系与集合划分之间的一一对应的关系；
理解偏序关系的基本概念。
主要内容
第一节集合上的关系
第二节自反性、对称性与传递性
第三节等价关系
第四节密码学的应用
第五节偏序关系
基本要求
理解：理解关系的定义，关系的自反、对称、传递性质，理解等价关系。
第七章函数
教学目的
从关系的角度理解函数，掌握用关系的概念处理函数问题的技巧。理解基数，以及
基数比较的概念，掌握求集合基数以及基数比较的基本方法。
主要内容
第一节函数的定义
第二节函数的性质
第三节应用：鸽笼原理
第四节函数的复合
第五节基数与可计算性
教学要求
理解：理解函数、单射、满射、函数可逆、函数复合的概念；理解鸽笼原理；理解集合的基数、集合等势的概念。
二、教学内容
第一章命题逻辑
教学目的
了解逻辑的基本问题，理解理解的基本概念，掌握处理逻辑问题的基本方法。
主要内容
第一节命题公式与逻辑等价性
第二节条件命题
第三节有效与无效的推理
第四节应用：数值逻辑电路
第五节应用：加法电路
教学要求
理解：理解命题、逻辑联结词、逻辑等价性、有（无）效推理等基本概念
掌握：掌握构造真值表的方法；掌握证明命题公式逻辑等价的方法；掌握简单的逻辑电路的设计方法。
（五）先修课程
高等代数
（六）后继课程
数据结构，操作系统等
（七）考核方式
闭卷考试
（八）使用教材
Susanna S.E.《Discrete Mathematics with Applications》(Third Edition). Beijing: Higher Education Press，2005
注：写明各学期教学总时数及各周学时数。
第五节直接证明与反例V：Floor与Ceiling函数
第六节间接证明：反证法与换位证法
第七节两个经典的定理
第八节应用：算法
教学要求
理解：理解整数的相关结论；理解对存在性命题的构造与非构造性证明的思想；理解商－余数定理、Floor与Ceiling函数、求商和余数的除法算法、求最大公约数的Euclidean算法。
深圳大学数学与计算科学学院
课程教学大纲
（2006年10月重印版）
课程编号22143111
课程名称离散数学
课程类别专业必修
教材名称离散数学
制订人李国
审核人陈之兵
2005年4月修订
一、课程设计的指导思想
（一）课程性质
1．课程类别：专业必修课
2．适应专业：信息与计算科学、数学与应用数学
3．开设学期：第三学期
主要内容
第一节引言
第二节概率树与乘法原理
第三节不相交集合的计数：加法原理
第四节排列与组合
第五节可重复的组合
第六节组合公式及其证明，贝叶斯公式，独立事件
教学要求
理解：理解概率树的概念。
掌握：掌握乘法原理、加法原理、可重复组合的计数方法。
了解：了解概率公理、期望条件概率、贝叶斯公式、独立事件等概率统计的基本概念；了解二项式定理，会排列、组合。
教学要求
理解：理解良序原理。
掌握：掌握数学归纳法。
了解：了解怎样应用数学归纳法证明算法的正确性。
第五章集合论
教学目的
理解并掌握集合论的基本定义与基本证明方法；从布尔代数的角度，理解并统一命
题逻辑运算系统与集合运算系统。
主要内容
第一节集合论基本定义
第二节集合的性质
第三节证伪，代数证明与布尔代数
第四节罗素悖论与停机问题
掌握：掌握证明关系等价性、偏序关系的方法。
了解：关系在密码学中的应用。
第十章图和树
教学目的
了解图论的基本问题以及处理问题较独特的方法，理解其基本概念，理解并掌握求
最小生成树的Kruskal与prim算法。
主要内容
第一节引言
第二节路与回路
第三节图的矩阵表示
第四节同构图
第五节树
第六节生成树
基本要求
理解：理解图、度、路、回路、欧拉图、汉密尔顿图、点割集、割边、树、根树、二叉树等基本概念。
掌握：掌握图的矩阵表示方法；掌握最小生成树的Kruskal与prim算法。
了解：了解图的同构的概念。
注：根据各课程的具体情况编写，但必须写明各章教学目的、要求、内容提要。
三、课时分配及其它
（一）课时分配
课程总教学时数为54学时，安排在第三学期，分单双周上课，共18周。具体分配如下
第一章命题逻辑6学时
（九）参考书目
（1）左孝凌，李为鑑，刘永才.《离散数学》.上海：上海科学技术文献出版社，2003.
（2）Kolman B., Busby R.C., and Ross S. Discrete Mathematical Structures.Beijing:TsinghuaUniversityPress, 2002
主要考查学生对离散数学基本概念、基本方法与基本理论的一般理解）、计算题(主要考查学生对离散数学基本方法的具体、灵活应用)、证明题(主要考查学生对离散数学基本理论、基本方法的综合运用能力)各占约1/3。难易比例控制在15％难、50％适中、35％易之间。涉及教材章的100％，节的85％，知识点的70％左右。试卷末设置难度系数在0.7～0.9、分值为30分的附加题，目的在于筛选基础知识扎实、探索精神强烈、创新意识浓厚的同学。试卷采用A、B卷。
掌握：掌握对全称条件命题的直接证法、举反例法、反证法与换位证法；掌握两个经典定理证明的基本技巧。
了解：了解对数学问题如何选取证明方式的策略。
第四章序列与数学归纳法
教学目的
理解并掌握数学归纳法。
主要内容
第一节序列
第二节数学归纳法I
第三节数学归纳法II
第四节强数学归纳法与良序原理
第五节应用：算法正确性的证明
（三）基本要求
理解逻辑的基本概念，掌握真值表证明问题的方法；掌握基本的证明方法；理解等价关系、偏序关系等基本概念；从关系的角度理解函数，掌握基本的判断函数的基数或比较函数基数的方法；理解布尔代数的基本理论；理解图论的基本概念与理论。
（四）主要内容
命题与谓词逻辑，数论及证明方法，序列与数学归纳法，集合论，布尔代数，计数与概率，函数，递归，关系，图论