离散数学：第三章 命题逻辑的推理理论

《离散数学：第三章 命题逻辑的推理理论》由会员分享，可在线阅读，更多相关《离散数学：第三章 命题逻辑的推理理论（36页珍藏版）》请在装配图网上搜索。

1、 第一节：推理的形式结构第一节：推理的形式结构l 推理的正确与错误推理的正确与错误l 推理的形式结构推理的形式结构l 判断推理正确的方法判断推理正确的方法l 推理定律推理定律 第二节：自然推理系统第二节：自然推理系统P Pl 形式系统的定义与分类形式系统的定义与分类l 自然推理系统自然推理系统P Pl 在在P P中构造证明中构造证明:直接证明法、附加前提证明法、归直接证明法、附加前提证明法、归谬法谬法1 1计算机科学与工程学院计算机科学与工程学院n逻辑逻辑(语义语义)蕴涵：给定命题公式蕴涵：给定命题公式A A1 1,A Ak k和和B B 对任意赋值对任意赋值v v:如果如果v v(A(Ai

2、i)=T,)=T,则则v v(B)=T(B)=T或者存在或者存在A Ai i使得使得v v(A(Ai i)=F)=F 称由前提称由前提A A1 1,A Ak k 推出结论推出结论B B的推理是的推理是有效的有效的 B B为有效结论为有效结论 符号：符号：A A1 1,A Ak k B Bn讨论讨论 蕴涵跟蕴涵式的关系？蕴涵跟蕴涵式的关系？注意注意:推理正确不能保证结论一定正确推理正确不能保证结论一定正确2 2计算机科学与工程学院计算机科学与工程学院pqp(pq)qp(q p)qFFFFFFFTFTFTTFFFTFTTTTTTn 例子：判断推理是否正确例子：判断推理是否正确 p p,p p q

3、q q q？p p,q q p p q q？3 3计算机科学与工程学院计算机科学与工程学院n定理：定理：A A1 1,A Ak k B B 当且仅当当且仅当 A A1 1 A Ak k B B 为重言式为重言式证明证明:必要性必要性：任意：任意v v,若若v v(A(Ai i)=T)=T，则，则v v(B)=T(B)=T 所以所以v v(A(A1 1 A Ak k B)=TB)=T 充分性充分性：任意：任意v v,v v(A(A1 1 A Ak k B)=TB)=T 如果如果v v(A(Ai i)=T)=T，则，则v v(B)=T(B)=T4 4计算机科学与工程学院计算机科学与工程学院n蕴涵元

4、语言符号：蕴涵元语言符号：nA1 Ak B 代表代表 A1,Ak Bn推理形式结构推理形式结构前提：前提：A1,Ak结论：结论：B5 5计算机科学与工程学院计算机科学与工程学院n 判断推理是否正确方法判断推理是否正确方法真值表法真值表法等值演算法等值演算法主析取范式法主析取范式法6 6计算机科学与工程学院计算机科学与工程学院7 7例例1 1 判断下面推理是否正确判断下面推理是否正确(1)(1)若今天是若今天是1 1号，则明天是号，则明天是5 5号号.今天是今天是1 1号号.所以所以,明天明天是是5 5号号.(2)(2)若今天是若今天是1 1号，则明天是号，则明天是5 5号号.明天是明天是5 5

5、号号.所以所以,今天今天是是1 1号号.计算机科学与工程学院计算机科学与工程学院解解 设设 p p：今天是：今天是1 1号，号，q q：明天是：明天是5 5号号.(1)(1)推理的形式结构推理的形式结构:(pq)pq用等值演算法用等值演算法 (p pq q)p pq q (p p q q)p p)q q p pq q q q 1 1由由定理定理3.13.1可知推理正确可知推理正确或者，前提或者，前提：pq,p 结论：结论：q 8 8(2)(2)推理的形式结构推理的形式结构:(pq)qp 用用主析取范式法主析取范式法 (p pq q)q qp p (p p q q)q qp p (p p q q

6、)q q)p p q q p p (p pq q)(p pq q)(p pq q)(p p q q)m m0 0 m m2 2 m m3 3 结果结果不含不含m m1 1,故故0101是成假赋值，所以推理不正确是成假赋值，所以推理不正确计算机科学与工程学院计算机科学与工程学院 推理定律推理定律A A (A A B B)(A A B B)A A(A A B B)A A B B(A A B B)B B A A(A A B B)B B A A(A A B B)(B B C C)(A A C C)(A A B B)(B B C C)(A A C C)(A A B B)(C C D D)(A A C C

7、)(B B D D)(A A B B)(A A B B)B B(A A B B)(C C D D)(B B D D)(A A C C)附加律破坏性二难构造性二难（特殊形式）构造性二难等价三段论假言三段论析取三段论拒取式假言推理化简律9 9计算机科学与工程学院计算机科学与工程学院 推理定律推理定律计算机科学与工程学院计算机科学与工程学院1010A (A B)(A B)A(A B)A B(A B)B A(A B)B A(A B)(B C)(A C)(A B)(B C)(A C)(A B)(C D)(A C)(B D)(A B)(A B)B(A B)(C D)(B D)(A C)附加律破坏性二难构造

