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

等价式(equivalences),蕴涵式(implication),定义1-5.3当且仅当PQ是一个重言式时，我们称“P蕴含Q”，并计作PQ,定义1-8.1设A和C是两个命题公式，当且仅当AC为一重言式，即AC，称C是A的有效结论。或C可由A逻辑地推出。定义1-8.2设H1，H2，Hm和C为命题公式，若H1H2HmC，则称C为一组前提H1，H2，Hm的有效结论。,1.pqppqq2.p，pqq3.p，pqq4.q，pqp5.pq，qrpr6.pq,pq，qrr,证明H1H2HmC的方法,真值表法：（1）假设A为T时，说明B也为T。（2）假设B为F时，说明A也为F。例：证明p(pq)q,证明H1H2HmC的方法,1.pqppqq2.p，pqq3.p，pqq4.q，pqp5.pq，qrpr6.pq,pq，qrr,直接证法：P规则：前提在论证过程中随时可以引用。(premise)T规则：在推导中，如果有一个或多个公式蕴含着公式S，则公式S可以引入推导之中。,证：(PR)(QR)(PQ)R证明：(1)PRP(2)QRP(3)PQP(4)PQT(3)E(5)PRT(4),(2)I(6)(PR)(PR)T(1),(5)I(7)RT(6)E,证明：J(MN),(HG)J,HGMN证明：(1)J(MN)P(2)(HG)JP(3)(HG)(MN)T(1),(2)I(4)HGP(5)MNT(3),(4)I,证明H1H2HmC的方法,间接证法：,要证H1H2HmC记A=H1H2Hm，即是要证AC，AC是重言式，AC是重言式，AC是矛盾式，即是要证H1H2HmC是矛盾式等于多了一个前提C，用直接证明方法证得矛盾即可,（1）反证法,例：证：SQ,SR,R,PQP证明:(1)PP(附加前提)(2)SRP(3)RP(4)ST(2),(3)I(5)SQP(6)QT(4),(5)I(7)PQP(8)(PQ)(QP)T(7)E(9)PQT(8)I(10)QT(9)I(11)QQ(永假）T(6),(10)I,证明H1H2HmC的方法,间接证法：,若要证H1H2HmRC记A=H1H2Hm，即是要证ARC，A(RC)是重言式，A(RC)是重言式，(AR)C是重言式，(AR)C是重言式，(AR)C即要证H1H2HmRCR作为附加前提，用直接证法得到C即可,（2）CP规则,例：证：ABCD,DEFAF证明:利用CP规则(1)AP(附加前提)(2)ABT(1)I3(3)ABCDP(4)CDT(2),(3)I11(5)DT(4)I2(6)DET(5)I3(7)DEFP(8)FT(6),(7)I11(9)AFCP规则,1.如果小霞是理科生，她一定学微积分，如果她不是文科生，她一定是理科生，她没学微积分,所以她是文科生。2.所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。,LogicPuzzles,Thereisanislandthathastwokindsofinhabitants,knights,whoalwaystellthetruth,andtheiropposites,knaves.Whoalwayslie.YouencountertwopeopleAandBifAsays“Bisaknight”andBsays“Thetwoofusareoppositetypes.”一个岛上居住着两类人骑士和流氓。骑士说的都是实话，而流氓只会说谎。你碰到两个人A和B，如果A说“B是骑士”，B说“我们不是一类人”。请判断A、B两人到底是流氓还是骑士。其它情况：A说：“我们之间至少有一个是流氓”，B什么都没说。A说：“我们是流氓或者B是骑士”，B什么都没说。A说：“我们都是流氓”，B什么都没说。,2020/5/23,Muddychildrenpuzzle,2.Afathertellshistwochildren,aboyandagirl,toplayintheirbackyardwithoutgettingdirty.However,whileplaying,bothchildrengetmudontheirforeheads.Whenthechildrenstopplaying,thefathersays“Atleastoneofyouhasamuddyforehead.”andthenasksthechildrentoanswer“Yes”or“No”tothequestion:“Doyouknowwhetheryouhaveamuddyforehead?”Thefatherasksthisquestiontwice.Whatwillthechildrenanswereachtimethisquestionisasked,assumingthatachildcanseewhetherhisorhersiblinghasamuddyforehead,butcannotseehisorherownforehead?Assumethatbothchildrenarehonestandthatthechildrenanswereachquestionsimultaneously.,2020/5/23,Muddychildrenpuzzle,2.父亲让两个孩子（一个男孩，一个女孩）在后院玩耍，并让他们不要把身上搞脏。然而，在玩的过程中，两个孩子都在额头上沾了泥。当孩子们回来后，父亲说“你们当中至少有一个人额头是有泥”，然后他问每两个孩子“你知道你额头上有泥吗？”，要求他们回答“yes”或者“no”,同样的问题问了两遍。假设每个孩子都可以看到对方的额头上是否有泥，但不能看见自己的额头，孩子们每次的回答是什么样的呢？假设两个孩子都很诚实并且都同时回答每一次提问。,2020/5/23,蕴含式(implication),定理1-5.4：设P、Q为任意两个命题公式，PQ的充分必要条件是PQ且QP。证明：由定理1-5.3，PQ，则PQ为重言式，因为由表1-4.7PQ(PQ)(QP)，故(PQ)为T且(QP)为T，即PQ且QP成立。反之，若PQ且QP成立，则(PQ)为T且(QP)为T，因此PQ为T，PQ为重言式，即PQ。这个定理也可作为两个公式等价的定义。,蕴含的性质,*（1）设A、B、C是