屈婉玲离散数学第三章讲解学习.ppt

《屈婉玲离散数学第三章讲解学习.ppt》由会员分享，可在线阅读，更多相关《屈婉玲离散数学第三章讲解学习.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、屈婉玲离散数学第三章推理的形式结构推理的形式结构2.A1 A2 AkB 若推理正确若推理正确,记为记为A1 A2 Ak B3.前提：前提：A1,A2,Ak 结论：结论：B判断推理是否正确的方法判断推理是否正确的方法:真值表法（见例子真值表法（见例子3.1）等值演算法（见例子等值演算法（见例子3.2）主析取范式法（见例子主析取范式法（见例子3.2）由由A1,A2,Ak推推B的的推理有以下的形式结构：推理有以下的形式结构：1.A1,A2,Ak B 若推理正确若推理正确,记为记为A1,A2,An B2推理实例推理实例例例1 判断下面推理是否正确判断下面推理是否正确(1)若今天是若今天是1号，则明天是

2、号，则明天是5号号.今天是今天是1号号.所以所以,明天是明天是5号号.(2)若今天是若今天是1号，则明天是号，则明天是5号号.明天是明天是5号号.所以所以,今天是今天是1号号.解解 设设 p：今天是：今天是1号，号，q：明天是：明天是5号号.(1)推理的形式结构推理的形式结构:(pq)pq用等值演算法用等值演算法 (pq)pq (p q)p)q pq q 1 由定理由定理3.1可知推理正确可知推理正确3推理实例推理实例(2)推理的形式结构推理的形式结构:(pq)qp 用主析取范式法用主析取范式法 (pq)qp (p q)qp (p q)q)p q p (pq)(pq)(pq)(p q)m0 m

3、2 m3 结果不含结果不含m1,故故01是成假赋值，所以推理不正确是成假赋值，所以推理不正确4推理定律推理定律重言蕴涵式重言蕴涵式1.A (A B)附加律附加律 2.(A B)A 化简律化简律3.(AB)A B 假言推理假言推理4.(AB)B A 拒取式拒取式 5.(A B)B A 析取三段论析取三段论6.(AB)(BC)(AC)假言三段论假言三段论7.(AB)(BC)(AC)等价三段论等价三段论8.(AB)(CD)(A C)(B D)构造性二难构造性二难 (AB)(AB)B 构造性二难构造性二难(特殊形式特殊形式)9.(AB)(CD)(BD)(AC)破坏性二难破坏性二难每个等值式可产生两个推

4、理定律每个等值式可产生两个推理定律如如,由由AA可产生可产生 AA 和和 AA53.2 自然推理系统自然推理系统P定义定义3.2 一个一个形式系统形式系统 I 由下面四个部分组成：由下面四个部分组成：(1)非空的字母表，记作非空的字母表，记作 A(I).(2)A(I)中符号构造的合式公式集，记作中符号构造的合式公式集，记作 E(I).(3)E(I)中一些特殊的公式组成的公理集，记作中一些特殊的公式组成的公理集，记作 AX(I).(4)推理规则集，记作推理规则集，记作 R(I).记记I=,其中其中是是 I 的的形式语言系统形式语言系统,是是 I 的的形式演算系统形式演算系统.自然推理系统自然推理

5、系统:无公理无公理,即即AX(I)=公理推理系统公理推理系统 推出的结论是系统中的重言式推出的结论是系统中的重言式,称作称作定理定理本节对本节对由由A1,A2,Ak推推B的正确的正确推理的证明给出严格的形推理的证明给出严格的形式描述式描述6自然推理系统自然推理系统P定义定义3.3 自然推理系统自然推理系统 P 定义定义如下如下:1.字母表字母表 (1)命题变项符号：命题变项符号：p,q,r,pi,qi,ri,(2)联结词符号：联结词符号：,(3)括号与逗号：括号与逗号：(,),，2.合式公式（同定义合式公式（同定义1.6）3.推理规则推理规则 (1)前提引入规则：前提引入规则：在证明的任何步骤

