离散数学(高教版)第3章

1、1主要内容主要内容推理的形式结构推理的形式结构l 推理的正确与错误推理的正确与错误l 推理的形式结构推理的形式结构l 判断推理正确的方法判断推理正确的方法l 推理定律推理定律自然推理系统自然推理系统Pl 形式系统的定义与分类形式系统的定义与分类l 自然推理系统自然推理系统Pl 在在P中构造证明中构造证明:直接证明法、附加前提证明法、归谬法直接证明法、附加前提证明法、归谬法第三章第三章 命题逻辑的推理理论命题逻辑的推理理论23.1 推理的形式结构推理的形式结构定义定义3.1 设设A1, A2, , Ak, B为命题公式为命题公式. 若对于每组赋值，若对于每组赋值，A1 A2 Ak 为假，或当为假

2、，或当A1 A2 Ak为真时，为真时，B也为真，也为真，则称由则称由前提前提A1, A2, , Ak推出推出结论结论B的的推理推理是是有效的有效的或或正确正确的的, 并称并称B是是有效结论有效结论.说明：1. 由前提A1, A2, , Ak推出结论B的推理是否正确与诸前提的排列次序无关，前提是一个有限集的公式集合。前提A1, A2, , Ak推出结论B记为A1, A2, , Ak B 推理的形式结构推理的形式结构1. A1, A2, , Ak B 若推理正确若推理正确, 记为记为A1,A2,An B2. 设设A1, A2, , Ak, B中共出现中共出现n个命题变项，对于任一组赋个命题变项，对

3、于任一组赋值值a1, a2, , ak（ai =0或者或者1），），前提和结论的取值前提和结论的取值 情况共有情况共有以下以下 4种种 ： （1） A1 A2 Ak 为为0，B为为 0 （2）A1 A2 Ak 为为0，B为为 1 （3）A1 A2 Ak 为为1，B为为 0 （4）A1 A2 Ak 为为1，B为为 1由定义可知，只要由定义可知，只要 不出现第不出现第 3种情况，推理就是正确的，因种情况，推理就是正确的，因而判断推理是否正确，就是判断是否而判断推理是否正确，就是判断是否 会出现情况（会出现情况（3）。）。3.推理正确并不能保证结论一定成立；前提不正确，不论结推理正确并不能保证结论一

4、定成立；前提不正确，不论结论是否成立，都说推理正确。论是否成立，都说推理正确。34例3.1 判断下列推理是否正确。 （1） p,pq) q （2） p, qp) q判断方法：真值表法。判断依据：看是否出现前提合取式为真，而结论为假的情况。解:(1) 构造真值表：4p qp (p q)q0 00 11 01 11101 0101由真值表可知，推理正确5（2） p, qp) q解:(1) 构造真值表：5 5p qp (qp)q0 00 11 01 10011 0101由真值表可知，推理不正确63.1 推理的形式结构推理的形式结构定理定理3.1 由命题公式由命题公式A1, A2, , Ak 推推B的

5、推理正确当且仅当的推理正确当且仅当A1 A2 AkB为重言式为重言式注意注意: 推理正确不能保证结论一定正确推理正确不能保证结论一定正确定理说明： . A1, A2, , Ak B 等同于蕴含式等同于蕴含式A1 A2 AkB A1, A2, , Ak B 等同于等同于 A1 A2 Ak B 7推理的形式结构推理的形式结构2. A1 A2 AkB 若推理正确若推理正确, 记为记为A1 A2 Ak B3. 前提：前提： A1, A2, , Ak 结论：结论： B判断推理是否正确的方法判断推理是否正确的方法: 真值表法真值表法 等值演算法等值演算法 主析取范式法主析取范式法推理的形式结构推理的形式结

6、构1. A1, A2, , Ak B 若推理正确若推理正确, 记为记为A1,A2,An B例例2 判断下列推理是否正确判断下列推理是否正确 若若a能被能被4整除，则整除，则a能被能被2整除。整除。a能被能被4整除。所以整除。所以a能被能被2整除整除. 若若a能被能被4整除，则整除，则a能被能被2整除。整除。a能被能被2整除。所以整除。所以a能被能被4整除整除. 下午马芳或去看电影或去游泳。她没去看电影。所以，下午马芳或去看电影或去游泳。她没去看电影。所以，她去游泳了。她去游泳了。 若下午气温超过若下午气温超过30度，则王小燕必去游泳，她就不去看度，则王小燕必去游泳，她就不去看电影了。所以，若王

