ch3命题逻辑的推理理论

1、1主要内容推理的形式结构推理的正确与错误推理的形式结构判断推理正确的方法推理定律自然推理系统P形式系统的定义与分类自然推理系统P在P中构造证明:直接证明法、附加前提证明法、归谬法第三章 命题逻辑的推理理论23.1 推理的形式结构定义3.1 设A1, A2, , Ak, B为命题公式. 若对于每组赋值，A1A2 Ak 为假，或当A1A2Ak为真时，B也为真，则称由前提A1, A2, , Ak推出结论B的推理是有效的或正确的, 并称B是有效结论.定理3.1 由命题公式A1, A2, , Ak 推B的推理正确当且仅当A1A2AkB为重言式注意: 推理正确不能保证结论一定正确3推理的形式结构2. A1

2、A2AkB 若推理正确, 记为A1 A2 Ak B3. 前提： A1, A2, , Ak 结论： B判断推理是否正确的方法: 真值表法 等值演算法 主析取范式法推理的形式结构1. A1, A2, , Ak B 若推理正确, 记为A1,A2,An B4推理实例例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可知推理正确5推理实

3、例(2) 推理的形式结构:(pq)qp 用主析取范式法 (pq)qp (pq)qp (pq)q)p qp (pq)(pq) (pq)(pq) m0m2m3 结果不含m1, 故01是成假赋值，所以推理不正确6推理定律重言蕴涵式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)

4、破坏性二难每个等值式可产生两个推理定律如, 由AA可产生 AA 和 AA73.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)=公理推理系统 推出的结论是系统中的重言式, 称作定理8自然推理系统P定义3.3 自然推理系统 P 定义如下:1. 字母表 (1) 命题变项符号

5、：p, q, r, , pi, qi, ri, (2) 联结词符号：, , , , (3) 括号与逗号：(, ), ，2. 合式公式（同定义1.6）3. 推理规则 (1) 前提引入规则 (2) 结论引入规则 (3) 置换规则9推理规则(4) 假言推理规则 (6) 化简规则 (8) 假言三段论规则 AB AB AAB AB A(5) 附加规则 (7) 拒取式规则 (9) 析取三段论规则 AB BA AB BCACAB BA10推理规则(10) 构造性二难推理规则 (11) 破坏性二难推理规则 (12) 合取引入规则 AB CD AC BD AB CD BD AC A BAC11在自然推理系统P中

6、构造证明P中构造证明就是由一组P中公式作为前提，利用P中的规则，推出结论。构造形式结构A1A2Ak B 的推理的书写方法：前提： A1,A2,Ak 结论： B证明方法：直接证明法 附加前提法归谬法（或称反证法）12直接证明法实例例2 在自然推理系统P中构造下面推理的证明：前提：pq, rq ,rs 结论：ps pq 前提引入 pq 置换 rq 前提引入 qr 置换 pr 假言三段论 rs 前提引入 ps 假言三段论 13 q qr r r(pq)例3 在自然推理系统P中构造下面推理的证明:(1) 前提: pq,qr,ps,s 结论: r(pq)qrr(pq)spqpspqrpq证明: ps s

7、 p pq 合取假言推理拒取式析取三段式前提引入前提引入 拒取式前提引入析取三段式前提引入假言推理合取14(2) 前提: pq, rq, rs 结论: ps证明: pq pq rq qr pr rs pspr假言三段论pqrqrspsrspqqr置换置换假言三段论前提引入置换前提引入置换 假言三段论前提引入假言三段论15直接证明法实例例4 在自然推理系统P中构造下面推理的证明：前提：p（qr）, pq 结论： rs p（qr） 前提引入 pq 前提引入 p 化简 q 化简 qr 假言推理 r 假言推理 rs 附加 rs置换16证明: ps p s p(qr) 例5 在自然推理系统P中构造下面推

