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

1、1.离散数学，讲师：南昌大学信息工程学院计算机科学系，李，2010年9月，教材：离散数学(第二版)，瞿万玲、耿素云、主编，清华大学出版社，教学参考书离散数学习题的解法与学习指导(第二版)，瞿万玲、耿素云、主编，清华大学出版社，2008年2月，教材和教学参考书。它是计算机科学基础理论的核心课程，为计算机科学提供了强有力的理论基础和工具。离散数学的基本思想、概念和方法已经渗透到计算机科学和技术发展的各个领域，其基本理论和研究成果全面系统地影响和促进了其发展。离散数学的内容非常丰富，最重要和最核心的是：数理逻辑、集合论、图论、组合计数理论和代数系统。本课程将着重于这五个部分的相关知识。数理逻辑：它是

2、一门用数学方法研究推理的形式结构和规则的数学学科，与数学的其他分支、计算机科学、人工智能、语言学等学科密切相关。命题逻辑和一阶谓词逻辑是数理逻辑中最成熟的部分，在计算机科学中应用广泛。命题逻辑是数理逻辑最基本的部分，谓词逻辑是在此基础上发展起来的。本课程在第二章和第三章介绍数理逻辑中的命题逻辑和一阶谓词逻辑。著名的物理学家阿尔伯特爱因斯坦曾经问过这样一个问题：一个土耳其商人想找一个非常聪明的助手帮他做生意，于是有两个人来应聘。为了试一试哪个更聪明，商人带着两个人进了一个黑暗的房间。打开电灯后，他说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的。现在，我关掉灯，把帽子的位置搞乱了。然后我们

3、三个每人摸一顶帽子，戴在他的头上。我开灯后，请尽快告诉我你头上的帽子是什么颜色。”之后，商人关上灯，然后三个人都摸了一顶帽子，把它戴在头上。同时，商人把剩下的两顶帽子藏了起来，然后打开了灯。这时，两位候选人看到这位商人戴着一顶红帽子。过了一会儿，其中一个喊道：“我戴着一顶黑帽子。”这个人对吗？这是怎么推断出来的？答案是：“合适的人戴一顶黑帽子”是真的，所以合适的人肯定地说：“我戴一顶黑帽子”。例2:理发师悖论在某个城市有一个理发师，他的广告上写着：“我的理发师很棒，在全市都很有名。”我会给这个城市里所有不刮胡子的人刮胡子，我只刮这些人。我要向你们所有人表示热烈的欢迎！”有很多人来找他刮胡子，自

4、然他们都是不刮胡子的人。然而，有一天，当理发师在镜子里看到他的胡子长出来时，他本能地抓起了剃刀。你认为他会刮胡子吗？如果他不刮胡子，他属于“不刮胡子的人”，他会刮胡子，但是如果他刮胡子呢？他属于“刮胡子的人”，所以他不应该刮胡子。这类似于著名数学家伯特兰罗素(1872-1970)提出的罗素悖论问题：所有集合都分为两类。第一组把自己当作一个元素，而第二组不把自己当作一个元素。如果第一套是P，第二套是Q，那么P=AAA，Q=AAA，Q，QP还是QQ？图论是数学的一个古老分支，起源于对游戏难题的研究。图论内容丰富，应用广泛。许多学科，如运筹学、信息论、控制论、网络理论、博弈论、化学、生物学、物理学、

5、社会科学、语言学、计算机科学等。都把它作为解决实际和理论问题的工具。随着计算机科学的发展，图论在上述学科中发挥着越来越重要的作用，图论本身也得到充分的发展。本课程在第6章和第7章介绍了与计算机科学密切相关的图论内容。现代图论的历史可以追溯到18世纪的七桥问题，它要求每座桥只经过一次。1736年，欧拉证明这样的路线不可能存在。例3:柯尼斯堡的七座桥，欧拉定理，如果一对于任何非空连通图，如果它是欧拉的，当且仅当它没有奇数点。对应于Knigsberg桥的图，组合计数理论：它是一个研究离散结构的存在、计数、分析和优化的数学分支。20世纪60年代以来，随着计算机的诞生，组合计数理论发展迅速，“为上个世纪

