离散数学课件重言式与蕴含式.ppt

1 5重言式与蕴含式 1 5 1重言式 tautology 定义1 5 1 重言式 给定一个命题公式 若无论对分量作怎样的指派 其对应的真值永为T 则称该命题公式为重言式或永真公式 1 5重言式与蕴含式 1 5 1重言式 tautology 定义1 5 2 矛盾式 给定一个命题公式 若无论对分量作怎样的指派 其对应的真值永为F 则称该命题公式为矛盾式或永假公式 1 5 1重言式 tautology 性质1 5 1若A和B均为重言式 则A B及A B也为重言式 性质1 5 2若A是一个重言式 则对A的同一个分量都用另外一个合式公式置换 所得公式仍为重言式 例 P Q P Q 是重言式 P14 P用R T替换 还是重言式 1 5 1重言式 tautology 定理1 5 3设A B为两个命题 A B当且仅当AB为一个重言式 证明 若A B 则A B有相同的真值 由双条件定义AB永为T 上例是重言式 则 P Q P Q 德 摩根律得证 若AB为重言式 则AB永为T 故A B有相同的真值 即A B 1 5 2蕴含式 implication 定义1 5 3 蕴含式 当且仅当 是一个重言式时 我们称 蕴含 并记作 对于 来说 逆换式为 反换式为 逆反式为 有 与 不等价 命题与逆否命题等价 1 5 2蕴含式 implication 证明A B的方法 要证A B 即证A B是重言式 或证其逆反式 B A是重言式即可 要证A B是重言式 推理法 1 假设A为T时 说明B也为T 因为当A为T B为F时 A B为F 或 2 假设B为F时 说明A也为F 因为可得 B为T时 A也为T 即 B A是重言式 此方法是命题逻辑中的一个基本证明方法 可使用表1 5 2的蕴含式 1 5 2蕴含式 implication 例 n是整数 证明若n2是奇数 n也是奇数 证明 反证法 若n是偶数 n2也是偶数 设n 2k k是一个整数 则n2 2k 2 2 2k2 所以n2是偶数 所以原命题得证 1 5 2蕴含式 implication 例 见P21例1课上做表1 5 2的11式看表1 5 2 记住常用的蕴含式 1 5 2蕴含式 implication 定理1 5 4 设P Q为任意两个命题公式 P Q的充分必要条件是P Q且Q P 证明 由定理1 5 3 P Q 则PQ为重言式 因为由表1 4 7PQ P Q Q P 故 P Q 为T且 Q P 为T 即P Q且Q P成立 反之 若P Q且Q P成立 则 P Q 为T且 Q P 为T 因此PQ为T PQ为重言式 即P Q 这个定理也可作为两个公式等价的定义 1 5 3蕴含的性质 1 设A B C是合式公式 若A B且A是重言式 则B必是重言式 2 若A B B C 则A C 传递性 3 若A B A C 则A B C 4 若A B C B 则A C B以上性质在推理中常用 特别说明 如果推导蕴含 则可以用等价的式子替换 因为 等价 比 蕴含 强 好比 大于等于 与 等于 的关系 作业 1 5 P23 1 b c 2 b 说明 6 8 先不做 因为有效性第八节讲 1 6其它联结词 定义1 6 1不可兼析取 ExclusiveOR 设P和Q是两个命题公式 复合命题P Q称作P和Q的不可兼析取 P Q的真值为T 当且仅当P与Q的真值不相同时为T 否则 P Q的真值为F 真值表如下 1 6 1不可兼析取的性质 设P Q R为命题公式 则有 1 P Q Q P交换性 2 P Q R P Q R 结合性 3 P Q R P Q P R 分配性 4 P Q P Q P Q 5 P Q PQ 由定义得到 6 P P F F P P T P P 1 6 2条件否定 定义1 6 2条件否定设P和Q是两个命题公式 复合命题P Q称作P和Q的条件否定 P Q的真值为T 当且仅当P的真值为T Q的真值为F 否则 P Q的真值为F 真值表如下 C C C C 1 6 2条件否定的性质 由定义可知 P Q P Q C 1 6 3与非 定义1 6 3与非设P和Q是两个命题公式 复合命题P Q称作P和Q的 与非 当且仅当P和Q的真值都为T时 P Q的真值为F 否则P Q的真值都为T 真值表如下 1 6 3与非的性质 1 P Q P Q 2 P P P P P 3 P Q P Q P Q P Q 4 P P Q Q P Q P Q P Q 1 6 4或非 定义1 6 4或非设P和Q是两个命题公式 复合命题P Q称作P和Q的 或非 当且仅当P和Q的真值都为F时 P Q的真值为T 否则 P Q的真值都为F 真值表如下 1 6 4或非的性质 1 P Q P Q 2 P P P P P 3 P Q P Q P Q P Q 4 P P Q Q P Q P Q P Q 1 6 5联结词是否够用 每种联结词对应一种四个T或F的组合 总共可以有24 16种组合 似乎需要16种联结词才够用 事实上 我们定义的这九种就够用了 请看P27表1 6 5 1 6 6最小联结词组 最小联结词组应为 或 亦可以为 或 证明 1 用这些联结词组可以表示其它的联结词 2 用 以及 不能表示其它的联结词 不能表示 因为含有二元联结词的命题公式不能用仅含一元联结词