一、有效推理一、有效推理 数理逻辑的主要任务是用数学的方法来研究数学中的推理所谓推理是指从前提出发推出结论的思维过程，而前提是已知命题公式集合，结论是从前提出发应用推理规则推出的命题公式要研究推理就应该给出推理的形式结构，为此，首先应该明确什么样的推理是有效的或正确的 定义定义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记为.其中是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） 假言推理规则（或称分离规则）：若证明的公式序列中已出现过A→B和A，则由假言推理定律(A→B)∧AB可知，B是A→B和A的有效结论由结论引入规则可知，可将B引入到命题序列中来用图式表示为如下形式：（5） 附加规则： （6） 化简规则： （7） 拒取式规则： （8） 假言三段论规则： （9） 析取三段论规则： （10） 构造性二难推理： （11） 破坏性二难推理规则： （12） 合取引入规则： 这就完成了P的定义 三、三、P中的证明中的证明 P中的证明就是由一组P中公式作为前提，利用P中的规则，推出结论当然此结论也为P中公式 例例3.3 在自然推理系统P中构造下面推理的证明： (1)前提：p∨q,q→r,p→s,┐s 结论：r∧(p∨q) (2)前提：┐p∨q, r∨┐q ,r→s 结论：p→s (1)前提：p∨q,q→r,p→s,┐s 结论：r∧(p∨q) 解解 (1)证明： ① p→s 前提引入 ② ┐s 前提引入 ③ ┐p ①②拒取式 ④ p∨q 前提引入 ⑤ q ③④析取三段论 ⑥ q→r 前提引入 ⑦ r ⑤⑥假言推理 ⑧ r∧(p∨q) ⑦④合取 此证明的序列长为8，最后一步为推理的结论，所以推理正确，r∧(p∨q)是有效结论。
(2)前提：┐p∨q, r∨┐q ,r→s 结论：p→s (2)证明： ① ┐p∨q 前提引入 ② p→q ①置换 ③ r∨┐q 前提引入 ④ q→r ③置换 ⑤ p→r ②④假言三段论 ⑥ r→s 前提引入 ⑦ p→s ⑤⑥假言三段论 从最后一步可知推理正确，p→s是有效结论 例例3.4 在自然推理系统P中构造下面推理的证明： 若数a是实数，则它不是有理数就是无理数；若a不能表示成分数，则它不是有理数；a是实数且它不能表示成分数所以a是无理数 解解 首先将简单命题符号化： 设 p：a是实数 q：a是有理数 r：a是无理数 s：a能表示成分数 前提：p→(q∨r), ┐s→┐q, p∧┐s 结论：r 前提：p→(q∨r), ┐s→┐q, p∧┐s 结论：r 证明： ① p∧┐s 前提引入 ② p ①化简 ③ ┐s ①化简 ④ p→(q∨r) 前提引入 ⑤ q∨r ②④假言推理 ⑥ ┐s→┐q 前提引入 ⑦ ┐q ③⑥假言推理 从最后一步可知推理正确，r是有效结论。
⑧ r ⑤⑦析取三段论 。