命题逻辑的推理理论.ppt

第3章 命题逻辑的推理理论,离 散 数 学,本章说明,本章的主要内容 推理的形式结构 自然推理系统P 本章与后续各章的关系 本章是第五章的特殊情况和先行准备,第一节 推理的形式结构,数理逻辑的主要任务：是用数学的方法来研究 推理问题。 推理：是指从前提出发推出结论的思维过程。 前提：是已知命题公式的集合。 结论：是从前提出发应用推理规则推出的命题公式。 要研究推理，首先应该明确什么样的 推理是有效的或正确的。,铺垫,定义3.1： 设A1,A2,Ak和B都是命题公式，若对于 A1,A2,Ak和B中出现的命题变项的任意一组赋值， （1）或者A1A2 Ak为假; （2）或者当A1A2 Ak为真时，B也为真; 则称由前提A1,A2,Ak推出B的推理是有效的或正确的，并称B是有效结论。,有效推理的定义,关于有效推理的说明,2.A1，A2，Ak 由 推B的推理记为 B 若推理是正确的，记为 B 若推理是不正确的，记为 B,1.由前提A1，A2，Ak推结论B的推理是否正确与诸前提的排列次序无关。,关于有效推理的说明,3.设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。 4.只要不出现(3)中的情况，推理就是正确的，因而判断推理是否正确，就是判断是否会出现(3)中的情况。 5.推理正确，并不能保证结论B一定为真。我们注重的是推理过程的正确性。,(1) p,pq q (2) p,qp q,例3.1 判断下列推理是否正确。（真值表法）,例题,正确 q是有效结论,不正确 q不是有效结论,该定理是判断推理是否正确的另一种方法。,说明,有效推理的等价定理,定理3.1的证明,(1)证明必要性。若A1,A2,Ak推B的推理正确， 则对于A1,A2,Ak,B中所含命题变项的任意一组赋值，不会出现 A1A2Ak为真，而B为假的情况， 因而在任何赋值下，蕴涵式(A1A2Ak )B均为真， 故它为重言式。 (2)证明充分性。若蕴涵式(A1A2Ak)B为重言式， 则对于任何赋值此蕴涵式均为真，因而不会出现前件为真后件 为假的情况， 即在任何赋值下，或者A1A2Ak为假， 或者A1A2Ak和B同时为真，这正符合推理正确的定义。,前提： A1, A2, , Ak 结论： B,推理的形式结构,对推理的理解： 设= A1, A2, , Ak，记为B （前提推结论） A1A2 Ak B （讨论此蕴涵式的真值情况）,推理正确时 B,推理正确时 A1A2AkB 为重言式 记为A1A2AkB,推理的形式结构：(A1A2Ak )B,真值表法 等值演算法 主析取范式法,判断推理是否正确的方法,当命题变项较少时,这三种方法比较方便。,说明,表中不会出现前提合取为真，结论为假的情况,A1A2AkB析取范式中含全部极小项,A1A2AkB为重言式,（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,( p q) q p, (pq) (pq) (pq) (pq) (pq), m0m2m3,主析取范式不含m1，故不是重言式（01是成假赋值），所以推理不正确。,解：设p：今天是1号，q：明天是5号。 前提：pq，q 结论： p 推理的形式结构： (pq)qp,例题, ( p q) q (p p) p (q q),(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节给出的16个等值式中的每一个都派生出两条推理定律。例如双重否定律A A产生两条推理定律A A和 AA。,第二节 自然推理系统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,若今天下雪,则将去滑雪（AB）。 今天下雪（A），所以去滑雪（ B ）。,现在气温在冰点以下（A）。因此，要么现在气温在冰点以下，要么现在下雨（ AB ）。,现在气温在冰点以下并且正在下雨（ AB ）。因此，现在气温在冰点以下（A）。,自然推理系统的定义,（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 证明方法： 1.直接证明法 2.附加前提法 3.归谬法（或称反证法）,直接证明,例3.3-1： 在自然推理系统P中构造下面推理的证明： 前提：pq, rq ,rs 结论：ps pq 前提引入 pq 置换 rq 前提引入 qr 置换 pr 假言三段论 rs 前提引入 ps 假言三段论,直接证明,例3.3-2： 在自然推理系统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 析取三段论,直接证明,前提：p(qr), sq, ps 结论：r,附加前提法,问题：如果推理的形式结构具有如下形式 ： 前提：A1, A2, , Ak 结论：CB 解决办法：将结论中的前件也作为推理的前提，使结论只为B。 即：前提：A1, A2, , Ak, C 结论：B 证明： (A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2Ak)CB ( A1A2AkC)B (A1A2AkC)B,附加前提法,例3.5 在自然推理系统P中构造下面推理的证明。 如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影。 构造证明： （1）将简单命题符号化： 设 p:小张去看电影。 q:小王去看电影。 r:小李去看电影。 s:小赵去看电影。,附加前提法,（2） 形式结构： 前提：(pq)r,sp,q 结论：sr,附加前提后形式结构： 前提：(pq)r，sp，q，s 结论：r,附加前提法,（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）证明：用归谬法 前提：(pq)r,rs,s ,p ，q 结论： 矛盾 q 结论的否定引入 rs 前提引入 s 前提引入 r 析取三段论 (pq)r 前提引人 (pq) 拒取式 pq 置换 p 前提引入 q 析取三段论 qq 合取,小节结束,矛盾,原结论是 有效结论,本章主要内容,推理的形式结构： 推理的前提 推理的结论 推理正确 判断推理是否正确的方法： 真值表法 等值演算法 主析取范式法 对于正确的推理，在自然推理系统P中构造证明: 自然推理系统P的定义 自然推理系统P的推理规则： 附加前提证明法 归谬法,本章学习要求,1.理解并记住推理的形式结构的三种等价形式，即： A1,A2,AkB A1A2AkB 前提：A1,A2,Ak 结论：B,在判断推理是否正确时用,在P系统中构造证明时用,本章学习要求,5.会用附加前提证明法和归谬法。,小节结束,2.熟练掌握判断推理是否正确的三种方法（真值表法，等值演算法，主析取范式法）。,3.牢记P系统中的各条推理规则。,4.对于给定的正确推理，要求在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的真值表为,结论（不正确）是对的。,前提：qr, pr 结论：qp,（2）推理正确 方法一 真值表法（自己做） 方法二 等值演算法（自己做） 方法三 主析取范式法（自己做） 方法四 P系统中构造证明 证明： （直接证明法） pr （前提引入） rp （置换） qr （