(1.2.5)--ch1-第六讲离散数学离散数学.pdf

《(1.2.5)--ch1-第六讲离散数学离散数学.pdf》由会员分享，可在线阅读，更多相关《(1.2.5)--ch1-第六讲离散数学离散数学.pdf（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学离散数学 Discrete Mathematics 数理逻辑的主要任务是数理逻辑的主要任务是用数学的方法来研究数学中用数学的方法来研究数学中 的推理的推理.推理推理是指从前提出发推出结论的思维过程是指从前提出发推出结论的思维过程.前提前提是已知命题公式集合是已知命题公式集合.结论结论是从前提出发应用推理规则推出的命题公式是从前提出发应用推理规则推出的命题公式.要研究推理要研究推理,首先应该明确什么样的推理是有效的或首先应该明确什么样的推理是有效的或正确的正确的.1-8 推理理论推理理论(Inference Theory)1-8 推理理论推理理论(Inference Theory)定义定

2、义1-8.1 设设A和和C是两个命题公式是两个命题公式,当且仅当当且仅当AC为一为一 重言式重言式,即即A C,称称C是是A的的有效结论有效结论,或或C 可由可由A逻辑推出逻辑推出.一般地一般地,序列序列H1,H2,Hn和和C 是命题公式是命题公式,当且仅当当且仅当 H1H2Hn C 称称 C 是一组前提是一组前提 H1,H2,Hn的的有效结论有效结论.判断有效结论的过程叫做判断有效结论的过程叫做论证过程论证过程.(1)由前提由前提 H1,H2,Hk 推结论推结论C 的推理是否正确与的推理是否正确与诸前提的排列次序无关诸前提的排列次序无关.说说 明明 (2)形式结构形式结构 (H1H2Hn)C

3、 或或 前提：前提：H1,H2,Hk 结论：结论：C 若推理正确，若推理正确，则记为则记为 H1H2Hk C H1H2Hk C 0 0 0 1 1 0 1 1(4)推理正确推理正确,并不能保证结论并不能保证结论C 一定为真一定为真.(3)前提和结论的取值有以下四种前提和结论的取值有以下四种.真值表法真值表法 a)在真值表中在真值表中,先找出前提先找出前提 H1,H2,Hn 的真值均为真的真值均为真 的行的行,若相应行中结论若相应行中结论C 的真值也都为真的真值也都为真,则则 D 为真为真,即即C为为 有效结论有效结论;b)在真值表中在真值表中,先找出结论先找出结论 C 的真值为假的所有行的真值

4、为假的所有行,若这若这 些行中些行中,前提前提 H1,H2,Hn的真值都至少有一个为假的真值都至少有一个为假,则则 D 为真为真,即即 C 为有效结论为有效结论.构造构造(H1H2Hn)C 的真值表的真值表.判断有效结论的常用方法判断有效结论的常用方法 例例1.如果张老师来了如果张老师来了,这个问题可以得到解答这个问题可以得到解答,如果李老师如果李老师 来了来了,这个问题也可以得到解答这个问题也可以得到解答,总之张老师或李老师来了总之张老师或李老师来了,这个问题就可得到解答这个问题就可得到解答.解解:设设 P:张老师来了张老师来了 Q:李老师来了李老师来了 R:这个问题可以得到解答这个问题可以

5、得到解答 此题可翻译为此题可翻译为(PR)(QR)(P Q)R.(PR)(QR)(P Q)R.P Q R PR QR P Q 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 1 1 1 1 1 1 可看出可看出,PR,QR,R Q 的真值都为的真值都为1的情况为第四的情况为第四,第六行和第八行第六行和第八行,而这三行而这三行 中中R的真值都为的真值都为1,故有故有:说明说明:在这里在这里,我们不关心结论是真还是假我们不关心结论是真还是假,而主要关心由给而主要关心由给定的前提是

6、否能推出这个结论来定的前提是否能推出这个结论来.直接证法直接证法 直接证法直接证法:由一组前提由一组前提,利用一些公认的利用一些公认的推理规则推理规则,根据已知根据已知 的等价或蕴含公式推演得到有效结论的等价或蕴含公式推演得到有效结论.常用的推理规则常用的推理规则 P 规则规则:(前提引入规则前提引入规则)前提在推导过程中的任何时候都可前提在推导过程中的任何时候都可 以引用以引用.T 规则规则:(结论引入规则结论引入规则)在推导过程中在推导过程中,前面已导出的有效结前面已导出的有效结 论都可作为后续推导的前提引入论都可作为后续推导的前提引入.例例1.证明证明:(PQ)(PR)(QS)SR (1

7、)PQ P (2)PQ T(1)E (3)QS P (4)PS T(2)(3)I (5)SP T(4)E (6)P R P (7)SR T(5),(6)I (8)SR T(7)E 证法证法1.例例1.证明证明:(PQ)(PR)(QS)SR (1)PR P (2)PQ RQ T(1)I (3)PQ P (4)RQ T(2),(3)I (5)RQ T(4)E (6)Q S P (7)R S T(5),(6)I (8)SR T(7)E 证法证法2.例例2.证明证明(WR)V,V(CS),SU,C U W 证明证明.(1)C U P(2)U T(1)I(3)SU P(4)S T(2),(3)I(5)C

