《离散数学第7讲》由会员分享，可在线阅读，更多相关《离散数学第7讲（26页珍藏版）》请在金锄头文库上搜索。
1、离散数学 第7讲回顾上节课重要知识点：n理解命题逻辑推理的基本概念；n掌握推理常用的三种方法：真值表法等价值演算法主析取范式n掌握九条重要的推理定律；1离散数学 第7讲本节课基本知识点：n自然推理系统的定义n自然推理系统中的常用的推理规则；n自然推理系统中的构造证明法。2第三章 命题逻辑的推理理论3.2 自然推理系统在推理过程中，如果命题变元较多或前提较多， 以上三种方法都不方便，因而引入构造证明方法。证 明是一个描述推理过程的命题公式序列，其中的每个 命题公式，或者是已知的前提，或者是由某些前提应 用推理规则得到的结论（中间结论或推理中的结论） 。而要构造出严谨的证明就必须在形式系统中进行，
2、 因而首先给出形式系统的定义。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第三章 命题逻辑的推理理论形式系统一般分为两类：自然推理系统（本书介绍）特点：从任意给定的前提出发，应用系统中的推理规则进 行推理演算，得到的最后命题公式是推理的结论，此结 论可能是重言式，也可能不是。 公理推理系统特点：只
3、能从若干条给定的公理出发，应用系统中的推 理规则进行推理演算 ，得到的结论是系统中的重言式， 称为系统中的定理。5第三章 命题逻辑的推理理论定义3.3 自然推理系统（不含有公理部分）自然推理系统p定义如下： 1、字母表（1）命题变项符号：p,q,r,（2）联结词符号： ，（3）括号与逗号：() , 2、合式公式 定义同1.6 3、推理规则6第三章 命题逻辑的推理理论构造证明法祥解：n构造证明法也是自然推理中的一种常 用方法，适用于命题变项较多时，且必 须在给定的规则下进行。n构造证明法是一个描述推理过程的命题 公式序列，其中的每个命题公式或者是已 知的前提，或者是某些前提应用推理规则 得到的结
4、论。7第三章 命题逻辑的推理理论证明中常用的推理规则： 1、前提引入规则P：在证明的任何一步上都 可引入前提。 2、结论引入规则T：在证明的任何一步上， 所证明的结论都可作为后续证明的前提。 3、置换规则：在证明的任何一步上，命题 公式中任何子命题公式都可用与之等值的 命题公式置换。（等值公式参考课本P21 ）8第三章 命题逻辑的推理理论4、代入规则：在证明的任何一步上，永真式中某 一变元的所有出现都可代入同一公式。 5、假言推理规则(分离规则)： A B, A=B 6、 附加规则：A=AB 7、化简规则：AB =A 8、拒取式规则：A B, B = A 9、假言三段论规则：A B,B C =
5、 A C9第三章 命题逻辑的推理理论10、析取三段论规则:A B, A = B 11、构造性两难规则：A B,C D, AC = B D 12、合取引入规则：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 构造性两难规则11第三章 命题逻辑的推理理论例3.3：在自然推理系统中构造下列推理的证明。 (1)前提：p q , q r ,p s , s 结论：r (q p
6、) （前提、结论已明确给出） 证明： 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 前提引入 p q 置换规则 r q 前提引入 q r 置换规则 p r 假言三段论 r s 前提引入 p s 假言三段论13第三章 命题逻辑的推理理论注： 1、推理过程不是唯一的。 只要严格按照推理规则从而得到有效结论的 推理就是正确的。 2、证明过程中不要跳步。（跳步在等价公 式或蕴含式的证明中可
7、以使用，但这里不 可以）14第三章 命题逻辑的推理理论例3.4：在自然推理系统中构造下列推理的证明。 若a是实数，则它不是有理数就是无理数。若a不 能表示成分数，则它不是有理数。a是实数且它 不能表示成分数，所以a是无理数。（前提、结论未明确给出,需要自己构造。)解：首先将简单命题符号化p: a是实数q: a是有理数r: a是无理数s: a能表示成分数15第三章 命题逻辑的推理理论前提： p (qr) , s q ， p s 结论：r 证明: p s 前提引入 p 化简规则 s 化简规则 p (qr) 前提引入 qr 假言推理 s q 前提引入 q 假言推理 r 析取三段论16第三章 命题逻辑
8、的推理理论两种特殊的证明方法1附加前提证明法（CP规则）适用于此类蕴涵式的证明(A1 A2 Ak ) (A B ) (*)欲证明(*)式为重言式，只需证明(A1 A2 Ak A ) B 为重言式，因为17第三章 命题逻辑的推理理论(*) 式 (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 附
9、加前提引入CP规则 p 假言推理 p (q r) 前提引入 q r 假言推理 q 前提引入 r 假言推理 s r CP规则 19第三章 命题逻辑的推理理论两种特殊的证明方法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 前提引入 q
10、 假言推理 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 ) 置换规则(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 (PS), QS = P(QR) 2、RQ，RS，SQ，PQ = P 3、试证明 （）， = 。26
