命题逻辑的推理理论.ppt

1、第三章 命题逻辑的推理理论,推理的形式结构 自然推理系统P,关于“推理,推理：指从前提出发推出结论的思维过程， 前提是已知命题公式集合， 结论是从前提出发应用推理规则推出的命题公式。 数理逻辑的主要任务是用数学的方法来研究数学中的推理,推理的形式结构问题的引入,推理举例: (1) 正项级数收敛当且仅当部分和上有界. (2) 若ACBD，则AB且CD. 推理: 从前提出发推出结论的思维过程 上面(1)是正确的推理，而(2)是错误的推理. 证明: 描述推理正确或错误的过程,推理的形式结构,定义 设A1，A2 ，Ak，B都是命题公式, 若对于A1，A2 ，Ak，B中出现的命题变 项的任意一组赋值，A

2、1A2 Ak 均为假， 或当A1A2Ak为真时, B也为真, 则称由 A1,A2, Ak推B的推理正确 ,并称B是有效的 结论； 否则推理不正确（错误,说明（1,由前提A1，A2 ，Ak推结论B的推理是否正确与诸前提的排列次序无关。 因而前提中的公式不一定是序列，而是一个有限公式集合，记为 。 可将由推B的推理记为B，若推理是正确的，则记为|=B，否则记为 | B。 这里可以称B 和A1，A2 ，Ak B 为推理的形式结构,说明（2,设A1，A2 ，Ak，B中共出现n个命题变项，对于任一组赋值 a1a2an （ai0或1， i1，2，n），前提和结论的取值情况有以下四种： （1） A1A2Ak

3、 为0，B为0； （2） A1A2Ak 为0，B为1； （3） A1A2Ak 为1，B为0； （4） A1A2Ak 为1，B为1。 由定义可知，只要不出现（3）中的情况，推理就是正确的，因而判断推理正确与否，就是判断是否会出现（3）中的情况,例3.1 判断下列推理是否正确,1） p， p q q （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

4、 0 0 1 0 1 1 0 1 0 1 1 1 1,定理3.1 命题公式A1，A2 ，Ak推B的推 理正确当且仅当： （A1A2Ak ） B 为重言式。 证明：必要性 若命题公式A1，A2 ，Ak推B的推 理正确，则不会出现A1A2Ak为真， 而B为假的情况，因而在任何赋值下， 蕴涵式（A1A2Ak ） B 均为真，故 为重言式,证明：充分性 若蕴涵式（A1A2Ak ） B 为 重言式，则对于任何赋值此重言式均为真， 因而不会出现前件为真后件为假的情况。即 在任何赋值下，或者A1A2Ak为假， 或者A1A2Ak和B同时为真，这正符合 定义3.1中推理正确的定义,分析,由定理3.1可知，可以将

5、由前提A1, A2, , Ak 推B的推理的形式结构 A1A2Ak B 转换成蕴涵式 （A1A2Ak ） B 推理前提的合取式成了蕴涵式的前件，结论成了蕴涵式的后件，并将推理正确 A1A2Ak | B 转换成 A1A2Ak B 其中是一种元语言符号，表示蕴涵式为重言式,判断推理是否正确的方法,真值表法 等值演算法 主析取范式法 构造证明法 说明：当命题变项比较少时，用前3个方法比较方 便, 此时采用形式结构“ A1A2AkB” . 而在 构造证明时，采用“前提: A1, A2, , Ak, 结论: B,例3.2 判断下面推理是否正确,解上述类型的推理问题，首先应将简单命题符号化。然后分别写出前

6、提、结论、推理的形式结构，接着进行判断,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整除,2）设 p：a能被4整除 q：a能被2整除 前提：p q，q 结论：p 推理的形式结构：（p q） q p 可知上式不为重言式，所以此推理不正确，即 （p q） p q,3）下午马芳或去看电影或去游泳。她没去看电影。所以，她去游泳了,3）设 p：马芳下午去看电影 q：马芳下

7、午去游泳 前提：p q，p 结论： q 推理的形式结构：（p q） p ） q 用等值演算法可知上市为重言式，所以，推理正 确,4）若下午气温超过30度，则王小燕必去游泳。若她去游泳，她就不去看电影。所以，若王小燕没去看电影，下午气温必超过了30度,4）设 p：下午气温超过30度 q： 王小燕去游泳 r： 王小燕去看电影 前提： p q， q r 结论： r p 推理的形式结构： （ p q ） （q r） （r p） 用主析取范式法可知上式不是重言式，所以 推理不正确,重要的推理定律（重言蕴涵式 ） A (AB) 附加律 (AB) A 化简律 (AB)A B 假言推理 (AB)B A 拒取式

