第三章命题逻辑的推理理论

1、第三章 命题逻辑的推理理论第第1节节 推理的形式结构推理的形式结构 一、有效推理一、有效推理 数理逻辑的主要任务是用数学的方法来研究数数理逻辑的主要任务是用数学的方法来研究数学中的推理学中的推理. 所谓推理是指从前提出发推出结论的思所谓推理是指从前提出发推出结论的思维过程，而前提是已知命题公式集合，结论是从前提维过程，而前提是已知命题公式集合，结论是从前提出发应用推理规则推出的命题公式出发应用推理规则推出的命题公式. 要研究推理就应要研究推理就应该给出推理的形式结构，为此，首先应该明确什么样该给出推理的形式结构，为此，首先应该明确什么样的推理是有效的或正确的的推理是有效的或正确的. 定义3.1

2、 设A1, A2, , Ak, B为命题公式. 若对于每组赋值，A1A2 Ak 为假，或当A1A2Ak为真时，B也为真，则称由前提A1, A2, , Ak推出结论B的推理是有效的或正确的, 并称B是有效结论.关于定义关于定义3.1几点说明：几点说明： 1) 由前提由前提 A1, A2, , Ak 推结论推结论 B 的推理是否正确的推理是否正确 与诸前提的排列次序无关。前提的公式是一个有与诸前提的排列次序无关。前提的公式是一个有 限的公式集合。限的公式集合。 若推理是正确的，则记为若推理是正确的，则记为 B ，否则记为，否则记为 B . 记记 = A1, A2, , Ak ，将由将由推推 B 的

3、推理记为的推理记为 B .这里，可以称这里，可以称 B和和 A1, A2, , Ak B为为推理的形推理的形式结构式结构. 2）设）设A1, A2, , Ak ，B中共出现中共出现n个命题变项，个命题变项，对于任何一组赋值对于任何一组赋值1,2, , n( i =0或者或者1，i=1, 2, , n )，前提和结论的取值情况有以下四种：，前提和结论的取值情况有以下四种： (i) A1A2 Ak为为0，B为为0.(ii) A1A2 Ak为为0，B为为1. (iv) A1A2 Ak为为1，B为为1.(iii) A1A2 Ak为为1，B为为0. 由定义由定义3.1可知，只要不出现可知，只要不出现 (

4、iii) 中的情况中的情况. 推理就是正确的，因而判断推理是否正确，就是推理就是正确的，因而判断推理是否正确，就是判断是否会出现判断是否会出现 (iii) 中的情况。中的情况。 3) 推理正确，并不能保证结论推理正确，并不能保证结论B一定为真，这一定为真，这与数学中的推理是不同的与数学中的推理是不同的. 例例3.1 判断下列推理是否正确：判断下列推理是否正确： 解解 只要写出前提的合取式与结论的真值只要写出前提的合取式与结论的真值表，看是否出现前提合取式为真，而推论表，看是否出现前提合取式为真，而推论为假的情况。为假的情况。 (1) p,pq q (2) p,qp q 表表3.1 (1) 由表

5、由表3.1可知可知, (1)中推理正确，即中推理正确，即p, pq q . (2) 由表由表3.1可知可知, (2)推理不正确，即推理不正确，即p, qp q . (A1A2Ak )B 为为. 二、有效的推理的等价定理二、有效的推理的等价定理证证 明明 首先证明其必要性：首先证明其必要性： 若若 A1, A2, , Ak 推推 B 的推理正确，则对的推理正确，则对于于A1, A2, , Ak, B 中所含命题变项的任意一中所含命题变项的任意一组赋值，不会出现组赋值，不会出现 A1A2Ak为真，为真，而而 B 为假的情况，因而在任何赋值下，蕴涵为假的情况，因而在任何赋值下，蕴涵式式(A1A2Ak

6、 )B均为真，故它为重均为真，故它为重言式言式. 再证明其充分性：再证明其充分性： 若蕴涵式若蕴涵式(A1A2Ak)B为重言式为重言式，则对于任何赋值此蕴涵式均为真，因而不，则对于任何赋值此蕴涵式均为真，因而不会出现前件为真后件为假的情况，即在任何会出现前件为真后件为假的情况，即在任何赋值下，或者赋值下，或者A1A2Ak为假，或者为假，或者A1A2Ak和和 B同时为真，这正符合定同时为真，这正符合定义义3.1中推理正确的定义。中推理正确的定义。 前提：前提：A1, A2, , Ak 结论：结论：B 有时可以更直观地将有时可以更直观地将 A1, A2, , AkB表达为：表达为： (1) 由此定

