《命题与联结词》PPT课件.ppt

请各位同学认真选择好座位 以后便对号入座 以后点名 只对座位不对人 靠门的最后一排不坐人 离散数学 任课老师 邓炳茂 课程名称 离散数学课程代码 GE1032课程学时 每周4学时学分 4学分课程性质 必修考试 课程介绍 绪论1 何谓离散数学离散数学是随着计算机科学的发展而形成的一门工具性课程 它主要是研究离散量的结构及相互之间的关系 同时离散数学不仅重视存在性问题的研究 更重视可行性问题的研究 2 开设离散数学的目的奠定计算机科学必备的数学知识 提高学生逻辑思维的能力 3 离散数学所包含的内容 目录 第一篇数理逻辑第1章命题逻辑第2章一阶逻辑第二篇集合论第3章集合第4章关系第三篇代数结构 不讲 第四篇图论第7 8 9章 学习本课程的具体要求 一 课前预习 按时上课 二 集中精力 手脑并用 三 课后复习 完成作业 课程考核 期末总评 平时30 考勤10 作业15 课堂表现5 期末考试70 凡主动找老师问问题和认真订正作业中的错误者都适当加分 对抄袭和作弊行为的管理 高等院校和任何学术交流都严禁任何方式的抄袭和作弊行为 学生在考试中有任何作弊行为 将根据学院 学生考试作弊行为处理规定 修订 条例由教务处给予处罚 学生作业中 需要引用他人的 必须有明确的标示 有明确标示的不视为抄袭 如果不同学生的作业有70 以上的内容雷同 或同一段里有70 相类似 或连续30个中文字词是一样的 视为抄袭 抄袭和被抄袭的作业或考试被评为零分 授课人 邓炳茂答疑时间 星期一10 30am 12 00am星期二10 00am 12 00am办公地点 基础部 综合楼414 电话 020 8781799813611484322684322QQ 190687208E MAIL dbm 课件下载地址 ftp 172 16 3 240基础部 第一篇数理逻辑 逻辑学是一门研究思维形式及思维规律的学科 可分为 辨证逻辑 以辨证法认识论的世界观为基础的逻辑学 形式逻辑 研究思维形式结构和规律的学科 是一门工具性学科 用数学的方法研究形式逻辑中推理规则的理论称为数理逻辑 即以量的形式来研究思维规律 它引入一套符号体系来表示逻辑关系 故此也称符号逻辑 辩证逻辑传统演绎逻辑逻辑学传统形式逻辑传统归纳逻辑简单逻辑方法形式逻辑现代演绎逻辑 数理逻辑 现代归纳逻辑现代形式逻辑 概率逻辑等 非标准逻辑 模态逻辑等 在数理逻辑中 它撇开研究对象的实质含义 把直观的内容抽象为形式化 而且仅仅研究其形式关系 这些形式关系是数理逻辑研究的关键 数理逻辑在计算机科学中的作用 1 在程序设计中的应用 2 在逻辑电路设计中的应用 3 在程序正确性证明中的应用 第一章命题逻辑 1 1命题与联结词1 2命题公式1 3等价公式1 4其他联结词及联结词的完备性1 5对偶式与范式1 6蕴含公式1 7推理理论1 8应用 第一章命题逻辑 1 1命题符号化及联结词主要内容 1 命题的基本概念及符号化 2 联结词 重点内容 理解命题 联接词的概念 掌握命题的符号化 1 1命题与联结词 1 1 1命题及其表示人们的思维活动是靠自然语言来表达的 然而 由于自然语言易产生二义性 用它来表示严格的推理就不合适了 为了解决这个问题 在数理逻辑中引进了一种形式化的语言 自然语言的基本单位是句子 句子分为陈述句 祈使句 疑问句和感叹句等 其中能判断对错的只有陈述句 因为只有陈述句才能够表达对事物有 肯定 或 否定 的思维方式 我们把这种 肯定 和 否定 称为真值 Truth 例如陈述句 今天下雨 这是一个判断 如果今天真的下雨 则这个判断的值为真 true 如果今天没有下雨 则这个判断的值为假 false 我们把具有这种特点的句子叫命题 它是形式语言中的基本单位 定义1 1在数理逻辑中 把能惟一判断真假的陈述句称为命题 proposition 以命题作为研究对象的逻辑称为命题逻辑 propositionlogic 命题可能为真 也可能为假 命题的真 ture 假 false 统称为命题的真值 真值为真的命题称为真命题 记作 1 也可记作 T 真值为假的命题称为假命题 记作 0 也可记作 F 判断命题的两个步骤 首先判断它是否为陈述句 再判断它是否有确定的 惟一的真值 例1 1判断下列句子哪些是命题 1 广州是广东省的省会 2 雪是黑色的 3 2100年人类将在月亮上生活 4 11 1 100 5 如果天气炎热 小梅就去游泳 6 我正在撒谎 7 请把门关好 8 这里可以坐吗 9 这幅画真好看 解 这9个句子中 7 9 都不是陈述句 因而都不是命题 1 是真命题 2 是假命题 3 的真值虽然现在还不能判断 到2100年就能判断了 因而是命题 4 在十进制中为假 在二进制中为真 当确定了进位制时其真值就确定了 因而是命题 5 是命题 真值视具体情况惟一确定 不是真就是假 6 是陈述句 但无法给出真假值 这种自相矛盾的判断称为悖论 以后再讲 从以上分析解答可以看出 命题一定是陈述句 但并非所有陈述句都是命题 如例1 1 6 命题必须有惟一确定的真值 但其真值可能受到环境 判断的标准及认识程度的限制 一时无法确定 只要能分辨真假值的判断均为命题 1 1 2命题的分类 命题可分为原子命题和复合命题 定义1 2凡不能再分解的命题称为原子命题 简单命题 由原子命题和联结词联结而成的命题称为复合命题 例1 1中 1 4 是原子命题 例1 1中 5 是复合命题 数理逻辑也称符号逻辑 它引入一套符号体系来表示命题和命题之间的联系 这个过程称为命题形式化 命题形式化可分为原子命题形式化和命题之间联系的形式化 在数理逻辑中 通常用大写英文字母或带下标的大写英文字母P Q R Pi Qj 来表示命题 用来表示命题的符号称为命题标识符 例如 P 广州是广东省的省会 Q 今天天下雨 1 1 3命题的表示方法 命题分类 简单命题 也称原子命题 与复合命题简单命题符号化用小写英文字母p q r pi qi ri i 1 表示简单命题用 1 表示真 用 0 表示假例如 令p 是有理数 则p的真值为0 q 2 5 7 则q的真值为1 定义1 3如果一个命题标识符代表任意未知命题 则称该命题标识符为命题变元 命题变项 如果一个命题标识符代表一个确定的命题 则称之为命题常元 命题变元类似代数中的变量 命题常元类似常量 但两者有着本质的区别 命题变元或常元代表的是命题元素 而变量和常量代表的是一个数值 例如 x y 5这是一个代数表达式 其中x和y是变量 不是命题变元 但该表达式也可以作为一个命题变元 假设代表该表达式的命题变元为z 当变量x和y的值确定后 表达式成为一个命题常元 命题变元z被该命题常元所取代成为命题 且命题的真值随变量x和y不同取值而变化 当用确定的命题代入命题变元时称为对命题变元的代入 1 1 4命题联结词 在命题逻辑中 主要研究的是复合命题 而复合命题是由原子命题与逻辑联结词组合而成 联结词是复合命题的重要组成部分 1 2 1否定联结词 Negation 1 2 2合取联结词 Conjunction 1 2 3析取联结词 Disjunction 1 2 4条件联结词 蕴涵联结词Conditional 1 2 5双条件联结 等值联结词Biconditional 定义1 1设P为一命题 P的否定是一个新的复合命题 称为P的否定式 记作 P 读作 非P 符号 称为否定联结词 P为真当且仅当P为假 1否定联结词 例 P 天津是一个城市 于是 P 天津不是一个城市 说明 1 属于一元 unary 运算符 2 联结词 的定义真值表如下 定义1 2设P Q为二命题 复合命题 P并且Q 或 P与Q 称为P与Q的合取式 记作P Q 符号 称为合取联结词 P Q为真当且仅当P和Q同时为真 2合取联结词 说明 1 属于二元 binary 运算符 2 联结词 的定义真值表如下 日常语言中与合取相似的联结词有 和 与 并且 既 又 不但 而且 尽管 仍然 例3 将下列命题符号化 1 李平既聪明又用功 2 李平虽然聪明 但不用功 解 设P 李平聪明 Q 李平用功 则 1 P Q 2 P Q 注意 不要见到 与 或 和 就使用联结词 例如 1 李敏和李华是姐妹 2 李敏和张华是朋友 定义1 3设P Q为二命题 复合命题 P或Q 称为P与Q的析取式 记作P Q 符号 称为析取联结词 P Q为真当且仅当P与Q中至少有一个为真 3析取联结词 2 联结词 的定义真值表如下 说明 1 属于二元 binary 运算符 日常语言中的 或者 或者 可能 可能 等词均可符号化为 说明 析取又称为逻辑 或 它可分为可兼或和不可兼或 联结词 代表的是可兼或 还有不可兼或 例如 命题 小李在看书或听音乐 这里的 或 显然是 可兼或 而命题 小李正在教室看书或正在图书馆上网 的 或 是 不可兼或 因为同一个人不可能同时出现在两个不同的地方 不可兼或指的是二者不能同时存在 例1 3将下列命题符号化 1 小李在看书或听音乐 2 小李正在教室看书或正在图书馆上网 解 1 设p 小李在看书 Q 小李在听音乐 则该命题符号化为 P Q 2 设R 小李正在教室看书 S 小李正在图书馆上网 此命题必须使用多个联结词 命题符号化为 可兼或 不可兼或 4条件联结词 蕴涵联结词 定义1 4设P Q为二命题 复合命题 如果P 则Q 若P 则Q 称为P与Q的条件命题 记作P Q 称符号 为条件联结词 并称P为前件 Q为后件 P Q为假当且仅当P为真且Q为假 联结词 的定义真值表如下 在真值表中 除了前件为真 后件为假时为假 其余都为真 对前件为真我们不难理解 因为前件为真 是前提 是达到结论的先决条件 如果前件为真 后件也为真 正符合我们的要求 若前件为真 后件为假 则不符合我们的要求 所以为假 至于前件为假不是我们考虑的对象 所以不管后件是真还是假 都有为真 这种情况逻辑学上称为 善意推定 正是因为这个 善意推定 阿基米德才会说 给我一个支点 我能把地球撬起来 这句话永远是对的 因为没有谁能给他这样一个支点 前件总为假 不管他能否把地球撬起来 他都是对的 与此类似的有 如果太阳从西边出 那末 若公鸡也能下蛋 说明 1 属于二元 binary 运算符 2 P Q表示的基本逻辑关系是 Q是P的必要条件或P是Q的充分条件 因此复合命题 只要P就Q 因为P 所以Q P仅当Q 只有Q才P 等都可以符号化为P Q的形式 例1 4将下列命题符号化 1 如果明天是晴天 那么明天举行学校运动会 2 如果明天举行学校运动会 明天必定是晴天 3 如果明天不是晴天 明天不举行学校运动会 4 如果明天不举行学校运动会 则明天不是晴天 解设P 明天是晴天 Q 明天举行学校运动会 1 原命题 2 逆命题 3 否命题 4 逆否命题 从上述例子可以看出 原命题与逆否命题意思相同 即等价 逆命题与反命题意思相同 这一点非常重要 在推理过程中 有时按原命题进行推导比较困难 而用逆否命题却可收到事半功倍的效果 定义1 5设P Q为二命题 复合命题 P当且仅当Q 称为P与Q的双条件命题 记作PiffQ或P Q 符号 称为双条件 等价 联结词 P Q为真当且仅当P Q真值相同 5双条件联结词 等价联结词 联结词 的定义真值表如下 说明 1 属于二元 binary 运算符 2 双条件命题P Q所表达的逻辑关系是 P与Q互为充分必要条件 相当于 P Q Q P 只要P与Q的真值同为1或同为0 P Q的真值就为1 否则P Q的真值为0 双条件联结词连接的两个命题之间可以没有因果关系 3 P仅当Q可译为P Q P当Q可译为Q P P当且仅当Q译为P Q 例6 分析下列命题的真值 1 2 2 4当且仅当3是奇数 P Q P 2 2 4 Q 3是奇数 2 2 2 4当且仅当3不是奇数 P Q 3 2 2 4当且仅当3是奇数 P Q 4 2 2 4当且仅当3不是奇数 P Q 例1 5符号化下列命题 1 两个三角形全等 当且仅当两个三角形对应边相等 复合命题符号化步骤 第一步 分析出各简单命题 并将它们符号化第二步 使用合适的联接词 把简单命题逐个联结起来 练习 设P表示命题 天下雪 Q