关系一词是大家所熟知的.doc

《关系一词是大家所熟知的.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章关系关系一词是大家所熟知的，不论科学研究还是日常生活中，关系无处不在。例如，人与人之间有父子、兄弟、师生关系；两数之间有大于、等于、小于关系；元素与集合之间的属于关系等等。在计算机科学中“关系”这个概念有着广泛地应用，它在有限自动机、形式语言、编译程序设计、信息检索、数据结构、算法分析和数据库等方面起着重要作用。4.1有序对与笛卡尔积4.1.1有序对定义4.1-1由两个元素x，y(允许x=y)按给定次序排成的二元组合称为一个有序对或序偶（Orderedpair），记作，其中称x是有序对的第一元素，y是有序对的第二元素。对定义

2、我们指出：1.有序对是强调次序的，若x≠y，则¹。2.有序对可以看成是一种由两个元素组成的特殊集合，即={x,{x,y}}。定理4.1-1对任意的有序对＜x,y＞=＜u,v＞的充要条件是x=u且y=v。例4.1-1设<2x+y,5>=<10,x-3y>，求x，y。解由定理4.1-1列出如下方程组：求解得x=5，y=0。在实际问题中有时会用到有序3元组，有序4元组，…，有序n元组。定义4.1-2由n个元素x1,x2,…,xn按给定顺序排列成的n元组合称为一个有序n元组（N-Type）（Vector），记作

3、xn>，其中xi称为它的第i元素，i=1,2,…,n。有序n元组可用有序对递归地定义，若已经定义了有序的(n-1)元组（n≥3），有序n元组可定义为=<,xn>。例4.1-2(1)若有序对的第一个元素为有序对，第二个元素为z，此时将有序对<,z>称为有序3元组，简记为＜x,y,z>。(2)三维立体空间坐标系中点的坐标<1,-1,3>，<2,4.5,0>等都是有序3元组。n维空间中点的坐标或n维向量都是有序n元组。同样＜x1,x2,…,xn＞=＜y1,y2,…,y

4、n＞的充要条件是xi=yi，i=1,2,…,n。4.1.2笛卡尔积定义4.1-3设A，B是任意集合，以A中元素作第一元素，B中元素作第二元素生成的所有有序对的集合称为A，B的笛卡尔积（DescartesProduct），记作A×B。即A×B={½xA∧yB}。107由笛卡尔积的定义，对于有限集合可以进行多次的笛卡尔积运算。定义4.1-4定义A1´A2´…´An=(A1´A2´…´An-1)´An，称为集合A1,A2,…,An的叉积。特别地，当A1=A2=…=An=A时，简记A1´A2´…´An为An。由定义，两集合的笛卡尔积仍是集合，所以可应用集合的

5、运算，如并、交、差、补。例4.1-3设集合A={x,y,z}，B={0,1},C={u,v}，求A×B,B×A,A×A,A×B×C,(A×B)×C,A×(B×C),(A×B)∩(B×A)。解A×B={,,,,,}B×A={<0,x>,<0,y>,<0,z>,<1,x>,<1,y>,<1,z>}A×A={,,,,,,,,}A×B×C={,,,,,

6、,,,,,,}(A×B)×C={<,u>,<,v>,<,u>,<,v>,<,u>,<,v>,<,u>,<,v>,<,u>,<,v>,<,u>,<,v>}={,,,,,,,,,,,}

7、A×(B×C)={>,>,>,>,>,>,>,>,>,>,>,>}¹{,,,,,,,,,,,}由笛卡尔积的定义可得，1．对于任意集合A，A´=，´A=。2．笛卡尔积运算是不可交换的，当A¹，B¹，A¹B时A

8、´B≠B´A。3．笛卡尔积运算是不可结