ch03命题逻辑的推理理论.ppt

09:35:38,1,主要内容 推理的形式结构 自然推理系统P推理的正确与错误 判断推理正确的方法 推理定律 形式系统的定义与分类 自然推理系统P 在P中构造证明:直接证明法、附加前提证明法、归谬法,第三章 命题逻辑的推理理论,09:35:38,2,3.1 推理的形式结构,定义3.1 设A1, A2, , Ak, B为命题公式. 若对于每组赋值，A1A2 Ak 为假，或当A1A2Ak为真时，B也为真，则称由前提A1, A2, , Ak推出结论B的推理是有效的或正确的, 并称B是有效结论.,定理3.1 由命题公式A1, A2, , Ak 推B的推理正确当 且仅当A1A2AkB为重言式,09:35:38,3,3.1 推理的形式结构,注意: 推理正确不能保证结论一定正确 必须把推理的有效性和结论的真实性区别开。有效的推理不一定产生真实的结论，产生真实结论的推理过程未必一定是有效的。再说，有效的推理中可能包含假的前提；而无效的推理却可能包含真的前提。,09:35:38,4,3.1 推理的形式结构,可见，推理的有效性是一回事，前提与结论的真实与否是另一回事。所谓推理有效，指它的结论是它的前提的合乎逻辑的结果，也即，如果它的前提都为真，那么所得结论也必然为真，而并不是要求前提或结论一定为真或为假。如果推理是有效的话，那么不可能它的前提都为真时而它的结论为假。,09:35:38,5,推理的形式结构,2. A1A2AkB 若推理正确, 记为A1 A2 Ak B 3. 前提： A1, A2, , Ak 结论： B 判断推理是否正确的方法: 真值表法 等值演算法 主析取范式法,推理的形式结构 1. A1, A2, , Ak B 若推理正确, 记为A1,A2,An B,09:35:38,6,推理实例,例1 判断下面推理是否正确 (1) 若今天是1号，则明天是5号. 今天是1号. 所以, 明天是5号. (2) 若今天是1号，则明天是5号. 明天是5号. 所以, 今天是1号.,解 设 p：今天是1号，q：明天是5号. (1) 推理的形式结构:,(pq)pq,用等值演算法 (pq)pq (pq)p)q pqq 1 由定理3.1可知推理正确,09:35:38,7,推理实例,(2) 推理的形式结构:,(pq)qp,用主析取范式法 (pq)qp (pq)qp (pq)q)p qp (pq)(pq) (pq)(pq) m0m2m3 结果不含m1, 故01是成假赋值，所以推理不正确,09:35:38,8,推理实例,例2 判断下面推理是否正确 如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王也去看电影。所以，当小赵去看电影时，小李必定也去。 解：令 p: 小张去看电影； q: 小王去看电影； r: 小李去看电 影； s: 小赵去看电影。 推理的形式结构: 前提： (p q) r, sp, q 结论： s r ( (p q) r) ( sp) q (s r),推理的形式结构:,09:35:38,9,推理定律重言蕴涵式,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) (AC) 等价三段论 8. (AB)(CD)(AC) (BD) 构造性二难 (AB)(AB) B 构造性二难(特殊形式) 9. (AB)(CD)( BD) (AC) 破坏性二难 每个等值式可产生两个推理定律 如, 由AA可产生 AA 和 AA,09:35:38,10,自然推理系统简介,自然推理系统。与公理系统相对，是按照自然演绎思想构造的形式系统。其出发点是一些变形规则或推演规则，但没有公理。应用变形规则可以推出一些定理。 自然推理系统更接近于一般的数学思维，所以许多成熟的逻辑演算公理系统都有与之等价的自然推理系统。自然推理系统是在世纪年代第一次分别由甘岑和杰司柯夫斯基独立提出。自然推理系统主要是强调推理规则的重要性，通过对规则的应用可以从假设得出推断。,09:35:38,11,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 的形式演算系统. 自然推理系统: 无公理, 即AX(I)= 公理推理系统 推出的结论是系统中的重言式, 称作定理,09:35:38,12,自然推理系统P,定义3.3 自然推理系统 P 定义如下: 1. 字母表 (1) 命题变项符号：p, q, r, , pi, qi, ri, (2) 联结词符号：, , , , (3) 括号与逗号：(, ), ， 2. 合式公式（同定义1.6） 3. 推理规则 (1) 前提引入规则 (2) 结论引入规则 (3) 置换规则,09:35:38,13,推理规则,(4) 假言推理规则 (6) 化简规则 (8) 假言三段论规则,(5) 附加规则 (7) 拒取式规则 (9) 析取三段论规则,09:35:38,14,推理规则,(10) 构造性二难推理规则 (11) 破坏性二难推理规则 (12) 合取引入规则,09:35:38,15,在自然推理系统P中构造证明,设前提A1, A2, Ak,结论B及公式序列C1, C2, Cl.如果每一个Ci(1il)是某个Aj, 或者可由序列中前面的公式应用推理规则得到, 并且Cl =B, 则称这个公式序列是由A1, A2, Ak推出B的证明,09:35:38,16,在自然推理系统P中构造证明,例3 构造下面推理的证明： 若明天是星期一或星期三，我明天就有课. 若我明天有 课，今天必备课. 我今天没备课. 所以，明天不是星期一、也不是星期三. 解 (1) 设命题并符号化 设 p：明天是星期一，q：明天是星期三， r：我明天有课，s：我今天备课,09:35:38,17,直接证明法,(2) 写出证明的形式结构 前提：(pq)r, rs, s 结论：pq (3) 证明 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 拒取式 pq 置换,09:35:38,18,附加前提证明法,附加前提证明法: 适用于结论为蕴涵式 欲证 前提：A1, A2, , Ak 结论：CB 等价地证明 前提：A1, A2, , Ak, C 结论：B 理由：(A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2AkC)B,09:35:38,19,附加前提证明法实例,例4 构造下面推理的证明 2是素数或合数. 若2是素数，则 是无理数. 若 是无理数，则4不是素数. 所以，如果4是素数，则2是合数. 解 用附加前提证明法构造证明 (1) 设 p：2是素数，q：2是合数， r： 是无理数，s：4是素数 (2) 推理的形式结构 前提：pq, pr, rs 结论：sq,09:35:38,20,附加前提证明法实例,(3) 证明 s 附加前提引入 pr 前提引入 rs 前提引入 ps 假言三段论 p 拒取式 pq 前提引入 q 析取三段论,09:35:38,21,归谬法（反证法）,归谬法 (反证法) 欲证 前提：A1, A2, , Ak 结论：B 做法: 在前提中加入B，推出矛盾. 理由 A1A2AkB (A1A2Ak)B (A1A2AkB) (A1A2AkB)0 A1A2AkB0,09:35:38,22,归谬法实例,例5 前提：(pq)r, rs, s, p 结论：q 证明 用归缪法 q 结论否定引入 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 析取三段论 pq 置换 p 析取三段论 p 前提引入 pp 合取,09:35:38,23,第三章 习题课,主要内容 推理的形式结构 判断推理是否正确的方法 真值表法 等值演算法 主析取范式法 推理定律 自然推理系统P 构造推理证明的方法 直接证明法 附加前提证明法 归谬法(反证法),09:35:38,24,基本要求,理解并记住推理形式结构的两种形式： 1. (A1A2Ak)B 2. 前提：A1, A2, , Ak 结论：B 熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等） 牢记 P 系统中各条推理规则 熟练掌握构造证明的直接证明法、附加前提证明法和归谬 法 会解决实际中的简单推理问题,09:35:38,25,练习1：判断推理是否正确,1. 判断下面推理是否正确: (1) 前提：pq, q 结论：p,解 推理的形式结构:,(pq)qp,方法一：等值演算法 (pq)qp (pq)q)p (pq)qp (pq)(qq)p pq,易知10是成假赋值，不是重言式，所以推理不正确.,09:35:38,26,练习1解答,方法二：主析取范式法， (pq)qp (pq)q)p pq M2 m0m1m3 未含m2, 不是重言式, 推理不正确.,09:35:38,27,练习1解答,方法三 真值表法 不是重言式, 推理不正确,方法四 直接观察出10是成假赋值,09:35:38,28,练习1解答,用等值演算法 (qr)(pr)(qp) (qr)(pr)(qp) (qr)(pr)(qp) (qp)(qr)(rp)(qp) (qp)(qr)(rp)(qp) 1 推理正确,(2) 前提：qr, pr 结论：qp,解 推理的形式结构：,(qr)(pr)(qp),09:35:38,29,练习2：构造证明,2. 在系统P中构造下面推理的证明： 如果今天是周六，我们就到颐和园或圆明园玩. 如果颐和 园游人太多，就不去颐和园. 今天是周六，并且颐和园游 人太多. 所以, 我们去圆明园或动物园玩.,证明： (1) 设 p：今天是周六，q：到颐和园玩， r：到圆明园玩，s：颐和园游人太多 t：到动物园玩 (2) 前提：p(qr), sq, p, s 结论：rt,09:35:38,30,练习2解答,(3) 证明： p(qr) 前提引入 p 前提引入 qr 假言推理 sq 前提引入 s 前提引入 q 假言推理 r 析取三段论 rt 附加,09:35:38,31,命题逻辑在计算机科学中的应用,逻辑难题 可以用逻辑推理解决的难题称为逻辑难题。求解逻辑难题是实践逻辑规则的一种好方法。同样，涉及用于执行逻辑推理的计算机程序通常也使用著名的逻辑难题来演示它们的能力。许多人对求解逻辑难题感兴趣，有许多书和杂志也登载逻辑难题以供娱乐。,09:35:38,32,命题逻辑在计算机科学中的应用,这是著名物理学家爱因斯坦出过的一道题。 一个土耳其商人，想找一个十分聪明的助手协助他经商，有两个人前来应聘。这个商人为了试一试哪一个聪明些，就把两个人带进一间漆黑的屋子里，他打开电灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的。现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在头上，在我开灯后，请你们尽快地说出自己头上戴的帽子是什么颜色的。”说完之后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来接着把电灯打开，这时那两个应试者看到商人头上戴的是一顶红帽子，过了一会儿，其中一个人便喊到：“我戴的是黑帽子。” 请问这个人猜得对吗？是怎么推导出来的？,09:35:38,33,命题逻辑在计算机科学中的应用,分析1：如果我戴的也是红帽子，那么，B就马上可以猜到自己是戴黑帽子(因为红帽子只有两顶)；而现在B并没有立刻猜到，可见，我戴的不是红帽子。 可见，B的反应太慢了。,09:35:38,34,命题逻辑在计算机科学中的应用,分析2：设P1表示“猜对的人戴红帽子”；P2表示“猜对的人戴黑帽子”；Q1表示“另一个人戴红帽子”；Q2表示“另一个人戴黑帽子”；R1表示“商人戴红帽子”。 现在知道，商人头上戴的是红帽子，即R1为真，又知道另一个人没有作出断定，即既不能断定Q1为真，也不能断定Q2为真。,09:35:38,35,命题逻辑在计算机科学中的应用,根据题设条件，可得如下公式： R1P1Q2：如果商人和猜对的人戴的都是红帽子，那么另一个戴的就是黑帽子，因为红帽子只有两顶。 R1Q1P2：如果商人和另一个戴的都是红帽子，那么猜对的人戴的就是黑帽子。 P1P2：如果猜对的人戴的不是红帽子，那么他戴的就是黑帽子。 Q1Q2：如果另一个人戴的不是红帽子，那