1、屈婉玲离散数学第三章(与“推理”有关的文档共25张)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 AkB为重言式为重言式注意注意:推理正确不能保证结论一定正确推理正确不能保证结论一定正确所
2、谓推理是指从前提出发推出结论的思维过程。所谓推理是指从前提出发推出结论的思维过程。第二页，共25页。用主析取范式法(pq)(pq)(pq)(pq)前提：A1,A2,Ak,C在自然推理系统P中构造证明(1)若今天是1号，则明天是5号.前提：A1,A2,Ak(pq)r 前提引入 p 拒取式r：到圆明园玩，s：颐和园游人太多 p 析取三段论前提：A1,A2,Ak若2是素数，则 是无理数.A1A2 Ak 为假，或当A1A2Ak为真时，B也为真，若 是无理数，则4不是素数.推理的形式结构推理的形式结构2.A1 A2 AkB 若推理正确若推理正确,记为记为A1 A2 Ak B3.前提：前提：A1,A2,A
3、k 结论：结论：B判断推理是否正确的方法判断推理是否正确的方法:真值表法（见例子真值表法（见例子3.1）等值演算法（见例子等值演算法（见例子3.2）主析取范式法（见例子主析取范式法（见例子3.2）由由A1,A2,Ak推推B的的推理有以下的形式结构：推理有以下的形式结构：1.A1,A2,Ak B 若推理正确若推理正确,记为记为A1,A2,An B第三页，共25页。推理实例推理实例例例1 判断下面推理是否正确判断下面推理是否正确(1)若今天是若今天是1号，则明天是号，则明天是5号号.今天是今天是1号号.所以所以,明天是明天是5号号.(2)若今天是若今天是1号，则明天是号，则明天是5号号.明天是明天
4、是5号号.所以所以,今天是今天是1号号.解解 设设 p：今天是：今天是1号，号，q：明天是：明天是5号号.(1)推理的形式结构推理的形式结构:(pq)pq用等值演算法用等值演算法 (pq)pq (p q)p)q pq q 1 由定理由定理3.1可知推理正确可知推理正确第四页，共25页。推理实例推理实例(2)推理的形式结构推理的形式结构:(pq)qp 用主析取范式法用主析取范式法 (pq)qp (p q)qp (p q)q)p q p (pq)(pq)(pq)(p q)m0 m2 m3 结果不含结果不含m1,故故01是成假赋值，所以推理不正确是成假赋值，所以推理不正确第五页，共25页。推理定律推
5、理定律重言蕴涵式重言蕴涵式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.(AB)(BC)(AC)等价三段论等价三段论8.(AB)(CD)(A C)(B D)构造性二难构造性二难 (AB)(AB)B 构造性二难构造性二难(特殊形式特殊形式)9.(AB)(CD)(BD)(AC)破坏性二难破坏性二难每个等值式可产生两个推理定律每个等值式可产生两个推理定律如如,由由AA可产生可产生 AA 和和 AA第六页，共25页。3.2
6、自然推理系统自然推理系统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、推出的结论是系统中的重言式,称作称作定理定理本节对本节对由由A1,A2,Ak推推B的正确的正确推理的证明给出严格的形式描推理的证明给出严格的形式描述述第七页，共25页。自然推理系统自然推理系统P定义定义3.3 自然推理系统自然推理系统 P 定义定义如下如下:1.字母表字母表 (1)命题变项符号：命题变项符号：p,q,r,pi,qi,ri,(2)联结词符号：联结词符号：,(3)括号与逗号：括号与逗号：(,),，2.合式公式（同定义合式公式（同定义1.6）3.推理规则推理规则 (1)前提引入规则：前提引入规则：在证明的任何步骤都可引入前提在证明的任何步骤都可引入前提 (2)结论引入规则：结论引入规
8、则：在证明的任何步骤得到的结论都可以做在证明的任何步骤得到的结论都可以做 为后续证明的前提为后续证明的前提 (3)置换规则：置换规则：在证明的任何步骤，命题公式中的子公式都在证明的任何步骤，命题公式中的子公式都 可用等值的公式置换，得到公式序列中又可用等值的公式置换，得到公式序列中又 一个公式一个公式第八页，共25页。推理规则推理规则(4)假言推理规则假言推理规则(6)化简规则化简规则 (8)假言三段论规则假言三段论规则 AB AB AA B A B A(5)附加规则附加规则(7)拒取式规则拒取式规则 (9)析取三段论规则析取三段论规则 AB B A AB BCACA B BA第九页，共25页
9、。推理规则推理规则(10)构造性二难推理规则构造性二难推理规则 (11)破坏性二难推理规则破坏性二难推理规则 (12)合取引入规则合取引入规则 AB CD A C B D AB CD BD A C A BA C第十页，共25页。在自然推理系统在自然推理系统P中构造证明中构造证明设前提设前提A1,A2,Ak,结论结论B及公式序列及公式序列C1,C2,Cl.如果每如果每一个一个Ci(1 i l)是某个是某个Aj,或者可由序列中前面的公式应用推理或者可由序列中前面的公式应用推理规则得到规则得到,并且并且Cl=B,则称这个公式序列是由则称这个公式序列是由A1,A2,Ak推推出出B的的证明证明见例子见例
10、子3.3/3.4例例2 构造下面推理的证明：构造下面推理的证明：若明天是星期一或星期三，我明天就有课若明天是星期一或星期三，我明天就有课.若我明天有若我明天有 课，今天必备课课，今天必备课.我今天没备课我今天没备课.所以，明天不是星期一、所以，明天不是星期一、也不是星期三也不是星期三.解解 (1)设命题并符号化设命题并符号化 设设 p：明天是星期一，：明天是星期一，q：明天是星期三，：明天是星期三，r：我明天有课，：我明天有课，s：我今天备课：我今天备课第十一页，共25页。直接证明法直接证明法(2)写出证明的形式结构写出证明的形式结构 前提：前提：(p q)r,rs,s 结论：结论：pq(3)
11、证明证明 rs 前提引入前提引入 s 前提引入前提引入 r 拒取式拒取式 (p q)r 前提引入前提引入 (p q)拒取式拒取式 pq 置换置换第十二页，共25页。附加前提证明法附加前提证明法附加前提证明法附加前提证明法 适用于结论为蕴涵式适用于结论为蕴涵式欲证欲证 前提：前提：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)B第十三页，共25页。附加前提证明法实例附加前提证明法实例例例3 构造下面推理的证明构造下面推
12、理的证明 2是素数或合数是素数或合数.若若2是素数，则是素数，则 是无理数是无理数.若若 是无理是无理数，则数，则4不是素数不是素数.所以，如果所以，如果4是素数，则是素数，则2是合数是合数.解解 用附加前提证明法构造证明用附加前提证明法构造证明 (1)设设 p：2是素数，是素数，q：2是合数，是合数，r：是无理数，是无理数，s：4是素数是素数 (2)推理的形式结构推理的形式结构 前提：前提：p q,pr,rs 结论：结论：sq 222第十四页，共25页。附加前提证明法实例附加前提证明法实例 (3)证明证明 s 附加前提引入附加前提引入 pr 前提引入前提引入 rs 前提引入前提引入 ps 假
13、言三段论假言三段论 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段论析取三段论第十五页，共25页。归谬法（反证法）归谬法（反证法）归谬法归谬法(反证法反证法)欲证欲证 前提：前提：A1,A2,Ak 结论：结论：B做法做法 在前提中加入在前提中加入 B，推出矛盾，推出矛盾.理由理由 A1 A2 AkB (A1 A2 Ak)B (A1 A2 AkB)(A1 A2 AkB)0 A1 A2 AkB0第十六页，共25页。归谬法实例归谬法实例例例4 前提：前提：(p q)r,rs,s,p 结论：结论：q证明证明 用归缪法用归缪法 q 结论否定引入结论否定引入 rs 前提引入前提引入 s 前提引入
14、前提引入 r 拒取式拒取式 (p q)r 前提引入前提引入 (p q)析取三段论析取三段论 pq 置换置换 p 析取三段论析取三段论 p 前提引入前提引入 p p 合取合取第十七页，共25页。第三章第三章 习题课习题课主要内容主要内容l 推理的形式结构推理的形式结构l 判断推理是否正确的方法判断推理是否正确的方法 真值表法真值表法 等值演算法等值演算法 主析取范式法主析取范式法l 推理定律推理定律l 自然推理系统自然推理系统Pl 构造推理证明的方法构造推理证明的方法 直接证明法直接证明法 附加前提证明法附加前提证明法 归谬法归谬法(反证法反证法)第十八页，共25页。基本要求基本要求l 理解并记
15、住推理形式结构的两种形式：理解并记住推理形式结构的两种形式：1.(A1 A2 Ak)B 2.前提：前提：A1,A2,Ak 结论：结论：Bl 熟练掌握判断推理是否正确的不同方法（如真值表法、等熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）值演算法、主析取范式法等）l 牢记牢记 P 系统中各条推理规则系统中各条推理规则l 熟练掌握构造证明的直接证明法、附加前提证明法和归谬熟练掌握构造证明的直接证明法、附加前提证明法和归谬 法法l 会解决实际中的简单推理问题会解决实际中的简单推理问题第十九页，共25页。练习练习1：判断推理是否正确：判断推理是否正确1.判断下面推理是否正
16、确判断下面推理是否正确:(1)前提：前提：pq,q 结论：结论：p 解解 推理的形式结构推理的形式结构:(pq)qp 方法一：等值演算法方法一：等值演算法 (pq)qp (p q)q)p (pq)qp (p q)(q q)p p q易知易知10是成假赋值，不是重言式，所以推理不正确是成假赋值，不是重言式，所以推理不正确.第二十页，共25页。练习练习1解答解答方法二：主析取范式法，方法二：主析取范式法，(pq)qp (p q)q)p p q M2 m0 m1 m3未含未含m2,不是重言式不是重言式,推理不正确推理不正确.第二十一页，共25页。练习练习1解答解答方法三方法三 真值表法真值表法 不是
17、重言式不是重言式,推理不正确推理不正确111001110100(pq)qpqp pq 0 1 1 1(pq)q 0 0 1 0方法四方法四 直接观察出直接观察出10是成假赋值是成假赋值第二十二页，共25页。练习练习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)(qp)1推理正确推理正确(2)前提：前提：qr,pr 结论：结论：qp 解解 推理的形式结构：推理的形式结构：(qr)(pr)(qp)第二十三页，共25页。练习练习2：构造证明：构造证明2.在系统在系统P
18、中构造下面推理的证明：中构造下面推理的证明：如果今天是周六，我们就到颐和园或圆明园玩如果今天是周六，我们就到颐和园或圆明园玩.如果颐和如果颐和 园游人太多，就不去颐和园园游人太多，就不去颐和园.今天是周六，并且颐和园游今天是周六，并且颐和园游 人太多人太多.所以所以,我们去圆明园或动物园玩我们去圆明园或动物园玩.证明证明：(1)设设 p：今天是周六，：今天是周六，q：到颐和园玩，：到颐和园玩，r：到圆明园玩，：到圆明园玩，s：颐和园游人太多：颐和园游人太多 t：到动物园玩：到动物园玩 (2)前提：前提：p(q r),sq,p,s 结论：结论：r t第二十四页，共25页。练习练习2解答解答(3)证明：证明：p(q r)前提引入前提引入 p 前提引入前提引入 q r 假言推理假言推理 sq 前提引入前提引入 s 前提引入前提引入 q 假言推理假言推理 r 析取三段论析取三段论 r t 附加附加第二十五页，共25页。
