离散数学课件

1、离散数学,信 息 科 学 与 工 程 学 院,Discrete Mathematics,2,离散数学的发展,18世纪以前, 数学基本上是研究离散对象的数量和空间关系的科学。 之后,因天文学,物理学的发展,如行星轨道,牛顿三大力学定律等研究,极大地推动了连续数学(以微积分,数学物理方程, 实、复变函数论为代表)的发展。 离散对象的研究则处于停滞状态。 20世纪30年代, 图灵提出计算机的理论模型图灵机。 这种模型早于实际制造计算机十多年,现实的计算机的计算能力, 本质上和图灵机的计算能力一样。 由于在计算机内,机器字长总是有限的, 它代表离散的数或其它离散对象，因此随着计算机科学和技术的迅猛发展

2、,离散数学就显得重要。,3,为什么要学离散数学,计算机求解的基本模式是：实际问题 数学建模 算法设计 编程实现 离散数学为数学建模打下知识基础、为算法设计提供具体指导 离散数学结构实际上就是通用的抽象的模式的集合，告诉你各种模式的本质特征和它们之间的关系，以及选用它们的策略；告诉你哪些问题是可解的，哪些是当前在图灵机模型上无（最优）解的，哪些是可以得到近似/较优解的。 简而言之，离散数学的作用就在于训练运用离散结构作为问题的抽象模型、构造算法、解决问题的能力。,课程内容,数理逻辑(Mathematical Logic) 命题逻辑 谓词逻辑 集合论(Sets Theory) 集合与关系 代数系统

3、(Algebraic Structures) 图论(Graph Theory),4,5,离散数学的应用举例,关系型数据库的设计（关系代数） 表达式解析（树） 优化编译器的构造（闭包） 编译技术、程序设计语言（代数结构） Lisp和Prolog、人工智能、自动推理、机器证明（数理逻辑） 网络路由算法（图论） 游戏中的人工智能算法（图论、树、博弈论） 专家系统（集合论、数理逻辑知识和推理规则的计算机表达） 软件工程团队开发时间和分工的优化（图论网络、划分） (各种)算法的构造、正确性的证明和效率的评估（离散数学的各分支）,“数学是解决信息检索和自然语言处理的最好工具，它能非常清晰的描述这些领域的实

4、际问题并且给出漂亮的解决方案”. -吴军 自然语言处理：Google中英文翻译 搜索引擎,6,自然语言处理,7,Machine translation Information Extraction Information Retrieval, question answering Text classification, spam filtering, etc.,新问题及新应用,8,Computational advertising Estimate click-through rate Optimal ads placement ,Search engine Query classifica

5、tion Ranking Spam detection,新问题及新应用推荐系统,Recommendation contributes 35% of sales in Amazon,9,10,KDD Cup,11,12,引 言 1,离散数学是随着计算机科学的发展而逐步建立的，它形成于七十年代初期，是一门新兴的工具性学科。 离散数学是现代数学的一个重要分支，是计算机科学与技术的理论基础，所以又称为计算机数学，是计算机科学与技术专业的核心、骨干课程。 它以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。 内容包含：数理逻辑、集合论

6、、代数结构与布尔代数、图论等。,13,引 言 2,学习该课程的目的： 一方面，它给后继课，如数据结构、编译系统、操作系统、数据库原理、软件工程与方法学、计算机网络和人工智能等，提供必要的数学基础； 另一方面，通过学习离散数学，可以培养和提高自己的抽象思维和逻辑推理能力，为以后的软、硬件学习和研究开发工作，打下坚实的数学基础。,14,引 言 3,教学要求： 通过该课程的学习，学生应当了解并掌握计算机科学中普遍采用的离散数学中的一些基本概念、基本思想、基本方法。 自学要求： 通过反复看书及做课后习题，来加深对该课程中的一些基本概念的理解，逐步提高自己的抽象思维和逻辑推理能力。,引 言 4,考核方式

7、： 笔试70+平时30 平时： 点名 作业 回答问题,15,16,引 言 4,教材： 离散数学 左孝凌等 上海科学技术文献出版社 参考书目： 1、离散数学 耿素云等 高等教育出版社 2、Discrete Mathematics and Its Applications，Kenneth H. Rosen，China Machine Press(机械工业出版社)，McGraw-Hill（1999）,17,第一章 命题逻辑,1-1 命题及其表示法 基本概念 命题：能够判断真假的陈述句。 命题的真值：命题的判断结果。真值只取两个值： 真、假，分别用T和F表示。 真命题：真值为真的命题。 假命题：真值为

8、假的命题。 判断命题的两个步骤： 1、是否为陈述句； 2、是否能够判断真假（或有确定的真值）。,18,第一章 命题逻辑,例：判断下列句子是否为命题。 上海是个小村庄。 存在外星人。 禁止吸烟！ 北京是中国的首都。 4是素数或6是素数。 今天你吃了吗？ 11+1=100 我正在说谎。 (9)x=3 解：命题(F)，命题(待定)，不是命题(祈使句)，命题(T)，命题(F)，不是命题(疑问句), 不是命题(由上下文确定), 不是命题(悖论),(9)不是命题（有变量）。,19,第一章 命题逻辑,命题及其真值的抽象化 在本书中，用大写英文字母A，B， ，P，Q，或带下标的大写字母Ai或数字12表示命题。

