[工学]离散数学第一章.ppt

离散数学 Discrete Mathematics 前言 离散数学,是现代数学的一个重要分支,计算机科学与技术一级学科的核心课程,是整个计算机学科的专业基础课。 离散数学是以研究离散量的结构和相互间的关系为主要目标,其研究对象一般地是有限个或可数个元素,因此它充分描述了计算机科学离散性的特点。 离散数学是随着计算机科学的发展而逐步建立的,它形成于七十年代初期,是一门新兴的工具性学科。 离散数学课程设置 计算机系核心课程 信息类专业必修课程 其它类专业的重要选修课程 后续课程 数据结构 编译理论 系统结构 人工智能 数据库原理 …… …… 离散数学的发展 18世纪以前, 数学基本上是研究离散对象的数量和空间关系的科学。 之后,因天文学,物理学的发展,如行星轨道,牛顿三大力学定律等研究,极大地推动了连续数学（以微积分,数学物理方程,实、复变函数论为代表）的发展。 离散对象的研究则处于停滞状态。 离散数学的发展（续） 20世纪30年代, 图灵提出计算机的理论模型——图灵机。 这种模型早于实际制造计算机十多年,现实的计算机的计算能力, 本质上和图灵机的计算能力一样。 由于在计算机内,机器字长总是有限的, 它代表离散的数或其它离散对象,因此随着计算机科学和技术的迅猛发展,离散数学就显得重要。 离散数学的发展（续） 算法化思维：许多问题都可以通过构造一个可以被程序实现的算法来解决。它的三个步骤是：构造（选择合适的离散模型和操作步骤）、验证（算法的正确性）、评估（时间和空间的复杂性）。 应用和建模：在可以想到的任何研究领域都有离散数学的应用。计算科学、化学、植物学、动物学、语言学、地理、经济学等,构造离散模型都是极其有用的解决问题的方法。 计算机求解的基本模式是：实际问题 ? 数学建模 ? 算法设计 ? 编程实现 离散数学为数学建模打下知识基础、为算法设计提供具体指导 离散数学结构实际上就是通用的抽象的模式的集合。告诉你各种模式的本质特征和它们之间的关系,以及选用它们的策略；告诉你哪些问题是可解的,哪些是当前在图灵机模型上无（最优）解的,哪些是可以得到近似/较优解的。 简而言之,离散数学的作用就在于训练运用离散结构作为问题的抽象模型、构造算法、解决问题的能力。 教学内容 教材与教学参考书 教材： 耿素云、屈婉玲,离散数学（修订版）,高等教育出版社, 2004. 教学参考书： 左孝凌、李为槛、刘永才,离散数学,上海科学技术文献出版社. 离散数学的学习要领 概念（正确） 必须掌握好离散数学中大量的概念 判断（准确） 根据概念对事物的属性进行判断 推理（可靠） 根据多个判断推出一个新的判断 离散数学的学习要领 本课程特点定义+定理+例题 多做习题,完成作业想的清楚,说的明白,写的工整 考试方式 平时成绩 40％ 期末考试 60％ 计算机科学技术系 孟志刚 Email addr Tel Web:/courses/lssx/longtime/index.htm 数理逻辑部分 第1章 命题逻辑基本概念 第2章 命题逻辑等值演算 第3章 命题逻辑的推理理论 数理逻辑 数理逻辑—用数学的方法研究推理、证明等问题的学科。 这里所指的数学方法就是引进一套符号体系的方法。 数理逻辑又称符号逻辑,它是从量的侧面来研究思维规律的。 数字电子计算机是数理逻辑与电子学结合的产物。 第1章 命题逻辑基本概念 1.1 命题与联结词 1.2 命题公式及其赋值 习题1 1.1 命题与联结词 命题与真值 原子命题 复合命题 命题常项 命题变项 联结词 命题与真值 命题: 判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 感叹句、祈使句、疑问句都不是命题 陈述句中的悖论以及判断结果不惟一确定的也不是 命题 例 下列句子中哪些是命题？ (1) 是无理数. (2) 2 + 5 ＝8. (3) x + 5 ＞ 3. (4) 你有铅笔吗？ (5) 这只兔子跑得真快呀！ (6) 请不要讲话！ (7) 本命题是假的. 命题的分类 简单命题(原子命题)： 简单陈述句构成的命题 复合命题： 由简单命题与联结词按一定规则复合 而成的命题 简单命题符号化 联结词与复合命题 1.否定式与否定联结词“?” 定义 设p为命题,复合命题 “非p”（或 “p的否