8、理的证明: 若数a 是实数, 则它不是有理数就是无理数。若a不能表示成分数, 则它不是有理数。a 是实数且它不能表示成分数, 所以a是无理数。解: 令 p: a是实数; q: a是有理数; r: a是无理数; s: a能表示成分数.前提: p(qr), s q, p s 结论: r qr s q q rp(qr)s qp srqpsqr析取三段论假言推理p化简假言推理前提引入化简 化简 前提引入假言推理前提引入假言推理析取三段论17直接证明法实例例6 构造下面推理的证明： 若明天是星期一或星期三，我明天就有课. 若我明天有 课，今天必备课. 我今天没备课. 所以，明天不是星期一、 也不是星期三

9、. 解 (1) 设命题并符号化 设 p：明天是星期一，q：明天是星期三， r：我明天有课，s：我今天备课 前提：(pq)r, rs, s 结论：pq18直接证明法实例(2) 写出证明的形式结构 前提：(pq)r, rs, s 结论：pq(3) 证明 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 拒取式 pq 置换19附加前提证明法附加前提证明法 适用于结论为蕴涵式欲证 前提：A1, A2, , Ak 结论：CB等价地证明 前提：A1, A2, , Ak, C 结论：B理由： (A1A2Ak)(CB) ( A1A2Ak)(CB) ( A1A2AkC)B (A1A2Ak

10、C)B20附加前提证明法实例例6 构造下面推理的证明 2是素数或合数. 若2是素数，则 是无理数. 若 是无理数，则4不是素数. 所以，如果4是素数，则2是合数. 解 用附加前提证明法构造证明 (1) 设 p：2是素数，q：2是合数， r： 是无理数，s：4是素数 (2) 推理的形式结构 前提：pq, pr, rs 结论：sq 21附加前提证明法实例 (3) 证明 s 附加前提引入 pr 前提引入 rs 前提引入 ps 假言三段论 p 拒取式 pq 前提引入 q 析取三段论22 例7 在自然推理系统P中构造下面推理的证明： 如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影

11、。小王去看电影。所以，当小赵去看电影时，小李必定也去。解：令 p: 小张去看电影；q: 小王去看电影； r: 小李去看电影； s: 小赵去看电影。 前提：(pq) r, sp, q结论：sr证明：用附加前提法。 s sp p q pq (pq)r rr(pq) rspqspqp假言推理合取析取三段论附加前提引入前提引入 析取三段论前提引入 合取前提引入 假言推理附加前提证明法23 前提：(pq) r, sp, q 结论：sr证明： sp s p (pq)r pqr q pr s r s r(pq) rspq析取三段论直接证明法s pp rpqr置换置换假言三段论前提引入 置换前提引入置换前提引

12、入 析取三段论 假言三段论24归谬法（反证法）归谬法 (反证法)欲证 前提：A1, A2, , Ak 结论：B做法 在前提中加入B，推出矛盾.理由 A1A2AkB (A1A2Ak)B (A1A2AkB) (A1A2AkB)0 A1A2AkB025归谬法实例例8 前提：(pq)r, rs, s, p 结论：q证明 用归缪法 q 结论否定引入 rs 前提引入 s 前提引入 r 拒取式 (pq)r 前提引入 (pq) 析取三段论 pq 置换 p 析取三段论 p 前提引入 pp 合取26 如果小张守第一垒并且小李向B队投球，则A 队将取胜。或者A队未取胜，或者A队成为联赛第一名。A队没有成为联赛第一名

13、。小张守第一垒。因此，小李没向 B队投球。例9在自然推理系统P 中构造下面推理的证明：解：令 p: 小张守第一垒； q: 小李向B队投球； r: A队取胜； s: A队成为联赛第一名。前提：(pq) r, rs, s, p结论：q(pq) rrsspqr(pq)pqq证明：(1)用归谬法（2）直接证明qq析取三段论拒取式析取三段论附加前提合取27证明：用归谬法 q 结论否定引入 (pq) 拒取式 rs 前提 pq 置换 s 前提 p 前提 r 析取三段论 q 析取三段论 (pq) r 前提 qq 合取因 qq 0 ，故原推理正确。直接证明 rs 前提 (pq) 拒取式 s 前提 pq 置换 r

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

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