东北大学：《离散数学》课程教学资源（PPT课件讲稿）第四章 二元关系

另外 (A×B)×C={<<a,b>c>ab>∈ AXB AC∈C} Ax(BxC){<a,<b,c>>a∈A入<bc>∈BxC}, 因<a<b,c>不是有序三元组, 所以(AXB)XC≠A×(B×C 故x也不满足结合律 2.性质 1)如果A、B都是有限集,且A=m,|Bn,则 A×Bmn 证明:由笛卡尔积的定义及排列组合中的乘法原 理,直接推得此定理 2)A×=①×B=①

另外 (AB)C={<<a,b>,c>|<a,b>AB cC} A(BC)={<a,<b,c>>|aA <b,c>BC}, 因 <a,<b,c>>不是有序三元组, 所以(AB)CA(BC)。 故也不满足结合律。 2.性质 1) 如果A、B都是有限集，且|A|=m, |B|=n，则 |AB |=mn. 证明：由笛卡尔积的定义及排列组合中的乘法原 理，直接推得此定理。 2) AΦ=ΦB=Φ

3)×对U和∩满足分配律。 设A,BC是任意集合,则 (1)A×(B∪C)=(A×B)∪(A×C); (2)Ax(B∩C)=(A×B)∩(A×C); (3)(A∪B)XC=(AXC)∪(B×C); (4)(A∩B)xC=(A×C)n(B×C 证明(1):任取<xy>∈Ax(BUC) 台X∈A~y∈B∪C分X∈A∧(y∈BVy∈C) 台(X∈ANy∈B)V(X∈Ay∈C 冷冷<Xy>∈A×BV<xy>∈A×C 台<xy>∈(AxB)∪(AxC)所以()式成立。 其余可以类似证明

3) 对∪和∩满足分配律。 设A,B,C是任意集合，则 ⑴ A(B∪C)= (AB)∪(AC)； ⑵ A(B∩C)= (AB)∩(AC)； ⑶ (A∪B)C= (AC)∪(BC)； ⑷ (A∩B)C= (AC)∩(BC) 证明⑴ ：任取<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) 所以⑴式成立。 其余可以类似证明

4若C≠①,则 A∈B冷(A×CcB×C)冷( CXACCXB) 证明:必要性:设AcB,求证 AxCcBXC 任取<xy>∈AxC分x∈Ay∈C →X∈BNy∈C(因AcB) 台<x,y>∈BxC所以,AxC≤B×C 充分性:若C西Φ,由 AXCcBXO求证AcB 取C中元素y任取x∈A→X∈Ay∈C <Xy>∈A×C →<x2y>∈BxC(由 AxCcBXO) 台→X∈BNy∈C→X∈B所以,AcB 所以AcB台→( AXCcBXC) 类似可以证明AB台> CxACCxB)

4)若C,则 AB(ACBC) (CACB). 证明: 必要性： 设AB，求证ACBC 任取<x,y>AC xAyC xByC (因AB) <x,y>BC 所以, ACBC. 充分性： 若C, 由ACBC 求证 AB 取C中元素y, 任取 xAxAyC <x,y>AC <x,y>BC (由ACBC ) xByCxB 所以, AB. 所以 AB(ACBC) 类似可以证明 AB (CACB)

5)设A、B、C、D为非空集合,则 A×B<C×D<→AC∧BcD 证明:首先,由A×BCXD证明AcC∧BD 任取x∈A,任取y∈B,所以 X∈Ay∈B 冷<X2y>∈A×B →<xy>∈CXD(由A× BECXD) >X∈CNy∈D所以,A≌C∧B<D 其次,由AcC,B<D.证明 AXBCO×D 任取<xy>∈A×B <Xy>∈A×B分X∈Ay∈B →x∈ CAyED(由AcC,BD) 台xxy>∈C×D所以, AXBCCXD证毕

5) 设A、B、C、D为非空集合，则 ABCDAC∧BD. 证明: 首先,由ABCD 证明AC∧BD. 任取xA，任取yB，所以 xAyB <x,y>A×B <x,y>C×D (由ABCD ) xCyD 所以, AC∧BD. 其次, 由AC，BD. 证明ABCD 任取<x,y>A×B <x,y>A×B  xAyB  xCyD (由AC，BD) <x,y>C×D 所以, ABCD 证毕

6)约定 (…(A1×A2)××An21)XAn)=A1×A2××An 特别AxAx.×A=A 设R是实数集合,则R2表示笛卡尔坐标平面, R3表示三维空间,R表示n维空间 3应用 1)令A1={xx是学号}A2={xx是姓名}A3={男,女} A:={xx是出生日期}A5={xx是班级}A6={xx是籍贯} 则A1XA2×A3×AxA×A6中一个元素: <001,王强,男,1981:02:16,计2001-1,辽宁 这就是学生档案数据库的一条信息,所以学生 的档案就是AA2XA3×A4×A×A的一个子集

6)约定 (…(A1A2 )…An-1 )An )=A1A2…An 特别 AA…A = An 设R是实数集合，则R2表示笛卡尔坐标平面， R3表示三维空间，Rn表示n维空间。 3.应用 1)令A1={x|x是学号} A2={x|x是姓名} A3={男,女} A4={x|x是出生日期} A5={x|x是班级} A6 ={x|x是籍贯} 则A1A2A3 A4A5 A6中一个元素： <001，王强，男，1981:02:16，计2001-1，辽宁> 这就是学生档案数据库的一条信息，所以学生 的档案就是A1A2A3 A4A5 A6的一个子集。 n 个