离散数学：3-2 集合的基本概念与运算

复习思考题6(x)P(x)=0当且仅当x个体域D，有P(x)=0.(x)Q(x)=0当且仅当x0个体域D，使Q(x0)=0.xP(x)xQ(x)

前提xP(x)①化简

P(c)②

-规则xQ(x)①化简

Q(c)④-规则

P(c)Q(c)③⑤合取x(P(x)Q(x))⑥+规则下列推理是否有错？若有错，如何改正？

Q(d)④-规则

yQ(y)

⑤+规则xQ(x)yQ(y)④⑥合取xy(P(x)Q(y))⑦置换第3章集合的基本概念和运算3.1集合的基本概念3.2集合的基本运算3.3集合中元素的计数集合之间的关系

集合与集合的关系包含

A

B

x(xA

xB)

不包含A⊈B

x(xAxB)

相等

A=B

A

B

B

A

x(xAxB)

不相等A

B(x)((xBxA)(xAxB))

真包含

A

B

A

B

A

B

不真包含

A

B思考：和的定义空集与全集空集——不含任何元素的集合。

={x|xx}如：A={x|x2+1=0xR}=定理：空集是任何集合的子集。Ax(xxA)1

推论：空集是惟一的.全集E在一定范围内，如果所涉及的集合均是某个集合的子集，则称此集合为全集（E）。

在给定问题中，全集包含任何集合，即A(AE)

1全集的概念相当于个体域（论域）

。

x(x

)0

x(x

E)1确定下列命题的真假：(1)(2)(3){}(4){}解：(1)为真

(2)为假

(3)为真

(4)为真注意：和是不同层次的问题幂集定义设A为集合，把A的全体子集构成的集合叫做A的幂集，记作P(A)，符号化表示为

P(A)={x|xA}

求A={a，b，c}的全部子集及幂集。解：将A的子集从小到大分类：0元子集，即空集，只有1个：

。1元子集，即单元子集，有3个：{a}，{b}，{c}。2元子集，有3个：{a,b}，{a,c}，{b,c}。3元子集，有1个：{a,b,c}。P(A)={，{a}，{b}，{c}，{a,b}，{a,c}，{b,c}，{a,b,c}}。幂集定理：设A为有限集合，则|P(A)|=2|A|。证明:

设|A|=n，A的子集有：含0个元素的子集有一个，即

个。含一个元素的子集有n个，即

个。含两个元素的子集有

个。

……

含n个元素的子集有

个。

求A={a，b，c}的全部子集及幂集

|A|=3，|P(A)|=8=23=2|A|P(A)={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}。3.2集合的基本运算集合的基本运算并

AB={x|xA

xB}交

AB={x|xA

xB}相对补

AB={x|xA

xB}绝对补

A=EA={x|xA}

（A的绝对补集是A对E的相对补集）对称差

AB

集合的并和交运算的性质满足交换律AB=B

AA

B=B

A满足幂等律A

A=A

A

A=A满足对的分配律、对的分配律A(BC)=(AB)(AC)A(BC)=(AB)(AC)A

=AA

=设A,B为集合，B对A的相对补集A－B定义为：重要结论：

A－B=A

~B集合相对补与绝对补的关系将相对补集与绝对补集联系在一起

A－B={x|xAxB}

ABA

AB=AB=A设A，B为集合，则A与B的对称差是集合的对称差运算

AB=(A-B)(B-A)=(A

~B)(B~A)

其文氏图如下：

AB=(A

B)－(AB)集合对称差运算的性质满足交换律AB=

B

A满足结合律(A

B)C=A

(B

C

)A

=AA

A

=AB=A

C

B=C

AB=(A-B)(B-A)交换AB=BAAB=BAAB=BA结合(AB)C=A(BC)(AB)C=A(BC)(AB)C=A(BC)幂等AA=AAA=A与与分配A(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)=(AB)(AC)吸收A(AB)=AA(AB)=A集合运算的算律吸收律的前提：、可交换集合运算的算律（续）D.M

律A(BC)=(AB)(AC)A(BC)=(AB)(AC)(BC)=BC(BC)=BC双重否定A=AE补元律AA=AA=E零律A=AE=E同一律A=AAE=A否定=EE=集合包含的证明方法证明

XY命题演算法包含传递法等价条件法反证法并交运算法以上的X,Y代表集合公式任取x，

xX…xY命题演算法证XY证:

(1)AB

P(A)P(B)

任取x,

xP(A)xA

xBxP(B)

(2)P(A)P(B)

AB

任取x

xA{x}A

{x}P(A){x}P(B){x}B

xB

例1证明AB

P(A)P(B)X

Yx(xXxY)包含传递法证XY找到集合T满足XT

且TY，从而有XY例2AB

AB证

因为AB

A

而

A

AB

所以

AB

AB

利用包含的等价条件证

XY(1)证

(AB)C=C

(AB)C

=A(BC)=AC

=C(AB)C=CABC

(2)证

(AB)

C=AB

(AB)C

=(AC)(BC)=AB(AB)C=ABABC例3ACBCABC

反证法证XY欲证XY,假设命题不成立，必存在x使得

xX且xY.然后推出矛盾.

例4证明ACBCABC证:

假设ABC不成立，则

AB⊈

C

x(xAB

xC)x((xA

xB)

xC)x((xA

xC)

(xBxC))x(xA

xC)

x(xBxC)

A⊈C

B⊈C（与前提矛盾）QPP

Q

A⊈B

x(xAxB)利用已知包含式并交运算证XY例5证明

ACBC

ACBCAB证:

上述两条件分别两边求并，得

(AC)(AC)

(BC)(BC)

(AC)(A~C)

(BC)(B~C)

A(C~C)

B(C~C)

AE

BE

A

B由已知包含式通过运算产生新的包含式

(X

Y)∧(SW

)

(XS)(YW)(X

Y)∧(SW

)

(XS)(YW)集合相等的证明方法证明X=Y命题演算法等式替换法反证法运算法以上的X,Y代表集合公式例6证明A－(BC)＝(A－B)(A－C)

证:对x，xA－(BC)=

x

A

x

(BC)=

x

A

(x

B

x

C)=

x

A

(xBxC)=(xA

x

B)(x

A

x

C)=

x(A－B)

x

(A－C)=

x(A－B)(A－C)命题演算法证明X=Y任取x

，xX…xY

xY…xX或者

xX…xY

XYYXX=Yx(xXxY)A-B={x|xAxB}等式替换证明X=Y例7证明A(AB)=A

（吸收律）证

(假设分配律、同一律、零律成立)

A(AB)=(AE)(AB)同一律

=A(EB)分配律

=AE

零律

=A

同一律不断进行代入化简，最终得到两边相等反证法证明X=Y例8证明ABAB=证:

假设A

B≠，即

x(xAxB)A

⊈

B与条件AB矛盾.所以，结论正确。假设X=Y不成立，则存在x使得xX且xY，或者存在x使得xY且xX，然后推出矛盾.

A

⊈

B={x|xAxB}集合运算法证明X=Y例9证明AC=BC

AC=BC

A=B证:

由第二个条件减第一个条件得

(AC)-(AC)=(BC)-(BC)

从而有AC=BC(AC)C=(BC)C

A(CC)=B(CC)A=B

A=B由已知等式通过运算产生新的等式

(X=Y)∧(Z=W)

XZ=YW,XZ=YW,X-Z=Y-W