离散数学-1-5重言式与蕴含式.ppt

《离散数学-1-5重言式与蕴含式.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章命题逻辑1-5重言式与蕴含式1一、公式的真假值分类有些命题公式不论对分量做何种指派，其对应的真值都为1（真）或0（假），这两类特殊的命题公式在今后的命题演算中极为有用，可根据公式的取值情况对公式进行分类。定义1-5.1给定一个命题公式，若无论对分量作怎样的指派，其对应的真值永为1，则称该命题公式为重言式或永真公式。定义1-5.2给定一个命题公式，若无论对分量作怎样的指派，其对应的真值永远为0，则称该命题为矛盾式或永假公式。*注：命题公式若不是矛盾式,则可称为可满足式。2一、公式的真假值分类真值表可用来判断公式的类型:    (1)若真值表最后一列全为1，则公式为重言式。(2)若真值

2、表最后一列全为0，则公式为矛盾式。(3)若真值表最后一列中至少有一个1，则公式为可满足式。3一、公式的真假值分类定理1.5.1及证明P19定理1.5.2及证明P19定理1.5.3及证明P204二、(永真/重言)蕴含式形如A→B重言式在我们将要学习的推理理论中有着十分重要的作用。定义1-5.3当且仅当P→Q是一个重言式时，我们称“P蕴含Q”，并记作PQ。（注：本课约定，“P→Q”读作P蕴含Q，“PQ”读作P永真/重言蕴含Q。）*注：其中“”同样是一种元语言符号，用来表示蕴涵式为重言式。5二、(永真/重言)蕴含式P→Q是不对称的，P→Q与Q→P一般是不等价的。对P→Q来说：Q→P称为它的逆

3、换式。（前、后件取逆序）P→Q称为它的反换式。（前、后件取其否定）Q→P称为它的逆反式。（前、后件取逆序及否定）注：“→”命题公式与它的逆反式等价(P→Q)(Q→P)，(Q→P)(P→Q)证明见P20真值表1-5.1*因此要证明PQ,只需要证明QP，反之亦然6三、蕴含式证明对P→Q来说，除一种情况（P真值取1，Q真值取0这样一种指派时，P→Q为0）外，其余情况P→Q真值为1。要证PQ，只需对命题P→Q的前件P指派真值为1，若可由此出发，推导出Q的真值为真，则PQ成立（即P→Q为重言式）。同理，可假定后件Q的真值取0，若可由推出P的真值必为0,即证明了QP。

4、7三、蕴含式证明例题1：推证Q∧(P→Q)P证法一：（由假定前件为真推出后件必为真）假定Q∧(P→Q)为1，则Q为1且P→Q为1，由Q为1可知Q为0，此时由P→Q为1可知，P必为0，故P为真证法二:(由假定后件为假推出前件必为假）假定P为0,则P为1。对Q的情况做如下讨论：（1）：若Q为0,则P→Q为0,Q∧(P→Q)为0（2）：若Q为1,则Q为0,Q∧(P→Q)为0所以P为0时，必有Q∧(P→Q)为0，Q∧(P→Q)P成立。8四、一些重要的（重言）蕴含式P21页这些重言蕴含式有些与思维逻辑相似P∧QP，P∧QQPP∨Q（附加律）P(P→Q)Q(P

5、→Q)(P→Q)P(P→Q)QP∧(P→Q)Q(假言推理）9四、一些重要的（重言）蕴含式Q∧(P→Q)P(拒取式)P∧(P∨Q)Q(析取三段论)(P→Q)∧(Q→R)P→R(假言三段论)(P∨Q)∧(P→R)∧(Q→R)R(P→Q)∧(R→S)(P∧R)→(Q∧S)(P↔Q)∧(Q↔R)(P↔R)(等价三段论）10五、重言蕴含的常用性质定理1-5.4设P、Q为任意两个命题公式，PQ的充分必要条件是PQ，QP。证明见P22蕴含的几个常用性质（1）设A、B、C为合式公式，若AB且A为重言式，则B是重言式。（2）若AB，BC，则AC，即永真蕴含关系是传递

6、的。（3）若AB，且AC,那么A（B∧C）（4）若AB，CB，则A∨CB性质的证明见P2211内容小结公式的真假值分类(重言)蕴含式蕴含式证明一些重要的（重言）蕴含式重言蕴含的常用性质12课后作业P23（7）（8）(a)、(c)、(e)13