逻辑符号集合及其运算.ppt

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

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

3、带进一间漆黑的屋子里，他打开电灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的。现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在头上，在我开灯后，请你们尽快地说出自己头上戴的帽子是什么颜色的。”说完之后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来接着把电灯打开，这时那两个应试者看到商人头上戴的是一顶红帽子，过了一会儿，其中一个人便喊到：“我戴的是黑帽子。” 请问这个人猜得对吗？是怎么推导出来的？,答案：“猜对的人戴着黑帽子”是真的，所以猜对的人肯定的说：“我戴的是黑帽子”。,实例二：理发师悖论（Paradox）,在某个城

4、市中有一位理发师，他的广告词是这样写的：“本人的理发技艺十分高超，誉满全城。我将为本城所有不给自己刮脸的人刮脸，我也只给这些人刮脸。我对各位表示热诚欢迎！”来找他刮脸的人络绎不绝，自然都是那些不给自己刮脸的人。可是，有一天，这位理发师从镜子里看见自己的胡子长了，他本能地抓起了剃刀，你们看他能不能给他自己刮脸呢？如果他不给自己刮脸，他就属于“不给自己刮脸的人”，他就要给自己刮脸，而如果他给自己刮脸呢？他又属于“给自己刮脸的人”，他就不该给自己刮脸。 这与由著名数学家伯特兰罗素（Russel，18721970）提出的罗素悖论问题相似： 把所有集合分为2类，第一类中的集合以其自身为元素，第二类中的集

5、合不以自身为元素，假令第一类集合所组成的集合为P，第二类所组成的集合为Q，于是有P=AAA，Q=AAA，问，QP 还是 QQ？,图论：是一个古老的数学分支，它起源于游戏难题的研究。图论的内容十分丰富，应用得相当广泛，许多学科，诸如运筹学、信息论、控制论、网络理论、博弈论、化学、生物学、物理学、社会科学、语言学、计算机科学等，都以图作为工具来解决实际问题和理论问题。随着计算机科学的发展，图论在以上各学科中的作用越来越大，同时图论本身也得到了充分的发展。 本课程在第六，七两章中介绍与计算机科学关系密切的图论的内容。,近代图论的历史可追溯到18世纪的七桥问题穿过Knigsberg城的七座桥，要求每座

6、桥通过一次且仅通过一次。 Euler1736年证明了不可能存在这样的路线。,实例三：哥尼斯堡七桥问题,Euler 定理,如果一个图包含一条经过每条边恰好一次的闭途径，则称这个图为欧拉图。 对任意的非空连通图，若它是欧拉的, 当且仅当它没有奇度点。,Knigsberg桥对应的图,组合计数理论：是一个研究离散结构的存在、计数、分析和优化等问题的数学分支。上世纪60年代以来，随着计算机的诞生，组合计数理论得到了迅速发展， “为上世纪计算机革命奠定了基础”，计算机之所以被称之为电脑，就是因为计算机被人编写了程序，而程序就是算法。算法运行效率和存储需求分析需要大量的组合计数思想，正是因为有了组合算法，才

7、使人感到计算机好像是有思维的。 本课程在第八，九和十三章中介绍组合计数理论中的组合计数基础、容斥原理和递推方程与生成函数等内容。,我国古代的河洛图(幻方)问题,传说在公元前23世纪大禹治水的时候，在黄河支流洛水中，浮现出一个 大乌龟，甲上背有9种花点的图案，人们将图案中的花点数了一下，竞惊奇地发现9种花点数正巧是19这9个数，各数位置的排列也相当奇妙，横的3行、纵的3列以及两对角线上各自的数字之和都为15。,上图为三阶洛书,实例三：幻方问题,组合数学中有许多象幻方这样精巧的结构。 1977年美国旅行者1号、2号宇宙飞船就带上了幻方以作为人类智慧的信号。, 阶 幻 方,阿基米德手稿,上图为一份用

8、希腊文写在羊皮纸上的阿基米德手稿副本, 最近科学家借助现代科技手段初步破译了古希腊数学家阿基米德的这篇论文, 结论是这篇被称作Stomachion的论文解决的是组合数学问题。,实例四：Tiling（阿基米德手稿）问题,在论文中阿基米德是在计算把14条不规则的纸带拼成正方形一共能有多少种不同的拼法？ 现在称为Tiling问题,当今数学家借助计算机得出的答案是17152种拼法，这在当时是相当困难的。,Periodic Tilings,Non-Periodic Tilings,Penrose Tilings,Symmetric Tilings,Symmetric Tilings,模式: 对任意一个排

