命题逻辑的推理理论.ppt

3.1推理的形式结构*推理的形式结构:前提:A1,A2,…,An结论:B重要的推理定律A∧B?A,A∧B?B(化简律)A?A∨B,B?A∨B(附加律)(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)∧(┐A→B)?B构造性二难(特殊形式)(A→B)∧(C→D)∧(┐B∨┐D)?(┐A∨┐C)破坏性二难?3.1推理的形式结构*论证的方法真值表法等值演算法将推理过程形式化证明公式A1?A2?…?An?B是重言式即证明(A1?A2?…?An?B)?1形式系统一般分为两类一类是自然推理系统，它的特点是从任意给定的前提出发，应用系统中的推理规则进行推理演算，得到的最后命题公式是推理的结论（有时称为有效的结论，它可能是重言式，也可能不是）一类是公理推理系统，它只能从若干给定的公理出发，应用系统中推理规则进行推理演算，得到的结论是系统中的重言式，称为系统中的定理。?3.2自然推理系统P*定义3.2一个形式系统I由下面四个部分组成：

????（1）非空的字符表集，记作A(I)

????（2）A(I)中符号构造的合式公式集，记作E(I)

????（3）E(I)中一些特殊的公式组成的公理集，记作AX(I)

????（4）推理规则集，记作R(I)可以将I记为A(I),E(I),AX(I),R(I)其中A(I),E(I)是I的形式语言系统AX(I),R(I)为I的形式演算系统。定义3.3自然推理系统P定义如下：

????1．字母表

????（1）命题变项符号：p，q，r，…,pi，qi，ri，…

???（2）联结词符号：┐,∧,∨,→,???（3）括号和逗号：(,)，，????2．合式公式同定义1.6????3．推理规则?3.2自然推理系统P*定理3.1{A1,A2,…,An}┝Ai,i=1,2,…,n证明因为A1?A2?…?An?(A1?A2?…?Ai–1?Ai+1?…?An)?Ai?Ai所以{A1,A2,…,An}┝Ai定理3.2若{A1,A2,…,An}┝Bi,i=1,2,…,m且{B1,B2,…,Bm}┝C,则{A1,A2,…,An}┝C证明由重言蕴涵的性质和题设可知A1?A2?…?An?B1?B2?…?Bm再由重言蕴涵的传递性可知A1?A2?…?An?C,即{A1,A2,…,An}┝C定理3.3若{A1,A2,…,An,B}┝C,则{A1,A2,…,An}┝(B?C)证明因为{A1,A2,…,An,B}┝C,所以1?A1?A2?…?An?B?C??(A1?A2?…?An?B)?C??(A1?A2?…?An)??B?C??(A1?A2?…?An)?(B?C)?(A1?A2?…?An)?(B?C)即{A1,A2,…,An}┝B?C?3.2自然推理系统P*?T规则在推演过程中可以随时引用前面已经得到的结论