《2015离散数学蕴含与推理.ppt》由会员分享，可在线阅读，更多相关《2015离散数学蕴含与推理.ppt（17页珍藏版）》请在三一办公上搜索。
1、等价式(equivalences),蕴涵式(implication),定义1-5.3 当且仅当P Q是一个重言式时，我们称“P蕴含Q”，并计作P Q,定义1-8.1 设A和C是两个命题公式，当且仅当AC为一重言式，即AC，称C是A的有效结论。或C可由A逻辑地推出。定义1-8.2 设H1，H2，Hm 和C为命题公式，若H1 H2 Hm C，则称C为一组前提H1，H2，Hm 的有效结论。,1.pqp pqq 2.p，p qq3.p，pqq 4.q，p q p 5.p q，q rp r 6.pq,p q，q r r,证明H1 H2 Hm C的方法,真值表法：（1）假设A为T时，说明B也为T。（2）假
2、设B为F时，说明A也为F。例：证明 p(p q)q,证明H1 H2 Hm C的方法,1.pqp pqq 2.p，p qq3.p，pqq 4.q，p q p 5.p q，q rp r 6.pq,p q，q r r,直接证法：P 规则：前提在论证过程中随时可以引用。(premise)T规则：在推导中，如果有一个或多个公式蕴含着公式S，则公式S可以引入推导之中。,证：(PR)(QR)(PQ)R证明：(1)PR P(2)QR P(3)PQ P(4)PQ T(3)E(5)PR T(4),(2)I(6)(PR)(PR)T(1),(5)I(7)R T(6)E,证明：J(MN),(HG)J,HG MN证明：(
3、1)J(MN)P(2)(HG)J P(3)(HG)(MN)T(1),(2)I(4)HG P(5)MN 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）反证法,例：证：SQ,SR,R,P Q P证明:(1)P P(附加前提)(2)SR P(3)R P(4)S T(2),(3)I(5)SQ P(6)Q T(4),(5)I(7)P Q P(8)(PQ)(QP)T(7)E(9)P
4、Q T(8)I(10)Q T(9)I(11)QQ(永假）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规则,例：证：ABCD,DEFAF证明:利用CP规则(1)A P(附加前提)(2)AB T(1)I3(3)ABCD P(4)CD T(2),(3)I11(5)D T(4)I2(6)DE T(5)I3(7)DEF P(8)F
5、T(6),(7)I11(9)AF CP规则,1.如果小霞是理科生，她一定学微积分，如果她不是文科生，她一定是理科生，她没学微积分,所以她是文科生。2.所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。,Logic Puzzles,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 kni
6、ght”and B says“The two of us are opposite types.”一个岛上居住着两类人骑士和流氓。骑士说的都是实话，而流氓只会说谎。你碰到两个人A和B，如果A说“B是骑士”，B说“我们不是一类人”。请判断A、B两人到底是流氓还是骑士。其它情况：A说：“我们之间至少有一个是流氓”，B什么都没说。A说：“我们是流氓或者B是骑士”，B什么都没说。A说：“我们都是流氓”，B什么都没说。,2023/7/4,Muddy children puzzle,2.A father tells his two children,a boy and a girl,to play in
7、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?”
8、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 simu
9、ltaneously.,2023/7/4,Muddy children puzzle,2.父亲让两个孩子（一个男孩，一个女孩）在后院玩耍，并让他们不要把身上搞脏。然而，在玩的过程中，两个孩子都在额头上沾了泥。当孩子们回来后，父亲说“你们当中至少有一个人额头是有泥”，然后他问每两个孩子“你知道你额头上有泥吗？”，要求他们回答“yes”或者“no”,同样的问题问了两遍。假设每个孩子都可以看到对方的额头上是否有泥，但不能看见自己的额头，孩子们每次的回答是什么样的呢？假设两个孩子都很诚实并且都同时回答每一次提问。,2023/7/4,蕴含式(implication),定理1-5.4：设P、Q为任意两个命
10、题公式，PQ的充分必要条件是PQ且QP。证明：由定理 1-5.3，P Q，则P Q为重言式，因为由表1-4.7 P Q(PQ)(QP)，故(PQ)为T且(Q P)为T，即PQ且QP 成立。反之，若PQ且QP 成立，则(PQ)为T且(QP)为T，因此P Q为T，P Q为重言式，即PQ。这个定理也可作为两个公式等价的定义。,蕴含的性质,*（1）设A、B、C是合式公式，若A B且A是重言式，则B必是重言式。*（2）若A B，B C，则A C（传递性）*（3）若A B，A C，则A BC（4）若A B，C B，则AC B以上性质在推理中常用。特别说明：如果推导蕴含，则可以用等价的式子替换，因为“等价”比“蕴含”强，好比“大于等于”与“等于”的关系。,
