第0章 离散数学准备知识

《离散数学教程》教案与习题解析 理工学院 段景辉 第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 =｛ Q(x1,x2,…,xn)｝或 B =｛：Q(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的元素也属于A。 定义1.3 集合A称为集合B的子集合（或子集，subsets），如果A的每一个元素都是B的元素，即，若元素x属于A，那么x也属于B。 关于子集关系我们有以下定理和定义。 定理0.1对任意集合A，B，A＝B当且仅当A  B且B  A 。特别地，对任意集合A，A  A 。 定理0.2 对任意集合A，AU。 定理0.3 设A，B，C为任意集合，若A  B , B  C，则A  C。 定理0.4 对任何集合A，  A。 定理0.5空集是唯一的。 定义0.4 如果AB且A  B，那么，集合A称为集合 B的真子集。“A是B的真子集”记为AB。 0.1.5 运算 定义0.5 分别称，为集合A上的一元、二元运算(operating)，如果，分别是对单元素和序偶的操作，并且对任意x,yA，其操作结果，记为(x)，xy，是集合A中唯一确定的成员。 定义0.6 设，为集合A上的二元运算， （1）如果对A中的任意元素x,y.z有x(yz)=(xy)z，那么称  运算满足结合律； （2）如果对A中的任意元素x,y.z有xy=yx，那么称  运算满足交换律； （3）如果对A中的任意元素x,y.z有x(yz)=(xy)( xz)，那么称  运算对  运算满足分配律， 定义0.7 设  为集合A上的二元运算，如果eA，且对任意元素xA有xe = ex = x，那么，称元素e为集合A的关于运算  的幺元(identity elements) 。 定义0.8 设  为集合A上的二元运算，如果oA，且对任意xA有xo＝ox＝o，那么，称元素o为集合A的关于运算  的零元(zero)。 定理0.6 设  为集合A上的二元运算，那么集合A的关于运算  的幺元是唯一的。 定理0.7 设  为集合A上的二元运算，那么集合A的关于运算  的零元是唯一的。 定义0.9 设  为集合A上的二元运算，e为幺元，x,y为A中元素，若xy＝yx＝e，那么称x(y)为y(x)的逆元(inverse elements)。x的逆元通常记为x1 。 定理0.8设  为集合A上的二元运算，e为幺元，且运算  满足结合律，那么当A中 《离散数学教程》教案与习题解析 理工学院 段景辉 元素x有逆元时，它的逆元是唯一的。

练习0.1 1、选择题 (1) 可称为集合的是（ ） A. 《水浒传》中第70页上汉字的全体。 B. 很大的数的全体。 C. 比复数1+i大的数的全体。 D. 接近于0的数的全体。 【答案】：A (2) 不能称为集合的是（ ） A. 大于1、小于60的整数的全体。 B. 比较小的正整数的全体。 C. 正三角形的全体。 D. 平面上到点(0,0)距离等于1的点的全体。 【答案】：B (3) 不空的集合是（ ） A. {x｜x2－1=0，且x∈R} B. {x∣x2＋9=0，且x∈R} C. {x｜x=x＋1，且x∈R} D. {x｜x2=－1，且x∈R} 【答案】：A (4) 下述论断中, 对任意集合A、B和C均正确的是（ ） A. 若A∈B，B⊆C，则A∈C B. 若A∈B，B⊆C，则A⊆C C. 若A⊆B，B∈C，则A∈C D. 若A⊆B，B∈C，则A⊆C 【答案】：A (5) 设P={x│(x+1) 2≤4}，Q={x│x2+16≥5x}，则下式中成立的是（ ） A. QP B. QP C. PQ D. PQ 【答案】：D (6) 下列各式中错误的是（ ） A. Ø ⊆ Ø B. Ø ∈Ø C. {Ø}{{Ø}} D. Ø ∈{Ø} 【答案】：B (7) 设S={{1},3,9,10},K={1,3,π},T={{1,3,π},1},下列各式中为真的是( ) A. {1} K B. 1  S C. {1} S D. {1} T 【答案】：C 《离散数学教程》教案与习题解析 理工学院 段景辉 (8) 在自然数集Ｎ上，下列哪种运算*满足结合律？( ) A．a*b=ab B. a*b=max{a,b} C. a*b=a+2b D. a*b=︱a-b︱ 【答案】：B

(9) 对自然数集Ｎ，下列哪种运算*不满足结合律？( ) A. a*b=a+b+3 B. a*b=min{a,b} C. a*b=a+2b D. a*b= max{a,b} 【答案】：C (10) Q为有理数集，Q上定义运算*为：a*b=a+b-ab，则Q 中*运算的幺元是（ ） A a; B b; C 1; D 0. 【答案】：D 2. 填空题 (1) 用列举法表示下列各集合: A={x|x2<50，x为正奇数}= ；

B={:,5,,pxxpqpqIq}= 。 【答案】：{1，3，5，7}；{1/4，2/3，3/2，4/1} 。 (2) 用列举法表示以下各集合： ① 100以下9的倍数所成集合为 ； ② 100以下12的倍数所成集合为 ； ③ 100以下9与12公倍数所成集合为 。 【答案】：①{9，18，27，36，45，54，63，72，81，90，99}；②{12，24，36，48，60，72，84，96}③{36，72}。 (3) 设E={a,b,c,d},则E的含有a的子集有 ；不含有a，含有b的子集有 。 【答案】：①{a,b,c},{a,b,d},{a,c,d},{a,b},{a,c},{a,d},{a},E；②{b,c,d},{b,c}, {b,d}, {b} (4) 设A={2，a，{3}，4},B={{a}，3，4，1},请在下列每对集合中间填入适当的符号（∈或者⊆）；{a} B；{a,4,{3}} A；{{a}}__B。 【答案】：①∈；②⊆;③⊆ (5) 集合A={a,b,c}上总共可定义的二元运算的个数为___。