离散数学准备知识.doc

第0章 准备知识 0.1集合、命题、谓词和运算 0.1.1集合 集合是由确定的、互相区别的、并作整体识别的一些对象组成的总体。对象 人们还把所有成员均为集合的集合称作集合族(collections of sets)。 0.1.2命题与谓词 逻辑学把“对事物作出确定判断的陈述句”称作命题，当判断正确或符合客观实际时，称该命题真(true)，否则称该命题假(false)。“真、假”常被称为命题的真值。 个断言常常涉及若干对象以及它们的性质或关系，前者是断言的“主语”，后者是断言的“谓语”。因此，逻辑学把断言中关于对象基本性质或相互关系的语言成分称为谓词。谓词通常用带有空位的大写拉丁字母（或字母串）来表示，例如，用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)，常称为谓词填式，表示:对象序列t1,…,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,…｝ 二、描述法；表示一个集合A时，将A中元素的特征性用一个谓词来描述，其表示形式如 A =｛x ( P(x)｝或 A =｛x：P(x)｝ B =｛x1,x2,…,xn( Q(x1,x2,…,xn)｝或 B =｛x1,x2,…,xn：Q(x1,x2,…,xn)｝ 其中x1,x2,…,xn表示n个对象的序列x1,…,xn。 集合理论约定，每一个谓词确定一个集合。它被称为概括原理(abstract principle)。 有些常用的集合习惯用特定字母符号来表示。如：N表示所有自然数组成的集合，I表示所有整数组成的集合，Nn表示前n个自然数的集合等。常见的还有，Q表示所有有理数组成的集合，R表示所有实数组成的集合，C表示所有复数组成的集合，Q+表示所有正有理数组成的集合，R(表示所有负实数组成的集合等等。 关于集合的下列概念无疑是十分基础的。 定义0.1 没有任何元素的特定集合称为空集，记为(，即(＝{}={x( P(x)恒假}；由研究对象全体组成的集合称为全集，记为U={x( P(x)恒真}。 定义0.2 空集和只含有有限多个元素的集合称为有限集(finite sets)，否则称为无限集(infinite sets)。有限集合中成员的个数称为集合的基数(cardinatity)（无限集合的成员个数，即无限集合的基数概念将在以后严格定义）。集合A的基数表示为 (A (。 三、归纳法：集合的归纳法表示（也称归纳定义induction definition）就是用以下三个条款来确定集合： （1）基础条款：规定待定义集合以某些对象为其成员，集合的其它元素可以从它们出发逐步确定。 （2）归纳条款：规定由已确定的集合成员去进一步确定其它成员的规则。于是，可以从基础条款确认的成员出发，反复运用这些规则来确认待定义集合的所有成员。 （3）终极条款：规定待定义集合只含有（l），（2）条款所确定的成员。 条款（l），（2）又称归纳表示或归纳定义的完备性条款，它们必须保证毫无遗漏地产生出待定义集合的全部成员；条款（3）又称归纳定义的纯粹性条款，它保证整个定义过程所规定的集合只包括满足要求的那些对象。 0.1.4 外延性原理与子集合 除了正规原理、概括原理，集合理论的另一个重要约定是外延性原理，用于规定集合相等的意义是描述集合本质的核心原理。 外延性原理(extensionality principle)：集合A和集合B相等，当且仅当它们具有相同的元素。也就是说，对任意集合A,B，A=B当且仅当属于A的元素也属于B；反之,属于B