逻辑符号集合及其运算

《逻辑符号集合及其运算》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1离散数学主讲教师：李向军南昌大学信息工程学院计算机系2010年9月教材：离散数学（第2版）屈婉玲、耿素云、张立昂主编清华大学出版社,2008.2教学参考书：离散数学习题解答与学习指导（第2版）屈婉玲、耿素云、张立昂主编清华大学出版社，2008.2教材与教学参考书离散数学是现代数学的一个重要分支。是计算机科学中基础理论的核心课程，为计算机科学提供了有力的理论基础和工具。离散数学的基本思想、概念和方法广泛地渗透到计算机科学与技术发展的各个领域，而且其基本理论和研究成果更是全面而系统地影响和推动着其发展。离散数学的内容十分丰富，最重要，最核心的是：数理逻辑、集合论、图论、组合计数理论

2、和代数系统。本课程将围绕这五个部分相关知识展开介绍。数理逻辑：是用数学方法来研究推理的形式结构和推理规律的数学学科，它与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切的联系。命题逻辑和一阶谓词逻辑是数理逻辑中最成熟的部分，在计算机科学中应用最为广泛，其中命题逻辑是数理逻辑的最基础部分，谓词逻辑是在它的基础上发展起来的。本课程在第二，三两章中介绍数理逻辑中的命题逻辑和一阶谓词逻辑的内容。实例一：聪明助手问题著名物理学家爱因斯坦出过如下一道题：一个土耳其商人，想找一个十分聪明的助手协助他经商，有两个人前来应聘。这个商人为了试一试哪一个聪明些，就把两个人带进一间漆黑的屋子里

3、，他打开电灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的。现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在头上，在我开灯后，请你们尽快地说出自己头上戴的帽子是什么颜色的。”说完之后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来接着把电灯打开，这时那两个应试者看到商人头上戴的是一顶红帽子，过了一会儿，其中一个人便喊到：“我戴的是黑帽子。”请问这个人猜得对吗？是怎么推导出来的？答案：“猜对的人戴着黑帽子”是真的，所以猜对的人肯定的说：“我戴的是黑帽子”。现代数学中，每个对象(如数，函数等)本质上都是集合，都可以

4、用某种集合来定义，数学的各个分支，本质上都是在研究某一种对象集合的性质。集合论的特点是研究对象的广泛性，它也是计算机科学与工程的基础理论和表达工具，而且在程序设计，数据结构，形式语言，关系数据库，操作系统等都有重要应用。本课程在第四，五章中介绍集合论中的关系和函数部分的内容。集合论：是研究集合一般性质的数学分支，它的创始人是康托尔(，1845－1918)。在实例二：理发师悖论（Paradox）在某个城市中有一位理发师，他的广告词是这样写的：“本人的理发技艺十分高超，誉满全城。我将为本城所有不给自己刮脸的人刮脸，我也只给这些人刮脸。我对各位表示热诚欢迎！”来找他刮脸的人络绎不绝，自

5、然都是那些不给自己刮脸的人。可是，有一天，这位理发师从镜子里看见自己的胡子长了，他本能地抓起了剃刀，你们看他能不能给他自己刮脸呢？如果他不给自己刮脸，他就属于“不给自己刮脸的人”，他就要给自己刮脸，而如果他给自己刮脸呢？他又属于“给自己刮脸的人”，他就不该给自己刮脸。这与由著名数学家伯特兰·罗素（Russel，1872—1970）提出的罗素悖论问题相似：把所有集合分为2类，第一类中的集合以其自身为元素，第二类中的集合不以自身为元素，假令第一类集合所组成的集合为P，第二类所组成的集合为Q，于是有P={A∣A∈A}，Q={A∣AA}，问，Q∈P还是Q∈Q？图论：是一个古老的数学分支

6、，它起源于游戏难题的研究。图论的内容十分丰富，应用得相当广泛，许多学科，诸如运筹学、信息论、控制论、网络理论、博弈论、化学、生物学、物理学、社会科学、语言学、计算机科学等，都以图作为工具来解决实际问题和理论问题。随着计算机科学的发展，图论在以上各学科中的作用越来越大，同时图论本身也得到了充分的发展。本课程在第六，七两章中介绍与计算机科学关系密切的图论的内容。近代图论的历史可追溯到18世纪的七桥问题—穿过Königsberg城的七座桥，要求每座桥通过一次且仅通过一次。Euler1736年证明了不可能存在这样的路线。实例三：哥尼斯堡七桥问题Euler定理如果一个图包含一条经过每条边恰

7、好一次的闭途径，则称这个图为欧拉图。对任意的非空连通图，若它是欧拉的,当且仅当它没有奇度点。Königsberg桥对应的图组合计数理论：是一个研究离散结构的存在、计数、分析和优化等问题的数学分支。上世纪60年代以来，随着计算机的诞生，组合计数理论得到了迅速发展，“为上世纪计算机革命奠定了基础”，计算机之所以被称之为电脑，就是因为计算机被人编写了程序，而程序就是算法。算法运行效率和存储需求分析需要大量的组合计数思想，正是因为有了组合算法，才使人感到计算机好像是有思维的。本课程在第八