离散数学13.ppt

离散数学Discrete Mathematics
1
第一章命题逻辑第3讲§1—5 重言式与蕴含式
重点:重言式、蕴含式
难点:用推理方法证明蕴含式。
2
一、重言式和矛盾式
从上节真值表和命题的等价公式推证中可以看到,有些命题公式,无论对分量作何种指派,其对应的真值都为T (见14页表1-)或都为F(见13页表1-)。
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
表1-
3
表 1-
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
4
重言式和矛盾式这两类特殊的命题公式在今后的命题演算中极为有用。
定义1- 给定一命题公式,若无论对分量作怎样的指派,其对应的真值永为T,则称该命题公式为重言式或永真公式。
对于矛盾式也有类似于定理1--。
证明由于重言式的真值与分量的指派无关,故对同一分量以任何合式公式置换后,重言式的真值仍永为T。口
定理1- 一个重言式,对同一分量都用任何合式公式置换,其结果仍为一重言式。
证明设A和B为两个重言式,则不论A和B的分量指派任何真值,总有A为T,B为T,故A∧BT,A∨BT。口
定理1- 任何两个重言式的合取或析取,仍然是一个重言式。
定义1- 给定一命题公式,若无论对分量作怎样的指派,其对应的真值永为F,则称该命题公式为矛盾式或永假公式。
5
重点将研究重言式,因为重言式的否定是矛盾式,矛盾式的否定是重言式,这样只研究其一就可以了。
重言式最有用,因为它有以下特点:①两重言式的合取式、析取式、条件式和双条件式等都仍是重言式。于是,由简单的重言式可构造出复杂的重言式。②由重言式使用公认的规则可以产生许多有用等价式和蕴涵式。
6
证明重言式的方法给定一命题公式,至少存在一个指派,公式相应确定真值为真,称为可满足式。重言式必是可满足式,反之一般不真。判定给定公式是否为永真式、永假式或可满足式的问题,称为给定公式的判定问题。在Ls中,由于任何一个命题公式的指派数目总是有限的,所以Ls的判定问题是可解的。其判定方法有真值表法和公式推演法。
7
例题1 证明((P∨S)∧R)V┐((P∨S)∧R)为重言式。
证明因为PV┐PT, 如以((P∨S)∧R)置换P即得
((P∨S)∧R)V┐((P∨S)∧R) T
8
定理1- 设A、B为两个命题公式,A  B当且仅当A B为一个重言式。
证明
若AB,则A、B有相同真值,即A B永为T。
若A B为重言式,则A B永为T,故A、B的真值相同,即AB。
例题2 证明┐(P∧Q)(┐P∨┐Q)
证明由表1-,┐(P∧Q) (┐P∨┐Q)为重言式,故据定理1- :
┐(P∧Q)(┐P∨┐Q)
9
二、蕴含式
联结词可用→来表达。由第4节例题5可知:
A B(A→B)∧(B→A)
下面讨论A→B的重言式。

定义1- 当且仅当P→Q是一个重言式时,我们称“P蕴含Q”,并记作P  Q。
10