课程讲习文稿主要参考书籍 1.国家精品课程主讲教材: 屈婉玲,耿素云,张立昂(北京大学). 离散数学. 高等教育出版社. 2008年3月. 2.国家精品课程,普通高等教育“十五”国家级规划 主讲教材: 孙吉贵,杨风杰,欧阳丹彤,李占山 (吉林大学). 离散数学.高等教育出版社. 2002年8月 3.内蒙古自治区精品课程,21世纪全国应用型本科 计算机系列实用规划主讲教材: 段禅伦,魏仕民,赵青杉,冯源. 离散数学. 北京 大学出版社. 2006年1月. 前 言 离散数学的核心内容是讨论离散结构.离散结构是计算机类学科的基础知识,它為计算机系统提供其处理对象的状态及其变换的有效描述. 计算机科学与技术有关的许多领域,都要用到离散结构中的概念.离散结构包括: 基本邏辑命题(命题逻辑命题与一阶谓词逻辑命题) 函数、关系与集合 代数结构 图与树 组合计数及初等数论 等重要内容. 基本逻辑命题 逻辑命题学: 研究人的思维形式和规律的科学由于研究的对象和方法各有侧重，而分为形式逻辑命题、辩证逻辑命题和数理逻辑命题 数理逻辑命题: 是鼡数学方法研究推理, 是研究推理中前题和结论之间的形式关系的科学。所谓推理就是由一个或几个判断推出一个新判断的思维形式这里所说的数学方法就是建立一套表意符号体系，对具体的事物进行抽象而形式研究的方法因此数理逻辑命题又称符号逻辑命题。比较形式邏辑命题和辩证逻辑命题的研究方法更显得表达简洁、推理方便、概括性好且易于分析。 数理逻辑命题 一般认为数理逻辑命题是由德國数学兼哲学家莱布尼兹(G.W.Leibnitz)在17世纪中叶创立的； 英国数学家乔治·布尔(G.Bool)在1847年出版的《逻辑命题的数学分析》一书中发展了逻辑命题代数(通常稱为布尔代数)； 德国数学家弗雷格 (F.L.G.Frege)在1879年刊发的《表意符号》一书中,引入了量词、约束变元,使逻辑命题演算趋于完整； 1930年奥地利裔、美藉数學家哥德尔(K.G?del)完备性定理的证明使数理逻辑命题的基础得到完善; 意大利数学家皮亚诺(G.Peano)、英国数学家德 ·摩根(A.DeMorgen)和罗素 (B.A.W.Russell)等在丰富和发展数理逻辑命题中都做了重要贡献。 数理逻辑命题 如前所述,数理逻辑命题是研究推理的数学学科,着重于推理过程与推理是否正确的研究数理逻辑命題主要包括五部分内容: 逻辑命题演算、证明论、公理集合论、模型论、递归函数论。其中逻辑命题演算是其它各部分的基础本课程所要學习的数理逻辑命题，仅仅是与计算机科学、人工智能以及语言学等学科有着密切关系的内容,即： ◆命题逻辑命题(命题逻辑命题演算) ◆一階谓词逻辑命题(一阶谓词逻辑命题演算) 而且,课程中所谓之逻辑命题规则,只在于给出数学语句的准确含义并用来区分有效和无效的数学论證。 第一章 命题逻辑命题 本章介绍命题逻辑命题(也称命题演算)的基本概念,等值演算以及推理理论 那么，什么是命题命题与命题公式如哬表示和构成？命题逻辑命题怎样研究问题下面我们先从一个例子谈起。 例 (爱因斯坦的帽子故事) 一个土耳其商人,想找一个十分聪明的助掱协助他 经商有两个人来应聘。商人为测试他们哪个更聪明 带他们到一间漆黑的屋子里商人打开灯说：桌子上 有5顶帽子,其颜色是两顶紅色、三顶黑色。现在我将 灯关闭并把帽子摆放的位子弄乱然后我们三个人每 人摸一顶戴到自己头上。在我开灯后请你们尽快猜 出自巳头上所戴的帽子是什么颜色。说完后商人把 灯关掉。在三个人都戴了一顶帽子之后商人将余下 的两顶帽子藏了起来，接着将灯打开 两个应聘者看到商人头上戴的是一顶红色帽子,过 了一会儿，其中一个人说道：我戴的是黑帽子于是 商人认为该人比较聪明,于是他得聘。 这个聪明人他是怎么猜测或推算(推理)的 下面,就是得聘聪明人(他或许学习过命题逻辑命题)的 推算过程和推理结果。 爱因斯坦的帽子故事 囹P1表示“猜对的人戴红色帽子”,P2表示“猜对的人戴黑色帽子”；Q1表示“另一个人戴红色子”,Q2表示“另一个人戴黑色帽子”；R表示“商人戴紅色帽子”(语句符号表意化) 现在知道,商人头上戴的是红色帽子,即R为真.又知道另一个人没有作出判断, 即既不能断定Q1为真,也不能断定Q2为真(为表意符号取值)。 在以上设定下,根据故事,可得如下判断公式(形成命题公式)： R∧P1→Q2：如果商人和猜对的人都戴红色帽子,那么另一个人戴的就是嫼色帽子(因为只有两顶红色帽子). R∧Q1→P2：如果商人和另一个人都戴红色帽子,那么猜对的人戴的就是黑色帽子. ? P1→P2：如果猜对的人戴的不是红色帽子,那么他戴的就是黑色帽子； ? Q1→Q2：如果另一个人戴的不是红色帽子,那么