离散数学课件PPT课件

1 49 1 60 离散数学DiscreteMathematics 计算机科学与工程学院袁夏 E mail yxlucker 2 49 课程说明 课程类型 计算机科学专业基础课学分 4 5学分教学方式 理论教学考核方式 闭卷笔试成绩评定 平时成绩20 期末成绩80 教材与教学参考书 1 离散数学 第2版 朱保平 金忠等 北京理工大学出版社 2014 2 离散数学概念 题解与自测 朱保平 金忠等 北京理工大学出版社 2009 3 49 课件与作业参考答案请进入邮箱文件中心下载用户名 cs lisanshuxue 密码 lisanshuxue课件每次课后上传更新 作业参考答案不定期上传更新 4 49 5 49 离散数学 研究离散数量关系和离散结构数学模型的数学分支的统称 古代数学 整数 整数的比近代数学 连续的数量概念 实数 处理连续数量关系的数学 微积分 Discrete 6 49 对计算机专业系统知识的辐射作用 胡慧君 刘茂福 武汉科技大学计算机科学与技术学院 计算机光盘软件与应用 188 189 2013 7 49 主要内容 数理逻辑 1 5 集合论 6 8 图论 9 10 代数 11 12 没有预修课程 学习数理逻辑时会涉及一点中学阶段学习的集合知识 8 49 数理逻辑 数学化的逻辑学 德国G W Leibniz 1626 1716 把数学引入形式逻辑 明确提出用数学方法研究推理 英国G Boole 1815 1864 等创立了逻辑代数 1847年Boole实现了命题演算 德国G Frege 1848 1925 在1879年建立了第一个谓词演算系统 英国B Russell 1872 1970 等从逻辑学的基本法则建立了自然数理论 实数理论及解析几何学等 英国AlanM Turing 1912 1954 在1936年提出一种抽象计算模型 数学逻辑机 引入图灵机 一种理想的计算机 9 49 数理逻辑的学习 我现在年纪大了 搞了这么多年的软件 错误不知犯了多少 现在觉悟了 我想 假如我早年在数理逻辑上好好下点工夫的话 我就不会犯这么多的错误 不少东西逻辑学家早就说过了 可是我不知道 要是我能年轻二十岁的话 我就去学逻辑 Edsger W Dijkstra1972年Turing奖获得者 1930 2002 带权图的最短通路算法 10 49 数理逻辑 第一章命题演算基础第二章命题演算的推理理论第三章谓词演算基础第四章谓词演算的推理理论第五章递归函数论 11 49 大数据技术 情感分类 现在是晚上十一点 天很暖 如果我考试通过了 那么我很快乐 如果我快乐 那么阳光灿烂 并非如果只有考试通过才能心情好那么我心情好 QQ心情谜语 12 49 一 命题定义 凡是可以判断真假的陈述句称为命题 13 49 例 下列句子都是命题吗 雪是白的 雪是黑的 好大的雪啊 8大于12 1 101 110 14 49 例 下列句子都是命题吗 21世纪末 人类将住在月球 大于2的偶数可表示成两个素数之和 X 0 如果x大于3 则x2大于9 我正在说谎 悖论 15 49 命题的真假问题 在数理逻辑的学习中 不能去纠缠各种具体命题的真假问题 而是将命题当成数学概念来处理 看成一个抽象的形式化的概念 把命题定义成非真必假的陈述句 16 49 带联结词的命题 今晚我看书 今晚我玩网络游戏 今晚我不看书 今晚我不玩网络游戏 今晚我不看书 我玩网络游戏 今晚我看书 或者我玩网络游戏 否定 并且 或者 17 49 二 原子命题和复合命题 原子命题 不可剖开或分解为更简单命题的命题 也称为简单命题 复合命题 由原子命题利用联结词构成的命题 约定用大写字母表示 18 49 复合命题例子 1 并非雪是白的 2 今晚我看书或者去看电影 3 如果天气好 那么我去接你 4 偶数a是质数 当且仅当a 2 a是常数 5 2是偶数且3也是偶数 6 你去了学校 我去了工厂 19 49 三 命题变元 当P表示任意命题时 称P为命题变元 20 49 命题变元的变域 一个命题变元P的可能取值有两种情况 真T 或假F P的变域 T F 两个命题变元P Q的可能取值有几种情况 怎么表达这些情况 P Q的变域 21 49 1 1 2联结词 否定词 合取词 析取词 蕴含词 等价词 22 49 P 读作 非P 是指命题 P的否定 P PTFFT 真值表 例P 雪是黑色的 P 并非雪是黑色的 雪不是黑色的 23 49 否定联结词使用的原则 将真命题变成假命题 将假命题变成真命题 但这并不是简单的随意加个不字就能完成的 例P 这些人都是学生 P 这些人不都是学生 这些人都不是学生 24 49 P Q 读作 P合取Q 是指命题 P并且Q 例P 今天刮风 Q 今天下雨 P Q 今天刮风 下雨 真值表 25 49 P Q 读作 P析取Q 是指命题 P或者Q PQP QTTTTFTFTTFFF 例P 他会英语 Q 他会法语 P Q 他会英语或者法语 26 49 可兼的 或 不可兼的 或 PQP QTTTTFTFTTFFF 他会英语或法语 27 49 P Q 读作 P蕴含Q 是指命题 如果P 则Q 例如果1 1 3 则雪是黑的 PQP QTTTTFFFTTFFT 真值表 28 49 注1 前件为假时 蕴含式命题为真 如果蕴含前件P是假命题 那么不管Q是什么命题 命题P Q在逻辑中都被认为是真命题 29 49 注2 蕴含式前件 后件可以毫不相关 在日常语言中 如果 则 所联结的句子之间表现的是一种因果关系 但在数理逻辑中 尽管说前件蕴涵后件 但两个命题可以是毫不相关的 例P 我心情好 Q 1 2 P Q 如果我心情好 那么1 2 30 49 灵活叙述蕴含词的例子 设R 天下雨 H 我回家 试表示下列命题 只要天下雨 我就回家 只有天下雨 我才回家 除非天下雨 否则我不回家 仅当天下雨 我才回家 R H H R或 R H 可以将蕴含看作充分条件 如果A是充分条件的前件 B是后件 那么A蕴含B的意思就是有A必有B 31 49 P Q 读作 P等价于Q 是指命题 P当且仅当Q PQP QTTTTFFFTFFFT 例P 2 3 5Q e是无理数P Q 2 3 5的充要条件是e是无理数 32 49 是否命题 是否复合命题 例Tom和John是兄弟 例如果x 0 则x2 0 例若两圆面积相等 则它们的半径相等 反之亦然 33 49 真值函项的定义 以真假为定义域并以真假为值域的函数 映射 T F T F 2 T T T F F T F F 34 49 一元真值函项 一元联结词 Pf0 P f1 P f2 P f3 P TTTFFFTFTF 永真 恒等 否定 P 永假 35 49 二元真值函项 二元联结词 f4为析取 f2为蕴含 f8为等价 f11为合取 f14为或非 f1为与非 36 49 三元联结词共有多少个 28 37 49 1 1 3合式公式 合式公式为如下定义的式子 简称为公式 任何命题变元均是公式 如果P为公式 则 P为公式 如果P Q为公式 则P Q P Q P Q P Q为公式 当且仅当经过有限次使用 所组成的符号串才是公式 否则不为公式 Wellformedformulae 38 49 n元公式 有n个不同的命题变元的公式 例 39 49 优先级约定 优先级相同 比其它联结词有更高的优先级括号 内的运算优先 40 49 命题符号化 分析出简单命题 符号化用联结词联结简单命题 例将下述命题符号化 如果只有懂得希腊文才能了解柏拉图 那么我不了解柏拉图 解 令P表示 我懂得希腊文 Q表示 我了解柏拉图 则原句符号化为 Q P Q 41 49 真值 例令P 北京比天津人口多 Q 2 2 4 R 乌鸦是白色的 求下列公式的真值 1 Q R P R 2 P R P R 42 49 真值表及其应用 并非如果只有考试通过就能心情好那么我心情好 我心情不好 43 49 真值表及其应用 并非如果只有考试通过才能心情好那么我心情不好 我心情好 并且考试通过 44 49 1 2真假性 定义 设n元公式 中所有的不同的命题变元为P1 P2 Pn 问题 n元公式 有多少个完全解释 1 2 1解释 如果对每个命题变元均给予一个确定的值 则称对公式 给了一个完全解释 如果仅对部分变元给予确定的值 则称对公式 给了一个部分解释 45 49 例考察公式 P Q R 46 49 成真解释与成假解释 定义 对于任何公式 凡使得 取值真的解释 均称为 的成真解释 凡使得 取值假的解释 均称为 的成假解释 47 49 例考察公式 P Q R 48 49 永真公式与永假公式 定义 如果一个公式的所有完全解释 例 均为成真解释 则称该公式为永真公式或称为重言式 均为成假解释 则称该公式为永假公式或称为予盾式 49 49 可满足公式与非永真公式 定义 如果一个公式 例P Q可满足公式 非永真公式P Q可满足公式 非永真公式 存在成真解释 则称该公式为可满足公式 存在成假解释 则称该公式为非永真公式 50 60 1 2 2等价公式 逻辑等值 等价 的概念几组重要的等值 等价 公式利用等值 等价 公式 对公式进行化简 以求解公式的成真解释 成假解释 51 60 逻辑相等 定义给定两个公式 和 设P1 P2 Pn为 和 的所有命题变元 那么 和 有2n个解释 如果对每个解释 和 永取相同的真假值 则称 和 是逻辑等价 等值 相等 的 记为 真值表相同 52 60 例问 P P P 从真值表 可以看出 P P P 考察真值表如下 53 60 等值公式 54 60 等值公式 55 60 等值变换 否定深入公式 56 65 57 60 原命题 逆命题 否命题 逆否命题 设原命题为蕴含式 P Q 则逆命题为 Q P 否命题为 P Q 逆否命题为 Q P 于是 P Q Q PQ P P Q 真值表法等值变换法 58 60 例判断下列公式的类型Q P Q P 解 Q P Q P Q P Q P Q P Q P Q P P Q P P Q T T所以 它是永真的 59 60 例判断下列公式的类型 P P Q Q R 解 P P Q Q R T F R F R F所以 它是永假的 60 60 例 Q P Q P Q Q 记P 我考试通过 Q 我心情好 并非如果只有考试通过才能心情好那么我心情好 如果只要考试通过就能心情好那么我心情不好 也可以利用等值公式证明 61 60 成真解释和成假解释的求解方法 1 否定深入 即把否定词一直深入至命题变元上 2 部分解释 选定某个出现次数最多的变元对它作真或假的两种解释从而得公式 3 化简 4 依次类推 直至产生公式的所有解释 前提是公式中没有蕴含词 等价词 62 60 例 p7 试判定公式 P Q Q P R 的永真性和可满足性 解 对P F进行解释并化简 原式 F Q Q F R F Q R Q R当Q T时 原式 T R R 于是 当R T时 原式 F 当R F时 原式 T 因此 存在成真解释 P Q R F T F 存在成假解释 P Q R F T T 故公式可满足但非永真 63 60 例试求下列公式的成真解释和成假解释 P Q Q R P 解 当P T时 原式 T Q Q R T Q Q R Q R当P F时 原式 F Q Q R F T Q F Q由上可知 公式不是永真公式 是可满足的 并且 成真解释为 P Q R T F F F T 成假解释为 T T T T F