集合论 王智慧 复旦大学计算机学院
1 集合论 王智慧 复旦大学计算机学院
二元关系 有序对与笛卡儿积 二元关系 关系的运算 关系的性质 关系的闭包 等价关系与划分 偏序关系
2 二元关系 • 有序对与笛卡儿积 • 二元关系 • 关系的运算 • 关系的性质 • 关系的闭包 • 等价关系与划分 • 偏序关系
有序对 由两个元素x和y按一定顺序排列成的二元组叫做一个有 序对或序偶 Ordered pair),记作,其中x是它的第 元素,y是它的第二元素 有序对具有以下性质: 当x≠y时,x,y>≠; =的充分必要条件是x=u且y=v 有序对中的元素是有序的,而集合中的元素是无序的 例如:当x≠y时,有{x,y}={y,X}.但是x,y>≠<y,x 3
3 有序对 z 由两个元素x和y按一定顺序排列成的二元组叫做一个有 序对或序偶(Ordered Pair), 记作, 其中x是它的第 一元素, y是它的第二元素. z 有序对具有以下性质: ¾ 当x ≠ y时, ≠ ; ¾ = 的充分必要条件是x = u且y = v. z 有序对中的元素是有序的, 而集合中的元素是无序的. ¾ 例如: 当x ≠ y时, 有{ x, y } = { y, x }. 但是 ≠
笛卡儿积 设A和B为集合,以A中元素为第一元素,B中元素为 第二元素构成有序对;所有这样的有序对组成的集合 叫做A和B的笛卡儿积( Cartesian product/ Product Set),记作AxB. ●笛卡儿积的符号化表示为: A×B={|x∈A,y∈B} 例如,设A={a,b},B={0,1,2},则 A×B={,,,,,} B×A={,,,,,} 由排列组合的知识不难证明,如果A|=m,|B=n,则 A×B|=m*n
4 笛卡儿积 z 设A和B为集合, 以A中元素为第一元素, B中元素为 第二元素构成有序对;所有这样的有序对组成的集合 叫做A和B的笛卡儿积(Cartesian Product/Product Set), 记作A × B. z 笛卡儿积的符号化表示为: A × B = { | x∈A, y∈B } z 例如, 设A = { a, b }, B = { 0, 1, 2 }, 则 ¾ A × B = { , , , , , } ¾ B × A = { , , , , , } z 由排列组合的知识不难证明, 如果|A| = m, |B| = n, 则 |A × B| = m*n
笛卡儿积 笛卡儿积运算具有以下性质 性质1:对任意集合A,根据定义有 A×φ=φ,φ×A=φ 性质2:不满足交换律,即 A×B≠BXA(当A≠B,A≠中B≠中时) 性质3:不满足结合律,即 (AxB)×C≠Ax(B×C)(当A≠中,B≠,C≠中时)
5 笛卡儿积 z 笛卡儿积运算具有以下性质: ¾ 性质1: 对任意集合A, 根据定义有 A × φ = φ, φ × A = φ ¾ 性质2: 不满足交换律, 即 A × B ≠ B × A (当A ≠ B, A ≠ φ, B ≠ φ时) ¾ 性质3: 不满足结合律, 即 (A × B) × C ≠ A × (B × C) (当A ≠ φ, B ≠ φ, C ≠ φ时)
笛卡儿积 笛卡儿积运算具有以下性质 性质4:对并和交运算满足分配律,即 (1)A×(BUO)=(A×B)∪U(A×C (2)(BUC)XA=(B×A)U(C×A) (3)A×(B∩C)=(4×B)n(A×C) (4)(BnC×A=(B×A)n(C×A)
6 笛卡儿积 z 笛卡儿积运算具有以下性质: ¾ 性质4: 对并和交运算满足分配律, 即 (1) A × (B∪C) = (A × B)∪(A × C) (2) (B∪C) × A = (B × A)∪(C × A) (3) A × (B∩C) = (A × B)∩(A × C) (4) (B∩C) × A = (B × A)∩(C × A)
笛卡儿积 笛卡儿积运算具有以下性质 性质5:AcC∧BcD→A×BgC×D 性质5的证明和性质4类似,也采用命题演算的方法 注意性质5的逆命题不成立,可分多种情况来讨论 A=B=φ >A≠φ,B≠中 A=,B≠φ A≠中,B=φ
7 笛卡儿积 z 笛卡儿积运算具有以下性质: ¾ 性质5: A ⊆ C∧B ⊆ D ⇒ A × B ⊆ C × D ¾ 性质5的证明和性质4类似, 也采用命题演算的方法. z 注意性质5的逆命题不成立, 可分多种情况来讨论. ¾ A=B= φ ¾ A≠ φ, B ≠ φ ¾ A =φ, B ≠ φ ¾ A≠ φ, B = φ
笛卡儿积 例:设A={1,2},求P(A)×A 解:由幂集可知:P(A)={￠,{1},{2},{1,2}} P(A)×A {,, ,, {1,2},2>}
8 笛卡儿积 例: 设A = { 1, 2 }, 求P(A) × A. 解: 由幂集可知: P(A) = { φ, { 1 }, { 2 }, { 1, 2 } } P(A) × A = { , , , , , , , }
笛卡儿积 例:设A,B,C,D为任意集合,判断以下命题是否为真,并 说明理由 >(1)A×B=A×C→B=C 2)A-(B×C)=(A-B)×(A-C) >(3)A=B∧C=D→A×C=B×D >(4)存在集合A,使得: ACAXA 解: (1)不一定为真当A=中B={1},C={2}时, 有:AxB=AxC=,但,B≠C (2)不一定为真当A=B={1},C={2}时, A-(B×C)={1}-{}={1} (A-B)×(A-C)=φ×{2}=φ (3)真.因为A=B,所以有AxC=B×C又因为C=D,所 以有A×C=B×D (4)真当A=时,有:A三AxA成立
9 笛卡儿积 z 例: 设A, B, C, D为任意集合, 判断以下命题是否为真, 并 说明理由. ¾ (1) A × B = A × C ⇒ B = C ¾ (2) A - (B × C) = (A - B) × (A - C) ¾ (3) A = B∧C = D ⇒ A × C = B × D ¾ (4) 存在集合A, 使得: A ⊆ A × A 解: (1) 不一定为真.当A = φ, B = { 1 }, C = { 2 }时, 有: A × B = A × C = φ, 但, B ≠ C. (2) 不一定为真.当A = B = { 1 }, C = { 2 }时, A - (B × C) = { 1 } - { } = { 1 } (A - B) × (A - C) = φ × { 2 } = φ (3) 真. 因为A = B,所以有A × C = B × C.又因为C=D,所 以有A × C = B × D. (4) 真.当A = φ时, 有: A ⊆ A × A成立
二元关系 若一个集合满足以下条件之 (1)集合非空,且它的元素都是有序对 (2)集合是空集 则称该集合为二元关系( Binary relation),记作R. ·二元关系也可简称为关系若∈R,可记作:xRy;否 则,记作:xRy 例如:R1={,},R2={,a,b},则R是 二元关系,R2不是二元关系
10 二元关系 z 若一个集合满足以下条件之一: (1) 集合非空, 且它的元素都是有序对 (2) 集合是空集 则称该集合为二元关系(Binary Relation), 记作R. z 二元关系也可简称为关系. 若∈R, 可记作: xRy;否 则, 记作: xRy. z 例如: R1 = { , }, R2 = { , a, b }, 则R1是 二元关系, R2不是二元关系