lecture 4 推理的形式结构.pptVIP

* 一、有效推理 ????数理逻辑的主要任务是用数学的方法来研究数学中的推理。所谓推理是指从前提出发推出结论的思维过程，而前提是已知命题公式集合，结论是从前提出发应用推理规则推出的命题公式。要研究推理就应该给出推理的形式结构，为此，首先应该明确什么样的推理是有效的或正确的。 定义3.1 设A1,A2,…,Ak和B都是命题公式，若对于A1,A2,…,Ak和B中出现的命题变项的任意一组赋值，或者A1∧A2 ∧…∧Ak为假，或者当A1∧A2 ∧…∧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) A1∧A2 ∧…∧Ak为0，B为0.????(2) A1∧A2 ∧…∧Ak为0，B为1.????(3) A1∧A2 ∧…∧Ak为1，B为0.????(4) A1∧A2 ∧…∧Ak为1，B为1. ????3．由以上的讨论可知，推理正确，并不能保证结论B一定为真，这与数学中的推理是不同的。 定理3.1 命题公式A1,A2,…,Ak推B的推理正确当且仅当 ????????????????? ????????(A1∧A2∧…∧Ak )→B 为重言式。 于是，推理正确 ???????????????? {A1,A2,…,Ak }|=B 可记为 ???????????????? A1∧A2∧…∧Ak =B 其中=同=一样是一种元语言符号，用来表示蕴涵式为重言式。 ????若A→B为重言式，则称B为A的推论，记为A=B，下面是几个重要的重言蕴涵式及其名称 1．A=(A∨B) ?????????????????????? ??????附加律 2．(A∧B)=A ????????????????????????????? 化简律 3．(A→B)∧A=B ?????????????????????????? 假言推理 4．(A→B)∧┐B=┐A ????????????? ????? ???拒取式 5．(A∨B)∧┐B=A ??????????????????????? ?析取三段论 6．(A→B)∧(B→C)=(A→C) ?????????? ?? ???假言三段论 7．(A ? B)∧(B ? C)=(A ? C) ????????? ?? ??等价三段论 8．(A→B)∧(C→D)∧(A∨C)=(B∨D)??? ????? 构造性二难 ????? (A→B)∧(┐A→B)∧(A∨┐A)=B?? ??????构造性二难 (特殊形式) 9．(A→B)∧(C→D)∧(┐B∨┐D)=(┐A∨┐C) ??????????破坏性二难 3.2 自然推理系统 P 可以将I记为A(I),E(I),AX(I),R(I).其中A(I),E(I)是I的形式语言系统，AX(I),R(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） 结论引入规则：在证明的任何步骤上所得到的结论都可以作为后