离散数学第7讲.ppt

《离散数学第7讲.ppt》由会员分享，可在线阅读，更多相关《离散数学第7讲.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学离散数学 第第7讲讲回顾上节课重要知识点：回顾上节课重要知识点：n理解命题逻辑推理的基本概念；理解命题逻辑推理的基本概念；n掌握推理常用的三种方法：掌握推理常用的三种方法：真值表法真值表法等价值演算法等价值演算法主析取范式主析取范式n掌握九条重要的推理定律；掌握九条重要的推理定律；1离散数学离散数学 第第7讲讲本节课基本知识点：本节课基本知识点：n自然推理系统的定义自然推理系统的定义n自然推理系统中的常用的推理规则；自然推理系统中的常用的推理规则；n自然推理系统中的构造证明法。自然推理系统中的构造证明法。2第三章第三章 命题逻辑的推理理论命题逻辑的推理理论 3.2 自然推理系统自然推理

2、系统 在推理过程中，如果命题变元较多或前提较多，在推理过程中，如果命题变元较多或前提较多，以上三种方法都不方便，因而引入以上三种方法都不方便，因而引入构造证明方法构造证明方法。证证明明是一个描述推理过程的是一个描述推理过程的命题公式序列命题公式序列，其中的每个，其中的每个命题公式，或者是已知的前提，或者是由某些前提应命题公式，或者是已知的前提，或者是由某些前提应用推理规则得到的结论（中间结论或推理中的结论）。用推理规则得到的结论（中间结论或推理中的结论）。而要构造出严谨的证明就必须在形式系统中进行，而要构造出严谨的证明就必须在形式系统中进行，因而首先给出形式系统的定义。因而首先给出形式系统的定

3、义。3第三章第三章 命题逻辑的推理理论命题逻辑的推理理论定义定义3.2 形式系统形式系统一个形式系统一个形式系统I 由下列四个部分组成：由下列四个部分组成：（1）非空的字母表集，记作）非空的字母表集，记作A（I）。）。（2）由）由A（I）中符号构造的合式公式集，记作中符号构造的合式公式集，记作E（I）。）。（3）E（I）中中一一些些特特殊殊的的公公式式组组成成的的公公理理集集,记记作作AX（I）。）。（4）推理规则集，记作推理规则集，记作r（I）。可以将可以将I 记作为记作为4元组元组其中其中是是I 的的形式语言系统形式语言系统 为为I 的的形式演算系统形式演算系统4第三章第三章 命题逻辑的推

4、理理论命题逻辑的推理理论形式系统一般分为两类：形式系统一般分为两类：自然推理系统自然推理系统（本书介绍）（本书介绍）特特点点：从从任任意意给给定定的的前前提提出出发发，应应用用系系统统中中的的推推理理规规则则进进行行推推理理演演算算，得得到到的的最最后后命命题题公公式式是是推推理理的的结结论论，此此结结论可能是重言式，也可能不是。论可能是重言式，也可能不是。公理推理系统公理推理系统 特特点点：只只能能从从若若干干条条给给定定的的公公理理出出发发，应应用用系系统统中中的的推推理理规规则则进进行行推推理理演演算算，得得到到的的结结论论是是系系统统中中的的重重言言式式，称为系统中的定理。称为系统中的

5、定理。5第三章第三章 命题逻辑的推理理论命题逻辑的推理理论定义定义3.3 自然推理系统自然推理系统（不含有公理部分）（不含有公理部分）自然推理系统自然推理系统p定义如下：定义如下：1、字母表、字母表 （1）命题变项符号：）命题变项符号：p,q,r,（2）联结词符号：联结词符号：，（3 3）括号与逗号括号与逗号：(),(),2 2、合式公式、合式公式 定义同定义同1.61.63 3、推理规则、推理规则 6第三章第三章 命题逻辑的推理理论命题逻辑的推理理论构造证明法祥解：n构造证明法也是自然推理中的一种常用方法，适用于命题变项较多时，且必须在给定的规则下进行。n构造证明法是一个描述推理过程的命题公

