# 离散数学
离散数学是研究离散量的结构及其相互关系的数学学科,是计算机科学的理论基础。
# 集合论
集合论是数学的一个基本的分支学科,研究对象是一般集合的性质、结构、关系、运算等
# 集合
定义:集合是指具有某种特定性质的对象组成的集体,构成集合的对象则称为该集合的元素。
# 元素和集合的关系
集合中的元素有三个性质:
- 确定性:集合中的元素必须是明确的,即对于任何一个对象,都能判断它是否属于该集合。例如,集合
{1, 2, 3}
中的元素是明确的,1
属于该集合,而4
不属于。 - 互异性:集合中的元素是互不相同的,不允许出现重复的元素。例如,集合
{1, 2, 3}
和{1, 1, 2, 3}
是相同的。 - 无序性:集合中的元素没有固定的顺序。例如,集合
{1, 2, 3}
和{3, 2, 1}
是相同的。
元素与集合之间的关系用“属于”(
- 如果
是集合 的元素,则记作 。 - 如果
不是集合 的元素,则记作 。
集合本身也可以作为元素,例如 { {1, 2}, {3, 4} }
,这两个集合是整个大集合的元素
# 空集
定义:不含任何元素的集合称作空集,记作
- 空集是任何集合的子集:对于任意集合
,都有 - 空集与任何集合的交集仍为空集:
- 空集与任何集合的并集为该集合本身:
- 空集的幂集(即由空集的所有子集构成的集合)为
,这是一个只包含空集的集合
# 集合的基本运算
运算规则 | 符号 | 说明 | 示例 |
---|---|---|---|
并集 | 若 A = {1, 2, 3} 和 B = {2, 3, 4} ,则 {1, 2, 3, 4} | ||
交集 | 若 A = {1, 2, 3} 和 B = {2, 3, 4} ,则 {2, 3} | ||
差集 | 若 A = {1, 2, 3} 和 B = {2, 3, 4} ,则 {1} | ||
补集 | 若 E = {1, 2, 3, 4, 5} 和 A = {1, 2, 3} ,则 {4, 5} | ||
对称差集 | 若 A = {1, 2, 3} 和 B = {2, 3, 4} ,则 {1, 4} | ||
笛卡尔积 | 若 A = {1, 2} 和 B = {a, b} ,则 {(1, a), (1, b), (2, a), (2, b)} |
# 集合的运算性质
- 幂等律:
; - 交换律:
; - 结合律:
; - 零律:
; - 同一律:
; - 分配律:
; - 吸收律:
; - 对合率:
- 排中率:
- 矛盾率:
- 德摩根定律:
;