离散数学 31集合概念表示法

离散数学集合的表示方法离散数学是指以一定的符号系统来表示数学概念和数学运算的学科，其中最基本的概念是集合。

集合是一组独立的元素的有序集，也可以说是一类物体的总称，它可以用简单的符号表示。

这种表示方法在数学研究和计算上起着重要作用。

本文着重介绍离散数学集合的表示方法。

首先，在离散数学中，所有的集合都可以用符号表示，通常用大写字母代表集合，如A、B、C等。

确定集合的方法通常有三种：①通过给出其元素的方式，如表示集合A={1,3,5,7,9}；②通过用公式表示法，如表示集合B={2n|n∈N，n≤5}；③通过用符号表示，如表示集合C={x|x∈A，x>3}。

此外，在离散数学中，还有一些特殊的集合概念，包括空集、自身的集合、全集以及基本集合。

空集是指不包含元素的集合，它有一个特殊的符号，即；自身的集合，即一个集合的元素全部不在其他集合中，如集合A={1,2,3}，则A∈A；全集是指包含所有元素的集合，标识符为G；基本集合是指包含元素的所有集合，标识符通常是N、Z、R等。

另外，集合运算也是离散数学中非常重要的概念，其中有一些重要的运算，如交集、并集、补集、差集等。

其定义和运算方法是：对于两个集合A={1,2,3}、B={2,4,6}，交集A∩B={2}，即A和B的交集，两个集合的公共元素；并集A∪B={1,2,3,4,6}，即A和B的并集，包含A和B全部元素；补集A′={4,6}，即在A中没有的元素；差集A-B={1,3}，即A中有，而B中没有的元素。

总之，离散数学集合的表示方法有大写字母表示、公式表示法和符号表示，以及特殊的集合概念如空集、自身的集合、全集以及基本集合，以及交集、并集、补集、差集等重要的集合运算。

它们为离散数学的理解和应用提供了基础，同时也为计算机科学技术的发展提供了条件和依据。

康托尔(Cantor)9 3.1 集合的基本概念集合、元素、子集、包含、集合相等、真子集、空集、幂集、全集9 3.2 集合的基本运算并集、交集、相对补集、绝对补集、对称差、文氏图、算律、9 3.3 集合中元素的计数基数、有(无)穷集、包含排斥原理3.1 集合的基本概念9把具有共同性质的一些东西，汇集成一个整体，就形成一个集合。

9由确定的相互区别的一些对象组成的整体称为集合。

9可确定的可分辨的事物构成的整体。

例：教室内的桌椅、图书馆的藏书、全国的高等学校、自然数的全体、直线上的点、26个英文字母3.1 集合的基本概念集合的元素(member或element)9集合内的对象或单元称为元素。

9集合通常用大写英文字母标记。

例如，N代表自然数集合（包括0），Z代表整数集合，Q代表有理数集合，R代表实数集合，C代表复数集合。

趣味思考9任意自然数都可以表示为两个自然数的平方差吗?9请严谨、详细分析说明。

3.1 集合的基本概念集合的表示法列举法将集合中的元素一一列举，或列出足够多的元素以反映集合中元素的特征。

例如：V={a,e,i,o,u} 或B={1,4,9,16,25,36……}。

描述法通过描述集合中元素的共同特征来表示集合。

例如：V= {x| x是元音字母}B={x| x=a2, a是自然数}C= {x| x∈Z ∧3<x≤6}，即C={4,5,6}3.1 集合的基本概念集合的表示9元素a属于集合A，记作a ∈A。

9元素a不属于集合A ，记作a ∉A3.1 集合的基本概念3.1 集合的基本概念集合的特征9确定性：任何一个对象，或者是这个集合的元素，或者不是，二者必居其一。

例如：A={x| x∈N ∧x<100}，C={x| x是秃子}9互异性：集合中任何两个元素都是不同的，即集合中不允许出现重复的元素。

例如：集合A={a,b,c,c,b,d}，应该是A={a,b,c,d}3.1 集合的基本概念集合的特征9无序性：集合与其中的元素的顺序无关。

