离散数学高教版第一部分第三章

离散数学——数理逻辑第三章命题逻辑的推理理论3.1推理的形式结构定义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。•2.设A1，A2…..Ak,B中出现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.1命题公式A1,A2….Ak推B的正确推理正确，当且仅当（A1∧A2∧….Ak)→B为重言式。例：（1）若a能被4整除，则a能被2整除。a能被4整除，所以a能被2整除。（2）下午马芳或去看电影或去游泳，她没有去看电影，所以她去游泳了。（1）解：设p：a能被4整除q:a能被2整除.前提:p→q,p结论:q推理的形式结构:(p→q)∧p→q(2)设P:马芳下午去看电影.Q:马芳下午去游泳.前提:p∨q,p结论:q推理的形式结构（（p∨q）∧～q）→q3.2自然推理系统P定义3.2一个形式系统I由下面四个部分成：•（1）非空的字母表，记作A(I)。•（2）A（I）中符号构造的合式集，记作E（I）•（3）E（I）中一些特殊的公式组成的公理集，记作Ax（I）。•（4）推理规则集，记作R（x）。3.2自然推理系统P1.字母表(1)命题变项符号：p，q，r….(2)连接词符号：∧，∨，→等(3)括号与逗号：（），‘2.合式公式3.推理规则（1）前提引入规则：在证明的任何步骤都可以引入前提。（2）结论引入规则：在证明的任何步骤上的所得结论都可以作为定义3.3自然推理系统P定义如下后继证明的前提。（3）置换规则：在证明的任何规则步骤上，命题公式中的子公式都可以用于之等值的公式置换，得到公式序列中有一个公式。假言推理规则（或称分离规则），附加规则，化简规则，拒取式规则，假言三段论规则，析取三段论规则，构造性二难推理规则，破坏性二难推理规则合取引入规则例：如果小王是理科学生，则他的数学成绩一定很好。如果小王不是文科生，他一定是理科生。小王的数学成绩不好，所以小王是文科生。•解：设p：小王是理科学生，q：小王数学成绩好，r：小王是文科学生。•前提：•结论：•证明•1.p→q前提引入•2.非q前提引入•3.非p1，2拒绝式•4.非r→q前提引入•5.r3，4拒绝式