计算机科学与技术专业·集合论与图论.pdf

计算机科学与技术专业 ·集合论与图论 第二讲 关 系 周 晓 聪 中山大学计算机科学系软件工程实验室 2008年9 月 /∼zxc isszxc@ 周 晓 聪 ( 中山大学计算机科学系) 离散数学基础 ·集合论与图论 2008年9 月 1 / 33 内容提要 1 关系的基本概念 2 二元关系的性质 3 二元关系的闭包 4 等价关系 5 偏序关系 周 晓 聪 ( 中山大学计算机科学系) 离散数学基础 ·集合论与图论 2008年9 月 2 / 33 关系的基本概念 关系基本概念 有序对和n元组 − 有序对：a, b = {{a}, {a, b}}； − a, b = c, d ⇔ a = c ∧ b = d ； − n元组：a , a , · · · , a = a , · · · , a , a 。 1 2 n 1 n −1 n 笛卡尔积 − A ×B = {a, b | a∈A ∧ b∈B}； − A ×A ×· · ·×A = {a , a , · · · , a | a ∈A , 1 ≤ i ≤ n} 1 2 n 1 2 n i i 笛卡尔积的基本性质 − A ×∅ = ∅, ∅×A = ∅； − 不适合交换律和结合律 − 笛卡尔积对并、交分配：A ×(B ∪ C) = (A ×B) ∪ (A ×C)； − A ⊆ C ∧ B ⊆ D ⇒ A ×B ⊆ C×D ； − A ×B = C×D ⇔ ∀a, b(a, b∈A ×B ↔ a, b∈C×D)。 周 晓 聪 ( 中山大学计算机科学系) 离散数学基础 ·集合论与图论 2008年9 月 3 / 33 关系的基本概念 关系基本概念举例 关系基本概念举例 写出三元组a, b, c和a, b, c的集合表达式，这两者相等吗？ 什 么条件下，下列等式成立？ − A ×B = ∅ − A ×B = B ×A − A ×(B ×C) = (A ×B)×C 设A ,B , C是任意集合，证 明下列等式成立： − (A − B)×C = (A ×C) − (B ×C) − (A ⊕ B)×C = (A ×C) ⊕ (B ×C) 设|A | = n, |B | = m ，A 到B 共有 多少个不同的二元关系？ 设A = {a, b, c},B = {1}，写出A 到B和B 到A 的全部二元关系。 周 晓 聪 ( 中山大学计算机科学系) 离散数学基础 ·集合论与图论 2008年9 月 4 / 33 关系的基本概念 关系基本概念举例 写出三元组a, b, c和a, b, c的集合表达式，这两者相等吗？ − a, b, c = a, b, c = {{{a}, {a, b}}, {{{a}, {a, b}}, c}} − a, b, c = {{a}, {a, {{b}, {b, c}}}} − 显然这两者不相等 什 么条件下，下列等式成立？ − A ×B = ∅ ◦ A = ∅或B = ∅ − A ×B = B ×A