命题逻辑的推理理论.ppt

第三章第三章 命题逻辑的推理理论命题逻辑的推理理论推理的形式结构推理的形式结构自然推理系统自然推理系统P关于“推理”n推理：指从推理：指从前提前提出发推出出发推出结论结论的思维过程的思维过程，前提前提是已知命题公式集合，是已知命题公式集合，结论结论是从前提出发应用推理规则推出的命题是从前提出发应用推理规则推出的命题公式。公式。数理逻辑的主要任务是用数学的方法来研究数数理逻辑的主要任务是用数学的方法来研究数学中的推理。学中的推理。推理的形式结构推理的形式结构问题的引入问题的引入推理举例推理举例:(1)正项级数收敛当且仅当部分和上有界正项级数收敛当且仅当部分和上有界.(2)若若A C B D，则，则A B且且C D.推理推理:从前提出发推出结论的思维过程从前提出发推出结论的思维过程上面上面(1)是正确的推理，而是正确的推理，而(2)是错误的推理是错误的推理.证明证明:描述推理正确或错误的过程描述推理正确或错误的过程.推理的形式结构定义定义设设A1，A2，Ak，B都是命题公式都是命题公式,若对于若对于A1，A2，Ak，B中出现的命题变中出现的命题变项的任意一组赋值，项的任意一组赋值，A1 A2 Ak均为假，均为假，或当或当A1 A2 Ak为真时为真时,B也为真也为真,则称由则称由A1,A2,Ak推推B的的推理正确推理正确,并称并称B是有效的是有效的结论；结论；否则否则推理不正确（错误）推理不正确（错误）.说明（1）：n由前提由前提A1，A2，Ak推结论推结论B的推理是否正确的推理是否正确与诸前提的排列次序无关。与诸前提的排列次序无关。n因而前提中的公式不一定是序列，而是一个有限因而前提中的公式不一定是序列，而是一个有限公式集合，记为公式集合，记为。n可将由可将由推推B的推理记为的推理记为 B B，若推理是正确，若推理是正确的，则记为的，则记为|=B|=B，否则记为，否则记为|B B。n这里可以称这里可以称BB 和和 A1，A2，Ak B B 为推理的形式结构。为推理的形式结构。说明（2）n设设A1，A2，Ak，B中共出现中共出现n个命题变项，对于任个命题变项，对于任一组赋值一组赋值 a1a2an（ai0或或1，i1，2，n），前），前提和结论的取值情况有以下四种：提和结论的取值情况有以下四种：（1）A1 A2 Ak 为为0，B为为0；（2）A1 A2 Ak 为为0，B为为1；（3）A1 A2 Ak 为为1，B为为0；（4）A1 A2 Ak 为为1，B为为1。由定义可知，只要不出现（由定义可知，只要不出现（3）中的情况，推理就是）中的情况，推理就是正确的，因而判断推理正确与否，就是判断是否会出正确的，因而判断推理正确与否，就是判断是否会出现（现（3）中的情况。）中的情况。例3.1 判断下列推理是否正确n（1）p，p q qn（2）p，q p q解：只要写出前提的合取式与结论的真值表，看是解：只要写出前提的合取式与结论的真值表，看是否出现前提为真，而结论为假的情况即可。否出现前提为真，而结论为假的情况即可。由下面真值表可看出，（由下面真值表可看出，（1）推理正确，（）推理正确，（2）推理不正确。推理不正确。p q p （p q ）q 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 p q p （q p ）q 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1定理定理3.1 命题公式A1，A2，Ak推B的推理正确当且仅当：（A1 A2 Ak）B B 为重言式。为重言式。证明：必要性 若命题公式A1，A2，Ak推B的推理正确，则不会出现A1 A2 Ak为真，而B为假的情况，因而在任何赋值下，蕴涵式（A1 A2 Ak）B B 均为真，故为重言式。证明：充分性 若蕴涵式（A1 A2 Ak）B B 为重言式，则对于任何赋值此重言式均为真，因而不会出现前件为真后件为假的情况。即在任何赋值下，或者A1 A2 Ak为假，或者A1 A2 Ak和B同时为真，这正符合定义3.1中推理正确的定义。分析：由定理3.1可知，可以将由前提A1,A2,Ak 推B的推理的形式结构 A1 A2 Ak B 转换成蕴涵式 （A1 A2 Ak）B B 推理前提的合取式成了蕴涵式的前件，结论成了蕴涵式的后件，并将推理正确 A1 A2 Ak|B 转换成 A1 A2 Ak B其中是一种元语言符号，表示蕴涵式为重言式。判断推理是否正确的方法真值表法真值表法等值演算法等值演算法主析取范式法主析取范式法构造证明法构造证明法 说明：当命题变项比较少时，用前说明：当命题变项比较少时，用前3 3个方法比较方个方法比较方便便,此时采用此时采用形式结构形式结构“A1 A2 AkB”.而在而在构造证明时，构造证明时，采用采用“前提前提:A1,A2,Ak,结论结论:B”.例3.2 判断下面推理是否正确 解上述类型的推理问题，首先应将简单命题符号化。然后分别写出前提、结论、推理的形式结构，接着进行判断。（1）设 p：a能被4整除 q：a能被2整除 前提：p q，p 结论：q 推理的形式结构：（p q）p q 可知此推理正确，即（p q）p q。（1）若）若a能被能被4整除，则整除，则a能被能被2整除。整除。a能被能被4整除，整除，所以所以a能被能被2整除。整除。（2）若）若a能被能被4整除，则整除，则a能被能被2整除。整除。a能被能被2整除，整除，所以所以a能被能被4整除。整除。n（2）设 p：a能被4整除 q：a能被2整除 前提：p q，q 结论：p 推理的形式结构：（p q）q p 可知上式不为重言式，所以此推理不正确，即（p q）p q。（3）下午马芳或去看电影或去游泳。她没去看电影。）下午马芳或去看电影或去游泳。她没去看电影。所以，她去游泳了。所以，她去游泳了。n（3）设）设p：马芳下午去看电影：马芳下午去看电影q：马芳下午去游泳：马芳下午去游泳前提：前提：p q，p 结论：结论：q 推理的形式结构推理的形式结构：（：（p q）p ）q 用等值演算法可知上市为重言式，所以，推理正用等值演算法可知上市为重言式，所以，推理正确。确。（4）若下午气温超过）若下午气温超过30度，则王小燕必去游泳。度，则王小燕必去游泳。若她去游泳，她就不去看电影。所以，若王小燕没若她去游泳，她就不去看电影。所以，若王小燕没去看电影，下午气温必超过了去看电影，下午气温必超过了30度。度。n（4）设）设p：下午气温超过：下午气温超过30度度q：王小燕去游泳王小燕去游泳r：王小燕去看电影王小燕去看电影前提：前提：pq，q r结论：结论：rp推理的形式结构：推理的形式结构：（pq）（q r）（rp）用主析取范式法可知上式不是重言式，所以用主析取范式法可知上式不是重言式，所以推理不正确。推理不正确。重要的推理定律（重要的推理定律（重言蕴涵式重言蕴涵式 ）A(A B)附加律附加律(A B)A化简律化简律(AB)AB假言推理假言推理(AB)B A拒取式拒取式(A B)BA析取三段论析取三段论(AB)(BC)(AC)假言三段论假言三段论(AB)(BC)(AC)等价三段论等价三段论(AB)(CD)(A C)(B D)构造性二难构造性二难推理定律推理定律(续续)(AB)(AB)(AA)B构造性二难（特殊形式）构造性二难（特殊形式）(AB)(CD)(BD)(AC)破坏性二难破坏性二难说明：说明：(1)A,B,C为元语言符号，代表任意的命题公式。为元语言符号，代表任意的命题公式。(2)若某推理符合某条推理定律，则它自然是正确的若某推理符合某条推理定律，则它自然是正确的.(3)AB产生两条推理定律产生两条推理定律:A B,B A.实例实例例例判断下面推理是否正确判断下面推理是否正确(1)若今天是若今天是1号，则明天是号，则明天是5号号.今天是今天是1号号.所所以明天是以明天是5号号.解解设设p：今天是：今天是1号，号，q：明天是：明天是5号号.证明的形式结构为证明的形式结构为:(pq)pq证明（用等值演算法）证明（用等值演算法）(pq)pq(p q)p)q pq q1得证推理正确得证推理正确实例实例(续续)(2)若今天是若今天是1号，则明天是号，则明天是5号号.明天是明天是5号号.所以今天是所以今天是1号号.解解设设p：今天是：今天是1号，号，q：明天是：明天是5号号.证明的形式结构为证明的形式结构为:(pq)qp证明（用主析取范式法）证明（用主析取范式法）(pq)qp(p q)qp(p q)q)p q p(pq)(pq)(pq)(p q)m0 m2 m3结果不含结果不含m1,故故01是成假赋值，所以推理不正确是成假赋值，所以推理不正确.重要的推理定律（重要的推理定律（重言蕴涵式重言蕴涵式 ）A(A B)附加律附加律(A B)A化简律化简律(AB)AB假言推理假言推理(AB)B A拒取式拒取式(A B)BA析取三段论析取三段论(AB)(BC)(AC)假言三段论假言三段论(AB)(BC)(AC)等价三段论等价三段论(AB)(CD)(A C)(B D)构造性二难构造性二难推理定律推理定律(续续)(AB)(AB)(AA)B构造性二难（特殊形式）构造性二难（特殊形式）(AB)(CD)(BD)(AC)破坏性二难破坏性二难说明：说明：A,B,C为元语言符号为元语言符号若某推理符合某条推理定律，则它自然是正确的若某推理符合某条推理定律，则它自然是正确的AB产生两条推理定律产生两条推理定律:A B,B A3.2 自然推理系统Pn判断推理是否正确的三种常用方法：判断推理是否正确的三种常用方法：1.1.真值表技术真值表技术 2.2.演绎法演绎法 3.3.间接证明方法间接证明方法 当命题变项较多时，以上三种方法的演当命题变项较多时，以上三种方法的演算量太大，此时可考虑推理证明的方法。算量太大，此时可考虑推理证明的方法。而要构造严谨的证明必须要在形式系统中而要构造严谨的证明必须要在形式系统中进行。进行。形式系统的定义n一个形式系统一个形式系统I由下面四个部分组成：由下面四个部分组成：（1）非空的字母表，记做）非空的字母表，记做A(I)。（2）A(I)中符号构造的合式公式集，记做中符号构造的合式公式集，记做E(I)。（3）E(I)中一些特殊的公式组成的公理集，记做中一些特殊的公式组成的公理集，记做Ax(I)。（4）推理规则集，记做）推理规则集，记做R(I)。可以将可以将I记为记为4元组元组。其中。其中是是I的形式语言系统，而的形式语言系统，而为为I的形式演算系统。的形式演算系统。形式系统的分类（1）自然推理系统自然推理系统 它的特点是从任意给定的前提前提出发，应用系统中的推理规则进行推理演算，得到的最后命题公式是推理的结论（可能是重言式，也可能不是可能是重言式，也可能不是）。（2）公理推理系统公理推理系统 它的特点是只能从若干条给定的公理公理出发，应用系统中的推理规则进行演算，得到的是系统中的定理（是是重言式重言式）。定义3.3 自然推理系统P定义如下：1、字母表 （1）命题变项符号：p，q，r，（2）联结词符号：,（3）括号与逗号：（），2、合式公式 (参见定义1.6 P10）3、推理规则推理规则推理规则（1）前提引入规则：在证明的任何步骤上都可以引入前提。（2）结论引入规则：在证明的任何步骤上所得到的结论都可以做为后续证明的前提。（3）置换规则：在证明的任何步骤上所得到的结论都可以作为后续证明的前提。推理规则推理规则 （续）（续）(4)假言推理规则假言推理规则 AB A B(5)附加规则附加规则 A A B (6)化简规则化简规则 A B A(7)拒取式规则拒取式规则 AB B A(8)假言三段论规则假言三段论规则 AB BC AC 推理规则推理规则(续续)(11)破破坏坏性性二二难难推推理理规则规则 AB CD BD AC(12)合取引入规则合取引入规则 A B A B(9)析取三段论规则析取三段论规则 A B B A(10)构构造造性性二二难难推推理理规则规则 AB CD A C B D构造证明构造证明直接证明法直接证明法n例例3.3在自然推理系统在自然推理系统P中构造下面推理的证明；中构造下面推理的证明；（1）前提：前提：p q，qr，ps，s结论：结论：r（p q）（2）前提：）前提：p q，r q，rs结论：结论：ps（1）前提：前提：p q，qr，ps，s结论：结论：r（p q）证明证明:(1)ps前提引入前提引入(2)s前提引入前提引入(3)p(1)(2)拒取式拒取式(4)p q前提引入前提引入(5)q(3)(4)析取三段论析取三段论(6)qr前提引入前提引入(7)r(5)(6)假言推理假言推理(8)r（p q）(7)(4)合取合取（2）前提：）前提：p q，r q，rs结论：结论：ps证明：(1)p q前提引入前提引入 (2)p q(1)置换置换 (3)r q前提引入前提引入 (4)q r(3)置换置换 (5)p r(2)(4)假言三段论假言三段论 (6)rs前提引入前提引入(7)ps(5)(6)假言三段论假言三段论构造证明构造证明直接证明法直接证明法n例例3.4在自然推理系统在自然推理系统P中构造下面推理的证明；中构造下面推理的证明；若若a是实数，则它不是无理数就是有理数。若是实数，则它不是无理数就是有理数。若a不能表示成分数，则它不是有理数。不能表示成分数，则它不是有理数。a是实数且它是实数且它不能表示成分数。所以不能表示成分数。所以a是无理数。是无理数。解：首先将简单命题符号化：解：首先将简单命题符号化：p：a是实数。是实数。q：a是有理数。是有理数。r：a是无理数。是无理数。S：a能表示成分数。能表示成分数。则可知：则可知：前提：前提：p (q r)，s q，p s结论：结论：r前提：前提：p (q r)，s q，p s结论：结论：r证明证明:(1)p s前提引入前提引入 (2)p (1)化简 (3)s(1)化简 (4)p (q r)前提引入前提引入 (5)q r(2)(4)假言推理假言推理 (6)s q前提引入前提引入 (7)q(3)(6)假言推理假言推理 (8)r(5)(7)析取三段论析取三段论构造证明构造证明附加前提证明法附加前提证明法 欲证明欲证明前提：前提：A1,A2,Ak结论：结论：CB等价地证明等价地证明前提：前提：A1,A2,Ak,C结论：结论：B理由：理由：(A1 A2 Ak)(CB)(A1 A2 Ak)(C B)(A1 A2 Ak C)B(A1 A2 Ak C)B将C称为附加前提附加前提证明法附加前提证明法n例例3.5在自然推理系统在自然推理系统P中构造下面推理的证明。中构造下面推理的证明。如果小张和小王去看电影，则小李也去看电影。如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王去看电影。小赵不去看电影或小张去看电影。小王去看电影。所以，当小赵去看电影时，小李也去。所以，当小赵去看电影时，小李也去。解：将简单命题符号化：解：将简单命题符号化：p：小张去看电影：小张去看电影q：小王去看电影：小王去看电影r：小李去看电影：小李去看电影s：小赵去看电影：小赵去看电影 前提：（前提：（p q）r，s p，q结论：结论：sr证明：证明：(1)(1)s附加前提引入附加前提引入 (2)(2)s p前提引入前提引入 (3)(3)p(1)(2)析取三段论析取三段论 (4)(4)（p q）r前提引入前提引入 (5)(5)q前提引入前提引入 (6)(6)p q(3)(5)(3)(5)合取合取 (7)(7)r (4)(6)(4)(6)假言推理假言推理附加前提证明法附加前提证明法(续续)例例 构造下面推理的证明构造下面推理的证明:2是素数或合数是素数或合数.若若2是素数，则是素数，则 是无理数是无理数.若若 是无理数，则是无理数，则4不是素数不是素数.所以，如果所以，如果4是是 素数，则素数，则2是合数是合数.用附加前提证明法构造证明用附加前提证明法构造证明解解 设设 p：2是素数，是素数，q：2是合数，是合数，r：是无理数，是无理数，s：4是素数是素数形式结构形式结构 前提：前提：p q,pr,rs 结论：结论：sq附加前提证明法附加前提证明法(续续)证明证明s附加前提引入附加前提引入pr前提引入前提引入r s前提引入前提引入p s假言三段论假言三段论 p拒取式拒取式p q前提引入前提引入q析取三段论析取三段论请用直接证明法证明之请用直接证明法证明之构造证明构造证明归谬法（反证法）归谬法（反证法）欲证明欲证明前提：前提：A1,A2,Ak结论：结论：B将将 B加入前提，若推出矛盾，则得证推理正确加入前提，若推出矛盾，则得证推理正确.理由理由:A1 A2 AkB(A1 A2 Ak)B(A1 A2 AkB)括号内部为矛盾式当且仅当括号内部为矛盾式当且仅当(A1 A2 AkB)为重言式。为重言式。归谬法归谬法(续续)例例3.6在自然推理系统在自然推理系统p中构造下面推理的证明。中构造下面推理的证明。如果如果小张守第一垒并且小李向小张守第一垒并且小李向B队投球，队投球，则则A队将取胜。或者队将取胜。或者A队未取胜，或者队未取胜，或者A队成为联队成为联赛第一名。赛第一名。A队没有成为联赛的第一名。小张守队没有成为联赛的第一名。小张守第一垒。因此，小李没有向第一垒。因此，小李没有向B队投球。队投球。解：先将简单命题符号化解：先将简单命题符号化p：小张守第一垒小张守第一垒q：小李向小李向B队投球队投球r：A队取胜队取胜s：A队成为联赛第一名队成为联赛第一名前提：（前提：（p q）r，r s，s，p结论：结论：q证明：证明：(1)q结论的否定引入结论的否定引入(2)r s前提引入前提引入(3)s前提引入前提引入(4)r(2)(3)析取三段论析取三段论(5)（p q）r前提引入前提引入(6)（p q）(4)(5)拒取式拒取式(7)p q(6)置换置换(8)p前提引入前提引入(9)q(7)(8)析取三段论析取三段论(10)q q(1)(9)合取合取 由于（由于（10）步）步等价于等价于0，由归缪法知：推理正确。，由归缪法知：推理正确。归谬法归谬法(续续)例例构造下面推理的证明构造下面推理的证明前提：前提：(p q)r,rs,s,p结论：结论：q证明（用归缪法）证明（用归缪法）q结论否定引入结论否定引入rs前提引入前提引入 s前提引入前提引入 r拒取式拒取式归谬法归谬法(续续)(p q)r前提引入前提引入(p q)析取三段论析取三段论 pq置换置换 p析取三段论析取三段论p前提引入前提引入 p p合取合取请用直接证明法证明之请用直接证明法证明之