01-命题逻辑-14~15.ppt

第一章命题逻辑 2020年3月14日星期六 第四节对偶式与蕴涵式 第四节对偶式与蕴涵式一 对偶式定义 在给定的仅使用联结词 的命题公式A中 若把 和 互换 F和T互换 得到一个公式A 称A 是A的对偶式 称A和A 互为对偶式 2020年3月14日星期六 对偶式 例1 24求下列公式的对偶式 P Q R P TP Q P Q R P F P Q P Q P Q P Q 2020年3月14日星期六 对偶式 对偶定理 设A和A 互为对偶式 P1 P2 Pn是出现在A和A 的原子命题变元 则 A P1 P2 Pn A P1 P2 Pn A P1 P2 Pn A P1 P2 Pn 2020年3月14日星期六 A P1 P2 Pn A P1 P2 Pn 证明 设公式A中含有联结词 的数目为L当L 0时 A P1 A A P1 P1 P1 A P1 当L 1时 A P1 P2 或 P1 P2 或 P1 当A P1 P2 时 A P1 P2 A P1 P2 P1 P2 P1 P2 A P1 P2 当A P1 P2 时 A P1 P2 A P1 P2 P1 P2 P1 P2 A P1 P2 当A P1时 A P1 A P1 P1 A P1 2020年3月14日星期六 A P1 P2 Pn A P1 P2 Pn 设当L k 1时 k 1 2 时 A P1 P2 Pn A P1 P2 Pn 成立当L k时若A P1 P2 Pn A1 P1 P2 Pn A2 P1 P2 Pn 则LA1 LA2 k 1 由上面结论得 A1 P1 P2 Pn A1 P1 P2 Pn A2 P1 P2 Pn A2 P1 P2 Pn 2020年3月14日星期六 A P1 P2 Pn A P1 P2 Pn A P1 P2 Pn A1 P1 P2 Pn A2 P1 P2 Pn A1 P1 P2 Pn A2 P1 P2 Pn A1 P1 P2 Pn A2 P1 P2 Pn A P1 P2 Pn 2020年3月14日星期六 A P1 P2 Pn A P1 P2 Pn 同理 若A P1 P2 Pn A1 P1 P2 Pn A2 P1 P2 Pn 可证 A P1 P2 Pn A P1 P2 Pn 若A P1 P2 Pn A1 P1 P2 Pn 可证 A P1 P2 Pn A1 P1 P2 Pn A P1 P2 Pn 由上证明 可得当L K时 A P1 P2 Pn A P1 P2 Pn 证毕 2020年3月14日星期六 对偶式 例1 25设A P Q R P Q R 求证 A P Q R P Q R 证明 A P Q R P Q R P Q R 又因为 A P Q R A P Q R 所以 A P Q R P Q R 证毕 A P1 P2 Pn A P1 P2 Pn 2020年3月14日星期六 对偶式 对偶定理 设A和B是两个命题公式 若A B 则A B 证明 A B意味着A P1 P2 Pn B P1 P2 Pn 永真 所以 A P1 P2 Pn B P1 P2 Pn 永真 因为 A P1 P2 Pn A P1 P2 Pn B P1 P2 Pn B P1 P2 Pn 因此A P1 P2 Pn B P1 P2 Pn 永真 用 Pi代入Pi得到A P1 Pn B P1 Pn 永真因此A B 证毕 2020年3月14日星期六 对偶式 例1 26求证 P Q P Q P Q证明 P Q P Q P Q P Q E1E11 P P Q Q P Q E2E4 T P Q E6E10 P QE7 2020年3月14日星期六 对偶式 例1 27求证 P Q P Q P Q证明 由前面证明得知 P Q P Q P Q P Q P Q P Q P Q P Q P Q证毕 设A和B是两个命题公式 若A B 则A B 2020年3月14日星期六 蕴涵式 二 蕴涵式定义 设A和B是两个命题公式 若A B是永真式 则称A蕴涵B 记做A B 称A B为蕴涵式或条件永真式 与 的区别 是逻辑联结词 出现在命题公式中 是一个符号 表示两个命题公式之间的蕴涵关系 2020年3月14日星期六 蕴涵式 蕴涵式有以下性质 自反性对任意公式A 有A A传递性对任意公式A B C 若有A B B C 则有A C对任意公式A B C 若有A B A C则A B C 对任意公式A B C 若有A C B C则 A B C 2020年3月14日星期六 蕴涵式 等价式和蕴涵式的关系 定理 设A和B是两个命题公式 A B的充要条件是 A B且B A证明 1 若A B 则A B是永真式 因为 A B A B B A 所以 A B B A 是永真式所以 A B 和 B A 都是永真式所以A B且B A 必要条件得证 P QP是Q的充分条件 Q是P的必要条件 2020年3月14日星期六 蕴涵式 证明 2 若A B且B A 则 A B 和 B A 都是永真式 因为 A B A B B A 所以A B是永真式所以A B 充分条件得证 因此 A B的充要条件是 A B且B A 证毕 2020年3月14日星期六 蕴涵式的证明 蕴涵式的证明方法 真值表法若前件为真 能推得后件为真 则此蕴涵式为真若后件为假 能推得前件为假 则此蕴涵式为真 指明两种证明思路 2020年3月14日星期六 蕴涵式的证明 例1 28求证 Q P Q P证明 1 真值表法 2020年3月14日星期六 蕴涵式的证明 2 前件真则后件真 Q P Q P 设 Q P Q 为T 则 Q为T P Q也为T可得到 Q为F 故P为F 因此 P为T 得证3 后件假则前件假设 P为F 则P为T若Q为T 则 Q为F 则 Q P Q 为F若Q为F 则P Q为F 则 Q P Q 为F 证毕 2020年3月14日星期六 基本蕴涵公式 基本蕴涵公式A B C D代表任意命题I1化简式A B AI2A B BI3附加式A A B A B AI4附加式变形 A A BI5B A BI6化简式变形 A B AI7 A B B 2020年3月14日星期六 基本蕴涵公式 I8假言推论A A B BI9拒取式 B A B AI10析取三段论 A A B BI11条件三段论 A B B C A CI12双条件三段论 A B B C A CI13合取构造二难 A B C D A C B D A B C D代表任意命题 如果A则B A 所以B 如果A则B B 所以 A 要么A 要么B A 所以B 2020年3月14日星期六 基本蕴涵公式 I14析取构造二难 A B C D A C B D特别的 当B D时 有 A B C B A C B A B C B A C BI15前后件附加A B A C B C A B A C B C A B C D代表任意命题 如果A则B 并且如果C则D 但是要幺A要幺C 所以 要幺B要幺D 2020年3月14日星期六 基本蕴涵公式 补充 I16A B B C A C I17 A B C D A C B D I18A B A BA B B AI19A B A B A B C D代表任意命题 A和B分别为真 所以A B为真 2020年3月14日星期六 蕴涵式 例1 29求证 P Q P Q证明 1 P Q P Q P Q P Q P Q P Q P Q Q T2 P Q QI2 P QI5 指明两种证明思路按定义套公式 定义 若A B是永真式 则称A蕴涵B 2020年3月14日星期六 第五节联结词的扩充与功能完全组 第五节联结词的扩充与功能完全组一 联结词的扩充合取非 设P Q是任意两个原子命题 定义 P Q P Q 当且仅当P和Q的值均为T时 P Q的值为FP Q读作 P合取非Q 合取非 又称 与非 2020年3月14日星期六 联结词的扩充 析取非 设P Q是任意两个原子命题 定义 P Q P Q 当且仅当P和Q的值均为F时 P Q的值为TP Q读作 P析取非Q 析取非 又称 或非 2020年3月14日星期六 联结词的扩充 条件非 设P Q是任意两个原子命题 定义 P Q P Q 当且仅当P为T而Q为F时 P Q的值为TP Q读作 P条件非Q 2020年3月14日星期六 联结词的扩充 双条件非 设P Q是任意两个原子命题 定义 P Q P Q 当且仅当P和Q的真值不同时 P Q的值为TP Q读作 P双条件非Q 双条件非 又称 异或 2020年3月14日星期六 扩充联结词的性质 与非的性质交换律P Q Q P幂律P P P P Q P Q P Q P P Q Q P Q 2020年3月14日星期六 扩充联结词的性质 与非的性质 补充 P T PP F T德 摩根律 P Q P Q 自己证明 2020年3月14日星期六 扩充联结词的性质 或非的性质交换律P Q Q P幂律P P P P Q P Q P Q P P Q Q P Q 2020年3月14日星期六 扩充联结词的性质 或非的性质 补充 P F PP T F德 摩根律 P Q P Q 自己证明 2020年3月14日星期六 扩充联结词的性质 例1 30求证 P Q的对偶式是P Q证明 P Q P Q P Q P Q P Q P Q 2020年3月14日星期六 扩充联结词的性质 例1 31求证 P Q P Q P Q证明 P Q P Q P Q E12 P Q同理 可证 P Q P Q 2020年3月14日星期六 扩充联结词的性质 异或的性质交换律P Q Q P结合律P Q R P Q R分配律P Q R P Q P R 幂律P P F P P T同一律P F P P T P若P Q R 则Q R P R P Q且P Q R F 2020年3月14日星期六 扩充联结词的性质 我们一共学习了9个联结词 优先级由高到低为 由教材P16的真值表可知 这9个命题联结词可以表示所有的命题间的联结关系 是不是必须用这9个表示命题间的联结关系呢 能不能再少一些 2020年3月14日星期六 联结词功能完全组 二 联结词功能完全组由定义知 P Q P Q P Q P Q P Q P Q P Q P Q 因此 仅使用 就足够了 2020年3月14日星期六 联结词功能完全组 又因为 P Q P Q P Q E12P Q P QE11P Q P Q E5P Q P Q E5仅使用 或 就足够了 2020年3月14日星期六 联结词功能完全组 定义 设D为联结词集合 若D中一个联结词可以由D中其他的联结词表示 则该联结词成为冗余联结词 设D为联结词集合 若任何命题公式总可以用含有D中的联结词的等值式表示 且D中不含有冗余联结词 则称D为全功能联结词集合 或联结