01-命题逻辑-11~13.ppt

2020年3月14日星期六 有一逻辑学家误入某部落 被拘于牢狱 酋长欲放行 他对逻辑学家说 今有两门 一为自由 一为死亡 你可任意开启一门 为协助你脱逃 今加派两名战士负责解答你所提的任何问题 惟可虑者 此两战士中一名天性诚实 一名说谎成性 今后生死由你自己选择 逻辑学家沉思片刻 即向一战士发问 然后开门从容离去 逻辑学家手指一门问身旁一名战士说 这扇门是死亡门 他 指另一名战士 将回答 是 对吗 2020年3月14日星期六 P 被问战士是诚实人 Q 被问战士的回答是 是 R 另一战士回答的是 是 S 这扇门是死亡门 S P Q P Q P P Q Q S的真值总与Q的真值相反 当被问人回答 是 时 此门是生门当被问人回答 否 时 此门是死门 2020年3月14日星期六 逻辑 逻辑 是研究思维形式及思维规律的科学 也把它称为研究推理的科学 它分为 辨证逻辑 是研究人的思维中的辩证法 例如 用全面的和发展的观点观察事物 具体问题具体分析 实践是检查事物正误的唯一标准 等等 形式逻辑 是研究人的思维的形式和一般规律 在本学科 我们只关心形式逻辑 思维的形式结构包括了概念 判断和推理之间的结构和联系 形式逻辑主要研究推理 推理 就是由若干个已知的判断 前提 推出新的判断 结论 的思维过程 概念是思维的基本单位 通过概念对事物是否具有某种属性进行肯定或否定的回答 这就是判断 由一个或几个判断推出另一判断的思维形式 就是推理 2020年3月14日星期六 推理 推理分为以下几种 类比推理 由个别事实推出个别结论 如 地球上有空气 水 地球上有生物 火星上有空气 水 火星上有生物 归纳推理 由若干个别事实推出一般结论 如 铜能导电 铁能导电 锡能导电 铅能导电 一切金属都导电 演绎推理 由一般规律推出个别事实 形式逻辑主要是研究演绎推理的 2020年3月14日星期六 演绎推理 演绎推理举例 例1 如果天下雨 则路上有水 一般规律 天下雨了 个别事实 推出结论 路上有水 个别结论 例2 大前提 所有金属都导电 一般规律 小前提 铜是金属 个别事实 推出结论 铜能导电 个别结论 不能仅停留在文字表面 否则无法与机器沟通 若停留在文字表面 如 下雨换成下雪 铜换成铁 机器该如何处理 2020年3月14日星期六 数理逻辑 数理逻辑是用数学的方法研究形式逻辑 所谓数学方法 主要是指引进一套符号体系的方法 因此数理逻辑又称为符号逻辑现代数理逻辑有四大分支 证明论 模型论 递归论 公理化集合论它们共同的基础 命题逻辑 Ls 命题演算 谓词逻辑 Lp 谓词演算 2020年3月14日星期六 命题逻辑 命题逻辑示例 如果天下雨 则路上有水 一般规律 天下雨了 个别事实 推出结论 路上有水 个别结论 设P表示 天下雨 设Q表示 路上有水 设 表示 如果 则 以上的推理过程表示为 前提1 P Q 如果天下雨 则路上有水 前提2 P 天下雨了 结论 Q 路上有水 2020年3月14日星期六 谓词逻辑 谓词逻辑示例 大前提 所有金属都导电 一般规律 小前提 铜是金属 个别事实 推出结论 铜能导电 个别结论 设M x x是金属 设C x x能导电 设 x表示 所有的x 设a 表示铜 以上的推理过程表示为 大前提 x M x C x 所有金属都导电 小前提 M a 铜是金属 结论 C a 铜能导电 2020年3月14日星期六 命题逻辑的应用 给后继课程 编译原理 人工智能 数字逻辑等提供必要的数学基础 第一章命题逻辑 2020年3月14日星期六 命题逻辑 命题逻辑研究由命题为基础单位构成的前提和结论之间的可推导关系它是谓词逻辑的基础本章的主要内容 命题 联结词 命题公式等价式 蕴涵式范式 主范式推理理论 2020年3月14日星期六 第一节命题与联结词 第一节命题与联结词一 命题的概念所谓命题 Proposition 是指具有非真必假的陈述句 疑问句 感叹句 祈使句都不能判断其真假 故而都不是命题 命题仅有两种可能的真值 truthvalue 真 true 用T或1表示 假 false 用F或0表示 因此 命题逻辑也称为二值逻辑 陈述句二值逻辑 2020年3月14日星期六 命题 命题的真假是具有客观性质的 而不是由人的主观决定的 命题是一个真或假的语句 但是不能既真又假 若一个命题的真值为真 称该命题为真命题 用T或1表示 若一个命题的真值为假 称该命题为假命题 用F或0表示 2020年3月14日星期六 命题 注意 命题有真假 并不意味着现在就能确定其为真还是为假 而是指它具有能够唯一确定的真假值这一性质 例如 地球外的星球上存在生物 2020年3月14日星期六 命题 例1 1 判断下面的语句是否为命题 如果是命题 是真命题还是假命题 今天下雪 明天会刮风吗 x y 42是偶数 而3是奇数 陈胜起义那天 杭州下雨了 这真是太好了 假命题 不是命题 不是命题 真命题 是命题 未知真假 不是命题 2020年3月14日星期六 命题 你去哪里 给我一只笔 我正在说谎 1 1 10金星的表面温度是800oC 本命题是假的 不是命题 不是命题 悖论 不是命题 是命题 在二进制条件下是真命题 其他进制条件下是假命题 假命题 悖论 不是命题 465oC 485oC 2020年3月14日星期六 悖论 悖论 paradox 其字面意思为 荒谬的理论或自相矛盾的话 从逻辑上看 悖论性的语句具有这样的特征 如果假定这个语句为真 那么会推出这个语句为假 反之 如果假定这个语句为假 又会推出这个语句为真 说它对也不是 不对也不是 真是左右为难 2020年3月14日星期六 悖论 2020年3月14日星期六 命题 命题应当是有客观真值的 但是命题的真值会因时 因地 因人而异 现在是21世纪 中国的首都是北京 今天这里下雨了 我是女性 从今天的角度上讲 这是真命题从上世纪的角度上讲 这是假命题 目前讲 这是真命题如果从唐朝的角度讲 这是假命题 对于有些地方而言 这是真命题对于有些地方而言 这是假命题 对于我来讲 这是真命题对于男性来讲 这是假命题 2020年3月14日星期六 命题 命题分为两类 如果一个陈述句 再也不能分解成更小的语句 由它构成的命题称为原子命题 或本原命题 原子命题是命题逻辑的基本单位 用大写英文字母P Q R 或Pi Qi Ri表示例如 用P表示 今天是星期一 记为P 今天是星期一 2020年3月14日星期六 命题 由原子命题 命题联结词和圆括号组成复合命题 例如 P 明天下雨 Q 明天下雪可利用联结词 不 并且 或者 等分别构成新的命题 明天不下雪 非Q 明天下雨并且明天下雪 P并且Q 明天下雨或者明天下雪 P或者Q 2020年3月14日星期六 命题联结词 下面我们来讨论由已有命题产生新命题的方法 这些方法在1854年 曾由英国数学家乔治 布尔 1815 1864 在他的 TheLawsofThought 一书中讨论过 许多数学陈述都是组合一个或多个命题而来 称为复合命题的新命题 是由已有的命题用逻辑运算符组合而来的 复合命题的 真 或 假 只与所含的原子语句的真值有关 与他们的含义无关 2020年3月14日星期六 命题联结词 二 命题联结词命题联结词就是命题演算中的运算符 也叫逻辑运算符 常用的有以下5个 否定词 设P为命题 命题 非P 称为P的否定式复合命题 记做 P 称为否定联结词 P为真 当且仅当P为假 2020年3月14日星期六 命题联结词 否定词 在学习命题公式之前 我们先来认识一下真值表 定义运算符的真值表 指明如何用运算对象的真值 来决定一个应用运算符的命题的真值 真值表左边列出运算对象的真值的所有组合 结果命题的真值列在最右边的一列 P的真值表为 2020年3月14日星期六 命题联结词 否定词 例1 2 P 4是质数 P表示什么 P 4不是质数 或者 4是质数 不是这样 Q 这些都是男同学 Q表示什么 Q 这些不都是男同学 或者 这些都是男同学 是错误的 不要翻译成 这些都不是男同学 2020年3月14日星期六 命题联结词 合取词 设P Q是两个命题 命题 P并且Q 称为P和Q的合取式复合命题 记做 P Q 也读作 P与Q 称为合取联结词 P Q为真 当且仅当P和Q同时为真 P Q的真值表为 合取是对称的 即给P和Q指派真值 P Q和Q P的真值相同 2020年3月14日星期六 命题联结词 合取词 例1 3 P 王华的成绩很好 Q 王华的品德很好P Q 王华的成绩很好 并且品德很好P 今天天晴 Q 三加三等于六 P Q表示什么 P Q 今天天晴 并且三加三等于六能将命题 汤姆和杰克是亲兄弟 符号化为 P Q 的形式吗 不能 这本身就是一个原子命题 常把合取 与 用于具有某种关系的两个命题之间 但是 在逻辑学中 则不然 完全允许用两个相互无关系的原子命题 生成新的命题 2020年3月14日星期六 命题联结词 析取词 设P Q是两个命题 命题 P或者Q 称为P和Q的析取式复合命题 记做 P Q 称为析取联结词 P Q为假 当且仅当P和Q同时为假 P Q的真值表为 2020年3月14日星期六 命题联结词 析取词 例1 4 P 今晚我写字 Q 今晚我看书 P Q表示什么 P Q 今晚我写字或者看书P 今年是闰年 Q 今年她生孩子 P Q表示什么 P Q 今年是闰年或者今年她生孩子 2020年3月14日星期六 命题联结词 析取词 通常语言中的 或者 有两种含义 可兼或如前面的例子 今晚我写字或看书 不排除今晚 我 既看书又写字排斥或例如 人固有一死 或重于泰山 或轻于鸿毛 其中的 或 表示非此即彼 不可兼得析取词 表示的是可兼或 排斥或 将用 表示 特例 他昨天做了二十或三十道题 此例中的 或 只表示了习题的近似数目 不能用联接词析取表达 它是个原子命题 2020年3月14日星期六 命题联结词 蕴涵词 设P Q是两个命题 命题 P蕴涵Q 称为P和Q的蕴涵式 条件式 复合命题 记做 P Q 读作 如果P 那么Q P叫做 前件 前提 假设 Q叫做 后件 结论 称为蕴涵 蕴含 联结词 或条件联结词 P Q为假 当且仅当P为真而Q为假 2020年3月14日星期六 命题联结词 蕴涵词 P Q的真值表为 自然语言中对 如果 则 这样的语句 当前提为假时 结论不管真假 这个语句的意义 往往无法判断 而在条件命题中 规定为 善意的推定 即前提为F时 条件命题的真值都为T 2020年3月14日星期六 命题联结词 蕴涵词 例1 5 P 天不下雨 Q 草木枯黄 P Q表示什么 P Q 若天不下雨 则草木枯黄 这种前提和结论之间有因果或实质关系的蕴涵式 叫做形式蕴涵如 P G是正方形 Q G四边相等P Q 若G是正方形 则G四边相等 2020年3月14日星期六 命题联结词 蕴涵词 若前提和结论之间并不需要因果或实质关系存在 这种蕴涵式 叫做实质蕴涵如 P 桔子是黄色的 Q 大地是不平的P Q 若桔子是黄色的 则大地是不平的蕴涵词 表示的是实质蕴涵 并不在乎前提和结论之间是否有实质上的关系 2020年3月14日星期六 命题联结词 蕴涵词 P Q 可以用多种方式表述 若P 则QP是Q的充分条件Q是P的必要条件 2020年3月14日星期六 只要 就 只要你不安心工作 工作就做不好 命题联结词 只要 就为充分条件 即有这个条件就会产生后一个分句所指出的结果 但并不排除在别的条件下也会产生这样的结果 强调的是充分条件 但不是到达结果的唯一条件 A B 2020年3月14日星期六 只有 才 只有年满18岁 才有选举权 命题联结词 只有 才为必要条件 即缺少了这个条件就不能产生后面分句指出的结果 但有了所说的条件 也不一定就能产生所说的结果 还要看是否具备其它条件 A B 2020年3月14日星期六 命题联结词 只有共产党 才能救中国P 共产党Q 救中国 命题可以表示为 Q P只要到了高三 大家的学习生活就会变得特别紧张P 到了高三 Q 大家的学习生活就会变得特别紧张 命题可以表示为 P Q 2020年3月14日星期六 如果 就 必须 才 除非 否则 命题联结词 2020年3月14日星期六 命题联结词 蕴涵词 例1 6 用蕴涵联结词表示下列命题如果这门课的材料无趣 习题也不难 那么这门课不会让人喜欢 P 这个材料有趣 Q 习题很难 R 这门课让人喜欢 这命题可以表示为 P Q R 2020年3月14日星期六 命题联结词 我今天进城 仅当不下雨P 我今天进城 Q 今天下雨 命题可以表示为 Q PP Q仅当你走 我将留下P 你走 Q 我留下 命题可以表示为 P QQ P 符号化时 P Q后的语句应该主谓完整 不要写成P 进城Q 下雨 2020年3月14日星期六 命题联结词 除非是冬天 否则不会下雪 P 现在是冬天 Q 现在下雪 命题可以表示为 P QQ P除非天气好 我才骑自行车上班 P 天气好 Q 我骑自行车上班 命题可以表示为 Q P P Q 2020年3月14日星期六 命题联结词 等值词 设P Q是两个命题 命题 P等值于Q 称为P和Q的等值式 双条件式 复合命题 记做 P Q 读作 P当且仅当Q 或 P等价Q 称为等值联结词 或双条件联结词 P Q为真 当且仅当P和Q有相同的真值 2020年3月14日星期六 命题联结词 等值词 P Q的真值表为 2020年3月14日星期六 命题联结词 等值词 例1 7 将下面命题符号化这个材料很有趣 意味着这些习题很难 反之亦然 P 这个材料很有趣 Q 这些习题很难 P Q假如上午不下雨 我将去看电影 否则就在家中读书 P 上午下雨 Q 我去看电影 R 我在家中读书 P Q P R 2020年3月14日星期六 命题联结词 一个数是素数 当且仅当它只能被1和其自身整除 P 一个数是素数 Q 一个数能被1整除R 一个数能被自身整除 S 一个数能被1和其自身以外的数整除 P Q R S 2020年3月14日星期六 命题联结词 使用以上的五个基本联结词 可以将一些语句翻译成逻辑式 翻译时为了减少圆括号 一般不用其他括号 的使用 我们作以下的约定 运算符结合能力的强弱顺序为 相同的运算符 按从左到右的次序计算时 括号可以省略最外层的圆括号可以省去 2020年3月14日星期六 命题联结词 例1 8 设P 他富有 Q 他幸福 将下面命题符号化 如果他富有 那么他不幸福 他既不富有 也不幸福 要幸福就必须贫穷贫穷就不幸福 P Q P Q P Q P Q Q P 2020年3月14日星期六 命题联结词 将下面命题符号化说小学生编不了程序 或说小学生用不了计算机 那是不对的 P 小学生会编程序 Q 小学生会用计算机 P Q P Q若不是他生病或出差了 我是不会同意他不参加学习的 P 他生病了 Q 他出差了 R 我同意他不参加学习 P Q R P Q R 当且仅当 2020年3月14日星期六 命题联结词 例1 9 设P 明天下雨 Q 明天下雪 R 我去学校 将下面命题符号化 如果明天不是雨夹雪 则我去学校 如果明天不下雨 并且不下雪 则我去学校 如果明天下雨或下雪 我不去学校明天 我将雨雪无阻 一定去学校 当且仅当明天不下雨而且不下雪时 我去学校 2020年3月14日星期六 命题联结词 P 明天下雨 Q 明天下雪 R 我去学校 如果明天不是雨夹雪 则我去学校 P Q R如果明天不下雨 并且不下雪 则我去学校 P Q R如果明天下雨或下雪 我不去学校 P Q R 2020年3月14日星期六 命题联结词 P 明天下雨 Q 明天下雪 R 我去学校 明天 我将雨雪无阻 一定去学校 P Q R P Q R P Q R P Q R 或 P Q P Q P Q P Q R或 P P Q Q R或 R当且仅当明天不下雨而且不下雪时 我去学校 P Q R 2020年3月14日星期六 命题联结词 例1 10将下面命题符号化林芳和林芬都在做作业P 林芳在做作业 Q 林芬在做作业P Q林芳和林芬是姐妹 这是一个原子命题 可以表示为 P 林芳和林芬是姐妹 2020年3月14日星期六 第二节命题变元与合式公式 第二节命题变元与合式公式一 命题常元与命题变元若P代表一个真值已经指定的具体命题 则称P为命题常元 若P代表一个真值未指定的任意命题 则称P为命题变元 显然 命题变元不是命题 只有用一个特定的命题取代才能确定它的真值 2020年3月14日星期六 命题变元 定义 以真值真 或T 1 假 或F 0 为其域的变元 称为命题变元真值真 或T 1 假 或F 0 称为命题常元 2020年3月14日星期六 合式公式 二 合式公式通常把含有命题变元的断言 陈述句 称为命题公式 但不是所有由命题变元 联结词和小括号组成的字符串都是命题公式 由下面定义归纳命题公式的结构 称为合式公式 2020年3月14日星期六 合式公式 定义 单个的命题变元和命题常元称为原子命题公式 简称原子公式单个原子公式是合式公式若A是一个合式公式 则 A 也是一个合式公式若A B是合式公式 则 A B A B A B A B 也是合式公式只有有限次使用2 4 产生的公式才是合式公式 2020年3月14日星期六 合式公式 我们通常用P Q R等表示原子公式 用A B C等表示命题公式 命题公式的真假值一般是不确定的 当命题公式中的所有命题变元代以命题时 命题公式就变成命题 在不产生混乱的情况下 命题公式也叫作命题 2020年3月14日星期六 合式公式 按照上面定义 来说明 P P Q 是合式公式 P是合式公式Q是合式公式因此 P Q 是合式公式因此 P P Q 是合式公式 2020年3月14日星期六 合式公式 按照上面定义 下列字符串不是合式公式 P Q P Q QPQ R P Q 2020年3月14日星期六 合式公式 按照上节我们给出的约定 运算符结合能力的强弱顺序为 相同的运算符 按从左到右的次序计算时 括号可以省略最外层的圆括号可以省去我们可以省略一些括号 因此认为 P Q是合式公式 2020年3月14日星期六 公式真值表 三 公式真值表设A为含有命题变元P1 P2 Pn的命题公式 给P1 P2 Pn指定一组真值 称为对A的一个赋值或真值指派 定义 对公式中每一个命题变元的每一种可能的真值指派 以及由它们所确定的公式的真值所列成的表 称为公式的真值表 2020年3月14日星期六 公式真值表 定义 若B是公式A的一部分 且B为公式 则称B是A的子公式 例1 11 P Q P 的真值表为 2020年3月14日星期六 公式真值表 两个公式 若具有相同的真值 称它们是逻辑等价命题 例1 12求证 P Q与P Q P Q是等价命题 证毕 2020年3月14日星期六 公式真值表 若某公式种含有n个命题变元 则该公式会有多少个真值指派 公式中含有n个命题变元 每个变元都可以被赋值为T或F所以 含有n个命题变元的公式 会有2n个真值指派 2020年3月14日星期六 第三节公式分类与等价公式 第三节公式分类与等价公式一 公式分类定义 设A为任意公式若对应每一个指派 A的值均为真称A为重言式 或永真式 若对应每一个指派 A的值均为假称A为矛盾式 或永假式 若A既不是重言式 也不是矛盾式称A为偶然式 2020年3月14日星期六 第三节公式分类与等价公式 第三节公式分类与等价公式一 公式分类定义 设A为任意公式 若至少存在一个指派 使A的值为真称A为可满足式若至少存在一个指派 使A的值为假称A为非永真式 2020年3月14日星期六 重言式的特点 重言式有以下特点重言式的否定是矛盾式 矛盾式的否定是重言式 重言式和矛盾式只研究其中之一即可两个重言式的合取式 析取式 条件式 双条件式都是重言式 由简单的重言式可以构造出复杂的重言式由重言式使用公认的规则 可以产生许多有用的等价式和蕴涵式 2020年3月14日星期六 公式的判定 判定某公式属于哪种类型 重言式 矛盾式 偶然式 称为公式的判定问题在命题逻辑中 由于任何一个命题公式的指派数目总是有限的 所以Ls的判定问题是可解的 判定方法有 真值表法公式推演法 2020年3月14日星期六 真值表法 例1 13用真值表判定 P Q Q是哪种类型的公式 该公式是矛盾式 即永假式 2020年3月14日星期六 真值表法 当公式所含不同命题变元较多或较复杂时 真值表法很麻烦 计算一些复杂的真值表所花费时间的程度甚至可能连现代最快速的计算机也无法达到 而且真值表法也是一个很乏味的方法 它对于培养逻辑思维与推理能力帮助甚少因此我们一般采用等值公式推演法或主范式来判定 2020年3月14日星期六 真值表法 例1 14列出P Q和 P Q的真值表 这两个公式的真值表是相同的也就是说 在任意指派下这两个公式的真值都是相同的 2020年3月14日星期六 等价公式 二 等价公式定义 设A和B是两个命题公式 若A和B在任意指派下 其真值都是相同的 则称A和B是等价的或逻辑相等 记做A B 称 A B 为等价式 永真双条件式 例如 前面我们写出的P Q和 P Q的真值表是完全一致的 因此P Q和 P Q就是等价式 2020年3月14日星期六 等价公式 我们已经知道 对于含有n个命题变元的命题公式 可以有2n种真值指派 由于对于每一种真值指派 命题公式的值都有两种可能的取值 T或F 因此由n个命题变元组成命题公式 可以构成22种不同的真值表 n n个命题变元可以组合成多少种命题公式 n 9时 质子 电子 2020年3月14日星期六 等价公式 定理 A B当且仅当A B是永真式这里要注意 与 的区别 是逻辑联结词 出现在命题公式中它表示在一个命题公式中 用它来连接的两个子公式的等值关系 是一个符号 并不是逻辑联结词 表示两个命题公式之间的等价关系 并不属于任何公式 2020年3月14日星期六 等价公式 等价式有以下性质 自反性对任意公式A 有A A对称性对任意公式A和B 若有A B 则有B A传递性对任意公式A B C 若有A B B C 则有A C 2020年3月14日星期六 基本等价公式 三 基本等价公式A B C代表任意命题 T表示真命题 F表示假命题E1双否定 A AE2交换律A B B AA B B AA B B AE3结合律 A B C A B C A B C A B C A B C A B C E 等值演算I 蕴含P 前提引入T 中间结论引入 2020年3月14日星期六 基本等价公式 E4分配律A B C A B A C A B C A B A C E5德 摩根律 A B A B A B A BE6等幂律A A A A A AE7同一律A T A A F AE8零律A F F A T TE9吸收律A A B AA A B A A B C代表任意命题 T表示真命题 F表示假命题 2020年3月14日星期六 基本等价公式 E10互补律A A F A A TE11条件式转化律A B A B B AE12双条件式转化律A B A B B A A B A B A B A B A B A B E13输出律 A B C A B C E14归谬律 A B A B A A B C代表任意命题 T表示真命题 F表示假命题 2020年3月14日星期六 例 求证P Q P P P Q 证明 P Q P P P Q P Q P E11 条件式转化律 P Q P E11 条件式转化律 P Q PE3结合律 P P Q E2交换律 P P Q E11 条件式转化律 P P Q E11 条件式转化律 基本等价公式 2020年3月14日星期六 代入规则和替换规则 四 代入规则和替换规则代入规则 在一个永真式A中 任何一个原子命题变元R出现的每一处 用另一个公式代入得到公式B 那么B仍然是永真式例1 15求证 P Q P Q 为永真式证明 已知R R T 用 P Q 代入公式中的R得到 P Q P Q T证毕 以真值真 或T 1 假 或F 0 为其域的变元 称为命题变元单个的命题变元和命题常元称为原子命题公式 简称原子公式 2020年3月14日星期六 代入规则 需要注意的是 对于非重言式 我们通常不作代入运算 特别是偶然式 例1 16已知公式A P Q 这是一个偶然式用R R代入公式A中的Q得到 P R R P T T这样一个偶然式经过代入运算 变成