二元关系 (1)

电子科技大学离散数学课程组——国家精品课程离散数学任课教师：杨春2020年1月21日星期二数学科学学院电子科技大学离散数学课程组——国家精品课程150-22020/1/21第三篇二元关系关系理论历史悠久。它与集合论、数理逻辑、组合学、图论和布尔代数都有密切的联系。关系是日常生活以及数学中的一个基本概念，例如：兄弟关系，师生关系、位置关系、大小关系、等于关系、包含关系等。电子科技大学离散数学课程组——国家精品课程150-32020/1/21第6章二元关系关系的性质3关系的闭包运算4二元关系1关系的运算2内容提要电子科技大学离散数学课程组——国家精品课程150-42020/1/216.2二元关系6.2.1序偶与笛卡尔积定义6.2.1由两个元素x,y按照一定的次序组成的二元组称为有序偶对(序偶)，记作x,y，其中称x为x,y的第一元素，y为x,y的第二元素。电子科技大学离散数学课程组——国家精品课程150-52020/1/21例6.2.1用序偶表示下列语句中的次序关系(1)平面上点A的横坐标是x，纵坐标是y，x,y∈R；(2)成都是四川的省会；(3)英语课本在书桌上；(4)左，右关系。x,y，x,y∈R；成都,四川；英语课本,书桌；左,右。电子科技大学离散数学课程组——国家精品课程150-62020/1/21N重有序组定义6.2.3由n个元素a1,a2,a3,…,an按照一定次序组成的n元组称为n重有序组(n-Type)(Vector)，记作：a1,…,an例6.2.2用n重有序组描述下列语句。（1）中国四川成都电子科技大学计算机学院；（2）2006年9月10日18点16分25秒；（3）16减5再加3除以7等于2。定义6.2.4给定n重有序组a1,a2,…,an和b1,b2,…,bn。a1,a2,…,an=b1,b2,…,bn⇔ai=bi(i=1,2,…,n)中国,四川,成都,电子科技大学,计算机学院2006,9,10,18,16,2516,5,3,7,2电子科技大学离散数学课程组——国家精品课程150-72020/1/21笛卡尔乘积定义6.2.5设A，B是两个集合，称集合：A×B＝{x,y|(x∈A)∧(y∈B)}为集合A与B的笛卡尔积(DescartesProduct)。注意：①集合A与B的笛卡儿积A×B仍然是集合；②集合A×B中的元素是序偶，序偶中的第一元素取自A，第二元素取自B。电子科技大学离散数学课程组——国家精品课程150-82020/1/21例6.2.3设A={a}，B={b,c}，C=Φ，D={1,2}，请分别写出下列笛卡儿积中的元素。（1）A×B，B×A；（2）A×C，C×A；（3）A×(B×D)，(A×B)×D。解根据笛卡儿积的定义，有（1）A×B={a,b,a,c}，B×A={b,a,c,a}；（2）A×C=Φ，C×A=Φ；电子科技大学离散数学课程组——国家精品课程150-92020/1/21例6.2.3解（续）（3）因为B×D={b,1,b,2,c,1,c,2}，所以A×(B×D)={a,b,1,a,b,2,a,c,1,a,c,2}。同理，(A×B)×D={a,b,1,a,b,2,a,c,1,a,c,2}。电子科技大学离散数学课程组——国家精品课程150-102020/1/21注意由例6.2.3我们可以看出：（1）笛卡儿积不满足交换律；（2）A×B=Φ当且仅当A=Φ或者B=Φ；（3）笛卡儿积不满足结合律；（4）对有限集A,B，有|A×B|=|B×A|=|A|×|B|。电子科技大学离散数学课程组——国家精品课程150-112020/1/21定理6.2.1设A,B,C是任意三个集合，则（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)。电子科技大学离散数学课程组——国家精品课程150-122020/1/21定理6.2.1证明（1）对任意x,y∈A×(B∪C)，由笛卡儿积的定义知，x∈A且y∈B∪C；由并运算定义知，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)。电子科技大学离散数学课程组——国家精品课程150-132020/1/21定理6.2.1证明（续）另一方面，对任意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∪C，从而x,y∈A×(B∪C)。所以(A×B)∪(A×C)A×(B∪C)。于是，根据定理1.2.2，有A×(B∪C)=(A×B)∪(A×C)。(2)、(3)和(4)的证明作为练习，自证。电子科技大学离散数学课程组——国家精品课程150-142020/1/21定理6.2.2设A,B,C,D是任意四个集合，则(A×B)(C×D)AC，BD。证明充分性()：对任意x,y∈A×B，有x∈A且y∈B。又因为AC，BD，所以有x∈C且y∈D，即x,y∈C×D，从而(A×B)(C×D)。电子科技大学离散数学课程组——国家精品课程150-152020/1/21定理6.2.2证明（续）必要性()：对任意x∈A，y∈B，有x,y∈A×B。又因为(A×B)(C×D)，所以x,y∈C×D。根据笛卡儿积的定义有x∈C且y∈D，从而AC，BD。综上所述，定理成立。电子科技大学离散数学课程组——国家精品课程150-162020/1/21推广定义6.2.6设A1,A2,…,An是n个集合，称集合A1×A2×…×An={a1,a2,…,an|(ai∈Ai)∧i∈{1,2,3,…,n}}为集合A1,A2,…,An的笛卡儿积(DescartesProduct)当A1=A2=…=An=A时，有A1×A2×…×An=An。定理6.2.3当集合A1,A2,…,An都是有限集时，|A1×A2×…×An|=|A1|×|A2|×…×|An|。电子科技大学离散数学课程组——国家精品课程150-172020/1/21定义6.2.7设A,B为两个非空集合，称A×B的任何子集R为从A到B的二元关系，简称关系(Relation)。如A＝B，则称R为A上的二元关系。这里，A称为R的前域，B称为R的后域。令C＝{x|x,yR}A，D＝{y|x,yR}B，称C为R的定义域，记为C＝domR；称D为R的值域，记D＝ranR；并称fldR＝D∪C为R的域。二元关系电子科技大学离散数学课程组——国家精品课程150-182020/1/21当R=Φ时，称R为空关系(emptyrelation)；当R=A×B时，则称R为全关系(TotalRelation)。设一有序对x,y：若x,y∈R，则记为xRy，读作“x对y有关系R”；若x,yR，则记为xRy，读作“x对y没有关系R”。特别电子科技大学离散数学课程组——国家精品课程150-192020/1/21例6.2.4假设A={a,b}，B={c,d}，试写出从A到B的所有不同关系。解因为A={a,b}，B={c,d}，所以A×B={a,c,a,d,b,c,b,d}。于是A×B的所有不同子集为：0–元子集：Φ；1–元子集：{a,c},{a,d},{b,c},{b,d}；2–元子集：{a,c,a,d}，{a,c,b,c}，{a,c,b,d}，{a,d,b,d}，{a,d,b,d}，{b,c,b,d}；电子科技大学离散数学课程组——国家精品课程150-202020/1/21例6.2.4解（续）3–元子集：{a,c,a,d,b,c},{a,c,a,d,b,d}，{a,c,b,c,b,d},{a,d,b,c,b,d}；4–元子集：{a,c,a,d,b,c,b,d}。注意当集合A,B都是有限集时，A×B共有2|A|•|B|个不同的子集，即从A到B的不同关系共有2|A|•|B|个。电子科技大学离散数学课程组——国家精品课程150-212020/1/21求定义在Z上关系的定义域、值域和域。（1）R1={x,y|(x,y∈Z)∧{y=x2}}；（2）R2={x,y|(x,y∈Z)∧{|x|=|y|=7}}。解（1）domR1=Z，ranR1={x2|x∈Z}，fldR1=Z；（2）domR2={7,-7}，ranR2={7,-7}，fldR2={7,–7}。例6.2.5电子科技大学离散数学课程组——国家精品课程150-222020/1/216.2.3关系的表示法1.集合表示法（枚举法和叙述法）例6.2.7（1）设A={a}，B={b,c}，用枚举法写出从A到B的不同关系；（2）用叙述法写出定义在R上的“相等”关系。解（1）A到B的不同关系有：R1=Ф，R2={a,b}，R3={a,c}，R4={a,b,a,c}；（2）设R上的“相等”关系为S，则S={x,y|(x,y∈R)∧(x=y)}。电子科技大学离散数学课程组——国家精品课程150-232020/1/212.关系图法（1）A≠B设A＝{a1,a2,…,an}，B＝{b1,b2,…,bm}，R是从A到B的一个二元关系，则规定R的关系图如下：①.设a1,a2,…,an和b1,b2,…,bm分别为图中的结点，用“。”表示；②.如ai,bjR，则从ai到bj可用有向边ai。。bj相连。ai,bj为对应图中的有向边。电子科技大学离散数学课程组——国家精品课程150-242020/1/21（2)A=B设A＝B=a1,a2,…,an，R是A上的关系，则R的关系图规定如下：①.设a1,a2,…,an为图中结点，用“。”表示②.如ai,ajR，则从ai到aj可用有向边ai。。bj相连。ai,aj为对应图中的有向边。③.如ai,aiR,则从ai到ai用一带箭头的小圆环表示，即：ai关系图法（续）电子科技大学离散数学课程组——国家精品课程150-252020/1/21例6.2.8试用关系图表示下面的关系。（1）设A={2,3,4}，B={3,4,5,6}，则A到B之间的一种整除关系R1={2,4,2,6,3,3,3,6,4,4}2443365ABR1关系图中的有向边与关系集合中的序偶一样多电子科技大学离散数学课程组——国家精品课程150-262020/1/21例6.2.8(续)（2）假设A={1,2,3,4}，则A上的小于等于关系R2={1,1,2,2,3,3,4,4,1,2,1,3,1,4,2,3,2,4,3,4}。2341电子科技大学离散数学课程组——国家精品课程150-272020/1/21设A＝{a1,a2,…,an}，B＝{b1,b2,…,bm}，R是从A到B的一个二元关系，称矩阵MR＝（rij)n×m为关系R的关系矩阵(RelationMatrix)，其中又称MR为R的邻接矩阵(AdjacencyMatrix)。ijijij1a,bRr=(i=1,2,...,n,j=1,2,...,m)0a,bR3.关系矩阵1.必须先对集合A,B中的元素排序2.A中元素序号对应矩阵元素的行下标，3.B中元素序号对应矩阵元素的列下标；4.关系矩阵是0-1矩阵，称为布尔矩阵。注意电子科技大学离散数学课程组——国家精品课程150-282020/1/21例6.2.9设A={1,2,3,4}，考虑A上的整