大学离散数学第1章.ppt

离散数学,2,一、课程简介 课程名称：离散数学 英文名称：Discrete Mathematics 离散数学：离散数学是现代数学的一个重要分支，是计算机科学的核心课程。以研究离散量的结构和相互间的关系为主要目标，其研究对象是有限个或无限个元素。离散数学与计算机科学中的数据结构、操作系统、编译理论、算法分析、逻辑设计、系统结构、容错诊断、机器定理证明等课程紧密相关。是一门重要的基础课程。 教学内容：数理逻辑、集合论、图论和在计算机中的应用共四部分。其中第四部分不做考试要求，不占计划内学时。 教学要求：通过该课程的学习，培养和锻炼抽象思维和缜密概括的能力，为专业基础课和专业课的学习打下坚实的理论基础。 15周 =42学时（3学时/周）,3,二、适用对象 本课程教学教案主要针对计算机科学与技术本科专业 三、学习要领 概念（正确）：必须掌握好离散数学中大量的概念 判断（准确）：根据概念对事物的属性进行判断 推理（可靠）：根据多个判断推出一个新的判断,4,四、离散数学与计算机的关系 第一部分 数理逻辑 计算机是数理逻辑和电子学相结合的产物 第二部分 集合论 集合：一种重要的数据结构 关系：关系数据库的理论基础 函数：所有计算机语言中不可缺少的一部分 第三部分 图论 数据结构、操作系统、编译原理、计算机网络原理的基础,5,五、教材及主要参考书 教材：离散数学 （第五版） 耿素云 曲婉玲 张立昂 参考书： 1 王元元、张桂芸，离散数学导论，科学出版社，2002 2 左孝凌、李为鑑、刘永才，离散数学，上海科学技术出版社，1982年9月第1版。 3 王元元、张桂芸，计算机科学中的离散结构，机械工业出版社，2004 4 Bernard Kolman , Robert C. Busby, Sharon Ross, Discrete Mathematical Structures (Fourth Edition), 高等教育出版社，2001 5 孙吉贵 杨凤杰 欧阳丹彤 李占山，离散数学， 高等教育出版社，2002 6 马振华，离散数学导引 ，清华大学出版社，1993 7 王树禾，离散数学引论，中国科技大学出版社，2001 8 Andrew Simpon 著 冯速译 离散数学导学 机械工业出版社 2005,6,第二部分 课程内容与要求 离散数学为计算机科学与技术专业的一门重要基础理论课。它以研究离散量的结构和相互关系为主要目标。离散数学的内容十分丰富和广泛，本课程选择与计算机科学中相关的最基本最重要的数学课题进行系统的论述，为研究计算机科学提供理论基础和工具，为学习有关专业课，如数据结构、操作系统、编译原理、人工智能等，作必要的数学准备。同时，通过离散数学的学习，培养学生抽象思维和逻辑推理的能力。 课程内容对每一个从事计算机技术的人都要求掌握和了解。因为在形式证明、验证、密码学的研究与学习中要有理解形式证明的能力；图论的概念被用于计算机网络、操作系统和程序设计语言的编译系统等领域；集合论的概念、关系代数等在软件工程和数据库中也会用到。总之，为了适应计算技术的要求及将来的发展，学生需要对离散结构有比较深入的理解。 本课程教学内容注重培养学生抽象思维能力和逻辑推理的能力。在教学中把教改、教研最新的研究成果及本学科最新发展成果引入教学，不断地修改和调整教学内容，取得了良好的效果。,7,第一篇 数理逻辑 逻辑学（ logic ）：是一门研究思维形式及思维规律的科学。 数理逻辑（mathematical logic)：是用数学的方法来研究人类推理过程的一门数学学科。其显著特征是符号化和形式化，即把逻辑所涉及的“概念、判断、推理”用符号来表示，用公理体系来刻划, 并基于符号串形式的演算来描述推理过程的一般规律。 数理逻辑又称符号逻辑、现代逻辑。,8,数理逻辑简介,数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科，它与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切的联系。命题逻辑和一阶谓词逻辑是数理逻辑中最成熟的部分，在计算机科学中应用最为广泛，其中命题逻辑是数理逻辑的最基础部分，谓词逻辑是在它的基础上发展起来的。本课程在第一，二两章中介绍数理逻辑的内容。,9,数理逻辑的发展历史介绍 “数理逻辑”的名称由皮亚诺（Peano）首先给出，他又称其为符号逻辑。数理逻辑在本质上依然是亚里士多德的逻辑学，但从记号学的观点来讲，它是用抽象代数来记述的。 某些哲学倾向浓厚的数学家对用符号或代数方法来处理形式逻辑作过一些尝试，比如说莱布尼兹和朗伯（Johann Heinrich Lambert）；但他们的工作鲜为人知，后继无人。直到19世纪中叶，乔治布尔和其后的奥古斯都德摩根才提出了一种处理逻辑问题的系统性的数学方法（当然不是定量性的）。 亚里士多德以来的传统逻辑得到改革和完成，由此也得到了研究数学基本概念的合适工具。虽然这并不意味着1900年至1925年间的有关数学基础的争论已有了定论，但这“新”逻辑在很大程度上澄清了有关数学的哲学问题。,10,传统的逻辑研究较偏重于“论证的形式”，而当代数理逻辑的态度也许可以被总结为对于内容的组合研究。它同时包括“语法”（例如，从一形式语言把一个文字串传送给一编译器程序，从而转写为机器指令）和“语义”（在模型论中构造特定模型或全部模型的集合）。 数理逻辑的重要著作有哥特洛布弗雷格（Gottlob Frege）的概念文字（Begriffsschrift）、伯特兰罗素的数学原理（Principia Mathematica）等。,11,数理逻辑的主要分支包括：模型论、证明论、递归论和公理化集合论。数理逻辑和计算机科学有许多重合之处，这是因为许多计算机科学的先驱者既是数学家、又是逻辑学家，如阿兰图灵、邱奇等。 程序语言学、语义学的研究从模型论衍生而来，而程序验证中的模型检测则从模型论衍生而来。 柯里霍华德同构给出了“证明”和“程序”的等价性，这一结果与证明论有关，直觉主义逻辑和线性逻辑在此起了很大作用。演算和组合子逻辑这样的演算现在属于理想程序语言。 计算机科学在自动验证和自动寻找证明等技巧方面的成果对逻辑研究做出了贡献，比如说自动定理证明和逻辑编程。,12,用数学的方法研究逻辑的系统思想一般追溯到莱布尼茨，他认为经典的传统逻辑必须改造和发展，使之更为精确和便于演算。后人基本是沿着莱布尼茨的思想进行工作的。 简而言之，数理逻辑就是精确化、数学化的形式逻辑。它是现代计算机技术的基础。新的时代将是数学大发展的时代，而数理逻辑在其中将会起到很关键的作用。 逻辑是探索、阐述和确立有效推理原则的学科，最早由古希腊学者亚里士多德创建的。用数学的方法研究关于推理、证明等问题的学科就叫做数理逻辑。也叫做符号逻辑。,13,利用计算的方法来代替人们思维中的逻辑推理过程，这种想法早在十七世纪就有人提出过。莱布尼茨就曾经设想过能不能创造一种“通用的科学语言”，可以把推理过程象数学一样利用公式来进行计算，从而得出正确的结论。由于当时的社会条件，他的想法并没有实现。但是它的思想却是现代数理逻辑部分内容的萌芽，从这个意义上讲，莱布尼茨可以说是数理逻辑的先驱。,14,1847年，英国数学家布尔发表了逻辑的数学分析，建立了“布尔代数”，并创造一套符号系统，利用符号来表示逻辑中的各种概念。布尔建立了一系列的运算法则，利用代数的方法研究逻辑问题，初步奠定了数理逻辑的基础。 十九世纪末二十世纪初，数理逻辑有了比较大的发展，1884年，德国数学家弗雷格出版了数论的基础一书，在书中引入量词的符号，使得数理逻辑的符号系统更加完备。对建立这门学科做出贡献的，还有美国人皮尔斯，他也在著作中引入了逻辑符号。从而使现代数理逻辑最基本的理论基础逐步形成，成为一门独立的学科。,15,先看著名物理学家爱因斯坦出过的一道题： 一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴的帽子是什么颜色的。”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把灯打开。这时，那两个应试者看到商人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽子。” 请问这个人说得对吗？他是怎么推导出来的呢？ 要回答这样的问题，实际上就是看由一些诸如“商人戴的是红帽子”这样的前提能否推出“猜出答案的应试者戴的是黑帽子”这样的结论来。这又需要经历如下过程： (1) 什么是前提？有哪些前提？ (2) 结论是什么？ (3) 根据什么进行推理？ (4) 怎么进行推理？ 下面的第一章回答第一个问题。第二章回答第二、三个问题。,第一章命题逻辑,17,内容：命题，逻辑联结词，命题符号化,(1)掌握命题概念 (2)掌握联结词含义及真值表 (3)掌握命题符号化方法,重点：,第一节 命题符号化及联结词,18,一、命题的概念,命题：能判断真假的陈述句。,第一节 命题符号化及联结词,19,说明：,命题的真值：作为命题所表达的判断只有两个结果：正确和错误，此结果称为命题的真值。 命题是正确的，称此命题的真值为真； 命题是错误的，称此命题的真值为假。 真值为真的命题称为真命题 ； 真值为假的命题称为假命题。,其它类型的句子，如疑问句、祈使句、感叹句均没有真假意义，因为均不是命题。,在数理逻辑中，命题的真值的真和假，有时分别用1和0来表达，也有时分别用T和F来表达。,20,例1、判断下列句子中哪些是命题。,(1) 北京是中国的首都。,(2) 雪是黑色的。,(4) 请把门关上！,(6) 地球外的星球上也有人。,祈使句 非命题,简单命题,简单命题,简单命题,21,（7）今天是7号。,在一定条件下是真命题（如果今天是7号）。,（8）1+11=100。,在一定条件下是真命题（在二进制中）。,（9）我学英语，或者学法文。,复合命题,（10）如果天气好，我就去游泳。,复合命题,例1、判断下列句子中哪些是命题。,(11) 明天有课吗？,(12) 本语句是假的。,(13) 小明和小林都是三好生。,(14) 小明和小林是好朋友。,疑问句 非命题,悖论,复合命题,复合命题,22,例1、判断下列句子中哪些是命题。,判断一个语句是否为命题，首先看是否为陈述句，再看其真值是否唯一。,（15）我不给所有自己给自己理发的人理发， 但是却会给所有自己不给自己理发的人理发。,（14）我正在说谎。,悖论,悖论,23,数学家伯特兰罗素（Russel，18721970） 提出的悖论,在某个城市中有一位理发师，他的广告词是这样写的：“本人的理发技艺十分高超，誉满全城。我将为本城所有不给自己刮脸的人刮脸，我也只给这些人刮脸。我对各位表示热诚欢迎！”来找他刮脸的人络绎不绝，自然都是那些不给自己刮脸的人。可是，有一天，这位理发师从镜子里看见自己的胡子长了，他本能地抓起了剃刀，你们看他能不能给他自己刮脸呢？如果他不给自己刮脸，他就属于“不给自己刮脸的人”，他就要给自己刮脸，而如果他给自己刮脸呢？他又属于“给自己刮脸的人”，他就不该给自己刮脸。,24,二、逻辑联结词。,25,真值表,26,真值表,27,(1) 李平既聪明又用功。,(2)李平虽然聪明，但不用功。,(3)李平不但聪明，而且用功。,(4)李平不是不聪明，而是不用功。,28,真值表,例如，,：小明学过英语，,：小明学过日语，,则小明学过英语或日语可表示为,29,注意：相容性或与不可相容性或,相容性或：明天下雨或刮风。 不可相容性或：今天晚上去电影院看电影，或在家看电视。,30,真值表：,31,例3、一位父亲对儿子说：“如果我去书店，就一定给你买本儿童画报。”问：什么情况下父亲食言？,解：可能情况有四种：,(1) 父亲去了书店，给儿子买了儿童画报。 (2) 父亲去了书店，却没给儿子买儿童画报。 (3) 父亲没去书店，却给儿子买了儿童画报。 (4) 父亲没去书店，也没给儿子买儿童画报。,32,(1) 如果天不下雨，我就骑车上班。,(2) 只要天不下雨，我就骑车上班。,(3) 只有天不下雨，我才骑车上班。,(4) 除非天下雨，否则我就骑车上班。,(5) 如果天下雨，我就不骑车上班。,(或 ),33,例：将下列命题符号化,1) 如果1+23,则太阳从东边升起 2) 如果1+23,则太阳从东边升起 3) 如果1+23,则太阳从东边升起 4) 如果1+23,则太阳从东边升起 p:1+2=3 q:表示太阳从东边升起,34,真值表：,35,36,6、逻辑联结词与自然语言中联结词的关系。,否定不是，没有，非，不。,合取并且，同时，和，既又，不但而且，虽然但是。,析取或者，或许，可能。,蕴涵若则，假如那么，既然那就，倘若就。,等价当且仅当，充分必要，相同，一样。,37,7、运算顺序,例如：,38,三、命题符号化。,步骤：(1) 找出各简单命题，分别符号化。,(2) 找出各联结词，把简单命题逐个联结起来。,39,例6、将下列命题符号化。,(1) 小王是游泳冠军或百米赛跑冠军。,(2) 小王现在在宿舍或在图书馆。,40,(3) 选小王或小李中的一人当班长。,(4) 如果我上街，我就去书店看看，除非我很累。,例6、将下列命题符号化。,41,(5) 小丽是计算机系的学生，她生于1982或1983年， 她是三好生。,例6、将下列命题符号化。,第二节 命题公式及分类,43,内容：命题公式，重言式，矛盾式，可满足公式。,重点：(1) 掌握命题公式的定义及公式的真值表。,(2) 掌握重言式和矛盾式的定义及使用真 值表进行判断。,第二节 命题公式及分类,44,一、命题公式,通俗地说，命题公式是由命题常项，命题变项， 联结词，括号等组成的字符串。,命题常项：简单命题 命题变项：真值不确定的陈述句,45,1、合式公式 (命题公式, 公式),递归定义如下： (1) 单个命题常项或变项 p,q,r,pi ,qi ,ri ,0,1 是合式公式 (2) 若A是合式公式，则 (A)也是合式公式 (3) 若A, B是合式公式，则(AB), (AB), (AB), (AB)也是合式公式 (4) 只有有限次地应用(1)(3)形成的符号串才是合式公式 说明: 元语言与对象语言, 外层括号可以省去,46,例1、判断以下字符串中哪些是命题公式。,(1),(2),(3),(4),(5),(6),解：(1)、(2)、(6)是公式，(3)、(4)、(5)不是。,47,2、命题公式的层次。,(a) A=B, B是n层公式； (b) A=BC, 其中B,C分别为i层和j层公式，且 n=max(i, j)； (c) A=BC, 其中B,C的层次及n同(b)； (d) A=BC, 其中B,C的层次及n同(b)； (e) A=BC, 其中B,C的层次及n同(b).,(1) 若公式A是单个的命题变项, 则称A为0层公式.,(2) 称A是n+1(n0)层公式是指下面情况之一：,48,5,例如公式 p 0层 p 1层 pq 2层 (pq)r 3层 (pq) r)(rs) 4层,2、命题公式的层次。,49,3、真值表,50,3、真值表,(3) 对应每个赋值，计算各层次的值，直至整个公式。,51,例3、求下列命题公式的真值表。,(1),解：,52,例3、求下列命题公式的真值表。,(2),解：,53,二、重言式、矛盾式，可满足式。,2、判定方法:真值表法。,1、定义 设A为一个命题公式 (1) 若A无成假赋值，则称A为重言式(也称永真式) (2) 若A无成真赋值，则称A为矛盾式(也称永假式) (3) 若A不是矛盾式，则称A为可满足式,注意：重言式是可满足式，但反之不真.,54,例4、给定命题公式如下，请判断哪些是重言式，哪些是矛盾式，哪些是可满足式？,55,例4、给定命题公式如下，请判断哪些是重言式，哪些是矛盾式，哪些是可满足式？,56,解：列出各题真值表如下(步骤简略),57,58,(1)、(2)、(5)、(6)、(9)为重言式； (3)、(8)为矛盾式； (4)、(7)、(10)及以上的重言式均为可满足式。,第三节 等值演算,60,内容：等值关系，24个重要等值式，等值演算。,重点：(1) 掌握两公式等值的定义。,(2) 掌握24个重要等值式，并能利用其进行等值演算。,第三节 等值演算,61,一、两命题公式间的等值关系。,2、判定 。,62,说明：,等值与等价不是一回事 等价是命题联结词，是AB公式，在某些 指派下为真，某些指派下为假。 等值不是逻辑联结词是公式关系符，AB描述了A、B两公式之间的关系，只有“成立”，“不成立”的区别。,63,(1) ，,解：作真值表如下：,64,解：作真值表如下：,(2) ，,65,二、重要等值式。,66,二、重要等值式。,67,二、重要等值式。,10、双重否定律,68,二、重要等值式。,11、蕴涵等值式,12、等价等值式,13、假言易位,14、等价否定等值式,15、归谬论,69,三、等值演算。,由已知的等值式推演出新的等值式的过程,70,例2、验证下列等值式。,71,(1),解：,蕴涵等值式,蕴涵等值式,结合律,德摩根律,蕴涵等值式,例2、验证下列等值式。,72,(2),解：,交换律,分配律,排中律,同一律,例2、验证下列等值式。,73,(3),解：,分配律,矛盾律,同一律,德摩根律,结合律,排中律,零律,74,考虑问题:能否利用等值式来化简，或判断公式的类型(重言，矛盾，可满足)。,判断一个公式是否重言式，矛盾式，可满足式，或者判断两个命题公式是否等值。有两种方法，即真值表法和等值演算法。,75,例3、用两种方法证明:,证法一 用真值表法,由最后两列真值完全相同，于是命题成立。,76,例3、用两种方法证明:,证法二 用等值式法,蕴涵等值式,双重否定律,交换律,结合律,吸收律,第四节 联结词的全功能集,78,内容：联结词的全功能集，极小功能集。,了解：全功能集，极小功能集。,第四节 联结词的全功能集,79,真值表 ：,由定义知：,80,真值表 ：,81,真值表：,82,二、全功能集，极小功能集。,定义 在一个联结词的集合中，如果一个联结词可 由集合中的其他联结词定义，则称此联结词为冗余 的联结词，否则称为独立的联结词. 例如,在联结词集, , , , 中，由于 pqpq, 所以，为冗余的联结词; 类似地，也是冗余的 联结词. 又在, , 中，由于 pq(pq)， 所以，是冗余的联结词. 类似地，也是冗余的联 结词.,83,二、全功能集，极小功能集。,全功能集：若干个联结词的集合，其余的联结词均可由它们表示。,最小全功能集：不含冗余联结词的全功能集。,等都是极小全功能集。,第五节 对偶与范式,85,内容：对偶原理，命题公式的范式。,重点：(1) 掌握对偶式，对偶原理。,(2) 掌握析取范式和合取范式的定义和求法步骤。,(3) 掌握极小项，极大项的概念及主范式的求法。,第五节 对偶与范式,86,一、对偶原理。,1、对偶式。,与,87,2、对偶原理。,所以可得：,88,二、范式。,1、简单析取式，简单合取式。,89,2、析取范式，合取范式。,为合取范式。,90,2、析取范式，合取范式。,为析取范式。,91,2、析取范式，合取范式。,92,求范式步骤：,(2) 否定消去或内移。,(3) 利用分配律。,(1) 消去联结词,93,解：原式,消去,内移,消去,上式即析取范式,94,解：原式,消去,内移,消去,上式即合取范式,95,1.求命题公式(p(qr)(pqr)的析取范式和合取范式 . 2.求命题公式(pq)(pq) 的析取范式和合取范式,96,三、主范式。,1、极小项，极大项。,97,都是极小项，,都是极大项，,极小项,记法,极大项,记法,100,2、主析取范式，主合取范式。,两种求法，等值式法和真值表法。,定理：任何命题公式的主析取范式、主合取范式 都存在且都是唯一的。,101,步骤：,(3) 消去重复的及永假项。,102,解：由例1的析取范式为,103,解：由例1的析取范式为,104,步骤：,105,解：(1) 列真值表,106,解：(2) 的成真赋值有010，100，101，110，111,(3) 对应的十进制数为2，4，5，6，7,所以的主析取范式为,107,步骤：,(3) 消去重复的及永真项；,108,解：由例1，,合取范式,109,解：由例1，,110,2.4、利用真值表求命题公式的主合取范式。,步骤：,111,112,(3) 对应的十进制数为0，1，3。,113,由例3、例5知：,114,(2) 写出与(1)中极小项角码相同的极大项，,115,116,117,3、主范式的用途。,(1) 判断两命题公式是否等值。,(2) 判断命题公式的类型。,118,3、主范式的用途。,(2) 判断命题公式的类型。,(3) 求成真(假)赋值。,(4) 求真值表。,119,120,的成假赋值有010，011，100，101。,121,解：真值表,第六节 推理规则,123,内容：,重点：,(1) 理解推理的概念；,(2) 掌握8条推理定律；,(3) 掌握推理规则；,(4) 掌握构造证明法。,了解：,附加前提证明法和归谬法。,第六节 推理规则,124,一、推理的形式结构。,2、判断推理的方法。,等值演算法，真值表法，主析取范式法。,125,例1、判断下面各推理是否正确。,结论：,推理形式结构为：,判断此蕴涵式是否为重言式。,126,方法一 用等值式法。,所以推理正确。,方法二 用真值表法。,其真值表中最后一列全为1，,所以推理正确。,127,方法三 用主析取范式法。,主析取范式含全部最小项，所以推理正确。,128,前提：,结论：,推理的形式结构为：,129,方法一,用主析取范式法,130,方法二用等值式法,蕴涵等值式,吸收律,方法三,131,二、构造证明法。,1、推理定律有以下8条：,(1) 附加,(2) 化简,(3) 假言推理,(4) 拒取式,(5) 析取三段论,132,二、构造证明法。,1、推理定律有以下8条：,(6) 假言三段论,(7) 等价三段论,(8) 构造性二难,133,2、推理规则。,(1) 前提引入规则,(3) 置换规则,3、构造证明法。,依照推理规则，应用推理规律。,(2) 结论引入规则,134,例2、构造下列推理的证明。,证明：,前提引入,前提引入,前提引入,构造性二难,135,例2、构造下列推理的证明。,证明：,前提引入,前提引入,拒取式,前提引入,假言推理,136,例2、构造下列推理的证明。,证明：,前提引入,拒取式,前提引入,析取三段论,137,例3、写出对应下面推理的证明。,解：,前提：,结论：,138,证明：,前提引入,前提引入,假言推理,前提引入,前提引入,假言推理,析取三段论,前提：,结论：,139,解：,前提：,结论：,140,证明：,前提引入,置换规则,前提引入,假言推理,前提引入,拒取式,前提：,结论：,141,解：,前提：,结论：,142,证明：,前提引入,置换规则,前提引入,假言三段论,前提：,结论：,143,3、附加前提证明法和归谬法。,(1) 附加前提证明法。,144,例如：例3 (3),前提：,结论：,用附加前提证明：,附加前提引入,前提引入,拒取式,145,例如：例3 (3),前提：,结论：,用附加前提证明：,前提引入,假言推理,化简,由附加前提证明法知推理正确。,146,(2) 归谬法。,因为,147,例如：例3 (2),前提：,结论：,用归谬法证明：,否定结论引入,前提引入,假言推理,前提引入,148,例如：例3 (2),前提：,结论：,用归谬法证明：,析取三段论,前提引入,合取,由归谬法知推理正确。,第一章 小结与例题,150,一、命题与联结词。,1、基本