8、性二难（特殊形式）构造性二难等价三段论假言三段论假言三段论析取三段论拒取式假言推理化简律证明：证明：(A(A B)B)(B(B C)C)(A(A C)C)(A (A B)B)(B(B C)C)(A(A C)C)(A A B)B)(B B C)C)(A(A C)C)(A A B)B)(B B C)C)(A(A C)C)(A(A B)B)(B(B C)C)(A(A C)C)(A(A B)B)(B(B C)C)(A A C)C)(A(A B)B)A)A)(B(B C)C)C)C)(B B A)A)(B(B C)C)T T计算机科学与工程学院计算机科学与工程学院1111从一组从一组已知为真的已知为真的

9、事实出发，直接运用经典逻辑事实出发，直接运用经典逻辑推理规则推理规则推出结论的过程推出结论的过程为什么要自然演绎为什么要自然演绎(natural deduction)？给出验证给出验证 的推理过程的推理过程需要引入需要引入证明证明的概念的概念自然演绎模拟人类的推理自然演绎模拟人类的推理A1Ak B1212计算机科学与工程学院计算机科学与工程学院定义定义3.2 3.2 一个形式系统一个形式系统 I I 由下面四个部分组成：由下面四个部分组成：(1)(1)非空的非空的字母表字母表，记作，记作 A A(I I).(2)(2)A A(I I)中符号构造的合式中符号构造的合式公式集公式集，记作，记作 E

10、 E(I I).(3)(3)E E(I I)中一些特殊的公式组成的中一些特殊的公式组成的公理集公理集，记作，记作 A AX X(I I).(4)(4)推理规则集推理规则集，记作，记作 R R(I I).记记I I=,),其中其中)是是 I I 的的形形式语言系统式语言系统,)是是 I I 的的形式演算系统形式演算系统.自然推理系统自然推理系统:无公理集无公理集,即即A AX X(I I)=)=公理推理系统公理推理系统 推出的结论是系统中的重言式推出的结论是系统中的重言式,称作称作定理定理1313计算机科学与工程学院计算机科学与工程学院n 定义定义3.3 3.3 自然推理系统自然推理系统 P P

11、 定义如下定义如下:1.1.字母表字母表 (1)(1)命题变项符号：命题变项符号：p p,q q,r r,p pi i,q qi i,r ri i,(2)(2)联结词符号：联结词符号：,(3)(3)括号与逗号：括号与逗号：(,),(,),，2.2.合式公式（同定义合式公式（同定义1.61.6）3.3.推理规则推理规则 (1)(1)前提引入规则前提引入规则 (2)(2)结论引入规则结论引入规则 (3)(3)置换规则置换规则1414计算机科学与工程学院计算机科学与工程学院 假言推理规则假言推理规则 A B A 结论：结论：B 如果苏格拉底是人，则苏格拉底会死如果苏格拉底是人，则苏格拉底会死 苏格拉

12、底是人苏格拉底是人 苏格拉底会死苏格拉底会死(A B)A B1515计算机科学与工程学院计算机科学与工程学院n 附加规则附加规则 A 结论：结论：A BA (A B)1616计算机科学与工程学院计算机科学与工程学院n 化简规则化简规则 A B 结论结论：A n 合取引入规则合取引入规则 A B 结论结论：A B (A B)A1717计算机科学与工程学院计算机科学与工程学院 证明证明 p,q,p q r r p q p q p q r r推理过程可以写成证明树推理过程可以写成证明树1818计算机科学与工程学院计算机科学与工程学院 拒取式规则拒取式规则 A B B 结论结论：A 假言三段式规则假言

13、三段式规则 A B B C 结论结论：A C(A B)B A(A B)(B C)(A C)1919计算机科学与工程学院计算机科学与工程学院 析取三段式规则析取三段式规则 A B B 结论结论：A 构造二难推理规则构造二难推理规则 A B C D A C 结论结论：B D(A B)B A(A B)(C D)(A C)(B D)2020计算机科学与工程学院计算机科学与工程学院n 破坏性二难推理规则破坏性二难推理规则 A B C D B D 结论结论：A C(A B)(C D)(B D)(A C)2121计算机科学与工程学院计算机科学与工程学院n 形式推演形式推演(语法蕴涵语法蕴涵)：给定：给定A

