《--逻辑符号,集合及其运算》由会员分享，可在线阅读，更多相关《--逻辑符号,集合及其运算（62页珍藏版）》请在金锄头文库上搜索。
1、1离散数学主讲教师：李向军南昌大学信息工程学院计算机系2010年9月教材：离散数学（第2版）屈婉玲、耿素云、张立昂 主编清华大学出版社, 2008.2教学参考书：离散数学习题解答与学习指导（第2版）屈婉玲、耿素云、张立昂 主编清华大学出版社，2008.2教材与教学参考书离散数学是现代数学的一个重要分支。是计算机科学中基础理论的核心课程，为计算机科学提供了有力的理论基础和工具。离散数学的基本思想、概念和方法广泛地渗透到计算机科学与技术发展的各个领域，而且其基本理论和研究成果更是全面而系统地影响和推动着其发展。离散数学的内容十分丰富，最重要，最核心的是：数理逻辑、集合论、图论、组合计数理论和代数系
2、统。本课程将围绕这五个部分相关知识展开介绍。n数理逻辑：是用数学方法来研究推理的形式结构和推理规律的数学学科，它与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切的联系。命题逻辑和一阶谓词逻辑是数理逻辑中最成熟的部分，在计算机科学中应用最为广泛，其中命题逻辑是数理逻辑的最基础部分，谓词逻辑是在它的基础上发展起来的。本课程在第二，三两章中介绍数理逻辑中的命题逻辑和一阶谓词逻辑的内容。实例一：聪明助手问题著名物理学家爱因斯坦出过如下一道题：一个土耳其商人，想找一个十分聪明的助手协助他经商，有两 个人前来应聘。这个商人为了试一试哪一个聪明些，就把两个 人带进一间漆黑的屋子里，他打开电灯后说
3、：“这张桌子上有 五顶帽子，两顶是红色的，三顶是黑色的。现在，我把灯关掉 ，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子 戴在头上，在我开灯后，请你们尽快地说出自己头上戴的帽子 是什么颜色的。”说完之后，商人将电灯关掉，然后三人都摸 了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来接 着把电灯打开，这时那两个应试者看到商人头上戴的是一顶红 帽子，过了一会儿，其中一个人便喊到：“我戴的是黑帽子。 ”请问这个人猜得对吗？是怎么推导出来的？答案：“猜对对的人戴着黑帽子”是真的，所以猜对对的人肯定的 说说：“我戴的是黑帽子”。 现代数学中，每个对象(如数，函数等)本质上都是集合， 都可以用
4、某种集合来定义，数学的各个分支，本质上都 是在研究某一种对象集合的性质。集合论的特点是研究 对象的广泛性，它也是计算机科学与工程的基础理论和 表达工具，而且在程序设计，数据结构，形式语言，关 系数据库，操作系统等都有重要应用。本课程在第四，五章中介绍集合论中的关系和函数部 分的内容。n集合论：是研究集合一般性质的数学分支，它的创始人是康托尔(，18451918)。在实例二：理发师悖论（Paradox）在某个城市中有一位理发师，他的广告词是这样写的：“本人 的理发技艺十分高超，誉满全城。我将为本城所有不给自己刮脸 的人刮脸，我也只给这些人刮脸。我对各位表示热诚欢迎！”来找 他刮脸的人络绎不绝，自
5、然都是那些不给自己刮脸的人。可是， 有一天，这位理发师从镜子里看见自己的胡子长了，他本能地抓 起了剃刀，你们看他能不能给他自己刮脸呢？如果他不给自己刮 脸，他就属于“不给自己刮脸的人”，他就要给自己刮脸，而如果 他给自己刮脸呢？他又属于“给自己刮脸的人”，他就不该给自己 刮脸。这与由著名数学家伯特兰罗素（Russel，18721970）提出 的罗素悖论问题相似：把所有集合分为2类，第一类中的集合以其自身为元素，第 二类中的集合不以自身为元素，假令第一类集合所组成的集合为 P，第二类所组成的集合为Q，于是有P=AAA，Q=AAA， 问，QP 还是 QQ？n图论：是一个古老的数学分支，它起源于游戏
6、难题的研究。图论的内容十分丰富，应用得相当广泛，许多学 科，诸如运筹学、信息论、控制论、网络理论、博弈论 、化学、生物学、物理学、社会科学、语言学、计算机科学等，都以图作为工具来解决实际问题和理论问题。 随着计算机科学的发展，图论在以上各学科中的作用越 来越大，同时图论本身也得到了充分的发展。本课程在第六，七两章中介绍与计算机科学关系密 切的图论的内容。 近代图论的历史可追溯到18世纪的七桥问题 穿过Knigsberg城的七座桥，要求每座桥通过 一次且仅通过一次。Euler1736年证明了不可能存在这样的路线。实例三：哥尼斯堡七桥问题Euler 定理如果一个图包含一条经过每条边恰好一次的闭途径
7、， 则称这个图为欧拉图。对任意的非空连通图，若它是欧拉的, 当且仅当它没 有奇度点。KnigsbergKnigsberg桥对应的图桥对应的图n组合计数理论：是一个研究离散结构的存在、计数、 分析和优化等问题的数学分支。上世纪60年代以来，随着 计算机的诞生，组合计数理论得到了迅速发展， “为上世 纪计算机革命奠定了基础”，计算机之所以被称之为电脑 ，就是因为计算机被人编写了程序，而程序就是算法。算 法运行效率和存储需求分析需要大量的组合计数思想，正 是因为有了组合算法，才使人感到计算机好像是有思维的 。 本课程在第八，九和十三章中介绍组合计数理论中的组 合计数基础、容斥原理和递推方程与生成函数
8、等内容。 我国古代的河洛图(幻方)问题传说在公元前23世纪大禹 治水的时候，在黄河支流 洛水中，浮现出一个 大乌 龟，甲上背有9种花点的 图案，人们将图案中的花 点数了一下，竞惊奇地发 现9种花点数正巧是19 这9个数，各数位置的排 列也相当奇妙，横的3行 、纵的3列以及两对角线 上各自的数字之和都为15 。上图为三阶洛书实例三：幻方问题组合数学中有许多象幻方这样精巧的结构。1977年美国旅行者1号、2号宇宙飞船就带 上了幻方以作为人类智慧的信号。神 农 幻 方2200BC1 15 14 412 6 7 98 10 11 513 3 2 16 15世纪 阶 幻 方阿基米德手稿上图为一份用希腊文
9、写在羊皮纸上的阿基米德手稿副本, 最近科学家借助现代科技手段初步破译了古希腊数学家阿基米德的这篇论文, 结论是这篇被称作Stomachion的论文解决的是组合数学问题。 实例四：Tiling（阿基米德手稿）问题在论文中阿基米德是在计算把14条不规则的纸带拼成正方形一共能有多少种不同的拼法？ 现在称为Tiling问题n当今数学家借助计算机得出的答案是17152种拼法，这在当时是相当困难的。 Periodic Tilings Non-Periodic TilingsPenrose Tilings Symmetric Tilings Symmetric Tilings 模式: 对任意一个排列 , 最
10、小的元素用 代替，次小的元素用代替以此类推 ，这样得到的排列叫的模式。例如914的模式为：31237925 的模式为： 24513实例五：栈排序问题(Knuth, 1960s)栈排序问题(Knuth, 1960s)避免排列：一个排列是避免 的，当且仅当它的任意子序列中没有 模式。例如 132564是避免 312的排列 146235是包含312的排列栈排序问题(Knuth, 1960s)87654321避免312排列n代数系统：这部分内容属于近世代数的范畴，近世代数是研究具有运算的集合，它第一次揭示了数学系统的多变性与丰富性。代数结构理论可用于计算机算法的复杂性分析，研究抽象数据结构的性质及操作
11、，同时也是程序设计语言的理论基础。本课程教材在第十一至十四章中介绍代数系统有关内容。 20世纪20年代，由Karinthy提出。1950年， Pool 和 Kochen提出这样一个问题：“两个 毫无关系的人，要让他们互相认识，至少要经过多 少人？”美国哈佛大学社会心理学家S. Milgram在1967年做 过一项有趣的实验，据说他从内布拉斯加州的奥马 哈随机选了300人，然后请他们每个人尝试寄一封 信到波士顿的一位证券业务员。寄信的规则很简单 ，就是任何收信者只能把信寄给自己熟识的人。 实例五：无尺度网络问题相关重要结论“6度分离” 对每个人来说，平均大约只需要 通过个人就能将信寄到目的地。研
12、究无尺度网络及其结构，对于防备黑客攻 击、防治流行病、和开发新药等，都具有重 要的意义。在1999年，Barabasi et al.发现在因特网上 ，任意两个网页间的链接最多为19次。 (Nature 401, 1999)无尺度网络的一个例子因特网是一个无尺度 网络，左图的星爆形 结构描绘了从某一测 试站点到其他约十万 个站点的最短连结路 径。图中以相同的颜 色来表示相类似的站 点。第1章 数学语言与证明方法本章主要内容1.1 常用数学符号集合符号、运算符号、逻辑符号1.2 集合及其运算1.3 证明方法概述251.1 逻辑符号26关键知识点： 命题与真值 联结词(, ,) 命题公式(重言式,矛
13、盾式,可满足式)重要等值式 重要推理规则 个体,个体域与谓词全称量词与存在量词命题与真值命题:具有确定真值的表达判断的陈述句, 通常用p,q,r等 表示（即命题符号化） 命题的真值:作为命题所表达的判断只有两个结果：正确 和错误，此结果称为命题的真值。命题是正确的，称此命题的真值为真；命题是错误 的，称此命题的真值为假。在数理逻辑中，命题的真值的真和假，有时分别用 1和0来表达，也有时分别用T(True)和F(False)来表 达。（即真值的符号化） 真命题:真值为真的命题 假命题:真值为假的命题 例如, p:2+2=4, q:3是偶数 它们都是命题, p是真命题, q是假命题.27联结词l否
14、定联结词否定式p: 非p (p的否定)p 为真当且仅当p为假l合取联结词合取式pq:p并且q (p与q)pq为真当且仅当p与q同时为真l析取联结词析取式pq: p或qpq为假当且仅当p与q同时为假28联结词(续)29 排斥或联结词排斥或p q: p并且非q, 或者q并且非pp q为真当且仅当p与q中一个为真,另一个为假蕴涵联结词蕴涵式pq:如果p,则qpq为假当且仅当 p 为真 q 为假 等价联结词等价式pq:p当且仅当qpq为真当且仅当p与q同时为真或同时为假实例设p:2是偶数, q:1+1=3, 则30p的真值为 1q的真值为p的真值为q的真值为pq的真值为pq的真值为pq的真值为 pq的
15、真值为pq的真值为pq的真值为p q的真值为p q的真值为p q的真值为p q的真值为0010110111001pq的真值为pq的真值为00实例(续)pq的真值为31pq的真值为pq的真值为pq的真值为0111又设 r:今天是星期一, s:明天是星期二, t:明天是星期三rs的真值为rt的真值为1不定命题公式命题变项:取值为0或1的变元, 也用p,q,r等表示. 命题公式:用联结词和圆括号把命题和命题变项按照一定 规则连接起来的符号串, 常用A,B,C等表示. 例如, A=(pq)(rp)公式的赋值:对公式中每一个命题变项给定一个值(0或1). 公式的成真赋值:使公式为真的赋值. 公式的成假赋值:使公式为假的赋值. 例如, p=1,q=1,r=1是A的成真赋值,p=0,q=1,r=0是A的成假赋值.32重言式,矛盾式与可满足式重言式(永真式):无成假赋值的命题公式 矛盾式(永假式):无成真赋值的命题公式 可满足式:不是矛盾式的命题公式 例如, A= (pq)(rp)是可满足式, 但不是重言式,B= (pq)(pq)(pq)(pq)是重言式,C= p(pq)(pq)是矛盾式.AB:蕴涵式AB是重言式的简记. AB:等价式AB是重言式的简记，称A与B等值，AB是等值式. 33基本等值式（16组）双重否定律 AA 幂等律 AAA, AA
