离散数学第三章 命题逻辑的推理理论PPT讲稿.ppt

《离散数学第三章 命题逻辑的推理理论PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《离散数学第三章 命题逻辑的推理理论PPT讲稿.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学第三章离散数学第三章 命题逻辑的推理理论命题逻辑的推理理论第1页，共25页，编辑于2022年，星期日13.1 推理的形式结构推理的形式结构定义定义3.1 设设A1,A2,Ak,B为命题公式为命题公式.若对于每组赋值，若对于每组赋值，A1 A2 Ak 为假，或当为假，或当A1 A2 Ak为真时，为真时，B也为真，也为真，则称由则称由前提前提A1,A2,Ak推出推出结论结论B的的推理推理是是有效的有效的或或正确正确的的,并称并称B是是有效结论有效结论.定理定理3.1 由命题公式由命题公式A1,A2,Ak 推推B的推理正确当且仅当的推理正确当且仅当A1 A2 AkB为重言式为重言式注意注意:

2、推理正确不能保证结论一定正确推理正确不能保证结论一定正确第2页，共25页，编辑于2022年，星期日2推理的形式结构推理的形式结构2.A1 A2 AkB 若推理正确若推理正确,记为记为A1 A2 Ak B3.前提：前提：A1,A2,Ak 结论：结论：B判断推理是否正确的方法判断推理是否正确的方法:真值表法真值表法 等值演算法等值演算法 主析取范式法主析取范式法推理的形式结构推理的形式结构1.A1,A2,Ak B 若推理正确若推理正确,记为记为A1,A2,An B第3页，共25页，编辑于2022年，星期日3推理实例推理实例例例1 判断下面推理是否正确判断下面推理是否正确(1)若今天是若今天是1号，

3、则明天是号，则明天是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可知推理正确可知推理正确第4页，共25页，编辑于2022年，星期日4推理实例推理实例(2)推理的形式结构推理的形式结构:(pq)qp 用主析取范式法用主析取范式法 (pq)qp (p q)qp (p q)q)p

4、q p (pq)(pq)(pq)(p q)m0 m2 m3 结果不含结果不含m1,故故01是成假赋值，所以推理不正确是成假赋值，所以推理不正确第5页，共25页，编辑于2022年，星期日5推理定律推理定律重言蕴涵式重言蕴涵式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 构造性二难构造性二难(特殊

5、形式特殊形式)9.(AB)(CD)(BD)(AC)破坏性二难破坏性二难每个等值式可产生两个推理定律每个等值式可产生两个推理定律如如,由由AA可产生可产生 AA 和和 AA第6页，共25页，编辑于2022年，星期日63.2 自然推理系统自然推理系统P定义定义3.2 一个一个形式系统形式系统 I 由下面四个部分组成：由下面四个部分组成：(1)非空的字母表，记作非空的字母表，记作 A(I).(2)A(I)中符号构造的合式公式集，记作中符号构造的合式公式集，记作 E(I).(3)E(I)中一些特殊的公式组成的公理集，记作中一些特殊的公式组成的公理集，记作 AX(I).(4)推理规则集，记作推理规则集，

6、记作 R(I).记记I=,其中其中是是 I 的的形式语言形式语言系统系统,是是 I 的的形式演算系统形式演算系统.形式系统一般分为两类：形式系统一般分为两类：自然推理系统自然推理系统:无公理无公理,即即AX(I)=公理推理系统公理推理系统 推出的结论是系统中的重言式推出的结论是系统中的重言式,称作称作定理定理第7页，共25页，编辑于2022年，星期日7自然推理系统自然推理系统P定义定义3.3 自然推理系统自然推理系统 P 定义定义如下如下:1.字母表字母表 (1)命题变项符号：命题变项符号：p,q,r,pi,qi,ri,(2)联结词符号：联结词符号：,(3)括号与逗号：括号与逗号：(,),，2

