第一章 命题逻辑1516.ppt

第一章 命题逻辑1516.ppt§ 重言式与蕴含式
定理1- 任何两个重言式的合取或析取,仍然是一个重言式。
证明:设A和B为两个重言式,则不论A和B的分量指派任何真值,总有A为T,B为T,
故A∧BT,A ∨ B T 。
§ 重言式与蕴含式
定理1- 一个重言式,对同一个分量都用任何合式公式置换,其结果仍为一个重言式。
证明:由于重言式的真值与命题变元指派无关,所以在对重言式中的同一命题变元均用任何一个合式公式置换后,该合式公式取真或取假均不影响置换后的公式的取值,所以置换后的公式的值仍为真,故得证。
§ 重言式与蕴含式
定理1- 一个重言式,对同一个分量都用任何合式公式置换,其结果仍为一个重言式。
证明((P ∨ S) ∧ R) ∨((P ∨ S) ∧ R)为重言式
§ 重言式与蕴含式
证明:
必要性:若AB,则A、B具有相同的真值,
即AB为一永真式
充分性:若A B为重言式,则A B永为T,
故A、B具有相同的真值,即AB
公式等价与重言式间的关系
定理1- 设A、B为两个命题公式,AB当且仅当AB 为一个重言式。
§ 重言式与蕴含式
证明(P ∧ Q) P ∨ Q
方法:将要证明为等价的两个公式用“”连接起来,得到公式(P ∧ Q) (P ∨ Q),然后求出该公式的真值表
P
Q
(P ∧ Q)
P ∨ Q
(P ∧ Q) (P ∨ Q)
T
T
F
F
T
T
F
T
T
T
F
T
T
T
T
F
F
T
T
T
§ 重言式与蕴含式
公式的蕴含与常用的蕴含式
定义1- 当且仅当P→Q是一个重言式,称“P蕴含Q”,记作P  Q。

例可以验证P ∧Q →Q是一个重言式,所以P ∧Q 蕴含Q,记作P ∧Q  Q
§ 重言式与蕴含式
公式的蕴含与常用的蕴含式
通常,对公式P→Q来说, 公式Q→P称作它的逆换式;  P→ Q称为它的反换式;  Q→ P称它的逆反式。
可以验证: P→Q  Q→ P,即原公式与逆反式等价
Q→P  P→ Q,即逆换式与反换式等价
§ 重言式与蕴含式
常用的蕴含式
PP∨Q (QP∨Q)
PΛQ P (PΛQ Q)
PΛ(P→Q) Q
(P→Q)Λ¬Q¬P
¬PΛ(P∨Q)  Q
(P→Q)Λ(Q→R) (P→R)
(P→Q)Λ(R→S) (PΛR→QΛS)
(PQ)Λ(QR) (PR)
¬P P→Q
§ 重言式与蕴含式
常用的蕴含式
Q P→Q
¬(P→Q)  P
¬(P→Q) ¬Q
(P∨Q)Λ(P→R)Λ(Q→R)  R
证明上述蕴含式的方法有三种:
(1)把“”关系符改为“→”联结词,证明它为永真式。
(a)真值表法
(b)命题演算法
§ 重言式与蕴含式
(2)*找出使单条件命题前件为“T”的所有真值指派,试看能否导致后件均为“T”,若为“T”,则永真蕴含关系成立。
T
T
T
F
F
T
T
T
F
T
F
F
P→Q
Q
P