命题逻辑的推理理论.ppt

命题逻辑的推理理论,福建师范大学数学与计算机科学学院,数理逻辑的主要任务是用数学的方法来研究数学中的推理。 推理是指从前提出发推出结论的思维过程。 前提是已知命题公式集合。 结论是从前提出发应用推理规则推出的命题公式。 证明是描述推理正确或错误的过程。 要研究推理，首先应该明确什么样的推理是有效的或正确的。,定义1.24 设A1,A2,Ak和B都是命题公式，若对于A1,A2,Ak和B中出现的命题变项的任意一组赋值， （1）或者A1A2 Ak为假; （2）或者当A1A2 Ak为真时，B也为真; 则称由前提A1,A2,Ak推出B的推理是有效的或正确的，并称B是有效结论。,有效推理的定义,即：（A1A2 Ak）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,例1 判断下列推理是否正确。（真值表法）,正确,不正确,当推理正确时， 形式（1）记为 B。 形式（2）记为A1A2AkB。 表示蕴涵式为重言式。,= A1, A2, , Ak，记为B。 A1A2AkB 前提： A1, A2, , Ak 结论： B,说明,推理的形式结构,真值表法 等值演算法 主析取范式法,判断推理是否正确的方法,是否有其他的证明方法？,思考,当命题变项较少时,这三种方法比较方便。,说明,下午马芳或去看电影或去游泳。她没去看电影，所以，她 去游泳了。,例2 判断下列推理是否正确。（等值演算法）,解：设p:马芳下午去看电影，q:马芳下午去游泳。 前提： pq，p 结论： q 推理的形式结构： (pq)p)q (pq)p)q (pq)p) q (pq)p) q (pp )(qp) q (qp) q 1,例题,(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) 构造性二难 (9)(AB)(CD)(BD) (AC) 破坏性二难,推理定律-重言蕴含式,关于推理定律的几点说明,A,B,C为元语言符号，代表任意的命题公式。 若一个推理的形式结构与某条推理定律对应的蕴涵式一致，则不用证明就可断定这个推理是正确的。 1.3节给出的24个等值式中的每一个都派生出两条推理定律。例如双重否定律A A产生两条推理定律A A和 AA。 由九条推理定律可以产生九条推理规则,它们构成了推理系统中的推理规则。,构造性证明方法,判断推理是否正确的三种方法：真值表法、等值演算法和主析取范式法。 当推理中包含的命题变项较多时，上述三种方法演算量太大。 对于由前提A1,A2,Ak推B的正确推理应该给出严谨的证明。 证明是一个描述推理过程的命题公式序列，其中的每个公式或者是前提，或者是由某些前提应用推理规则得到的结论（中间结论或推理中的结论）。,常用的推理规则,（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,构造证明,构造证明就是由一组公式作为前提，利用自然推理系统中的规则，推出结论。 构造形式结构A1A2Ak B 的推理的书写方法： 前提： A1,A2,Ak 结论： B 证明方法： 直接证明法 附加前提法 归谬法（或称反证法）,例3.1 构造下面推理的证明： 前提：pq, rq ,rs 结论：ps pq 前提引入 pq 置换 rq 前提引入 qr 置换 pr 假言三段论 rs 前提引入 ps 假言三段论,例题,例3.2 构造下面推理的证明： 前提：p（qr）, pq 结论： rs p（qr） 前提引入 pq 前提引入 p 化简 q 化简 qr 假言推理 r 假言推理 rs 附加 rs 置换,技巧一：附加前提证明法,(A1 A2 Ak) (A B) 等价于 (A1 A2 Ak A) B 即原来结论中的前件变成前提了！,例4 构造下面推理的证明。 如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影。 构造证明： （1）将简单命题符号化： 设 p:小张去看电影。 q:小王去看电影。 r:小李去看电影。 s:小赵去看电影。,（2） 形式结构： 前提：(pq)r,sp,q 结论：sr （3）证明：用附加前提证明法 s 附加前提引入 sp 前提引入 p 析取三段论 (pq)r 前提引入 q 前提引入 pq 合取 r 假言推理,技巧二：归谬法,(A1 A2 Ak) B 等价于（ A1 A2 Ak B ） 因此，若A1 A2 Ak 与B 不相容（即A1 A2 Ak B 为矛盾式，或（ A1 A2 Ak B ） 为重言式），则说明B是A1 A2 Ak的逻辑结论。 这种将B 作为附加前提推出矛盾的证明方法成为归谬法。,例5 构造下面推理的证明。 如果小张守第一垒并且小李向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 合取 由于最后一步为矛盾式，所以推理正确。,小节结束,本节主要内容,推理的形式结构： 推理的前提 推理的结论 推理正确 判断推理是否正确的方法： 真值表法 等值演算法 主析取范式法 对于正确的推理，给予构造证明: 1.常用的推理规则： 2.附加前提证明法 3.归谬法,本章学习要求,理解并记住推理的形式结构的三种等价形式，即 A1,A2,AkB A1A2AkB 前提：A1,A2,Ak 结论：B 在判断推理是否正确时，用；在系统中构造证明时用。 熟练掌握判断推理是否正确的三种方法（真值表法，等值演算法，主析取范式法）。 牢记各条推理规则。 对于给定的正确推理，要求在系统中给出严谨的证明序列。 会用附加前提证明法和归谬法。,典型例题,1、用不同的方法验证下面推理是否正确。对于正确的推理还要在系统中给出证明。 （1） 前提：pq, q 结论：p （2） 前提：qr, pr 结论：qp,（1）不正确。 验证答案，只需证明 (pq)q p 不是重言式。 方法一 等值演算 (pq)qp (pq)q)p (pq)qp (pq)(qq)p pq 易知10是成假赋值，故(pq)qp不是重言式，所以推理不正确。,方法二 主析取范式法 经过演算后可知 (pq)qp m0m1m3 未含m2, 故(pq)qp不是重言式。,方法三 直接观察出10是成假赋值。,方法四 真值表法 (pq)qp的真值表为,结论（不正确）是对的。,（2）推理正确 方法一 真值表法（自己做） 方法二 等值演算法（自己做） 方法三 主析取范式法（自己做） 方法四 构造证明 证明： （直接证明法） pr （前提引入） rp （置换） qr （前提引入） qp （假言三段论）,2、构造下面推理的证明： 如果今天是周六，我们就到颐和园或圆明园玩。 如果颐和园游人太多，就不去颐和园。 今天是周六，并且颐和园游人太多。 所以我们去圆明园或动物园玩