14、A1 1,A Ak k和和B B 符号：符号：A A1 1,A Ak k B B 存在公式序列存在公式序列C C1 1,C C2 2,C Cn n，对每个，对每个i i(i i=1,=1,n n),),C Ci i是某个是某个A Aj j或者或者C Ci i是由序列中前面的公式应用推理规则得到是由序列中前面的公式应用推理规则得到C Cn n=B=B 称称C C1 1,C Cn n是由是由A A1 1,A Ak k 推推B B 的的证明证明 2222计算机科学与工程学院计算机科学与工程学院：考虑下述论证：考虑下述论证 如果这里有球赛，则通行是困难的如果这里有球赛，则通行是困难的 如果他们按时到达

15、，则通行是不困难的如果他们按时到达，则通行是不困难的 他们按时到达了他们按时到达了 所以这里没有球赛所以这里没有球赛设设p p:这里有球赛这里有球赛 q q:通行是困难的通行是困难的 r r:他们按时到他们按时到达达 p p q q r r q q r r p p 2323计算机科学与工程学院计算机科学与工程学院 前提前提p q，r q，r 结论：结论：p 解解：r r q q p q p 前提引入前提引入前提引入前提引入假言推理假言推理前提引入前提引入拒取式拒取式2424计算机科学与工程学院计算机科学与工程学院c d,c r,d s r s 解解：c d c d d s c s c r r

16、c r s r s计算机科学与工程学院计算机科学与工程学院2525 前提引入前提引入前提引入前提引入假言三段论假言三段论前提引入前提引入置换规则置换规则置换规则置换规则假言三段论假言三段论置换规则置换规则n 构造证明的方法构造证明的方法 附加前提证明法附加前提证明法 归谬法归谬法 2626计算机科学与工程学院计算机科学与工程学院n 附加前提证明法附加前提证明法 对形如对形如 (A A1 1 A Ak k)(A A B B)的证明的证明 转化为：转化为：A1,Ak,A B2727计算机科学与工程学院计算机科学与工程学院(p(q s)(rp)q)(r s)解解：r r p r p p p(q s)

17、q s q s 附加前提附加前提引入引入前提引入前提引入假言推理假言推理前提引入前提引入置换规则置换规则假言推理假言推理假言推理假言推理前提引入前提引入2828计算机科学与工程学院计算机科学与工程学院 归谬法归谬法 对形如对形如 (A A1 1 A Ak k)B B的证明的证明 转化为：转化为：A1 Ak B为矛盾式为矛盾式2929计算机科学与工程学院计算机科学与工程学院n 证明证明rq rs sq pq p解解：p p q q s q q s s rs r rq q3030计算机科学与工程学院计算机科学与工程学院公理推理系统公理推理系统 命题变项符号命题变项符号 合式公式合式公式 公理集合公

18、理集合 推理规则推理规则 A A B B A A 结论：结论：B B 又称又称MPMP（modus ponensmodus ponens）规则）规则 3131计算机科学与工程学院计算机科学与工程学院 公理集合公理集合 A A (B B A A)(A A (B B C C)(A A B B)(A A C C)(A A B B)(A A B B)A A)3232计算机科学与工程学院计算机科学与工程学院 形式推演形式推演(语法蕴涵语法蕴涵)：给定给定B B 存在公式序列存在公式序列C C1 1,C C2 2,C Cn n，对每个，对每个i i (i i=1,=1,n n),),C Ci i是某个公理

19、或者是某个公理或者存在存在k k,j j i i,C Cj j =C Ck k C Ci iC Cn n=B=B 称称C C1 1,C Cn n是定理是定理B B的证明的证明 符号：符号：B B 3333计算机科学与工程学院计算机科学与工程学院 命题演算的可靠性命题演算的可靠性 A A1 1,A Ak k B B A A1 1,A Ak k B B 命题演算的完备性命题演算的完备性 A A1 1,A Ak k B B A A1 1,A Ak k B B3434计算机科学与工程学院计算机科学与工程学院n 主要内容主要内容 推理的形式结构推理的形式结构 判断推理是否正确的方法判断推理是否正确的方法

20、 真值表法真值表法 等值演算法等值演算法 主析取范式法主析取范式法 推理定律推理定律 自然推理系统自然推理系统P P 构造推理证明的方法构造推理证明的方法 直接证明法直接证明法 附加前提证明法附加前提证明法 归谬法归谬法(反证法反证法)3535计算机科学与工程学院计算机科学与工程学院36理解并记住推理形式结构的两种形式：理解并记住推理形式结构的两种形式：1.(1.(A A1 1 A A2 2 A Ak k)B B 2.2.前提：前提：A A1 1,A A2 2,A Ak k 结论：结论：B B熟练掌握判断推理是否正确的不同方法（如真熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）值表法、等值演算法、主析取范式法等）牢记牢记 P P 系统中各条推理规则系统中各条推理规则熟练掌握构造证明的直接证明法、附加前提证熟练掌握构造证明的直接证明法、附加前提证明法和归谬法明法和归谬法会解决实际中的简单推理问题会解决实际中的简单推理问题计算机科学与工程学院计算机科学与工程学院