1-1.2 命题逻辑 离散数学 教学课件.pptVIP

公式 C= (p?q) ??r 的真值表 p q r p?q ?r (p?q)? ?r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 若公式C不是矛盾式，则称C为可满足式) 注意： 重言式是可满足式，但反之不真. 作业1 P32: 1 (2)(4)(6)(8) P33: 3 (1)(3)(5) P33: 5 (1)(3)(5)(7) P33: 6 (1)(2) P33: 7 (1)(2) * 它是随着计算机科学的发展而逐步建立，它形成于70‘S初期，是一门新兴的工具性学科。 * 因此，它充分描述了计算机科学离散性的特点。 它是随着计算机科学的发展而逐步建立，它形成于70‘S初期，是一门新兴的工具性学科。 * 要回答这样的问题，实际上就是看由一些诸如“商人戴的是红帽子”这样的前提能否推出“猜出答案的应试者戴的是黑帽子”这样的结论来。 而当时与他一同获奖的钱学森45岁,华罗庚46岁。 * * 除地球外的星球有生物. (是命题) 它的真值是唯一确定的,只是目前人们不知道。 太阳明天会出来。 (是命题) 它的真值是唯一确定的,到明天就知道了。 * “不可兼或”可用”可兼或”联结词来表示 * 理学院信息与计算科学系 主讲 凌卫新 x1 x2 x3 y1 y2 Y y3 X 离 散 数 学 《离散数学》课程的重要性 现代科学技术的各个领域，都提出了大量离散结构的科学问题。例如： 计算机科学 程序设计 计算机网络 信息论与编码 它们都与离散数学密切相关。 离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。 主要目标—— 研究离散量的结构和相互之间关系 研究对象—— 一般是有限个或可数个元素 通信理论 现代密码学 数字信号处理 形式语言 《离散数学》课程的重要性 研究内容—— 数理逻辑 集合论 代数学 组合数学 与之关系密切的课程 数据结构 操作系统 编译原理 算法分析 图论 计算理论 复杂网络 网格及网络计算 逻辑设计 系统结构 容错诊断 机器定理证明 《离散数学》课程的主要内容 第一部分 数理逻辑 第1章 命题逻辑 第2章 一阶逻辑 第二部分 集合论 第3章 集合的基本概念和运算 第4章 二元关系和函数 第三部分 代数结构 第5章 代数系统的一般性质 第6章 几个典型的代数系统 第四部分 图论 第7章 图的基本概念 第8章 一些特殊的图 第9章 树 第五部分 组合分析初步（第10章） 本课程的要求 授课总学时 48学时：授课周数为12周，每周4学时； 作业 第2、4、7、9、11周星期二为交作业时间， 只有当作业收齐交到讲台上后才开始上课； 成绩评定 平时成绩：20% 考试成绩：80% 第一部分 数理逻辑 ??先看著名物理学家爱因斯坦出的一道题: 一个商人想招聘一个聪明的助手，有两人前来应聘，商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里， 他打开灯后说：“桌子上有五顶帽子，两顶红色，三顶黑色，现在把灯关掉，并把帽子的位置弄乱，然后我们每人摸一顶帽子戴在自己头上，我再藏起余下的两顶帽子，开灯后，你们要尽快说出自己头上戴的帽子的颜色。” 当开灯后，那两个应试者看到商人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽子。” 请问这个人说得对吗？他是怎么推导出来的呢？ 第一部分 数理逻辑 这需要经历如下过程： 什么是前提？有哪些前提？ 结论是什么？ 根据什么进行推理？ 怎么进行推理？ 数理逻辑将回答这些问题，它包括—— 命题逻辑 一阶逻辑 数理逻辑 研究的中心问题是推理 是用数学方法来研究推理的形式结构和推理规律的数学学科 吴文俊(1919-)——数学机械化 1976年，吴文俊教授在中国古代数学机械化思想的启发下，创建了数学机械化方法—— 从几何公理体系出发，引进坐标，将任意几何问题代数化，将证明题的假设与结论分别表示成多元多项式方程，在计算机上编程运算，以判断定理是否成立。 至2008年，运用吴文俊教授的方法，已证明出600多条定理，许多定理的证明不超过几秒钟。甚至有一些定理证明相当繁杂，即便交给杰出的数学家来证也是相当困难的。 “数学机械化” 是近代数学史上的第一个中国原创的领域，被国际上称为“吴方法”。 它终于实现了千百年来几何定理机械化证明的梦想。 它给2000多年的公理化演绎体系带来了