计算机科学导论-基于计算思维的思想与方法（第4版） 课件【ch09】问题求解的离散结构

计算机科学导论基于计算思维的思想与方法问题求解的离散结构第九章新工科建设之路·计算机类系列教材01数理逻辑数理逻辑01一、命题逻辑在数理逻辑中，能够分辨真假但不能同时既真又假的陈述句的内容被称为命题。命题是具有唯一判断结果(有明确的对错之分)的陈述句，而不是类似感叹的抒情句、祈使句等。命题一定是通过陈述句来表达的，但是陈述句并不一定都是命题。只有明确“真”“假”可言的陈述句才是命题。1.命题和真值数理逻辑01一、命题逻辑在命题逻辑中，可以通过连接词由已知命题产生新的命题，我们把这个连接命题与命题的字词称为命题连接词。把由简单命题通过连接词而成的陈述句被称为复合命题。构成复合命题的连接词有5个，分别为：否定、合取、析取、蕴含、等价，并且此顺序为逻辑运算的优先级。2.命题连接词数理逻辑01一、命题逻辑3.命题公式数理逻辑01一、命题逻辑[定义9-7]根据命题公式A在命题变元的任何真值指派下其值的性质，可分为3种。(1)永真式：如果命题公式A在命题变元的任何真值指派下其值恒为真，则称A为永真式或重言式，并常用1表示永真式。(2)永假式：如果命题公式A在命题变元的任何真值指派下其值恒为假，则称A为永假式或矛盾式，常用0表示永假式。(3)可满足式：如果命题公式A至少有一组命题变元的真值指派使其值为真，则称A为可满足式或可能式。4.命题公式分类定积分的近似计算01一、数理逻辑5.逻辑等价关系在所有可能的情况下具有相同真值的两个复合命题称为逻辑等价。T表示永远为真，F表示永远为假，则复合命题的等价关系如表9-6所示。定积分的近似计算01二、谓词逻辑1.个体词(IndividualWord)[定义9-8]在命题逻辑中，个体词是指所研究对象中可以独立存在的具体或抽象的客体。在命题逻辑中，个体词具有以下三要素。(1)个体常元；(2)个体变元；(3)个体域。2.谓词(PredicateWord)[定义9-9]在命题逻辑中，谓词是指用来刻画个体词的性质或个体词之间相互关系的词。定积分的近似计算01二、谓词逻辑3.量词(MeasureWord)[定义9-10]在命题逻辑中，量词是指表示个体常元(项)或个体变元(项)之间数量关系的词。为了区分命题中的“所有的”和“有一些”，量词又分为“全称量词”和“存在量词”。4.谓词推理(VerbReasoning)谓词推理是利用命题公式间的各种等价关系、蕴含关系，通过一些推理规则，从已知命题公式推出一些新的公式。因此，谓词推理是命题逻辑推理的推广。定积分的近似计算01二、谓词逻辑4.谓词推理(VerbReasoning)由于谓词推理不是以整个命题为推理对象的，它的推理对象通常有量词限制，因而具有以下规则。(1)全称量词消去规则(2)存在量词消去规则(3)全称量词引入规则(4)存在量词引入规则定积分的近似计算01三、数理逻辑在计算机科学中的应用数理逻辑对于计算机科学理论的研究有着非常重要的作用，主要体现在以下几方面。1.培养逻辑思维通过对数理逻辑中所揭示的思维规律和所用方法的学习，能培养自己严密的逻辑思维能力，为计算机科学后继课程的学习奠定良好的基础。2.作为理论支撑02集合论集合论021.集合的表示集合通常用大写的英文字母A、B、C、……表示，它的元素通常用小写的英文字母a、b、c、……表示。表示一个集合的方法通常有列举法和描述法。(1)列举法：也称枚举或穷举法，就是列举出集合的所有元素，元索之间用逗号隔开，并把它们用“{}”括起来。(2)描述法：不要求列出集合中的所有元素，只要把集合中的元素具有的性质或满足的条件用文字或字符描述出来。一、集合的表示与运算集合论022.集合间的关系一、集合的表示与运算集合论022.集合间的关系一、集合的表示与运算集合论023.集合的基本运算一、集合的表示与运算集合论023.集合的基本运算一、集合的表示与运算集合论02一、集合的表示与运算4.集合的文氏图表示集合之间的运算也可以用文氏图(VennDiagram)来描述，即用一个矩形表示全集E，在矩形内用圆表示子集，这种表示方法被称为文氏图表示法。集合并、集合交、集合差、集合对称差、集合补的文氏图如图9-3所示。集合论02一、集合的表示与运算5.集合运算恒等式集合运算具有与逻辑运算等价相似的运算规则，集合运算的恒等式如表9-9所示。集合论02一、集合的表示与运算6.有限集合的计数集合论02二、二元关系1.笛卡尔积集合论02二、二元关系2.二元关系定义集合论02二、二元关系3.二元关系表示二元关系通常用三种方式表示有限集之间的关系：集合表示法、矩阵表示法和关系图表示法。集合表示法关系也是一种特殊的结合，所以集合两种基本的表示法也可以用到关系的表示中，即可用列举法和描述法来表示关系。集合论02二、二元关系4.二元关系运算集合论02二、二元关系5.二元关系的性质集合论02二、二元关系6.二元关系的特征(1)等价关系在实数之间的相等关系、集合之间的相等关系、谓词公式之间的等值关系具有类似的性质，它们都具有自反性、对称性和传递性，具有这三种性质的关系称为等价关系。(2)偏序关系事物之间的次序常常是事物群体的重要特征，决定事物之间的次序是事物间的关系一偏序关系，具有传递性，因此可根据这个特性来研究集合中各元素的排序关系。集合论02三、函数1.函数定义集合论02三、函数2.函数性质如图9-11所示。集合论02四、集合论在计算机科学中的应用1.在程序语言中的应用计算机内部的所有信息、各种编码都是字符的集合。2.在数据结构中的应用数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。一个数据结构有两个要素：数据元素的集合、关系的集合。3.在数据库中的应用集合在关系数据库中有着广泛的应用，数据库的数据模型是以集合、二元关系、多元关系和关系代数为理论基础的。03逻辑代数逻辑代数03一、逻辑代数的表示1.逻辑代数与命题逻辑的区别逻辑代数03一、逻辑代数的表示2.布尔变量及其基本运算布尔变量运算只有“·”(与)“+”(或)“-”(非)三种。““与”运算：又称为逻辑乘，两个变量“与”运算的逻辑关系可表示为C=A·B。“或”运算：又称为逻辑加，两个变量“或”运算的逻辑关系可表示为C=A+B.“非”运算：又称为逻辑反，对一个变量“非”运算的逻辑关系可表示为