9、 如： A：罗纳尔多是球星。 P：5是负数。 P3：明天天气晴。 皆为符号化的命题，其真值依次为T、F、T或F。,20,第一章 命题逻辑,命题常量： 表示确定命题的命题标识符。 如：A：罗纳耳朵是球星。 命题变元： 不表示确定命题的命题标识符。可以表示任意命题，故不能确定真值，不是命题。 命题变元的指派： 用一个特定命题取代命题变元,21,第一章 命题逻辑,命题的分类 简单/原子命题：由不能再分解为更简单的陈述句的陈述句构成。 如上例中的命题。 复合命题：由简单命题通过联结词联结而成的陈述句。,22,第一章 命题逻辑,1-2 联结词 定义1-2.1 设P为命题，复合命题“非P”（或“P的否定”

10、）称为P的否定式，记作 P，符号 称为否定联结词。 运算规则：属于单目运算符,23,第一章 命题逻辑,定义1-2.2 设P,Q为二命题，复合命题“P并且Q”（或“P与Q”）称为P与Q的合取式，记作P Q，符号称为合取联结词。 运算规则：属于双目运算符,24,第一章 命题逻辑,合取运算特点：只有参与运算的二命题全为真时，运算结果才为真，否则为假。 自然语言中的表示“并且”意思的联结词，如“既又”、“不但而且”、“虽然但是”、“一面一面”等都可以符号化为 。 注意：不要见到“与”或“和”就使用联结词 ！ 例题：小王和小李是好朋友。,25,第一章 命题逻辑,定义1-2.3 设P,Q为二命题，复合命题

11、“P或Q” 称为P与Q的析取式，记作P Q，符号称为析取联结词。 运算规则：属于双目运算符,26,第一章 命题逻辑,析取运算特点：只有参与运算的二命题全为假时，运算结果才为假，否则为真。 这里的析取运算只能表示自然语言中的“可兼或”的意思，不能表示自然语言里的“排斥或” 。例如： （1）小王爱打球或爱跑步。 设P：小王爱打球。 Q：小王爱跑步。 则上述命题可符号化为：P Q,27,第一章 命题逻辑,（2）今天晚上我在家看电视或去剧院看戏。 设P：在家看电视。 Q：去剧院看戏。 则上述命题就不可简单符号化为：P Q 而应描述为(P Q) ( PQ) 在汉语中，还有一些“或”字，实际不是命题联结词

12、。如： 小明昨天做了20或30道题目。 此例中的“或”字，只表示题目的近似数目，不能用析取联结词表达，它是一个原子命题。,28,第一章 命题逻辑,定义1-2.4 设P,Q为二命题，复合命题“如果P，则Q” 称为P与Q的条件式，记作P Q，并称P为条件式的前件，Q为条件式的后件，符号称为条件联结词。 运算规则：属于双目运算符,29,第一章 命题逻辑,条件运算P Q表示的逻辑关系是：Q是P的必要条件。 自然语言中可用P Q条件式表述命题格式有： “只要P，就Q” 、 “因为P，所以Q” “P仅当Q” 、 “只有Q才P” “除非Q才P” 、 “除非Q，否则非P”等。 与自然语言的不同：前件与后件可以

13、没有任何内在联系！,30,第一章 命题逻辑,例：如果3+3=6，则雪是白色的。 如果明天下雨，则我就不去上课了。 均可表示为P Q。 只要a能被4整除，则a能被2整除。 只有a能被2整除，a才能被4整除。 除非a能被2整除，否则a不能被4整除。 令P: a能被4整除。 Q: a能被2整除。 均可表示为P Q。,31,第一章 命题逻辑,定义1-2.5 设P,Q为二命题，复合命题“P当且仅当Q” 称为P与Q的双条件式，记作P Q，符号称为双条件联结词。 运算规则：属于双目运算符,32,第一章 命题逻辑,双条件运算P Q表示的逻辑关系是：P与Q互为充分必要条件。相当于(P Q) (Q P) 例题：两

14、个三角形全等，当且仅当它们的三组对应边相等。 若两个圆的面积相等，则它们的半径相等，反之亦然。 均可表示为P Q。,33,第一章 命题逻辑,以上5种最基本、最常用、最重要的联结词可以组成一个集合，成为一个联结词集，其运算的优先级为：， ，对于同一级者，先出现者先运算。,34,第一章 命题逻辑,1-3 命题公式与翻译 基本概念 简单命题/命题常项/命题常元：真值唯一确定的陈述句。 命题变项/命题变元：真值可以变化的陈述句。 命题常项与命题变项都可以用P,Q,R等表示，具体情况由上下文确定。 合式公式/命题公式：将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串。 当使用联结词集 ，时，合

15、式公式定义如下：,35,第一章 命题逻辑,定义1-3.1 命题演算的合式公式（wff）规定为： （1）单个命题变元是合式公式，并称为原子命题公式。 （2）若A是合式公式，则( A)也是合式公式。 （3）若A，B是合式公式，则(A B)，(A B)，(A B)，(A B)也是合式公式。 （4）只有有限次地应用(1)(3)形成的符号串才是合式公式。 合式公式也称为命题公式或命题形式，并简称为公式。,36,第一章 命题逻辑,(P Q) , (r t) e , P，(P)等均为合式公式， 而(pq)(q)，(pq，(pq)q) 等不是合式公式。 上述归纳定义方式中的符号A,B不同于具体公式里面的P,Q,r等符号，可以用来表示任意的合式公式,属于元语言符号。 对象语言：用来描述研究对象的语言。 元语言：用来描述对象语言的语言。,37,第一章 命题逻辑,有了联结词的合式公式概念，我们可以把自然语言中的有些语句，翻译成数理逻辑中的符号形式。 例1、符号化下列命题： 他既聪明又用功。 设 A：他聪明。B：他用功。 则命题为 A B。,38,第一章 命题逻辑,例2、有人最初说