资源描述：
《命题逻辑推理理论-离散数学.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2.4命题逻辑推理理论2.4.1推理的形式结构推理及其形式结构推理定律2.4.2自然推理系统P自然推理系统的定义证明方法12.4.1推理的形式结构一、什么是推理定义2.19设A1，A2，…，Ak，B都是命题公式，若对于每组赋值,A1A2…Ak为假,或者当A1A2…Ak为真时，B也为真,则称由前提A1，A2，…,Ak推B的推理有效或推理正确,并称B是有效的结论。2定理2.8由前提A1,A2,…,Ak推出B的推理正确当且仅当A1A2…AkB为重言式.如果把（A1A2…Ak）B为永真式记为：上式的含
2、义？？？3二、推理的形式结构定义2.20称（A1A2…Ak）B为由前提A1,A2,…,Ak推结论B的推理的形式结构。推理的形式结构一般有以下三种：形式(1)A1A2…AkB形式(2)前提:A1,A2,…,Ak结论:B形式(3)A1，A2，…，AkB4真值表法等值演算法主析取范式法构造证明法判断推理是否正确的方法:真值表的方法参见P.67例2.23。5例1判断下面推理是否正确:(1)若今天是1号,则明天是5号.今天是1号.所以,明天是5号.解设p:今天是1号,q:明天是5号推理的形式结构为证明用等值演算法
3、所以，原推理正确。6例1(2)若今天是1号,则明天是5号.明天是5号.所以,今天是1号。解设p:今天是1号,q:明天是5号推理的形式结构为证明用主析取范式法这不是一个永真式，01是该公式成假的赋值，所以推理不正确。7三、推理定律——重言蕴涵式AÞ(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)Ù(Ø
4、A®B)ÞB构造性二难(特殊形式)(A®B)Ù(C®D)Ù(ØBÚØD)Þ(ØAÚØC)破坏性二难8注意：（1）推理规则中出现的A、B、C等是元语言符号；（2）直接引用而不需证明，只要说明所引用规则的名称；（3）24个永真公式每个都可以等效为2个推理规则。92.4.2自然推理系统P自然推理系统P由下述3部分组成:1.字母表(1)命题变项符号:p,q,r,…,pi,qi,ri,…(2)联结词:,,,,(3)括号与逗号:(),,2.合式公式3.推理规则(1)前提引入规则(2)结论引入规则(3)置换规则10自然推理系
5、统P(续)(7)拒取式规则A®BØBØA(8)假言三段论规则A®BB®CA®C(4)假言推理规则A®BAB(5)附加规则AAÚB(6)化简规则AÙBA11自然推理系统P(续)(11)破坏性二难推理规则A®BC®DØBÚØDØAÚØC(12)合取引入规则ABAÙB(9)析取三段论规则AÚBØBA(10)构造性二难推理规则A®BC®DAÚCBÚD12直接证明法例2在自然推理系统P中构造下面推理的证明:前提:pÚq,q®r,p®s,Øs结论:rÙ(pÚq)证明①p®s前提引入②Øs前提引入③Øp①②拒取式④p
6、Úq前提引入⑤q③④析取三段论⑥q®r前提引入⑦r⑤⑥假言推理⑧rÙ(pÚq)⑦④合取推理正确,rÙ(pÚq)是有效结论13实例例3构造推理的证明:若明天是星期一或星期三,我就有课.若有课,今天必需备课.我今天下午没备课.所以,明天不是星期一和星期三.解设p:明天是星期一,q:明天是星期三，r:我有课，s:我备课前提:(pÚq)®r,r®s,Øs结论:ØpÙØq14实例(续)前提:(pÚq)®r,r®s,Øs结论:ØpÙØq证明①r®s前提引入②Øs前提引入③Ør①②拒取式④(pÚq)®r前提引入⑤Ø(pÚq)③④拒取式
7、⑥ØpÙØq⑤置换结论有效,即明天不是星期一和星期三15附加前提证明法欲证明等价地证明前提:A1,A2,…,Ak前提:A1,A2,…,Ak,C结论:C®B结论:B理由:(A1ÙA2Ù…ÙAk)®(C®B)ÛØ(A1ÙA2Ù…ÙAk)Ú(ØCÚB)ÛØ(A1ÙA2Ù…ÙAkÙC)ÚBÛ(A1ÙA2Ù…ÙAkÙC)®B16实例例4构造下面推理的证明:前提:ØpÚq,ØqÚr,r®s结论:p®s证明①p附加前提引入②ØpÚq前提引入③q①②析取三段论④ØqÚr前提引入⑤r③④析取三段论⑥r®s前提引入⑦s⑤⑥假言推理推理正确,
8、p®s是有效结论17归谬法(反证法)欲证明前提：A1,A2,…,Ak结论：B将ØB加入前提,若推出矛盾,则得证推理正确.理由:A1ÙA2Ù…ÙAk®BÛØ(A1ÙA2Ù…ÙAk)ÚBÛØ(A1ÙA2Ù…ÙAkÙØB)括号内部为矛盾式当且仅当(A1ÙA2Ù…ÙAk®B)为重言式18实例例5构造下面推理的证明前提:Ø(p
