第三章-代数系统

《第三章-代数系统》由会员分享，可在线阅读，更多相关《第三章-代数系统（36页珍藏版）》请在装配图网上搜索。

1、第三章第三章 命题逻辑的推理理论命题逻辑的推理理论3.1 推理的形式结构 前提（多个）结论推理推理推理：从前提出发推出结论的思维过程。前提：已知命题公式集合。结论：从前提出发应用推理规则推出的命题公式。要研究推理就应该给出推理的形式结构，为此，首先应该明确什么样的推理是有效的或正确的。定义定义3.1 设A1,A2,Ak和B都是命题公式，若对于A1,A2,Ak和B中出现的命题变项的任意一组赋值，或者A1A2 Ak为假，或者当A1A2 Ak为真时，B也为真，则称由前提A1,A2,Ak推出B的推理是有效的或正确的推理是有效的或正确的，并称B是有效结论有效结论。其中，前提是一个有限的公式集合，记为。将

2、由推B的推理记为 B。若推理是正确的，则记为 B，否则记为 B。称B 或 A1,A2,Ak B 为推理的形式结构。几点说明：1由 B是否正确与前提的排列次序无关。2.判断推理是否正确，就是判断是否会出现A1A2 Ak为1，B为0情况，如果不出现，就正确。3推理正确，并不能保证结论B一定为真，这与数学中的推理是不同的。例例3.1 判断下列推理是否正确：解：解：只要写出前提的合取式与结论的真值表，看是否出现前提合取式为真，而推论为假的情况。(1)p,pq q(2)p,qp q 3.1 推理的形式结构(1)由表可知，没有出现前提合取式为真，而结论为假的情况，因而(1)中推理正确，即 p,pq q(2

3、)由表可知，在赋值为1 0情况下，出现了前提合取式为真，而结论为假的情况，因而(2)推理不正确，即 p,qp q定理定理3.1 命题公式A1,A2,Ak推B的推理正确当且仅当 (A1A2Ak)B 为重言式重言式。证：证：必要性。若A1,A2,Ak推B的推理正确，则对于A1,A2,Ak,B中所含命题变项的任意一组赋值，不会出现A1A2Ak为真，而B为假的情况，因而在任何赋值下，蕴涵式(A1A2Ak)B均为真，故它为重言式。充分性:若蕴涵式(A1A2Ak)B为重言式，则对于任何赋值此蕴涵式均为真，因而不会出现前件为真后件为假的情况，即在任何赋值下，或者A1A2Ak为假，或者A1A2Ak和B同时为真