6、式序列，其中的每个命题公式或者是已知的前提，或者是某些前提应用推理规则得到的结论。7第三章第三章 命题逻辑的推理理论命题逻辑的推理理论证明中常用的推理规则：1、前提引入规则P：在证明的任何一步上都可引入前提。2、结论引入规则T：在证明的任何一步上，所证明的结论都可作为后续证明的前提。3、置换规则：在证明的任何一步上，命题公式中任何子命题公式都可用与之等值的命题公式置换。（等值公式参考课本P21）8第三章第三章 命题逻辑的推理理论命题逻辑的推理理论4、代入规则：在证明的任何一步上，永真式中某一变元的所有出现都可代入同一公式。5、假言推理规则(分离规则)：A B,A=B 6、附加规则：A=AB7、

7、化简规则：AB=A8、拒取式规则：A B,B=A9、假言三段论规则：A B,B C=A C9第三章第三章 命题逻辑的推理理论命题逻辑的推理理论10、析取三段论规则:A B,A=B11、构造性两难规则：A B,C D,AC=B D12、合取引入规则：A，B=AB 13、假设引消规则CP规则规则：可在任何步骤引入假设A，此后推出B后，即可消去假设A，而得到结论A B(附加前提)。10第三章第三章 命题逻辑的推理理论命题逻辑的推理理论例：例：前提：前提：P R，Q S，P Q 结论：结论：R S证明：证明：P R 前提引入前提引入 Q S 前提引入前提引入 P Q 前提引入前提引入 R S 构造性两

8、难规则11第三章第三章 命题逻辑的推理理论命题逻辑的推理理论例例3.3：在自然推理系统中构造下列推理的证明。：在自然推理系统中构造下列推理的证明。(1)前提：前提：p q,q r,p s,s结论：结论：r(q p)（前提、结论已明确给出）证明：证明：p s 前提引入前提引入 s 前提引入前提引入 p 拒取式拒取式 p q 前提引入前提引入 q 析取三段论析取三段论 q r 前提引入前提引入 r 假言推理假言推理 r(q p)合取规则合取规则12第三章第三章 命题逻辑的推理理论命题逻辑的推理理论(2)前提：前提：p q,r q,r s结论：结论：p s（前提、结论已明确给出）解：p q 前提引入

9、前提引入 p q 置换规则置换规则 r q 前提引入前提引入 q r 置换规则置换规则 p r 假言三段论假言三段论 r s 前提引入前提引入 p s 假言三段论假言三段论13第三章第三章 命题逻辑的推理理论命题逻辑的推理理论注：注：1 1、推理过程不是唯一的。、推理过程不是唯一的。只要严格按照推理规则从而得到有效结论的只要严格按照推理规则从而得到有效结论的推理就是正确的。推理就是正确的。2 2、证明过程中不要跳步。（跳步在等价公、证明过程中不要跳步。（跳步在等价公式或蕴含式的证明中可以使用，但这里不式或蕴含式的证明中可以使用，但这里不可以）可以）14第三章第三章 命题逻辑的推理理论命题逻辑的

10、推理理论例例3.4：在自然推理系统中构造下列推理的证明。：在自然推理系统中构造下列推理的证明。若若a是是实实数数，则则它它不不是是有有理理数数就就是是无无理理数数。若若a不不能能表表示示成成分分数数，则则它它不不是是有有理理数数。a是是实实数数且且它它不能表示成分数，所以不能表示成分数，所以a是无理数。是无理数。（前提、结论未明确给出,需要自己构造。)解：首先将简单命题符号化解：首先将简单命题符号化 p:a是实数是实数 q:a是有理数是有理数 r:a是无理数是无理数 s:a能表示成分数能表示成分数15第三章第三章 命题逻辑的推理理论命题逻辑的推理理论前提：前提：p (qr),s q，p s结论

