《离散数学ch3[1]命题演算的推理》由会员分享，可在线阅读，更多相关《离散数学ch3[1]命题演算的推理（44页珍藏版）》请在金锄头文库上搜索。
1、离 散 数 学,第一部分 数理逻辑 命题演算的推理,简 单 回 顾,命题和联结词,命题公式分类永真式永假式可满足式,判定问题,真值表方法,命题演算,范式,推理理论,数理逻辑的主要任务 形式逻辑 定义: 研究演绎推理及其规律的科学 研究对象: 形式逻辑研究推理中的前提和结论之间的关系 研究方法: 建立逻辑演算是形式逻辑的主要方法 数理逻辑 用数学方法研究符号化、形式化的逻辑演绎规律的数学分支,是现代的形式逻辑数理逻辑的主要任务: 用数学的方法来研究推理的规律,推理理论,推理的形式结构 推理的方法,推理的形式结构,推理和演绎(形式证明) 推理: 从若干命题（前提）直接得出一个命题（结论）的思维过程
2、 推理分为:演绎推理与非演绎推理(归纳推理 )两类 演绎(形式证明): 按照推理规则，从给定的前提出发，推导出结论 特点: 如果前提都为真，则结论必然真 演绎推理常常简称为推理，其前提与结论之间的联系反映了事物情况之间的必然联系。 前提 已知的命题公式 结论 从前提出发，应用推理规则推出的命题公式,推理的形式结构,论证的合法性和有效性 论证的合法性: 前提正确、推理规则正确，则结论正确 论证的有效性: 不论前提是否正确、推理过程正确，论证有效,推理的形式结构,有效结论(或逻辑结论) 定义：若H1H2H3HnC，则称C是命题公式H1，H2，H3.Hn的有效结论。 特别地，AB称B是A的有效结论，
3、记为：A B 论证的具体过程叫证明。 推理的形式结构: H1H2H3Hn C H1H2H3Hn C,推理的形式结构,例1:如果天气凉，小王就不去游泳。天气凉。所以小王没去游泳。,P:天气凉; Q:小王去游泳,前提: PQ; P,结论: Q,推理的形式结构:,(PQ) P) Q,推理的方法,判断推理是否正确的问题,已知: 一个前提集合和一个结论前例中的前提:(PQ; P)前例中的结论: Q,问题: 以有限数目的步骤判断，由给定的前 提集合是否可以推导出该结论,即:判断由前提集合和结论构成的条件式是 否是永真蕴涵式,前例中的(PQ) P) Q是否是永真式,推理的方法,判断推理是否正确的2种方法：
4、转化为判定问题: 真值表法 命题演算法 范式法 基于推理规则方法,推理的方法:转化为判定问题,例1的证明: 即证明(PQ) P) Q是永真式 (1)真值表法:(真值表的最后一列全为1),推理的方法:转化为判定问题,例1的证明: (2)命题演算法,(PQ) P) Q,(P Q) P) Q,(Q P) Q, (Q P) Q, (Q P) Q, 1,推理的方法:转化为判定问题,例1的证明: (3)范式法,(PQ) P) Q,m0 m1 m2 m3,(0,1,2,3),1,例2:考察C是下列前提H1和H2的有效结论 (a) H1: PQ H2:P C:Q (b) H1: PQ H2: P C:Q (c
5、) H1: PQ H2:Q C:P 证明: 推理(a)的形式结构: 推理(b)的形式结构: 推理(c)的形式结构:,推理的方法:转化为判定问题,(PQ )P) Q,(PQ ) P) Q,(PQ ) Q) P,推理的方法:转化为判定问题,例2的证明: (1)真值表法:(真值表的最后一列全为1),(PQ )P) Q(假言推理),推理的方法:转化为判定问题,例2的证明: (2)命题演算法,推理(a): (PQ )P) Q 1,推理(b): (PQ ) P) Q,推理(c): (PQ ) Q) P,推理的方法:转化为判定问题,例2的证明: (3)范式法,推理(a): (PQ )P) Q (0,1,2,
6、3),推理(b): (PQ ) P) Q (1,2,3),推理(c): (PQ ) Q) P (0,2,3),推理的方法:转化为判定问题,例3 前提: 1. 如果一个人是单身汉，则他不幸福 2. 如果一个人不幸福，则他死得早 结论:单身汉死得早推理的形式结构:,PQ,QR,PR,(PQ) ( QR) (PR),证明:(略),假言三段论:(PQ) ( QR) (PR),推理的方法:转化为判定问题,例4:某人被杀害，凶手为王某或陈某，但王某有不在作案现场证明，则陈某为凶手。,P Q, P,(P Q) P) Q,证明:(略),析取三段论: (P Q) P) Q,Q,前提: 1.凶手为王某或陈某,2.
7、王某不是凶手,结论:王某为凶手,推理的形式结构:,推理的方法:转化为判定问题,例5 前提: 1. 如果某同学为省级运动员，则他被大学录取 2. 如果某同学高考总分590分以上，则他被大学录取 3. 某同学为省级运动员或高考总分590分以上 结论:该同学被大学录取 推理的形式结构:,PR,QR,P Q,(PR) ( QR) (P Q) R,证明:(略),二难推论:(PR) ( QR) (P Q) R,R,推理规则,基于推理规则方法(动态推理技术),理论上：真值表等3种方法可以在有限步判定推理是否正确,实际上：如果命题变项较多，则以上3种方法都不方便,建立若干推理规则，实现演绎推理的“动态推理技术
8、”,自然推理系统,自然推理系统,一个形式系统I由四个部分组成: (1)非空的字母表，记作A(I) (2)A(I)中符号构造的合式公式集，记作E(I) (3)E(I)中的一些特殊的公式组成的公理集，记作Ax(I) (4)推理规则集，记作R(I) 可以将I记为: 形式语言系统: 形式演算系统:,自然推理系统,两类形式系统 自然推理系统 公理推理系统,自然推理系统,自然推理系统P 1.字母表 命题和命题变量符号 联接词符号 括号与逗号 2.合式公式 3.推理规则,建立在永真蕴含式(推理定律)和等价式(命题定律) 基础之上的推理规则,常用的推理规则,推理规则,建立在永真蕴含式(推理定律)和等价式(命题
9、定律) 基础之上的推理规则 a.任一永真蕴含式都代表一条推理规则 b.恒等式AB表示AB，BA，故恒等式也是推理规则例: P49的规则412,推理规则,重要的推理定律,(PQ )P) Q (假言推理),(PQ) P (化简式),Q P Q (附加式),(PQ ) Q) P (拒取式),(PQ) ( QR) (PR) (假言三段论),(P Q) P) Q (析取三段论),(PQ) ( QR) (PR) (等价三段论),(PR) ( QR) (P Q) R (二难推论),推理规则: 常用推理规则,定理: 设 G1，G2.Gn,和H1，H2.Hm，R,C都是命题公式，则 1. G1，G2.Gn Gi
10、 (i=1,2,n) 2. 若G1，G2.Gn Hj (j=1,2,m)且H1，H2.Hm C,则G1，G2.Gn C 3. G1，G2.Gn RC当且仅当G1，G2.Gn ，RC,推理规则: 常用推理规则,1.证明 G1，G2.Gn Gi (i=1,2,n),G1 G2 . Gn Gi,(G1 G2 . Gn) Gi, (G1 G2 . Gn) Gi, G1 . Gi Gi. Gn, 1,规则P: 在推理的任何步骤上，都可以引入前提,推理规则: 常用推理规则,2.证明若G1，G2.Gn Hj (j=1,2,m)且H1，H2.Hm C,则G1，G2.Gn C,(G1 . Gn) C,(G1 G
11、2 . Gn) (H1 H2 . Hm) 1, (G1.Gn)C,前提1:G1，G2.Gn H1，H2.Hm,前提2:H1，H2.Hm C 1,(H1.Hm)(H1.Hm), (G1.Gn)(H1.Hm)C(H1.Hm)C(G1.Gn), (G1.Gn) (H1.Hm)C (H1.Hm)C(G1.Gn),(G1 . Gn) C, 1C 1(G1.Gn), 1,推理规则: 常用推理规则,2.证明若G1，G2.Gn Hj (j=1,2,m)且H1，H2.Hm C,则G1，G2.Gn C,规则T:在推导过程中，如果前面有一个或多个命题公式，永真蕴涵公式S,那么就可以把公式S引入推导过程中,推理规则:
12、 常用推理规则,3.证明 G1，G2.Gn RC当且仅当G1，G2.Gn ，RC,(G1 G2 . Gn) (RC),(G1 G2 . Gn) (RC),(G1 G2 . Gn) RC,(G1 G2 . Gn R)C,(G1 G2 . Gn R) C,规则CP:如果能从前提集合和R中推导出S来，那么就能够从前提集合推导出RS, 1, 1,推理规则: 常用推理规则,规则P: 在推理的任何步骤上，都可以引入前提(P49规则1) 规则T:在推导过程中，如果前面有一个或多个命题公式，永真蕴涵公式S,那么就可以把公式S引入推导过程中(P49规则2) 规则CP:如果能从前提集合和R中推导出S来，那么就能够
13、从前提集合推导出RS (P51),常用证明方法,直接证明法 分情况证明 反证法(间接证法),常用证明方法:直接证明,1.直接证明法,例1.如果考试及格，那我高兴。 若我高兴，那么我饭量增加。我的饭量减少。所以我考试没有及格。试对上述论证构造证明。,解：设P：我考试及格,Q：我高兴。,R：我饭量增加。此论证可表为,前提1： PQ,前提2: QR,前提3: R,证明永真蕴涵成立:(PQ) (QR) R P,证明：方法1. 真值表法方法2. 命题演算法方法3. 范式法,常用证明方法:直接证明,推理规则方法:,1 PQ P,2 QR P,3 R P,4 Q T，2，3,5 P T，1，4,永真蕴涵式成
14、立:(PQ) (QR) R P,(PQ) (QR) R P,例2.证明 RS是前提CD，CR,DS的有效结论。 证明：1.CD P2.CR P 3.DS P 4.CD T，15.RC T，26.RS T，5，4，37.RS T，6,常用证明方法:直接证明,常用证明方法:直接证明,附加前提 规则CP:如果能从前提集合和R中推导出S来，那么就能够从前提集合推导出RS 即: 从前提集合证明条件式RS，就等价于证明从前提集合和R中推导出S来 这时，R也作为一种前提条件，称为附加前提,例3：证明：（AB C ) （BA)(DC) (AD)证： 1.AB C P2.BA P3.DC P4.A P，附加前提5.B C T，1，46.AB T，27.CD T，38.B T，4，69.C T，5，810. D T，7，911.AD ， CP,
