离散数学课件：1-6 公式的蕴含关系

1、 逻辑的一个重要功能是研究推理逻辑的一个重要功能是研究推理. . 固然，依靠固然，依靠等价关系可以进行推理等价关系可以进行推理. . 但是，进行推理时，不必但是，进行推理时，不必一定要依靠等价关系，只需是一定要依靠等价关系，只需是蕴含关系蕴含关系就可以了就可以了. .又如，若行列式两行成比例，则行列式值为又如，若行列式两行成比例，则行列式值为0，例如，若三角形等腰，则两底角相等，例如，若三角形等腰，则两底角相等，所以，这个行列式值为所以，这个行列式值为0. .所以，这个三角形两底角相等所以，这个三角形两底角相等. .这个三角形等腰，这个三角形等腰，这个行列式两行成比例，这个行列式两行成比例，&

2、amp;上面两个例子的推理关系涵义不同，但依据的推上面两个例子的推理关系涵义不同，但依据的推理规则相同，推理形式为：理规则相同，推理形式为： 若若P则则Q，P，所以，所以Q. .&推理的正确性与命题推理的正确性与命题P，Q涵义无关，只决定于逻涵义无关，只决定于逻辑形式，命题逻辑中用公式表示命题，命题间演绎辑形式，命题逻辑中用公式表示命题，命题间演绎推理关系，反映为公式间逻辑蕴含关系。推理关系，反映为公式间逻辑蕴含关系。(一一)蕴含关系的概念蕴含关系的概念&蕴含式蕴含式(implication)：当且仅当命题公式当且仅当命题公式PQ为重言式时，称为重言式时，称“P蕴含蕴含Q”，记

3、为，记为PQ，它又，它又称为称为逻辑蕴含式逻辑蕴含式.&蕴含式的理解蕴含式的理解 符号符号不是联结词，它表示公式间的不是联结词，它表示公式间的“永真永真蕴含蕴含”关系，也可以看成是关系，也可以看成是“推导推导”关系关系.即即PQ可以理解成：由可以理解成：由P可推出可推出Q.&当当PQ 为永真时，则认为为永真时，则认为“由由P可推出可推出Q”&即由即由P为真，可以推出为真，可以推出Q也为真也为真.与公式与公式PQ有关的几个公式有关的几个公式&逆换式：逆换式： Q P&反换式：反换式： P Q&逆反式：逆反式： QP&PQ QP&Q

4、P P Q六、公式的蕴含关系六、公式的蕴含关系（二）证明蕴含式二）证明蕴含式PQ的方法的方法方法方法1：列真值表，证明列真值表，证明PQ为永真式为永真式(略略).下面讨论另外两种方法下面讨论另外两种方法. 先看先看PQ的的真值表：真值表：PQTTTFFTFFPQT F TT于是有下面两种证明方法：于是有下面两种证明方法：方法方法2：假设前件假设前件P为为T，推出后件，推出后件Q也也为为T.方法方法3：假设后件假设后件Q为为F，推出前件，推出前件P也也为为F.六、公式的蕴含关系六、公式的蕴含关系 如果如果PQ为为永真式，则下永真式，则下述真值表的第二组指派不会出现述真值表的第二组指派不会出现.证

5、：证：设设 P (P Q)为为T ，则则 P 和和P Q为为T ，那么那么 P为为F ，再由再由P Q为为T ，得知得知Q为为T.证：证：设设PR为为F ，则则P为为T且且 R为为F ， 若若 Q为为T ， 则则 QR为为F ； 若若 Q为为F ， 则则 PQ为为F.故故(PQ) (QR)为为F.证明证明 P (P Q)Q.证明证明(PQ) (QR) PR.六、公式的蕴含关系六、公式的蕴含关系求证：求证： (A B) C) D ( C D) A B .证：证：假设前件假设前件(A B) C) D ( C D)为为T，则，则(A B) C, D, C D均为均为T.由由 D为为T， 则则D为为F

6、.又又 C D为为T， 得得 C 为为T， 即即C 为为F.又又(A B) C为为T， 得得A B为为F.而而 A B (A B) ，所以，所以， A B 为为T，得证，得证.解法解法1：假设前件为假设前件为T，推出后件，推出后件也也为为T.六、公式的蕴含关系六、公式的蕴含关系证：证：假设后件假设后件 A B为为F， 则则A 与与 B均为均为T.(1)如如C为为F，所以前件所以前件(A B) C) D ( C D)为为F.则则(A B) C为为F，(2)如如C为为T，则，则(a)如如D为为T，则则 D为为F，所以前件所以前件(A B) C) D ( C D)为为F.(b)如如D为为F，则则 C