9、列 , 最小的元素用代替，次小的元素用代替以此类推，这样得到的排列叫的模式。 例如 914的模式为：312 37925 的模式为： 24513,实例五：栈排序问题(Knuth, 1960s),栈排序问题(Knuth, 1960s),避免排列：一个排列是避免的，当且仅当它的任意子序列中没有模式。 例如 132564是避免 312的排列 146235是包含312的排列,栈排序问题(Knuth, 1960s),8,7,6,5,4,3,2,1,避免312排列,代数系统：这部分内容属于近世代数的范畴，近世代数是研究具有运算的集合，它第一次揭示了数学系统的多变性与丰富性。代数结构理论可用于计算机算法的复杂

10、性分析，研究抽象数据结构的性质及操作，同时也是程序设计语言的理论基础。 本课程教材在第十一至十四章中介绍代数系统有关内容。,20世纪20年代，由Karinthy提出。 1950年， Pool 和 Kochen提出这样一个问题：“两个毫无关系的人，要让他们互相认识，至少要经过多少人？” 美国哈佛大学社会心理学家S. Milgram在1967年做过一项有趣的实验，据说他从内布拉斯加州的奥马哈随机选了300人，然后请他们每个人尝试寄一封信到波士顿的一位证券业务员。寄信的规则很简单，就是任何收信者只能把信寄给自己熟识的人。,实例五：无尺度网络问题,相关重要结论,“6度分离” 对每个人来说，平均大约只需

11、要通过个人就能将信寄到目的地。 研究无尺度网络及其结构，对于防备黑客攻击、防治流行病、和开发新药等，都具有重要的意义。 在1999年，Barabasi et al.发现在因特网上，任意两个网页间的链接最多为19次。(Nature 401, 1999),无尺度网络的一个例子,因特网是一个无尺度网络，左图的星爆形结构描绘了从某一测试站点到其他约十万个站点的最短连结路径。图中以相同的颜色来表示相类似的站点。,第1章 数学语言与证明方法,本章主要内容,1.1 常用数学符号 集合符号、运算符号、逻辑符号 1.2 集合及其运算 1.3 证明方法概述,25,1.1 逻辑符号,26,关键知识点： 命题与真值

12、联结词(, ,) 命题公式(重言式,矛盾式,可满足式) 重要等值式 重要推理规则 个体,个体域与谓词 全称量词与存在量词,命题与真值,命题:具有确定真值的表达判断的陈述句, 通常用p,q,r等表示（即命题符号化） 命题的真值:作为命题所表达的判断只有两个结果：正确和错误，此结果称为命题的真值。 命题是正确的，称此命题的真值为真；命题是错误的，称此命题的真值为假。 在数理逻辑中，命题的真值的真和假，有时分别用1和0来表达，也有时分别用T(True)和F(False)来表达。（即真值的符号化） 真命题:真值为真的命题 假命题:真值为假的命题 例如, p:2+2=4, q:3是偶数 它们都是命题,

13、p是真命题, q是假命题.,27,联结词,否定联结词 否定式p: 非p (p的否定) p 为真当且仅当p为假 合取联结词 合取式pq:p并且q (p与q) pq为真当且仅当p与q同时为真 析取联结词 析取式pq: p或q pq为假当且仅当p与q同时为假,28,联结词(续),29,排斥或联结词 排斥或p q: p并且非q, 或者q并且非p p q为真当且仅当p与q中一个为真,另一个为假 蕴涵联结词 蕴涵式pq:如果p,则q pq为假当且仅当 p 为真 q 为假 等价联结词 等价式pq:p当且仅当q pq为真当且仅当p与q同时为真或同时为假,实例,设p:2是偶数, q:1+1=3, 则,30,p的

14、真值为,1,q的真值为,p的真值为,q的真值为,pq的真值为,pq的真值为,pq的真值为, pq的真值为,pq的真值为,pq的真值为,p q的真值为,p q的真值为,p q的真值为,p q的真值为,0,0,1,0,1,1,0,1,1,1,0,0,1,pq的真值为,pq的真值为,0,0,实例(续),pq的真值为,31,pq的真值为,pq的真值为,pq的真值为,0,1,1,1,又设 r:今天是星期一, s:明天是星期二, t:明天是星期三,rs的真值为,rt的真值为,1,不定,命题公式,命题变项:取值为0或1的变元, 也用p,q,r等表示. 命题公式:用联结词和圆括号把命题和命题变项按照一定 规则

