离散数学 命题逻辑2.ppt

1 真值表逻辑等价永真蕴涵 命题公式的真值表 对命题公式中各分量 命题变元 指派所有可能的真值 以及由此而确定的命题公式的真值汇列而成的表称为真值表 真值表示例1 P Q的真值表 真值表示例2 P Q P的真值表 真值表示例3 构成 P Q R的真值表 真值表结论 含有n个命题变元的命题公式中 n个变元共有 组不同的取值 回答 2n组 永真式和永假式 永真式 重言式 在命题变元的不同指派下 真值总是真的命题公式 记为1或T永假式 矛盾式 在命题变元的不同指派下 真值总是假的命题公式 记为0或F 永真式举例 P Q P的真值表 P Q P是永真式 永假式举例 P Q P 的真值表 P Q P 是永假式 逻辑等价 在真值表中 两个命题公式A和B在分量的不同指派下 其真值总是相同的 则称这两个命题公式A和B是逻辑等价的记做A B 逻辑等价例1 证明 P Q P Q 逻辑等价例2 证明P Q P Q Q P 常用的逻辑等价公式 1 P Q P QP Q P Q Q P P Q P Q P Q P Q Q P 常用的逻辑等价公式 2 P P 对合律 P Q R P Q R 结合律 P Q R P Q R P Q Q P 交换律 P Q Q PP Q R P Q P R 分配律 P Q R P Q P R P P Q P 吸收律 P P Q P 常用的逻辑等价公式 3 P Q P Q 摩根律 P Q P QP P P 等幂律 P P PP 0 P 同一律 P 1 PP 1 1 零律 P 0 0P P 1 否定律 P P 0 代换规则 设命题公式A和B逻辑等价 即A B 如果在命题公式C中出现A的地方用B替换后 不一定是每一处 得到命题公式D则C D 代换规则示例1 证明P P Q P Q证明 因为P Q P Q 利用代换规则得P P Q P P Q P P P Q 0 P Q P Q 命题的演算 利用代换规则从一个命题得到另一个逻辑等价的命题称为命题的演算 证明逻辑等价 永真 假 式的方法 1 方法一 真值表法设P1 Pn为命题A和B包含的所有命题变元 A B A为永真式 A为永假式 证明逻辑等价 永真 假 式的方法 2 方法二 命题演算A B A BA为永真式 A 1A为永假式 A 0 证明逻辑等价例 证明 P Q P Q证明 因为P Q P Q Q P P Q P Q Q P P Q Q P P Q Q P P Q Q P P Q Q P P Q 证明逻辑等价例2 证明 P Q P 1证明 P Q P P Q P P Q P P P Q 1 Q 1 对偶式 设A是命题公式 且A中仅有联结词 在A中将 1 0分别换成 0 1后所得的命题公式称为A的对偶式 记为A 对偶式示例 命题公式 P Q R 的对偶式为 P Q R 命题公式 P 0 Q的对偶式为 P 1 Q 对偶原理 设A B为仅有命题变元和联结词 构成的命题公式 A 为A的对偶式 B 为B的对偶式如果A B 则A B 永真蕴含式 设A B是命题公式 如果A B是永真式则称A永真蕴含B记为 A B 永真蕴涵的证明方法 1 欲证 A B方法一 构造A B的真值表方法二 利用等价演算证明A B 1方法三 证明当A为真时 B必为真 方法四 利用常用的等价公式和永真蕴涵公式证明 方法五 范式 永真蕴含式例1 1 证明P Q P证明 方法一等价于证明P Q P为永真式 P Q P的真值表如下 由真值表可知 P Q P为永真公式 故P Q P 永真蕴含式例1 2 证明P Q P证明 方法二 等价演算等价于证明 P Q P 1 P Q P P Q P P Q P 1故P Q P 永真蕴含式例1 2 证明P Q P方法三 证明P Q P为永真式等价于证明当P Q为真时 P必为真 若P Q为真 则P为真且Q为真 因此P必为真 永真蕴含式例2 证明 P Q Q R P R证明 等价于证明 当 P Q Q R 为T时 P R必为T 若 P Q Q R 为T时 有 P Q 为T且 Q R 为T 下面根据R的取值分两种情况讨论P R的取值 1 当R取值为T时 显然 P R为T 2 当R取值为F时 由 Q R 为T可知 Q必为F 进而 由 P Q 为T可知 P必为F 因此 当R为F时 P R必为T综上所证 当 P Q Q R 为T时 P R必为T所以 P Q Q R P R 常用的永真蕴含式 1 1 P Q PP Q Q 2 P P QQ P Q 3 P P Q 4 Q P Q 5 P Q P 6 P Q Q 常用的永真蕴含式 2 7 P P Q Q 8 Q P Q P 9 P P Q Q 10 P Q Q R P R 11 P Q P R Q R R 12 P Q R S P R Q S 13 P Q Q R P R 永真蕴含的性质 设A B C是命题公式 1 若A B 则A B B A 2 若A B 则P A P B P A P B 补充 P A P B 补充 注意 A P B P A P B P P A P B或P A P B都不一定成立 3 若A B P Q 则P A Q B 4 若A B B C 则A C 利用常用永真式证明永真蕴含式 证明 P Q S Q S R R P证明 由于S R R S R S 因此 P Q S Q S R R P Q S Q R S R 根据逻辑等价的代换规则 P Q S Q S 根据P P Q Q P Q Q 根据P P Q Q P 根据 Q P Q Q 永真蕴含式中的代换规则 设命题公式A B如果在命题