资源描述：
《第0章 离散数学准备知识》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《离散数学教程》教案与习题解析理工学院段景辉第0章准备知识0.1集合、命题、谓词和运算0.1.1集合集合是由确定的、互相区别的、并作整体识别的一些对象组成的总体。通常用{¼}表示一个集合，其中¼是集合中的对象，对象间用逗号分开。人们还把所有成员均为集合的集合称作集合族(collectionsofsets)。0.1.2命题与谓词逻辑学把“对事物作出确定判断的陈述句”称作命题，当判断正确或符合客观实际时，称该命题真(true)，否则称该命题假(false)。“真、假”常被称为命题的真值。个断言常常涉及若干对象以及它们的性质或关系，前者是断言的“主语”，后者是断言的“谓语”。因此，逻辑学把断言中关于
2、对象基本性质或相互关系的语言成分称为谓词。谓词通常用带有空位的大写拉丁字母（或字母串）来表示，例如，用P()表示“¼小于等于零”，QR(,)表示“¼与¼的平方和等于1”，ADD(,,)表示“¼与¼的和等于¼”。为了增加可读性，可用变元去填满空位，例如，P(x)，QR(x,y)，ADD(x,y,z),读作“x满足性质P”，“x,y满足关系QR”，“x,y,z满足关系ADD”。含有n个空位（或变元）的谓词，称为n元谓词。当谓词的空位或变元处填以确定的对象后，便可判别其真假，即可得到一个命题。一般地，n元谓词P(x1,…,xn)填满对象后的表达式P(t1,…,tn)，常称为谓词填式，表示:对象序列t
3、1,…,tn满足n元谓词P(x1,…,xn)，或对象序列t1,…,tn具有性质P、或关系P。上文介绍的谓词，如P(x)，QR(x,y)，ADD(x,y,z)都是所谓前置表示形式。一些大家熟知的对象间的关系，把关系符号放在空位的中部，例如，x≤y，uÍv。它们也是谓词，只是使用关系符号中置的形式来表示。0.1.3集合的表示集合的表示方式主要有以下三种：列举法、描述法和归纳法。一、列举法：表示一个集合A时，可将A中元素一一列举在一个大括号中，或列出足够多的元素以反映A中成员的特征，其表示形如A＝｛a1,a2,…,an｝或A=｛a1,a2,a3,…｝二、描述法《离散数学教程》教案与习题解析理工学院段
4、景辉；表示一个集合A时，将A中元素的特征性用一个谓词来描述，其表示形式如A=｛x
5、P(x)｝或A=｛x：P(x)｝B=｛
6、Q(x1,x2,…,xn)｝或B=｛：Q(x1,x2,…,xn)｝其中表示n个对象的序列x1,…,xn。集合理论约定，每一个谓词确定一个集合。它被称为概括原理(abstractprinciple)。有些常用的集合习惯用特定字母符号来表示。如：N表示所有自然数组成的集合，I表示所有整数组成的集合，Nn表示前n个自然数的集合等。常见的还有，Q表示所有有理数组成的集合，R表示所有实数组成的集合，C表示所有复数
7、组成的集合，Q+表示所有正有理数组成的集合，R-表示所有负实数组成的集合等等。关于集合的下列概念无疑是十分基础的。定义0.1没有任何元素的特定集合称为空集，记为Æ，即Æ＝{}={x½P(x)恒假}；由研究对象全体组成的集合称为全集，记为U={x½P(x)恒真}。定义0.2空集和只含有有限多个元素的集合称为有限集(finitesets)，否则称为无限集(infinitesets)。有限集合中成员的个数称为集合的基数(cardinatity)（无限集合的成员个数，即无限集合的基数概念将在以后严格定义）。集合A的基数表示为
8、A
9、。三、归纳法：集合的归纳法表示（也称归纳定义inductiondefin
10、ition）就是用以下三个条款来确定集合：（1）基础条款：规定待定义集合以某些对象为其成员，集合的其它元素可以从它们出发逐步确定。（2）归纳条款：规定由已确定的集合成员去进一步确定其它成员的规则。于是，可以从基础条款确认的成员出发，反复运用这些规则来确认待定义集合的所有成员。（3）终极条款：规定待定义集合只含有（l），（2）条款所确定的成员。条款（l），（2）又称归纳表示或归纳定义的完备性条款，它们必须保证毫无遗漏地产生出待定义集合的全部成员；条款（3）又称归纳定义的纯粹性条款，它保证整个定义过程所规定的集合只包括满足要求的那些对象。0.1.4外延性原理与子集合除了正规原理、概括原理，集合理论
11、的另一个重要约定是外延性原理，用于规定集合相等的意义，是描述集合本质的核心原理。外延性原理(extensionality《离散数学教程》教案与习题解析理工学院段景辉principle)：集合A和集合B相等，当且仅当它们具有相同的元素。也就是说，对任意集合A,B，A=B当且仅当属于A的元素也属于B；反之,属于B的元素也属于A。定义1.3集合A称为集合B的子集合（或子集，subsets），如果A的每一
