数理逻辑-上海交通大学.ppt

离散数学 刘胜利 计算机科学与工程系 上海交通大学 liu-sl@cs.sjtu.edu.cn Tel:教材和辅导书 离散数学课程说明 研究对象----离散个体及其结构 研究思想----以集合和映射为工具、体现公理化和结构的思想 研究内容----包含不同的数学分支，模块化结构 数理逻辑：推理、形式化方法 集合论：离散结构的表示、描述工具 代数结构：离散结构的代数模型 图论：离散结构的关系模型 组合数学：离散结构的存在性、计数、枚举、优化、设计 离散概率（概率统计课程） 离散数学主要内容的知识结构 离散数学与计算机科学的关系 数理逻辑：人工智能、程序正确性证明、　　　　　程序验证等 集合论：　关系数据库模型 图论：　　数据结构、数据库模型、　　　　　网络模型等 代数结构：软件规范、形式语义、编译系统、　　　　　编码理论、密码学、数据仓库 组合数学：算法分析与设计、编码理论、容错 课程说明书 讲授内容： 数理逻辑 集合论 图论 作业： 每周一交作业 第一部分 数理逻辑 逻辑：是对人类推理过程的研究。 数理逻辑：是用数学的方法对人类推理过程作研究。 数学研究方法：使用符号 第一章 命题逻辑的基本概念 命题逻辑(Logic) 研究命题的推理演算； 命题逻辑的应用： 数学上定理的推导 在计算机科学上，验证程序的正确性 主要内容 命题的基本概念； 命题联结词； 命题合式公式、重言式； 自然语句的形式化． 1.1 命题（proposition） 命题是一个非真即假(不可兼)的陈述句 命题是一个陈述句，命令句、疑问句和感叹句都不是命题； 命题只有两个取值：真或假。这个陈述句所表达的内容可决定是真还是假，而且不是真的就是假的，不能不真又不假，也不能又真又假。 真假命题： 凡与事实相符的陈述句为真语句，而与事实不符的陈述句为假语句．这就是说，一个命题具有两种可能的取值(又称真值)，为真或为假，并且只能取其一． 通常用大写字母“T”表示真值为真，用“F”表示真值为假．因为只有两种取值，所以这样的命题逻辑称为二值逻辑． 命题举例 (1)“雪是白的” ?； (2)“雪是黑的” ? ； (3)“好大的雪啊” ? ，不是陈述句，不是命题； (4)“一个偶数可表示成两个素数之和” ? ．只不过当今尚不知其是真命题还是假命题． (5)“1+10l＝110”． ? 这是一个数学表达式，相当于一个陈述句，可以叙述为“1加101等于110，这个句子所表达的内容在十进制范围中真值为假，而在二进制范围中真值为真．可见，这个命题的真值与所讨论问题的范围有关． 命题变项 为了对命题作逻辑演算，采用数学手法将命题符号化(形式化)是十分重要的． 命题的表示：大写符号 P表示“雪是白的” Q表示“北京是中国的首都” 命题变项：P表示任一命题时，P就称为命题变项(变元)． 命题与命题变项含义是不同的： 命题指具体的陈述句，是有确定的真值； 命题变项的真值不定，只当将某个具体命题代入命题变项时，命题变项化为命题，方可确定其真值， 命题与命题变项像初等数学中常量与变量的关系一样．如5是一个常量，是一个确定的数字，而x是一个变量，赋给它一个什么值它就代表什么值，即x的值是不定的。 简单命题和复合命题 简单命题又称原子命题(Primitive proposition) 简单命题是不包含任何的与、或、非一类联结词的命题． 简单命题不可再分割，如“雪是白的”再分割就不是命题了． 命题“雪是白的而且l+l＝2”不是简单命题，它可以分割为“雪是白的”以及“1十1＝2”两个简单命题，联结词是“而且”． 在简单命题中，尽管常有主语和谓语，但我们不去加以分割，是将简单命题作为一个不可分的整体来看待，进而作命题演算．在谓词逻辑里，才对命题中的主谓结构进行深入分析． 复合命题(Compound proposition) 复合命题：把一个或几个简单命题用联结词(如与、或、非等)联结所构成的新的命题。 “张三学英语和李四学日语”就是一个复合命题； 由简单命题“张三学英语” “李四学日语”经联结词“和”联结而成。 复合命题的真值：依赖于构成该复合命题的各个简单命题的真值以及联结词。 上例中，当以上两个简单命题真值均为真时，该复合命题方为真． 命题逻辑所讨论的是多个命题联结而成的复合命题的规律性． 内容 / 形式 命题是一个可取真或可取假的陈述句。 数理逻辑不关心：这些具体的陈述句的真值究竟为什么或在什么环境下是真还是假。 数理逻辑关心的是：命题可以被赋予真或假这样的可能性，以及规定了真值后怎样与其他命题发生联系。 1.2 命题联结词及真值表 联结词可将命题联结起来构成复杂的命题。 命题逻辑联结词的引入是十分重要的，其作用相当于初等数学里在实数集