《命题逻辑的推理理论ch.ppt》由会员分享，可在线阅读，更多相关《命题逻辑的推理理论ch.ppt（46页珍藏版）》请在三一办公上搜索。
1、本章说明,本章的主要内容推理的形式结构自然推理系统P本章与后续各章的关系本章是第五章的特殊情况和先行准备,3.1 推理的形式结构3.2 自然推理系统P 本章小结 习题 作业,3.1 推理的形式结构,数理逻辑的主要任务是用数学的方法来研究数学中的推理。推理是指从前提出发推出结论的思维过程。前提是已知命题公式集合。结论是从前提出发应用推理规则推出的命题公式。证明是描述推理正确或错误的过程。要研究推理，首先应该明确什么样的推理是有效的或正确的。,定义3.1 设A1,A2,Ak和B都是命题公式，若对于A1,A2,Ak和B中出现的命题变项的任意一组赋值，（1）或者A1A2 Ak为假;（2）或者当A1A2
2、 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、中的情况，推理就是正确的，因而判断推理是否正确，就是判断是否会出现(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均为真，故
4、它为重言式。(2)证明充分性。若蕴涵式(A1A2Ak)B为重言式，则对于任何赋值此蕴涵式均为真，因而不会出现前件为真后件为假的情况，即在任何赋值下，或者A1A2Ak为假，或者A1A2Ak和B同时为真，这正符合推理正确的定义。,当推理正确时，形式（1）记为 B。形式（2）记为A1A2AkB。表示蕴涵式为重言式。,设=A1,A2,Ak，记为B。A1A2AkB 前提：A1,A2,Ak 结论：B,说明,推理的形式结构,真值表法 等值演算法 主析取范式法,判断推理是否正确的方法,是否有其他的证明方法？,思考,当命题变项较少时,这三种方法比较方便。,说明,（1）下午马芳或去看电影或去游泳。她没去看电影，所
5、以，她 去游泳了。,例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)若下午气温超过30，则王小燕必去游泳；若她去游泳，她就不去看电影了。所以王小燕没有去看电影，下午气温必超过了30。（主析取范式法）,解：设 p：下午气温超过30。q：王小燕去游泳。r：王小燕去看电影。前提：pq，qr 结论：rp 推理的形式结构：(pq)(qr)(rp)(3.4),用主析取范式法判断(3.4
6、)式是否为重言式。(pq)(qr)(rp)(pq)(qr)(rp)(pq)(qr)rp rp(用两次吸收律)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m1m3m4m5m6m7（重排了序）可见(3.4)式不是重言式（主析取范式中少两个极小项 m0，m2），所以推理不正确。,(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)
7、B 构造性二难(特殊形式)(9)(AB)(CD)(BD)(AC)破坏性二难,推理定律-重言蕴含式,小节结束,关于推理定律的几点说明,A,B,C为元语言符号，代表任意的命题公式。若一个推理的形式结构与某条推理定律对应的蕴涵式一致，则不用证明就可断定这个推理是正确的。2.1节给出的24个等值式中的每一个都派生出两条推理定律。例如双重否定律A A产生两条推理定律A A和 AA。由九条推理定律可以产生九条推理规则,它们构成了推理系统中的推理规则。,3.2 自然推理系统P,判断推理是否正确的三种方法：真值表法、等值演算法和主析取范式法。当推理中包含的命题变项较多时，上述三种方法演算量太大。对于由前提A1
8、,A2,Ak推B的正确推理应该给出严谨的证明。证明是一个描述推理过程的命题公式序列，其中的每个公式或者是前提，或者是由某些前提应用推理规则得到的结论（中间结论或推理中的结论）。要构造出严谨的证明就必须在形式系统中进行。,定义3.2 一个形式系统I由下面四个部分组成：（1）非空的字符表集，记作A(I)。（2）A(I)中符号构造的合式公式集，记作E(I)。（3）E(I)中一些特殊的公式组成的公理集，记作AX(I)。（4）推理规则集，记作R(I)。可以将I记为.其中是I的形式语言系统，为I的形式演算系统。形式系统一般分为两类:自然推理系统 公理推理系统,自然推理系统的定义,1字母表（1）命题变项符号
9、：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）现在气温在冰
10、点以下并且正在下雨。因此，现在气温在冰点以下。,自然推理系统的定义,（7）拒取式规则 AB B A（8）假言三段论规则 AB BC AC（9）析取三段论规则 AB B A,（7）如果x是偶数,则x2是偶数。x不是偶数。x2不是偶数,自然推理系统的定义,（10）构造性二难推理规则 AB CD AC BD（11）破坏性二难推理规则 AB CD BD AC（12）合取引入规则 A B AB,例,1)、前提：1.如果明天天晴，我们准备外出旅游。PQ2明天的确天晴。P结论：我们外出旅游。Q上述例子可描述为：PQ，PQ(假言推理)2)、前提：1.如果一个人是单身汉，则他不幸福。PQ2.如果一个人不幸福，则
11、他死得早。QR结论：单身汉死得早。PR上述例子可描述为：PQ，QRPR(前提三段论),考虑以下语句，并将其前提和结论符号化。,例,3)、某女子在某日晚归家途中被杀害，据多方调查确证，凶手必为王某或陈某，但后又查证，作案之晚王某在工厂值夜班，没有外出，根据上述案情可得前提如下：前提：1.凶手为王某或陈某。PQ2.如果王某是凶手，则他在作案当晚必外出。PR3.王某案发之晚并未外出。R结论：陈某是凶手。Q则上述例子可描述为：PR,RP(拒取式)PQ，PQ(析取三段论),例,4)、前提：1.如果某同学为省二级以上运动员，则他将被大学录取。PR2.如果某同学高考总分在560分以上，则将被大学录取。QR3
12、.某同学高考总分在560分以上或者是省二级运动员。PQ结论：该同学被大学录取。R则上述例子可描述为：PQ，PR，QRR(构造性二难推理),证明：令P：马会飞；Q：羊吃草；R：母鸡是飞鸟；S：那么烤熟的鸭子还会跑。,如果马会飞或羊吃草，则母鸡就会是飞鸟；如果母鸡是飞鸟，那么烤熟的鸭子还会跑；烤熟的鸭子不会跑。所以羊不吃草。,例,证明：SPRSPR拒取式,PQRP(PQ)拒取式PQQ简化式,符号化上述语句为：=PQR,RS,S,G=Q。证明G。,在自然推理系统P中构造证明,P中构造证明就是由一组P中公式作为前提，利用P中的规则，推出结论。构造形式结构A1A2Ak B 的推理的书写方法：前提：A1,
13、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 若数a是实数，则它不是有理数就是无理数。若a不能表示成分数，则它不是有理数；a是实数且它不能表示成分数。所以a是无理数。
14、解 首先将简单命题符号化：设 p：a是实数。q：a是有理数。r：a是无理数。s：a能表示成分数。前提：p(qr),sq,ps 结论：r,ps 前提引入 p 化简 s 化简 p(qr)前提引入 qr 假言推理 sq 前提引入 q 假言推理 r 析取三段论,例题,例题,例3.5 在自然推理系统P中构造下面推理的证明。如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影。构造证明：（1）将简单命题符号化：设 p:小张去看电影。q:小王去看电影。r:小李去看电影。s:小赵去看电影。,例题,（2）形式结构：前提：(pq)r,sp,q
15、 结论：sr（3）证明：用附加前提证明法 s 附加前提引入 sp 前提引入 p 析取三段论(pq)r 前提引入 q 前提引入 pq 合取 r 假言推理,例题,例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
16、 前提引入 r 析取三段论(pq)r 前提引人(pq)拒取式 pq 置换 p 前提引入 q 析取三段论 qq 合取 由于最后一步为矛盾式，所以推理正确。,小节结束,本章主要内容,推理的形式结构：推理的前提推理的结论推理正确判断推理是否正确的方法：真值表法等值演算法主析取范式法 对于正确的推理，在自然推理系统P中构造证明:自然推理系统P的定义自然推理系统P的推理规则：附加前提证明法归谬法,本章学习要求,理解并记住推理的形式结构的三种等价形式，即A1,A2,AkBA1A2AkB前提：A1,A2,Ak 结论：B在判断推理是否正确时，用；在P系统中构造证明时用。熟练掌握判断推理是否正确的三种方法（真值
17、表法，等值演算法，主析取范式法）。牢记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不是重言式。
18、,方法三 直接观察出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 附加,小节结束,作业,习题三：14（1）、15（1）、16（1）,结束,
