lecture4推理的形式结构.ppt

一、有效推理 数理逻辑的主要任务是用数学的方法来研究数学中的推理。所谓推理是指从前提出发推出结论的思维过程，而前提是已知命题公式集合，结论是从前提出发应用推理规则推出的命题公式。要研究推理就应该给出推理的形式结构，为此，首先应该明确什么样的推理是有效的或正确的。,定义3.1 设A1,A2,Ak和B都是命题公式，若对于A1,A2,Ak和B中出现的命题变项的任意一组赋值，或者A1A2 Ak为假，或者当A1A2 Ak为真时，B也为真，则称由前提A1,A2,Ak推出B的推理是有效的或正确的，并称B是有效结论。,关于定义3.1还需要做以下几点说明：,1由前提A1,A2,Ak推结论B的推理是否正确与诸前提的排列次序无关。因而前提的公式不一定是序列，而是一个有限的公式集合，若将这个集合记为，可将由推B的推理记为 B。若推理是正确的，则记为|=B，否则记为|B。这里，可以称B和 A1,A2,Ak B 为推理的形式结构。,2设A1,A2,Ak，B中共出现n个命题变项，对于任何一组赋值1,2,n(i =0或者1，i=1,2,n)，前提和结论的取值情况有以下四种： (1) A1A2 Ak为0，B为0. (2) A1A2 Ak为0，B为1. (3) A1A2 Ak为1，B为0. (4) A1A2 Ak为1，B为1.,3由以上的讨论可知，推理正确，并不能保证结论B一定为真，这与数学中的推理是不同的。,定理3.1 命题公式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(A B)(B C)=(A C) 等价三段论,8(AB)(CD)(AC)=(BD) 构造性二难 (AB)(AB)(AA)=B 构造性二难 (特殊形式),9(AB)(CD)(BD)=(AC) 破坏性二难,3.2 自然推理系统 P,可以将I记为.其中是I的形式语言系统，为I的形式演算系统。,定义3.2 一个形式系统I由下面四个部分组成：,（1） 非空的字符表集，记作A(I)。,（2） A(I)中符号构造的合式公式集，记作E(I)。,（3） E(I)中一些特殊的公式组成的公理集，记作AX(I)。,（4） 推理规则集，记作R(I)。,形式系统一般分为两类。一类是自然推理系统，它的特点是从任意给定的前提出发，应用系统中的推理规则进行推理演算，得到的最后命题公式是推理的结论（有时称为有效的结论，它可能是重言式，也可能不是）。,另一类是公理推理系统，它只能从若干给定的公理出发，应用系统中推理规则进行推理演算，得到的结论是系统中的重言式，称为系统中的定理。,P是一个自然推理系统，因而没有公理。故P只有三个部分。 定义3.3 自然推理系统P定义如下：,1字母表 （1） 命题变项符号：p，q，r，,pi，qi，ri， （2） 联结词符号：, （3） 括号和逗号：( , )，,2合式公式,3推理规则 （1） 前提引入规则：在证明的任何步骤上都可以引入前提。 （2） 结论引入规则：在证明的任何步骤上所得到的结论都可以作为后继证明的前提。 （3） 置换规则：在证明的任何步骤上，命题公式中的子公式都可以用与之等值的公式置换，得到公式序列中的又一个公式。,由九条推理定律和结论引入规则还可以导出以下各条推理定律 （4） 假言推理规则（或称分离规则）：若证明的公式序列中已出现过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 ,rs 结论：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