恭喜你完成了数理逻辑的学习，现在迎接你的是更大的一坨：集合论。记得高中学过的集合吧。对，跟那玩意没多大关系，你很快就会知道了。

---

第6章 集合代数

6-1 集合的基本概念

• 集合这个概念无法被精确定义。它将一系列具有相同属性的元素汇集成为一个整体。这些事物是这个集合的元素或成员。 表示集合有两种方法：列元素法和谓词表示法。 集合的元素不重复，且集合是无序的
• 设A，B为集合，若B中的每个元素都是A的元素，称B是A的子集，称B被A包含，或A包含B，记作B ⊆ A（不被包含：B⊈A）。
• 如果A ⊆ B且B ⊆ A，则A=B，称A，B相等。
• 如果B ⊆ A且B ≠ A，称B是A的真子集，记作B ⊂ A。
• 空集∅不包含任何元素，是任何元素的子集，且唯一。
• 含有n个元素的集合称为n元集。
• A的全体子集构成的集合称为A的幂集，记作P(A)。若A是n元集，则P(A)有2n个元素。

6-2 集合的运算

• 并集A ∪ B、交集A ∩ B 相对补集：A − B，即A中有但B中没有的符号，可以理解为减号。 绝对差集：A ⊕ B，AB并集减去AB交集，即两个相对补集的并集 。 绝对补集：~A，给定全集E，绝对补集就是E对A的相对补集。
• 广义交：∩A，A中所有元素的公共元素构成的集合，例如：

$$ A={a, {c, d},{c}}\ \cap A = a\cap{c} $$

• 广义并：∪A，如果A的元素是集合，广义并A是A中集合元素之和。
• 空集的广义并仍是空集。空集不能进行广义交。
• 广义交，广义并，P(A)的优先级大于∩, ∪, −, ⊕。

6-3 有穷集的计数

• 集合的关系和初级运算可以通过文氏图表现。
• 有穷集的计数问题可以通过包含排斥原理求解。具体过程请看书。

6-4 集合恒等式

和公式、一阶逻辑一样，集合也有用于逻辑推理的恒等式。下面的恒等式列出了集合运算的主要算律。

• 幂等律

$$ A \cap A = A\ A \cup A = A $$

• 结合律，交换律
• 分配律

$$ A \cap (B \cup C) = (A\cap B) \cup (A\cap C)\ A \cup (B \cap C) = (A\cup B) \cap (A\cup C) $$

• 同一律

$$ A \cap E = A \ A \cup \emptyset = A $$

• 零律

$$ A \cap \emptyset = \emptyset\ A \cup E = E $$

• 排中律
• 矛盾律
• 吸收律

$$ A \cap(A \cup B) = A\ A \cup(A \cap B) = A $$

• 德摩根律

  由于没找到~对应的公式符号，而且直接打的话会消失，所以排中律，矛盾律和德摩根律请至书中101页

第7章 二元关系

7-1 有序对与笛卡尔积

• 将两个元素x和y按照一定顺序排列成的二元组称作一个有序对，记作<x,y>，其中x是它的第一元素，y是第二元素。将x，y颠倒组成的新有序对与原来的不相等。
• 设A，B是集合，用A中的元素为第一元素，B中的元素为第二元素组成的有序对称作笛卡尔积，记作A × B。
• 对于一般的集合，空集和A的笛卡尔积仍未空集。 一般来说，笛卡尔积不满足交换律，不满足结合律，但满足交换律。

7-2 二元关系

• 将一个元素都是有序对的非空集合或空集称为二元关系（简称关系）。记作R0，如果 < x, y > ∈ R则有xRy。
• 设A，B为集合，则AxB的任意子集所定义的二元关系称作从A到B的二元关系。特别地当A=B时称为A上的二元关系，∅称为A的空关系。
• 全域关系EA是指AxA中除却空集外的所有关系的集合。 如A={ 1, 2 }，EA = { < 1, 1>, < 1, 2>, < 2, 1>, < 2, 2 > }
• 恒等关系IA是A中单个元素组成的关系，如IA = { < 1, 1>, < 2, 2 > }
• 小于等于关系LA是<x, y>且x≤y。
• 整除关系DA是<x, y>，且y能被x整除。
• 设R的关系矩阵的第i，j元素为0时xi，xj不满足R关系；为1时满足R关系。
• R的关系图记作GR。如果xiRxj成立，就有一条线从xi指向xj。

7-3 关系的运算

• R中有序对第一元素的集合为R的定义域，记作domR。 R中有序对第二元素的集合为R的值域，记作ramR。 定义域和值域的并集称为R的域，记作fldR。
• R的逆关系为R−1，就是将x，y颠倒位置。 < x, y > → < y, x>。
• 设F，G为二元关系，G对F的右复合记作F ∘ G。有点像合并两个二元关系 < 1, 2 > < 2, 3 > → < 1, 3>。 用符号表示为： F ∘ G = { < x, y > | ∃t( < x, t >  ∈ F ∧ < t, y >  ∈ G)} 亦可以定义左复合，不做赘述。
• R在A的限制，记作R ↑ A，指R中<x, y>且x在集合A中。
• R在A的像，记作R[A]，即ran(R ↑ A)，就是上面定义中的y。 ⊆  ⊈  ⊂  ⊂ ∅ ∪ ∩ ⊕ × ∈ F ∘ G↑