Presentation is loading. Please wait.

Presentation is loading. Please wait.

第二章 逻辑和证明 2.2 命题等价 命题演算:用真值相同的命题取代另一个 在证明时广泛使用 定义1. 永真式(重言式):真值总是真

Similar presentations


Presentation on theme: "第二章 逻辑和证明 2.2 命题等价 命题演算:用真值相同的命题取代另一个 在证明时广泛使用 定义1. 永真式(重言式):真值总是真"— Presentation transcript:

1 第二章 逻辑和证明 2.2 命题等价 命题演算:用真值相同的命题取代另一个 在证明时广泛使用 定义1. 永真式(重言式):真值总是真
2.2 命题等价 命题演算:用真值相同的命题取代另一个 在证明时广泛使用 定义1. 永真式(重言式):真值总是真 矛盾(式):真值总是假 可能式:真值可真也可假 真值表判定法 例1 pp和pp 表2-1 永真式和矛盾的例子

2 定义2 命题逻辑等价:两个复合命题在所有可能的情况下 都有相同真值
是永真式 记为 真值表判定法 例2 证明命题 和 逻辑等价 解 在表2-2 中构造了这两个命题的真值表,由于 和 的真值相同,它们是逻辑等价的。(接下页)

3 表2-2 和 的真值表

4 例3 证明命题p∨(q∧r)和(p∨q)∧(p∨r)逻辑等价。这是析取对合取的分配律。
证明: 表1-11 中构造了这两个命题的真值表。因为p∨(q∧r)的真值和(p∨q)∧(p∨r)的真值一样,它们是逻辑等价的。

5 (3)交换律:A  B = B  A, A  B = B  A (4)结合律:(A  B)  C = 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 C)  (B  C) (A  B)  C = (A C)  (B  C) (6)德.摩根律:(A  B) = A  B (A B) =  A   B

6 (7)吸收律:A  (A  B) = A A (A  B) = A (8)零律: A  F = F A  T = T (9)一律: A  F = A A  F = A (10)排中律:A   A = T (11)矛盾律:A   A = F (12)蕴涵等值式:A→B = A  B (13)假言易位:A→B = B → A (14)等价等值式:AB = (AB)  (BA)

7 基本(p1p2…pn )  (p1 p2… pn )
命题逻辑等价关系与基本的集合恒等式的相似性 的结合律与pqrs的含义 的结合律与p q r s的含义 德摩根律的扩展 (p1 p2… pn )  (p1 p2… pn ) 等值演算:将复合命题中的一个子命题用与它逻辑等 价的另一个命题替换,不会改变原命题的真值,从而 得到新的逻辑等价的命题

8 例5 证明(p(pq))和pq逻辑等价
证明: 我们有下列等价关系 (p(pq))= p(pq) 由第二得摩根定律 = p((p)q) 由第一得摩根定律 = p(pq) 由双非律 =(pp)(pq) 由分配律 = F(pq) = pq 由 F的恒等律

9 例6 证明(p∧q)→(p∨q)为永真式。 证明 : 为证明这个命题是永真式,我们将用逻辑等价证明它逻辑上等价于T。(注意:这也可以用真值表来完成。) (p∧q)→(p∨q) = ¬(p∧q)∨(p∨q) = (¬p∨¬q)∨(p∨q) = ¬(p∨p)∨(¬q∨q) = T∨T = T

10 对偶原理:若两个命题等价,则它们的对偶命题也等价
只含逻辑运算符 、 和的命题的对偶命题:  、 TF 主析取范式和主合取范式 范式:具有某种特殊形式(结构)的命题公式 文字:命题变量或命题变量的否定(如p、p) 主析取范式:析取式,其中的每个析取项都是极小项 极小项: 由文字构成的合取式,且原命题公式中的每个命题变量都在合取式中出现一次 主合取范式:合取式,其中的每个合取项都是极大项 极大项: 由文字构成的析取式,且原命题公式中的每个命题变量都在析取式中出现一次

11 任意命题公式都有与之等价的主析取范式和主析取范式
从真值表构造主析取范式 对应于真值表中为真的每一行,在主析取范式中都有一个对应的合取式 行中为F的变量在相应的合取式中带有 从真值表构造主合取范式 对应于真值表中为假的每一行,在主合取范式中都有一个对应的析取式 行中为T的变量在相应的合取式中带有

12 例 命题公式A= 的主析取范式与主合取范式。 真值表: 主析取范式: 主合取范式:

13 习题 1.用真值表证明等价关系 2.证明 和 等 价 。 3.找一个只含命题p,q和r的复合命题,当p和q为真而r为假时命题为真,否则为假。
2.证明 和 等 价 。 3.找一个只含命题p,q和r的复合命题,当p和q为真而r为假时命题为真,否则为假。 (提示:用各个命题或其否定构造合取。)


Download ppt "第二章 逻辑和证明 2.2 命题等价 命题演算:用真值相同的命题取代另一个 在证明时广泛使用 定义1. 永真式(重言式):真值总是真"

Similar presentations


Ads by Google