7、小燕没去看电影，下午气温必超过电影了。所以，若王小燕没去看电影，下午气温必超过30度。度。8推理实例推理实例解题方法：第一步：将简单命题符号化解题方法：第一步：将简单命题符号化 第二步：写出前提、结论、推理的形式结构第二步：写出前提、结论、推理的形式结构 第三步：进行判断。第三步：进行判断。解：设解：设 前提：前提：p q, p 结论：结论：q 推理的形式结构推理的形式结构: (p q) p q. 构造真值表：构造真值表：9 若若a能被能被4整除，则整除，则a能被能被2整除。整除。a能被能被4整除。所以整除。所以a能能被被2整除整除.p qpq (p q) p (p q) p q1101 p:

8、a能被能被4整除整除q:a能被能被2整除整除0 00 11 01 11101 111110 2) 若a能被4整除，则a能被2整除。a能被2整除。所以a能被4整除.解：设解：设 前提：前提：p q, p 结论：结论：q 推理的形式结构推理的形式结构: (p q) p q. 用等值演算判断用等值演算判断形式结构是否是重言式。形式结构是否是重言式。 p:a能被能被4整除整除q:a能被能被2整除整除（3）下午马芳或去看电影或去游泳。她没去看电影。所以）下午马芳或去看电影或去游泳。她没去看电影。所以，她去游泳了。，她去游泳了。 解：设解：设 前提：前提： 结论：结论： 推理的形式推理的形式 结构：结构：

9、( ) . 用等值演算来判断式子是否用等值演算来判断式子是否 为为 等值式。等值式。 ( (p q) p ) q ( ( ) ( ) q( ) q(q p ) q p q q1所以所以 形式形式 结构结构 为为 重言式，推理重言式，推理 正确。正确。11p:马芳下午去看电影马芳下午去看电影 . q:马芳下午去游泳马芳下午去游泳.p q, pq(p q) pqp p qpq p 解：设：解：设： p:下午气温超过下午气温超过30度度12（4）若下午气温超过30度，则王小燕必去游泳，她就不去看电影了。所以，若王小燕没去看电影，下午气温必超过30度。q:王小燕去游泳r:王小燕去看电影前提： ,qr结

10、论pqrp推理的形式结构(p q) p(pq)(q r) (rp)用主析取范式判断上式是否是重言式(pq)(q r) (rp)(p q)(q r) (rp)13推理实例推理实例练习练习 ：判断下面推理是否正确：判断下面推理是否正确(1) 若今天是若今天是1号，则明天是号，则明天是5号号. 今天是今天是1号号. 所以所以, 明天是明天是5号号. (2) 若今天是若今天是1号，则明天是号，则明天是5号号. 明天是明天是5号号. 所以所以, 今天是今天是1号号. 解解 设设 p：今天是：今天是1号，号，q：明天是：明天是5号号. (1) 推理的形式结构推理的形式结构: (pq) pq用等值演算法用等

11、值演算法 (pq) pq ( p q) p) q pq q 1 由定理由定理3.1可知推理正确可知推理正确14推理实例推理实例(2) 推理的形式结构推理的形式结构:(pq) qp 用主析取范式法用主析取范式法 (pq) qp ( p q) qp ( p q) q) p q p ( pq) (pq) (pq) (p q) m0 m2 m3 结果不含结果不含m1, 故故01是成假赋值，所以推理不正确是成假赋值，所以推理不正确15推理定律推理定律重言蕴涵式重言蕴涵式1. A (A B) 附加律附加律 2. (A B) A 化简律化简律3. (AB) A B 假言推理假言推理4. (AB)B A 拒取

12、式拒取式 5. (A B)B A 析取三段论析取三段论6. (AB) (BC) (AC) 假言三段论假言三段论7. (AB) (BC) (AC) 等价三段论等价三段论8. (AB) (CD) (A C) (B D) 构造性二难构造性二难 (AB) ( AB) B 构造性二难构造性二难(特殊形式特殊形式)9. (AB) (CD) ( BD) ( AC) 破坏性二难破坏性二难每个等值式可产生两个推理定律每个等值式可产生两个推理定律如如, 由由AA可产生可产生 AA 和和 AA163.2 自然推理系统自然推理系统P定义定义3.2 一个一个形式系统形式系统 I 由下面四个部分组成：由下面四个部分组成：

