03命题逻辑的推理理论.ppt
第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为1。(3)A1A2 Ak为1，B为0。(4)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 析取三段论 qq 合取 由于最后一步为矛盾式，所以推理正确。,小节结束,本章主要内容,推理的形式结构：推理的前提推理的结论推理正确判断推理是否正确的方法：真值表法等值演算法主析取范式法 对于正确的推理，在自然推理系统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)(qq)p pq易知10是成假赋值，故(pq)qp不是重言式，所以推理不正确。,方法二 主析取范式法经过演算后可知(pq)qp m0m1m3 未含m2,故(pq)qp不是重言式。,方法三 直接观察出10是成假赋值。,方法四 真值表法(pq)qp的真值表为,结论（不正确）是对的。,（2）推理正确方法一 真值表法（自己做）方法二 等值演算法（自己做）方法三 主析取范式法（自己做）方法四 P系统中构造证明证明：（直接证明法）pr（前提引入）rp（置换）qr（前提引入）qp（假言三段论）,2、在P系统中构造下面推理的证明：如果今天是周六，我们就到颐和园或圆明园玩。如果颐和园游人太多，就不去颐和园。今天是周六，并且颐和园游人太多。所以我们去圆明园或动物园玩。,构造证明：（1）设p：今天是周六。q：到颐和园玩。r：到圆明园玩。s：颐和园游人太多。t：到动物园玩。（2）前提：p(qr),sq,p,s 结论：rt,（3）证明：p(qr)前提引入 p 前提引入 qr 假言推理 sq 前提引入 s 前提引入 q 假言推理 r 析取三段论 rt 附加,小节结束,