6、都可引入前提在证明的任何步骤都可引入前提 (2)结论引入规则：结论引入规则：在证明的任何步骤得到的结论都可以做在证明的任何步骤得到的结论都可以做 为后续证明的前提为后续证明的前提 (3)置换规则：置换规则：在证明的任何步骤，命题公式中的子公式都在证明的任何步骤，命题公式中的子公式都 可用等值的公式置换，得到公式序列中又可用等值的公式置换，得到公式序列中又 一个公式一个公式7推理规则推理规则(4)假言推理规则假言推理规则(6)化简规则化简规则 (8)假言三段论规则假言三段论规则 AB AB AA B A B A(5)附加规则附加规则(7)拒取式规则拒取式规则 (9)析取三段论规则析取三段论规则

7、AB B A AB BCACA B BA8推理规则推理规则(10)构造性二难推理规则构造性二难推理规则 (11)破坏性二难推理规则破坏性二难推理规则 (12)合取引入规则合取引入规则 AB CD A C B D AB CD BD A C A BA C9在自然推理系统在自然推理系统P中构造证明中构造证明设前提设前提A1,A2,Ak,结论结论B及公式序列及公式序列C1,C2,Cl.如果每如果每一个一个Ci(1 i l)是某个是某个Aj,或者可由序列中前面的公式应用推或者可由序列中前面的公式应用推理理规则得到规则得到,并且并且Cl=B,则称这个公式序列是由则称这个公式序列是由A1,A2,Ak推推出出

8、B的的证明证明见例子见例子3.3/3.4例例2 构造下面推理的证明：构造下面推理的证明：若明天是星期一或星期三，我明天就有课若明天是星期一或星期三，我明天就有课.若我明天有若我明天有 课，今天必备课课，今天必备课.我今天没备课我今天没备课.所以，明天不是星期一、所以，明天不是星期一、也不是星期三也不是星期三.解解 (1)设命题并符号化设命题并符号化 设设 p：明天是星期一，：明天是星期一，q：明天是星期三，：明天是星期三，r：我明天有课，：我明天有课，s：我今天备课：我今天备课10直接证明法直接证明法(2)写出证明的形式结构写出证明的形式结构 前提：前提：(p q)r,rs,s 结论：结论：p

9、q(3)证明证明 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式 (p q)r 前提引入前提引入 (p q)拒取式拒取式 pq 置换置换11附加前提证明法附加前提证明法附加前提证明法附加前提证明法 适用于结论为蕴涵式适用于结论为蕴涵式欲证欲证 前提：前提：A1,A2,Ak 结论：结论：CB等价地证明等价地证明 前提：前提：A1,A2,Ak,C 结论：结论：B理由：理由：(A1 A2 Ak)(CB)(A1 A2 Ak)(C B)(A1 A2 Ak C)B (A1 A2 Ak C)B12附加前提证明法实例附加前提证明法实例例例3 构造下面推理的证明构造下面推理的证明 2是素数或合数

10、是素数或合数.若若2是素数，则是素数，则 是无理数是无理数.若若 是无理是无理数，则数，则4不是素数不是素数.所以，如果所以，如果4是素数，则是素数，则2是合数是合数.解解 用附加前提证明法构造证明用附加前提证明法构造证明 (1)设设 p：2是素数，是素数，q：2是合数，是合数，r：是无理数，是无理数，s：4是素数是素数 (2)推理的形式结构推理的形式结构 前提：前提：p q,pr,rs 结论：结论：sq 13附加前提证明法实例附加前提证明法实例 (3)证明证明 s 附加前提引入附加前提引入 pr 前提引入前提引入 rs 前提引入前提引入 ps 假言三段论假言三段论 p 拒取式拒取式 p q

11、前提引入前提引入 q 析取三段论析取三段论14归谬法（反证法）归谬法（反证法）归谬法归谬法(反证法反证法)欲证欲证 前提：前提：A1,A2,Ak 结论：结论：B做法做法 在前提中加入在前提中加入 B，推出矛盾，推出矛盾.理由理由 A1 A2 AkB (A1 A2 Ak)B (A1 A2 AkB)(A1 A2 AkB)0 A1 A2 AkB015归谬法实例归谬法实例例例4 前提：前提：(p q)r,rs,s,p 结论：结论：q证明证明 用归缪法用归缪法 q 结论否定引入结论否定引入 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式 (p q)r 前提引入前提引入 (p q)析取三段

