离散数学第三章集合的基本概念和运算知识点总结.docx

该【离散数学第三章集合的基本概念和运算知识点总结 】是由【飞行的优优】上传分享，文档一共【9】页，该文档可以免费在线阅读，需要了解更多关于【离散数学第三章集合的基本概念和运算知识点总结 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。失散数学第三章会集的基本看法和运算知识点总
结
会集论部分
第三章、会集的基本看法和运算

会集与元素
会集没有精确的数学定义
理解:一些失散个体组成的全体组成会集的个体称为它的元素或成员
会集的表示
列元素法A={a,b,c,d}
谓词表示法B={x|P(x)}
B由使得P(x)为真的x组成常用数集
N,Z,Q,R,C分别表示自然数、整数、有理数、
实数和复数会集,注意0是自然数.
元素与会集的关系:隶属关系
属于,不属于
实例
A={x|xRx2-1=0},A={-1,1}
1A,2A
注意:关于任何会集A和元素x(能够是会集),
xA和xA两者成立其一,且仅成立其一.
会集之间的关系
包含(子集)ABx(xAxB)
不包含ABx(xAxB)
相等A=BABBA
不相等AB
真包含ABABAB
不真包含AB
思虑:和的定义
注意和是不同样层次的问题
空集不含任何元素的会集
实例{x|x2+1=0xR}就是空集
定理空集是任何会集的子集
Ax(xxA)T
推论空集是独一的.
证假设存在1和2,则12且12,因此1=2
全集E
相对性
在给定问题中,全集包含任何会集,即A(AE)
幂集定义P(A)={x|xA}
实例
P()={},
P({})={,{}}
P({1,{2,3}})={,{1},{{2,3}},{1,{2,3}}}
计数
若是|A|=n,则|P(A)|=2n

会集基本运算的定义
并AB={x|xAxB}
交AB={x|xAxB}
相对补AB={x|xAxB}
对称差AB=(AB)(BA)
=(AB)(AB)
绝对补A=EA
文氏图(JohnVenn)
关于运算的说明
运算序次:和幂集优先,其他由括号确定
并和走运算能够实行到有穷个会集上,即
A1A2
An={x|xA1xA2
xAn}
A1A2
An={x|xA1xA2
xAn}
某些重要结果
ABA
ABAB=(后边证明)
AB=AB=A
命题演算法证XY:任取x,xX
例3证明ABP(A)P(B)
任取x
xY
xP(A)xAxBxP(B)
任取x
xA{x}A{x}P(A){x}P(B)
{x}BxB
包含传达法证XY:找到会集T满足XT且TY,从而有XY例4
ABAB
证ABA
AAB
因此ABAB
利用包含的等价条件证XY:
例5ACBCABC
证ACAC=C
BCBC=C
(AB)C=A(BC)=AC=C(AB)C=CABC
命题得证
反证法证XY:欲证XY,假设命题不成立,必存在x使得xX且x
.
例6证明ACBCABC
证假设ABC不成立,
则x(xABxC)
因此xA或xB,且xC
若xA,则与AC矛盾;若xB,则与BC矛盾.
利用已知包含式并走运算:由已知包含式经过运算产生新的包含式X
YXZYZ,XZYZ
例7证明ACBCACBCAB
证ACBC,ACBC
上式两边求并,得
(AC)(AC)(BC)(BC)
(AC)(AC)(BC)(BC)
A(CC)B(CC)
AEBE
AB
命题演算法证明X=Y:任取x,
xXxY
xYxX
也许
xXxY
例8证明A(AB)=A(吸取律)
证任取x,
xA(AB)xAxAB
xA(xAxB)xA
等式代替证明X=Y:不断进行代入化简,最后获取两边相等
例9证明A(AB)=A(吸取律)
证(假设交换律、分配律、同一律、零律成立)A(AB)
=(AE)(AB)同一律
=A(EB)

分配律
=A(BE)

交换律
=AE

零律
=A

同一律
反证法证明

X=Y:假设

X=Y

不成立,则存在

x使得

xX且

xY,或
者存在

x使得

xY且

xX,尔后推出矛盾

.
例10证明以低等价条件
ABAB=BAB=AAB=
(1)(2)(3)(4)证明序次:
(2),(2)(3),(3)(4),(4)(1)
(2)
显然BAB,下面证明ABB.
任取x,
xABxAxBxBxBxB
(2)得证.
(2)(3)
A=A(AB)A=AB
(将AB用B代入)
(3)(4)
假设AB,即xAB,.
从而与AB=A矛盾.
(4)(1)
假设AB不成立,那么
x(xAxB)xABAB
与条件(4)矛盾.
会集运算法证明X=Y:由已知等式经过运算产生新的等式
X=YXZ=YZ,XZ=YZ,X-Z=Y-Z
例11证明AC=BCAC=BCA=B
证由AC=BC和AC=BC获取
(AC)-(AC)=(BC)-(BC)
从而有AC=BC
因此
AC=BC(AC)C=(BC)C
A(CC)=B(CC)A=BA=B

会集的基数与有穷会集
会集A的基数:会集A中的元素数,记作cardA有穷集A:cardA=|A|=n,n为自然数.
有穷集的实例:
A={a,b,c},cardA=|A|=3;
B={x|x2+1=0,xR},cardB=|B|=0
无量集的实例:
N,Z,Q,R,C

等
包含排斥原理:定理

设S为有穷集,

P1,P2,

,Pm是

m

种性质,
Ai

是

S中拥有性质

Pi

的元素组成的子集,

i=1,2,
,,P2,,Pm的元素数为
证明要点:任何元素x,若是不拥有任何性质,则同等式右边计数贡
献为1,否则为0
证设x不拥有性质P1,P2,,Pm,
xAi,i=1,2,

,m
xAiAj,1i

jm
xA1A2Am,
对右边计数贡献为
10+00+
+(1)m0=1
例1求1到1000之间(包含1
和1000在内)既不能够被
5和6整
除,也不能够被
8整除的数有多少个?
解:S={x|xZ,1x1000},
以下定义S的3个子集A,B,C:
A={x|xS,5|x},
B={x|xS,6|x},
C={x|xS,8|x}
对上述子集计数:
|S|=1000,
|A|=1000/5=200,|B|=1000/6=133,
|C|=1000/8=125,
|AB|=1000/30=33,|BC|=1000/40=25,
|BC|=1000/24=41,
|ABC|=1000/120=8,
代入公式
N=1000(200+133+125)+(33+25+41)8=600
例2
24名科技人员,每人最少会1门外语.
英语:13;日语:5;德语:10;法语:9英日:2;英德:4;
英法:4;法德:4会日语的不会法语、德语
求:只会1种语言人数,会3种语言人数x+2(4-x)+y1+2=13