离散数学学习笔记——集合论基础

1495-冯同学

发表文章数:80

热门标签

,
首页 » 算法 » 正文

空集

Definition

不含任何元素的集合叫做空集(empty set),记作

.

/varnothing .

.

空集可以符号化为

=

{

x

x

x

}

.

/varnothing=/{x /mid x /neq x/} .

={xx=x}.

Example

  • A

    =

    {

    x

    x

    R

    ,

    x

    2

    <

    0

    }

    ,

    A=/left/{x /mid x /in R, x^{2}<0/right/},

    A={xxR,x2<0},

    A

    =

    A=/varnothing

    A=

  • =

    0

    ,

    {

    }

    =

    1

    |/varnothing|=0,|/{/varnothing/}|=1

    =0,{}=1

空集是绝对唯一的。

全集

Definition

针对一个具体范围,我们考虑的所有对象的集合叫做全集(universal set),记作

U

U

U

E

E

E

在文氏图一般使用方形表示全集。

Example

  • 在立体几何中,全集是由空间的全体点组成的 ;
  • 在我国的人口普查中,全集是由我国所有人组成的。

全集是相对唯一的。

集合的相等关系

  • 集合中的元素是无序的。

    {

    1

    ,

    2

    ,

    3

    ,

    4

    }

    /{1, 2, 3, 4/}

    {1,2,3,4}

    {

    2

    ,

    3

    ,

    1

    ,

    4

    }

    /{2, 3, 1, 4/}

    {2,3,1,4}相同。

  • 集合中的元素是不同的。

    {

    1

    ,

    2

    ,

    2

    ,

    3

    ,

    4

    ,

    3

    ,

    4

    ,

    2

    }

    /{1, 2, 2, 3, 4, 3, 4, 2/}

    {1,2,2,3,4,3,4,2}

    {

    1

    ,

    2

    ,

    3

    ,

    4

    }

    /{1, 2, 3, 4/}

    {1,2,3,4}相同。

citing example

E

=

{

x

(

x

1

)

(

x

2

)

(

x

3

)

=

0

,

x

R

}

,

F

=

{

x

x

Z

+

,

x

2

<

12

}

/quad E=/{x /mid(x-1)(x-2)(x-3)=0, x /in R/}, F=/left/{x /mid x /in Z^{+}, x^{2}<12/right/}

E={x(x1)(x2)(x3)=0,xR},F={xxZ+,x2<12}
可见

E

E

E

F

F

F 具有相同的元素

{

1

,

2

,

3

}

,

/{1,2,3/},

{1,2,3}, 此时称两个集合相等。

Theorem (外延性原理)

两个集合

A

A

A

B

B

B 相等,当且仅当它们的元素完全相同,记为

A

=

B

,

A=B,

A=B, 否则

A

A

A

B

B

B 不相等,记为

A

B

A /neq B

A=B

集合的包含关系

A

=

{

B

A

S

I

C

,

P

A

S

C

A

L

,

A

D

A

}

,

B

=

{

A

D

A

,

P

A

S

C

A

L

}

A=/{B A S I C, P A S C A L, A D A/}, B=/{A D A, P A S C A L/}

A={BASIC,PASCAL,ADA},B={ADA,PASCAL},此时

A

A

A 中含有

B

B

B 中所有的元素,这种情况称为A 包含

B

B

B

Definition

A

,

B

A, B

A,B 是任意两个集合,

  • 如果

    B

    B

    B 的每个元素都是

    A

    A

    A 中的元素,则称

    B

    B

    B

    A

    A

    A 的子集,也称做

    B

    B

    B

    A

    A

    A 包含或

    A

    A

    A 包含

    B

    ,

    B,

    B, 记作

    B

    A

    ,

    B /subseteq A,

    BA, 否则记作

    B

    A

    .

    B /nsubseteq A .

    BA.

  • 如果

    B

    A

    B /subseteq A

    BA 并且

    A

    B

    ,

    A /neq B,

    A=B, 则称

    B

    B

    B

    A

    A

    A 的真子集,也称做

    B

    B

    B

    A

    A

    A 真包含或

    A

    A

    A 真包含

    B

    B

    B, 记 作

    B

    A

    ,

    B /subset A,

    BA, 否则记作

    B

    ⊄

    A

    .

    B /not /subset A .

    BA.

/subseteq

”关系的数学语言描述为:

B

A

