离散数学：03命题逻辑的推理理论.ppt
45页
第3章 命题逻辑的推理理论,离 散 数 学,大学本科生课程,计算机系,本章说明,本章的主要内容推理的形式结构自然推理系统P本章与后续各章的关系本章是第五章的特殊情况和先行准备,3.1 推理的形式结构3.2 自然推理系统P 本章小结 习题 作业,3.1 推理的形式结构,数理逻辑的主要任务是用数学的方法来研究数学中的推理推理是指从前提出发推出结论的思维过程前提是已知命题公式集合结论是从前提出发应用推理规则推出的命题公式证明是描述推理正确或错误的过程要研究推理，首先应该明确什么样的推理是有效的或正确的定义3.1 设A1,A2,Ak和B都是命题公式，若对于A1,A2,Ak和B中出现的命题变项的任意一组赋值，（1）或者A1A2 Ak为假;（2）或者当A1A2 Ak为真时，B也为真;则称由前提A1,A2,Ak推出B的推理是有效的或正确的，并称B是有效结论有效推理的定义,关于有效推理的说明,A1，A2，Ak由 推B的推理记为B若推理是正确的，记为 B若推理是不正确的，记为 B,由前提A1，A2，Ak推结论B的推理是否正确与诸前提的排列次序无关关于有效推理的说明,设A1，A2，Ak，B中共出现n个命题变项，对于任何一组赋值12n(i=0或者1，i=1,2,n)，前提和结论的取值情况有以下四种： (1) A1A2 Ak为0，B为0。
2) A1A2 Ak为0，B为13) A1A2 Ak为1，B为04) A1A2 Ak为1，B为1只要不出现(3)中的情况，推理就是正确的，因而判断推理是否正确，就是判断是否会出现(3)中的情况推理正确，并不能保证结论B一定为真1) p,pq q(2) p,qp q,例3.1 判断下列推理是否正确真值表法）,例题,正确,不正确,定理3.1 命题公式A1,A2,Ak推B的推理正确当且仅当 (A1A2Ak )B 为重言式该定理是判断推理是否正确的另一种方法说明,有效推理的等价定理,定理3.1的证明,(1)证明必要性若A1,A2,Ak推B的推理正确，则对于A1,A2,Ak,B中所含命题变项的任意一组赋值，不会出现A1A2Ak为真，而B为假的情况，因而在任何赋值下，蕴涵式(A1A2Ak )B均为真，故它为重言式 (2)证明充分性若蕴涵式(A1A2Ak)B为重言式，则对于任何赋值此蕴涵式均为真，因而不会出现前件为真后件为假的情况，即在任何赋值下，或者A1A2Ak为假，或者A1A2Ak和B同时为真，这正符合推理正确的定义当推理正确时，形式（1）记为 B形式（2）记为A1A2AkB 表示蕴涵式为重言式。
设= A1, A2, , Ak，记为B A1A2AkB 前提： A1, A2, , Ak 结论： B,说明,推理的形式结构,真值表法 等值演算法 主析取范式法,判断推理是否正确的方法,是否有其他的证明方法？,思考,当命题变项较少时,这三种方法比较方便说明,（1） 下午马芳或去看电影或去游泳她没去看电影，所以，她 去游泳了例3.2 判断下列推理是否正确等值演算法）,解：设p:马芳下午去看电影，q:马芳下午去游泳 前提： pq，p 结论： q 推理的形式结构： (pq)p)q (pq)p)q (pq)p) q (pq)p) q (pp )(qp) q (qp) q 1,由定理 3.1可知，推理正确例题,（2）若今天是1号，则明天是5号明天是5号，所以今天是1号例3.2 判断下列推理是否正确主析取范式法 ）,(pq)qp, (pq)qp, (pq)q)p, qp, (pq)(pq) (pq)(pq), m0m2m3,主析取范式不含m1，故不是重言式（01是成假赋值），所以推理不正确解：设p：今天是1号，q：明天是5号 前提：pq，q 结论： p 推理的形式结构： (pq)qp,例题,(1) A (AB) 附加律(2) (AB) A 化简律(3)(AB)A B 假言推理(4) (AB)B A 拒取式(5) (AB)B A 析取三段论 (6)(AB) (BC) (AC) 假言三段论(7)(AB) (BC) (A C) 等价三段论(8)(AB)(CD)(AC) (BD) 构造性二难 (AB)(AB)(AA) B 构造性二难 (特殊形式)(9)(AB)(CD)(BD) (AC) 破坏性二难,推理定律-重言蕴含式,小节结束,关于推理定律的几点说明,A,B,C为元语言符号，代表任意的命题公式。
若一个推理的形式结构与某条推理定律对应的蕴涵式一致，则不用证明就可断定这个推理是正确的2.1节给出的24个等值式中的每一个都派生出两条推理定律例如双重否定律A A产生两条推理定律A A和 AA由九条推理定律可以产生九条推理规则,它们构成了推理系统中的推理规则3.2 自然推理系统P,判断推理是否正确的三种方法：真值表法、等值演算法和主析取范式法当推理中包含的命题变项较多时，上述三种方法演算量太大对于由前提A1,A2,Ak推B的正确推理应该给出严谨的证明证明是一个描述推理过程的命题公式序列，其中的每个公式或者是前提，或者是由某些前提应用推理规则得到的结论（中间结论或推理中的结论）要构造出严谨的证明就必须在形式系统中进行形式系统的定义,定义3.2 一个形式系统I由下面四个部分组成：（1）非空的字母表，记作A(I)2）A(I)中符号构造的合式公式集，记作E(I)3）E(I)中一些特殊的公式组成的公理集，记作AX(I)4）推理规则集，记作R(I)可以将I记为4元组 是I的形式语言系统 是I的形式演算系统,形式系统的分类,（1）自然推理系统从任意给定的前提出发，应用系统中的推理规则进行推理演算，得到的最后命题公式是推理的结论（有时称为有效的结论）。
（2）公理系统从若干给定的公理出发，应用系统中推理规则进行推理演算，得到的结论是系统中的定理本书只介绍自然推理系统P说明,自然推理系统的定义,定义3.3 自然推理系统P的定义1. 字母表（1） 命题变项符号：p， q， r， ， pi，qi，ri ，（2） 联结词符号： ， ， ， ， （3） 括号与逗号：( )，2. 合式公式（同定义1.6）,自然推理系统的定义,3. 推理规则（1）前提引入规则 在证明的任何步骤上都可以引入前提 （2）结论引入规则 在证明的任何步骤上所得到的结论都可以作为后继证明的前提 （3）置换规则 在证明的任何步骤上，命题公式中的子公式都可以用与之等值的公式置换，得到公式序列中的又一个公式自然推理系统的定义,（4）假言推理规则 AB A B（5）附加规则 A AB（6）化简规则 AB A,（4）若今天下雪,则将去滑雪今天下雪，所以去滑雪5）现在气温在冰点以下因此，要么现在气温在冰点以下，要么现在下雨6）现在气温在冰点以下并且正在下雨因此，现在气温在冰点以下自然推理系统的定义,（7）拒取式规则 AB B A（8）假言三段论规则 AB BC AC（9）析取三段论规则 AB B A,自然推理系统的定义,（10）构造性二难推理规则 AB CD AC BD （11）破坏性二难推理规则 AB CD BD AC（12） 合取引入规则 A B AB,在自然推理系统P中构造证明,P中构造证明就是由一组P中公式作为前提，利用P中的规则，推出结论。
构造形式结构A1A2Ak B 的推理的书写方法：前提： A1,A2,Ak 结论： B证明方法：直接证明法 附加前提法归谬法（或称反证法）,例题,例3.3 在自然推理系统P中构造下面推理的证明：前提：pq, rq ,rs 结论：ps pq 前提引入 pq 置换 rq 前提引入 qr 置换 pr 假言三段论 rs 前提引入 ps 假言三段论,例题,例3.3 在自然推理系统P中构造下面推理的证明：前提：p（qr）, pq 结论： rs p（qr） 前提引入 pq 前提引入 p 化简 q 化简 qr 假言推理 r 假言推理 rs 附加 rs置换,例题,例3.4 在自然推理系统P中构造下面推理的证明： 若数a是实数，则它不是有理数就是无理数；若a不能表示成分数，则它不是有理数；a是实数且它不能表示成分数所以a是无理数构造证明：（1）将简单命题符号化： 设 p：a是实数 q：a是有理数 r：a是无理数 s：a能表示成分数2）形式结构： 前提：p(qr), sq, ps 结论：r, ps 前提引入 p 化简 s 化简 p(qr) 前提引入 qr 假言推理 sq 前提引入 q 假言推理 r 析取三段论,例题,附加前提法,有时推理的形式结构具有如下形式 ： 前提：A1, A2, , Ak 结论：CB可将结论中的前件也作为推理的前提，使结论只为B。
前提：A1, A2, , Ak, C 结论：B理由： (A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2AkC)B,例题,例3.5 在自然推理系统P中构造下面推理的证明如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影所以，当小赵去看电影时，小李也去看电影构造证明：（1）将简单命题符号化： 设 p:小张去看电影 q:小王去看电影 r:小李去看电影 s:小赵去看电影例题,（2）形式结构：前提：(pq)r,sp,q 结论：sr （3）证明：用附加前提证明法 s 附加前提引入 sp 前提引入 p 析取三段论 (pq)r 前提引入 q 前提引入 pq 合取 r 假言推理,归谬法（反证法）,有时推理的形式结构具有如下形式： 前提：A1, A2, , Ak 结论：B 如果将B作为前提能推出矛盾来，则说明推理正确 前提：A1, A2, , Ak, B 结论：矛盾 理由：A1A2AkB (A1A2Ak)B (A1A2AkB)若A1A2AkB为矛盾式，则说明(A1A2AkB) 为重言式例题,例3.6 在自然推理系统P中构造下面推理的证明。
如果小张守第一垒并且小李向B队投球，则A队将取胜；或者A队未取胜，或者A队获得联赛第一名；A队没有获得联赛的第一名；小张守第一垒因此，小李没有向B队投球 构造证明：（1）将简单命题符号化： 设 p:小张守第一垒 q:小李向B队投球 r:A队取胜 s:A队获得联赛第一名2）形式结构： 前提：(pq)r,rs,s ,p 结论：q,例题,（3）证明：用归谬法 q 结论的否定引入 rs 前提引入 s 前提引入 r 析取三段论 (pq)r 前提引人 (pq) 拒取式 pq 置换 p 前提引入 q 析取三段论 合取 由于最后一步为矛盾式，所以推理正确小节结束,本章主要内容,推理的形式结构：推理的前提推理的结论推理正确判断推理是否正确的方法：真值表法等值演算法主析取范式法 对于正确的推理，在自然推理系统P中构造证明: 自然推理系统P的定义自然推理系统P的推理规则：附加前提证明法归谬法,本章学习要求,理解并记住推理的形式结构的三种等价形式，即A1,A2,AkBA1A2AkB前提：A1,A2,Ak 结论：B在判断推理是否正确时，用；在P系统中构造证明时用熟练掌握判断推理是否正确的三种方法（真值表法，等值演算法，主析取范式法）。
牢记P系统中的各条推理规则对于给定的正确推理，要求在P系统中给出严谨的证明序列会用附加前提证明法和归谬法小节结束,习题,1、用不同的方法验证下面推理是否正确对于正确的推理还要在P系统中给出证明1） 前提：pq, q 结论：p（2）前提：qr, pr 结论：qp,（1）不正确 验证答案，只需证明(pq)qp不是重言式方法一 等值演算 (pq)qp (pq)q)p (pq)qp (pq)()p pq易知10是成假赋值，故(pq)qp不是重言式，所以推理不正确方法二 主析取范式法经过演算后可知(pq)qp m0m1m3 未含m2, 故(pq)qp不是重言式方法三 直接观察出10是成假赋值。