13、 (1) 非空的字母表，记作非空的字母表，记作 A(I). (2) A(I) 中符号构造的合式公式集，记作中符号构造的合式公式集，记作 E(I). (3) E(I) 中一些特殊的公式组成的公理集，记作中一些特殊的公式组成的公理集，记作 AX(I). (4) 推理规则集，记作推理规则集，记作 R(I). 记记I=, 其中其中是是 I 的的形式语言系统形式语言系统, 是是 I 的的形式演算系统形式演算系统.自然推理系统自然推理系统: 无公理无公理, 即即AX(I)=公理推理系统公理推理系统 推出的结论是系统中的重言式推出的结论是系统中的重言式, 称作称作定理定理17自然推理系统自然推理系统P定义定

14、义3.3 自然推理系统自然推理系统 P 定义定义如下如下:1. 字母表字母表 (1) 命题变项符号：命题变项符号：p, q, r, , pi, qi, ri, (2) 联结词符号：联结词符号： , , , , (3) 括号与逗号：括号与逗号：(, ), ，2. 合式公式（同定义合式公式（同定义1.6）3. 推理规则推理规则 (1) 前提引入规则前提引入规则 ：在证明的任何步骤都可以引入前提。：在证明的任何步骤都可以引入前提。 (2) 结论引入规则：在证明的任何步骤得到的结论都可以作结论引入规则：在证明的任何步骤得到的结论都可以作为后继证明的前提。为后继证明的前提。 (3) 置换规则：在证明的任

15、何步骤，命题公式中的子公式都置换规则：在证明的任何步骤，命题公式中的子公式都可以用等值的公式置换，得到公式序列中的又一个公式。可以用等值的公式置换，得到公式序列中的又一个公式。推理规则推理规则(4) 假言推理规则假言推理规则 (6) 化简规则化简规则 (8) 假言三段论规则假言三段论规则 AB AB AA B A B A(5) 附加规则附加规则 (7) 拒取式规则拒取式规则 (9) 析取三段论规则析取三段论规则 AB B A AB BCACA B BA19推理规则推理规则(10) 构造性二难推理规则构造性二难推理规则 (11) 破坏性二难推理规则破坏性二难推理规则 (12) 合取引入规则合取引

16、入规则 AB CD A C B D AB CD BD A C A BA B20在自然推理系统在自然推理系统P中构造证明中构造证明设前提设前提A1, A2, Ak,结论结论B及公式序列及公式序列C1, C2, Cl. 如果每如果每一个一个Ci(1 i l)是某个是某个Aj, 或者可由序列中前面的公式应用推理或者可由序列中前面的公式应用推理规则得到规则得到, 并且并且Cl =B, 则称这个公式序列是由则称这个公式序列是由A1, A2, Ak推推出出B的的证明证明例例 构造下面推理的证明：构造下面推理的证明： 若明天是星期一或星期三，我明天就有课若明天是星期一或星期三，我明天就有课. 若我明天有若我

17、明天有 课，今天必备课课，今天必备课. 我今天没备课我今天没备课. 所以，明天不是星期一、所以，明天不是星期一、 也不是星期三也不是星期三. 21直接证明法直接证明法例例 构造下面推理的证明：构造下面推理的证明： 若明天是星期一或星期三，我明天就有课若明天是星期一或星期三，我明天就有课. 若我明天有若我明天有 课，今天必备课课，今天必备课. 我今天没备课我今天没备课. 所以，明天不是星期一、所以，明天不是星期一、 也不是星期三也不是星期三. 解解 (1) 设命题并符号化设命题并符号化 设设 ， ，(2) 写出证明的形式结构写出证明的形式结构 前提：前提： 结论：结论：(3) 证明证明 置换置换

18、p：明天是星期一：明天是星期一q：明天是星期三，：明天是星期三，r：我明天有课：我明天有课s：我今天备课：我今天备课(p q)r, rs, s pqrs前提引入前提引入 s 前提引入前提引入 r拒取式拒取式(p q)r前提引入前提引入 (p q) 拒取式拒取式 pq例例3.3 在自然推理系统在自然推理系统P中构造下面的推理证明中构造下面的推理证明 前提：前提： 结论：结论：解：证明解：证明 22p q，qr, ps, sr (p q) ps前提引入前提引入 s 前提引入前提引入 p拒取式拒取式p q前提引入前提引入q 析取三段论析取三段论 rqr前提引入前提引入假言推理假言推理r (p q)

