离散数学--命题逻辑1.6

11.6命题逻辑的推理理论推理的形式结构判断推理是否正确的方法推理定律与推理规则构造证明法2推理的形式结构—问题的引入推理举例:(1)正项级数收敛当且仅当部分和有上界.(2)若ACBD，则AB且CD.推理:从前提出发推出结论的思维过程上面(1)是正确的推理，而(2)是错误的推理.证明:描述推理正确的过程.3推理的形式结构定义若对于每组赋值，或者A1A2…Ak均为假，或者当A1A2…Ak为真时,B也为真,则称由A1,A2,…,Ak推B的推理正确,否则推理不正确（错误）.“A1,A2,…,Ak推B”的推理正确当且仅当A1A2…AkB为重言式.推理的形式结构:A1A2…AkB或前提：A1,A2,…,Ak结论：B若推理正确，则记作：A1A2…AkB.4判断推理是否正确的方法•真值表法•等值演算法判断推理是否正确•主析取范式法•构造证明法证明推理正确说明：当命题变项比较少时，用前3个方法比较方便,此时采用形式结构“A1A2…AkB”.而在构造证明时，采用“前提:A1,A2,…,Ak,结论:B”.5实例例判断下面推理是否正确(1)若今天是1号，则明天是5号.今天是1号.所以明天是5号.解设p：今天是1号，q：明天是5号.推理的形式结构为:(pq)pq证明（用等值演算法）(pq)pq((pq)p)qpqq1得证推理正确6实例(续)(2)若今天是1号，则明天是5号.明天是5号.所以今天是1号.解设p：今天是1号，q：明天是5号.推理的形式结构为:(pq)qp证明（用主析取范式法）(pq)qp(pq)qp((pq)q)pqp(pq)(pq)(pq)(pq)m0m2m3结果不含m1,故01是成假赋值，所以推理不正确.7推理定律——重言蕴涵式重要的推理定律A(AB)附加律(AB)A化简律(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)构造性二难8推理定律(续)(AB)(AB)B构造性二难（特殊形式）(AB)(CD)(BD)(AC)破坏性二难说明：A,B,C为元语言符号若某推理符合某条推理定律，则它自然是正确的AB产生两条推理定律:AB,BA9推理规则(1)前提引入规则(2)结论引入规则(3)置换规则(4)假言推理规则ABA\B(5)附加规则A\AB(6)化简规则AB\A(7)拒取式规则ABB\A(8)假言三段论规则ABBC\AC10推理规则(续)(11)破坏性二难推理规则ABCDBD\AC(12)合取引入规则AB\AB(9)析取三段论规则ABB\A(10)构造性二难推理规则ABCDAC\BD11构造证明——直接证明法例构造下面推理的证明：若明天是星期一，我就有课.若有课，今天必备课.我今天没备课.所以，明天不是星期一解设p：明天是星期一，r：我有课，s：我备课推理的形式结构为前提：pr,rs,s结论：p12直接证明法(续)证明①rs前提引入②s前提引入③r①②拒取式④pr前提引入⑤p③④拒取式13构造证明——附加前提证明法欲证明前提：A1,A2,…,Ak结论：CB等价地证明前提：A1,A2,…,Ak,C结论：B理由：(A1A2…Ak)(CB)(A1A2…Ak)(CB)(A1A2…AkC)B(A1A2…AkC)B14附加前提证明法(续)222例构造下面推理的证明:2是素数或合数.若2是素数，则是无理数.若是无理数，则4不是素数.所以，如果4是素数，则2是合数.用附加前提证明法构造证明解设p：2是素数，q：2是合数，r：是无理数，s：4是素数推理的形式结构前提：pq,pr,rs结论：sq22215附加前提证明法(续)证明①s附加前提引入②pr前提引入③rs前提引入④ps②③假言三段论⑤p①④拒取式⑥pq前提引入⑦q⑤⑥析取三段论请用直接证明法证明之16构造证明——归谬法（反证法）欲证明前提：A1,A2,…,Ak结论：B将B加入前提，若推出矛盾，则得证推理正确.理由:A1A2…AkB(A1A2…Ak)B(A1A2…AkB)括号内部为矛盾式当且仅当(A1A2…AkB)为重言式17归谬法(续)例构造下面推理的证明前提：(pq)r,rs,s,p结论：q证明（用归缪法）①q结论否定引入②rs前提引入③s前提引入④r②③拒取式18归谬法(续)⑤(pq)r前提引入⑥(pq)④⑤析取三段论⑦pq⑥置换⑧p①⑦析取三段论⑨p前提引入⑩pp⑧⑨合取请用直接证明法证明之