离散数学第三章集合的基本概念和运算知识点总结集合论部分第三章、集合的基本概念和运算3.1 集合的基本概念集合的定义与表⽰集合与元素集合没有精确的数学定义理解：⼀些离散个体组成的全体组成集合的个体称为它的元素或成员集合的表⽰列元素法A={ a, b, c, d }谓词表⽰法B={ x | P(x) }B 由使得P(x) 为真的x构成常⽤数集N, Z, Q, R, C 分别表⽰⾃然数、整数、有理数、实数和复数集合，注意0 是⾃然数.元素与集合的关系：⾪属关系属于∈，不属于?实例A={ x | x∈R∧x2-1=0 }, A={-1,1}1∈A, 2?A注意：对于任何集合A 和元素x (可以是集合)，x∈A和x?A 两者成⽴其⼀，且仅成⽴其⼀.集合之间的关系包含（⼦集）A?B??x (x∈A→x∈B)不包含A?B??x (x∈A∧x?B)相等A = B?A?B∧B?A不相等A≠B真包含A?B?A?B∧A≠B不真包含A?B思考：≠和?的定义注意∈和?是不同层次的问题空集?不含任何元素的集合实例{x | x2+1=0∧x∈R} 就是空集定理空集是任何集合的⼦集Ax (x∈?→x∈A) ?T推论空集是惟⼀的.证假设存在?1和?2，则?1??2 且?1??2，因此?1=?2全集E 相对性在给定问题中，全集包含任何集合，即?A (A?E )幂集定义P(A) = { x | x?A }实例P(?) = {?}，P({?}) = {?,{?}}P({1,{2,3}})={?,{1},{{2,3}},{1,{2,3}}}计数如果|A| = n，则|P(A)| = 2n3.2 集合的基本运算集合基本运算的定义??-~⊕并A?B = { x | x∈A∨x∈B }交A?B = { x | x∈A∧x∈B }相对补A-B = { x | x∈A∧x?B }对称差A⊕B = (A-B)?(B-A)= (A?B)-(A?B)绝对补~A = E-A⽂⽒图（John Venn）关于运算的说明运算顺序：~和幂集优先，其他由括号确定并和交运算可以推⼴到有穷个集合上，即A1?A2?…A n= {x | x∈A1∨x∈A2∨…∨x∈A n}A1?A2?…A n= {x | x∈A1∧x∈A2∧…∧x∈A n}某些重要结果A-B?AA?B ?A-B=?（后⾯证明）A?B=??A-B=A命题演算法证X?Y：任取x ，x∈X?… ?x∈Y 例3 证明A?B?P(A)?P(B)任取xx∈P(A) ?x?A?x?B ? x∈P(B)任取xx∈A ? {x}?A ? {x}∈P(A) ? {x}∈P(B){x}B x∈B包含传递法证X?Y：找到集合T 满⾜X?T 且T?Y，从⽽有X?Y例4 A-B ? A?B证A-B ? AA ? A?B所以A-B ? A?B利⽤包含的等价条件证X?Y：例5 A?C∧B?C ?A?B?C证A?C?A?C=CB?C?B?C=C(A?B)?C=A?(B?C)=A?C=C(A?B)?C=C ?A?B?C命题得证反证法证X?Y：欲证X?Y, 假设命题不成⽴，必存在x 使得x∈X 且x?Y. 然后推出⽭盾.例6 证明A?C ∧ B?C ? A?B?C证假设A?B ? C 不成⽴，则?x (x∈A?B∧x?C)因此x∈A 或x∈B，且x?C若x∈A, 则与A?C ⽭盾；若x∈B, 则与B?C ⽭盾.利⽤已知包含式并交运算：由已知包含式通过运算产⽣新的包含式X?Y ?X?Z?Y?Z, X?Z?Y?Z 例7 证明A?C?B?C ∧ A-C?B-C ? A?B证A?C?B?C，A-C ? B-C上式两边求并，得(A?C)?(A-C) ? (B?C)?(B-C)(AC)(A~C) (BC)(B~C)A(C~C) B(C~C)AE BEA B命题演算法证明X=Y：任取x ，x∈X ?… ?x∈Yx∈Y ?… ?x∈X或者x∈X ?… ? x∈Y例8 证明A?(A?B)=A （吸收律）证任取x,x∈A?(A?B) ? x∈A∨ x∈A?Bx∈A ∨ (x∈A ∧ x∈B) ? x∈A等式替换证明X=Y：不断进⾏代⼊化简，最终得到两边相等例9 证明A?(A?B)=A （吸收律）证(假设交换律、分配律、同⼀律、零律成⽴)A?(A?B)=(A?E)?(A?B) 同⼀律=A?(E?B) 分配律=A?(B?E) 交换律=A?E 零律=A 同⼀律反证法证明X=Y：假设X=Y 不成⽴，则存在x 使得x∈X且x?Y，或者存在x 使得x∈Y且x?X，然后推出⽭盾.例10 证明以下等价条件A?B ? A?B=B ? A?B=A ? A-B=?(1) (2) (3) (4)证明顺序：(1) ?(2), (2) ?(3), (3) ?(4), (4) ?(1)(1) ?(2)显然B?A?B，下⾯证明A?B?B.任取x，x∈A?B ? x∈A∨x∈B ? x∈B∨x∈B ? x∈B因此有A?B?B. 综合上述（2）得证.(2) ?(3)A=A?(A?B) ? A=A?B（将A?B⽤B代⼊)(3) ?(4)假设A-B≠?, 即?x∈A-B，那么x∈A且x?B. ⽽x?B ? x?A?B.从⽽与A?B=A⽭盾.(4) ?(1)假设A?B不成⽴，那么x (x∈A ∧ x?B) ? x∈A-B ? A-B≠?与条件（4）⽭盾.集合运算法证明X=Y：由已知等式通过运算产⽣新的等式X=Y ? X?Z=Y?Z, X?Z=Y?Z，X-Z=Y-Z 例11 证明A?C=B?C ∧ A?C=B?C ? A=B证由A?C=B?C 和A?C=B?C 得到(A?C)-(A?C)=(B?C)-(B?C)从⽽有A⊕C=B⊕C因此A⊕C=B⊕C ? (A⊕C)⊕C =(B⊕C)⊕CA⊕(C⊕C) =B⊕(C⊕C) ?A⊕?=B⊕?? A=B3.3 集合中元素的计数集合的基数与有穷集合集合A 的基数：集合A中的元素数，记作card A有穷集A：card A=|A|=n，n为⾃然数.有穷集的实例：A={ a,b,c}, card A=|A|=3；B={ x | x2+1=0, x∈R}, card B=|B|=0⽆穷集的实例：N, Z, Q, R, C 等包含排斥原理：定理设S 为有穷集，P1, P2, …, P m是m 种性质，A i 是S中具有性质P i的元素构成的⼦集，i=1, 2,…, m.则S中不具有性质P1, P2, …, P m 的元素数为证明要点：任何元素x，如果不具有任何性质，则对等式右边计数贡献为１，否则为０证设x不具有性质P1, P2, … , P m ,x?A i, i= 1, 2, … , mx?A i?A j, 1≤i < j ≤m…x?A1?A2?…?A m,x 对右边计数贡献为1 - 0 + 0 -0 + … + (-1)m· 0 = 1例1 求1到1000之间（包含1和1000在内）既不能被5 和6 整除，也不能被8 整除的数有多少个？解：S ={ x | x∈Z, 1≤x ≤1000 },如下定义S的3 个⼦集A, B, C：A={ x | x∈S, 5 | x }，B={ x | x∈S, 6 | x }，C={ x | x∈S, 8 | x }对上述⼦集计数：|S|=1000,|A|= ?1000/5? =200, |B|=?1000/6?=133，|C|= ?1000/8? =125,|A?B|= ?1000/30? =33, |B?C| = ?1000/40? =25,|B?C|= ?1000/24? =41,|A?B?C| = ?1000/120? =8,代⼊公式N = 1000-(200+133+125)+(33+25+41)-8=600例224名科技⼈员，每⼈⾄少会1门外语.英语：13；⽇语：5；德语：10；法语：9英⽇：2; 英德：4；英法：4；法德：4 会⽇语的不会法语、德语求：只会1 种语⾔⼈数，会3 种语⾔⼈数x+2(4-x)+y1+2=13x+2(4-x)+y2=10x+2(4-x)+y3=9x+3(4-x)+y1+y2+y3=19x=1, y1=4, y2=3, y3=2。