7、理由此定理3.1知，推理形式：知，推理形式： 前提：前提：A1, A2, , Ak 结论：结论：B 是有效的是有效的当且仅当当且仅当(A1A2Ak)B为重言式为重言式.(2) (A1A2Ak)B 也称为上述也称为上述推理的形推理的形式结构式结构.这样，也可以将例3.1中的两个推理写成： (1) p,pq q (2) p,qp q 推理的形式结构：推理的形式结构：推理的形式结构：推理的形式结构：(P(pq ) q(P(qp ) q(3) 推理的有效性等价于它的形式结构为永真式推理的有效性等价于它的形式结构为永真式. 可记为可记为 其中其中 同同 一样是一种元语言符号，用一样是一种元语言符号，用来

8、表示蕴涵式为重言式来表示蕴涵式为重言式.A1A2Ak B A1, A2, , Ak B 于是，推理正确于是，推理正确 3 判断推理是否正确判断推理是否正确 ( 即判断命题公式永真性即判断命题公式永真性 ) 有三个方法：有三个方法： (1) 真值表法真值表法 (2) 等值演算法等值演算法 (3) 主析取范式法主析取范式法 例3.2 判断下面推理是否正确(1) 若今天是1号，则明天是5号. 今天是1号. 所以, 明天是5号. (2) 若今天是1号，则明天是5号. 明天是5号. 所以, 今天是1号. 解 设 p：今天是1号，q：明天是5号. (1) 推理的形式结构: (pq)pq用等值演算法 (pq

9、)pq (pq)p)q pqq 1 由定理3.1可知推理正确(2) 推理的形式结构:(pq)qp 用主析取范式法 (pq)qp (pq)qp (pq)q)p qp (pq)(pq) (pq)(pq) m0m2m3结果不含m1, 故01是成假赋值，所以推理不正确. 由上一个小节可以看出：形如由上一个小节可以看出：形如AB的重言式的重言式在推理中十分重要。在推理中十分重要。 若若AB为重言式，则称为重言式，则称B为为A的推论的推论，记为，记为A B， 2. (AB) A 化简律化简律 1. A (AB) 附加律附加律 下面是几个重要的重言蕴涵式及其名称下面是几个重要的重言蕴涵式及其名称:三、重言蕴

10、涵式三、重言蕴涵式( (推理定律推理定律) )3. (AB)A B 假言推理假言推理 4. (AB)B A 拒取式拒取式5. (AB)B A 析取三段论析取三段论 6. (A 6. (A B) (B B) (B C)(A C)(A C)C)假言三段论假言三段论 7.(A B) (B C) (A C)7.(A B) (B C) (A C)等价三段论等价三段论 8 8. .( (A A B B) ) ( (C C D D) ) ( (A AC C) ) ( (B BD D) ) 构造性二难构造性二难 构造性二难构造性二难 (特殊形式特殊形式) 9.(A 9.(A B) (C B) (C D) (

11、BD)( AC)D) ( BD)( AC)破坏性二难破坏性二难 BBABA)()(关于九条推理定律的几点说明关于九条推理定律的几点说明 (1) 出现的出现的 A, B, C 等依然是元语言符号等依然是元语言符号, 它们它们代表的是任意公式代表的是任意公式, 因而这些推理定律全是以模式因而这些推理定律全是以模式的形式出现的的形式出现的. (2) 若一个推理的形式结构与某条推理定律对应若一个推理的形式结构与某条推理定律对应的蕴的蕴涵式一致涵式一致, 则不用证明就可断定这个推理则不用证明就可断定这个推理是正确的是正确的, 只需说明用了某条推理定律即可只需说明用了某条推理定律即可. (3) 上一章给出

12、的上一章给出的 24 个等值式中的每一个等值式中的每一个都可派生出两条推理定律个都可派生出两条推理定律. (4) 在下一节将看到在下一节将看到, 由九条推理定律可由九条推理定律可以产生九条推理规则以产生九条推理规则. 它们构成了推理系统它们构成了推理系统中的推理规则中的推理规则. 如如, 由由AA可产生可产生 AA 和和 AA作业：作业： P526. (2) (6)第第2节节 自然推理系统自然推理系统 P定义定义 3.2 一个推理系统一个推理系统I由下面四个部分组成：由下面四个部分组成： 1. 定义定义（1） 非空的字符表集，记作非空的字符表集，记作 A(I) .（2） A(I) 中符号构造的

13、合式公式集，记作中符号构造的合式公式集，记作 E(I). 一、推理形式系统一、推理形式系统（3） E(I) 中一些特殊的公式组成的公理集，记作中一些特殊的公式组成的公理集，记作 AX(I). （4） 推理规则集，记作推理规则集，记作R(I)。 命题逻辑系统的公理：公理模式中P,Q,R为任意公式1).公理模式A1： R (QR)2).公理模式A2： (P (QR) (PQ) (PR)3).公理模式A3： (QR) (RQ) 把某些所要肯定的公式选出，作为推导其它所要肯定的公式的出发点，这些作为出发点的公式称为公理。可以将形式系统可以将形式系统 I 记为四元组记为四元组 ， 为为 I 的的形式演算

