2016/6/10 Zhengjin ,CSU 22
数学归纳法
第二数学归纳法原理
n[ k[k<n → P(k)] → P(n)]
∴
xP(x)
证明过程: (1)首先证明P(0)为真。 (2)证明:对任意n>0，如果P(k)对一切k<n 成立， 那么P(n)成立。
2016/6/10
Zhengjin ,CSU
2016/6/10
Zhengjin ,CSU
2
个体与集合之间的关系：属于关系。
对于某个个体 a 和某个集合 A 而言，a 只有两种可能 1）a属于A，记为 aA，同时称 a 是 A 中的元素。 2）a 不属于 A，记为 aA ，称 a 不是 A 中的元素。
个体a属于A或者a不属于A，二者居其一且只居其一。
例2 求出下列集合的全部子集： （a) {，{}} (b) {{a，b}，{a，a，b}，{b，a，b}}
2016/6/10 Zhengjin ,CSU 11
集合上的运算
定义2 设A，B是两个集合 1）A∩B = { x︱xA∧xB }，称A∩B为A与 B的交集，称∩为集合交运算。 2）A∪B = { x︱xA∨xB }，称A∪B为A与 B的并集，称∪为集合并运算。 3) A–B= { x︱xA ∧ x B }， 称A–B为A 与B的差集
21
数学归纳法
对于以自然数为论域的 x P(x)形式的归纳证明过程 如下: 第一数学归纳法 (1)（基础）先证明P(0)是真。 (2)（归纳) 再证明 n( P(n) → P(n+1))是真
即先假设“P(n) 对任意取定的自然数n是真，再由此推 出P(n+1)也真，一旦证明了P(n) → P(n+1)对任 意n是真，则用全称推广规则得 n( P(n) → P(n+1)) 再根据数学归纳法第一原理得出 x P(x)。
例2：设A={，{}}，则2A={，{ }，{{ }}， { ，{ }}}
定理1 设集合A是有限集合， A = n，则 2A = 2 A 定理2 设A，B是两个集合。那么， A=B当且仅当 2A = 2B。
2016/6/10 Zhengjin ,CSU 18
有限集的计数原理
2016/6/10
பைடு நூலகம்
Zhengjin ,CSU
25
定理1 <x，y>= <u，v>当且仅当 x=u且y=v （根据序偶的定义即可得出。） 定义2 设n是正整数，x1，x2，…，xn是任意的元素。 若n=1，则令 <x1>=x1 若n=2，则令 <x1,x2>={{x1},{x1，x2}} 若n>2，则令 <x1,x2,…，xn>=<<x1,x2,…,xn-1>,xn> 我们称 <x1 ， x2 ， … ， xn> 为由 x1 ， x2 ， … ， xn 组成 的n元序偶，并称每个xi为它的第i个分量。 （这样就定义了n元序偶）
23
集合的笛卡尔乘积
由任意两个元素x和y组成的集合{x，y}为偶集。因为{x， y}={y，x}，所以这种偶集只能叫无序偶集， 简称无序偶。
有序偶 : 它不仅与含有的元素 x ，y有关，还与x， y 出现的次序有关。 这样的偶集称为有序偶，并记为：<x,y>
例如，用<x，y>表示平面直角坐标系下的横坐标为x且纵 坐标为y的点时，则<x，y>和<y，x>在xy时就代表不 同的点，因而就不相同。
例1 设 A={1，2，3，4，5}，B={2，5，7}，则 A ∪ B={1，2，3，4，5，7} A ∩ B={2，5} A–B={1，3，4}
Zhengjin ,CSU 12
2016/6/10
定理1 设U是全集，A，B，C是U的三个子集 1）A∩A=A， A∪A=A 2）A∩U=A， A∪U=U 3）A∩ = ， A∪ =A 4）A∩B= B∩A， A∪B= B∪A 5）(A∩B) ∩C = A∩ (B∩C)， (A∪B) ∪C = A∪ (B∪C) 6）A∩(B ∪C) = (A∩B) ∪(A∩C) A∪(B ∩C) = (A∪B) ∩(A∪C)
记:A×A=A2
2016/6/10 Zhengjin ,CSU 27
（ 1 ）在 A×B 中， A 称为前集， B 称为后集。前集与后 集可以相同，也可以不同。若前集与后集相同，则记 为A×A=A2 。
（2）规定 A×Φ =Φ =Φ ×B。若偶对的第一分量或第 二分量不存在就没有偶对存在，故规定它们的叉积集 合为空集。 （ 3 ）由于偶对中的元素是有序的 ，因此一般地说 A×B≠B×A。(除非A=B，或者A、B中至少有一个为空 集)
提醒:一个集合也可以是别的集合的元素，如： {a， b， {a，b}} {a，b， φ ，{{a，b}}}
2016/6/10 Zhengjin ,CSU 8
集合与集合之间的关系
设A，B是两个集合 1）若对于A中的每个元素x，都有x属于B， 则称A包含在B中，记为:A B。同时称A是B的 子集。 2）若A中的每个元素都属于B，且B中的每个元 素都属于A，则称A等于B，记为A=B。 (A=B 当且仅当AB 且 BA） 3)集合的包含关系具有传递性:即 若A B且B C，则A C
2016/6/10
Zhengjin ,CSU
6
例1
如果论域是整数集 I，那么能被3整除的正整数集合 S 用归纳法可定义如下：
（1）（基础）3S，
（2）（归纳）如果xS和yS，则x+yS
2016/6/10
Zhengjin ,CSU
7
集合的特殊情况
1、不含任何元素的集合称为空集，记为φ 2、含讨论问题所需全部元素的集合称为全集，记为∪ 3、 称含有有限个元素的集合为有限集合 4、 含有无限个元素的的集合称为无限集合或无限集 5、 集合A中元素的个数（或基数或集合的势）记为:|A|
第二章
集 合（set)
集合的概念在现代数学中是一个非常重要的概念。 本节主要介绍集合及其表示、集合的运算，序偶， 集合的笛卡尔乘积。
2016/6/10
Zhengjin ,CSU
1
个体和集合之间的关系
集合不能精确定义，只能直观描述： 一个集合就是若干事物的全体。 组成集合的每个事物叫做这个集合的元素。 小写拉丁字母表示个体：a、b、c、d… 大写拉丁字母表示集合：A、B、C、D…
2016/6/10 Zhengjin ,CSU 9
子集的两种特殊情况（平凡子集）： 1）空集是任一集合的子集。 2）任何集合都是它自己的子集。
2016/6/10
Zhengjin ,CSU
10
例1：确定下列各命题的真假： (a)
(b) (c) {} (d) {} (e) {a，b} {a，b，c，{a，b，c}} (f) {a，b} {a，b，c，{a，b，c}} (g) {a，b} {a，b，c，{a，b}} (h) {a，b} {a，b，c，{a，b}}
(3)谓词表示法
{x︱p(x)} p表示x所满足的性质
例如： {x︱x2=1}={1，-1} {y︱y是开区间(a，b)上的连续函数 }
2016/6/10
Zhengjin ,CSU
5
（4）归纳定义法
用归纳法定义一个非空集合A时，包括以下三步： 1)基本项（保证A不空) 已知某些元素属于A 2)归纳项（生成规则） 给出一组规则，从A中的元素出发，依据这些规则所获得的 元素，仍然都是A中的元素。（这是构造A的关键步骤） 3）极小化（通常省略） 如果集合S也满足（1）和（2），且SA，则S=A。这一 点保证集合A的唯一性。
2016/6/10
Zhengjin ,CSU
24
用集合定义有序偶
定义1 有序偶的集合定义：若x，y为任意两个元素， 令 <x，y>={{x}，{x，y}}
称 <x， y>为由 x， y组成的二元序偶，简称有序偶或序偶。
提醒：此种定义显然体现了二元元素的有序性。但有序 偶的定义不只一种，还有别的定义方法，只要能体现 有序性就可以了
设A和B都是有限集合，则以下公式成立: | A∪B |= | A |+ |B |- | A B | | A B |<=min(| A |， | B |) | AB |= | A |+ |B |- 2| A B | | A -B |>= | A |- | B | | A1∪A2 ∪A3 |= | A 1|+ | A2 |+ | A3 || A1 A2 |- | A2 A3 |- | A1 A3 |+ | A1 A2 A3 |
2016/6/10
Zhengjin ,CSU
13
定理2 设A，B，C为三个集合，则 1）A A∪B， A∩B A； 2）若 A C 且 B C，则 A∪B C； 3）若 C A 且 C B，则 C A∩B 。 4) A-B A 5) A- =A 6) A∩(B-C)= (A∩B)-( A∩C) ；
2016/6/10
Zhengjin ,CSU
3
集合的表示法
(1)文字表示法
用文字表示集合的元素，两端加上花括号。 {在座的同学} {高等数学中的积分公式}
(2) 元素列举法 将集合中的元素逐一列出，两端加上花括号。 { 1，2，3，4，5}， { 风，马，牛 } { 2，4，6，8，10，… }
2016/6/10 Zhengjin ,CSU 4
2016/6/10 Zhengjin ,CSU 26
定义3 设n是正整数，A1，A2，…，An为n个任意集合。 A1×A2×…×An={<x1，x2，…，xn>若1≤i≤n，则xi∈Ai} 称A1×A2×…×An为A1，A2，…，An的n维笛卡尔乘积。
定义4 设A，B是两个非空集合 A×B={<a，b>｜aA ∧ bB} (即所有第一元素在A中，第二元素在B中的序偶的集合) 称A×B是A与B的叉积（笛卡儿积）集合。
定理3 设A，B为两个集合，则下面三式等价。 1）A B 2）A∪B = B 3) A∩B=A
图形表示：
2016/6/10 Zhengjin ,CSU 14
集合上的补运算(一元运算）
设U是全 集，A是U的子集。 ~A={ x xU ∧ xA }=U-A 称~A 是A关于U的补集，称 ~ 为补运算。 例2 设U={a，b，c，d，e}， A={c，d}，则 ~A= 定理4 设U是全 集，A，B是U的子集。则 1 ~ (~ A)=A； 2）若A B，则~ B ~ A； 3）若A = B，则~ A= ~ B ； 4） ~ U= ， ~ =U。 5) A ∪ ~A =U， A ∩ ~A =
2016/6/10 Zhengjin ,CSU 15
定理5 设A，B为两个集合，则 1） ~( A∪B) = ~ A∩ ~ B 2） ~( A∩B) = ~ A∪ ~ B
2016/6/10
Zhengjin ,CSU
16
集合的环和（对称差）运算
设A，B是两个集合， AB = (A-B) ∪ (B-A) = { x︱(xA∧xB) ∨ (xB∧xA) } 称 AB 为A和B的环和，称 为集合环和运算。 定义： 由环和运算和并、差运算的定义知 AB=(A∪B)–(AB)
例：设A={a，b，c，d，e}，B={a，b，c，f，g}，则
2016/6/10
Zhengjin ,CSU
17
幂
集
定义：设A是集合，A的所有子集组成的集合称为A的幂集， 记为 ：2A或p(A)。 2A ={ x x A } 例1：如果A={a，b}，则2A={，{a}，{b}，{a，b}}
2016/6/10
Zhengjin ,CSU
19
有限集计数原理
P68
2016/6/10
Zhengjin ,CSU
20
集合的广义并和广义交
定义 6 ：如果集合 C 中的成员本身又都是集合，则集合C 称 为集类(或称为搜集)。 设C={A1，A2，A3，…An} (1) C的成员的并，记为：∪C，称为C的广义并 ∪C=A1∪A2∪…∪An （2）C的成员的交，记为：∩C，称为C的广义交 ∩C=A1∩A2∩…∩An 例：设A={{1，2，4}，{3，4，5}，{4，6}} 则A广义交：∩A={1，2，4}∩{3，4，5}∩{4，6}=Φ A的广义并：∪A={1，2，4}∪{3，4，5}∪{4，6} 2016/6/10 Zhengjin ={1，2， 3，4,CSU ，5，6}
