离散数学有序对与笛卡尔积.ppt

牡丹江师范学院本科生课程 1.1 序偶与笛卡尔积 理学院 季丹丹 § 序偶 与笛卡儿积 定义 1 元素 x 和 y 按一定顺序排成的二元组叫做一个 有序对或序偶，记作 x,y ，其中 x 、 y 分别为第 一、第二元素。 有序对 x,y 具有的性质： （ 1 ）当x≠y时，x,y≠y,x . （ 2 ） x,y ＝ u,v 的充要条件是 x ＝ u 且 y ＝ v. 例 7.1 例 1 已知 x+2,4 ＝ 5,2x+y ，求 x 和 y. 解 : 由有序对相等的充要条件有 x+2=5 且 2x+y ＝ 4, 解得 x ＝ 3,y ＝ -2. 定义 2 设 A ， B 为集合 , 令 A 中元素为第一元素， B 中元素为第二元素的 有序对，构成的集合叫 A 和 B 的笛卡儿积。 笛卡儿积表示为 A × B ＝{x,y|x∈A∧y∈B} . 笛卡儿积的定义 笛卡尔积举例 设 A={a,b}, B={0,1,2} ，则 A × B={a,0,a,1,a,2,b,0,b,1,b,2}. B × A={0,a,0,b,1,a,1,b,2,a,2,b}. 举例 说明 ? 如果 |A|=m,|B|=n, 则 |A × B|=mn. 笛卡儿积的运算性质 (1) 对任意集合 A ，根据定义有 A × ? ＝ ? , ? × A ＝ ? . (2) 一般，笛卡儿积运算不满足交换律，即 A ×B≠B× A( 当 A≠ ? ∧ B≠ ? ∧ A≠B 时 ) 。 (3) 笛卡儿积运算不满足结合律，即 (A × B) ×C≠A× (B × C)( 当 A≠ ? ∧B≠ ? ∧C≠ ? 时 ) 。 (4) 笛卡儿积运算对并和交运算满足分配律，即 A ×(B∪C)=(A×B)∪(A× C). (B∪C)× A=(B ×A)∪(C× A). A ×(B∩C)=(A×B)∩(A× C). (B∩C)× A=(B ×A)∩(C× A). (5)A ? C ∧ B ? D ? A × B ? C × D. A ×(B∪C)=(A×B)∪(A× C) 的证明 任取 x,y, x,y∈A×(B∪C) ? x∈A ∧ y∈B∪C ? x∈A ∧ (y∈B∨y∈C) ? (x∈A∧y∈B) ∨ (x∈A∧y∈C) ? x,y∈A×B ∨ x,y∈A× C ? x,y∈(A×B)∪(A× C) 所以 A ×(B∪C)=(A×B)∪(A× C). 例 2 例 2 设 A={1,2}, 求 P(A) × A. P(A) × A ＝ { ? 2}} × {1,2} ＝ { ? ,1, ? ,2, {1},1,{1},2, {2},1,{2},2, {1,2},1,{1,2},2}. 解答 例 3 例 3 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,2} ＝ {1}, (A-B) × (A-C) ＝ ? × {1} ＝ ? . (3) 为真。由等量代入的原理可证。 (4) 为真。当 A ＝ ? 时，有 A ? A × A 成立。 解答