8、 (AB)B A 析取三段论 (AB)(BC) (AC) 假言三段论 (AB)(BC) (AC) 等价三段论 (AB)(CD)(AC) (BD) 构造性二难,推理定律 (续,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号. 证明的形式结构

9、为: (pq)pq 证明（用等值演算法） (pq)pq (pq)p)q pqq 1 得证推理正确,实例 (续,2) 若今天是1号，则明天是5号. 明天是5号. 所以今天是1号. 解 设p：今天是1号，q：明天是5号. 证明的形式结构为: (pq)qp 证明（用主析取范式法） (pq)qp (pq)qp (pq)q)p qp (pq)(pq) (pq)(pq) m0m2m3 结果不含m1, 故01是成假赋值，所以推理不正确,重要的推理定律（重言蕴涵式 ） A (AB) 附加律 (AB) A 化简律 (AB)A B 假言推理 (AB)B A 拒取式 (AB)B A 析取三段论 (AB)(BC) (

10、AC) 假言三段论 (AB)(BC) (AC) 等价三段论 (AB)(CD)(AC) (BD) 构造性二难,推理定律 (续,AB)(AB)(AA) B 构造性二难（特殊形式） (AB)(CD)( BD) (AC) 破坏性二难,说明： A, B, C为元语言符号 若某推理符合某条推理定律，则它自然是正确的 AB产生两条推理定律: A B, B A,3.2 自然推理系统P,判断推理是否正确的三种常用方法： 1.真值表技术 2.演绎法 3.间接证明方法 当命题变项较多时，以上三种方法的演算量太大，此时可考虑推理证明的方法。而要构造严谨的证明必须要在形式系统中进行,形式系统的定义,一个形式系统I由下面

11、四个部分组成： （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

12、、字母表 （1）命题变项符号：p，q，r， （2）联结词符号： , , , , （3）括号与逗号 ： （ ） ， ， 2、合式公式 (参见定义1.6 P10） 3、 推理规则,推理规则,1）前提引入规则 ：在证明的任何步骤上都可以引入前提。 （2）结论引入规则：在证明的任何步骤上所得到的结论都可以做为后续证明的前提。 （3）置换规则：在证明的任何步骤上所得到的结论都可以作为后续证明的前提,推理规则 （续,4) 假言推理规则 AB A B (5) 附加规则 A AB,推理规则(续,构造证明直接证明法,例3.3 在自然推理系统P中构造下面推理的证明； （1） 前提：p q， q r， p s ，

13、s 结论：r （p q） （2）前提： p q， r q ，r s 结论：p s,1） 前提：p q， q r， p s ， s 结论：r （p q,证明: (1) p s 前提引入 (2) s 前提引入 (3) p (1)(2)拒取式 (4) p q 前提引入 (5) q (3)(4)析取三段论 (6) q r 前提引入 (7) r (5)(6)假言推理 (8) r （p q） (7)(4)合取,2）前提： p q， r q ，r s 结论：p s,证明： (1) p q 前提引入 (2) p q (1)置换 (3) r q 前提引入 (4) q r (3)置换 (5) p r (2)(4)

14、假言三段论 (6) r s 前提引入 (7) p s (5)(6)假言三段论,构造证明直接证明法,例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

15、) 前提引入 (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 理由： (A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2AkC)B,将 C 称 为 附 加 前 提,附加前提证明法,例3.5 在自然推理系统P中构造下面推理的证明。 如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王去看电影。所以，当小赵去看电影时，

16、小李也去。 解：将简单命题符号化： p：小张去看电影 q：小王去看电影 r：小李去看电影 s：小赵去看电影,前提：（p q） r ， s p ，q结论：s r,证明：(1) s 附加前提引入 (2) s p 前提引入 (3) p (1)(2)析取三段论 (4) （p q） r 前提引入 (5) q 前提引入 (6) p q (3)(5)合取 (7) r (4)(6)假言推理,附加前提证明法 (续,例 构造下面推理的证明: 2是素数或合数. 若2是素数，则 是无理数. 若 是无理数，则4不是素数. 所以，如果4是 素数，则2是合数. 用附加前提证明法构造证明 解 设 p：2是素数，q：2是合数，

17、 r： 是无理数，s：4是素数 形式结构 前提：pq, pr, rs 结论：sq,附加前提证明法 (续,证明 s 附加前提引入 pr 前提引入 r s 前提引入 p s 假言三段论 p 拒取式 pq 前提引入 q 析取三段论 请用直接证明法证明之,构造证明归谬法（反证法,欲证明 前提：A1, A2, , Ak 结论：B 将B加入前提，若推出矛盾，则得证推理正确. 理由: A1A2AkB (A1A2Ak)B (A1A2AkB) 括号内部为矛盾式当且仅当 (A1A2AkB) 为重言式,归谬法 (续,例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)(