《离散数学》课件第三章.ppt

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

2、A2 Ak为真时，为真时，B也为真，也为真，则称由则称由前提前提A1,A2,Ak推出推出结论结论B的的推理推理是是有效的有效的或或正确正确的的,并称并称B是是有效结论有效结论.定理定理3.1 由命题公式由命题公式A1,A2,Ak 推推B的推理正确当且仅当的推理正确当且仅当A1 A2 AkB为重言式为重言式注意注意:推理正确不能保证结论一定正确推理正确不能保证结论一定正确3推理的形式结构推理的形式结构2.A1 A2 AkB 若推理正确若推理正确,记为记为A1 A2 Ak B3.前提：前提：A1,A2,Ak 结论：结论：B判断推理是否正确的方法判断推理是否正确的方法:真值表法真值表法 等值演算法等

3、值演算法 主析取范式法主析取范式法推理的形式结构推理的形式结构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 (p q)p)q pq q 1

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

5、B)(BC)(AC)等价三段论等价三段论8.(AB)(CD)(A C)(B D)构造性二难构造性二难 (AB)(AB)B 构造性二难构造性二难(特殊形式特殊形式)9.(AB)(CD)(BD)(AC)破坏性二难破坏性二难每个等值式可产生两个推理定律每个等值式可产生两个推理定律如如,由由AA可产生可产生 AA 和和 AA73.2 自然推理系统自然推理系统P定义定义3.2 一个一个形式系统形式系统 I 由下面四个部分组成：由下面四个部分组成：(1)非空的字母表，记作非空的字母表，记作 A(I).(2)A(I)中符号构造的合式公式集，记作中符号构造的合式公式集，记作 E(I).(3)E(I)中一些特殊

6、的公式组成的公理集，记作中一些特殊的公式组成的公理集，记作 AX(I).(4)推理规则集，记作推理规则集，记作 R(I).记记I=,其中其中是是 I 的的形式语言系统形式语言系统,是是 I 的的形式演算系统形式演算系统.自然推理系统自然推理系统:无公理无公理,即即AX(I)=公理推理系统公理推理系统 推出的结论是系统中的重言式推出的结论是系统中的重言式,称作称作定理定理8自然推理系统自然推理系统P定义定义3.3 自然推理系统自然推理系统 P 定义定义如下如下:1.字母表字母表 (1)命题变项符号：命题变项符号：p,q,r,pi,qi,ri,(2)联结词符号：联结词符号：,(3)括号与逗号：括号

7、与逗号：(,),，2.合式公式（同定义合式公式（同定义1.6）3.推理规则推理规则 (1)前提引入规则前提引入规则 (2)结论引入规则结论引入规则 (3)置换规则置换规则9推理规则推理规则(4)假言推理规则假言推理规则(6)化简规则化简规则 (8)假言三段论规则假言三段论规则 AB AB AA B A B A(5)附加规则附加规则(7)拒取式规则拒取式规则 (9)析取三段论规则析取三段论规则 AB B A AB BCACA B BA10推理规则推理规则(10)构造性二难推理规则构造性二难推理规则 (11)破坏性二难推理规则破坏性二难推理规则 (12)合取引入规则合取引入规则 AB CD A C

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

9、我今天没备课.所以，明天不是星期一、所以，明天不是星期一、也不是星期三也不是星期三.解解 (1)设命题并符号化设命题并符号化 设设 p：明天是星期一，：明天是星期一，q：明天是星期三，：明天是星期三，r：我明天有课，：我明天有课，s：我今天备课：我今天备课12直接证明法直接证明法(2)写出证明的形式结构写出证明的形式结构 前提：前提：(p q)r,rs,s 结论：结论：pq(3)证明证明 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式 (p q)r 前提引入前提引入 (p q)拒取式拒取式 pq 置换置换13附加前提证明法附加前提证明法附加前提证明法附加前提证明法 适用于结论为

10、蕴涵式适用于结论为蕴涵式欲证欲证 前提：前提：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)B14附加前提证明法实例附加前提证明法实例例例3 构造下面推理的证明构造下面推理的证明 2是素数或合数是素数或合数.若若2是素数，则是素数，则 是无理数是无理数.若若 是无理是无理数，则数，则4不是素数不是素数.所以，如果所以，如果4是素数，则是素数，则2是合数是合数.解解 用附加前提证明法构造证明用附加前提证明法构造证明 (

11、1)设设 p：2是素数，是素数，q：2是合数，是合数，r：是无理数，是无理数，s：4是素数是素数 (2)推理的形式结构推理的形式结构 前提：前提：p q,pr,rs 结论：结论：sq 22215附加前提证明法实例附加前提证明法实例 (3)证明证明 s 附加前提引入附加前提引入 pr 前提引入前提引入 rs 前提引入前提引入 ps 假言三段论假言三段论 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段论析取三段论16归谬法（反证法）归谬法（反证法）归谬法归谬法(反证法反证法)欲证欲证 前提：前提：A1,A2,Ak 结论：结论：B做法做法 在前提中加入在前提中加入 B，推出矛盾，推出矛盾.