19、合取引入23附加前提证明法附加前提证明法附加前提证明法附加前提证明法 适用于结论为蕴涵式适用于结论为蕴涵式欲证欲证 前提：前提：A1, A2, , Ak 结论：结论：CB等价地证明等价地证明 前提：前提：A1, A2, , Ak, C 结论：结论：B理由：理由： (A1 A2 Ak)(CB) ( A1 A2 Ak) ( C B) ( A1 A2 Ak C) B (A1 A2 Ak C)B24附加前提证明法实例附加前提证明法实例例例3 构造下面推理的证明构造下面推理的证明 2是素数或合数是素数或合数. 若若2是素数，则是素数，则 是无理数是无理数. 若若 是无理数，则是无理数，则4不是素数不是素

20、数. 所所以，如果以，如果4是素数，则是素数，则2是合数是合数. 解解 用附加前提证明法构造证明用附加前提证明法构造证明 (1) 设设 ， ， ， (2) 推理的形式结构推理的形式结构 前提：前提： , , 结论：结论：22 (3) 证明证明 p： 2是素数是素数q：2是合数是合数2r ： 是无理数是无理数s：4是素数是素数p qprrssq s 附加前提引入pr前提引入rs 前提引入ps 假言三段论p拒取式 pq 前提引入q析取三段论25归谬法（反证法）归谬法（反证法）归谬法归谬法 (反证法反证法)：将结论的否定式作为附加前提引入并推出：将结论的否定式作为附加前提引入并推出矛盾式的证明方法称

21、做归谬法。矛盾式的证明方法称做归谬法。欲证欲证 前提：前提：A1, A2, , Ak 结论：结论：B做法做法 在前提中加入在前提中加入 B，推出矛盾，推出矛盾.理由理由 A1 A2 AkB (A1 A2 Ak) B (A1 A2 AkB) (A1 A2 AkB)26归谬法实例归谬法实例例例4 前提：前提： (p q) r, rs, s, p 结论：结论： q证明证明 用归缪法用归缪法 q 结论否定引入结论否定引入rs 前提引入前提引入 s前提引入前提引入 r拒取式拒取式 (p q) r前提引入前提引入 (p q)析取三段论析取三段论 pq 置换置换 p 析取三段论析取三段论p前提引入前提引入

22、p p 合取合取27第三章第三章 习题课习题课主要内容主要内容l 推理的形式结构推理的形式结构l 判断推理是否正确的方法判断推理是否正确的方法 真值表法真值表法 等值演算法等值演算法 主析取范式法主析取范式法l 推理定律推理定律l 自然推理系统自然推理系统Pl 构造推理证明的方法构造推理证明的方法 直接证明法直接证明法 附加前提证明法附加前提证明法 归谬法归谬法(反证法反证法)28基本要求基本要求l 理解并记住推理形式结构的两种形式：理解并记住推理形式结构的两种形式： 1. (A1 A2 Ak)B 2. 前提：前提：A1, A2, , Ak 结论：结论：Bl 熟练掌握判断推理是否正确的不同方法

23、（如真值表法、等熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）值演算法、主析取范式法等）l 牢记牢记 P 系统中各条推理规则系统中各条推理规则l 熟练掌握构造证明的直接证明法、附加前提证明法和归谬熟练掌握构造证明的直接证明法、附加前提证明法和归谬 法法l 会解决实际中的简单推理问题会解决实际中的简单推理问题29练习练习1：判断推理是否正确：判断推理是否正确1. 判断下面推理是否正确判断下面推理是否正确: (1) 前提：前提： pq, q 结论：结论： p 解解 推理的形式结构推理的形式结构: ( pq)qp 方法一：等值演算法方法一：等值演算法 ( pq)qp (p q)q)p ( pq) qp ( p q) ( q q)p p q易知易知10是成假赋值，不是重言式，所以推理不正确是成假赋值，不是重言式，所以推理不正确.30练习练习1解答解答方法二：主析取范式法，方法二：主析取范式法， ( pq)qp (p q)q)p p q M2 m0 m