7、 D为为F，所以前件所以前件(A B) C) D ( C D)为为F.综上得证综上得证.解法解法2：假设后件为：假设后件为F，推出前件，推出前件也也为为F.求证：求证： (A B) C) D ( C D) A B .六、公式的蕴含关系六、公式的蕴含关系证：证：由由D E, (D E) A均为均为T，得得 A 为为T，又由又由 A(B C)为为T，得得B C为为T，得证，得证.反证：反证：设前件为设前件为T，并假设后件，并假设后件B C为为F.又又 A(B C)为为T，得得 A为为F.而而(D E) A为为T， 得得D E为为F.这与这与D E为为T矛盾矛盾.假设不成立假设不成立. 得证得证.)

8、e)证明证明 A(B C), D E, (D E) A B C 设前件设前件( A(B C) ) ( D E) (D E) A) 为为T，则，则 A(B C), D E, (D E) A均为均为T.六、公式的蕴含关系六、公式的蕴含关系1. P Q 2. P Q 化简化简 P Q3. P 附加附加 P Q4. Q P Q5. P P Q6. Q P Q附加的应用附加的应用7. (P Q) P8. (P Q) Q化简的应用化简的应用（三）常用的逻辑蕴含式（三）常用的逻辑蕴含式六、公式的蕴含关系六、公式的蕴含关系9. P (P Q) 10. Q (P Q) 假 言 推 理假 言 推 理 Q P11.

9、 P (P Q) 析取三段论析取三段论 Q12. (P Q) (Q R) P R拒取式拒取式假言三段论假言三段论常用的逻辑蕴含式常用的逻辑蕴含式13. (P Q) (Q R) (P R)等价三段论等价三段论即即“反证反证法法”又称又称“选言推理选言推理”或或“排除法排除法”六、公式的蕴含关系六、公式的蕴含关系16. P , Q 17. P Q合 取 引 入合 取 引 入 P Q ( P R) (Q R)常用的逻辑蕴含式常用的逻辑蕴含式18. P Q ( P R) (Q R)14. (P Q) (P R) (Q S)(R S)构造性二难构造性二难15. (P R) (Q S) (P Q)(R S

10、)六、公式的蕴含关系六、公式的蕴含关系证：证：若若P Q， 则则P Q为重言式为重言式. 因为因为P Q (PQ) (Q P),故故PQ和和Q P皆为皆为T, 即即 P Q且且Q P.若若P Q且且Q P ， 则则PQ和和Q P皆为皆为T，反之，反之，从而从而P Q为为T， 即即P Q为重言式，为重言式， 亦即亦即P Q.（四）等价关系与蕴含关系间的联系（四）等价关系与蕴含关系间的联系定理定理 设设P, Q为任意两个命题，为任意两个命题，P Q的充分必要条件是的充分必要条件是P Q且且Q P.六、公式的蕴含关系六、公式的蕴含关系(1) 若若A B且且A是重言式是重言式, 则则A B为永真式，为

11、永真式，证：证：所以，当所以，当A为永真时，为永真时，B必为永真必为永真.(2) 若若A B, B C, 由由A B，则则A B , B C为永真式，为永真式，证：证： 由由A B, B C ，从而从而(A B) (B C)亦为永真式亦为永真式.由常用蕴含式，由常用蕴含式，(A B) (B C) A C及性质及性质(1),得得A C是永真式，是永真式，亦即亦即A C.则则B必是重言式必是重言式.则则A C.（五）蕴含式的性质（五）蕴含式的性质六、公式的蕴含关系六、公式的蕴含关系(3) 若若A B且且 A C, 证：证：则则A B C.(4) 若若A B且且 C B, 则则A C B .则则A B , A C为永真式，为永真式，由由A B, A C ，从而从而(A B) (A C)亦为永真式亦为永真式.由常用蕴含式，由常用蕴含式，(A B) (A C) A B C及性质及性质(1),得得A B C是永真式，是永真式，亦即亦即A B C.证：证：则