离散数学第7讲.ppt

《离散数学第7讲.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、离散数学第7讲回顾上节课重要知识点：理解命题逻辑推理的基本概念；掌握推理常用的三种方法：真值表法等价值演算法主析取范式掌握九条重要的推理定律；1离散数学第7讲本节课基本知识点：自然推理系统的定义自然推理系统中的常用的推理规则；自然推理系统中的构造证明法。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.63、推理规则6第三章命题逻辑的推理理论构造证明法祥解：构造证明法也是自然推理中的一种常用方法，适用于命题变项较多时，且必须在给定的规则下

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

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

6、辑的推理理论例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前提引入②pq①置换规则③r∨רq前提引入④qr③置换规则⑤pr②④假言三段论⑥rs前提引入⑦ps⑤⑥假言三段论13第三章命题逻辑的推理理论注：1、推

7、理过程不是唯一的。只要严格按照推理规则从而得到有效结论的推理就是正确的。2、证明过程中不要跳步。（跳步在等价公式或蕴含式的证明中可以使用，但这里不可以）14第三章命题逻辑的推理理论例3.4：在自然推理系统中构造下列推理的证明。若a是实数，则它不是有理数就是无理数。若a不能表示成分数，则它不是有理数。a是实数且它不能表示成分数，所以a是无理数。（前提、结论未明确给出,需要自己构造。)解：首先将简单命题符号化p:a是实数q:a是有理数r:a是无理数s:a能表示成分数15第三章命题逻辑的推理理论前提：p(q∨r),רsרq，p∧רs结论：r证明:①p∧רs前提

8、引入②p①化简规则③רs①化简规则④p(q∨r)前