绪论命题逻辑.ppt

什么是离散数学 相对连续数学而言 连续数学：以连续函数为研究对象，如微积分，实变函数与复变函数，几何与拓扑。 研究离散量的结构及其相互关系的学科 离散量：逻辑变量，集合与关系，群、环等代数结构，图等。 课 程 说 明 离散数学为计算机专业的后继课程如数据结构、操作系统、数据库、编译原理、网络和算法设计等课程提供必要的数学基础。 为学生今后从事计算机科学和技术各方面的工作提供有力的工具。 离散数学是现代数学的一个重要分支，通过该课程的学习可以提高学生的抽象思维、严格推理以及综合归纳分析能力，培养出高素质的人才。 独立思考，大量练习。仅靠熟读教材并不能将书本上的知识变成你自己的知识，在熟读教材的基础上，必须通过大量练习，独立思考来真正获取知识。 注重抽象思维能力的培养。数学与其他学科相比较具有较高的抽象性，而离散数学的抽象性特点更为显著，它有着大量抽象的概念和抽象的推理，要学好这门课程必须具有较好的抽象思维能力，才能深入地掌握课程内容。 第一部分 数理逻辑。包括命题逻辑、谓词逻辑（教材的第一、二章） 第二部分 集合论。包括集合、关系和函数。（教材的第三、四章） 第三部分 代数系统。包括代数系统的一般概念，几类典型的代数系统，如办群、群、环、域、格与布尔代数。（教材的第五、六章） 第四部分 图论。包括图的基本概念，有向图、无向图。（教材的第七章） 第一篇 数理逻辑 用数学方法来研究推理的规律称为数理逻辑。这里所指的数学方法，就是引进一套符号体系的方法，所以数理逻辑又称为符号逻辑，它是从量的角度来研究思维规律的学科。 命题逻辑 谓词逻辑 第一章 命题逻辑 命题及其表示法 联结词 命题公式与翻译 真值表与等价式 重言式与蕴含式 对偶与范式 推理理论 1-1 命题及其表示法 判断：通过概念对事物是否具有某种属性进行肯 定（真）或否定（假）的回答。 1-1.1 命题类型 命题有两种类型： 原子命题：不能分解为更简单的陈述语句的命题。 复合命题：由联结词，标点符号和原子命题复合构成的命题。 所有这些命题，都应具有确定的真值。 联结词的例子，如：“并且”、“或者”、“如果…则…”等。 1-1.4 命题与命题变元的区别 命题变元和命题是不相同的。 命题是具体的，是具有真值的陈述句，有确定的真值；而命题变元是抽象的，只有将某个具体的命题代入时，才有确定的真值。 1-2 联 结 词 否定示例 例： 设 P：成都是一个大城市； Q：每个自然数都是偶数。 1-2.4 异或 以下是几点值得注意的地方： 从条件的定义可以看到，联结词?与汉语中的“如果，则”相对应，但又有区别。 自然语言中“如果，就”前提（前件）与结论（后件）之间常有因果关系；而“?”不涉及具体内容。 例：设 P：2＋2＝5。 Q：太阳从东边升起。 则 P?Q：如果2＋2＝5，则太阳从东边升起。 示例 对下面各命题符号化(设P：天下雨 Q：我骑自行车上班) 只要不下雨，我就骑自行车上班。 只有(仅当)不下雨，我才骑自行车上班。 除非下雨，否则我就骑自行车上班。 如果下雨，我就不骑自行车上班。 1-3 命题公式与翻译 1-3.2 联结词的运算优先级 规定联结词的运算优先次序为： ┒， ? ， ? ， → ， ? 1-4 真值表与等价公式 说明 有一类公式不论命题变元作何种指派，其真值永为真(假)，可把这类公式记为T(F)。 命题公式真值的取值数目，决定于命题变元的个数。一般来说，n个命题变元组成的命题公式共有2n种真值情况。 有些命题公式在命题变元的不同指派下，其对应的真值与另一个命题公式的真值完全相同。 1-5 命题公式的等价与蕴含式 先看下面几个定义与定理： 定义1-5.1 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为T，则称该命题公式为重言式或永真公式。 定义1-5.2 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为F，则称该命题公式为矛盾式或永假公式。 定义 若至少存在一种对组成命题的命题变元的真值指派，使该命题公式的真值为T，则该命题公式称为可满足式。 定理：n个命题变元共可组成 个不等价命题公式，其中矛盾式有1个，重言式有1个，可满足式有 －1个。 定理1-5.1 任何两个重言式的合取或析取，仍然是一个重言式。 证明: 设A和B为两个重言式，则不论A和B的分量指派任何真值，总有A为T，B为T，故A∧B ? T,A∨B ? T。 1-5.1 等价 定义：设A、B是两