逻辑符号集合及其运算

《逻辑符号集合及其运算》由会员分享，可在线阅读，更多相关《逻辑符号集合及其运算（62页珍藏版）》请在金锄头文库上搜索。

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是重言式的简记. 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(A