离散数学-复习和例题讲解.ppt

《离散数学-复习和例题讲解.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、温故而知新!9/19/20211温故而知新!数理逻辑2温故而知新!数理逻辑研究内容第二章第四章第三章第五章第一章在教材中体现不多3温故而知新!熟练掌握将简单自然语句形式化的方法。熟悉基本的等值公式，对于常用的等值公式，能在理解的基础上熟记并能在等值演算中灵活使用；理解范式的概念深入理解主析取范式和主合取范式的构成，能够将命题公式熟练的化成相应的主析取范式和主合取范式；理解推理形式的基本结构，掌握重言蕴涵的概念和主要结果；熟悉基本的推理公式，掌握推理公式的不同证明方法；理解基本的推理规则，掌握使用推理规则进行推理演算的方法；重点解决使用谓词逻辑描述自然语

2、句的表达问题，能够熟练的将一些自然语句进行形式化描述；理解谓词逻辑公式等值的概念，掌握否定型等值式的不同形式及其证明方法；熟悉谓词逻辑的基本推理公式，能够给出解释性的证明和其它推理公式正确性的判断；理解谓词逻辑有关量词的四条推理规则，掌握使用推理规则进行推理演算的方法；4温故而知新!命题逻辑命题逻辑也称命题演算，或语句逻辑。它研究以命题为基本单位构成的前提和结论之间的可推导关系，研究什么是命题？如何表示命题？如何由一组前提推导一些结论？命题逻辑的特征：在研究逻辑的形式时，我们把一个命题只分析到其中所含的命题成份为止，不再分析下去。不把一个简单命题再分析

3、为非命题的集合，不把谓词和量词等非命题成份分析出来。5温故而知新!具有确切真值的陈述句称为命题明年国庆节是晴天。地球外的星球上也有人１＋１＝１０。x+y>０。一般来说，命题可分两种类型：原子命题(简单命题)：不能再分解为更为简单命题的命题。复合命题：可以分解为更为简单命题的命题。而且这些简单命题之间是通过如“或者”、“并且”、“不”、“如果...则...”、“当且仅当”等这样的关联词和标点符号复合而构成一个复合命题。命题的分类6温故而知新!命题联结词联结词记号记法读法否定┐┐A非A合取∧A∧BA合取B析取∨A∨BA析取B蕴涵→A→BA蕴涵B等价AB

4、A等价于B联结词连接的是两个命题真值之间的联结，而不是命题内容之间的连接，因此复合命题的真值只取决于构成他们的各原子命题的真值，而与它们的内容、含义无关，与联结次所连接的两原子命题之间是否有关系无关；与非:P↑Q=┐(P∧Q)或非:P↓Q=┐(P∨Q)排斥或(异或):P⊕Q=┐(PQ)=P∧┐Q∨┐P∧Q蕴含否定:P→Q=┐(P→Q)7温故而知新!｛┐，∨｝,｛┐，∧｝可以构成功能联结词集合。使用上述全功能联结词集合表达的命题公式类的系统常称为Boole代数系统｛┐，→｝也可构成全功能联结词集合。该全功能联结词集合在研究逻辑系统的演绎与推理，以及在程

5、序系统的研究中经常遇到。｛↑｝,｛↓｝是全功能联结词集合。在大规模集成电路中有广泛的应用。一些重要的全功能联结词集合8温故而知新!定义(命题公式)简称公式单个原子公式本身是一个命题公式；如P是公式，则(┐P)也是命题公式；如P，Q是公式，则(P∧Q)、(P∨Q)、(P→Q)、(PQ)也是命题公式；命题公式仅由有限步使用规则1-3后产生的结果。该公式常用符号G、H、…等表示。单个命题变元和命题常元叫原子公式9温故而知新!公式G1称为永真公式(重言式)，如果在它的所有解释之下都为“真”。设A:A(P1,P2,…,Pn),B:B(P1,P2,…,Pn)是两

6、个命题公式,这里Pi(i=1,2,…,n)不一定在两公式中同时出现。恒等式如果AB是重言式,则A与B对任何指派都有相同的真值。记为A=B,叫做逻辑恒等式,读做“A恒等于B”。10温故而知新!逻辑恒等式11温故而知新!牌输毛立等运归恒等式的记忆排中律输出律矛盾律逆反律等值表达式蕴含表达式归缪律焦急又等得丰收交换律结合律双否定等幂律德.摩根定律分配律吸收律12温故而知新!首先，双条件词“”是一种逻辑联结词，公式GH是命题公式，其中“”是一种逻辑运算，GH的结果仍是一个命题公式。而逻辑等价“”则是描述了两个公式G与H之间的一种逻辑等价关系，GH表

7、示“命题公式G等价于命题公式H”，GH的结果不是命题公式。其次，如果要求用计算机来判断命题公式G、H是否逻辑等价，即GH那是办不到的，然而计算机却可“计算”公式GH是否是永真公式。“”与“”的区别13温故而知新!永真蕴含式如果A→B是一永真式,那么称为永真蕴含式,记为AB,读做“A永真蕴含B”。设G，H是两个公式，称H是G的逻辑结果(或称G蕴涵H)当且仅当对任意解释I，如果I满足G，则I也满足H。将G蕴涵H记为GH。此时G称为前提，H称为结论。永真蕴含式可用真值表证明，但也可用以下办法证明:(1)假定前件是真,若能推出后件是真,则此蕴含式是

8、真。(2)假定后件是假,若能推出前件是假,则此蕴含式是真。14温故而知新!“”与“→”的区别