6、的计算机革命奠定了基础”。计算机之所以被称为计算机，是因为计算机已经被编程，而程序就是算法。对算法运行效率和存储需求的分析需要大量的组合计数思想，这让人们觉得计算机似乎有思维。在本课程的第8、9和13章中，介绍了组合计数的基础、包含和排除的原理、递归方程和组合计数理论中的母函数。中国古代的河洛图(魔方)问题，据说在公元前23世纪，当大禹治水的时候，一只中国乌龟出现在黄河的一条支流洛水。人们数了数图案中的花点，惊奇地发现这九个花点恰好是19的九个数字，而且每个数字位置的排列都很奇妙，三个横排，三个纵列，它们各自的数字之和在两条对角线上。上图显示的是三阶罗数。例3:魔方。组合数学中有许多像幻方这样

7、精致的结构。1977年，美国航海家1号和2号宇宙飞船携带魔术方块作为人类智慧的信号。上图显示了一份用希腊语写在羊皮纸上的阿基米德手稿。最近，科学家们借助现代科学技术初步破译了古希腊数学家阿基米德的这篇论文。结论是这篇名为胃的论文解决了组合数学的问题。例子4:平铺(阿基米德手稿)在这篇论文中，阿基米德正在计算把14个不规则的纸带拼成一个正方形可以拼出多少种不同的拼法。现在被称为平铺问题，数学家在计算机的帮助下得到了17152个拼写，这在当时是相当困难的。周期镶嵌，非周期镶嵌，彭罗斯镶嵌，对称镶嵌，对称镶嵌，图案：排列任何一个，最小的元素被替换，下一个最小的元素被替换，等等。这样获得的排列被称为模

8、式。例如，914的模式是：312 37925是：24513。示例5:堆栈排序问题(Knuth，60年代)，堆栈排序问题(Knuth，60年代)，避免排列：当且仅当任何子序列中没有模式时，才避免排列。例如，132564是避免312的排列，146235是包含312的排列。堆栈排序问题(Knuth，60年代)，8，7，6，5，4，3，2，1，避免了312。代数系统：这部分属于现代代数范畴。代数结构理论可以用来分析计算机算法的复杂性，研究抽象数据结构的性质和运算，也是编程语言的理论基础。本课程教材的第11-14章介绍了代数系统。20世纪20年代，由卡瑞提提出。1950年，普尔和科赫恩提出了这样一个问题

9、：“两个不相关的人需要经历多少人才能相互了解？”哈佛大学的社会心理学家斯米尔格拉姆在1967年做了一个有趣的实验。据说，他从内布拉斯加州的奥马哈随机挑选了300人，然后要求他们每个人试着给波士顿的一个证券推销员发一封信。寄信的规则很简单，也就是说，任何收信人只能给自己熟悉的人寄信。例5:无标度网络问题，相关重要结论，“六度分离”对于每个人来说，平均只需要通过个人向目的地发送信件。研究无标度网络及其结构对于防范黑客攻击、预防流行病和开发新药具有重要意义。1999年，巴拉巴斯等人发现，互联网上任何两个网页之间最多有19个链接。(自然401，1999)，无标度网络的一个例子。互联网是一个无标度网络。

10、左图中的星暴结构描绘了从一个测试站点到大约100，000个其他站点的最短连接路径。图中相似的站点用相同的颜色表示。第1章数学语言与证明方法，本章的主要内容，1.1常用数学符号集合符号，运算符号，逻辑符号1.2集合及其运算1.3证明方法概述，25，1.1逻辑符号，26，关键知识点：命题与真值连词(，)命题公式(重言式，矛盾式，可满足性)重要等价性，重要推理规则个体，个体域与谓词全量词与存在量词，命题与真值，命题3360有一个陈述句，决定了要表达的真值通常是p、q、r等。用来表达命题的真值(即命题符号化)。命题3360所表达的判断只有两个结果：对与错，这个结果被称为命题的真值。这个命题是正确的，这