15、连接起来的符号串, 常用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是

16、重言式的简记. AB:等价式AB是重言式的简记， 称A与B等值，AB是等值式.,33,基本等值式（16组）,双重否定律 AA 幂等律 AAA, AAA 交换律 ABBA, ABBA 结合律 (AB)CA(BC) (AB)CA(BC) 分配律 A(BC)(AB)(AC) A(BC) (AB)(AC) 德摩根律 (AB)AB (AB)AB,34,基本等值式(续),吸收律 A(AB)A, A(AB)A 零律 A11, A00 同一律 A0A, A1A 排中律 AA1 矛盾律 AA0 蕴涵等值式 AB AB 等价等值式 AB(AB)(BA) 假言易位等值式 AB B A 等价否定等值式 AB A B

17、归谬论 (AB)(AB) A,35,重要推理规则(推理定律，9组),附加律 A (AB) 化简律 (AB) A 假言推理 (AB)A B 拒取式 (AB)B A 析取三段论 (AB)B A 假言三段论 (AB)(BC) (AC) 等价三段论 (AB)(BC) (AC) 构造性二难 (AB)(CD)(AC) (BD) 破坏性二难 (AB)(CD)( BD) (AC),36,谓词与量词,个体域:被研究对象的全体, 如自然数集, 人类等. 个体词:个体域中的一个元素. 全称量词: 表示任意的, 所有的, 一切的等. 存在量词: 表示存在, 有的, 至少有一个等. 谓词: 表示个体词性质或相互之间关系

18、的词 例如, 谓词P(x)表示x具有性质P x P(x) 表示个体域中所有的x具有性质P x P(x) 表示个体域中存在x具有性质P,37,1.2 集合及其运算,关键知识点： 集合及其表示法 包含(子集)与相等 空集与全集 集合运算(, - , , ) 基本集合恒等式 包含与相等的证明方法,38,集合的概念,朴素集合论(Naive Set Theory)：德国数学家康托尔(G.Cantor)最早创立的第一个集合论。在朴素集合论中，集合是被当做一堆物件构成的整体之类的自证概念。 罗素(Russell)悖论（Paradox）：把所有集合分为2类，第一类中的集合以其自身为元素，第二类中的集合不以自身

19、为元素，假令第一类集合所组成的集合为P，第二类所组成的集合为Q，于是有P=AAA，Q=AAA，问，QP 还是 QQ？这就是著名的“罗素悖论”，著名的“理发师悖论”即为其一种通俗表达方式。 公理集合论（数理逻辑范畴）：是一个严谨的公理化数学分支，是因为发现了朴素集合论中的一些严重缺陷（如罗素悖论）后由德国数学家策梅罗（ Zermelo ）提出并发展起来的。在公理化集合论中，集合和集合成员并不直接被定义，而是先规范可以描述其性质的一些公理，目的是消除悖论。,39,集合的概念（续）,集合是数学中最基本的概念,没有严格的定义 理解成某些个体组成的整体, 常用A,B,C等表示 元素:集合中的个体 xA(

20、x属于A): x是A的元素 xA(x不属于A): x不是A的元素 无穷集:元素个数无限的集合 有穷集(有限集):元素个数有限的集合. |A|:A中元素个数 k元集:k个元素的集合, k 0,40,集合的表示法,列举法 如 A= a, b, c, d , N=0,1,2, 描述法 x | P(x) 如N= x | x是自然数 说明: (1) 集合中的元素各不相同. 如, 1,2,3=1,1,2,3 (2) 集合中的元素没有次序. 如, 1,2,3=3,1,2=1,3,1,2,2 (3) 有时两种方法都适用, 可根据需要选用. 常用集合 自然数集N, 整数集Z, 正整数集Z+, 有理数集Q, 非零

21、有理数集Q*, 实数集R, 非零实数集R*, 复数集C, 区间a,b,(a,b)等,41,包含与相等,包含(子集) A B x (xA xB) 不包含 A B x (xA xB) 相等 A = B A B B A 不相等 A B A B B A 真包含(真子集) A B A B A B 例如, A=1,2,3, B= x | xR|x|1 , C= x | xRx2=1 , D=-1,1, C B, C B, C A, A B, B A, C = D 性质 (1) A A (2) A B B C A C,42,空集与全集,空集: 不含任何元素的集合 例如, x | x20 xR= 定理1.1

