离散数学屈婉玲第三章.ppt

主要内容主要内容推理的形式结构推理的形式结构l推理的正确与错误推理的正确与错误l推理的形式结构推理的形式结构l判断推理正确的方法判断推理正确的方法l推理定律推理定律自然推理系统自然推理系统Pl形式系统的定义与分类形式系统的定义与分类l自然推理系统自然推理系统Pl在在P中构造证明中构造证明:直接证明法、附加前提证明法、归谬法直接证明法、附加前提证明法、归谬法第三章第三章 命题逻辑的推理理论命题逻辑的推理理论13.1 推理的形式结构推理的形式结构定义定义3.1 设设A1, A2, …, Ak, B为命题公式为命题公式. 若对于每一组赋值，若对于每一组赋值，A1 A2 …  Ak 为假，或当为假，或当A1 A2 … Ak为真时，为真时，B也为真，也为真，则称由则称由前提前提A1, A2, …, Ak推出推出结论结论B的的推理推理是是有效的有效的或或正确正确的的, 并称并称B是是有效结论有效结论.定理定理3.1 由命题公式由命题公式A1, A2, …, Ak 推出推出B的推理正确当且仅当的推理正确当且仅当A1 A2 … AkB为重言式为重言式注意注意: 推理正确不能保证结论一定正确推理正确不能保证结论一定正确2推理的形式结构推理的形式结构2. A1 A2 … AkB 若推理正确若推理正确, 记为记为A1   A2   …   Ak  B3. 前提：前提： 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) 推理的形式结构推理的形式结构: (pq) pq用等值演算法用等值演算法 (pq) pq   (( p q) p) q   pq q  1推理正确推理正确4推理实例推理实例(2) 推理的形式结构推理的形式结构:(pq) qp 用主析取范式法用主析取范式法 (pq) qp  ( p q) qp    (( p q) q) p   q p  ( pq) (pq)  (pq) (p q)  m0 m2 m3 推理不正确推理不正确5推理定律推理定律————重言蕴涵式重言蕴涵式1. A  (A B) 附加律附加律 2. (A B)  A 化简律化简律3. (AB) A  B 假言推理假言推理4. (AB)B   A 拒取式拒取式 5. (A B)B  A 析取三段论析取三段论6. (AB) (BC)  (AC) 假言三段论假言三段论7. (AB) (BC)  (AC) 等价三段论等价三段论8. (AB) (CD) (A C)  (B D) 构造性二难构造性二难 (AB) ( AB)  B 构造性二难构造性二难(特殊形式特殊形式)9. (AB) (CD) (  BD)  ( AC) 破坏性二难破坏性二难每个等值式可产生两个推理定律每个等值式可产生两个推理定律如如, 由由AA可产生可产生 AA 和和 AA6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)=公理推理系统公理推理系统 有公理集有公理集, 推出的结论是系统中的重言式推出的结论是系统中的重言式, 称称 作作定理定理7自然推理系统自然推理系统P定义定义3.3 自然推理系统自然推理系统 P 定义定义如下如下:1. 字母表字母表 (1) 命题变项符号：命题变项符号：p, q, r, …, pi, qi, ri, … (2) 联结词符号：联结词符号： ,  ,  , ,  (3) 括号与逗号：括号与逗号：(, ), ，，2. 合式公式（同定义合式公式（同定义1.6））3. 推理规则推理规则 (1) 前提引入规则前提引入规则 (2) 结论引入规则结论引入规则 (3) 置换规则置换规则8推理规则推理规则(4) 假言推理规则假言推理规则 (6) 化简规则化简规则 (8) 假言三段论规则假言三段论规则 AB A∴∴B A∴∴A B A B∴∴ A(5) 附加规则附加规则 (7) 拒取式规则拒取式规则 (9) 析取三段论规则析取三段论规则 AB  B∴∴ A AB BC∴∴ACA B  B∴∴A9推理规则推理规则(10) 构造性二难推理规则构造性二难推理规则 (11) 破坏性二难推理规则破坏性二难推理规则 (12) 合取引入规则合取引入规则 AB CD A C ∴∴B D AB CD  BD ∴∴ A  C A B∴∴A C10在自然推理系统在自然推理系统P中构造证明中构造证明设前提设前提A1, A2,, Ak,结论结论B及公式序列及公式序列C1, C2,, Cl. 如果每如果每一个一个Ci(1 i l)是某个是某个Aj, 或者可由序列中前面的公式应用推或者可由序列中前面的公式应用推理理规则得到规则得到, 并且并且Cl =B, 则称这个公式序列是由则称这个公式序列是由A1, A2,, Ak推推出出B的的证明证明例例2 构造下面推理的证明：构造下面推理的证明： 若明天是星期一或星期三若明天是星期一或星期三, 我明天就有课我明天就有课. 若我明天有课若我明天有课, 今天必备课今天必备课. 我今天没备课我今天没备课. 所以所以, 明天不是星期一明天不是星期一, 也不也不 是星期三是星期三. 解解 (1) 设命题并符号化设命题并符号化 设设 p：明天是星期一，：明天是星期一，q：明天是星期三，：明天是星期三， r：我明天有课，：我明天有课，s：我今天备课：我今天备课11直接证明法直接证明法(2) 写出证明的形式结构写出证明的形式结构 前提：前提：(p q)r, rs,  s 结论：结论： pq(3) 证明证明 ①① rs 前提引入前提引入 ②②  s 前提引入前提引入 ③③  r ①②①②拒取式拒取式 ④④ (p q)r 前提引入前提引入 ⑤⑤  (p q) ③④③④拒取式拒取式 ⑥⑥  pq ⑤⑤置换置换12附加前提证明法附加前提证明法附加前提证明法附加前提证明法 适用于结论为蕴涵式适用于结论为蕴涵式欲证欲证 前提：前提：A1, A2, …, Ak 结论：结论：CB等价地证明等价地证明 前提：前提：A1, A2, …, Ak, C 结论：结论：B理由：理由： (A1 A2 … Ak)(CB)   ( A1 A2 … Ak) ( C B)   ( A1 A2 … Ak C) B  (A1 A2 … Ak C)B13附加前提证明法实例附加前提证明法实例例例3 构造下面推理的证明构造下面推理的证明 2是素数或合数是素数或合数. 若若2是素数是素数, 则则   是无理数是无理数. 若若  是无理数是无理数, 则则4不是素数不是素数. 所以所以, 如果如果4是素数是素数, 则则2是合数是合数. 解解 用附加前提证明法构造证明用附加前提证明法构造证明 (1) 设设 p：：2是素数，是素数，q：：2是合数，是合数， r：：  是无理数，是无理数，s：：4是素数是素数 (2) 推理的形式结构推理的形式结构 前提：前提：p q, pr, rs 结论：结论：sq 14附加前提证明法实例附加前提证明法实例 (3) 证明证明 ①① s 附加前提引入附加前提引入 ②② pr 前提引入前提引入 ③③ rs 前提引入前提引入 ④④ ps ②③②③假言三段论假言三段论 ⑤⑤  p ①④①④拒取式拒取式 ⑥⑥ p q 前提引入前提引入 ⑦⑦ q ⑤⑥⑤⑥析取三段论析取三段论15归谬法（反证法）归谬法（反证法）归谬法归谬法 (反证法反证法)欲证欲证 前提：前提：A1, A2, … , Ak 结论：结论：B做法做法 在前提中加入在前提中加入 B，推出矛盾，推出矛盾.理由理由 A1 A2 … AkB   (A1 A2 … Ak) B   (A1 A2 … AkB)   (A1 A2 … AkB) 0  A1 A2 … AkB016归谬法实例归谬法实例例例4 前提：前提： (p q) r, rs,  s, p 结论：结论： q证明证明 用归缪法用归缪法 ①① q 结论否定引入结论否定引入 ②② rs 前提引入前提引入 ③③  s 前提引入前提引入 ④④  r ②③②③拒取式拒取式 ⑤⑤  (p q) r 前提引入前提引入 ⑥⑥  (p q) ④⑤④⑤析取三段论析取三段论 ⑦⑦  pq ⑥⑥置换置换 ⑧⑧  p ①⑦①⑦析取三段论析取三段论 ⑨⑨ p 前提引入前提引入  p p ⑧⑨⑧⑨合取合取17第三章第三章 习题课习题课主要内容主要内容l推理的形式结构推理的形式结构l判断推理是否正确的方法判断推理是否正确的方法 真值表法真值表法 等值演算法等值演算法 主析取范式法主析取范式法l推理定律推理定律l自然推理系统自然推理系统Pl构造推理证明的方法构造推理证明的方法 直接证明法直接证明法 附加前提证明法附加前提证明法 归谬法归谬法(反证法反证法)18基本要求基本要求l理解并记住推理形式结构的两种形式：理解并记住推理形式结构的两种形式： 1. (A1 A2 … Ak)B 2. 前提：前提：A1, A2, … , Ak 结论：结论：Bl熟练掌握判断推理是否正确的不同方法（如真值表法、等熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）值演算法、主析取范式法等）l牢记牢记 P 系统中各条推理规则系统中各条推理规则l熟练掌握构造证明的直接证明法、附加前提证明法和归谬熟练掌握构造证明的直接证明法、附加前提证明法和归谬 法法l会解决实际中的简单推理问题会解决实际中的简单推理问题19练习练习1：判断推理是否正确：判断推理是否正确1. 判断下面推理是否正确判断下面推理是否正确: (1) 前提：前提： pq,  q 结论：结论： p 解解 推理的形式结构推理的形式结构: ( pq)qp 方法一：等值演算法方法一：等值演算法 ( pq)qp   ((p q)q)p  ( pq) qp  (( p q) ( q q))p   p q不是重言式，所以推理不正确不是重言式，所以推理不正确.20练习练习1解答解答方法二：主析取范式法，方法二：主析取范式法， ( pq)qp ((p q)q)p p q M2 m0 m1 m3未含未含m2, 不是重言式不是重言式, 推理不正确推理不正确.21练习练习1解答解答方法三方法三 真真值值表法表法 不是重言式不是重言式, 推理不正确推理不正确111001110100( pq)qpqp pq 0 1 1 1( pq)q 0 0 1 0方法四方法四 直接直接观观察出察出10是成假是成假赋值赋值22练习练习1解答解答用等值演算法用等值演算法 (qr) (pr)(qp) ( q r) ( pr)( qp) ((qr) (p r))( qp) ((q p) (q r) ( r p))( qp) ((q p) (q r) ( r p)) ( qp)1推理正确推理正确(2) 前提：前提：qr, pr 结论：结论：qp 解解 推理的形式结构：推理的形式结构： (qr) (pr)(qp) 23练习练习2：构造证明：构造证明2. 在系统在系统P中构造下面推理的证明：中构造下面推理的证明： 如果今天是周六，我们就到颐和园或圆明园玩如果今天是周六，我们就到颐和园或圆明园玩. 如果颐和如果颐和 园游人太多，就不去颐和园园游人太多，就不去颐和园. 今天是周六，并且颐和园游今天是周六，并且颐和园游 人太多人太多. 所以所以, 我们去圆明园或动物园玩我们去圆明园或动物园玩. 证明证明：： (1) 设设 p：今天是周六，：今天是周六，q：到颐和园玩，：到颐和园玩， r：到圆明园玩，：到圆明园玩，s：颐和园游人太多：颐和园游人太多, t：到动物园玩：到动物园玩. (2) 前提：前提：p(q r), sq, p, s 结论：结论：r t24练习练习2解答解答(3) 证明：证明： ①① p(q r) 前提引入前提引入 ②② p 前提引入前提引入 ③③ q r ①②①②假言推理假言推理 ④④ sq 前提引入前提引入 ⑤⑤ s 前提引入前提引入 ⑥⑥  q ④⑤④⑤假言推理假言推理 ⑦⑦ r ③⑥③⑥析取三段论析取三段论 ⑧⑧ r t ⑦⑦附加附加25。