《离散数学教学课件：lecture 4 推理的形式结构》由会员分享，可在线阅读，更多相关《离散数学教学课件：lecture 4 推理的形式结构（14页珍藏版）》请在金锄头文库上搜索。
1、一、有效推理一、有效推理 数理逻辑的主要任务是用数学的方法来研究数学中的推理。所谓推理是指从前提出发推出结论的思维过程，而前提是已知命题公式集合，结论是从前提出发应用推理规则推出的命题公式。要研究推理就应该给出推理的形式结构，为此，首先应该明确什么样的推理是有效的或正确的。定义定义3.1设A1,A2,Ak和B都是命题公式，若对于A1,A2,Ak和B中出现的命题变项的任意一组赋值，或者A1A2Ak为假，或者当A1A2Ak为真时，B也为真，则称由前提A1,A2,Ak推出B的推理是有效的或正确的推理是有效的或正确的，并称B是有效结论有效结论。关于定义3.1还需要做以下几点说明：1由前提A1,A2,A
2、k推结论B的推理是否正确与诸前提的排列次序无关。因而前提的公式不一定是序列，而是一个有限的公式集合，若将这个集合记为，可将由推B的推理记为B。若推理是正确的，则记为|=B，否则记为|B。这里，可以称B和A1,A2,AkB为推理的形式结构。2设A1,A2,Ak，B中共出现n个命题变项，对于任何一组赋值1,2,n(i=0或者1，i=1,2,n)，前提和结论的取值情况有以下四种：(1)A1A2Ak为0，B为0.(2)A1A2Ak为0，B为1.(3)A1A2Ak为1，B为0.(4)A1A2Ak为1，B为1.3由以上的讨论可知，推理正确，并不能保证结论B一定为真，这与数学中的推理是不同的。定理定理3.1
3、命题公式A1,A2,Ak推B的推理正确当且仅当(A1A2Ak)B为重言式。于是，推理正确A1,A2,Ak|=B可记为A1A2Ak=B其中=同一样是一种元语言符号，用来表示蕴涵式为重言式。若AB为重言式，则称B为A的推论，记为A=B，下面是几个重要的重言蕴涵式及其名称1A=(AB)附加律2(AB)=A化简律3(AB)A=B假言推理4(AB)B=A拒取式5(AB)B=A析取三段论6(AB)(BC)=(AC)假言三段论7(AB)(BC)=(AC)等价三段论8(AB)(CD)(AC)=(BD)构造性二难(AB)(AB)(AA)=B构造性二难(特殊形式)9(AB)(CD)(BD)=(AC)破坏性二难3.
4、2自然推理系统P可以将I记为.其中是I的形式形式语言系统语言系统，为I的形式演算系统形式演算系统。定义定义3.2一个形式系统形式系统I由下面四个部分组成：（1）非空的字符表集，记作A(I)。（2）A(I)中符号构造的合式公式集，记作E(I)。（3）E(I)中一些特殊的公式组成的公理集，记作AX(I)。（4）推理规则集，记作R(I)。形式系统一般分为两类。一类是自然推理系统，它的特点是从任意给定的前提出发，应用系统中的推理规则进行推理演算，得到的最后命题公式是推理的结论（有时称为有效的结论，它可能是重言式，也可能不是）。另一类是公理推理系统，它只能从若干给定的公理出发，应用系统中推理规则进行推理
5、演算，得到的结论是系统中的重言式，称为系统中的定理。P是一个自然推理系统，因而没有公理。故P只有三个部分。定义定义3.3自然推理系统自然推理系统P定义如下：1字母表（1）命题变项符号：p，q，r，,pi，qi，ri，（2）联结词符号：,（3）括号和逗号：(,)，2合式公式3推理规则（1）前提引入规则：在证明的任何步骤上都可以引入前提。（2）结论引入规则：在证明的任何步骤上所得到的结论都可以作为后继证明的前提。（3）置换规则：在证明的任何步骤上，命题公式中的子公式都可以用与之等值的公式置换，得到公式序列中的又一个公式。由九条推理定律和结论引入规则还可以导出以下各条推理定律（4）假言推理规则（或称
6、分离规则）：若证明的公式序列中已出现过AB和A，则由假言推理定律(AB)AB可知，B是AB和A的有效结论。由结论引入规则可知，可将B引入到命题序列中来。用图式表示为如下形式：（5）附加规则：（6）化简规则：（7）拒取式规则：（8）假言三段论规则：（9）析取三段论规则：（10）构造性二难推理：（11）破坏性二难推理规则：（12）合取引入规则：这就完成了P的定义。三、三、P中的证明中的证明 P中的证明就是由一组P中公式作为前提，利用P中的规则，推出结论。当然此结论也为P中公式。例例3.3在自然推理系统P中构造下面推理的证明：(1)前提：pq,qr,ps,s结论：r(pq)(2)前提：pq,rq,r
7、s结论：ps(1)前提：pq,qr,ps,s结论：r(pq)解解(1)证明：ps前提引入s前提引入p拒取式pq前提引入q析取三段论qr前提引入r假言推理r(pq)合取此证明的序列长为8，最后一步为推理的结论，所以推理正确，r(pq)是有效结论。(2)前提：pq,rq,rs结论：ps(2)证明：pq前提引入pq置换rq前提引入qr置换pr假言三段论rs前提引入ps假言三段论从最后一步可知推理正确，ps是有效结论。例例3.4在自然推理系统P中构造下面推理的证明：若数a是实数，则它不是有理数就是无理数；若a不能表示成分数，则它不是有理数；a是实数且它不能表示成分数。所以a是无理数。解解首先将简单命题符号化：设p：a是实数。q：a是有理数。r：a是无理数。s：a能表示成分数。前提：p(qr),sq,ps结论：r前提：p(qr),sq,ps结论：r证明：ps前提引入p化简s化简p(qr)前提引入qr假言推理sq前提引入q假言推理从最后一步可知推理正确，r是有效结论。r析取三段论