12、理由理由 A1 A2 AkB (A1 A2 Ak)B (A1 A2 AkB)(A1 A2 AkB)0 A1 A2 AkB017归谬法实例归谬法实例例例4 前提：前提：(p q)r,rs,s,p 结论：结论：q证明证明 用归缪法用归缪法 q 结论否定引入结论否定引入 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式 (p q)r 前提引入前提引入 (p q)析取三段论析取三段论 pq 置换置换 p 析取三段论析取三段论 p 前提引入前提引入 p p 合取合取18第三章第三章 习题课习题课主要内容主要内容l 推理的形式结构推理的形式结构l 判断推理是否正确的方法判断推理是否正确的方法

13、 真值表法真值表法 等值演算法等值演算法 主析取范式法主析取范式法l 推理定律推理定律l 自然推理系统自然推理系统Pl 构造推理证明的方法构造推理证明的方法 直接证明法直接证明法 附加前提证明法附加前提证明法 归谬法归谬法(反证法反证法)19基本要求基本要求l 理解并记住推理形式结构的两种形式：理解并记住推理形式结构的两种形式：1.(A1 A2 Ak)B 2.前提：前提：A1,A2,Ak 结论：结论：Bl 熟练掌握判断推理是否正确的不同方法（如真值表法、等熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）值演算法、主析取范式法等）l 牢记牢记 P 系统中各条推理规则系

14、统中各条推理规则l 熟练掌握构造证明的直接证明法、附加前提证明法和归谬熟练掌握构造证明的直接证明法、附加前提证明法和归谬 法法l 会解决实际中的简单推理问题会解决实际中的简单推理问题20练习练习1：判断推理是否正确：判断推理是否正确1.判断下面推理是否正确判断下面推理是否正确:(1)前提：前提：pq,q 结论：结论：p 解解 推理的形式结构推理的形式结构:(pq)qp 方法一：等值演算法方法一：等值演算法 (pq)qp (p q)q)p (pq)qp (p q)(q q)p p q易知易知10是成假赋值，不是重言式，所以推理不正确是成假赋值，不是重言式，所以推理不正确.21练习练习1解答解答方

15、法二：主析取范式法，方法二：主析取范式法，(pq)qp (p q)q)p p q M2 m0 m1 m3未含未含m2,不是重言式不是重言式,推理不正确推理不正确.22练习练习1解答解答方法三方法三 真值表法真值表法 不是重言式不是重言式,推理不正确推理不正确111001110100(pq)qpqp pq 0 1 1 1(pq)q 0 0 1 0方法四方法四 直接观察出直接观察出10是成假赋值是成假赋值23练习练习1解答解答用等值演算法用等值演算法 (qr)(pr)(qp)(q r)(pr)(qp)(qr)(p r)(qp)(q p)(q r)(r p)(qp)(q p)(q r)(r p)(q

16、p)1推理正确推理正确(2)前提：前提：qr,pr 结论：结论：qp 解解 推理的形式结构：推理的形式结构：(qr)(pr)(qp)24练习练习2：构造证明：构造证明2.在系统在系统P中构造下面推理的证明：中构造下面推理的证明：如果今天是周六，我们就到颐和园或圆明园玩如果今天是周六，我们就到颐和园或圆明园玩.如果颐和如果颐和 园游人太多，就不去颐和园园游人太多，就不去颐和园.今天是周六，并且颐和园游今天是周六，并且颐和园游 人太多人太多.所以所以,我们去圆明园或动物园玩我们去圆明园或动物园玩.证明证明：(1)设设 p：今天是周六，：今天是周六，q：到颐和园玩，：到颐和园玩，r：到圆明园玩，：到圆明园玩，s：颐和园游人太多：颐和园游人太多 t：到动物园玩：到动物园玩 (2)前提：前提：p(q r),sq,p,s 结论：结论：r t25练习练习2解答解答(3)证明：证明：p(q r)前提引入前提引入 p 前提引入前提引入 q r 假言推理假言推理 sq 前提引入前提引入 s 前提引入前提引入 q 假言推理假言推理 r 析取三段论析取三段论 r t 附加附加