14、系统形式演算系统. 其中其中 是是 I 的的形式语言系统，形式语言系统， 一类是一类是自然推理系统自然推理系统, 它的特点是从任意给定的它的特点是从任意给定的前提出发，应用系统中的推理规则进行推理演算，前提出发，应用系统中的推理规则进行推理演算，得到的最后命题公式是推理的结论（有时称为有效得到的最后命题公式是推理的结论（有时称为有效的结论，它可能是重言式，也可能不是）的结论，它可能是重言式，也可能不是）. 另一类是另一类是公理推理系统公理推理系统，它只能从若干给定的，它只能从若干给定的公理出发，应用系统中推理规则进行推理演算，得公理出发，应用系统中推理规则进行推理演算，得到的到的结论是系统中的

15、结论是系统中的重言式重言式，称为系统中的定理，称为系统中的定理. .我们只介绍自然推理系统我们只介绍自然推理系统 P，它的定义中无公理部分，它的定义中无公理部分. . P是一个自然推理系统，因而没有公理是一个自然推理系统，因而没有公理. 故故P只有三只有三个部分。个部分。 定义定义3.3 自然推理系统自然推理系统P定义如下：定义如下： 1字母表字母表二、自然推理系统二、自然推理系统 P（1） 命题变项符号：命题变项符号：p，q，r，,pi，qi，ri， （2） 联结词符号：联结词符号：, （3） 括号和逗号：括号和逗号：( )， 2合式公式合式公式 同定义同定义1.63推理规则推理规则 (1)

16、 前提引入规则：前提引入规则：在证明的任何步骤上都可以在证明的任何步骤上都可以引入前提引入前提. (2) 结论引入规则：结论引入规则：在证明的任何步骤上所得到在证明的任何步骤上所得到的结论都可以作为后继证明的前提的结论都可以作为后继证明的前提. (3) 置换规则：置换规则：在证明的任何步骤上，命题公式在证明的任何步骤上，命题公式中的子公式都可以用与之等值的公式置换，得到公中的子公式都可以用与之等值的公式置换，得到公式序列中的又一个公式式序列中的又一个公式. 由九条推理定律和结论引入规则还可以导出以下各由九条推理定律和结论引入规则还可以导出以下各条推理定律。条推理定律。 (4) 假言推理规则（或

17、称分离规则）：假言推理规则（或称分离规则）：若证明的公若证明的公 式序列中已出现过式序列中已出现过AB和和A，则由假言推理定律，则由假言推理定律 (AB)AB 可知，可知，B是是AB和和A的有效结论的有效结论. 由结由结论引入规则可知，可将论引入规则可知，可将B引入到命题序列中来引入到命题序列中来. 用图式用图式表示为如下形式：表示为如下形式： ABAB以下各条推理定律直接以图式给出以下各条推理定律直接以图式给出. （5） 附加规则：附加规则： AAB （6） 化简规则：化简规则： ABA（7） 拒取式规则：拒取式规则： ABBA （8） 假言三段论规则：假言三段论规则： A A B BB B

18、 C CA A C C （9） 析取三段论规则：析取三段论规则： B BABABA A （10） 构造性二难推理：构造性二难推理： ABABCDCDACACBDBD（11） 破坏性二难推理规则：破坏性二难推理规则： BDBDADADABABCDCD （12） 合取引入规则：合取引入规则： A A B BABAB本条规则说明，若证明的公式序列中已出现本条规则说明，若证明的公式序列中已出现 A 和和B , 则可将则可将 AB 引入序列中。引入序列中。 P中的证明就是由一组中的证明就是由一组P中公式作为前提，利中公式作为前提，利用用P中的规则，推出结论中的规则，推出结论.在自然推理系统在自然推理系统

19、P中，中，构造形式结构为构造形式结构为三、自然系统三、自然系统P P中的证明中的证明的推理，在对其证明时，首先写出：的推理，在对其证明时，首先写出：前提：前提： 12,kA AA结论：结论： B然后用定义然后用定义3.3中给出的推理规则进行证明中给出的推理规则进行证明.12kAAAB 设前提A1, A2, Ak,结论B及公式序列C1, C2, Cl. 如果每一个i(1il)是某个Aj, 或者可由序列中前面的公式应用推理规则得到, 并且Cl =B, 则称这个公式序列是由A1, A2, Ak推出B的证明.例例3.3 在自然推理系统在自然推理系统P中构造下面推理的证明：中构造下面推理的证明： (1)