11、：结论：r证明证明:p s 前提引入前提引入 p 化简规则化简规则 s 化简规则化简规则 p (qr)前提引入前提引入 qr 假言推理假言推理 s q 前提引入前提引入 q 假言推理假言推理 r 析取三段论析取三段论16第三章第三章 命题逻辑的推理理论命题逻辑的推理理论两种特殊的证明方法两种特殊的证明方法1附加前提证明法（附加前提证明法（CP规则）规则）适用于此类蕴涵式的证明适用于此类蕴涵式的证明 (A1 A2 Ak)(A B)(*)欲欲证明证明(*)式为式为重言式重言式，只需证明只需证明 (A1 A2 Ak A)B 为重言式，因为为重言式，因为17第三章第三章 命题逻辑的推理理论命题逻辑的推

12、理理论(*)式式 (A1 A2 Ak)(A B)(A1 A2 Ak)(A B)(A1 A2 Ak)(A B)A1 A2 Ak A B (A1 A2 Ak A)B (A1 A2 Ak A)B (A1 A2 Ak A)B18第三章第三章 命题逻辑的推理理论命题逻辑的推理理论例例：前提：前提：p(q r),s p,q结论：结论：s r证明：证明：s p 前提引入前提引入 s 附加附加前提引入前提引入CP规则规则 p 假言推理假言推理 p(q r)前提引入前提引入 q r 假言推理假言推理 q 前提引入前提引入 r 假言推理假言推理 s r CP规则规则19第三章第三章 命题逻辑的推理理论命题逻辑的推

13、理理论两种特殊的证明方法两种特殊的证明方法2归谬法归谬法 适用于此类蕴涵式的证明适用于此类蕴涵式的证明 (A1 A2 Ak)B (*)欲欲证证明明(*)式式，只只需需将将 B作作为为前前提提能能推推出出矛矛盾盾来来即即可。因为：可。因为：(*)(A1 A2 Ak)B (A1 A2 Ak B）若若(A1 A2 Ak B）为）为矛盾式，则矛盾式，则 (A1 A2 Ak)B 为为重言式重言式 ，即，即 (A1 A2 Ak)=B20第三章第三章 命题逻辑的推理理论命题逻辑的推理理论例例：前提：前提：p q ,r q,r s 结论：结论：p证明：证明：p 结论否定结论否定引入引入 p q 前提引入前提引

14、入 q 假言推理假言推理 r q 前提引入前提引入 r 析取三段论析取三段论 r s 前提引入前提引入 r 化简规则化简规则 r r 合取，矛盾合取，矛盾21第三章第三章 命题逻辑的推理理论命题逻辑的推理理论练习练习：用归谬法证明：用归谬法证明前提：前提：p q，p r ,q s 结论：结论：r s证明：证明：(r s)结论否定结论否定引入引入 r s 置换规则置换规则 r 化简规则化简规则 p r 前提引入前提引入 p 拒取拒取 s 化简规则化简规则 q s 前提引入前提引入22第三章第三章 命题逻辑的推理理论命题逻辑的推理理论 q 拒取拒取 p q 合取合取 (p q)置换规则置换规则 (

15、11)p q 前提引入前提引入 (12)(p q)(p q)(11)合取合取,矛盾矛盾23第三章第三章 命题逻辑的推理理论命题逻辑的推理理论本讲小结本讲小结n掌握自然推理系统中的常用的推理规则；掌握自然推理系统中的常用的推理规则；n能够应用这些推理规则在自然推理系统对能够应用这些推理规则在自然推理系统对推理进行构造证明。推理进行构造证明。作业作业 P55第第11、12、14、15、16、18题题 24第三章第三章 命题逻辑的推理理论命题逻辑的推理理论本章小结本章小结一、本章重要知识点：一、本章重要知识点：n理解命题逻辑推理的基本概念；理解命题逻辑推理的基本概念；n掌握推理常用的三种方法：掌握推理常用的三种方法：n掌握九条重要的推理定律；掌握九条重要的推理定律；n掌握自然推理系统中的常用的推理规则；掌握自然推理系统中的常用的推理规则；n能够应用这些推理规则在自然推理系统对能够应用这些推理规则在自然推理系统对推理进行构造证明。推理进行构造证明。25第三章第三章 命题逻辑的推理理论命题逻辑的推理理论二、典型例题二、典型例题1、R(P S),Q S=P(QR)2、RQRQ，RSRS，SQSQ，PQ PQ=PP 3 3、试证明、试证明（），=。26