2.1命题逻辑的基本概念.ppt

1 离散数学 唐存琛刘峰武汉大学国际软件学院 2 教材与参考资料 教材 离散数学 第2版 屈婉玲 耿素云 张立昂编 清华大学出版社参考资料 离散数学 刘玉珍 刘咏梅编 武汉大学出版社 DiscreteMathematicalStructures BernardKolman FobertC BusbyandSharonRoss著PrenticeHall出版社DiscreteMathematicsandItsApplications 美 KennethH Rosen 3 课程主要内容 数理逻辑集合论图论代数系统 4 目的 意义和要求 研究内容 离散量的结构及其相互间的关系 意义 计算机科学的理论基础 目的 打基础必备的数学知识培养抽象思维能力 逻辑推理能力教学要求 内容 第1 7章 第9章 重点 第14章备选 第8 11章自学 第10 12 13章不要求作业 按时交 课后复习 概念 定理 5 学习要求 1 课堂要求 按时上课认真听讲2 课外要求 复习 每次课后 安排半个小时 认真 按时完成作业 每次课后 安排1个小时 6 学习考查方法 1 出勤率 10 不定期检查出勤情况2 作业完成情况 10 对作业完成情况进行登记3 课堂测验 期中考试 20 共5次4 期末考试 闭卷 60 7 第一篇数理逻辑第1章导论 数理逻辑的概念数理逻辑的发展简史数理逻辑的地位和作用 8 1 定义 1 1数理逻辑的概念 数理逻辑是采用数学方法研究抽象思维推理规律 形式推理 的一门科学 命题逻辑是数理逻辑的基本组成部分之一推理的基本要素是命题把命题作为基本单位来分析 符号化 研究公式间的关系 推导 演算 9 2 方法 引入一套数学符号系统来进行研究 强调推理过程中前提和结论之间的形式关系 例 A B C D4人做百米竞赛 观众甲 乙 丙预报比赛结果的名次为 甲 C第一 B第二乙 C第二 D第三丙 A第二 D第四比赛结束后发现甲乙丙每人报告的情况都各对一半 试问实际名次如何 1 引入pi qi ri si分别表示 A排名第i B排名第i C排名第i D排名第i 2 给出个命题之间的关系 1 r1 q2 r1 q2 1 2 r2 s3 r2 s3 1 3 p2 s4 p2 s4 13 通过演算规则 得出结果 10 3 内容 谓词逻辑 命题逻辑 11 4 分支 模型论 证明论 公理集合论 递归论 12 1 2数理逻辑的发展简史 创立阶段 起源阶段 完善阶段 发展历史 13 起源阶段 德国数学家 哲学家G Leibniz 1646 1716 提出建立一种普遍的符号语言 利用符号语言进行思维演算的设想 14 创立阶段 英国数学家G Bool于1847年发表 逻辑的数学分析 创建一套表示逻辑推理的基本符号以及符号的运算规律 建立了布尔代数 德国数学家G Frege于1879年在 概念的演算 一书中引进谓词符号和量词符号 创建第一个比较严格的逻辑演算系统 15 完善阶段 英国逻辑学家A N Witehead和B Russel于1910将当时的数理逻辑写入了 数学原理 中 使数理逻辑成为了一门专门的学科 20世纪30年代 由于众多科学家的努力 衍生出许多新的分支 如 直觉主义逻辑 多值逻辑 组合逻辑等 16 1 3数理逻辑的地位和作用 1 计算机科学的重要的理论基础之一 2 对数学 计算机科学 人工智能 语言学 控制论等诸多学科产生深远的影响 3 在计算机科学中的应用 软件 硬件设计 17 第2章命题逻辑 2 1命题逻辑基本概念2 2命题逻辑等值演算2 3范式2 4命题逻辑推理理论 18 2 1命题逻辑基本概念 2 1 1命题与联结词命题与真值 简单命题 复合命题 联结词 2 2 2命题公式及其分类命题公式及其赋值真值表命题公式的分类 19 2 1 1命题与联结词 1 命题及相关概念 1 命题的定义 两者必居其一且只居其一 二值逻辑 命题定义的理解 从两个方面把握这个概念 1 陈述句 2 真值唯一性 注意 真值可能目前还不知道答案 命题 一个具有真假意义的陈述句 什么是真值 只包含真 假两个值的量 T 1 真F 0 假 20 注意 1 感叹句 祈使句 疑问句都不是命题 2 陈述句中的悖论以及判断结果不唯一确定的也不是命题 21 中国的首都在北京 1 1 10请开门 x y 1明年10月1日是晴天 本命题是假的 李红既学英语又学日语 例1判断下列个自然语言是否是命题 22 2 几个基本概念真命题与假命题命题变元与命题常元 真命题 真值为真的命题假命题 真值为假的命题 若p即可以表示真命题 又可以表示假命题 则称p为命题变元 T永远表示真命题 F表示假命题 称T和F为命题常元 23 例2 真命题 假命题 真值不确定 疑问句 感叹句 祈使句 悖论 1 2 5 是命题 3 4 6 8 都不是命题 真值确定 但未知 下列句子中哪些是命题 并指出命题的真值 1 北京是中华人民共和国的首都 2 2 5 8 3 x 5 3 4 你会开车吗 5 2050年元旦北京是晴天 6 这只兔子跑得真快呀 7 请关上门 8 我正在说谎话 24 1 简单命题与复合命题 2 联结词的定义 3 联结词的优先级 2 联接词 25 1 简单命题与复合命题 简单命题 原子命题 简单陈述句构成的命题 简单命题的符号化 用p q r pi qi ri i 1 表示用 1 表示真 用 0 表示假复合命题 由简单命题通过联结词联结而成的陈述句 例如如果明天天气好 我们就出去郊游设p 明天天气好 q 我们出去郊游 如果p 则q又如张三一面喝茶一面看报设p 张三喝茶 q 张三看报 p并且q 26 2 联结词的定义 否定词 定义2 1设p为命题 复合命题 非p 或 p的否定 称为p的否定式 记作 p 符号 称作否定联结词 并规定 p为真当且仅当p为假 例如p 2是合数 p 2不是合数 p为假 p为真 27 合取词 定义2 2设p q为二命题 复合命题 p并且q 或 p与q 称为p与q的合取式 记作p q 称作合取联结词 并规定p q为真当且仅当p与q同时为真 例如p 2是偶数 q 2是素数 p q 表示的含义是2是偶素数 因为p为真 q也为真 所以p q为真 28 例3将下列命题符号化 解 记p 王晓用功 q 王晓聪明 1 p q 2 p q 3 p q 4 记r 张辉是三好生 s 王丽是三好生 r s 5 简单命题 记t 张辉与王丽是同学 1 王晓既用功又聪明 2 王晓不仅聪明 而且用功 3 王晓虽然聪明 但不用功 4 张辉与王丽都是三好生 5 张辉与王丽是同学 29 析取词 定义2 3设p q为命题 复合命题 p或q 称作p与q的析取式 记作p q 称作析取联结词 并规定p q为假当且仅当p与q同时为假 例如张三和李四至少有一人会英语设p 张三会英语 q 李四会英语 符号化为p q 30 相容或与排斥或 析取词表示的是相容或 即p和q均为真时 p q 亦为真 而与之对应的还有一个是排斥或 它表示的含义是p和q不能同时为真 例如这件事由张三和李四中的一人去做设p 张三做这件事 q 李四做这件事应符号化为 p q p q 31 例4将下列命题符号化 并指出其真值 解 记p 2是素数 q 3是素数 r 4是素数 s 6是素数 1 p r 2 p q 3 r s 4 记t 元元拿一个苹果 u 元元拿一个梨 真值 1 真值 1 真值 0 t u t u 5 记v 王晓红生于1975年 w 王晓红生于1976年 v w v w 又可形式化为v w 1 2或4是素数 2 2或3是素数 3 4或6是素数 4 元元只能拿一个苹果或一个梨 5 王晓红生于1975年或1976年 32 蕴涵词 定义2 4设p q为二命题 复合命题 如果p 则q 称作p与q的蕴涵式 记作p q 并称p是蕴涵式的前件 q为蕴涵式的后件 称作蕴涵联结词 并规定 p q为假当且仅当p为真且q为假 例如如果明天天气好 我们就出去郊游设p 明天天气好 q 我们出去郊游 形式化为p q 33 蕴涵词的其它表述方式 p q的逻辑关系 q为p的必要条件 p为q的充分条件 如果p 则q 的多种表述方式 若p 就q只要p 就qp仅当q只有q才p除非q 才p除非q 否则非p当p为假时 p q为真 不管q为真 还是为假 34 例5设p 天冷 q 小王穿羽绒服 将下列命题符号化 注意 p q与 q p等值 真值相同 p q p q q p或p q p q q p q p p q或q p q p 1 只要天冷 小王就穿羽绒服 2 因为天冷 所以小王穿羽绒服 3 若小王不穿羽绒服 则天不冷 4 只有天冷 小王才穿羽绒服 5 除非天冷 小王才穿羽绒服 6 除非小王穿羽绒服 否则天不冷 7 如果天不冷 则小王不穿羽绒服 8 小王穿羽绒服仅当天冷的时候 35 等价词 定义2 5设p q为命题 复合命题 p当且仅当q 称作p与q的等价式 记作p q 称作等价联结词 并规定p q为真当且仅当p与q同时为真或同时为假 p q的逻辑关系 p与q互为充分必要条件例如这件事张三能做好 且只有张三能做好设p 张三做这件事 q 这件事做好了形式化为 p q 36 例6求下列复合命题的真值 1 0 1 1 0 1 2 2 4当且仅当3 3 6 2 2 2 4当且仅当3是偶数 3 2 2 4当且仅当太阳从东方升起 4 2 2 5当且仅当美国位于非洲 5 f x 在x0处可导的充要条件是它在x0处连续 37 分析找出简单命题 用字母表示简单命题 用联接词联接命题符号 命题符号化的一般规则 38 分析找出简单命题 用字母表示简单命题 用联接词联接命题符号 解令p 我上街q 我累r 我去书店看看则可符号化为 p q r 例7将下列命题符号化 如果我上街并且我不累 我就去书店看看 简单命题 我上街 我累 我去书店看看 39 例8试将下列命题符号化 如果你不看电影 那么我也不看电影小王一边吃饭 一边看书 解 1 设p 你看电影 q 我看电影 则 p q 2 设p 小王吃饭 q 小王看书 则 p q 40 3 联结词的优先级 联结词优先级 同级按从左到右的顺序进行 41 例 分析下列各命题的真值 1 2 2 4当且仅当3是奇数 2 2 2 4当且仅当3不是奇数 3 2 2 4当且仅当3是奇数 4 2 2 4当且仅当3不是奇数 例 将下列命题符号化 1 小王是游泳冠军或者百米赛跑冠军 2 小王现在在宿舍或者在图书馆 3 选小王或者小李中的一人当班长 4 如果我上街 我就去书店看看 除非我很累 课堂练习 1 42 课堂练习 2 例 将下列命题符号化 1 李平既聪明又用功 2 李平虽然聪明 但不用功 3 李平不但聪明 而且用功 4 李平不是不聪明 而是不用功 例 将下列命题符号化 1 只要不下雨 我就骑自行车上班 2 只有不下雨 我才骑自行车上班 3 若2 2 4 则太阳从东方升起 4 若2 2 4 则太阳从东方升起 43 2 1 2合式公式及其分类 1 命题语言的字母表 2 合式公式的基本概念3 真值表4 合式公式的分类 44 1 命题语言的字母表 命题语言的字母表 命题常元 T F 或1 0 命题变元 p1 p2 pn联接词 辅助符号 45 1 合式公式 命题公式 公式 的定义 定义2 6合式公式递归定义如下 1 单个命题常项或变项是合式公式 并称作原子合式公式 2 若A是合式公式 则 A 也是合式公式 3 若A B是合式公式 则 A B A B A B A B 也是合式公式 4 只有有限次地应用 1 3 形成的符号串才是合式公式 2 合式公式的基本概念 说明 1 元语言符号与对象语言符号 2 在不影响运算顺序时 括号可以省去例如0 p p q p q p r p q r p q r 46 2 合式公式的层次 定义2 7 1 单个命题变项或命题常项是0层公式 2 称A是n 1 n 0 层公式是指下面情况之一 a A B B是n层公式 b A B C 其中B C分别为i层和j层公式 且n max i j c A B C 其中B C的层次及n同 b d A B C 其中B C的层次及n同 b e A B C 其中B C的层次及n同 b 例如p0层 p1层 p q2层 p q r3层 p q r r s 4层 47 3 公式的赋值 定义2 8设p1 p2 pn是出现在公式A中全部的命题变项 给p1 p2 pn指定一组真值 称为对A的一个赋值或解释 使公式为真的赋值称作成真赋值 使公式为假的赋值称作成假赋值 说明 1 赋值记作 1 2 n 其中 i 0或1 诸 i之间不加标点符号 2 通常赋值与命题变项之间按下标或字母顺序对应 即 当A的全部命题变项为p1 p2 pn时 给A赋值 1 2 n是指p1 1 p2 2 pn n 当A的全部命题变项为p q r 时 给A赋值 1 2 3 是指p 1 q 2 r 3 48 实例 例8公式A p1 p2 p3 p1 p2 000是成真赋值 001是成假赋值公式B p q r000是成假赋值 001是成真赋值 49 3 真值表 真值表 命题公式在所有可能的赋值下的取值的列表 含n个变项的公式有2n个赋值