第四章二元关系 4.1二元关系及其表示法 4.1.1序偶与笛卡尔积 ● 定义4.1：由两个元素x和y按一定的次序组成的二 元组称为有序对或序偶(0 rdered),记作<x,y>, 其中x是它的第一元素，y是它的第二元素。 ·性质4.1：(1)：<x,y>=<y,x>当且仅当x=y; (2):<x,y>=<u,V>当且仅当x=u,y=v; 例如：平面上的坐标<x,y>,x,y∈R;<操作码， 地址码>等都是序偶。 1157
1/57 第四章 二元关系 4.1 二元关系及其表示法 4.1.1 序偶与笛卡尔积 • 定义4.1：由两个元素x和y按一定的次序组成的二 元组称为有序对或序偶(Ordered)，记作<x, y>， 其中x是它的第一元素，y是它的第二元素。 • 性质4.1：(1)： <x, y>= <y, x>当且仅当x=y； (2)： <x, y>=<u, v>当且仅当x=u, y=v; 例如：平面上的坐标<x, y>，x, y R；<操作码， 地址码>等都是序偶。
4.1二元关系及其表示法 定义4.2：设A,B是两个集合，称集合 A×B={<x,y>lx∈A∧y∈B} 为集合A与B的 笛卡尔积(Descartes Product)。 ，品安 2, a> 1>,<6 2>}。 性质4.2：(1).AB=A×B|A,B为有限 ●1 集合)； (2.A×0=0,0×A=0 (3).不适合交换律，即AXB≠BXA(除非A,E =0 或A=B); (4).不适合结合律， (AXB)XC丰AX(BXC)(除 非A=⑩VB=⑦VC=D); (5).对U和∩运算满足分配律， 2/57
2/57 4.1 二元关系及其表示法 •定义4.2：设A，B是两个集合，称集合 为集合A与B的 笛卡尔积(Descartes Product)。 例：设A={1,2}；B={a, b}则A ×B={<1,a>，<1,b>， <2,a>，<2,b>}；B ×A={<a, 1>，<a, 2>，<b, 1>，<b, 2>}。 •性质4.2：(1). | A ×B |=|A|×|B|(A, B为有限 集合)； (2). ； (3). 不适合交换律，即A×B ≠B×A(除非A，B= 或A=B)； (4). 不适合结合律，(A×B)×C ≠A×(B×C)(除 非 )； (5). 对∪和∩运算满足分配律， A B ={ x, y | x A y B} A = ， A = A = B= C=
4.1二元关系及其表示法 A×(BUC)=(A×B)U(A×C),(BUC)×A=(B×A)U(C×A) A×(B∩C)=(A×B)∩(A×C),(B∩C)×A=(B×A)∩(C×A) 证明：<x,y>∈A×(BUC) 台x∈AAy∈BUC 台x∈AA(y∈BVy∈C) 台(x∈AAy∈B)V(x∈A∧y∈C) 台<x,y>∈(A×B)V<x,y>∈(A×C) →<x,y>∈(A×B)U(A×C) (6).ACCABED→A×BC×D,且当A=B=0 或A≠①人B≠①时，逆命题成立。 3/57
3/57 4.1 二元关系及其表示法 证明： (6). ，且当 或 时，逆命题成立。 (B C ) (A B) (A C),(B C ) A (B A) (C A); (B C ) (A B) (A C),(B C ) A (B A) (C A), = = = = A A , ( ) ( ) , ( ) , ( ) ( ) ( ) ( ) , ( ) x y A B A C x y A B x y A C x A y B x A y C x A y B y C x A y B C x y A B C A CB D AB CD A = B= A B
4.1二元关系及其表示法 定义4.3：一个有序n(n≥2)元组是一个有序对， 它的第一个元素为有序的n-1元组<41,2，，am-1> ,第二个元素为an,记为<a1,2,…,am-1,am> 即：<a1,a2,…,an1>,an>=<4,42,…,am> <a41,a2,…,an>=<b,b2,…,bn>; 当且仅当4，=b,i=1,2,…,n n维空间中的点M的坐标(x,x2,…,xm)为有序的n元组 <X1,X22…,Xn> 定义4.4：设A1,A2,…,An为n个集合(n≥2），称集 合{<x1,x2,…,xn>X1∈A∧x2∈A2∧…∧n∈An} 为n维卡氏积或n阶笛卡尔积，记作A×A,××A, 当A1=A,=…=An时简记为A”。 4/57
4/57 4.1 二元关系及其表示法 •定义4.3：一个有序n(n≥2)元组是一个有序对， 它的第一个元素为有序的n-1元组 ，第二个元素为 ，记为 即： ； 当且仅当 n维空间中的点M的坐标 为有序的n元组 。 • 定义4.4：设 为n个集合(n ≥2)，称集 合 为n维卡氏积或n阶笛卡尔积，记作 ， 当 时简记为 。 a1 ,a2 , ,an−1 n a a1 ,a2 , ,an−1 ,an a1 ,a2 , ,an−1 ,an = a1 ,a2 , ,an a1 ,a2 , ,an = b1 ,b2 , ,bn ai = bi ,i =1,2, ,n ( , , , ) 1 2 n x x x x1 , x2 , , xn A A An , , , 1 2 { , , , | } 1 2 n 1 1 2 2 n An x x x x A x A x A1 A2 An A1 = A2 == An n A
4.1二元关系及其表示法 4.1.2二元关系 ● 定义4.5：若集合F中的全体元素为有序的n(n≥2) 元组，则称F为n元关系，特别地，当n=2时，称F 为二元关系，简称关系。 对于二元关系F,若<x,y>eF, 常记作xy,反之 xy;规定0为n元空关系， 也是二元空关系，简称 空关系。 定义4.6：设A,B为两集合， ● AXB的集合子集R称 为A到B的二元关系，特别地，当A=B时，称R为A上 的二元关系。 例：A={a,b},B={c}, 则AXB的子集有O {Ka,c>},{Kb,c>},{Ka,c>,<b,c>}, 5/57
5/57 4.1 二元关系及其表示法 4.1.2 二元关系 •定义4.5：若集合F中的全体元素为有序的n(n≥2) 元组，则称F为n元关系，特别地，当n=2时，称F 为二元关系，简称关系。 对于二元关系F，若 ，常记作 ，反之 ；规定 为n元空关系，也是二元空关系，简称 空关系。 •定义4.6：设A，B为两集合，A×B的集合子集R称 为A到B的二元关系，特别地，当A=B时，称R为A上 的二元关系。 例：A={a, b}，B={c}，则A×B的子集有 ， {<a, c>}，{<b, c>}，{<a, c>, <b, c>}， x, y F xFy xF y