《离散数学-1-5重言式与蕴含式》由会员分享，可在线阅读，更多相关《离散数学-1-5重言式与蕴含式（13页珍藏版）》请在金锄头文库上搜索。
1、第一章 命题逻辑1-5 重言式与蕴含式1一、公式的真假值分类n 有些命题公式不论对分量做何种指派，其对应的 真值都为1（真）或0（假），这两类特殊的命题 公式在今后的命题演算中极为有用，可根据公式 的取值情况对公式进行分类。 n 定义1-5.1 给定一个命题公式，若无论对分量作怎 样的指派，其对应的真值永为1，则称该命题公式 为重言式或永真公式。 n 定义1-5.2 给定一个命题公式，若无论对分量作怎 样的指派，其对应的真值永远为0，则称该命题为 矛盾式或永假公式。 n *注：命题公式若不是矛盾式,则可称为可满足式 。 2一、公式的真假值分类n真值表可用来判断公式的类型: (1) 若真值表最后
2、一列全为1，则公式为 重言式。 (2) 若真值表最后一列全为0，则公式为 矛盾式。 (3) 若真值表最后一列中至少有一个1， 则公式为可满足式。 3一、公式的真假值分类n定理1.5.1及证明 P19 n定理1.5.2及证明 P19 n定理1.5.3及证明 P204二、(永真/重言)蕴含式n形如AB重言式在我们将要学习的推理理 论中有着十分重要的作用。 n定义1-5.3 当且仅当PQ是一个重言式时， 我们称“P蕴含Q”，并记作PQ。（注：本课约定，“P Q”读作P蕴含Q，“P Q”读作P永真/重言蕴含Q。） *注：其中“”同样是一种元语言符号，用来 表示蕴涵式为重言式。 5二、 (永真/重言)蕴
3、含式n PQ是不对称的， PQ与QP一般是不等价的 。对PQ来说：n QP 称为它的逆换式。（前、后件取逆序）n PQ 称为它的反换式。（前、后件取其否定）nQP 称为它的逆反式。（前、后件取逆序及否定）n 注： “”命题公式与它的逆反式等价(P Q)(QP)，(QP)(PQ) 证明见P20真值表1-5.1*因此要证明PQ,只需要证明Q P，反之亦然6三、蕴含式证明n对PQ来说，除一种情况（P真值取1，Q 真值取0这样一种指派时，PQ为0 ）外， 其余情况PQ真值为1。 n要证PQ，只需对命题PQ的前件P指派 真值为1，若可由此出发，推导出Q的真值 为真，则PQ成立（即PQ为重言式）。 n同理
4、，可假定后件Q的真值取0，若可由推 出P的真值必为0,即证明了Q P 。7三、蕴含式证明n 例题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成立。8四、一些重要的（重言）蕴含式nP21页 这些重言蕴含式有些与思维逻辑相似
5、 nPQP， PQQ nPPQ （附加律） nP (PQ) nQ ( PQ) n( PQ) P n( PQ) Q nP(PQ) Q (假言推理）9四、一些重要的（重言）蕴含式nQ (PQ) P (拒取式) n P(PQ )Q (析取三段论) n(PQ) (QR) PR (假言三段论) n (PQ ) (PR) (QR) R n (PQ) (RS) (PR) (QS) n (PQ) (QR) (P R) (等价三段论）10五、重言蕴含的常用性质n 定理1-5.4 设P、Q为任意两个命题公式，PQ的 充分必要条件是PQ，Q P。 证明见P22 n 蕴含的几个常用性质n（1）设A、B、C为合式公式，若AB且A为重言式， 则B是重言式。n（2）若AB， BC，则AC，即永真蕴含关系是传 递的。n（3）若AB，且AC,那么A（B C）n（4）若AB， CB，则ACBn性质的证明见P2211内容小结n公式的真假值分类 n(重言)蕴含式 n蕴含式证明 n 一些重要的（重言）蕴含式 n重言蕴含的常用性质12课后作业nP23 （7）（8）(a)、(c)、(e)13
