1、第二篇 集合论集合论初步 二元关系 函数第三章 集合论初步主要介绍如下内容： 集合的基本概念及表示方法 集合间的关系 特殊集合 集合的运算 包含排斥原理 3-1 集合的基本概念1.集合与元素 集合：是由确定对象(客体)构成的合体。 这里所谓“确定”是指：论域内任何客体，要么属于这个集合，要么不属于这个集合，是唯一确定的。 集合一般用大写的英文字母表示。 元素：集合中的对象，称之为元素。 ：表示元素与集合的属于关系。例如，N表示自然数集合，2N， 而1.5不属于N，写成(1.5N), 或写成 1.5N。2. 有限集合与无限集合 这里对有限集合与无限集合只给出朴素的定义，以后再给出严格的形式定义。
2、 有限集合：元素个数是有限个的集合。 如果A是有限集合，用|A|表示A中元素个数。例如，A=1,2,3, 则|A|=3。 无限集合：元素个数是无限个的集合。 对无限集合 大小的讨论，以后进行。3.集合的表示方法 列举法：将集合中的元素一一列出，写在大括号内。 例如，N=1,2,3,4, A=a,b,c,d 描述法：用命题或谓词公式描述元素的属性。 例如，B=x| x是偶数 C=x|x是实数且2x5 一般地，A=x|P(x), 其中P(x)是谓词公式，如果论域内客体a使得P(a)为真，则aA，否则aA。4.几点说明 集合中的元素必须是不同的，可以区分的，而它们之间的次序是无关紧要的。例如 A=a
3、,b,c，B=c,b,a，则 A=B。 对集合中的元素无任何限制，例如令 A=人，石头，1， B, B=, 本书中常用的几个集合符号的约定： N：自然数集合，I：整数集合，R：实数集合， Q：有理数集合。 集合中的元素也可以是集合，下面的集合的含义不同： a： 张书记 a: 党支部(只有一个书记) a： 党委(只有一个支部) 3-2 集合间的关系包含 相等 =真包含一、包含关系(子集) 定义：A、B是集合，如果A中元素都是B中元素，则称 B包含A，或 A包含于B，也称A是B的子集。记作AB。 例如：N是自然数集合， R是实数集合， 则 NR 谓词定义： ABx(xAxB)AB文氏图性质： 有自
4、反性，对任何集合 A，均有 AA。 有传递性，对任何集合 A、B、C，若有 AB 且 BC ，则有 AC。 有反对称性，对任何集合 A、B，若有 AB且 BA ，则有 A=B。二、相等关系定义：A、B是集合，如果它们的元素完全相同，则称A与B相等。记作A=B。 定理：A=B，当且仅当AB 且 BA。谓词定义：A=BABBAx(xAxB)x(xBxA)x(xAxB)(xBxA)x(xAxB) 性质：有自反性，对任何集合 A，均有A=A。有传递性，对任何集合 A、B、C，如果 A=B 且 B=C ，则 A=C。有对称性，对任何集合A、B，如果A=B， 则 B=A。三、真包含关系(真子集) 定义：A
5、、B是集合，如果AB且AB，则称B真包含A，A真包含于B，也称A是B的真子集。记作AB。谓词定义：ABA BABx(xAxB)x(xAxB)x(xAxB) (x(xAxB)x(xBxA)(x(xAxB) x(xBxA) (x(xAxB) x(xBxA) x(xAxB) x(xBxA)性质： 有传递性，对任何集合A、B、C，如果 AB 且 BC，则 AC。练习题：设A=a,a,a,b,a,b,c 判断下面命题的真值。 aA (a A) cA aa,b,c aA a,ba,b,c a,bA a,ba,b,c ca,b,c (cA)(a)3-3 特殊集合全集 E空集合 一、全集 E 定义：包含所讨论
6、的所有集合的集合，称之为全集，记作 E。 实际上，是论域。 由于讨论的问题不同，全集也不同。所以全集不唯一。若讨论数，可以把实数集看成全集。若讨论人，可以把人类看成全集。E全集文氏图 由于论域内任何客体 x 都属于 E， 所以 xE 为永真式。 用永真式定义全集 E。 E=x| P(x)P(x)性质：对于任何集合A，都有AE。二、空集 定义：没有元素的集合，称之为空集，记作。 因为在论域内，客体 x 是一个矛盾式，所以要用一个矛盾式去定义 。 =x| P(x)P(x)性质： 1. 对于如何集合A，都有A。 因为x(xxA)为永真式，所以A。 2. 空集是唯一的。证明：假设有两个空集1 、2 ，
7、则 因为是1空集，则由性质1得 1 2 。 因为是2空集，则由性质1得 2 1 。 所以1=2 。3-4 集合的运算求幂集合交运算 并运算 差运算 -补运算 对称差运算 一. 集合的幂集定义：A 是集合，由 A 的所有子集构成的集合，称之为 A 的幂集。记作 P (A) 或 2A。 P (A)=B| BA例如： A= P(A)= A= a， P(A)= ,a A= a,b ， P(A)= ,a,b,a,b A= a,b,c P(A)= ,a,b,c,a,b,a,c,b,c,a,b,c Cn2Cn0Cn1CnnCn2Cn0Cn1Cnnxn-1y xn-2y2xnynCn2Cn0Cn1Cnn性质：
8、1.给定有限集合A，如果|A|=n，则|P(A)|=2n。证明：因为有n个元素，故P(A)中元素个数为而(x+y)n=令 x=y=1 得 2n=所以 |P (A)|= 2n |2A|= 2|A|= 2n练习 P86 (7) 设A=，P(A)= ,若不熟练，可将,中的元素分别看成=a ,=b, 于是,=a,bB=P(P(A)=P(a,b)=, a, b, a,b然后再将a,b代回即可B=P(P(A)=P(,)=, , ,判断下列命题真值：a) B Bb) B B c) B Ba)、b)、c)中命题均为真。二. 交运算定义：令A、B是集合，由既属于 A，也属于 B 的元素构成的集合，称之为 A 与
9、 B 的交集，记作 AB。例如A=1,2,3，B=2,3,4， AB=2,3谓词定义：AB=x|xAxBxAB xAxB如果 AB=，则称 A 与 B 不相交。ABAB性质：幂等律 对任何集合 A，有 AA=A。交换律 对任何集合 A、B，有 AB=BA。结合律 对任何集合 A、B、C，有 (AB)C=A(BC)。同一律 对任何集合 A，有 AE=A。零律 对任何集合 A，有 A=。定理： AB AB=A。证明：AB=A x(xAB xA)x(xAB xA)(xA xAB)x(xABxA)(xAxAB)x(xAxB)xA) (xA(xAxB)x(xAxB)xA) (xA(xAxB)x(T(T
10、( xA xB)x( xA xB)x(xAxB) AB二.并运算定义：A、B是集合，由或属于A，或属于B的元素构成的集合，称之为A与B的并集，记作 AB。例如A=1,2,3，B=2,3,4，AB=1,2,3,4谓词定义：AB =x|xAxBxAB xAxBABAB性质：幂等律 对任何集合 A，有 AA=A。交换律 对任何集合 A、B，有 AB=BA。 结合律 对任何集合 A、B、C，有 (AB)C=A(BC)。同一律 对任何集合 A，有 A=A。零律 对任何集合 A，有 AE =E 。分配律 对任何集合 A、B、C，有 A(BC) =(AB)(AC)。 A(BC) =(AB)(AC)。吸收律
11、对任何集合 A、B，有 A(AB)=A A(AB) =A。证明： A(AB) = (AE)(AB) (同一) = A(EB) (分配) = AE=A (零律) (同一) 定理 AB AB=B。同学自己证明四. 差运算 - (相对补集)定义：A、B是集合，由属于 A，而不属于 B 的元素构成的集合，称之为 A 与 B 的差集，或B 对 A 的相对补集，记作 A-B。例如：A=1,2,3，B=2,3,4 A-B=1谓词定义：A-B =x|xAx BxA-B xAxBABA-B性质： 设 A、B、C是任意集合，则 A-=A -A= A-A= A-BA (A-B)-C=(A-C)-(B-C)（没有结合
12、律） 对-满足分配率 A(B-C) = (AB)-(AC)证明：对任意x， x(AB)-(AC) x(AB)x(AC) (xAxB)(xAxC) (xAxBxA)(xAxBxC) xA(xBxC) xAxB-C xA(B-C) 所以 A(B-C)=(AB)-(AC) 因为 xA xB于是 xA xB T 所以 A = B 但对 - 不满足分配率反例： A(A-B)=A 而 (AA)-(AB)=所以并对差不满足交换律。自然联想到 对及是否满足分配率？有如下公式： A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C)注意：这不是分配律定理：AB A-B=证明： A-B= x(xA
13、-B x) x(xA-B F )x( x A-B ) （P F P）x(xA xB)x( xA xB)x(xAxB) AB五. 绝对补集 定义：A 是集合，由不属于 A 的元素构成的集合，称之为 A 的绝对补集，记作 A。 实际上 A=E-A。例如：E=1,2,3,4A=2,3，A=1,4谓词定义： A =E-A=x|xEx A = x|x A xA xAAAE性质：设A、B、C 是任意集合，则 E= =E (A)=A AA= AA=E A-B=AB (AB)=AB (AB)=AB 证明：对任意元素x， x (AB) xAB (xAxB) xAxB xAxB x AB 所以 (AB)=AB 定
14、理1 AB BA证明： AB x(xAxB) x(xBxA) x(xBxA) BA定理2 A=B 当且仅当AB=E且AB=证明： AB=EAB=x(xABxE) (PTP) x(xABx) (PFP)x(xABT)x(xABF)x(xAB(xAB)x(xAxB)(xAxB)x(xAxB)(xAxB)x(xAxB)(xBxA)x(xAxB)(xBxA)x(xAxB) A=B六、对称差 定义：A、B是集合，由属于A而不属于B，或者属于B而不属于A的元素构成的集合，称之为A与B的对称差，记作AB。例如A=1,2,3 B=2,3,4 AB=1,4谓词定义： AB=(A-B)(B-A)=x|(xAxB)
15、(xBxA) AB=(AB)-(AB) ABABE证明：(AB)-(AB) = (A-B)(B-A)证明： (AB)-(AB)= (AB)(AB)= (AB)(AB)=(AA)(AB)(BA)(BB)= (AB)(BA)= (A-B)(B-A)性质：交换律 对任何集合 A、B，有 AB=BA。结合律 对任何集合 A、B、C，有 (AB)C=A(BC)。 同一律 对任何集合 A，有 A=A。 对任何集合A，有 AA=。 对可分配 A(BC)=(AB)(AC)证明： (AB) (AC)= (AB)(AC) - (AB)(AC)= (A(BC) - (ABC)= A(BC) - (BC) (对-分配
16、)= A(BC)集合论初步作业86页： (4)、 (5)、(6) 、(7)94页：（2） c)、d) 用数理逻辑的方法证明（4） iff 的 含义是当且仅当 （5）、（6）、（7）、（9）证明： A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C)证明： AB AB=B。*3-5 包含排斥原理这节主要解决集合的计数问题。例：有A，B两个商店，A店经营1000种商品，B店经营1200种商品，其中有100种商品两个商店都经营，问两个商店共经营多少种商品？显然 |AB|=|A|+|B|-|AB|如果有A,B,C三个有限集合，则|ABC|=|AB|+|C|-|(AB)C|=|A|+|
17、B|-|AB|+|C|-|(AC)(BC)|=|A|+|B|-|AB|+|C|-(|AC|+|BC|-|ABC|)=|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC| ABABAB一般地，有n个有限集合A1, A2 ,., An, 则例1 某个研究所有170名职工，其中120人会英语，80人会法语，60人会日语，50人会英语和法语，25人会英语和日语，30人会法语和日语，10人会英语、日语和法语。问有多少人不会这三种语言？令U为全集，E、F、J分别为会英语、法语和日语人的集合。|U|=170|E|=120 |F|=80 |J|=60 |EF|=50 |EJ|=25 |FJ|=30
18、 |EFJ|=10|EFJ|=|E|+|F|+|J|-|EF|-|EJ|-|FJ|+|EFJ| = 120806050253010165|U-(EFJ)|=170-165=5 即有5人不会这三种语言。EFJ10U例2.求1到1000之间不能被5、6、8整除的数的个数。解.设全集 Ex| x是1到1000的整数 |E|=1000 A5、 A6、 A8是E的子集并分别表示可被5、6、8整除的数的集合。x 表示小于或等于x的最大整数。LCM(x,y):表示x,y两个数的最小公倍数。(Least Common Multiple )不能被5、6、8整除的数的集合为(A5A6A8)|(A5A6A8)|=|
19、E|A5A6A8|=|E|(|A5|+|A6|+|A8|A5A6|A5A8|A6A8 |+|A5A6A8|)1000(200+166+1253325418)600作业：99页 （1）、（2） 本章小结： 1.掌握集合间三种关系的定义、谓词定义、 证明方法。 2.掌握二个特殊集合。 3.掌握集合的六种运算定义、计算方法、 性质。 *4.会用包含排斥原理解决集合计数问题. 第三章习题课第86页(4)判断下面命题的真值：a)如果AB，BC ，则 A C。 T证明：因为BC ， AB，所以A C。b)如果AB，BC，则 AC 。 F举反例A=1 B=1 C=1,2满足AB, BC ，但是不满足AC (
20、1A 但1C )。c)如果AB，BC，则 AC。 F举反例A=1 B=1,2 C=1,2满足AB, BC ，但是AC 。d)如果AB，BC，则 AC。 F举反例A=1 B=1,2 C=1,2满足AB, BC ，但是不满足AC 。e)、f) 的真值都为F，类似举反例。(7)设A=， B=P(P(A)B=P(P(A)=P(,)=, , ,a) B B b) B B c) B Ba)、b)、c)中命题均为真。第94页(3)全集=N=1,2,3,4,. 解. A=1,2,7,8 B=1,2,3,4,5,6,7C=3,6,9,12,15,18,21,24,27,30D=2,4,8,16,32,64 A=
21、3,4,5,6,9,10,11,12.c) B-(AC)=1,2,3,4,5,6,7-1,2,3,6,7,8,9,12,15,18,21,24,27,30=4,5d) (AB)D=3,4,5,6D=2,3,4,5,6,8,16,32,64(4) 证明 (AB)C=A(BC) 当且仅当 CA.证明：充分性 已知CA (AB)C=(AC)(BC) =A(BC) (因 CA ，所以 AC=A)必要性 已知(AB)C=A(BC) 任取 xC x(AB)C xA(BC) xA所以 CA.(5)b)证明 (A-B)-C=(A-C)-B方法1: 对任意元素x, x(A-B)-C x(A-B)xC (xAxB
22、)xC(xAxC)xB x(A-C)xB x(A-C)-B 所以(A-B)-C=(A-C)-B方法2 (A-B)-C=(AB)C =(AC)B =(A-C)-B(6) 计算= = , -=, ,-= ,-= (7) 证明各式彼此等价。c) AB=E, AB, BA.证明： AB=E x(xAB xE) x(xAB) (因xE 为T) (PTP)x(xAxB) x(xAxB) x(xAxB) AB AB x(xA xB) x(xAxB) x(xBxA) x(xBxA) BA所以AB=E AB BA.(9) .在什么条件下，下面命题为真？a) (A-B)(A-C)=A解：(A-B)(A-C) =
23、(AB)(AC) = A(BC) = A(BC) = A-(BC) = A-(ABC) = A 所以满足此式的充要条件是：ABC= b) (A-B)(A-C)=解：(A-B)(A-C)= A-(BC)= 由 AB A-B= 所以满足此式的充要条件是：A BCc) (A-B)(A-C)=解：(A-B)(A-C) = (AB)(AC) = A(BC) = A(BC) = A-(BC) = 所以满足此式的充要条件是: A BCd) (A-B)(A-C)=解：因为 当且仅当 A=B，才有AB=（若A=B，显然AB=；若AB=(A-B)(B-A)=，必有A-B =且 B-A =,于是有AB且 BA，即A
24、=B。）所以满足此式的充要条件是: A-B=A-C补充题1.A,B是有限集合, P(A)表示A的幂集,已知|A|=3,|P(B)|=64, |P(AB)|=256, 则|B|=( ),|AB|=( ), |A-B|=( ), |AB|=( )。解: 由|P(B)|=64=26，得 |B|=6由|P(AB)|=25628，得|AB|=8由包含排斥原理|AB|=|A|+|B|AB|于是 83+6|AB| ，所以 |AB|1|A-B|=|A|AB|=31=2|AB|=|AB|AB|=81=72.设F表示一年级大学生的集合,S表示二年级大学生的集合,M表示数学专业学生的集合,C表示计算机专业学生的集合,D表示听离散数学课学生的集合,G表示星期六晚上参加音乐会的学生的集合,H表示星期六晚上很迟才睡觉的学生集合,则将下面各个句子所对应的集合表达式分别写在句子后面的括号内:(1)所有计算机专业二年级的学生在学离散数学课。 ( ).(2)这些且只有这些学离散数学课的学生或者星期六晚上去听音乐会的学生在星期六晚上很晚才睡觉。 ( )(3) 星期六晚上的音乐会只有大学一、二年级的学生参加。 ( )(4)除去数学专业和计算机专业以外的二年级的学生都去参加星期六晚上的音乐会.( )CSDDG=HG F S(MC)SG