离散数学知识点归纳一、集合论。

1. 集合的基本概念。

- 集合是由一些确定的、彼此不同的对象组成的整体。

这些对象称为集合的元素。

例如，A = {1,2,3}，其中1、2、3是集合A的元素。

- 集合的表示方法有列举法（如上述A的表示）和描述法（如B={xx是偶数且x < 10}）。

2. 集合间的关系。

- 子集：如果集合A的所有元素都是集合B的元素，则称A是B的子集，记作A⊆ B。

例如，{1,2}⊆{1,2,3}。

- 相等：如果A⊆ B且B⊆ A，则A = B。

- 真子集：如果A⊆ B且A≠ B，则A是B的真子集，记作A⊂ B。

3. 集合的运算。

- 并集：A∪ B={xx∈ A或x∈ B}。

例如，A = {1,2}，B={2,3}，则A∪B={1,2,3}。

- 交集：A∩ B = {xx∈ A且x∈ B}。

对于上述A和B，A∩ B={2}。

- 补集：设全集为U，集合A相对于U的补集¯A=U - A={xx∈ U且x∉ A}。

二、关系。

1. 关系的定义。

- 设A、B是两个集合，A× B的子集R称为从A到B的关系。

当A = B时，R称为A上的关系。

例如，A={1,2}，B = {3,4}，R={(1,3),(2,4)}是从A到B的关系。

2. 关系的表示。

- 关系矩阵：设A={a_1,a_2,·s,a_m}，B={b_1,b_2,·s,b_n}，R是从A到B的关系，则R的关系矩阵M_R=(r_ij)，其中r_ij=<=ft{begin{matrix}1,(a_i,b_j)∈ R0,(a_i,b_j)∉ Rend{matrix}right.。

- 关系图：对于集合A上的关系R，用节点表示A中的元素，若(a,b)∈ R，则用有向边从a指向b。

3. 关系的性质。

- 自反性：对于集合A上的关系R，如果对任意a∈ A，都有(a,a)∈ R，则R 是自反的。

例如，A={1,2,3}，R = {(1,1),(2,2),(3,3)}是自反关系。