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

《离散数学-1-5重言式与蕴含式.ppt》由会员分享，可在线阅读，更多相关《离散数学-1-5重言式与蕴含式.ppt（13页珍藏版）》请在三一办公上搜索。

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

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

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

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

5、,Q(PQ)P(拒取式)P(PQ)Q(析取三段论)(PQ)(QR)PR(假言三段论)(PQ)(PR)(QR)R(PQ)(RS)(PR)(QS)(PQ)(QR)(P R)(等价三段论）,11,五、重言蕴含的常用性质,定理1-5.4 设P、Q为任意两个命题公式，PQ的充分必要条件是PQ，Q P。证明见P22蕴含的几个常用性质（1）设A、B、C为合式公式，若AB且A为重言式，则B是重言式。（2）若AB，BC，则AC，即永真蕴含关系是传递的。（3）若AB，且AC,那么A（B C）（4）若AB，CB，则ACB性质的证明见P22,12,内容小结,公式的真假值分类(重言)蕴含式蕴含式证明一些重要的（重言）蕴含式重言蕴含的常用性质,13,课后作业,P23（7）（8）(a)、(c)、(e),