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

1
离散数学
主讲教师:李向军
南昌大学信息工程学院计算机系
2010年9月
教材:
离散数学(第2版)
屈婉玲、耿素云、张立昂主编
清华大学出版社,
教学参考书:
离散数学****题解答与学****指导(第2版)
屈婉玲、耿素云、张立昂主编
清华大学出版社,
教材与教学参考书
离散数学是现代数学的一个重要分支。是计算机科学中基础理论的核心课程,为计算机科学提供了有力的理论基础和工具。离散数学的基本思想、概念和方法广泛地渗透到计算机科学与技术发展的各个领域,而且其基本理论和研究成果更是全面而系统地影响和推动着其发展。
离散数学的内容十分丰富,最重要,最核心的是:数理逻辑、集合论、图论、组合计数理论和代数系统。
本课程将围绕这五个部分相关知识展开介绍。
数理逻辑:是用数学方法来研究推理的形式结构和推理规律的数学学科,它与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切的联系。命题逻辑和一阶谓词逻辑是数理逻辑中最成熟的部分,在计算机科学中应用最为广泛,其中命题逻辑是数理逻辑的最基础部分,谓词逻辑是在它的基础上发展起来的。
本课程在第二,三两章中介绍数理逻辑中的命题逻辑和一阶谓词逻辑的内容。
实例一:聪明助手问题
著名物理学家爱因斯坦出过如下一道题:
一个土耳其商人,想找一个十分聪明的助手协助他经商,有两个人前来应聘。这个商人为了试一试哪一个聪明些,就把两个人带进一间漆黑的屋子里,他打开电灯后说:“这张桌子上有五顶帽子,两顶是红色的,三顶是黑色的。现在,我把灯关掉,而且把帽子摆的位置弄乱,然后我们三个人每人摸一顶帽子戴在头上,在我开灯后,请你们尽快地说出自己头上戴的帽子是什么颜色的。”说完之后,商人将电灯关掉,然后三人都摸了一顶帽子戴在头上,同时商人将余下的两顶帽子藏了起来接着把电灯打开,这时那两个应试者看到商人头上戴的是一顶红帽子,过了一会儿,其中一个人便喊到:“我戴的是黑帽子。”
请问这个人猜得对吗?是怎么推导出来的?
答案:“猜对的人戴着黑帽子”是真的,所以猜对的人肯定的说:“我戴的是黑帽子”。
现代数学中,每个对象(如数,函数等)本质上都是集合,都可以用某种集合来定义,数学的各个分支,本质上都是在研究某一种对象集合的性质。集合论的特点是研究对象的广泛性,它也是计算机科学与工程的基础理论和表达工具,而且在程序设计,数据结构,形式语言,关系数据库,操作系统等都有重要应用。
本课程在第四,五章中介绍集合论中的关系和函数部分的内容。
集合论:是研究集合一般性质的数学分支,它的
创始人是康托尔(
,1845-1918)。在
实例二:理发师悖论(Paradox)
在某个城市中有一位理发师,他的广告词是这样写的:“本人的理发技艺十分高超,誉满全城。我将为本城所有不给自己刮脸的人刮脸,我也只给这些人刮脸。我对各位表示热诚欢迎!”来找他刮脸的人络绎不绝,自然都是那些不给自己刮脸的人。可是,有一天,这位理发师从镜子里看见自己的胡子长了,他本能地抓起了剃刀,你们看他能不能给他自己刮脸呢?如果他不给自己刮脸,他就属于“不给自己刮脸的人”,他就要给自己刮脸,而如果他给自己刮脸呢?他又属于“给自己刮脸的人”,他就不该给自己刮脸。
这与由著名数学家伯特兰·罗素(Russel,1872—1970)提出的罗素悖论问题相似:
把所有集合分为2类,第一类中的集合以其自身为元素,第二类中的集合不以自身为元素,假令第一类集合所组成的集合为P,第二类所组成的集合为Q,于是有P={A∣A∈A},Q={A∣AA},问,Q∈P 还是 Q∈Q?
图论:是一个古老的数学分支,它起源于游戏难题的研究。图论的内容十分丰富,应用得相当广泛,许多学科,诸如运筹学、信息论、控制论、网络理论、博弈论、化学、生物学、物理学、社会科学、语言学、计算机科学等,都以图作为工具来解决实际问题和理论问题。随着计算机科学的发展,图论在以上各学科中的作用越来越大,同时图论本身也得到了充分的发展。
本课程在第六,七两章中介绍与计算机科学关系密切的图论的内容。
近代图论的历史可追溯到18世纪的七桥问题—穿过Königsberg城的七座桥,要求每座桥通过一次且仅通过一次。
Euler1736年证明了不可能存在这样的路线。
实例三:哥尼斯堡七桥问题
Euler 定理
如果一个图包含一条经过每条边恰好一次的闭途径,则称这个图为欧拉图。
对任意的非空连通图,若它是欧拉的, 当且仅当它没有奇度点。
Königsberg桥对应的图