# 离散数学

离散数学是研究离散量的结构及其相互关系的数学学科,是计算机科学的理论基础。

# 集合论

集合论是数学的一个基本的分支学科,研究对象是一般集合的性质、结构、关系、运算等

# 集合

定义:集合是指具有某种特定性质的对象组成的集体,构成集合的对象则称为该集合的元素。

# 元素和集合的关系

集合中的元素有三个性质:

  • 确定性:集合中的元素必须是明确的,即对于任何一个对象,都能判断它是否属于该集合。例如,集合 {1, 2, 3} 中的元素是明确的,1 属于该集合,而 4 不属于。
  • 互异性:集合中的元素是互不相同的,不允许出现重复的元素。例如,集合 {1, 2, 3}{1, 1, 2, 3} 是相同的。
  • 无序性:集合中的元素没有固定的顺序。例如,集合 {1, 2, 3}{3, 2, 1} 是相同的。

元素与集合之间的关系用“属于”()或“不属于”()表示。例如:

  • 如果 x 是集合 A 的元素,则记作 xA
  • 如果 x 不是集合 A 的元素,则记作 xA

集合本身也可以作为元素,例如 { {1, 2}, {3, 4} } ,这两个集合是整个大集合的元素

# 空集

定义:不含任何元素的集合称作空集,记作

  • 空集是任何集合的子集:对于任意集合 A,都有 A
  • 空集与任何集合的交集仍为空集:A=
  • 空集与任何集合的并集为该集合本身:A=A
  • 空集的幂集(即由空集的所有子集构成的集合)为 ,这是一个只包含空集的集合

# 集合的基本运算

运算规则 符号 说明 示例
并集 AB 表示 AB 中的所有元素组成的集合 A = {1, 2, 3}B = {2, 3, 4},则 AB = {1, 2, 3, 4}
交集 AB 表示同时属于 AB 的元素组成的集合 A = {1, 2, 3}B = {2, 3, 4},则 AB = {2, 3}
差集 AB 表示属于 A 但不属于 B 的元素组成的集合 A = {1, 2, 3}B = {2, 3, 4},则 AB = {1}
补集 A 表示属于全集 E 但不属于 A 的元素组成的集合 E = {1, 2, 3, 4, 5}A = {1, 2, 3},则 A = {4, 5}
对称差集 AB 表示所有属于 AB 但不属于 AB 交集的元素组成的集合 若 A = {1, 2, 3} 和 B = {2, 3, 4},则 AB = {1, 4}
笛卡尔积 × A×B 表示所有可能的有序对 (a,b) 组成的集合,其中 aAbB A = {1, 2}B = {a, b},则 A×B = {(1, a), (1, b), (2, a), (2, b)}

AB=(AB)(BA)=(AB)(AB)

A=EAEAE

# 集合的运算性质

  • 幂等律:AA=AAA=A
  • 交换律:AB=BAAB=BA
  • 结合律:(AB)C=A(BC)(AB)C=A(BC)
  • 零律:AE=EA=
  • 同一律:A=AAE=A
  • 分配律:A(BC)=(AB)(AC)A(BC)=(AB)(AC)
  • 吸收律:A(AB)=AA(AB)=A
  • 对合率:(A)=A
  • 排中率:A(A)=E
  • 矛盾率:A(A)=
  • 德摩根定律:(AB)=(A)(B)(AB)=(A)(B)

# 关系及其性质