4、，这正符合定义3.1中推理正确的定义。由此定理知，推理形式：前提：A1,A2,Ak 结论：B 是有效的当且仅当(A1A2Ak)B为重言式。(A1A2Ak)B称为上述推理的形式结构。从而推理的有效性等价于它的形式结构为重言式。于是，推理正确于是，推理正确 A1,A2,AkB 可记为可记为 A1A2AkB判断是否为重言式有三个方法：1 真值表法 2 等值演算法 3 主析取范式法例3.2 判断下面推理是否正确：(1)下午马芳或去看电影或去游泳。她没去看电影。所以，她去游泳了。解：设 p:马芳下午去看电影 q:马芳下午去游泳 前提：pq，p 结论：q 推理的形式结构：（p q）p）q(p q)p)q(

5、p q)p)q (p q)p q 1所以，推理正确所以，推理正确（2）若下午气温超过30，则王小燕必去游泳，若她去游泳，她就不去看电影了。所以，若王小燕没去看电影，下午气温必超过了30。解：设 p:下午气温超过30 q:王小燕去游泳 r:王小燕去看电影 前提：p q，q r 结论：r p 推理的形式结构：(p q)(q r)(r p)(p q)(q r)(r p)(pq)(q r)(r p)(pq)(q r)(r p)(p q)(q r)(r p)(p q)p(q r)r(p(qq)(rr)(r(qq)(pp)m1 m3 m4 m5 m6 m7 所以，推理不正确所以，推理不正确重言蕴涵式（推理

6、定律）1A (AB)附加律附加律 2.(AB)A 化简律化简律 3.(AB)A B 假言推理假言推理 4.(AB)B A 拒取式拒取式 5.(AB)B A 析取三段论析取三段论 6.(AB)(BC)(AC)假言三段论假言三段论 7.(A B)(B C)(A C)等价等价三段论三段论 8.(AB)(CD)(AC)(BD)构造性二难 (AB)(AB)(AA)B 构造性二难 (特殊形式)9.(AB)(CD)(BD)(AC)破坏性二难 说明：说明：1.九条推理定律是一个模式，对应多种不同形式；九条推理定律是一个模式，对应多种不同形式；2.若一若一 个推理的形式结构与某条推理定律对应个推理的形式结构与某

7、条推理定律对应的蕴含式一致，就可直接判定推理正确；的蕴含式一致，就可直接判定推理正确；3.24个等值式中的每一个都派生出两条推理定律。个等值式中的每一个都派生出两条推理定律。3.2 自然推理系统P 将推理用更严谨的形式推理系统描述出来。定义定义3.2 一个形式系统形式系统 I 由下面四个部分组成：（1）非空的字符表集，记作A(I)。（2）A(I)中符号构造的合式公式集，记作E(I)。（3）E(I)中一些特殊的公式组成的公理集，记作AX(I)。（4）推理规则集，记作R(I)。可以将I记为 其中是I的形式语言系统形式语言系统，为I的形式演算系统形式演算系统。形式系统一般分为两类:一类是自然推理系统

8、自然推理系统，它的特点是从任意给定的前提出发，应用系统中的推理规则进行推理演算，得到的最后命题公式是推理的结论（有时称为有效的结论，它可能是重言式，也可能不是）。另一类是公理推理系统公理推理系统，它只能从若干给定的公理出发，应用系统中推理规则进行推理演算，得到的结论是系统中的重言式，称为系统中的定理。P是一个自然推理系统，因而没有公理。故P只有三个部分。定义定义3.3 自然推理系统自然推理系统P定义如下：1字母表（1）命题变项符号：p，q，r，,pi，qi，ri，（2）联结词符号：,（3）括号和逗号：(,)，2合式公式 同定义1.6（1）前提引入规则：在证明的任何步骤上都可以引入前提。（3）置

9、换规则：在证明的任何步骤上，命题公式中的子公式都可以用与之等值的公式置换，得到公式序列中的又一个公式。（2）结论引入规则：在证明的任何步骤上所得到的结论都可以作为后继证明的前提。3推理规则（4）假言推理规则（5）附加规则：（6）化简规则：（7）拒取式规则：（8）假言三段论规则：（9）析取三段论规则：（10）构造性二难推理：（11）破坏性二难推理规则：（12）合取引入规则：P中的证明就是由一组P中公式作为前提，利用P中的规则，推出结论。当然此结论也为P中公式。例例3.3 在自然推理系统P中构造下面推理的证明：(1)前提：前提：pq,qr,ps,s 结论：结论：r(pq)证明：证明：ps 前提引入

10、前提引入 s 前提引入前提引入 p 拒取式拒取式 pq 前提引入前提引入 q 析取三析取三段论段论 qr 前提引入前提引入 r 假言推假言推理理 r(pq)合取合取 此证明的序列长为8，最后一步为推理的结论，所以推理正确，r(pq)是有效结论。(2)前提：前提：pq,rq,rs 结论：结论：ps 证明：证明：pq 前提引入前提引入 pq 置换置换 rq 前提引入前提引入 qr 置换置换 pr 假言三段论假言三段论 rs 前提引入前提引入 ps 假言三段论假言三段论从最后一步可知推理正确，ps是有效结论。例例3.4 在自然推理系统P中构造下面推理的证明：若数a是实数，则它不是有理数就是无理数；若

11、a不能表示成分数，则它不是有理数；a是实数且它不能表示成分数。所以a是无理数。解解 首先将简单命题符号化：设 p：a是实数。q：a是有理数。r：a是无理数。s：a能表示成分数。前提：p(qr),sq,ps 结论：r 证明：证明：ps 前提引入前提引入 p 化简化简 s 化简化简 p(qr)前提引入前提引入 qr 假言推理假言推理 sq 前提引入前提引入 q 假言推理假言推理 r 析取三段析取三段论论 P中证明的两个常用技巧：中证明的两个常用技巧：1附加前提证明法附加前提证明法 2归谬法归谬法 1、附加前提法、附加前提法 若推理的形式结构具有如下形式若推理的形式结构具有如下形式（A1A2Ak)(

12、AB)（3.5）此时可将结论中的前件也作为推理的前提，使结论只此时可将结论中的前件也作为推理的前提，使结论只为为B。即，将（。即，将（3.5）化为下述形式）化为下述形式 (A1A2AkA)B （3.6）其正确性证明如下：其正确性证明如下：（A1A2Ak)(AB)）(A1A2Ak)(A B）(A1A2AkA)B (A1A2AkA)B (A1A2AkA)B因为（3.5）式与（3.6）式是等值的，因而若能证明（3.6）式是正确的，则（3.5）式也是正确的。用形式结构（3.6）式证明，将A称为附加前提附加前提，并称此证明法为附加前提证明法附加前提证明法。例例3.5 在自然推理系统P中构造下面推理的证明

13、。如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影。解解:将简单命题符号化：设 p:小张去看电影。q:小王去看电影。r:小李去看电影。s:小赵去看电影。前提：前提：(pq)r,sp,q 结论：结论：sr 证明：用附加前提证明法。证明：用附加前提证明法。思考？思考？不用附加前提证明法构造例不用附加前提证明法构造例3.5的证明。的证明。s 附加前提附加前提引入引入 sp 前提引入前提引入 p 析析取三段论取三段论 (pq)r 前提引入前提引入 q 前提引入前提引入 pq 合取合取 r 假言假言推理推理 2、归谬法、归谬法

14、在构造形式结构为在构造形式结构为(A1A2Ak)B 的推理证明中，如果将的推理证明中，如果将B作为前提能推出矛盾作为前提能推出矛盾来，比如说得出来，比如说得出(AA)，则说明推理正确。，则说明推理正确。(A1A2Ak)B(A1A2Ak)B(A1A2AkB)若若(A1A2AkB)为矛盾式，正说明为矛盾式，正说明(A1A2Ak)B为重言式，即为重言式，即(A1A2Ak)B 故推理正确。故推理正确。例例3.6 在自然推理系统在自然推理系统P中构造下面推理的证明。中构造下面推理的证明。如果小张守第一垒并且小李向如果小张守第一垒并且小李向B队投球，则队投球，则A队将取胜；或者队将取胜；或者A队未取胜，或

15、者队未取胜，或者A队获得联赛第一队获得联赛第一名；名；A队没有获得联赛的第一名；小张守第一垒。因队没有获得联赛的第一名；小张守第一垒。因此，小李没有向此，小李没有向B队投球。队投球。解解 先将简单命题符号化。先将简单命题符号化。设设 p:小张守第一垒。小张守第一垒。q:小李向小李向B队投球。队投球。r:A队取胜。队取胜。s:A队获得联赛第一名。队获得联赛第一名。前提：前提：(pq)r,rs,s,p 结论：结论：q q 结论的否定引入结论的否定引入 rs 前前提引入提引入 s 前前提引入提引入 r 析取析取三段论三段论(pq)r 前提前提引人引人 (pq)拒取式拒取式 pq 置置换换 p 前提引

16、入前提引入 q 析取三段论析取三段论 qq 合取合取前提：前提：(pq)r,rs,s,p 结论：结论：q 证明：用归谬法 由于最后一步qq 0，即(pq)r)(rs)sp)q 0，所以推理正确。思考：不用归谬法证明例3.6 这是著名物理学家爱因斯坦出过的一道题：一个土耳其商人，想找一个十分聪明的助手协助他经商，有两个人前来应聘。这个商人为了试一试哪一个聪明些，就把两个人带进一间漆黑的屋子里，他打开电灯后说：“这张桌子上有五顶帽子、两顶是红色的，三顶是黑色的。现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在头上，在我开灯后，请你们尽快地说出自己头上戴的帽子是什么颜色的。

17、”说完之后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把电灯打开。这时，那两个应试者看到商人头上戴的是一顶红帽子，过了一会儿，其中一个人便喊到：“我戴的是黑帽子。”请问这个人猜得对吗？是怎么推导出来的?设：P1表示“猜对的人戴红帽子”；P2表示“猜对的人戴黑帽子”；Q1表示“另一个人戴红帽子”；Q2表示“另一个人戴黑帽子”；R表示“商人戴红帽子”。我们知道，商人头上戴的是红帽子，即R为真，又知道另一个人没有作出断定，即既不能断定Q1为真，也不能断定Q2为真。根据题意，我们可得如下的公式：(1)RP1Q2 (2)RQ1P2(3)P1P2 (4)Q1Q2推演步骤如下：设P1 P1 (根据假设)R （根据题设）RP1 (合取规则)RP1Q2 (根据题设）Q2 (假言推理)这就是说，“另一个人戴黑帽子”这个判定是必然可以作出的但这与题设条件(即“另一个人没有作出判定”)相矛盾，因此，P1为假，即P1为真，故可得：P1 P1P2 (根据题设)P2 (假言推理)这就是说，“猜对的人戴黑帽子”是真的，所以猜对的人肯定地说：“我戴的是黑帽子”