11、个命题的真正价值叫做真；命题是错的，而这个命题的真正价值被称为假的。在数理逻辑中，命题真值的真与假有时用1和0表示，有时分别用T(真)和F(假)表示。真命题：真命题：假命题：真命题假命题，例如，p:2 2=4，q:3是偶数，它们都是命题，p是真命题，q是假命题。27，连词，否定连词的否定p:不是p (p的否定p) p为真当且仅当p为假连词pq3360p和q (p和q) pq为真当且仅当p和Q都为真析取连词pq3360p或pq为假当且仅当p和Q都为假，28，连词(续)，29，排除或连词排除或p q: p而不是Q， 或者当且仅当P和Q中的一个为真，另一个为假时，Q和非p p q为真。如果P，那么q

12、 pq为假当且仅当P为真，Q为假时，当且仅当q pq为真且仅当P和Q都为真或假，例如，设p:2为偶数，q:1 1=3， 那么30，p的真值是1，q的真值是，q的真值是，pq的真值是，pq的真值是，pq的真值是。 1，0，0，1，pq的真值是，0，0，示例(续)，pq的真值是，31，pq的真值是，pq的真值是，0，1，1，让t:是今天星期一，s3330。命题变量：是一个参数，它的值是0或1，也用p，q，r等表示。命题公式：使用连接符和括号按照一定的规则连接命题和命题变量，这些规则通常用A、B、C等表示。例如，公式：的赋值给公式中的每个命题变量一个值(0或1)。公式：的真正赋值使公式成为真。公式：

13、的错误赋值使公式为假。例如，p=1，q=1，r=1是a的真赋值，p=0重复(从不为真):命题公式无假赋值矛盾(从不为假):命题公式无真赋值可以满足公式：命题公式不矛盾。例如，A=(pq)(rp)是可满足的但不是同义反复，B=(pq)(pq)(pq)(pq)(C=p(pq)(pq)是矛盾的。AB:的含义是同义反复的简写。AB:的等价AB是同义反复的简写，说a和b是等价的，AB是等价的。33，基本等价(16组)，双重否定定律AA幂等定律AAA，AAA交换定律ABBA，ABBA关联定律CA(AB)BC(AB)CA(BC)分布定律A(BC)AB(AC)A(BC)AB(AC)De mor gan定律AB

14、(AB)AB(AB)AB，34，基本等价(续)，吸收定律A (AB) A1A排除中间定律AA1矛盾定律AA0蕴涵等价AB等价AB(AB)(BA)假设移位等价AB A等价负等价AB AB还原佯谬附加定律A (AB)简化定律a (AB)假设推理a (ab)排斥公式B(AB)析取三段论B(AB)假设三段论(AB)(BC) (AC)等价三段论(AB)(BC) (AC)构造困境(ab) (CD) (AC) 36，谓词和量词，个体域：所有研究对象，如自然数集，人类等。 单个单词：是单个域中的一个元素。全称量词3360的意思是任意的，所有的，所有的，等等。存在量词3360意味着存在，一些，至少一个，等等。谓

15、词：指示单个单词或彼此相关的单词的性质，例如，谓词P(x)指示x具有属性PP(x)指示单个域中的所有x都具有属性PP(x)指示x存在于具有属性P的单个域中，37，1.2集合及其操作。关键知识点：集合及其表示包括(子集)和相等的空集合，完备集合运算(，-，)。基本集恒等式的证明方法包括和等式，38，朴素集合论：德国数学家康托创立的第一个集合论。在朴素集合论中，集合是一个自我证明的概念，如由一堆对象组成的整体。罗素悖论：所有的收藏都分为两类。第一类把自己当作一个元素，而第二类不把自己当作一个元素。如果第一类由P组成，第二类由Q组成，那么P=AAA，Q=AAA，Q，QP还是QQ？这就是著名的“罗素悖论”，而著名的“巴伯悖论”就是它的通俗表达。公理集合论(数理逻辑范畴)是公理数学的一个严格分支，由德国数学家策梅洛在发现朴素集