以上的 X, Y 代表集合公式
27
命题演算法证 XY
任取 x ， xX … xY 例3 证明AB P(A)P(B) 任取x xP(A) xA xB xP(B) 任取x xA {x}A {x}P(A) {x}P(B) {x}B xB
分配 吸收
与 与 A(BC)=(AB)(AC) A(BC)=(AB)(AC) A(BC)=(AB)(AC) A(AB)=A A(AB)=A
25
吸收律的前提：、可交换
集合运算的算律（续）
D.M 律 双重否定 A(BC)=(AB)(AC) A(BC)=(AB)(AC) (BC)=BC (BC)=BC A=A E
集合 没有精确的数学定义 理解：一些离散个体组成的全体 组成集合的个体称为它的元素或成员 集合的表示 1.列元素法:列出它的元素，元素之间用逗号分开，再 用花括号括起。 A={ a, b, c, d }
5
集合定义与表示
2.谓词表示法: 用谓词公式来确定集合。即个体域中能使 谓词公式为真的那些元素，确定了一个集合，因为这些元 素都具有某种特殊性质。若P(x)含有一个自由变元的谓词 公式，则{x|P(x)}定义了集合B ，并可表为 B={ x | P(x) } B 由使得 P(x) 为真的 x 构成 xBP(x)为真 3.文氏图法 常用数集 N, Z, Q, R, C 分别表示自然数、整数、有理数、 实数和复数集合，注意 0 是自然数.
例10 证明以下等价条件 AB AB=B AB=A AB= (1) (2) (3) (4) 证明顺序： (1) (2), (2) (3), (3) (4), (4) (1)
35
(1) (2) 显然BAB，下面证明ABB. 任取x， xAB xAxB xBxB xB 因此有ABB. 综合上述（2）得证. (2) (3) A=A(AB) A=AB （将AB用B代入)
32
命题演算法证明X=Y
任取 x ， xX … xY xY … xX 或者 xX … xY
例8 证明 A(AB)=A （吸收律） 证 任取x, xA(AB) xA xAB xA (xA xB) xA
33
等式替换证明X=Y
8
集合之间的关系
包含（子集）：设A和B是任意两个集合，如果 集合A的每个元素，都是集合B中的一个元素， 则称A是B的子集，或称A被包含于B中，或者 说B包含A，并记为A B A B x (xA xB)
这表明，要证明AB，只需对任意元素x，有 下式 xAxB 成立即可。
所有计算机系二年级学生都选修离散数学 数学系一年级的学生都没有选修离散数学 数学系学生或爱好文学或爱好体育运动 只有一、二年级的学生才爱好体育运动 除去数学和计算机系二年级学生外都不 选修离散数学 T(MR)S
S：二年级大学生的集合 M：数学系学生的集合
RS T
(MF)T= MLP PFS S(MR)P
6
集合与元素
元素与集合的关系：隶属关系 属于，不属于 实例 A={ x | xRx2-1=0 }, A={-1,1} 1A, 2A 注意：对于任何集合 A 和元素 x (可以是集合)， xA和 xA 两者成立其一，且仅成立其一.
7
隶属关系的层次结构
例 3.1 A={ a, {b,c}, d, {{d}} } {b,c}A bA {{d}}A {d}A dA
(5) 若 XS3，X S1, 则 X 与 S1, ... , S5 都不等
24
集合运算的算律
交换 结合 幂等 AB=BA (AB)C= A(BC) AA=A AB=BA (AB)C= A(BC) AA=A AB=BA (AB)C= A(BC)
15
3.2 集合的基本运算
集合基本运算的定义 文氏图（John Venn） 例题 集合运算的算律 集合包含或恒等式的证明
16
集合基本运算的定义
并
交 相对补 对称差
AB = { x | xA xB }
AB = { x | xA xB } AB = { x | xA xB } AB = (AB)(BA) = (AB)(AB)
不断进行代入化简，最终得到两边相等 例9 证明A(AB)=A （吸收律） 证 (假设交换律、分配律、同一律、零律成立) A(AB) =(AE)(AB) 同一律 =A(EB) 分配律 =A(BE) 交换律 =AE 零律 =A 同一律
34
反证法证明X=Y
假设 X=Y 不成立，则存在 x 使得 xX且xY， 或者存在 x 使得 xY且xX，然后推出矛盾.
36
(3) (4) 假设AB, 即xAB，那么xA且xB. 而 xB xAB. 从而与AB=A矛盾.
(4) (1) 假设AB不成立，那么 x (xA xB) xAB AB 与条件（4）矛盾.
37
集合运算法证明X=Y
由已知等式通过运算产生新的等式 X=Y XZ=YZ, XZ=YZ，X-Z=Y-Z 例11 证明AC=BC AC=BC A=B 证 由 AC=BC 和 AC=BC 得到 (AC)-(AC)=(BC)-(BC) 从而有 AC=BC 因此 AC=BC (AC)C =(BC)C A(CC) =B(CC) A=B A=B
38
集合的笛卡尔积
笛卡尔积在后面讨论关系有重要应用。 定义 两个元素a,b组成二元组，若它们有 次序之别，称为二元有序组，或有序对， 记为<a, b> ， 称a为第一分量，b为第一分 量。 若ab时，<a, b><b, a>。
其中P(x)为任何谓词公式。
{x | x2+1=0xR} 就是空集
定理 空集是任何集合的子集 A x (xxA) T 推论 空集是惟一的. 证 假设存在1和2，则12 且12，因此1=2
12
空集与全集
空集 不含任何元素的集合
={x|P(x)P(ห้องสมุดไป่ตู้)}
补元律 零律 同一律 否定
AA= A= A=A =E
AA=E AE=E AE=A E=
26
集合包含或相等的证明方法
证明 XY
命题演算法 包含传递法 等价条件法 反证法
证明 X=Y
命题演算法 等式代入法 反证法 运算法
并交运算法
30
反证法证 XY
欲证XY, 假设命题不成立，必存在 x 使得 xX 且 xY. 然后推出矛盾. 例6 证明 AC BC ABC 证 假设 AB C 不成立， 则 x (xABxC) 因此 xA 或 xB，且 xC 若 xA, 则与 AC 矛盾； 若 xB, 则与 BC 矛盾.
相对性 在给定问题中，全集包含任何集合，即A (AE )
14
幂集
定义：一个集合的幂集是指该集合所有子集的 集合，即是由这些子集所组成的集合族。 P(A) = { x | xA } 由定义可知，P(A)，AP(A)。 实例 P() = {}， P({}) = {,{}} P({1,{2,3}})={,{1},{{2,3}},{1,{2,3}}} 计数 如果 |A| = n，则 |P(A)| = 2n
绝对补
A = EA
17
文氏图表示
文氏(Venn)图是一种利用平面上的点构成 的图形来形象展示集合的一种方法。全
集U用一个矩形的内部表示，其他集合用
矩形内的园面或一封闭曲线圈成的面积 来表示。
18
如果AB，则表示A的圆面一般将完全落
在表示B的圆面内，如图1中(a)。如果A
与B没有公共元素，那么表示A的圆面将
真包含 ：设A和B是两个集合，若AB且AB， 则称A是B的真子集，记为AB，也称B真包含 A。该定义也可表为 ABABAB 不真包含 AB 思考： 和 的定义 注意 和 是不同层次的问题
11
空集与全集
空集 不含任何元素的集合
={x|P(x)P(x)}
实例
31
利用已知包含式并交运算
由已知包含式通过运算产生新的包含式 XY XZYZ, XZYZ
例7 证明 ACBC ACBC AB 证 ACBC， AC BC 上式两边求并，得 (AC)(AC) (BC)(BC) (AC)(AC) (BC)(BC) A(CC) B(CC) AE BE AB
28
包含传递法证 XY
找到集合T 满足 XT 且 TY，从而有XY 例4 AB AB 证 AB A A AB 所以 AB AB
29
利用包含的等价条件证 XY
A B A B B A B A A-B
例5 ACBC ABC 证 AC AC=C BC BC=C (AB)C=A(BC)=AC=C (AB)C=C ABC 命题得证
23
例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 } (1) 若 XS3=, 则 X = S2 (2) 若 XS4, XS2=, 则 X = S5 (3) 若 XS1，X S3, 则 X = S1, S2, S4 (4) 若 XS3=, 则 X = S3, S5
集合论
1
集合论部分
第3章 第4章
集合的基本概念和运算 二元关系和函数
2
第3章 集合的基本概念和运算
3.1 集合的基本概念 3.2 集合的基本运算 3.3 集合中元素的计数
3
3.1 集合的基本概念
集合的定义与表示
集合与元素 集合之间的关系 空集 全集 幂集
