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

时间:2025-04-04

集合论部分

第三章、集合的基本概念和运算

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} 就是空集

定理 空集是任何集合的子集

A x (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)| = 2n

3.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 …An= {x | x A1 x A2 … x An}

A1 A2 …An= {x | x A1 x A2 … x An}

某些重要结果

A B A

A B A B= (后面证明)

A B= A B=A

命题演算法证 X Y:任取 x , x X …

例3 证明A B P(A) P(B)

任取x

x Y

x P(A) x A x B x P(B)

任取x

x 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 A

A A B

所以 A B A B

利用包含的等价条件证 X Y:

例5 A C B C A B C

证 A C A C=C

B 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)

(A C) (A C) (B C) (B C)

A (C C) B (C C)

A E B E

A B

命题演算法证明X=Y:任取 x ,

x X … x Y

x Y … x X

或者

x X … x Y

例8 证明 A (A B)=A (吸收律)

证 任取x,

x A (A B) x A x A B

x 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) C

A (C C) =B (C C) A =B A=B

3.3 集合中元素的计数

集合的基数与有穷集合

集合 A 的基数:集合A中的元素数,记作 cardA

有穷集 A: cardA=|A|=n,n为自然数.

有穷集的实例:

A={ a,b,c}, cardA=|A|=3;

B={ x | x2+1=0, x R}, cardB=|B|=0

无穷集的实例:

N, Z, Q, R, C 等

包含排斥原理:定理 设 S 为有穷集,P1, P2, …, Pm 是 m 种性质, Ai 是 S 中具有 …… 此处隐藏:1507字,全部文档内容请下载后查看。喜欢就下载吧 ……

离散数学第三章集合的基本概念和运算知识点总结.doc 将本文的Word文档下载到电脑

    精彩图片

    热门精选

    大家正在看

    × 游客快捷下载通道(下载后可以自由复制和排版)

    限时特价:7 元/份 原价:20元

    支付方式:

    开通VIP包月会员 特价:29元/月

    注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
    微信:fanwen365 QQ:370150219