第1章1-2节-逻辑符号集合及其运算.ppt

*;教材： 离散数学（第2版） 屈婉玲、耿素云、张立昂 主编 清华大学出版社, 2008.2 教学参考书： 离散数学习题解答与学习指导（第2版） 屈婉玲、耿素云、张立昂 主编 清华大学出版社，2008.2 ; 离散数学是现代数学的一个重要分支。是计算机科学中基础理论的核心课程，为计算机科学提供了有力的理论基础和工具。离散数学的基本思想、概念和方法广泛地渗透到计算机科学与技术发展的各个领域，而且其基本理论和研究成果更是全面而系统地影响和推动着其发展。 离散数学的内容十分丰富，最重要，最核心的是：数理逻辑、集合论、图论、组合计数理论和代数系统。 本课程将围绕这五个部分相关知识展开介绍。;数理逻辑：是用数学方法来研究推理的形式结构和推理规律的数学学科，它与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切的联系。命题逻辑和一阶谓词逻辑是数理逻辑中最成熟的部分，在计算机科学中应用最为广泛，其中命题逻辑是数理逻辑的最基础部分，谓词逻辑是在它的基础上发展起来的。 本课程在第二，三两章中介绍数理逻辑中的命题逻辑和一阶谓词逻辑的内容。 ;实例一：聪明助手问题;现代数学中，每个对象(如数，函数等)本质上都是集合，都可以用某种集合来定义，数学的各个分支，本质上都是在研究某一种对象集合的性质。集合论的特点是研究对象的广泛性，它也是计算机科学与工程的基础理论和表达工具，而且在程序设计，数据结构，形式语言，关系数据库，操作系统等都有重要应用。 本课程在第四，五章中介绍集合论中的关系和函数部分的内容。;实例二：理发师悖论（Paradox）;图论：是一个古老的数学分支，它起源于游戏难题的研究。图论的内容十分丰富，应用得相当广泛，许多学科，诸如运筹学、信息论、控制论、网络理论、博弈论、化学、生物学、物理学、社会科学、语言学、计算机科学等，都以图作为工具来解决实际问题和理论问题。随着计算机科学的发展，图论在以上各学科中的作用越来越大，同时图论本身也得到了充分的发展。 本课程在第六，七两章中介绍与计算机科学关系密切的图论的内容。 ;近代图论的历史可追溯到18世纪的七桥问题—穿过K?nigsberg城的七座桥，要求每座桥通过一次且仅通过一次。 Euler1736年证明了不可能存在这样的路线。;Euler 定理;组合计数理论：是一个研究离散结构的存在、计数、分析和优化等问题的数学分支。上世纪60年代以来，随着计算机的诞生，组合计数理论得到了迅速发展， “为上世纪计算机革命奠定了基础”，计算机之所以被称之为电脑，就是因为计算机被人编写了程序，而程序就是算法。算法运行效率和存储需求分析需要大量的组合计数思想，正是因为有了组合算法，才使人感到计算机好像是有思维的。 本课程在第八，九和十三章中介绍组合计数理论中的组合计数基础、容斥原理和递推方程与生成函数等内容。 ;我国古代的河洛图(幻方)问题;组合数学中有许多象幻方这样精巧的结构。 1977年美国旅行者1号、2号宇宙飞船就带上了幻方以作为人类智慧的信号。;阿基米德手稿;在论文中阿基米德是在计算把14条不规则的纸带拼成正方形一共能有多少种不同的拼法？ ——现在称为Tiling问题; ;模式: 对任意一个排列π , 最小的元素用１代替，次小的元素用２代替……以此类推，这样得到的排列叫π的模式。 例如 　　　914的模式为：312 　　　37925 的模式为： 24513;栈排序问题(Knuth, 1960’s);栈排序问题(Knuth, 1960’s);代数系统：这部分内容属于近世代数的范畴，近世代数是研究具有运算的集合，它第一次揭示了数学系统的多变性与丰富性。代数结构理论可用于计算机算法的复杂性分析，研究抽象数据结构的性质及操作，同时也是程序设计语言的理论基础。 本课程教材在第十一至十四章中介绍代数系统有关内容。 ;20世纪20年代，由Karinthy提出。 1950年， Pool 和 Kochen提出这样一个问题：“两个毫无关系的人，要让他们互相认识，至少要经过多少人？” 美国哈佛大学社会心理学家S. Milgram在1967年做过一项有趣的实验，据说他从内布拉斯加州的奥马哈随机选了300人，然后请他们每个人尝试寄一封信到波士顿的一位证券业务员。寄信的规则很简单，就是任何收信者只能把信寄给自己熟识的人。 ;相关重要结论;无尺度网络的一个例子;第1章 数学语言与证明方法;本章主要内容;1.1 逻辑符号;命题与真值;联结词;联结词(续);实例;实例(续);命题公式;重言式,矛盾式与可满足式;基本等值式（16组）;基本等值式(续);重要推理规则(推理定律，9组)