第1章-命题逻辑.ppt

;为什学习离散数学? 作为一个专业的程序员, 计算机本质上应该将其看为一个抽象逻辑的运算机，一个推理机器，一个逻辑结论的暂存器. 我们要利用这样的一个magic box来做人想要它做的事，那么就要dismagic the box，也就是要理解它。;学习好离散数学的本质在于学习好一门语言，通过这样的语言就能很好的对这个magic box进行描述和表达（人类的自然语言不适于这样的需求，自然语言更加适用与日常表达）。;离散数学既是现代数学的一个重要分支，又是计算机科学中基础理论方面的核心内容。离散数学是以离散量的结构和相互之间的关系为主要研究目标，其研究对象一般地是有限个或可数个元素。 离散数学是随着计算机科学的发展而逐步建立的，它形成于20世纪70年代初，是一门新兴的工具性学科。 离散数学与计算机科学中的数据结构、操作系统、编译理论、算法分析、逻辑设计、系统结构、容错诊断、机器证明等课程联系紧密。;包括的主要内容如下： 一、数理逻辑：命题逻辑（10学时）和谓词逻辑（10学时） 。 二、集合论：集合与关系（10学时），函数（4学时） 三、代数结构与布尔代数 四、图论（16学时） 五、应用：形式语言与自动机；纠错码初步。;在使用逻辑法则进行推理或做出判断时，总要从某些公认的基本事实（命题）出发，利用公认的有效规则一步一步地导出最终结论。推理过程中的每一个中间命题要么是一个公认的事实，要么是前面一些命题的必然结果。;?先看著名物理学家爱因斯坦出过的一道题 一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴的帽子是什么颜色的。”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来， 接着把灯打开。这时，那两个应试者看到商人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽子。”请问这个人说得对吗？他是怎么推导出来的呢？ ;要回答这样的问题，实际上就是看由一些诸如“商人戴的是红帽子”这样的前提能否推出“猜出答案的应试者戴的是黑帽子”这样的结论来。这又需要经历如下过程： 什么是前提？有哪些前提？ 结论是什么？ 根据什么进行推理？ 怎么进行推理？ ;退出;第一章 命题逻辑;1.1 命题与联结词 1.2 命题变元和合式公式 1.3 公式分类与等价公式 1.4 对偶式与蕴含式 1.5 联结词的扩充与功能完全组 1.6 公式标准型——范式 1.7 公式的主范式 1.8 命题逻辑的推理理论;1.1 命题与联结词;几个实例： 雪是黑的。（ √ ） 别的星球上有生命。（能区分真假√ ） 1+101=110（看进制,需要前提条件才能判断） 天气真好！（） 全体立正！（） 明天有雨吗？（） 我正在说谎。（悖论） 孔夫子是我国古代伟大的思想家和教育家。(√ ) 白天比夜晚时间长。(需要依靠季节来判断No) ;x+y0 (要依赖于x和y的取值范围才能确定 出其真或假，因而也不是命题；) 两个三角形全等当且仅当它们的对应角相等。 我学英语或者我学日语。（√） 如果天气好，那么我去散步。(√) ;如果一陈述句再也不能分解成更为简单的语句，由它构成的命题称为原子命题。原子命题是命题逻辑的基本单位。 命题分为两类，第一类是原子命题，原子命题用大写英文字母P，Q，R…及其带下标的Pi，Qi，Ri，…表示。称为命题的标识符。 第二类是复合命题，它由原子命题、命题联结词和圆括号组成。;２. 命题联结词 定义1.1.1 设P表示一个命题，由命题联结词l和命题P连接成lP，称lP为P的否定式复合命题， lP读“非P”。称l为否定联结词。 lP是真当且仅当P为假；lP是假当且仅当P为真。否定联结词“l”的定义可由表1.1.1表示之。 ;由于否定”修改了命题，它是对单个命题进行操作，称它为一元联结词。 例：P： 上海是一个大城市。 lP： 上海并不是一个大城市 lP ： 上海是一个不大的城市。;定义1.1.2 设P和Q为两个命题，由命题联结词∧将P和Q连接成P∧Q，称P∧Q为命题P和Q的合取式复合命题，P∧Q读做“P与Q”，或“P且Q”。称∧为合取联结词。 当且仅当P和Q的真值同为真，命题P∧Q的真值才为真；否则，P∧Q的真值为假。合取联结词∧的定义由表1.1.2表示之。 ;例：P：今天下雨，Q：明天下雨。 P∧Q: 今天下雨而且明天下雨； P∧Q: 今天与明天下雨； P∧Q: 这两天都下雨； 例：