命题逻辑的推理理论,证明方法.ppt

命题逻辑的推理理论,证明方法.ppt

ID:52205179

大小:291.76 KB

页数:43页

时间:2020-04-02

命题逻辑的推理理论,证明方法.ppt_第1页
命题逻辑的推理理论,证明方法.ppt_第2页
命题逻辑的推理理论,证明方法.ppt_第3页
命题逻辑的推理理论,证明方法.ppt_第4页
命题逻辑的推理理论,证明方法.ppt_第5页
资源描述:

《命题逻辑的推理理论,证明方法.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、.武汉大学国际软件学院唐存琛刘峰12.4命题逻辑推理理论2.4.1推理的形式结构推理及其形式结构推理定律2.4.2自然推理系统P自然推理系统的定义证明方法.武汉大学国际软件学院唐存琛刘峰22.4.1推理的形式结构一、什么是推理定义2.19设A1,A2,…,Ak,B都是命题公式,若对于每组赋值,A1A2…Ak为假,或者当A1A2…Ak为真时,B也为真,则称由前提A1,A2,…,Ak推B的推理有效或推理正确,并称B是有效的结论。.武汉大学国际软件学院唐存琛刘峰3定理2.8由前提A1,A2,…,Ak推出B的推理正确当且仅当A1A2…AkB为重言式.如果

2、把(A1A2…Ak)B为永真式记为:上式的含义???.武汉大学国际软件学院唐存琛刘峰4二、推理的形式结构定义2.20称(A1A2…Ak)B为由前提A1,A2,…,Ak推结论B的推理的形式结构。推理的形式结构一般有以下三种:形式(1)A1A2…AkB形式(2)前提:A1,A2,…,Ak结论:B形式(3)A1,A2,…,AkB.武汉大学国际软件学院唐存琛刘峰5真值表法等值演算法主析取范式法构造证明法判断推理是否正确的方法:真值表的方法参见P.67例2.23。.武汉大学国际软件学院唐存琛刘峰6例1判断下面推理是否正确:(1)若今天是1号,则明天是

3、5号.今天是1号.所以,明天是5号.解设p:今天是1号,q:明天是5号推理的形式结构为证明用等值演算法所以,原推理正确。.武汉大学国际软件学院唐存琛刘峰7例1(2)若今天是1号,则明天是5号.明天是5号.所以,今天是1号。解设p:今天是1号,q:明天是5号推理的形式结构为证明用主析取范式法这不是一个永真式,01是该公式成假的赋值,所以推理不正确。.武汉大学国际软件学院唐存琛刘峰8三、推理规则1、推理规则的定义是一个推理规则,当且仅当,其中,A1,A2,…,An称为推理规则的前提,B称为推理规则的结论。.武汉大学国际软件学院唐存琛刘峰91)附加规则2)化简规则3)MP

4、规则(假言推理)4)拒取式2、常用的推理规则.武汉大学国际软件学院唐存琛刘峰105)析取三段论6)假言三段论7)合取引入8)构造性二难2、常见的推理规则(续).武汉大学国际软件学院唐存琛刘峰11注意:(1)推理规则中出现的A、B、C等是元语言符号;(2)直接引用而不需证明,只要说明所引用规则的名称;(3)24个永真公式每个都可以等效为2个推理规则。.武汉大学国际软件学院唐存琛刘峰122.4.2自然推理系统P自然推理系统P由下述3部分组成:1.字母表(1)命题变项符号:p,q,r,…,pi,qi,ri,…(2)联结词:,,,,(3)括号与逗号:(),,2.合

5、式公式一、自然推理系统P的定义.武汉大学国际软件学院唐存琛刘峰133.推理规则(1)前提引入规则(2)结论引入规则(3)置换规则(4)假言推理规则(5)附加规则(6)化简规则一、自然推理系统P的定义(续)(7)拒取式规则(8)假言三段论规则(9)析取三段论规则(10)构造性二难推理规则(11)破坏性二难推理规则(12)合取引入规则.武汉大学国际软件学院唐存琛刘峰14[证]例2证明前提前提①、②,假言三段前提③、④,拒取式①②③④⑤.武汉大学国际软件学院唐存琛刘峰15二、证明方法用推理的概念说明一些证明方法的正确性。为了证明,只需证明A永假即可。(2)后件真证明法为了

6、证明,只需证明B永真即可。(1)前件假证明法.武汉大学国际软件学院唐存琛刘峰16(3)直接证明法为了证明,只需证明若A为真,则B亦为真。为了证明,只需证明若B为假,则A亦为假。(4)间接证明法.武汉大学国际软件学院唐存琛刘峰17(5)分情况证明法只需证明对任意的,均有。为了证明,(6)附加前提证明法只需证明为了证明,.武汉大学国际软件学院唐存琛刘峰18附加前提证明法的说明:理由:(A1ÙA2Ù…ÙAk)®(C®B)ÛØ(A1ÙA2Ù…ÙAk)Ú(ØCÚB)ÛØ(A1ÙA2Ù…ÙAkÙC)ÚBÛ(A1ÙA2Ù…ÙAkÙC)®B欲证明等价地证明前提:A1,A2,…,Ak

7、前提:A1,A2,…,Ak,C结论:C®B结论:B.武汉大学国际软件学院唐存琛刘峰19不相容的概念:定义——若是可满足式,则称公式集是相容的(或一致的),否则,称之为不相容的。.武汉大学国际软件学院唐存琛刘峰20(7)反证法(归谬法)为了证明即证明是永假式只需证明是不相容的.武汉大学国际软件学院唐存琛刘峰21归谬法(反证法)的说明理由:A1ÙA2Ù…ÙAk®BÛØ(A1ÙA2Ù…ÙAk)ÚBÛØ(A1ÙA2Ù…ÙAkÙØB)括号内部为矛盾式当且仅当(A1ÙA2Ù…ÙAk®B)为重言式欲证明前提:A1,A2,…,Ak结论:B将ØB加入前提,若推出矛盾,则得证推理正

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。