7、.合式公式（同定义合式公式（同定义1.6）3.推理规则推理规则:(1)(12)(1)前提引入规则前提引入规则:在证明的任何步骤都可以引入前提在证明的任何步骤都可以引入前提.(2)结论引入规则结论引入规则:在证明的任何步骤所得的结论都有可以在证明的任何步骤所得的结论都有可以作为后继证明的前提作为后继证明的前提.(3)置换规则置换规则:在证明的任何步骤在证明的任何步骤,命题公式中的子公式都可命题公式中的子公式都可以用等值的公式置换以用等值的公式置换,得到公式序列中又一个公式得到公式序列中又一个公式.第8页，共25页，编辑于2022年，星期日8推理规则推理规则(4)假言推理规则假言推理规则(6)化简

8、规则化简规则 (8)假言三段论规则假言三段论规则 AB AB AA B A B A(5)附加规则附加规则(7)拒取式规则拒取式规则 (9)析取三段论规则析取三段论规则 AB B A AB BCACA B BA第9页，共25页，编辑于2022年，星期日9推理规则推理规则(10)构造性二难推理规则构造性二难推理规则 (11)破坏性二难推理规则破坏性二难推理规则 (12)合取引入规则合取引入规则 AB CD A C B D AB CD BD A C A BA C第10页，共25页，编辑于2022年，星期日10在自然推理系统在自然推理系统P中构造证明中构造证明设前提设前提A1,A2,Ak,结论结论B及

9、公式序列及公式序列C1,C2,Cl.如果每如果每一个一个Ci(1 i l)是某个是某个Aj,或者可由序列中前面的公式应用推或者可由序列中前面的公式应用推理理规则得到规则得到,并且并且Cl=B,则称这个公式序列是由则称这个公式序列是由A1,A2,Ak推推出出B的的证明证明例例2 构造下面推理的证明：构造下面推理的证明：若明天是星期一或星期四，我明天就有课若明天是星期一或星期四，我明天就有课.若我明天有若我明天有 课，今天必备课课，今天必备课.我今天没备课我今天没备课.所以，明天不是星期一、所以，明天不是星期一、也不是星期四也不是星期四.解解 (1)设命题并符号化设命题并符号化 设设 p：明天是星

10、期一，：明天是星期一，q：明天是星期四，：明天是星期四，r：我明天有课，：我明天有课，s：我今天备课：我今天备课第11页，共25页，编辑于2022年，星期日11直接证明法直接证明法(2)写出证明的形式结构写出证明的形式结构 前提：前提：(p q)r,rs,s 结论：结论：pq(3)证明证明 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式 (p q)r 前提引入前提引入 (p q)拒取式拒取式 pq 置换置换第12页，共25页，编辑于2022年，星期日12附加前提证明法附加前提证明法附加前提证明法附加前提证明法 适用于结论为蕴涵式适用于结论为蕴涵式欲证欲证 前提：前提：A1,A2

11、,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)B第13页，共25页，编辑于2022年，星期日13附加前提证明法实例附加前提证明法实例例例3 构造下面推理的证明构造下面推理的证明 2是素数或合数是素数或合数.若若2是素数，则是素数，则 是无理数是无理数.若若 是无理是无理数，则数，则4不是素数不是素数.所以，如果所以，如果4是素数，则是素数，则2是合数是合数.解解 用附加前提证明法构造证明用附加前提证明法构造证明 (1)设设 p

12、：2是素数，是素数，q：2是合数，是合数，r：是无理数，是无理数，s：4是素数是素数 (2)推理的形式结构推理的形式结构 前提：前提：p q,pr,rs 结论：结论：sq 第14页，共25页，编辑于2022年，星期日14附加前提证明法实例附加前提证明法实例 (3)证明证明 s 附加前提引入附加前提引入 pr 前提引入前提引入 rs 前提引入前提引入 ps 假言三段论假言三段论 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段论析取三段论第15页，共25页，编辑于2022年，星期日15归谬法（反证法）归谬法（反证法）归谬法归谬法(反证法反证法)欲证欲证 前提：前提：A1,A2,Ak 结论

