第四章二元关系 4.1二元关系及其表示法 4.1.1序偶与笛卡尔积 定义4.1:由两个元素x和y按一定的次序组成的二 元组称为有序对或序偶( Ordered),记作<x,y> 其中x是它的第一元素,y是它的第二元素。 性质4.1:(1):<x,y>=<y,x>当且仅当ⅹ=y; (2):<x,y>=<u,>当且仅当x=u,y=Vv; 例如:平面上的坐标<x,y>,ⅹ,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>x∈A∧y∈B} 为集合A与B的 笛卡尔积 Descartes product)。 例:设A=1,2;B={a,b则A×B=1,a>,<1b, a>,<2,b为;B×A〖<a,1>,<a,2>,<b, 质4.2:( A×B|=|A×|B(A,B为有限 A×O=0,0×A=O (3).不适合交换律,即A×B≠BXA(除非A,B=O 或A=B); 非A=O 倉律 (4).不适合结合 (A×B)×G≠A×(B×C(除 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二元关系及其表示法 Ax(B∪C)=(A×B)∪(AxC)(B∪C)xA=(B×A∪(C×A) A×(B∩C)=(A×B)∩(AxC)(B∩C)xA=(B×A∩C×A); 证明:<x,y>∈Ax(BUC >x∈A∧y∈B∪C →x∈AA(y∈BVy∈C) 分(x∈Ay∈B)v(x∈A∧y∈C <x,y>∈(A×B)V<x,y>∈(AxC) <x,y>∈(AxB)∪(A×C) (6)AcC∧BcD→A×BC×D,且当A=B=O 或A≠0∧B≠O时,逆命题成立。 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≥2)元组是一个有序对, 它的第一个元素为有序的n1元组<a1,m2 ,第二个元素为an,记为<a1,a2,…,an12an 即 a <<a,a2,,an-1un ∠C1 2 <b,b2…,bn>; 当且仅当a=b,i=1,2,…,n n维空间中的点M的坐标(x12x2…,x)为有序的n元组 定义4.4:设A1,A2 为n个集合(n≥2),称集 合{x12x2…,xnx1∈A1∧x2∈A2A…Axn∈An} 为n维卡氏积或n阶笛卡尔积,记作A1xA2x…×A, 当A1=A2=…=A时简记为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中的全体元素为有序的nn≥2 元组,则称F为n元关系,特别地,当n=2时,称F 为二元关系,简称关系。 对于二元关系F,若<x,y>∈F,常记作xhy,反之 xy;规定O为n元空关系,也是二元空关系,简称 空关系 定义4.6:设A,B为两集合,A×B的集合子集R称 为A到B的二元关系,特别地,当A=B时,称R为A上 的二元关系。 例:A={a,b},B={o},则AXB的子集有0, <a,c),〖<b,c习},〖a,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