离散数学-复习和例题讲解课件

2016年2月17日星期三温故而知新!%复述能力100%复50%不复习天1周1个月数理逻辑用数学方法(主要是建立符号体系的方法)来研究推理的形式结构和推理规律的数学学科。引入一套符号体系来研究推理规律的学科,故又称之为符号逻辑(SymbolicLogic)数理逻辑研究内容第二章第三章两个演寫四论命题演算与谓冏演算第五章集合论(集合、关系〈函数、基数模型论(形式语言语法与语义间的关系)在教材递归论(可计算性与可判定性)不多证明论(数学本身的无矛盾性1)熟练掌握将简单自然语句形式化的方法。2)熟悉基本的等值公式,对于常用的等值公式,能在理解的基础上熟记并能在等值演算中灵活使用3)理解范式的概念深入理解主析取范式和主合取范式的构成,能够将命题公式熟练的化成相应的主析取范式和主合取范式4)理解推理形式的基本结构,掌握重言蕴涵的概念和主要结果;熟悉基本的推理公式,掌握推理公式的不同证明方法;理解基本的推理规则,掌握使用推理规则进行推理演算的方法U5)重点解决使用谓词逻辑描述自然语句的表达问题,能够熟练的将些自然语句进行形式化描述6)理解谓词逻辑公式等值的概念,掌握否定型等值式的不同形式及其证明方法7)熟悉谓词逻辑的基本推理公式,能够给出解释性的证明和其它推理公式正确性的判断;8)理解谓词逻辑有关量词的四条推理规则,掌握使用推理规则进行推理演算的方法;命题逻辑命题逻辑也称命题演算,或语句逻辑。它研究以命题为基本单位构成的前提和结论之间的可推导关系,研究什么是命题?如何表示命题?如何由一组前提推导一些结论?命题逻辑的特征在研究逻辑的形式时,我们把一个命题只分析到其中所含的命题成份为止,不再分析下去。不把一个简单命题再分析为非命题的集合,不把谓词和量词等非命题成份分析出来命题的分类具有确切真值的陈述白称为命题1)明年国庆节是晴天2)地球外的星球上也有人3)1+1=104)x+y>0U一般来说,命题可分两种类型:1)原子命题(简单命题):不能再分解为更为简单命题的命题。2)复合命题:可以分解为更为简单命题的命题。而且这些简单命题之间是通过如“或者”、“并且”、不如果...则当且仅当”等这样的关联词和标点符号复合而构成一个复合命题命题联结词与非:P1Q=1(P∧Q)联结词记号记法读法或非:PQ=1(PVQ)排斥或异或:PQ=1(P分Q否定非A∧-gVηP∧Q合取∧AAA合取B蕴含否定:PAQ=1(P→Q联结词连接的是两个命题真析取AV叫A析取B值之间的联结,而不是命题内容之间的连接,因此复合蕴涵→A→A蕴涵B命题的真值只取决于构成他们的各原子命题的真值,而与它们的内容、含义无关等价叫A等价于B与联结次所连接的两原子命题之间是否有关系无关;些重要的全功能联结词集合1){-,V},{-,∧}可以构成功能联结词集合。使用上述全功能联结词集合表达的命题公式类的系统常称为B0O1e代数系统2)也可构成全功能联结词集合。该全功能联结词集合在研究逻辑系统的演绎与推理,以及在程序系统的研究中经常遇到3){↑},{↓}是全功能联结词集合。在大规模集成电路中有广泛的应用单个命题变元和命题常元叫原子公式定义(命题公式)简称公式1.单个原子公式本身是一个命题公式;2.如P是公式,则(P)也是命题公式U3.如P,Q是公式,则P∧Q)、(PVQ)、(P→Q)、(P(>Q)也是命题公式;4.命题公式仅由有限步使用规则1-3后产生的结果。该公式常用符号G、H、…等表示。公式G1称为永真公式(重言式),如果在它的所有解释之下都为“真叨。设A:A(P1,P2,…,Pn),B:B(P1,P2,,Pn)是两个命题公式,