《离散数学：1-6 推理理论》由会员分享，可在线阅读，更多相关《离散数学：1-6 推理理论（28页珍藏版）》请在金锄头文库上搜索。
1、1.6 命题逻辑的推理理论命题逻辑的推理理论 推理的形式结构推理的形式结构判断推理是否正确的方法判断推理是否正确的方法推理定律与推理规则推理定律与推理规则构造证明法构造证明法1推理的形式结构推理的形式结构问题的引入问题的引入推理举例推理举例:(1)正项级数收敛当且仅当部分和有上界正项级数收敛当且仅当部分和有上界.(2)若若A C B D，则，则A B且且C D.推理推理:从前提出发推出结论的思维过程从前提出发推出结论的思维过程上面上面(1)是正确的推理，而是正确的推理，而(2)是错误的推理是错误的推理.证明证明:描述推理正确的过程描述推理正确的过程.2推理的形式结构推理的形式结构定义定义若对于
2、每组赋值，或者若对于每组赋值，或者A1 A2 Ak均为假，均为假，或者当或者当A1 A2 Ak为真时为真时,B也为真也为真,则称由则称由A1,A2,Ak推推B的的推推理理正正确确,否否则则推推理理不不正正确确（错错误误）.“A1,A2,Ak推推B” 的推理正确的推理正确当且仅当当且仅当A1 A2 AkB为重言式为重言式.推理的形式结构推理的形式结构:A1 A2 AkB 或或前提：前提：A1,A2,Ak结论：结论：B若推理正确，则记作：若推理正确，则记作：A1 A2 AkB.3判断推理是否正确的方法判断推理是否正确的方法真值表法真值表法等值演算法等值演算法 判断推理是否正确判断推理是否正确主析取
3、范式法主析取范式法构造证明法构造证明法 证明推理正确证明推理正确 说明：当命题变项比较少时，用前说明：当命题变项比较少时，用前3 3个方法比较方个方法比较方便便, , 此时采用此时采用形式结构形式结构“A1 A2 AkB” . 而在而在构构造证明时，造证明时，采用采用“前提前提:A1,A2,Ak,结论结论:B”.4实例实例例例判断下面推理是否正确判断下面推理是否正确(1)若今天是若今天是1号，则明天是号，则明天是5号号.今天是今天是1号号.所所以明天是以明天是5号号.解解设设p：今天是今天是1号，号，q：明天是明天是5号号.推理的形式结构为推理的形式结构为:(pq) pq证明（用等值演算法）证
4、明（用等值演算法）(pq) pq ( p q) p) q pq q1得证推理正确得证推理正确5实例实例(续续)(2)若若今今天天是是1号号，则则明明天天是是5号号.明明天天是是5号号.所所以以今今天天是是1号号.解解设设p：今天是今天是1号，号，q：明天是明天是5号号.推理的形式结构为推理的形式结构为:(pq) qp证明（用主析取范式法）证明（用主析取范式法）(pq) qp( p q) qp ( p q) q) p q p( pq) (pq) (pq) (p q)m0 m2 m3结果不含结果不含m1,故故01是成假赋值，所以推理不正确是成假赋值，所以推理不正确.6推理定律推理定律重言蕴涵式重言
5、蕴涵式 重要的推理定律重要的推理定律 A(A B)附加律附加律(A B)A化简律化简律(AB) AB假言推理假言推理(AB)B A拒取式拒取式(A B)BA析取三段论析取三段论(AB) (BC)(AC)假言三段论假言三段论(AB) (BC)(AC)等价三段论等价三段论(AB) (CD) (A C)(B D)构造性二难构造性二难7推理定律推理定律(续续)(AB) ( AB)B构造性二难（特殊形式）构造性二难（特殊形式）(AB) (CD) ( BD)( AC)破坏性二难破坏性二难说明：说明：A,B,C为元语言符号为元语言符号若某推理符合某条推理定律，则它自然是正确的若某推理符合某条推理定律，则它自
6、然是正确的AB产生两条推理定律产生两条推理定律:A B, B A8推理规则推理规则 (1)前提引入规则前提引入规则(2)结论引入规则结论引入规则(3)置换规则置换规则(4)假言推理规则假言推理规则 AB A B(5)附加规则附加规则AA B(6)化简规则化简规则 A B A (7)拒取式规则拒取式规则 AB BA(8)假言三段论规则假言三段论规则ABBCAC9推理规则推理规则( (续续) )(11)破破坏坏性性二二难难推推理理规则规则ABCD BDAC(12)合取引入规则合取引入规则ABA B(9)析取三段论规则析取三段论规则A B BA(10)构构造造性性二二难难推推理理规则规则ABCDA
7、CB D10直接证明法例例2 在自然推理系统在自然推理系统P中构造下面推理的证明中构造下面推理的证明:前提前提: p q, qr, ps, s结论结论: r(p q) )11直接证明法例例2 在自然推理系统在自然推理系统P中构造下面推理的证明中构造下面推理的证明:前提前提: p q, qr, ps, s结论结论: r(p q) )证明证明 ps 前提引入前提引入 s 前提引入前提引入 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段论析取三段论 qr 前提引入前提引入 r 假言推理假言推理 r(p q) ) 合取合取推理正确推理正确, , r(p q) )是有效结论是有效结论12构造证
8、明构造证明直接证明法直接证明法例例构造下面推理的证明：构造下面推理的证明：若明天是星期一或星期三，我就有课若明天是星期一或星期三，我就有课.若有课，若有课，今天必备课今天必备课.我今天下午没备课我今天下午没备课.所以，所以，明天不是星期一和星期三明天不是星期一和星期三.解解设设p：明天是星期一，明天是星期一，q：明天是星期三，明天是星期三，r：我有课，我有课，s：我备课我备课推理的形式结构为推理的形式结构为前提：前提：(p q)r,rs, s结论：结论： pq13直接证明法直接证明法(续续)证明证明rs前提引入前提引入 s前提引入前提引入 r拒取式拒取式(p q)r前提引入前提引入 (p q)
9、拒取式拒取式 pq置换置换14附加前提证明法欲证明欲证明 等价地证明等价地证明前提前提: A1, A2, , Ak 前提前提: A1, A2, , Ak, C结论结论: CB 结论结论: B理由理由:(A1 A2 Ak)(CB) (A1 A2 Ak) ( C B) (A1 A2 Ak C) B(A1 A2 Ak C)B15实例例例4 构造下面推理的证明构造下面推理的证明:前提前提: p q, q r, rs结论结论: ps证明证明 p 附加前提引入附加前提引入 p q 前提引入前提引入 q 析取三段论析取三段论 q r 前提引入前提引入 r 析取三段论析取三段论 rs 前提引入前提引入 s 假
10、言推理假言推理推理正确推理正确, , ps是有效结论是有效结论16归谬法(反证法)欲证明欲证明前提：前提：A1, A2, , Ak 结论：结论：B将将 B加入前提加入前提, 若推出矛盾若推出矛盾, 则得证推理正确则得证推理正确. 理由理由:A1 A2 AkB (A1 A2 Ak) B (A1 A2 AkB)括号内部为矛盾式当且仅当括号内部为矛盾式当且仅当(A1 A2 AkB)为重言式为重言式17实例例例5 构造下面推理的证明构造下面推理的证明前提前提: (p q) r, rs, s, p结论结论: q证明证明 用归缪法用归缪法 q 结论否定引入结论否定引入 rs 前提引入前提引入 s 前提引入
11、前提引入 r 拒取式拒取式 (p q) r 前提引入前提引入 (p q) 析取三段论析取三段论 pq 置换置换 p 析取三段论析取三段论 p 前提引入前提引入 p p 合取合取 推理正确推理正确, , q是有效结论是有效结论18归结证明法理由理由 (p q)(p r)(q r) ( (p q)(p r) (q r) ( pq)(pr) q r ( ( pq) q)(pr) r) ( p q)(p r) 1 1归结规则归结规则 A B A C B C19归结特殊形式归结规则归结规则 A B A B归结规则归结规则 A A C C归结规则归结规则 A A 020归结证明法(续)在自然推理系统在自然
12、推理系统P中只需下述推理规则中只需下述推理规则:(1) 前提引入规则前提引入规则(2) 结论引入规则结论引入规则(3) 置换规则置换规则(4) 化简规则化简规则(5) 合取引入规则合取引入规则(6) 归结规则归结规则21归结证明法的基本步骤1. 将每一个前提化成等值的合取范式将每一个前提化成等值的合取范式, 设所有合取范式的设所有合取范式的 全部简单析取式为全部简单析取式为A1, A2, At2. 将结论化成等值的合取范式将结论化成等值的合取范式B1 B2 Bs, 其中每个其中每个Bj 是简单析取式是简单析取式3. 以以A1,A2,At为前提为前提, 使用归结规则推出每一个使用归结规则推出每一
13、个Bj, 1 j s4. 由合取引入规则得到结论由合取引入规则得到结论B1 B2 Bs22实例例例6 用归结证明法构造下面推理的证明用归结证明法构造下面推理的证明:前提前提: ( (pq)r, rs, s结论结论: ( (pq)()(p s) )解解 ( (pq)r ( (p q)r ( (pq)r ( (p r) (q r) ) rs r s ( (pq)()(p s) ) (p q)()(p s) () (pq)(p s) ) p (q s)推理可表成推理可表成前提前提: : p r, , q r, , r s, , s结论结论: p (q s)23实例(续)前提前提: : p r, ,
14、q r, , r s, , s结论结论: p(q s)证明证明 q r 前提引入前提引入 r s 前提引入前提引入 q s 归结归结 s 前提引入前提引入 r 归结归结 p r 前提引入前提引入 p 归结归结 p(q s) 合取引入合取引入 24归结证明法的基本步骤1. 将每一个前提化成等值的合取范式将每一个前提化成等值的合取范式, 设所有合取设所有合取范式的全部简单析取式为范式的全部简单析取式为A1, A2, At2. 将结论的反面化成等值的合取范式将结论的反面化成等值的合取范式B1 B2 Bs, 其中每个其中每个Bj 是简单析取式是简单析取式3. 以以A1,A2,At和和Bj, 1 j s
15、为前提导出矛盾！为前提导出矛盾！25实例例例6 用归结证明法构造下面推理的证明用归结证明法构造下面推理的证明:前提前提: ( (pq)r, rs, s结论结论: ( (pq)()(p s) )解解 ( (pq)r ( (p q)r ( (pq)r ( (p r) (q r) ) rs r s (pq)()(p s) ) (p q)()(p s) ) (pq)(p s) ) (pq)(p s) ) ( ( p q)(ps) ) ( ( p q) (ps) ) 推理可表成推理可表成前提前提: : p r, , q r, , r s, , s, p q, ps结论结论: 矛盾矛盾26前提前提: : p r, , q r, , r s, , s, p q, ps结论结论: 矛盾矛盾证明证明 q r 前提引入前提引入 r s 前提引入前提引入 q s 归结归结 s 前提引入前提引入 r 归结归结 p r 前提引入前提引入 p 归结归结 p q 前提引入前提引入 q 归结归结 r 归结归结 0 归结归结27作业：P35-36:T1.17(2)(4)自由练习：自由练习：T1.16T1.18-T1.2228