12、论析取三段论 pq 置换置换 p 析取三段论析取三段论 p 前提引入前提引入 p p 合取合取16第三章第三章 习题课习题课主要内容主要内容l推理的形式结构推理的形式结构l判断推理是否正确的方法判断推理是否正确的方法 真值表法真值表法 等值演算法等值演算法 主析取范式法主析取范式法l推理定律推理定律l自然推理系统自然推理系统Pl构造推理证明的方法构造推理证明的方法 直接证明法直接证明法 附加前提证明法附加前提证明法 归谬法归谬法(反证法反证法)17基本要求基本要求l理解并记住推理形式结构的两种形式：理解并记住推理形式结构的两种形式：1.(A1 A2 Ak)B 2.前提：前提：A1,A2,Ak

13、结论：结论：Bl熟练掌握判断推理是否正确的不同方法（如真值表法、等熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）值演算法、主析取范式法等）l牢记牢记 P 系统中各条推理规则系统中各条推理规则l熟练掌握构造证明的直接证明法、附加前提证明法和归谬熟练掌握构造证明的直接证明法、附加前提证明法和归谬 法法l会解决实际中的简单推理问题会解决实际中的简单推理问题18练习练习1：判断推理是否正确：判断推理是否正确1.判断下面推理是否正确判断下面推理是否正确:(1)前提：前提：pq,q 结论：结论：p 解解 推理的形式结构推理的形式结构:(pq)qp 方法一：等值演算法方法一：等

14、值演算法 (pq)qp (p q)q)p (pq)qp (p q)(q q)p p q易知易知10是成假赋值，不是重言式，所以推理不正确是成假赋值，不是重言式，所以推理不正确.19练习练习1解答解答方法二：主析取范式法，方法二：主析取范式法，(pq)qp (p q)q)p p q M2 m0 m1 m3未含未含m2,不是重言式不是重言式,推理不正确推理不正确.20练习练习1解答解答方法三方法三 真真值值表法表法 不是重言式不是重言式,推理不正确推理不正确111001110100(pq)qpqp pq 0 1 1 1(pq)q 0 0 1 0方法四方法四 直接直接观观察出察出10是成假是成假赋值

15、赋值21练习练习1解答解答用等值演算法用等值演算法 (qr)(pr)(qp)(q r)(pr)(qp)(qr)(p r)(qp)(q p)(q r)(r p)(qp)(q p)(q r)(r p)(qp)1推理正确推理正确(2)前提：前提：qr,pr 结论：结论：qp 解解 推理的形式结构：推理的形式结构：(qr)(pr)(qp)22练习练习2：构造证明：构造证明2.在系统在系统P中构造下面推理的证明：中构造下面推理的证明：如果今天是周六，我们就到颐和园或圆明园玩如果今天是周六，我们就到颐和园或圆明园玩.如果颐和如果颐和 园游人太多，就不去颐和园园游人太多，就不去颐和园.今天是周六，并且颐和园

16、游今天是周六，并且颐和园游 人太多人太多.所以所以,我们去圆明园或动物园玩我们去圆明园或动物园玩.证明证明：(1)设设 p：今天是周六，：今天是周六，q：到颐和园玩，：到颐和园玩，r：到圆明园玩，：到圆明园玩，s：颐和园游人太多：颐和园游人太多 t：到动物园玩：到动物园玩 (2)前提：前提：p(q r),sq,p,s 结论：结论：r t23练习练习2解答解答(3)证明：证明：p(q r)前提引入前提引入 p 前提引入前提引入 q r 假言推理假言推理 sq 前提引入前提引入 s 前提引入前提引入 q 假言推理假言推理 r 析取三段论析取三段论 r t 附加附加24此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