第3 编数理逻辑第6 章命题逻辑.ppt

1 第3编数理逻辑 第6章命题逻辑 2 6 1命题的概念与表示 命题日常语言不确切 具有二义性 需引入目标语言 公式符号 目标语言 表达判断的一些语言的汇集 判断 肯定 否定的思维形式 命题 能表达判断 具有确定真值的陈述句 3 真值 命题的判断结果称为真值 只有 真 和 假 两种 记为 T 和 F 或 1 和 0 没有判断无所谓是非的句子 感叹句 疑问句 祈使句不是命题 原子命题 不能分为更简单的陈述句 复合命题 由联结词 标点符号和原子命题复合构成的命题 用大写字母A B P Q 或Ai 12 等表示命题 例P 今天下雨 12 今天刮风 命题标识符 表示命题的符号 4 例 1 0 悖论 5 命题常量 一个命题标识符表示确定的命题 命题变量 一个命题标识符仅表示任意命题的位置标志 无真值 原子变元 命题变元表示原子命题 6 6 2命题联结词 复合命题 原子命题 联结词否定 定义设P为命题 P的否定是一个新的命题 记为 P 若P为T 则 P为F 若P为F 则 P为T 例 P 上海是大城市 P 上海不是大城市 或上海是不大的城市 一元联结词 7 合取 并且 定义两个命题P Q的合取是一个复合命题 记作P Q 当且仅当P Q同为T时 P Q为T 在其它情况下 P Q的真值为F 例 P 今天下雨 Q 明天下雨 P Q 今天下雨且明天下雨 今天明天都下雨 这两天都下雨 二元联结词 8 与自然语言不同 P 我们去看电影 Q 房间里有十张桌子 P Q 我们去看电影且房间里有十张桌子 仍是新命题 可将若干个命题联结一起 P 高中毕业 Q 上分数线 R 被某大学录取 P Q R 大学生 9 析取 或者 定义两个命题P Q的析取是一个复合命题 记作P Q 当且仅当P Q同为F时 P Q为F 在其它情况下 P Q的真值为T 例 P 今天下雨 Q 今天刮风 P Q 今天下雨或者刮风 二元联结词 10 日常语言中的 或者 可分 可兼或 与 不可兼或 两种 例1 今天晚上我在家看电视或去剧院看戏 不可兼或 例2 他可能是100米或400米赛跑的冠军 可兼或 析取是可兼或 例3 P 他中了大奖 Q 他中了小奖 P Q 他中了大奖或者中了小奖 也可能两奖都中 11 不可兼析取 排斥析取 定义设P Q是两个命题 复合命题P Q称为P Q的不可兼析取 P Q的真值为T当且仅当P与Q的真值不相同 否则 P Q的真值为F 例 P 他坐船去大连 Q 他乘车去大连 P Q 他坐船或乘车去大连 二元联结词 P Q P Q P Q 12 蕴含 条件 定义两个命题P Q的蕴含是一个复合命题 记作P Q 当且仅当P的真值为T Q的真值为F时 P Q的真值为F 在其它情况下 P Q的真值为T 例1 如果某动物为哺乳动物 则它必胎生 将命题符号化 设P 某动物为哺乳动物 Q 某动物胎生 命题符号化 P Q 且命题为真 P Q 1 二元联结词 13 例2 如果我得到这本小说 那么我今天就读完它 将命题符号化 并求命题的真值 解设P 我得到这本小说 Q 我今天就读完它 命题符号化 P Q 且命题的真值有以下四种实际情况 1 我得到这本小说 我今天读完它 T 2 我得到这本小说 我今天没有读完 F 3 我没有得到这本小说 我今天读完它 T 4 我没有得到这本小说 我今天没有读完 T 14 例3 如果雪是黑的 那么太阳从西方出 将命题符号化 并求命题的真值 解设P 雪是黑的 Q 太阳从西方出 命题符号化 P Q 且命题的真值 P Q 1 例4 如果雪是黑的 那么太阳从东方出 将命题符号化 并求命题的真值 解设P 雪是黑的 Q 太阳从东方出 命题符号化 P Q 且命题的真值 P Q 1 15 P Q中P称为前件 Q称为后件 自然语言中 若前提为假 无论结论为真或假 往往无法判断 在条件命题中 当前提为假时 结论都为真 称 善意的推定 P Q 如果P那么Q 只要P则Q 从P推出Q P仅当Q 只有Q才P P蕴含Q 16 等价 双条件 定义给定两个命题P和Q 复合命题P Q称为双条件命题 当P Q的真值相同时 P Q的真值为T 在其它情况下 P Q的真值为F 例1 两个三角形全等当且仅当对应边相等 设P 两个三角形全等 Q 三角形对应边相等 命题符号化 P Q 且命题为真 P Q 1 二元联结词 17 例2 燕子飞回南方 春天来了 将命题符号化 并求命题的真值 解 设P 燕子飞回南方 Q 春天来了 命题符号化 P Q 且命题的真值 P Q 1 例3 2 2 4当且仅当雪是白的 将命题符号化 并求命题的真值 解设P 2 2 4 Q 雪是白的 命题符号化 P Q 且命题的真值 P Q 1 18 复合命题 设A1 A2 An是命题 用五种逻辑联结词将这n个命题联结起来 得到一个新命题 称为复合命题 19 练习1 设命题P Q的真值为1 命题R S的真值为0 试确定下面命题的真值 P Q R P Q R S 解 P Q R P Q R S 1 1 0 1 1 0 0 1 0 1 0 0 0 0 1 1 20 6 3命题公式的翻译与解释 用大写英文字母代表一个抽象命题 而不代表一个具体命题 这个抽象命题称为命题符号 原子 命题符号称为原子 定义合式公式是如下定义的一个符号串 1 原子是合式公式 2 若G H是合式公式 则如下符号串 G G H G H G H G H G H 是合式公式 3 所有公式都是有限次使用 1 2 得到的符号串 21 命题公式 由命题变项 联结词 括号按一定规则组成的合式公式为命题公式 例 如下符号串 P Q R Q S R 就是公式 五种逻辑联结词的优先级按如下次序递减 故上例可写成 P Q R Q S R 对公式中的每个原子赋值后 公式就有一个真值 对原子一组赋值称公式的一个解释 22 定义设G是公式 A1 A2 An是出现在G中的所有原子 指定A1 A2 An一组真值 则这组真值称为G的一组赋值 解释 指派 记作I 例 G P Q R G的真值记为TI G 1 一般地G是具有n个不同原子的公式 则G有2n个不同的赋值 对一个公式G 将它在所有赋值下所取的真值列成一个表 称为G的真值表 6 4真值表与等价公式 23 例 求G P Q R 的真值表 成真赋值 成假赋值 24 有时赋值 0 0 0 写成 P Q R 0 0 1 写成 P Q R 0 1 0 写成 P Q R 1 1 1 写成 P Q R 25 定义 如果公式G H在任一组赋值I下真值相同 则称公式G H等值 记作G H 不是联结词 它表示两个公式的关系 逻辑等价 26 可见在所有赋值I下真值相同 P Q P Q 例 用真值表证明公式P Q和 P Q等值 证 由真值表 27 例 证明P Q P Q P Q 证 由真值表 可见在所有赋值I下真值相同 P Q P Q P Q 28 共学了六个联结词 全功能联结词组 任一命题公式都可用组中的联结词表示 这样的联结词组称全功能联结词组 如 由于P Q P Q Q P 也是全功能联结词组 由于P Q P Q P Q 也是全功能联结词组 由于P Q P Q 也是全功能联结词组 29 并非所有联结词都是必要的 公式中有些联结词可由其它联结词代替 最小联结词组 任一命题公式可由这些联结词表示 但不能再少一个 如 因为P Q P Q 如 因为P Q P Q 30 常用的逻辑等价式 A B A B B A 等价式 A B A B 蕴含式 A A A A A A 幂等律 A B B A A B B A 交换律 A B C A B CA B C A B C 结合律 A A B A A A B A 吸收律 A B C A B A C A B C A B A C 分配律 A 0 A A 1 A 同一律 A 0 0 A 1 1 零律 A A 1 A A 0 否定律 A B A B A B A B 德摩根律 31 A A 双重否定律 A B B A 假言易位 A B A B 等价否定式 A B A B A 归谬律 A B A B A B 异或等值式 32 以上公式的证明有两种方法 1 真值表 2 利用公式 例 证明吸收律A A B A 证一 A A B A 33 证二 A A B A 1 A B A 1 B A 1 A A A B A 34 代换规则在等值式中某命题变项用新的命题公式取代 得到新的等值式 如由A A A可产生 P Q P Q P Q 等等 等值演算 从某公式A推导出新公式B 且使A B 由基本等值式可以产生无数个不同等值式 35 重言式 永真式 G在所有的赋值下都是真的 矛盾式 永假式 G在所有的赋值下都是假的 可满足式 除矛盾式以外的公式 仅可满足式 除重言式和矛盾式以外的公式 6 5重言式与蕴含式 36 例 G P P Q 1 G是重言式 K P P Q K是可满足式 仅可满足式 H P P Q 0 H是矛盾式 37 重言蕴含式的三种等价定义 定义1 设G H是两个公式 如果对任意赋值I 都有TI G TI H 则称G重言蕴含H 记作G H 定义2 设G H是两个公式 对任意赋值I 如果G为真 必有H为真 则称G重言蕴含H 记作G H 定义3 设G H是两个公式 如果 G H 是恒真公式 则称G重言蕴含H 记作G H 例1 证P P G 证1 由定义1得证 证2 若P 1 则P G 1 G 1由定义2得证 证3 P P G P P G P P G 1 G 1由定义3得证 38 1 证明两个公式等值 化简公式 2 判别公式的类型 3 解决实际问题 等值式的推演能够解三类问题 39 例1证明 1 P Q P Q P 2 P Q R P Q R 证 1 P Q P Q P Q Q P 1 P P Q P Q P 2 P Q R P Q R P Q R P Q R P Q R P Q R P Q R 40 例2化简 A B B A C 解 B A B A A B A B A B B A C A B A B C 1 C 由等价的定义 当P Q的真值相同时 P Q的真值为1 C 41 例3判别下列公式的类型 1 Q P Q P 解 Q P Q P Q P Q P P Q P Q 1 公式Q P Q P 为重言式 42 2 P P Q Q R 解 P P Q Q R 1 0 R 1 0 0 公式 P P Q Q R 为矛盾式 3 P Q P 解 P Q P P Q P P当P 1 公式 0 当P 0 公式 1 公式 P Q P是可满足式 43 对偶式 对偶式 在一个不含联结词 和 的公式里 将 换成 换成 1换成0 0换成1 得一新公式 称为原公式的对偶式 将一个等值式的等号两端换成其对偶式 得到一新等值式 称为原等值式的对偶式 对偶性质 如果一个等值式是成立的 其对偶等值式也成立 6 6范式 44 公式的形式千变万化 G G G H G G G 1等等 是否有标准形式 定义 有限个命题变项或其否定构成的析取式称为简单析取式 有限个命题变项或其否定构成的合取式称为简单合取式 如 P Q A B C 定义 有限个简单合取式构成的析取式称为析取范式 有限个简单析取式构成的合取式称为合取范式 如 P P Q P Q R Q P Q P Q R 45 析取范式的对偶式称为合取范式 合取范式的对偶式称为析取范式 如 P Q P Q R 对偶式为 P Q P Q R P Q R既是析取范式 又是合取范式 P Q R既是析取范式 又是合取范式 P既是析取范式 又是合取范式 46 定理 范式存在定理 对于任意公式 都存在等值于它的析取范式和合取范式 证 对任意公式G 通过如下算法可得出等值于G的范式 1 将 化为 2 将 移到原子前 3 反复使用分配律 即可得到等值于G的范式 例1 将G P Q R S化为析取范式和合取范式 解 G P Q R S P Q R S P Q R S P Q R S P S Q R P S Q P S R 析取范式 合取范式 47 例2 将P Q R 化为析取范式和合取范式 解 P Q R 合取范式 P Q P R 析取范式 析取范式和合取范式不唯一 如 P P 1 P Q Q P Q P Q P P 0 P Q Q P Q P Q 第二式由对偶关系得到 主析取范式和主合取范式唯一 48 定义 n个命题变项P1 P2 Pn 每个变项与它的否定不同时出现 但是两者必须出现一个 且排列顺序与P1 P2 Pn的顺序一致 这样的简单合取式称为关于P1 P2 Pn的一个极小项或布尔合取 含n个命题变项的公式G共有2n个极小项 且与公式G的2n个赋值对应 49 例 公式G中包含P Q R三个命题变项 50 定义 对于含有n个命题变项的命题公式 如果有一个仅由极小项的析取构成的等值式 则该等值式称为原命题公式的主析取范式 定理 任何命题公式都存在与之等值的主析取范式 并且是唯一的 求主析取范式的方法 1 真值表法在一个命题公式的真值表中 真值为1的赋值所对应的极小项的析取 即为此命题公式的主析取范式 51 例3用真值表法求P Q P Q P Q 的主析取范式 解 P Q P Q P Q P Q m0 m1 m3 0 1 3 P Q P Q m3 3 P Q P Q P Q P Q m0 m1 m2 0 1 2 52 2 等值演算法 1 求命题公式的析取范式 2 消去 命题公式中所有矛盾式的析取项 如P P 合并相同项 3 若析取范式的某个合取项缺少命题变项Pj或 Pj 则添加 Pj Pj 再用分配律展开 4 将极小项按由小到大的次序排列 用 表示之 53 例 求公式G R P Q P R 的主析取范式 解 G R P Q P R R P Q P R R P Q P Q R R P Q Q Q P R R Q R P P R P Q R P Q Q P R Q P R Q R P Q R P P Q R P Q R P Q R P Q R P Q R P Q R 54 P Q R P Q R P Q R P Q R m3 m1 m7 m6 m1 m3 m6 m7 1 3 6 7 对任意公式G 存在唯一一个与G等值的主析取范式 恒假公式的主析取范式用0表示 55 主合取范式 定义 n个命题变项P1 P2 Pn 每个变项与它的否定不同时出现 但是两者必须出现一个 且排列顺序与P1 P2 Pn的顺序一致 这样的简单析取式称为关于P1 P2 Pn的一个极大项或布尔析取 极小项的对偶称为极大项 含n个原子的公式G共有2n个极大项 且与公式G的2n个赋值对应 56 例 公式G中包含P Q R三个命题变项 57 定义 对于含有n个命题变项的命题公式 如果有一个仅由极大项的合取构成的等值式 则该等值式称为原命题公式的主合取范式 定理 任何命题公式都存在与之等值的主合取范式 并且是唯一的 58 例5用真值表法求 R P Q P Q R 的主合取范式 解 59 M1 M4 M6 M7 1 4 6 7 R P Q P Q R P Q R P Q R P Q R P Q R 60 等值演算法 1 求命题公式的合取范式 2 消去 命题公式中所有永真的合取项 如P P 合并相同项 3 若合取范式的某个析取项缺少命题变项Pj或 Pj 则添加 Pj Pj 再用分配律展开 4 将极大项按由小到大的次序排列 用 表示之 61 主合取范式的求法与主析取范式的求法类似 例 求公式G P Q P的主合取范式 解 G P Q P P Q P P Q P P P Q P P Q P P Q Q Q P P Q P Q P Q P Q P Q M0 M1 0 1 62 主析取范式 主合取范式和真值表之间的关系 知道三者之一能直接求出另外两个 63 例 G R P Q P R 求G的主析取范式 主合取范式和真值表 解 前已求出G的主析取范式G P Q R P Q R P Q R P Q R m1 m3 m6 m7 1 3 6 7 0 2 4 5 M0 M2 M4 M5 P Q R P Q R P Q R P Q R 主合取范式 真值表 64 同一赋值对应的极小项和极大项不相同 如公式G中包含P Q二个原子 主析取范式 极小项 成真赋值主合取范式 极大项 成假赋值 65 主范式的用途 1 判断 证明 两个公式等值 2 判断公式的类型 解题可考虑三种方法 等值公式 主范式 真值表 3 解决实际问题 4 求公式的成真赋值和成假赋值 含2n个极小项 1 永真式 含0个极小项 0 永假式 至少含1个极小项 可满足 66 6 7命题逻辑的推理理论 推理 从给定的前提推出一个结论 也称为演绎 形式证明 蕴含 定义 设A1 A2 Am C为命题公式 如果 A1 A2 Am C为重言式 则称C为前提 A1 A2 Am 的有效结论 或称由 A1 A2 Am 逻辑地推出C 记作A1 A2 Am C上式为重言蕴含式 67 判断推理的五种方法 真值表法等值演算法主析取范式法直接证法间接证法 1 真值表法如果A1 A2 Am 1 C也为1 则有A1 A2 Am C 68 例1 C是否是前提A1和A2的有效结论 1 A1 P QA2 PC Q 2 A1 P QA2 PC Q 3 A1 P QA2 QC P 解 构造真值表 1 当A1和A2都为1时 C为1 P Q P Q 2 当A1和A2都为1时 C有值为0 Q不是P Q和 P的有效结论 2 当A1和A2都为1时 C有值为0 P不是P Q和Q的有效结论 69 2等值演算法 例2 证例1中各题 1 A1 P QA2 PC Q 解 1 P Q P Q P Q P Q P Q P Q P Q P Q P P Q Q P Q 1 1 1所以P Q P Q 70 2 P Q P Q 2 A1 P QA2 PC Q P Q P Q P Q P Q P Q不是重言式 所以Q不是P Q和 P的有效结论 71 3主析取范式法 例3 证例1中各题 1 A1 P QA2 PC Q 解 1 P Q P Q P Q P Q P Q P Q P Q P Q P Q P Q P Q P Q P Q P Q P Q P Q P Q m0 m1 m2 m3 0 1 2 3 所以P Q P Q 72 2 P Q P Q 2 A1 P QA2 PC Q P Q P Q P Q P Q P Q M0 0 1 2 3 不是重言式 所以Q不是P Q和 P的有效结论 73 4直接证法 形式演绎 A1 A2 An B 从前提推演出结论 形式演绎规则 规则P 在推导的过程中引入已知前提公式 规则T 在演绎过程中可以利用前面演绎出来的中间结果推出新的命题公式 演绎过程中需要用到等值式和重言蕴含式 74 重言蕴含式 14个 I1A B AI2A B B 化简 I3A A BI4B A B 附加 I5 A A B I6B A B I7 A B AI8 A B BI9A B A B 合取引入 I10 A A B B 析取三段论 I11A A B B 假言推论 I12 B A B A 拒取式 I13A B B C A C 假言三段论 I14A B A C B C C 构造性二难 I5和I7 I6和I8互为逆否命题 75 例4 证明C D C D H H A B A B R S R S 证 1 C DP 2 C D HP 3 HT 1 2 4 H A B P 5 A BT 3 4 6 A B R S P 7 R ST 5 6 C D C D H H A B A B R S R S 76 例5 证明A B A C D E D C E B 证 1 EP 2 D EP 3 DT 1 2 4 D CP 5 CT 3 4 6 A CP 7 AT 5 6 8 A BP 9 BT 7 8 A B A C D E D C E B 77 例6 证明P Q P R Q S S R 证 1 P QP 2 P QT 1 3 Q SP 4 P ST 2 3