8、 T(1)(6)C S T(4),(5)I(7)(CS)T(6)E(8)V(CS)P(9)V T(7),(8)I (10)(W R)V P(11)(W R)T(9),(10)I(12)W R T(11)E(13)W T(12)I (1)AD P (2)D P (3)A T(1)(2),I (4)AB P (5)B T,(3)(4),I (6)BC P (7)C T,(5)(6),I (8)C(AB)T,(4)(7),I 练习练习.证明证明 AB,BC,AD,D C(AB).证明证明.间接证法间接证法 定义定义1-8.2 设设 P1,P2,Pn 是出现于前提是出现于前提H1,H2,Hm中中 的全

9、部命题变元的全部命题变元,对于对于P1,P2,Pn的的一些一些真值指派真值指派,若能使若能使 H1H2Hm的真值为的真值为T,则称公式则称公式H1,H2,Hm是是相容的相容的.若对于若对于 P1,P2,Pn 的的每一组每一组真值指派使得真值指派使得 H1Hm 的真值为的真值为F,则称公式则称公式H1,H2,Hm 是是不相容的不相容的.要证明要证明:H1H2Hm C 即即:H1H2Hm C 为重言式为重言式 即即:(H1H2Hm)C 为重言式为重言式 即即:C(H1H2Hm)为矛盾式为矛盾式 因此因此:H1H2Hm C R R 间接证法间接证法 例例3.证明证明(AB),(B C)A 证明证明.

10、(1)A P(附加前提附加前提)(2)AB P(3)B T(1)(2),I(4)(B C)P(5)B C T(4),E (6)B T(5),I (7)B B(矛盾矛盾)T(3)(6),I 例例4.证明证明(PQ)(PR)(QS)SR(1)(S R)P(附加前提附加前提)(2)SR T(1),E(3)S T(2),I(4)QS P(5)Q T(3)(4),I(6)PQ P(7)P T(5)(6),I(8)PR P(9)R T(7),(8),I(10)R T(2),I(11)RR(矛盾矛盾)T(9),(10),I 证明证明.证明证明.(1)P P(附加前提附加前提)(2)P Q P (3)Q T(

11、1)(2),I (4)S Q P (5)S T(3)(4),I (6)RS P (7)R T(5)(6),I (8)R Q P (9)Q T(7)(8),I (10)Q Q(矛盾矛盾)T(3)(9),I 练习练习.证明证明 R Q,RS,S Q,PQ P 间接证明法的另一种情况间接证明法的另一种情况 若要证明若要证明 H1H2Hm(RC).将将H1H2Hm记作记作 S，即要证即要证 S (RC)或要证或要证 S(RC)故故 S(RC)为永真式为永真式 因为因为 S(RC)S(RC)(SR)C (S R)C (SR)C 所以若将所以若将R作为作为附加前提附加前提,若有若有(SR)C 即证得即证得

12、S (RC)由由(SR)C,证得证得S (RC)称为称为CP 规则规则.例例5.证明证明 A(BC),DA,B DC.证明证明:(1)D P(附加前提附加前提)(2)DA P (3)A T(1)(2),I (4)A(BC)P (5)BC T(3)(4),I (6)B P (7)C T(5)(6),I (8)DC CP 例例6.设有下列情况设有下列情况,结论是否成立结论是否成立?(a)或者是晴天或者是晴天,或者是下雨或者是下雨.(b)如果是晴天如果是晴天,我去看电影我去看电影.(c)如果我去看电影如果我去看电影,我就不看书我就不看书.解解.设设 A:晴天晴天,B:下雨下雨,C:我看电影我看电影,

13、D:我看书我看书 结论结论:如果我在看书如果我在看书,则天在下雨则天在下雨 AB,本例可符号化为本例可符号化为:结论为结论为:D B.前提为前提为:AC,C D (A B)(AB)证明证明:(1)D P(附加前提附加前提)(2)C D P (3)C T(1)(2),I (4)AC P (5)A T(3)(4),I AB,结论为结论为:DB.前提为前提为:AC,C D,(7)(AB)T(6),E(8)A B T(7),E(9)(A B)(BA)T(8),E(10)BA T(9),I(11)B T(5)(10),I(12)DB CP AB (6)P 内容小结内容小结 1.推理的基本概念：有效结论、

14、相容、不相容推理的基本概念：有效结论、相容、不相容 2.推理规则及推理定律推理规则及推理定律 3.判断有效结论的常用方法判断有效结论的常用方法 真值表法、直接证法、间接证法真值表法、直接证法、间接证法 解解 令令A:a是奇数是奇数,B:a是偶数是偶数,C:a能被能被2整除整除 练习练习.设有下列情况，结论是否有效设有下列情况，结论是否有效 (1)如果如果a是奇数，则是奇数，则a不能被不能被2整除；整除；(2)如果如果a是偶数，则是偶数，则a能被能被2整除；整除；结论：如果结论：如果a是偶数，则是偶数，则a不是奇数不是奇数 本例可符号化为：本例可符号化为：前提为前提为:A C，BC 结论为结论为:B A (H1H2Hn)C 是否为永真式是否为永真式 真值表法真值表法 等值演算法等值演算法 主范式法主范式法 推证法推证法 命题演算命题演算 推理规则推理规则 P规则规则 T规则规则 直接证法直接证法 间接证法间接证法 反证法反证法 CP规则规则