2015离散数学蕴含与推理.ppt

等价式(equivalences)蕴涵式(implication)定义定义1-5.3 当且仅当当且仅当P Q是一个重言式时，我们称是一个重言式时，我们称“P蕴含蕴含Q”，并计作，并计作P  Q定义定义1-8.1 设设A和和C是两个命题公式，当且仅当是两个命题公式，当且仅当AC为一重言式，即为一重言式，即AC ，称，称C是是A的有效结论或的有效结论或C可由可由A逻辑地推出逻辑地推出定义定义1-8.2 设设H1，，H2，，…，，Hm 和和C为命题公式，若为命题公式，若H1  H2   …   Hm  C，则称，则称C为一组前提为一组前提H1，，H2，，…，，Hm 的有效结论的有效结论 1. p qp p qq 2. p，，p  qq3.   p，，p qq 4.  q，，p  q   p 5. p  q，，q  rp  r 6. p q , p  q，，q  r r证明证明H1  H2   …   Hm  C的方法的方法真值表法：真值表法： （（1）假设）假设A为为T时，说明时，说明B也为也为T。

（（2）假设）假设B为为F时，说明时，说明A也为也为F例：证明例：证明  p  (p   q) qpqp  q  p TTFFTFTFFTFTFFFT证明证明H1  H2   …   Hm  C的方法的方法 1. p qp p qq 2. p，，p  qq3.   p，，p qq 4.  q，，p  q   p 5. p  q，，q  rp  r 6. p q , p  q，，q  r r直接证法：直接证法： P 规则：前提在论证过程中随时可以引用 (premise) T规则：在推导中，如果有一个或多个公式蕴含着公式S，则公式S可以引入推导之中 证：证：(PR) (QR) (P Q) R证明：证明：(1) PR P (2) QR P (3) P Q P (4)  PQ T(3) E (5)  PR T(4),(2) I (6) (PR) ( PR) T(1),(5) I (7) R T(6) E证明：证明：J (M N), (H G) J, H G  M N证明：证明：(1) J (M N) P (2) (H G) J P (3) (H G) (M N) T(1),(2) I (4) H G P (5) M N T(3),(4) I证明证明H1  H2   …   Hm  C的方法的方法间接证法：间接证法： 要证要证 H1   H2   …  Hm  C 记记A=H1   H2   …  Hm ，， 即是要证即是要证 A  C，，A C是重言式，是重言式，  A  C是重言式，是重言式，A    C是矛盾式，是矛盾式， 即是要证即是要证H1   H2   …  Hm    C是矛盾式是矛盾式 等于多了一个前提等于多了一个前提 C，用直接证明方法证，用直接证明方法证得矛盾即可得矛盾即可（（1）反证法）反证法例：证：例：证：SQ, S R,  R,  P Q  P证明证明: (1)  P P(附加前提附加前提) (2) S R P (3)  R P (4) S T(2),(3) I (5) SQ P (6)  Q T(4),(5) I (7)  P Q P (8) ( PQ) (QP) T(7) E (9)  PQ T(8) I (10) Q T(9) I (11) QQ(永假）永假） T(6),(10) I证明证明H1  H2   …   Hm  C的方法的方法间接证法：间接证法： 若要证若要证H1   H2   …  Hm  R  C记记A=H1   H2   …  Hm ，，即是要证即是要证 A  R  C，，A  (R  C)是重言式，是重言式，  A   ( R   C)是重言是重言式，式，  (A  R)   C是重言式，是重言式， (A  R)  C是重言式，是重言式， (A  R)  C即要证即要证H1   H2   …  Hm   R  CR作为附加前提，用直接证法得到作为附加前提，用直接证法得到C即可即可（（2））CP规则规则例：证：例：证：A BC D, D EFAF证明证明:利用利用CP规则规则 (1) A P(附加前提附加前提) (2) A B T(1) I3 (3) A BC D P (4) C D T(2),(3) I11 (5) D T(4) I2 (6) D E T(5) I3 (7) D EF P (8) F T(6),(7) I11 (9) AF CP规则规则 1.如果小霞是理科生，她一定学微积分，如果她不是文科生，她一定是理科生，她没学微积分,所以她是文科生。

2.所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的Logic Puzzles1.There is an island that has two kinds of inhabitants, knights, who always tell the truth, and their opposites, knaves. Who always lie. You encounter two people A and B if A says “ B is a knight” and B says “The two of us are opposite types.” 一个岛上居住着两类人一个岛上居住着两类人—骑士和流氓骑士说的骑士和流氓骑士说的都是实话，而流氓只会说谎你碰到两个人都是实话，而流氓只会说谎你碰到两个人A和和B，如果，如果A说说“B是骑士是骑士”，，B说说“我们不是一我们不是一类人类人”请判断A、、B两人到底是流氓还是骑士两人到底是流氓还是骑士 其它情况：其它情况： A说：说：“我们之间至少有一个是流氓我们之间至少有一个是流氓”，，B什么都没说。

什么都没说 A说：说：“我们是流氓或者我们是流氓或者B是骑士是骑士”，，B什么都没说什么都没说 A说：说：“我们都是流氓我们都是流氓”，，B什么都没说什么都没说8/30/2024Muddy children puzzle2. A father tells his two children, a boy and a girl, to play in their backyard without getting dirty. However, while playing ,both children get mud on their foreheads. When the children stop playing, the father says“At least one of you has a muddy forehead.” and then asks the children to answer “ Yes” or “ No” to the question:“Do you know whether you have a muddy forehead?” The father asks this question twice. What will the children answer each time this question is asked, assuming that a child can see whether his or her sibling has a muddy forehead, but cannot see his or her own forehead? Assume that both children are honest and that the children answer each question simultaneously.8/30/2024Muddy children puzzle2. 父亲让两个孩子（一个男孩，一个女孩）在后院玩耍，父亲让两个孩子（一个男孩，一个女孩）在后院玩耍，并让他们不要把身上搞脏。

然而，在玩的过程中，两个并让他们不要把身上搞脏然而，在玩的过程中，两个孩子都在额头上沾了泥当孩子们回来后，父亲说孩子都在额头上沾了泥当孩子们回来后，父亲说“你你们当中至少有一个人额头是有泥们当中至少有一个人额头是有泥”，然后他问每两个孩，然后他问每两个孩子子“你知道你额头上有泥吗？你知道你额头上有泥吗？”，要求他们回答，要求他们回答“yes” 或者或者“no”,同样的问题问了两遍假设每个同样的问题问了两遍假设每个孩子都可以看到对方的额头上是否有泥，但不能看见自孩子都可以看到对方的额头上是否有泥，但不能看见自己的额头，孩子们每次的回答是什么样的呢？假设两个己的额头，孩子们每次的回答是什么样的呢？假设两个孩子都很诚实并且都同时回答每一次提问孩子都很诚实并且都同时回答每一次提问 8/30/2024蕴含式(implication)定理定理1-5.4：设：设P、、Q为任意两个命题公式，为任意两个命题公式，PQ的充分必要条件是的充分必要条件是PQ且且QP 证明：由定理证明：由定理 1-5.3 ，，P Q，则，则P Q为重言式，为重言式，因为由表因为由表1-4.7 P Q (PQ) (QP)，故，故(PQ)为为T且且 (Q P)为为T，即，即PQ且且QP 成成立。

立 反之，若反之，若PQ且且QP 成立，则成立，则(PQ)为T且 (QP)为T，因此，因此P Q为为T，， P Q为重言式，为重言式，即即PQ这个定理也可作为两个公式等价的定义这个定理也可作为两个公式等价的定义蕴含的性质*（1）设A、B、C是合式公式，若A  B且A是重言式，则B必是重言式2）若A  B，B  C，则A  C（传递性）*（3）若A  B，A  C ，则A  BC （4）若A  B，C  B ，则AC  B以上性质在推理中常用特别说明：如果推导蕴含，则可以用等价的式子替换，因为“等价”比“蕴含”强，好比“大于等于”与“等于”的关系。