资源预览内容
第1页 / 共25页
第2页 / 共25页
第3页 / 共25页
第4页 / 共25页
第5页 / 共25页
第6页 / 共25页
第7页 / 共25页
第8页 / 共25页
第9页 / 共25页
第10页 / 共25页
亲,该文档总共25页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
主要内容 推理的形式结构 l 推理的正确与错误 l 推理的形式结构 l 判断推理正确的方法 l 推理定律自然推理系统Pl 形式系统的定义与分类 l 自然推理系统P l 在P中构造证明:直接证明法、附加前提证明法、归谬法第三章 命题逻辑的推理理论13.1 推理的形式结构定义3.1 设A1, A2, , Ak, B为命题公式. 若对于每组赋值, A1A2 Ak 为假,或当A1A2Ak为真时,B也为真, 则称由前提A1, A2, , Ak推出结论B的推理是有效的或正确 的, 并称B是有效结论.定理3.1 由命题公式A1, A2, , Ak 推B的推理正确当且仅当 A1A2AkB为重言式注意: 推理正确不能保证结论一定正确2推理的形式结构2. A1A2AkB若推理正确, 记为A1 A2 Ak B 3. 前提: A1, A2, , Ak结论: B 判断推理是否正确的方法:真值表法等值演算法主析取范式法推理的形式结构 1. A1, A2, , Ak B若推理正确, 记为A1,A2,An B3推理实例例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可知推理正确4推理实例(2) 推理的形式结构:(pq)qp用主析取范式法(pq)qp (pq)qp (pq)q)p qp (pq)(pq) (pq)(pq) m0m2m3 结果不含m1, 故01是成假赋值,所以推理不正确5推理定律重言蕴涵式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 63.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)= 公理推理系统 推出的结论是系统中的重言式, 称作定理7自然推理系统P定义3.3 自然推理系统 P 定义如下: 1. 字母表(1) 命题变项符号:p, q, r, , pi, qi, ri, (2) 联结词符号:, , , , (3) 括号与逗号:(, ), , 2. 合式公式(同定义1.6) 3. 推理规则: (1)(12)(1) 前提引入规则:在证明的任何步骤都可以引入前提.(2) 结论引入规则:在证明的任何步骤所得的结论都有可以 作为后继证明的前提.(3) 置换规则:在证明的任何步骤,命题公式中的子公式都可 以用等值的公式置换,得到公式序列中又一个公式.8推理规则 (4) 假言推理规则(6) 化简规则(8) 假言三段论规则ABA BA ABAB A(5) 附加规则(7) 拒取式规则(9) 析取三段论规则ABB AABBC ACABB A 9推理规则(10) 构造性二难推理规则 (11) 破坏性二难推理规则(12) 合取引入规则ABCDAC BDABCDBD ACAB AC10在自然推理系统P中构造证明设前提A1, A2, Ak,结论B及公式序列C1, C2, Cl. 如果每 一个Ci(1il)是某个Aj, 或者可由序列中前面的公式应用推理 规则得到, 并且Cl =B, 则称这个公式序列是由A1, A2, Ak推 出B的证明例2 构造下面推理的证明:若明天是星期一或星期四,我明天就有课. 若我明天有课,今天必备课. 我今天没备课. 所以,明天不是星期一、也不是星期四. 解 (1) 设命题并符号化 设 p:明天是星期一,q:明天是星期四,r:我明天有课,s:我今天备课11直接证明法(2) 写出证明的形式结构前提:(pq)r, rs, s结论:pq (3) 证明 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 拒取式 pq 置换12附加前提证明法附加前提证明法 适用于结论为蕴涵式 欲证前提:A1, A2, , Ak结论:CB等价地证明前提:A1, A2, , Ak, C结论:B理由:(A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2AkC)B 13附加前提证明法实例例3 构造下面推理的证明2是素数或合数. 若2是素数,则 是无理数. 若 是无理 数,则4不是素数. 所以,如果4是素数,则2是合数. 解 用附加前提证明法构造证明(1) 设 p:2是素数,q:2是合数,r: 是无理数,s:4是素数(2) 推理的形式结构前提:pq, pr, rs结论:sq 14附加前提证明法实例(3) 证明 s 附加前提引入 pr 前提引入 rs 前提引入 ps 假言三段论 p 拒取式 pq 前提引入 q 析取三段论15归谬法(反证法) 归谬法 (反证法)欲证前提:A1, A2, , Ak 结论:B做法在前提中加入B,推出矛盾.理由A1A2AkB (A1A2Ak)B (A1A2AkB) (A1A2AkB)0 A1A2AkB0 16归谬法实例 例4 前提:(pq)r, rs, s, p 结论:q证明 用归缪法 q 结论否定引入 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 析取三段论 pq 置换 p 析取三段论 p 前提引入pp 合取 17第三章 小结 主要内容 l 推理的形式结构 l 判断推理是否正确的方法真值表法 等值演算法主析取范式法 l 推理定律 l 自然推理系统Pl 构造推理证明的方法直接证明法附加前提证明法归谬法(反证法) 18基本要求l 理解并记住推理形式结构的两种形式:1. (A1A2Ak)B2. 前提:A1, A2, , Ak 结论:Bl 熟练掌握判断推理是否正确的不同方法(如真值表法、等 值演算法、主析取范式法等) l 牢记 P 系统中各条推理规则l 熟练掌握构造证明的直接证明法、附加前提证明法和归谬 法 l 会解决实际中的简单推理问题19练习1:判断推理是否正确1. 判断下面推理是否正确:(1) 前提:pq, q结论:p 解 推理的形式结构: (pq)qp 方法一:等值演算法(pq)qp (pq)q)p (pq)qp (pq)(qq)p pq易知10是成假赋值,不是重言式,所以推理不正确. 20练习1解答方法二:主析取范式法,(pq)qp(pq)q)ppqM2m0m1m3 未含m2, 不是重言式, 推理不正确.21练习1解答方法三 真值值表法不是重言式, 推理不正确 1 1 1 0 0 1 1 1 0 1 0 0 (pq)qp q p p q 0 1 1 1 (pq) q 0 0 1 0方法四 直接观观察出10是成假赋值赋值22练习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) 23练习2:构造证明2. 在系统P中构造下面推理的证明:如果今天是星期六,我们就到颐和园或圆明园去玩. 如果 颐和园游人太多,我们就不去颐和园玩. 今天是星期六.颐 和园游人太多. 所以, 我们去圆明园或动物园玩. 证明:(1) 设 p:今天是周六,q:到颐和园玩,r:到圆明园玩,s:颐和园游人太多t:到动物园玩(2) 前提:p(qr), sq, p, s结论:rt24练习2解答(3) 证明: p(qr) 前提引入 p 前提引入 qr 假言推理 sq 前提引入 s
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号