ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 笛卡尔乘积

笛卡尔乘积

原创 Linux操作系统 作者:ixavier 时间:2011-06-19 21:06:34 0 删除 编辑
笛卡尔(Descartes)乘积又叫直积。假设集合A={a,b},集合B={0,1,2},则两个集合的笛卡尔积为{(a,0),(a,1),(a,2),(b,0),(b,1), (b,2)}。可以扩展到多个集合的情况。类似的例子有,如果A表示某学校学生的集合,B表示该学校所有课程的集合,则A与B的笛卡尔积表示所有可能的选课情况。

序偶定义

  由两个元素x和y(x=y)按一定顺序排列成的二元组叫做一个有序对或序偶,记作,其中x是它的
  第一元素,y是它的第二元素。
  有序对具有以下性质:
  1.当x≠y时,.
  2.=的充分必要条件是x=u且y=v.
  这些性质是二元集{x,y}所不具备的。例如当x≠ys时有{x,y}={y,x}。原因在于有序对中的元素是有序的
  ,而集合中的元素是无序的。
  例:已知=<5,2x+y>,求x和y。
  解:由有序对相等的充要条件有 x+2=5和2x+y=4 联立解得 x=3,y=-2.

笛卡尔积定义

  设A,B为集合,用A中元素为第一元素,B中元素为第二元素构成的有序对,所有这样的有序对组成的集合
  叫做A与B的笛卡尔积,记作AxB.
  笛卡尔积的符号化为:
  AxB={|x∈A∧y∈B}
  例如,A={a,b},B={0,1,2},则
  AxB={,,,,,,}
  BxA={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}
  笛卡尔积的运算性质
  1.对任意集合A,根据定义有
  AxΦ =Φ ,Φ xA=Φ
  2.一般地说,笛卡尔积运算不满足交换律,即
  AxB≠BxA(当A≠Φ ∧B≠Φ∧A≠B时)
  3.笛卡尔积运算不满足结合律,即
  (AxB)xC≠Ax(BxC)(当A≠Φ ∧B≠Φ∧C≠Φ时)
  4.笛卡尔积运算对并和交运算满足分配律,即
  Ax(B∪C)=(AxB)∪(AxC)
  (B∪C)xA=(BxA)∪(CxA)
  Ax(B∩C)=(AxB)∩(AxC)
  (B∩C)xA=(BxA)∩(CxA)

推导过程

  给定一组域D1,D2,…,Dn,这些域中可以有相同的。D1,D2,…,Dn的笛卡尔积为:
  D1×D2×…×Dn={(d1,d2,…,dn)|di∈Di,i=1,2,…,n}
  所有的所有取值的一个组合不能重复

案例

  给出三个域:
  D1=SUPERVISOR ={ 张清玫,刘逸 }
  D2=SPECIALITY={计算机专业,信息专业}
  D3=POSTGRADUATE={李勇刘晨王敏}
  则D1,D2,D3的笛卡尔积为D:
  D=D1×D2×D3 =
  {(张清玫,计算机专业,李勇),(张清玫,计算机专业,刘晨),
  (张清玫,计算机专业,王敏),(张清玫,信息专业,李勇),
  (张清玫,信息专业,刘晨),(张清玫,信息专业,王敏),
  (刘逸,计算机专业,李勇),(刘逸,计算机专业,刘晨),
  (刘逸,计算机专业,王敏),(刘逸,信息专业,李勇),
  (刘逸,信息专业,刘晨),(刘逸,信息专业,王敏) }
  这样就把D1,D2,D3这三个集合中的每个元素加以对应组合,形成庞大的集合群。
  本个例子中的D中就会有2X2X3个元素,如果一个集合有1000个元素,有这样3个集合,他们的笛卡尔积所组成的新集合会达到十亿个元素。假若某个集合是无限集,那么新的集合就将是有无限个元素。

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/25957310/viewspace-700212/,如需转载,请注明出处,否则将追究法律责任。

下一篇: Oracle的索引
请登录后发表评论 登录
全部评论

注册时间:2011-06-18

  • 博文量
    8
  • 访问量
    19912