离散数学导论第5版-第五篇.ppt

《离散数学导论第5版-第五篇.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1离散数学导论（第5版）电子教案徐洁磐2第五篇数理逻辑数理逻辑是用数学方法研究形式逻辑演绎推理规则的科学，它是一门数学，是一门研究演绎推理规则的数学，在学习此部分时，主要要掌握如下几个要点：①思维的形式化②指派法③公式推理④公理系统⑤范式⑥自动定理证明3本篇由命题逻辑、谓词逻辑、公理化理论部分组成，其中命题逻辑以命题为研究对象而谓词逻辑则以谓词为研究对象，而公理化理论则是数理逻辑中演绎推理的形式化思想的介绍，它们的有机结合构成完整的整体。4第10章命题逻辑命题逻辑以命题为对象，研究命题的符号体系及推理规则。§10.1命题与命题联结词

2、（1）命题——能判别真假的语句。（2）基本命题联结词——否定、并且、或者、蕴含、等价。§10.2命题公式（3）命题公式——由命题及命题联结词构成命题公式。§10.3重言式（4）指派——命题公式中变元的一组确定的值。（5）重言式——所有指派均取值为真的公式。5§10.4命题逻辑基本等式及等式推理（6）等式推理：由三部分组成：它们是基本等式、推理规则及推理过程。（7）命题逻辑42个基本等式。交换律P∨Q＝Q∨P；P∧Q＝Q∧P；PQ＝QP．结合律（P∨Q）∨R＝P∨（Q∨R）；（P∧Q）∧R＝P∧（Q∧R）；（PQ）R＝P（Q

3、R）．分配律P∧（Q∨R）＝（P∧Q）∨（P∧R）；P∨（Q∧R）＝（P∨Q）∧（P∨R）；6否定深入P＝P；（P∧Q）＝P∨Q；（P∨Q）＝P∧Q；（PQ）＝P∧Q；(14)（PQ）＝PQ＝PQ；变元等同P∧P＝P；P∨P＝P；P∧P＝F；P∨P＝T；PP＝T；PP＝P；PP＝P；PP＝T；PP＝PP＝F；7常值与变元的联结T∧P＝P；F∧P＝F；T∨P＝T；F∨P＝F；TP＝P；FP＝T；PT＝T；PF＝P；TP＝P；FP＝P；8联结词化归P∧Q＝（

4、P∨Q）；P∨Q＝（P∧Q）；PQ＝P∨Q；PQ＝（PQ）∧（QP）其它PQ＝QP(PQ)∧（PR）＝PQ∧RP∨（P∧Q）＝PP（QR）＝P∧QRP∧（P∨Q）＝P9（8）推理规则：代入规则替换规则(9)推理过程由P到Q的推理过程是一个等式序列：P=P1P1=P2……Pn-1=PnPn=P10§10.5命题逻辑基本蕴含式及蕴含推理（10）蕴含推理是单向推理，它有三部分组成：前提－已知条件证明－是一种过程定理－结论(11)蕴含推理组成：基本蕴含式推理规则证明过程11（9）19个基本蕴含重言

5、式P∧QP；P∧QQ；PP∨Q；QP∨Q；PPQ；QPQ；（PQ）P；（PQ）Q；12P∧（P∨Q）Q；Q∧（P∨Q）P；P∧（PQ）Q；Q∧（PQ）P；(PQ)∧(QR)PR；(PQ)∧(RS)P∧RQ∧S；(P∨Q)∧(PR)∧(QR)R；P(QP∧Q)；(PQ)((QR)(PR))；(P(QR))(Q(PR))；(PQ)((RQ)(P∨RQ))．13（13）11个推理规则P∧Q├P；P∧Q├Q；P├P∨Q；Q├P∨Q；P

6、，QP├Q；P，P∨Q├Q；P，PQ├Q；Q，PQ├P；PQ，QR├PR；PQ，RS├P∧RQ∧S；P∨Q，PR，QR├R；14(14)证明过程是一个公式序列并运用三个规则：P规则T规则CP规则§10.6范式（15）范式——命题公式的一种标准形式（16）主析取范式：该范式是一个析取式，每个析取项是所有命题变元式其否定的合取式。（17）主异合取范式：该范式是一个合取式，每个析取项是所有命题变元式其否定的析取式。15§10.8命题联结词的扩充与归约（18）命题联结词的扩充——异或：、谢佛：、魏泊：、

7、蕴含否定：（19）命题联结词的归约命题联结词可归约为如下形式之一：{,}{,}{}{}16第11章谓词逻辑谓词逻辑基本概念§11.1谓词与个体（1）个体个体常量与个体变量个体域与全总个体域（2）谓词一元谓词——刻划个体性质二元谓词——刻划两个个体间关系n元谓词——刻划n个个体间关系17§11.2量词（3）存在量词：xP(x)——“有一些”之语义（4）全称量词：xP(x)——“所有”之语义（5）量词的辖域——量词所作用的范围§11.3函数（6）函数——个体间的特定关系称函数，它是个体间的映射。f(x

8、)中X是个体而f为函数符号，f(x)为函数。18§11.4谓词逻辑公式（7）谓词逻辑公式项：个体是项，函数是项原子公式：P（t1,t2,…tn）是原子公式（其中ti为项）公式：原子公式是公式；A，B是公式，则（A）,（