离散数学-耿素云PPT(第5版).ppt

《离散数学-耿素云PPT(第5版).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1集合论2集合论部分第3章集合的基本概念和运算第4章二元关系和函数3第3章集合的基本概念和运算3.1集合的基本概念3.2集合的基本运算3.3集合中元素的计数43.1集合的基本概念集合的定义与表示集合与元素集合之间的关系空集全集幂集5集合定义与表示集合没有精确的数学定义理解：一些离散个体组成的全体组成集合的个体称为它的元素或成员集合的表示列元素法A={a,b,c,d}谓词表示法B={x

2、P(x)}B由使得P(x)为真的x构成常用数集N,Z,Q,R,C分别表示自然数、整数、有理数、实数和复数集合，注意0是

3、自然数.6集合与元素元素与集合的关系：隶属关系属于，不属于实例A={x

4、xRx2-1=0},A={-1,1}1A,2A注意：对于任何集合A和元素x(可以是集合)，xA和xA两者成立其一，且仅成立其一.7隶属关系的层次结构例3.1A={a,{b,c},d,{{d}}}{b,c}AbA{{d}}A{d}AdA8集合之间的关系包含（子集）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

5、思考：和的定义注意和是不同层次的问题9空集与全集空集不含任何元素的集合实例{x

6、x2+1=0xR}就是空集定理空集是任何集合的子集Ax(xxA)T推论空集是惟一的.证假设存在1和2，则12且12，因此1=2全集E相对性在给定问题中，全集包含任何集合，即A(AE)10幂集定义P(A)={x

7、xA}实例P()={}，P({})={,{}}P({1,{2,3}})={,{1},{{2,3}},{1,{2,3}}}计数如果

8、A

9、=n，则

10、P

11、(A)

12、=2n113.2集合的基本运算集合基本运算的定义文氏图（JohnVenn）例题集合运算的算律集合包含或恒等式的证明12集合基本运算的定义并AB={x

13、xAxB}交AB={x

14、xAxB}相对补AB={x

15、xAxB}对称差AB=(AB)(BA)=(AB)(AB)绝对补A=EA13文氏图表示14关于运算的说明运算顺序：和幂集优先，其他由括号确定并和交运算可以推广到有穷个集合上，即A1A2…An={x

16、xA1xA2…xAn}A1A

17、2…An={x

18、xA1xA2…xAn}某些重要结果ABAABAB=（后面证明）AB=AB=A15只有一、二年级的学生才爱好体育运动F:一年级大学生的集合S：二年级大学生的集合R：计算机系学生的集合M：数学系学生的集合T：选修离散数学的学生的集合L：爱好文学学生的集合P：爱好体育运动学生的集合T(MR)SRST(MF)T=MLPPFSS(MR)P除去数学和计算机系二年级学生外都不选修离散数学例1所有计算机系二年级学生都选修离散数学数学

19、系一年级的学生都没有选修离散数学数学系学生或爱好文学或爱好体育运动16例2分别对条件(1)到(5)，确定X集合与下述那些集合相等。S1={1,2,…,8,9},S2={2,4,6,8},S3={1,3,5,7,9},S4={3,4,5},S5={3,5}若XS3=,则X若XS4,XS2=,则X若XS1，XS3,则X若XS3=,则X若XS3，XS1,则X=S2=S5=S1,S2,S4=S3,S5与S1,...,S5都不等17交换AB=BAAB=BAAB=BA结合(A

20、B)C=A(BC)(AB)C=A(BC)(AB)C=A(BC)幂等AA=AAA=A与与分配A(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)=(AB)(AC)吸收A(AB)=AA(AB)=A集合运算的算律吸收律的前提：、可交换18集合运算的算律（续）D.M律A(BC)=(AB)(AC)A(BC)=(AB)(AC)(BC)=BC(BC)=BC双重否定A=AE补元律

21、AA=AA=E零律A=AE=E同一律A=AAE=A否定=EE=19集合包含或相等的证明方法证明XY命题演算法包含传递法等价条件法反证法并交运算法证明X=Y命题演算法等式代入法反证法运算法以上的X,Y代表集合公式20任取x，xX…xY命题演算法证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B21