离散数学第1章重言式与蕴含式和其它连接词.ppt

1 离散数学DiscreteMathematics 山东科技大学信息科学与工程学院 2 为什么要学习离散数学 李开复 给中国学生的第四封信 大学四年应该这么度过数学是理工科学生必备的基础 很多学生在高中时认为数学是最难学的 到了大学里 一旦发现本专业对数学的要求不高 就会彻底放松对数学知识的学习 而且他们看不出数学知识有什么现实的应用或就业前景 但大家不要忘记 绝大多数理工科专业的知识体系都建立在数学的基石之上 例如 要想学好计算机工程专业 那至少要把离散数学 包括集合论 图论 数理逻辑等 线性代数 概率统计和数学分析学好 要想进一步攻读计算机科学专业的硕士或博士学位 可能还需要更高的数学素养 3 课程回顾 第1次课 命题 5个联结词第2次课 合式公式命题的翻译命题公式等价的两种证明方法真值表利用命题定律推导 第一章命题逻辑第3讲 1 5重言式与蕴含式 1 6其他连结词 重点 重言式 蕴含式难点 用推理方法证明蕴含式 5 回顾 表1 4 4 6 回顾 表1 4 2 7 一 重言式和矛盾式定义1 5 1给定一命题公式 若无论对分量作怎样的指派 其对应的真值永为T 则称该命题公式为重言式或永真公式 定义1 5 2给定一命题公式 若无论对分量作怎样的指派 其对应的真值永为F 则称该命题公式为矛盾式或永假公式 对于矛盾式也有类似于定理1 5 1和定理1 5 2的结果 证明由于重言式的真值与分量的指派无关 故对同一分量以任何合式公式置换后 重言式的真值仍永为T 口 定理1 5 2一个重言式 对同一分量都用任何合式公式置换 其结果仍为一重言式 证明设A和B为两个重言式 则不论A和B的分量指派任何真值 总有A为T B为T 故A B T A B T 口 定理1 5 1任何两个重言式的合取或析取 仍然是一个重言式 因为重言式的否定是矛盾式 矛盾式的否定是重言式 这样只研究其一就可以了 后面将重点研究重言式 重言式最有用 因为它有以下特点 两重言式的合取式 析取式 条件式和双条件式等都仍是重言式 于是 由简单的重言式可构造出复杂的重言式 由重言式使用公认的规则可以产生许多有用等价式和蕴涵式 10 证明重言式的方法 给定一命题公式 至少存在一个指派 公式相应确定真值为真 称为可满足式 重言式必是可满足式 反之一般不真 判定给定公式是否为永真式 永假式或可满足式的问题 称为给定公式的判定问题 在命题逻辑中 由于任何一个命题公式的指派数目总是有限的 所以命题逻辑的判定问题是可解的 其判定方法有真值表法和公式推演法 例题1证明 P S R V P S R 为重言式 证明因为PV P T 如以 P S R 置换P即得 P S R V P S R T 定理1 5 3设A B为两个命题公式 A B当且仅当AB为一个重言式 证明若A B 则A B有相同真值 即AB永为T 若AB为重言式 则AB永为T 故A B的真值相同 即A B 定理1 5 3的作用 为A B又提供了一种方法 其他方法 1 真值表法 2 利用命题定律推导证明 13 例题2证明 P Q P Q 证明 据定理1 5 3 只需证 P Q P Q 为重言式 二 蕴含式联结词可用 来表达 由第4节例题5可知 AB A B B A 下面讨论A B的重言式 1 定义定义1 5 3当且仅当P Q是一个重言式时 我们称 P蕴含Q 并记作P Q 符号 和 的区别与联系类似于 和 的关系 区别 是逻辑联结词 属于对象语言中的符号 是公式中的符号 不是联结词 属于元语言中的符号 表示两个公式之间的关系 不是两公式中符号 2 蕴含式的证明方法 1 列真值表法 根据定义 只需证P Q是重言式 2 逻辑推论前真看后真后假看前假 3 等价置换 例题3证明P P Q证明列出真值表 从表中看出P P Q是一个重言式 故P P Q成立 证明列出真值表 从表中看出P Q P不是一个重言式 故P Q P不成立 例题4考察P Q P是否成立 由例题3和例题4可知 P Q和Q P不等价 对P Q来说 Q P称作它的逆换式 P Q称为它的反换式 Q P称为它的逆反式 它们之间的关系如表所示 从表1 5 1中看出 P Q Q P Q P P Q 因此要证明P Q 只需证明 Q P 反之亦然 要证明P Q 即证P Q是重言式 对于P Q来说 除P的真值取T Q的真值取F这样一种指派时 P Q的真值为F外 其余情况 P Q的真值为T 要证P Q是重言式 1 只要对条件命题P Q的前件P 指定真值为T 若由此推出Q的真值也为T 则P Q是重言式 即P Q成立 前真看后真 2 同理 如条件命题P Q中 假定后件Q的真值取F 若由此推出P的真值为F 即推证了 Q P故P Q成立 后假看前假 例题1推证 Q P Q P 证法2 后假看前假 假定 P为F 则P为T a 若Q为F 则P Q为F Q P Q 为F b 若Q为T 则 Q为F Q P Q 为F 所以 Q P Q P成立 证法1 前真看后真 假定 Q P Q 为T 则 Q为T 且 P Q 为T 由Q为F 则必须P为F 故 P为T 表1 5 2常用的蕴含重言式 三 等价式和蕴含式的关系就象联结词和 的关系一样 等价式与蕴含式之间也有紧密的联系 定理1 5 4设P Q为任意两个命题公式 P Q的充分必要条件是P Q且Q P 证明若P Q 则PQ为重言式 因为PQ 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 设A B C为合式公式 若A B且A是重言式 则B必是重言式 证明因为A B永为T 所以 当A为T时 B必永为T 2 若A B 且B C则A C 即蕴含关系是传递的 证明由A B B C 即A B B C为重言式 所以 A B B C 为重言式 由表l 5 2的 11 式 A B B C A C 故由性质 1 A C为重言式 即A C 3 若A B 且A C 则A B C 证明由假设A B A C为重言式 设A为T 则B C为T 故B C为T 因此 A B C 为T 若A为F 则B C不论有怎样的真值 A B C 为T 所以 A B C 4 若A B 且C B 则A C B 证明因为A B为T C B为T 故 A B C B 为T 即 A C B 为T或A C B为T 所以A C B 四 小结本节主要内容1 深刻理解以下概念重言式给定一命题公式 若无论对分量作怎样的指派 其对应的真值永为T 则称该命题公式为重言式或永真公式 矛盾式给定一命题公式 若无论对分量作怎样的指派 其对应的真值永为F 则称该命题公式为矛盾式或永假公式 蕴含式当且仅当P Q是一个重言式时 称P蕴含Q 并记作P Q 逆换式对P Q来说 Q P称作它的逆换式 反换式对P Q来说 P Q称为它的反换式 逆反式对P Q来说 Q P称为它的逆反式 2 掌握以下定理定理1 5 1任何两个重言式的合取或析取 仍然是一个重言式 定理1 5 2一个重言式 对同一分量都用任何合式公式置换 其结果仍为一重言式 定理1 5 3设A B为两个命题公式 AB当且仅当AB为一个重言式 定理1 5 4设P Q为任意两个命题公式 PQ的充分必要条件是P Q且Q P 3 会证明重言式 蕴含式 28 前面已经定义了5种联结词 和 但这些联结词还不能广泛地直接表达命题间的联系 下面再定义4种命题联结词 1 6其他连结词 29 一 不可兼析取 异析取 表1 6 1 30 31 4 定理 证明 则 32 二 条件否定定义定义1 6 2设P和Q是两个命题公式 复合命题PQ称作命题P和Q的条件否定 PQ的真值为T 当且仅当P的真值为T Q的真值为F 否则的PQ的真值为F 表1 6 2 2 真值表联结词的定义如表1 6 2所示 从定义可知 33 三 与非定义 表1 6 3 2 真值表 从表1 6 3可以看出 2 真值表 34 3 性质 联结词 有如下几个性质 a P Q Q P b P P P c P Q P Q P Q d P P Q Q P Q 35 表1 6 4 从表1 6 4可以看出 2 真值表 1 定义 四 或非 36 3 性质 联结词 有如下几个性质 a P Q Q P b P P P c P Q P Q P Q d P P Q Q P Q 37 38 五 联结词完备集定义设S是一个联结词集合 如果任何n n 1 元真值函数都可以由仅含S中的联结词构成的公式表示 则称S是联结词完备集 根据需要 人们还可构造形式上更为简单的联结词完备集 例如 在计算机硬件设计中 用与非门或者或非门来设计逻辑线路时 就需要构造新联结词完备集 39 定理 都是联结词完备集 证已知 为联结词完备集 因而只需证明其中的每个联结词都可以由 定义即可 而 pp q p p p q p p 1 p q p q 定义 p p q q 由 1 3 p q p q p q 定义 p q p q 由 1 2 由 1 3 可知 是联结词完备集 类似可证 是联结词完备集 40 五 最小联结词组我们一共给出了九个联结词的定义 是否还需要定义其他联结词呢 下面列出两个命题变元可构成的所有不等价的命题公式 共有16个 41 由上述分析 除常量及命题变元本身外 命题联结词一共有九个就够了 42 实际上这九个联结词并非都是必要的 因为包含某些联结词的公式可以用另外一些联结词的公式等价代换 下面考虑最小联结词组 对于任何一个命题公式 都能由仅含这些联结词的命题公式等价代换 43 所以 44 六 小结本节所讲内容如下 不可兼析取设P和Q是两个命题公式 复合命题称作P和Q的不可兼析取 的真值为T 当且仅当P与Q的真值不同时为T 否则的真值为F 逆条件设P和Q是两个命题公式 复合命题PQ称作命题P和Q的条件否定 PQ的真值为T 当且仅当P的真值为T Q的真值为F 否则的PQ的真值为F 与非设P和Q是两个命题公式 复合命题称作命题P和Q的 与非 当且仅当P和Q真值都是T时 为F 否则的真值都为T 或非设P和Q是两个命题公式 复合命题称作命题P和Q的 或非 当且仅当P和Q的真值都为F时 的真值为T 否则的真值都为F 45 作业 P23 2 a 3种方法 8P29 3 46 离散数学DiscreteMathematics 山东科技大学信息科学与工程学院 第一章命题逻辑第4讲 1 7对偶与范式 要求 掌握对偶与范式 会求命题公式的主析取范式和主合取范式 重点和难点 求命题公式的主析取范式和主合取范式 一 对偶式1 复习命题定律 见15页表1 4 8 我们从表1 4 8可以看到命题定律除对合律外都是成对出现的 其不同的只是 和 互换 我们把这样的公式称作具有对偶规律 定义1 7 1在给定的命题公式中 将联结词 换成 将 换成 若有特殊变元F和T亦相互取代 所得公式A 称作A的对偶式 显然A也是A 的对偶式 2 对偶式的定义 例题1写出下列表达式的对偶式 P Q R P Q F P Q P Q S a P Q R b P Q T c P Q P Q S A A 定理1 7 1设A和A 是对偶式 P1 P2 Pn是出现在A和A 中的原子变元 则 A P1 P2 Pn A P1 P2 Pn A P1 P2 Pn A P1 P2 Pn 证明由德 摩根定律 P Q P Q P Q P Q 故 A P1 P2 Pn A P1 P2 Pn 同理 A P1 P2 Pn A P1 P2 Pn 例题3设A S W R 是 S W R 证明A S W R A S W R 所以A S W R A S W R 证明由于A S W R 是 S W R 则A S W R 是S W R 但A S W R 是 S W R 故 A S W R 是 S W R S W R 定理1 7 2设P1 P2 Pn是出现在公式A和B中的所有原子变元 如果A B 则A B 证明因为A B 即 是一个重言式 故 也是一个重言式 即 由定理1 7 1得 因此A B A p1 p2 pn B p1 p2 pn A p1 p2 pn B p1 p2 pn 定理1 7 2的作用 为A B又提供了一种方法 其他方法 1 真值表法 2 利用命题定律推导证明 3 证明A B为永真式