02a重言式、蕴涵式.ppt

第三讲 重言式、蕴含式 上节内容回顾 上节内容回顾 上节内容回顾 上节内容回顾 证明命题公式等价 定义重言式、矛盾式 定义重言式、矛盾式 可能性 重言式、矛盾式相关的定理 重言式的证明 Tautology example Tautology by truth table Tautology by truth table Tautology by truth table Tautology by truth table Tautology by truth table Tautology by proof 练习： 定义蕴含式 蕴含式的定理、性质 Logical Non-Equivalence of Conditional and Converse 蕴含式的证明 练习： 本节总结 课 后 任 务 * * 命题的定义： 不受时间限制，客观上能判别真假的陈述句。 命题的分类： 原子命题： 不能分解为更简单的陈述句。 复合命题： 由联结词、标点符号和原子命题复合构成的命题。 命题常量： 用来表示确定命题的标识符。 命题变元： 表示任意命题位置标志的命题标识符。 例如：P∨┑P， P∧Q 命题变元可以表示任何命题； 当用一个特定命题取代命题变元P时，称为对P指派。 命题公式 的定义： 1、单个命题变元或常元本身是一个命题公式； 2、如果A是命题公式，则 ┑A是命题公式； 3、如果A和B是命题公式，则(A∧B)、(A∨B)、(A?B)、(A?B)都是命题公式。 4、当仅当能够有限次地应用1、2、3所得到的包含命题变元、联结词和括号的符号串是命题公式。 这是一个递归定义，1、为基础，2、3为归纳，4、为界限（停机条件）。 命题公式按优先级约定省去括号之后也是命题公式 在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。 变元取值的顺序：按二进制递增或递减 n个命题变元组成的命题公式共有 种真值情况。 2n 方法一： 列真值表 方法二： 利用置换规则进行等价变换 熟记P15命题的定律： 结合律、交换律、分配律、摩根律、同一律…… 把下面五个等价命题作为定律使用： P→Q ? ┑P∨Q P? Q ? （P∧Q）∨（┑P∧┑Q） P? Q ? （P→Q）∧（Q→P ） ?满足结合率：(P?Q) ?R ? P? (Q?R) ?不满足结合率：(P?Q)?R P?(Q?R) 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永远为T，则称该命题公式为重言式或永真式。 DEF: A compound proposition is called a tautology if no matter what truth values its atomic propositions have, its own truth value is T. EG: p ? ?p (Law of excluded middle) new! 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永远为F，则称该命题公式为矛盾式或永假式。 The opposite to a tautology, is a compound proposition that’s always false –a contradiction. EG: p ? ?p new! a compound proposition whose truth value isn’t constant is called a contingency. EG: p ? ?p 供参考 任何两个重言式的合取和析取，仍然是一个重言式。 一个重言式，对同一分量都用相同的任意合式公式置换，其结果仍为一重言式。 （理解：重言式的真值与分量的指派无关,而是由变元和逻辑运算符之间的关系决定） 两个命题公式A、B，A ? B 当仅当 A ? B是重言式。 如何证明给定的一个命题公式是重言式？ 方法一： 往证与 T 等价 方法一：列真值表 方法二：利用置换规则进行等价变换 方法二： 由已知的重言式置换而来：P.20 例1 Demonstrate that [?p ?(p ?q )]?q is a tautology in two ways: Using a truth table – show that [?p ?(p ?q )]?q is always true Using a proof (will get to this later). F F T F F T T T [?p ?(p ?q )]?q ?p ?(p ?q ) p ?q