3-命题逻辑-2.ppt

文档介绍：重言式、等价式和蕴含式
公式的分类
一个命题公式,如果对于所有指派
命题公式的值都是T,则称该公式为重言式(永真式)
命题公式的值都是F,则称该公式为矛盾式(永假式)
至少存在一种真指派,则称该公式为可满足的
至少存在一种假指派,则称该公式为非永真的
例:重言式 P∨¬P
矛盾式 P∧¬P、(P∧Q)∧¬P
P
Q
¬P∨Q
P→Q
T
T
T
T
T
F
F
F
F
T
T
T
F
F
T
T
P
Q
P∧Q
¬P
(P∧Q)∧¬P
T
T
T
F
F
T
F
F
F
F
F
T
F
T
F
F
F
F
T
F
P
Q
P∧Q
¬(P∧Q)
¬P
¬Q
¬P∨¬Q
¬(P∧Q)↔(¬P∨¬Q)
T
T
T
F
F
F
F
T
T
F
F
T
F
T
T
T
F
T
F
T
T
F
T
T
F
F
F
T
T
T
T
T
P→Q是可满足式、是非永真的
(P∧Q)∧¬P是永假式
¬(P∧Q)↔(¬P∨¬Q)是永真式
公式的分类
定理
任何两个重言式的合取或析取,仍然是重言式
任何两个矛盾式的合取或析取,仍然是矛盾式
对一个重言式的同一分量都用某个公式置换,得到的仍然是重言式
对一个矛盾式的同一分量都用某个公式置换,得到的仍然是矛盾式
公式的分类
例:
P∨¬P、Q∨¬Q是重言式
所以(P∨¬P)∨(Q∨¬Q)、(P∨¬P)∧(Q∨¬Q)都是重言式
P∨¬P是重言式
用公式P∧Q置换P,得到的P∧Q∨¬(P∧Q)也是重言式
等价公式
定义
给定两个命题公式A和B,设P1,P2,…,Pn是所有出现在A和B中的原子变元,若给P1,P2,…,Pn任一组真值指派,A和B的值都相同,则称A和B是等价的,或逻辑相等的,记作AB
由上节真值表中的例子,可知¬P∨Q P→Q
等价公式
命题公式之间的等价关系具有自反性、对称性、传递性。即:
对任意公式A、B、C,有:
A  A
若A  B,则B  A
若A  B,B  C,则A  C
判断两个命题公式是否等价
真值表法
适用于公式中的变元较少的情况
利用等价的传递性来推导公式(等值演算)
常用的公式见教材9页基本等式(1)-(24)
特别重要的等价公式
等价公式---例题
求证Q→(P∨(P∧Q))Q→P
证明1
Q→(P∨(P∧Q))¬Q∨(P∨(P∧Q))
(¬Q∨P∨P)∧(¬Q∨P∨Q)
(¬Q∨P)∧T
¬Q∨P
Q→P
证明2
根据吸收律 P∨(P∧Q)P
所以 Q→(P∨(P∧Q))Q→P