ch3命题逻辑的推理

1、ch3命题逻辑的推理3.1 推理的形式构造定义 设A1, A2, , Ak, B为命题公式. 假设对于每组赋值，A1A2 Ak 为假，或当A1A2Ak为真时，B也为真，那么称由前提A1, A2, , Ak推出结论B的推理是有效的或正确的, 并称B是有效结论.例3.1 判断以下推理是否正确1 p,pq|-q2 p,qp|-q真值表法注意: 推理正确不能保证结论一定正确23.1 推理的形式构造33.1 推理的形式构造定义 设A1, A2, , Ak, B为命题公式. 假设对于每组赋值，A1A2 Ak 为假，或当A1A2Ak为真时，B也为真，那么称由前提A1, A2, , Ak推出结论B的推理是有效

2、的或正确的, 并称B是有效结论.定理 由命题公式A1, A2, , Ak 推B的推理正确当且仅当A1A2AkB为重言式注意: 推理正确不能保证结论一定正确4推理的形式构造2. A1A2AkB 假设推理正确, 记为A1 A2 Ak B3. 前提： A1, A2, , Ak 结论： B判断推理是否正确的方法: 真值表法 等值演算法 主析取范式法推理的形式结构1. A1, A2, , Ak B 若推理正确, 记为A1,A2,An B5推理的形式构造2. A1A2AkB 假设推理正确, 记为A1 A2 Ak B3. 前提： A1, A2, , Ak 结论： B判断推理是否正确的方法: 真值表法 等值演

3、算法 主析取范式法推理的形式结构1. A1, A2, , Ak B 若推理正确, 记为A1,A2,An B6推理实例例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 由定理可知推理正确7推理实例 用主析取范式法 (pq)qp (pq)qp (pq)q)p qp (pq)(pq) (pq)(pq) m0m2m3 结果不含m1, 故0

4、1是成假赋值，所以推理不正确(2) 假设今天是1号，那么明天是5号. 明天是5号. 所以, 今天是1号. 推理的形式构造:(pq)qp8推理定律重言蕴涵式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 和 A

5、A93.2 自然推理系统P定义 一个形式系统 I 由下面四个局部组成： (1) 非空的字母表，记作 A(I). (2) A(I) 中符号构造的合式公式集，记作 E(I). (3) E(I) 中一些特殊的公式组成的公理集，记作 AX(I). (4) 推理规那么集，记作 R(I). 记I=, 其中是 I 的形式语言系统, 是 I 的形式演算系统.自然推理系统: 无公理, 即AX(I)=公理推理系统 推出的结论是系统中的重言式, 称作定理10自然推理系统P定义3.3 自然推理系统 P 定义如下:1. 字母表 (1) 命题变项符号：p, q, r, , pi, qi, ri, (2) 联结词符号：,

6、, , , (3) 括号与逗号：(, ), ，2. 合式公式同定义3. 推理规那么 (1) 前提引入规那么 (2) 结论引入规那么 (3) 置换规那么11推理规那么(4) 假言推理规那么 (6) 化简规那么 (8) 假言三段论规那么 AB AB AAB AB A(5) 附加规那么 (7) 拒取式规那么 (9) 析取三段论规那么 AB BA AB BCACAB BA12推理规那么(10) 构造性二难推理规那么 (11) 破坏性二难推理规那么 (12) 合取引入规那么 AB CD AC BD AB CD BD AC A BAC13在自然推理系统P中构造证明设前提A1, A2, Ak,结论B及公式序

7、列C1, C2, Cl. 假设每一个Ci(1il)是某个Aj, 或者可由序列中前面的公式应用推理规那么得到, 并且Cl =B, 那么称这个公式序列是由A1, A2, Ak推出B的证明例2 构造下面推理的证明： 假设明天是星期一或星期三，我明天就有课. 假设我明天有 课，今天必备课. 我今天没备课. 所以，明天不是星期一、 也不是星期三. 解 (1) 设命题并符号化 设 p：明天是星期一，q：明天是星期三， r：我明天有课，s：我今天备课14直接证明法(2) 写出证明的形式构造 前提：(pq)r, rs, s 结论：pq(3) 证明 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入

8、 (pq) 拒取式 pq 置换15附加前提证明法附加前提证明法 适用于结论为蕴涵式欲证 前提：A1, A2, , Ak 结论：CB等价地证明 前提：A1, A2, , Ak, C 结论：B理由： (A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2AkC)B16附加前提证明法实例例3 构造下面推理的证明 2是素数或合数. 假设2是素数，那么 是无理数. 假设 是无理数，那么4不是素数. 所以，假设4是素数，那么2是合数. 解 用附加前提证明法构造证明 (1) 设 p：2是素数，q：2是合数， r： 是无理数，s：4是素数 (2) 推理的形式构造 前提：pq,

9、 pr, rs 结论：sq 17附加前提证明法实例 (3) 证明 s 附加前提引入 pr 前提引入 rs 前提引入 ps 假言三段论 p 拒取式 pq 前提引入 q 析取三段论18归谬法反证法归谬法 (反证法)欲证 前提：A1, A2, , Ak 结论：B做法 在前提中参加B，推出矛盾.理由 A1A2AkB (A1A2Ak)B (A1A2AkB) (A1A2AkB)0 A1A2AkB019归谬法实例例4 前提：(pq)r, rs, s, p 结论：q证明 用归缪法 q 结论否认引入 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 析取三段论 pq 置换 p 析取三段论

10、 p 前提引入 pp 合取20第三章 习题课主要内容推理的形式构造判断推理是否正确的方法 真值表法 等值演算法 主析取范式法推理定律自然推理系统P构造推理证明的方法 直接证明法 附加前提证明法 归谬法(反证法)21根本要求理解并记住推理形式构造的两种形式： 1. (A1A2Ak)B 2. 前提：A1, A2, , Ak 结论：B纯熟掌握判断推理是否正确的不同方法如真值表法、等值演算法、主析取范式法等牢记 P 系统中各条推理规那么纯熟掌握构造证明的直接证明法、附加前提证明法和归谬 法会解决实际中的简单推理问题22练习1：判断推理是否正确1. 判断下面推理是否正确: (1) 前提：pq, q 结论

11、：p 解 推理的形式构造:(pq)qp 方法一：等值演算法 (pq)qp (pq)q)p (pq)qp (pq)(qq)p pq易知10是成假赋值，不是重言式，所以推理不正确.23练习1解答方法二：主析取范式法， (pq)qp (pq)q)p pq M2 m0m1m3未含m2, 不是重言式, 推理不正确.24练习1解答方法三 真值表法 不是重言式, 推理不正确111001110100(pq)qpqppq 0 1 1 1(pq)q 0 0 1 0方法四 直接观察出10是成假赋值25练习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) 26练习2：构造证明2. 在系统P中构造下面推理的证明： 假设今天是周六，我们就到颐和园或圆明园玩. 假设颐和 园游人太多，就不去颐和园. 今天是周六，并且颐和园游