离散数学 第二章 命题逻辑等值演算.ppt

文档介绍：第二章命题逻辑等值演算
等值式
一、等值式的概念
设A,B是两个命题公式,若A,B构成的等价式AB为重言式,则称A与B是等值的,记作AB.
     元语言符号记法
联结词
= 一般等号
判断等值式有如下方法:



二、用真值表判断公式的等值
判断下面两个公式是否等值:         ┐(p∨q)与┐p∧┐q
  解用真值表法判断┐(p∨q)(┐p∧┐q)是否为重言式。此等价式的真值表:
从表中可知它是重言式,因而┐(p∨q)与┐p∧┐q等值,即:┐(p∨q) ┐p∧┐q
判断下列各组公式是否等值:     (1)p→(q→r)与(p∧q)→r     (2)(p→q)→r与(p∧q)→r
解下表列出了p→(q→r),(p∧q)→r, (p→q)→r的真值表,不难看出p→(q→r)与(p∧q)→r等值,即 p→(q→r)(p∧q)→r 而(p→q)→r与(p∧q)→r的真值表不同,因而它们不等值,即 (p→q)→r (p∧q)→r
三、等值演算
16组重要的等值式
在下面公式中出现的A,B,C 是元语言符号,
它们代表任意的命题公式。
    1. 双重否定律        A ┐┐A ()
    2. 幂等律        AA∨A, AA∧A ()
    3. 交换律        A∨BB∨A,A∧BB∧A ()
4. 结合律     (A∨B)∨C  A∨(B∨C)      (A∧B)∧C  A∧(B∧C) ()
5. 分配律        A∨(B∧C) (A∨B)∧(A∨C)
(∨对∧的分配律)        A∧(B∨C) (A∧B)∨(A∧C)
(∧对∨的分配律) ()
 6. 德摩根律        ┐(A∨B) ┐A∧┐B,
┐(A∧B) ┐A∨┐B ()
7. 吸收律  A∨(A∧B) A,A∧(A∨B) A
()
 8. 零律        A∨11, A∧00 ()
 9. 同一律        A∨0A, A∧1A ()
10. 排中律        A∨┐A1 ()
11. 矛盾律        A∧┐A0 ()
12. 蕴涵等值式        A→B ┐A∨B ()
 13. 等价等值式        (AB) (A→B)∧(B→A) ()
 14. 假言易位        A→B┐B→┐A ()
 15. 等价否定等值式        AB ┐A ┐B ()
 16. 归谬论        (A→B)∧(A→┐B) ┐A ()