22、空集是任何集合的子集 证 用归谬法. 假设不然, 则存在集合A, 使得 A, 即存在x, x且xA, 矛盾. 推论 空集是惟一的. 证 假设存在1和2，则12 且12，因此1=2 全集E:限定所讨论的集合都是E的子集. 相对性,43,幂集,幂集P(A):A的所有子集组成的集合, 即 P(A) = x | xA 例如, 设A=a,b,c A的0元子集: A的1元子集: a, b, c A的2元子集:a,b,a,c,b,c A的3元子集: a,b,c P(A) =, a, b, c, a,b. a,c, b,c, a,b,c,44,定理1.2 如果 |A| = n，则 |P(A)| = 2n 证,

23、集合运算,并 AB = x | xA xB 交 AB = x | xA xB 相对补 AB = x | xA xB 对称差 AB = (AB)(BA) = (AB)(AB) 绝对补 A = EA= x | xA 例如 设E=0,1, ,9, A=0,1,2,3, B=1,3,5,7,9, 则 AB =0,1,2,3,5,7,9, AB =1,3, AB =0,2, AB =0,2,5,7,9, A =4,5,6,7,8,9, B =0,2,4,6,8 说明:1. 只使用圆括号 2. 运算顺序: 优先级别为(1)括号, (2)和幂集, (3)其他. 同级别的按从左到右运算,45,实例,例1 设E

24、= x | x是北京某大学学生, A,B,C,D是E的子集, A= x | x是北京人, B= x | x是走读生, C= x | x是数学系学生, D= x | x是喜欢听音乐的学生. 试描述下列各集合中学生的特征:,46,(AD) C=, AB=,(A-B) D=, D B=, x | x是北京人或喜欢听音乐, 但不是数学系学生, x | x是外地走读生, x | x是北京住校生, 并且喜欢听音乐, x | x是不喜欢听音乐的住校生,文氏图表示,47,集合运算(续),48,并和交运算可以推广到有穷个集合上 A1A2An= x | xA1xA2xAn A1A2An= x | xA1xA2xA

25、n 并和交运算还可以推广到可数无穷个集合上 A1A2= x | i (i=1,2,) xAi A1A2= x | i (i=1,2,) xAi ,实例,例2 设Ai=0, 1/i ), Bi=(0, i ), i=1,2, , 则,49,0, 1),0, 1),0, 1/n ), 0 ,(0, n),(0, +),(0, 1),(0, 1),基本集合恒等式,1. 幂等律AA=A, AA=A 2. 交换律AB=BA, AB=BA 3. 结合律(AB)C=A(BC) (AB)C=A(BC) 4. 分配律A(BC)=(AB)(AC) A(BC)=(AB)(AC) 5. 德摩根律 绝对形式(BC)=B

26、C, (BC)=BC 相对形式 A(BC)=(AB)(AC) A(BC)=(AB)(AC),50,基本集合恒等式(续),6. 吸收律 A(AB)=A, A(AB)=A 7. 零律 AE=E, A= 8. 同一律 A=A,AE=A 9. 排中律 AA=E 10. 矛盾律 AA= 11. 余补律 =E, E= 12. 双重否定律 A=A 13. 补交转换律 A-B= AB,51,基本集合恒等式(续),14. 关于对称差的恒等式 (1) 交换律 AB=BA (2) 结合律 (AB)C=A(BC) (3) 对的分配律 A(BC)=(AB)(AC) (4) A=A, AE= A (5) AA=, A A

27、= E,52,注意: 对没有分配律, 反例如下 A=a,b,c, B=b,c,d, C=c,d,e A(BC)= a,b,cb,e= a,b,c,e (AB)(AC)= a,b,c,da,b,c,d,e= e, 两者不等,证明集合包含或相等,方法一. 根据定义, 通过逻辑等值演算证明 方法二. 利用已知集合等式或包含式, 通过集合演算证明 例3 证明: (1) AB=BA (交换律) 证 x xAB xAxB (并的定义) xBxA (逻辑演算的交换律) xBA (并的定义),53,例3(续),(2) A(BC)=(AB)(AC) (分配律) 证 x xA(BC) xA(xB xC) (并,交的定义) (xAxB)(xAxC) (逻辑演算的分配律) x(AB)(AC) (并,交的定义) (3) AE=E (零律) 证 x xAE xAxE (并的定义) xA1 (全集E的定义) 1 (逻辑演算的零律) xE