B /subseteq A /Leftrightarrow

BA

x

,

/forall x,

x, 如果

x

B

,

x /in B,

xB,

x

A

.

x /in A .

xA.

离散数学学习笔记——集合论基础

由子集定义可有

(1)

A

/varnothing /subseteq A

A
(2)

A

A

A /subseteq A

AA

Example
已知

A

=

{

1

,

2

,

3

,

4

}

,

B

=

{

1

,

2

,

4

}

,

C

=

{

2

,

3

}

,

D

=

{

3

,

2

}

,

A=/{1,2,3,4/}, B=/{1,2,4/}, C=/{2,3/}, D=/{3,2/},

A={1,2,3,4},B={1,2,4},C={2,3},D={3,2}, 可见
(1)

A

A

,

B

A

,

C

A

,

D

A

,

A /subseteq A, B /subseteq A, C /subseteq A, D /subseteq A,

AA,BA,CA,DA,
(2)

C

D

,

D

C

,

C /subseteq D, D /subseteq C,

CD,DC, 同时,

C

=

D

C=D

C=D

证明集合相等

Theorem

A

,

B

A, B

A,B 为任意两个集合,则

A

=

B

A

B

A=B /Leftrightarrow A /subseteq B

A=BAB 并且

B

A

B /subseteq A

BA

⋆⋆⋆ 上面的定理非常重要,这是证明集合相等的一种非常有效的方式。

证明框架

证明:

(1) 首先证明

A

B

:

x

A

,


,

x

B

.

A

B

.

A /subseteq B: /forall x /in A, /cdots, x /in B . /therefore A /subseteq B .

AB:xA,,xB.AB.

( 2 其次证明

B

A

:

x

B

,


,

x

A

.

B

A

.

B /subseteq A: /forall x /in B, /cdots, x /in A . /therefore B /subseteq A .

BA:xB,,xA.BA.

元集的子集

对于任意

n

n

n 元集合

A

A

A, 它的

m

m

m

(

0

m

n

)

(0 /leqslant m /leqslant n)

(0mn) 子集个数为

C

n

m

C_{n}^{m}

Cnm 个, 所以不同的子集个数为

:

C

n

0

+

C

n

1

+

+

C

n

n

=

(

1

+

1

)

n

=

2

n

.

: C_{n}^{0}+C_{n}^{1}+/cdots+C_{n}^{n}=(1+1)^{n}=2^{n} .

:Cn0+Cn1++Cnn=(1+1)n=2n.

幂集

A

A

A 为任意集合,把

A

A

A 的所有不同子集构成的集合叫做

A

A

A 的幕集(power set), 记作

P

(

A

)

P(A)

P(A), 即,

P

(

A

)

=

{

x

x

A

}

P(A)=/{x /mid x /subseteq A/}

P(A)={xxA}

可知以下关系等价

x

P

(

A

)

x

A

/quad x /in P(A) /Leftrightarrow x /subseteq A

xP(A)xA

Example

A

=

{

a

,

b

,

c

}

,

B

=

{

a

,

{

b

,

c

}

}

,

A=/{a, b, c/}, B=/{a,/{b, c/}/},

A={a,b,c},B={a,{b,c}}, 求他们的幕集

P

(

A

)

P(A)

P(A)

P

(

B

)

P(B)

P(B)

:

P

(

A

)

=

{

,

{

a

}

,

{

b

}

,

{

c

}

,

{

a

,

b

}

,

{

b

,

c

}

,

{

a

,

c

}

,

{

a

,

b

,

c

}

}

: P(A)=/{/varnothing,/{a/},/{b/},/{c/},/{a, b/},/{b, c/},/{a, c/},/{a, b, c/}/}

:P(A)={,{a},{b},{c},{a,b},{b,c},{a,c},{a,b,c}}

P

(

B

)

=

{

,

{

a

}

,

{

{

b

,

c

}

}

,

{

a

,

{

b

,

c

}

}

}

P(B)=/{/varnothing,/{a/},/{/{b, c/}/},/{a,/{b, c/}/}/}

P(B)={,{a},{{b,c}},{a,{b,c}}}

幂集也叫做集族或集合的集合,对集族的研究在数学方面、知识库和表处理语言以及人工
智能等方面都有十分重要的意义。

未经允许不得转载:作者:1495-冯同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《离散数学学习笔记——集合论基础》 发布于2021-02-17

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录