命题逻辑基本概念.ppt

1,天津城市建设学院电子与信息工程系 Email: 2010.11-2011.12,2,教育的目的 应该使每个人都充满梦想！,3,一、绪论 二、数理逻辑简介 三、命题逻辑的基本概念 （一）命题的概念 （二）命题表示方法 （三）联结词 （四）命题合式公式 （五）命题公式的翻译,主要内容,4,漫谈离散数学 Swimming in Discrete Mathematics,一、绪 论,5,数学？/数学的研究对象是什么?,心智的产物-珀拉图;,研究数和量的学科-亚里士得多,数学=逻辑-罗素,逻辑是数学的少年时代; 数学是逻辑的成年时代,数 学,数学作为人类智慧的一种表达形式，反映生动活泼的意念、深入细致的思考、以及完美和谐的愿望。他的基础是逻辑和直觉、分析和推理、共性和个性。 科朗，罗宾斯（美） 数学是什么，1941年,6,离散数学-研究离散结构的数学分科。（辞海） 相对于研究连续量的微积分，离散数学是研究各种各样的离散量的结构及离散量之间的关系的一门学科。是现代数学的一个重要分支，是计算机科学与技术的理论基础，所以又称为计算机数学。,离散数学的含义,7,一、古老 历史: 计数:自然数 发展: 图论:Konigsberg七桥问题 二、年青 新生: 计算机:二进制运算,离散数学的由来与发展,8,离散数学-现代科学的重要分支,离散数学是在计算机问世之后，迅速发展起来的一门数学分支。 离散数学改变了传统数学中分析和代数占统治地位的局面。 离散数学是一门在基础数学研究中具有极为重要地位的、综合的数学学科。 离散数学在计算机科学、编码和密码学、物理、化学、生物等许多学科中均有重要应用。 离散数学特点-离散性、抽象性、逻辑性、可行性 这些特点正是离散数学难学的根本原因，也正是离散数学深具诱惑和迷人之处。,9,第一部分 数理逻辑 命题演算、谓词演算； 公理化集合论、递归论、模型论、证明论 -计算机是数理逻辑和电子学相结合的产物 第二部分 集合论 集合：一种重要的数据结构 关系：关系数据库的理论基础 函数：所有计算机语言中不可缺少的一部分 第三部分 代数系统 （运算、代数系统、半群、群、环、域、格、布尔代数） 计算机编码和纠错码理论 数字逻辑设计基础 计算机使用的各种运算 第四部分 图论 数据结构、操作系统、编译原理、计算机网络原理的基础,离散数学的内容及与计算机的关系,10,参考教材,1.离散数学（左孝琳、李为槛、刘永才，上海科技文献版） 2.离散数学学习指导与习题解析 耿素云 屈婉玲 高等教育出版社 （2005.3） 3.离散数学及其应用（Discrete Mathematical and Its Applications) （原书第5版） Kenneth Rosen著 袁崇义 屈婉玲 等译 机械工业出版社（2007.6）) 4.Discrete Mathematics（ Revised Edition: Biggs ) 5.离散数学常见题型解析及模拟题 傅彦 西北工业大学出版社 （2004 ）,11,课程地位,离散数学课程设置： 计算机系核心课程、信息类专业必修课程、其它类专业的重要选修课程,离散数学的后继课程： 数据结构、编译系统、人工智能、数据库、操作系统、软件工程与方法学、计算机网络、程序设计,12,（1）它给后继课提供必要的数学基础；为以后计算机的软、硬件学习和研究开发工作，打下坚实的数学基础； （2）通过离散数学课程的学习，可以培养数学抽象能力；用数学语言描述问题的能力；逻辑思维能力；数学论证能力。即培养抽象、表示、推理、论证的能力； （3）写出优秀的程序来解决实际问题； （4）能够针对科研和生产中产生的问题来建立数学模型，设计新的算法并论证算法的有效性；,学习目的,13,典型实例,离散数学无处不在，主要应用于在各种复杂的关系中找出最优方案。 离散数学完全可以看成是一门量化了的关系学，量化了的运筹学，量化了的管理学。 例如：世界近代三大数学难题、出差派遣问题、船夫过河问题、工作调度和安排问题、航空调度和航班设定问题、交通规划与管理问题、中国邮路问题、工程工序管理问题、地面铺砖问题、网络布局问题、金融分析问题、哥尼斯堡七桥问题、一笔画问题、蚂蚁比赛问题,14,典型实例,1、四色猜想问题 一张世界地图，若用一种颜色对一个国家着色，那么只需四种颜色，即可以保证每两个相邻的国家颜色不同。 世界近代三大数学难题之一。1852年，英国弗南西斯格思里(Francis Guthrie)提出四色猜想。 1976年，在J. Koch的算法的支持下，美国数学家阿佩尔(Kenneth Appel)与哈肯(Wolfgang Haken)在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明。最近人们发现了更简单的证明。,15,A，B，C，D四人中要派两个人出差，按下述三个条件有几种派法？ 如何派？ 若A去则C和D中要去一个人； B和C不能都去； C去则D要留下,2.出差派遣问题,典型实例,3.船夫过河问题,船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场,羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样才能把三者都运过河?,16,4、工作调度和安排问题,如在生产原子弹的曼哈顿计划中，涉及到很多工序、很多人员安排、很多元件生产。 怎样合理调度各种人员的工作？ 怎样科学安排各种工序间的衔接？ 怎样计划使整个工期的时间尽可能短？,5、航空调度和航班设定问题,怎样周密设定各个航班，以满足不同旅客转机的需求？ 怎样同时也使得每个机场的各个航班的起降分布合理？ 在一些航班有延误的特殊情况下，怎样作出科学的调整？,典型实例,17,6、交通规划与管理问题,哪些地方可能是阻塞要地？ 哪些地方应设单行道？ 立交桥建在哪里最合适？ 红绿灯怎样设置最合理？,7、中国邮路问题,一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应按怎样的路线走，他所走的路程才会最短？ 由我国数学家管梅谷在1962年首先提出的，因此，在国际上称为中国邮路问题。,典型实例,18,8、工程工序管理问题,世界著名的假日饭店在其科学管理中严格规定了有关工序： 清洁工第一步是换什么，洗什么？第二步又做什么？同时需要确保他进出房间的次数最少？ 一个如此简单的工作都要讲究工程工序管理，那么更复杂的的工作就更不用说了。,9、地面铺砖问题,用形状相同的方形砖块，无疑可将地面铺满（不考虑边缘的特殊情况）而如用不同形状，又非方形的砖块来铺地面时，能否铺满？ 这一常见的实际的简单问题，也涉及到很深的数学原理。,典型实例,19,10、网络布局问题,一个通信网络怎样布局最节省？ 美国的贝尔实验室和IBM公司都有世界一流的组合数学家在研究这个问题。该问题关系到巨大的经济效益。,11、金融分析问题,投资方案的确定 怎样找出好的投资组合以降低投资风险。 南开大学组合数学研究中心开发出“金沙股市风险分析系统”，已投放市场，为短线投资者提供有效的风险防范工具。,典型实例,20,12、一笔画问题,所谓一笔画，就是从图形上的某点出发，笔不离开纸，而且每条线都只画一次不准重复。什么样的图形能一笔画成呢？,21,13、蚂蚁比赛问题,甲乙两只蚂蚁进行比赛： 从他们所在的结点出发，在图中走过所有的点，最后到达C处，如果他们的速度相同，问谁先到达目的地？,22,14、哥尼斯堡七桥问题,18世纪时，欧洲有一个风景秀丽的小城哥尼斯堡，那里有七座桥。如图所示。当时哥尼斯堡的居民中流传着一道难题：一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点？,23,15、环游世界问题,从正十二面体的一个顶点出发，沿着正十二面体的棱前进，要把二十个顶点无一遗漏地全部通过，而且每个顶点恰好只通过一次，最后回到出发点，這样，便是哈密尔顿周游世界问题。,24,教学要求： 通过该课程的学习，学生应当了解并掌握计算机科学中普遍采用的离散数学中的一些基本概念、基本思想、基本方法。 自学要求： 通过反复看书及做课后习题，来加深对该课程中的一些基本概念的理解，逐步提高自己的抽象思维和逻辑推理能力。,学习要求,25,离散数学课程的学习方法: 强调：逻辑性、抽象性； 注重：概念、方法与应用 离散数学的学习要领： 概念（正确） 必须掌握好离散数学中大量的概念 判断（准确） 根据概念对事物的属性进行判断 推理（可靠） 根据多个判断推出一个新的判断,学习方法,26,第一部分 数理逻辑,数理逻辑,27,历史使人聪明， 诗歌使人机智， 数学使人精细， 哲学使人深邃， 道德使人严肃， 逻辑与修辞使人善辩。,数理逻辑,28,- 一套符号体系 + 一组规则,逻 辑 学：旧称“名学”、“论理学”，是研究推理的一门学科； 数理逻辑：用数学方法研究推理的形式结 构和规律的一门数学学科,数学方法：建立一套符号来描述和讨论问题，避免歧义性； 推 理： 就是研究前提和结论之间的关系和 思维规律，亦即符号之间的关系,数理逻辑,29,数理逻辑的创始人是Leibniz，为了实现把推理变为演算的想法，他把数学引入了形式逻辑。其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学科。 上个世纪30年代以后，数理逻辑进入一个崭新的发展阶段，逻辑学不仅与数学结合，还与计算机科学等密切关联。 1931年Godel不完全性定理的提出，以及递归函数可计算性的引入，促使了1936年Turing机的产生，十年后，第一台电子计算机问世。,数理逻辑,30,数理逻辑 在计算机科学中的作用,硬件开发 -硬件电路的表示、分析和设计 软件设计 -程序算法数据 -算法逻辑控制,为什么要研究数理逻辑？ “逻辑是不可战胜的，因为要反对逻辑还得使用逻辑。”P.Boutroux 计算机可处理大量信息，要利用计算机就要学会编制“程序”：,31,著名计算机软件设计大师E.W.Dijkstra曾经这样说：“我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟了。我想，假如我早年在数理逻辑上好好下点功夫的话，我就不会犯这么多的错误。不少东西逻辑学家早就说了，可我不知道。要是我能年轻20岁的话，就要回去学逻辑。” 我国著名数理逻辑学家甚至说得更加直截了当：“事实上，程序设计或者就是数理逻辑，或者是用计算机语言书写的数理逻辑，或者是数理逻辑在计算机上的应用。”可以说计算机的本质结构就是逻辑结构。,数理逻辑 在计算机科学中的作用,32,数理逻辑与计算机学、控制论、人工智能的相互渗透推动了其自身的发展，模糊逻辑、概率逻辑、归纳逻辑、时态逻辑等都是目前比较热门的研究领域。 本章和下一章我们只从语义出发，对数理逻辑中的命题逻辑与谓词逻辑等作一简单的、直接的、非形式化的介绍，将不涉及任何公理系统。,数理逻辑,33,任何基于命题分析的逻辑称为命题逻辑。命题是研究思维规律的科学中的一项基本要素，它是一个判断的语言表达。,第一章 命题逻辑的基本概念,（一）命题的概念 （二）命题表示方法 （三）联结词 （四）命题合式公式 （五）命题公式的翻译,34,命题与真值 命 题： 判断结果是否惟一的陈述句 命题的真值： 判断的结果 真值的取值： 真与假 真命题与假命题 注意： 感叹句、祈使句、疑问句都不是命题; 悖论，判断结果不惟一确定的不是命题.,一、 命题的概念,35,例1 下列句子中那些是命题？ (1) 是有理数. (2) 2 + 5 = 7. (3) x + 5 3. (4) 你去教室吗？ (5) 这个苹果真大呀！ (6) 请不要讲话！ (7) 2050年元旦下大雪. (8) 我正在说谎。,假命题,真命题,不是命题,不是命题,不是命题,不是命题,命题，但真值现在不知道,悖论，不是命题,36,一个人说：“我正在说谎”。 1)结论：如果他是说谎(命题为T），则他是讲真话。 （他认为他是说谎，他实际上是在说真话） 2)结论：如果他讲真话(命题为F），则他是在说谎。 (如果他讲真话，则他说的是真的，也就是他是在说谎) 此话既不是说谎也不是讲真话，不能判断它的真假值。,不能判断真假的陈述语句叫悖论（非命题）。,37,再例 A：数学是一门科学（T） B：四川是一个省 （T） C：2+3=6 （F） D：地球是不动的 （F） E：2010年人将到达火星（T/F） F：今天是十月一日（T/F） G：这菜辣了 （T/F）,38,以上所讨论的命题在数理逻辑中称为简单命题，或称为原子命题，用p、q、r、pi、qi、ri等符号表示（亦可用其它小写的英文字母表示）。如： p：4是偶数。 在命题逻辑的符号化过程中，通常的要求是每一个引进的表示命题的符号都表示一个原子命题。 例如：将下列命题符号化 杭州不是中国的首都。 解 令P：杭州是中国的首都。则命题“杭州不是中国的首都”符号化为：P,二、 命题的表示方法,39,【例】 下列命题特点： （1）4是偶数且是2的倍数。 （2）北京不是个小城市。 （3）小王或小李考试得第一。 （4）如果你努力，则你能成功。 （5）三角形是等边三角形，当且仅当三内角相等。,由命题和联结词构成的命题称为复合命题。构成复合命题的可以是原子命题，也可以是另一个复合命题。一个复合命题的真值不仅与构成复合命题的命题的真值有关，而且也与所用联结词有关。,命题分类：简单命题和复合命题,40,三、联结词（逻辑运算符）,定义1.3 设p, q为两个命题，复合命题“p或q”称作p与q的析取式，记作pq，称作析取联结词. 规定pq为假当且仅当p与q同时为假.,定义1.1 设 p为命题，复合命题“非p”(或“p的否定”)称为p的否定式，记作p，符号称作否定联结词. 规定p 为真当且仅当p为假.,定义1.2 设p,q为两个命题，复合命题“p并且q”(或“p与 q”)称为p与q的合取式，记作pq，称作合取联结词. 规定pq为真当且仅当p与q同时为真.自然语言中的表示“并且”意思的联结词，如“既又”、“不但而且”、“虽然但是”、“一面一面”等都可以符号化为。,41,例 将下列命题符号化. （1）设P 表示“整数都是自然数”，则P表示：,否定联结词的实例,“并非整数都是自然数”或“整数不都是自然数”， 而不是“整数都不是自然数”。,（2）设P表示“昨天张三去看球赛了”P表示：,“昨天张三没有去看球赛 若昨天张三去看球赛了，命题P是真的，那么新命题P必然是假的反之，若命题P是假的，那么P就是真的,42,例2 将下列命题符号化. (1) 吴颖既用功又聪明. (2) 吴颖不仅用功而且聪明. (3) 吴颖虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学.,合取联结词的实例,43,解 令p:吴颖用功, q:吴颖聪明 (1) pq (2) pq (3) pq (4) 设p:张辉是三好生, q:王丽是三好生 pq (5) p:张辉与王丽是同学 (1)(3) 说明描述合取式的灵活性与多样性 (4)(5) 要求分清 “与” 所联结的成分,合取联结词的实例,44,例3 将下列命题符号化 (1) 2 或 4 是素数. (2) 2 或 3 是素数. (3) 4 或 6 是素数. (4) 小元元只能拿一个苹果或一个梨. (5) 王小红生于 1975 年或 1976 年.,析取联结词的实例,45,解 (1) 令p:2是素数, q:4是素数, pq (2) 令p:2是素数, q:3是素数, pq (3) 令p:4是素数, q:6是素数, pq (4) 令p:小元元拿一个苹果, q:小元元拿一个梨 (pq)(pq) (5) p:王小红生于 1975 年, q:王小红生于1976 年, (pq)(pq) 或 pq (1)(3) 为相容或 (4)(5) 为排斥或, 符号化时(5)可有两种形式，而(4)则不能,析取联结词的实例,46,定义1.4 设p, q为两个命题，复合命题“如果p, 则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件，称作蕴涵联结词. 规定：pq为假当且仅当p为真q为假.,蕴涵联结词,(1) pq 的逻辑关系：q为 p 的必要条件 (2) “如果 p, 则 q” 有很多不同的表述方法： 若p，就q 只要p，就q p仅当q 只有q 才p 除非q, 才p 或 除非q，否则非p， (3) 当 p 为假时，pq恒为真，称为空证明 (4) 常出现的错误：不分充分与必要条件,47,例4 设 p：天冷，q：小王穿羽绒服，将下列命题符号化 (1) 只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候.,蕴涵联结词的实例,pq,注意： pq 与 qp 等值（真值相同）,pq,pq,qp,qp,pq,qp,qp,48,说明：数理逻辑中的联结词是对日常语言中的联结词的一种逻辑抽象，日常语言中联结词所联结的句子之间是有一定内在联系的，但在数理逻辑中，联结词所联结的命题可以毫无关系。 如与自然语言的不同： 前件与后件可以没有任何内在联系！ p：天下雨了； r：三七二十一。则 pr：如果天下雨，则三七二十一。,49,定义1.5 设 p, q为两个命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq，称作等价联结词. 规定pq为真当且仅当p与q同时为真或同时为假. pq 的逻辑关系：p与q互为充分必要条件,等价联结词,例5 求下列复合命题的真值 (1) 2 + 2 4 当且仅当 3 + 3 6. (2) 2 + 2 4 当且仅当 3 是偶数. (3) 2 + 2 4 当且仅当 太阳从东方升起. (4) 2 + 2 4 当且仅当 美国位于非洲. (5) 函数 f (x) 在 x0 可导的充要条件是 它在 x0 连续.,1,0,0,1,0,50,取反,均为真,至少一个为真,相同为真,51,总结,以上5种最基本、最常用、最重要的联结词可以组成一个集合 ，成为一个联结词集，其运算的优先级为： ， ，对于同一级者，先出现者先运算。,52,补充：,小明和小亮既是兄弟又是同学。,PQ,如果你和他不都是白痴，则你俩都不会去干此傻事。,无论你和他去不去，我去。,53,四、命题合式公式,为了用数学的方法研究命题，就必须像数学处理问题那样将命题公式化，并讨论对于这些公式的演算（推理）规则，以期由给定的公式推导出新的命题公式来。,54,定义1 简单命题/命题常项/命题常元：真值唯一确定的陈述句。 定义2命题变项/变元：真值可以变化的陈述句。