离散数学第四章

离散数学第四章Tag内容描述：<p>1、1 离散数学 Discrete Mathematics 汪荣贵贵 教授 合肥工业业大学软软件学院专专用课课件 2010.05 Chapter 4Chapter 4 Sets and Relations bBijk, 则 j=1; cBijk, 则 k=1;否 则为0。 如a,b,c,d 子集 B9 = B1001 =a,d a,c,d= B1011 = B11 【example】集合0，1，2的幂集合是什么？ Solution： 幂集合P(0,1,2)是0，1，2所有子集的集合。因此 P(0,1,2)=,0,1,2,0,1,0,2,1,2,0,1,2 注意：空集和0，1，2自身都是这个子集集合的成员。 【example】空集的幂集合是什么？集合的幂集合是什么？ Solution： 空集只有一个子集，这就是它自己。因此 P()= 。</p><p>2、1 离散数学 Discrete Mathematics 汪荣贵贵 教授 合肥工业业大学软软件学院专专用课课件 2010.03 Date 1 第二章第二章 算法基础算法基础 Date 2 2.1 Algorithms算法 2.2 Complexity of Algorithms算法的复杂性 2.3 The Integers and Division整数和除法 2.4 Integers and Algorithm整数和算法 2.5 Applications of Number Theory数论的应用 2.6 Matrices矩阵 2.7 Recursion 递归 Date 13 The Euclidean Of Algorithms 欧几里德算法 Representations Of Integers 整数表示 Algorithms For Integers Operations 整数运算算法 &整数和除法 Da。</p><p>3、二元关系和函数,第四章,2,第4章 二元关系与函数,4.1 集合的笛卡儿积与二元关系 4.2 关系的运算 4.3 关系的性质 4.4 关系的闭包 4.5 等价关系和偏序关系 4.6 函数的定义和性质 4.7 函数的复合和反函数,3,4.1 集合的笛卡儿积和二元关系,有序对 笛卡儿积及其性质 二元关系的定义 二元关系的表示,4,有序对的性质： 1） 有序性 （当x y时） 2） 与 相等的充分必要条件是 = x=u y=v,例4.1 = ，求 x, y. 解 3y 4 = 2, x+5 = y y = 2, x = 3,4.1 二元关系的概念,1. 有序对/序偶：由两个元素x和y按一定顺序 排成二元组，记作： 。其中x称作第 一个。</p><p>4、第四章 谓词演算的推理理论,4.1 谓词演算的永真推理系统 4.2谓词演算的假设推理系统 4.3谓词演算的归结推理系统 4.3.1 置换 4.2.2 归结反演系统 4.3.3 霍恩子句逻辑程序,4.3 谓词演算的归结推理系统,问题：从公式集S出发，证明目标公式T。 在归结系统中: 首先否定目标公式， 然后将这个公式加到公式集S中， 再将该公式化成子句集， 若能归结成空子句(用表示)， 则认为证明了该公式T。,引例(p45),设有语句串及它的符号表示如下： (1)无论谁能读就有知识；x(R(x) L(x) (2)所有的海豚均没有知识；x(H(x) L(x) (3)有些海豚有智慧。x(H(x)I(x) 。</p><p>5、第四章 谓词演算的推理理论,4.1 谓词演算的永真推理系统 4.2谓词演算的假设推理系统 4.2.1 假设推理系统的组成及证明方法 4.2.2 推理过程的推导过程 4.3谓词演算的归结推理系统,一、假设推理系统的组成,(附加前提证明法) 如果，AB， 则(AB)， 也可表示为： 如果A1，A2，An，AB， 则A1，A2，An(AB)。 依次类推可得定理： (A1(A2(An(AB),(2) 存在推理定理,如果有 A1，An，xP(x)，P(e)Q， 其中Q中不含有自由的e，且在推理过程中不对假设中的自由变元和额外假设中的自由变元实施全规则和存在规则，则有： A1，A2，An，xP(x)Q,去“存在量词”,。</p><p>6、2020/7/5,离 散 数 学,1,2020/7/5,离 散 数 学,2,第一部分,数理逻辑,第四章 一阶逻辑基本概念,2020/7/5,离 散 数 学,3,复习命题演算,命题演算形式系统: 语法: 语义: 可靠性: 凡是推出来的都是正确的. 完全性: 凡是正确的都可以推出来.,2020/7/5,离 散 数 学,4,问题的提出,命题演算不能表达所有正确的推理. 例: 所有实数的平方都是非负的。</p><p>7、第四章二元关系,离散数学陈志奎主编人民邮电出版社,前言,在日常生活中，我们都十分熟悉关系这个词的含义，例如夫妻关系，同事关系，上下级关系，位置关系等。在数学中，关系可表达集合中元素间的联系。在计算机科学中，关系的概念也具有重要意义。例如，数字计算机的逻辑设计和时序设计中，都应用了等价关系和相容关系的概念。在编译程序设计、讯息检索、数据结构等领域中，关系的概。</p>