人工智能中离散数学.pptVIP

数理逻辑 逻辑学: 研究人的思维形式和规律的科学．由于研究的对象和方法各有侧重而又分为形式逻辑、辩证逻辑和数理逻辑． 数理逻辑: 用数学方法研究推理，是研究推理中前题和结论之间的形式关系的科学．所谓推理就是由一个或几个判断推出一个新判断的思维形式. 这里所说的数学方法就是建立一套表意符号体系，对具体事物进行抽象的形式研究的方法．因此，数理逻辑又称符号逻辑．这种方法的优点是表达简洁、推理方便、概括性好、易于分析等． 数理逻辑 一般认为，数理逻辑是由德国数学家兼哲学家莱布尼兹(G.W.Leibnitz)在17世纪中叶创立的．其后由英国数学家布尔(G.Bool)于1847年出版的《逻辑的数学分析》一书发展了逻辑代数，即通常称为布尔代数．还有德国数学家弗雷树(F.L.G.Frege)于1879年出版了《表意符号》,引入了量词、约束变元，使逻辑演算趋于完备．1930年出生于奥地利的美藉数学家哥德尔(K.G?del)的完全性定理证明，使数理逻辑的基础得到完善．意大利数学家皮亚诺(G.Peano)，英国数学家德·摩根(A.DeMorgen)、罗素(B.A.W.Russell)等人都做了很大贡献，丰富和发展了数理逻辑． 数理逻辑 数理逻辑主要包括五部分：逻辑演算、证明论、公理化集合论、模型论和递归函数论．本篇仅介绍计算机科学领域中所必需的数理逻辑基础知识： 命题逻辑 谓词逻辑 1.1命题逻辑 能判断真假的陈述语句称为命题。一个语句如果不能再进一步分解成更为简单的语句,而且又是一个命题则称此命题为原始命题 ????作为命题的陈述句所表达的判断结果称为命题的真值，真值只取两个值：真或假。真值为真的命题称为真命题，真值为假的命题称为假命题。真命题表达的判断正确，假命题表达的判断错误。任何命题的真值都是唯一的。 命题逻辑 判断给定句子是否为命题，应该分两步： 首先判定它是否为陈述句 其次判断它是否有唯一的真值。 例1 判断是否为命题? (1) 雪是黑色的。 (2) x大于y。 (3) 月球上有冰。 (4) 2100年元旦是晴天。 (5)π大于3.14 吗？ (6) 请不要吸烟！ (7) 这朵花真美丽啊！ (8) 我正在说假话。 本例中的8个句子中，(5)是疑问句，(6)是祈使句，(7)是感叹句，因而这3个句子都不是命题。 剩下的5个句子都是陈述句，但(2)无确定的真值，根据x,y的不同取值情况它可真可假，即无唯一的真值，因而不是命题。 虽然今天我们不知道(3)，(4)的真值，但它们的真值客观存在，而且是唯一的，将来总会知道(3)的真值，到2100年元旦(4)的真值就真相大白了。 若(8)的真值为真，即“我正在说假话”为真，也就是“我正在说真话”，则又推出(9)的真值应为假；反之，若(9)的真值为假，即“我正在说假话”为假，也就是“我正在说假话”，则又推出(9)的真值应为真。于是(9)既不为真又不为假，因此它不是命题。像(9)这样由真推出假，又由假推出真的陈述句称为悖论。凡是悖论都不是命题。 例2 2是偶素数； 2或4是素数； 如果2是素数，则3也是素数； 2是素数当且仅当3也是素数。 全是命题。 ????上述命题都是通过诸如“或”，“如果……，则……”等连词联结而成，这样命题，称为复合命题。相对地，构成复合命题的命题称为简单命题。 1.2 逻辑联词 联结词是逻辑联结词或命题联结词的简称，它是自然语言中连词的逻辑抽象. 有了联结词，便可以用它和原子命题构成复合命题．常用联结词有以下5种． 1.2 逻辑联词 1.2 逻辑联词 1.2 逻辑联词 (3) 析取(Disjunction)，∨ 命题P与Q的析取是命题P∨Q,读作P或Q。P∨Q假，当且仅当P与Q都假。 1.2 逻辑联词 (4) 条件联结词(Implication)，?? 命题P?Q,读作“P条件Q”或“如果P,则Q”。当P为F, P?Q为T,称为“善意推定”. P→Q假，当且仅当P真而Q假。 1.2 逻辑联词 (5) 双条件(Bicondition)，? 命题P与Q组成双条件命题P?Q,读作P当且仅当Q。P?Q 取真，当且仅当P与Q取相同的真值(同真或同假)。这里称P为双条件命题的左支,称Q为右支。 1.2逻辑联词 ????以上定义了五种最基本、最常用、也是最重要的联结词┐，∧，∨，→， ，将它们组成一个集合{┐，∧，∨，→， }，称为一个联结词集。其中┐为一元联结词，其余的都是二元联结词。 使用这些联结词的好处就是： 可以将复杂命题表示成简单的符号公式。 连接词的优先级: ┐，∧，∨，→， 1.3 命题形式与真值函数 从上可知，命题分两类：一类是原子命题；另一类是复合命题，它是由原子命题和联结词复合而成．判断一个命题是