20、 前提：前提：pq, qr, ps, s 结论：结论：r(pq) (2) 前提：前提：pq, rq , rs 结论：结论：ps 解解 (1) 证明：证明： ps 前提引入前提引入 s 前提引入前提引入 p 拒取式拒取式 pq 前提引入前提引入 q 析取三段论析取三段论 qr 前提引入前提引入 r 假言推理假言推理 r(pq) 合取合取 此证明的序列长为此证明的序列长为8,最后一步为推理的结论最后一步为推理的结论,所以推理正确，即所以推理正确，即 r(pq) 是有效结论是有效结论. (1) 前提：前提：pq,qr, ps, s 结论：结论：r(pq) pr 假言三段论假言三段论 rq 前提引入前

21、提引入 qr 置换置换 rs 前提引入前提引入 ps 假言三段论假言三段论 (2) 证明：证明： pq 前提引入前提引入 pq 置换置换因此，因此，ps 是有效结论是有效结论 . (2) 前提：前提：pq, rq , rs 结论：结论：ps 例例3.4 在自然推理系统在自然推理系统P中构造下面推理的证明：中构造下面推理的证明： 若数若数 a 是实数，则它不是有理数就是无理数；是实数，则它不是有理数就是无理数；若若 a 不能表示成分数，则它不是有理数；不能表示成分数，则它不是有理数；a 是实数且它不能表示成分数是实数且它不能表示成分数. 所以所以 a 是无理数是无理数. 解解 首先将简单命题符号

22、化：首先将简单命题符号化： 设设 p：a 是实数是实数. q：a 是有理数是有理数. r：a 是无理数是无理数. s：a 能表示成分数能表示成分数.前提：前提：p(qr), sq, ps 结论：结论：r 证明：证明： ps 前提引入前提引入 s 化简化简 p(qr) 前提引入前提引入 p 化简化简 qr 假言推理假言推理 r 析取三段论析取三段论 sq 前提引入前提引入 q 假言推理假言推理 有时推理的形式结构具有如下形式有时推理的形式结构具有如下形式（A1A2Ak)(AB) （3.5） （3.5）式中结论也为蕴涵式）式中结论也为蕴涵式. 此时可将结论中此时可将结论中的前件也作为推理的前提，使

23、结论只为的前件也作为推理的前提，使结论只为B. 即，即，（3.5）化为下述形式）化为下述形式 (A1A2AkA)B （3.6） 四四 附加前提法附加前提法下面介绍证明常用的的两种方法：下面介绍证明常用的的两种方法： 其正确性证明如下：其正确性证明如下： （A1A2Ak)(AB) (A1A2Ak)(A B） (A1A2AkA)B (A1A2AkA)B (A1A2Ak)A)B 可见（可见（3.5）式与（）式与（3.6）式是等值的）式是等值的. 用形式结构（用形式结构（3.6）式证明，将）式证明，将A称为附加前提，称为附加前提，并称此证明法为并称此证明法为附加前提证明法附加前提证明法. 例例3.5

24、在自然推理系统在自然推理系统P中构造下面推理的证明中构造下面推理的证明. 如果小张和小王去看电影，则小李也去看电影如果小张和小王去看电影，则小李也去看电影;小赵不去看电影或小张去看电影；小王去看电影小赵不去看电影或小张去看电影；小王去看电影.所以，当小赵去看电影时，小李也去看电影所以，当小赵去看电影时，小李也去看电影. 解解: 将简单命题符号化：将简单命题符号化： 设设 p:小张去看电影小张去看电影. q:小王去看电影小王去看电影. r:小李去看电影小李去看电影. s:小赵去看电影小赵去看电影. 前提：前提：(pq)r, 结论：结论：sr sp, q 前提：前提：(pq)r, sp, q 结论

25、：结论：sr 证明：证明： (pq)r 前提引入前提引入 sr 假言三段论假言三段论 q (p r) 置换置换 q 前提引入前提引入 p r 假言推理假言推理 sp 前提引入前提引入 s p 置换置换(pq)r (pq) r p q r p (q r) q p r p (q r) q (p r)(pq)r p (q r) q (p r)前提：前提：(pq)r, sp, q 结论：结论：sr 证明：证明：用附加前提证明法用附加前提证明法. sp 前提引入前提引入 s 附加前提引入附加前提引入 p 析取三段论析取三段论 pq 合取合取 (pq)r 前提引入前提引入 q 前提引入前提引入 r 假言推理假言推理 在构造形式结构为在构造形式结构为(A1A2Ak)B 的推的推理证明中，如果将理证明中，如果将B作为前提能推出矛盾来，比作为前提能推出矛盾来，比如说得出如说