离散数学0638673.ppt

下面我们学习本章的最后一个知识点： 2.5 推理理论 一、推理的含义 二、推理定律 三、推理规则 举例 本节习题 第二篇 集合论 第三章 集合 主要知识点： 首先学习第一个知识点： 3.1 集合的基本概念及其表示法 一、集合的概念 1、集合的定义 2、集合的元素 3、集合的分类 二、集合的表示方法 1、列举法 2、描述法 3、归纳定义法 举例 4、多重集 三、集合的包含与相等 1、集合的包含关系 2、集合的相等 3、集合的真包含关系 4、全集及相关概念 本节习题按某一次序列出集合的全部或部分元素，并用一对括号括起来。通常用部分列举法。 例3.1.4用谓词描述出集合元素的特征，其形式为： 例3.1.5归纳定义法通常包括以下三个步骤： （1）基本步：S0 非空且 S0 中的任意元素均是 A 的元素； （2）归纳步：给出一组规则，从 A 的元素出发，依据这些规则所得到的仍是 A 的元素； （3）极小化：若 S 的任意元素均是 A 的元素，并且 S 满足 (1) 和 (2)，则 S 与A 含有相同的元素。 P.57，例3.1.6 P.57，例3.1.7 P.57，例3.1.8 P.57，例3.1.9把元素可以多次出现的集合称为多重集，并把某元素出现的次数称为该元素的重复数。 定义3.1.2 设 A，B 是集合，若，则称 A 是 B 的子集，也称 A 包含于 B，或者 B 包含 A，记为。 例3.1.10 定义3.1.3 设 A，B 是集合，若，则称 A 与 B 相等，记为。否则称A 与 B 不等，记为。 例3.1.11 例3.1.12 定义3.1.4 设 A，B 是集合，若，则称 A 是 B 真子集，也称 A 真包含于 B，或者 B 真包含 A，记为。在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集，用U 表示。全集是一个相对的概念。 * * 1、命题的符号化 2、合式公式 3、永真公式 4、范式 5、推理理论 5、推理理论在一阶逻辑中，从前提 A1, A2, …, An 出发推结论 B 的推理的形式结构，依然采用如下的蕴含式形式： 若上式为永真式，则称推理正确；否则称推理不正确。在一阶逻辑中，称永真蕴含式为推理定律。若一个推理的形式结构正好是某条推理定律，则这个推理显然是正确的。有哪些推理定律呢？ 第一组 命题逻辑推理定律的代换实例。 例如： 化简律 附加律 第二组 由基本等值式生成的推理定律。2.3节中给出的等值式中的每个等值式可生成两个推理定律。例如：由 可生成和 第三组 已有的永真蕴含式。2.3节中给出的一些永真蕴含式。例如：在一阶逻辑的推理中，某些前提和结论可能受到量词的限制，为了能使用命题逻辑中的一些等价式和永真蕴含式，必须在推理过程中有消去和添加量词的规则，以便借用命题逻辑的推理方法来完成一阶逻辑的推理。约定：用 A(x) 表示 x 是 A 中的自由变元，那么 A(y) 表示用 y 去取代 A(x) 中 x 的所有自由出现所得到的结果。例如： 对于 则 1、全称指定规则（US） 使用条件： （1）在第一式中，取代 x 的 y 应为任意的不在 A(x) 中约束出现的个体变元； （2）在第二式中，c 为任意的不在 A(x) 中出现过的个体常元； （3）用 y 或 c 去取代 A(x) 中的自由出现的 x 时，一定要在 x 自由出现的一切地方进行取代。 或 例2.5.1 从前提 推出 的过程如下： 前提 (1)，US 但 是错的。 比如： 2、存在推广规则（EG） 使用条件： （1）c 是特定的个体常元； （2）取代 c 的 x 不能在 A(c) 中出现。 前提 (1)，EG 例2.5.2 下列推理过程是错误的： 3、存在指定规则（ES） 使用条件： （1）c 是使 A 为真的特定的个体常元； （2）c 不在 A(x) 中或其前面的推导中出现； （3）若 A(x) 中的除自由出现的 x 外，还有其它自由出现的个体变元，则此规则不能使用。 例2.5.3 的推导过程 前提 (1)，ES 前提 (3)，ES (2)、(4)，合取引入 (5)，EG 但 是错的。 例2.5.4 下列推导过程是错的： 前提 (1)，US (2)，ES (3)，EG 4、全称推广规则（UG） 上式的使用条件是： （1）无论 A(y) 中自由出现的个体变元 y 取何值， A(y) 均为真； （2）取代自由出现的 y 的 x 不能在 A(y) 中出现。 例2.5.5 下列推导过程是错的： 前提 (1)，ES (2)，UG╳ 不是任意取值 例2.5.6 考查下列推理过程： 前提 (1)，US (2)，ES