。逻辑代数03一、逻辑代数的表示3.布尔函数与布尔表达式布尔代数的函数定义与普通代数的函数定义极为相似，设x，y为输入F为输出，输入和输出之间的逻辑关系可表示为F=f(x，y)，则称C是x，y的逻辑函数，F=f(x，y)为逻辑函数表达式。逻辑代数03一、逻辑代数的表示4.布尔代数的恒等关系布尔代数运算的恒等式如表9-11所示。逻辑代数03二、逻辑电路的简化1.逻辑电路部件把实现逻辑函数的电路称为逻辑电路；把实现逻辑变量之间的运算称为逻辑运算；把由基本逻辑部件组成的电路称为逻辑电路，逻辑电路中的常用逻辑部件如图9-13所示。逻辑代数03三、代数系统在计算机科学中的应用1.提供精简的形式化语言2.提供严密的逻辑推理工具3.提供定量分析和计算方法4.为数据通信实现数据编码5.为生物学研究提供数学支撑04图论图论04一、图论的基本概念1.图的定义图论04一、图论的基本概念2.无向图和有向图图论04二、图的矩阵表示1.邻接矩阵(AdjacencyMatrix)图论04二、图的矩阵表示2.关联矩阵(IncidenceMatrix)图论04三、路径回路与连通图1.路径图论04三、路径回路与连通图2.回路与通路图论04三、路径回路与连通图3.连通图[定义9-42]在无向图G中，节点u与v之间若存在一条路，则节点u和v称为是连通的。若图G=<V，E>的任意两个节点均有路径连通，则G称为连通图(ConnectedGraph)，否则称为非连通图(UnconnectedGraph)。图论04三、路径回路与连通图4.计算节点之间的通路数在一个图G中两个节点之间的通路数可以用这个图的邻接矩阵A来确定，A相对于图中的节点v1，vn(允许带有无向边、有向边、多重边和环)，从vi到Vj长度为r的不同通