13、：结论：B做法做法 在前提中加入在前提中加入 B，推出矛盾，推出矛盾.理由理由 A1 A2 AkB (A1 A2 Ak)B (A1 A2 AkB)(A1 A2 AkB)0 A1 A2 AkB0第16页，共25页，编辑于2022年，星期日16归谬法实例归谬法实例例例4 前提：前提：(p q)r,rs,s,p 结论：结论：q证明证明 用归缪法用归缪法 q 结论否定引入结论否定引入 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式 (p q)r 前提引入前提引入 (p q)析取三段论析取三段论 pq 置换置换 p 析取三段论析取三段论 p 前提引入前提引入 p p 合取合取第17页，共

14、25页，编辑于2022年，星期日17第三章第三章 小结小结主要内容主要内容推理的形式结构推理的形式结构判断推理是否正确的方法判断推理是否正确的方法 真值表法真值表法 等值演算法等值演算法 主析取范式法主析取范式法推理定律推理定律自然推理系统自然推理系统P构造推理证明的方法构造推理证明的方法 直接证明法直接证明法 附加前提证明法附加前提证明法 归谬法归谬法(反证法反证法)第18页，共25页，编辑于2022年，星期日18基本要求基本要求理解并记住推理形式结构的两种形式：理解并记住推理形式结构的两种形式：1.(A1 A2 Ak)B 2.前提：前提：A1,A2,Ak 结论：结论：B熟练掌握判断推理是否

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

16、等值演算法 (pq)qp (p q)q)p (pq)qp (p q)(q q)p p q易知易知10是成假赋值，不是重言式，所以推理不正确是成假赋值，不是重言式，所以推理不正确.第20页，共25页，编辑于2022年，星期日20练习练习1解答解答方法二：主析取范式法，方法二：主析取范式法，(pq)qp (p q)q)p p q M2 m0 m1 m3未含未含m2,不是重言式不是重言式,推理不正确推理不正确.第21页，共25页，编辑于2022年，星期日21练习练习1解答解答方法三方法三 真真值值表法表法 不是重言式不是重言式,推理不正确推理不正确111001110100(pq)qpqp pq 0

17、1 1 1(pq)q 0 0 1 0方法四方法四 直接直接观观察出察出10是成假是成假赋值赋值第22页，共25页，编辑于2022年，星期日22练习练习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)第23页，共25页，编辑于2022年，星期日23练习练习2：构造证明：构造证明2.在系统在系统P中构造下面推理的证明：中构造下面推理的

18、证明：如果今天是星期六，我们就到颐和园或圆明园去玩如果今天是星期六，我们就到颐和园或圆明园去玩.如果如果颐和园游人太多，我们就不去颐和园玩颐和园游人太多，我们就不去颐和园玩.今天是星期六今天是星期六.颐颐和园游人太多和园游人太多.所以所以,我们去圆明园或动物园玩我们去圆明园或动物园玩.证明证明：(1)设设 p：今天是周六，：今天是周六，q：到颐和园玩，：到颐和园玩，r：到圆明园玩，：到圆明园玩，s：颐和园游人太多：颐和园游人太多 t：到动物园玩：到动物园玩 (2)前提：前提：p(q r),sq,p,s 结论：结论：r t第24页，共25页，编辑于2022年，星期日24练习练习2解答解答(3)证明：证明：p(q r)前提引入前提引入 p 前提引入前提引入 q r 假言推理假言推理 sq 前提引入前提引入 s 前提引入前提引入 q 假言推理假言推理 r 析取三段论析取三段论 r t 附加附加前提：前提：p(q r),sq,p,s结论：结论：r t第25页，共25页，编辑于2022年，星期日25