离散数学3-4序偶与笛卡尔积3-5关系及其表示.

离散数学DiscreteMathematics山东科技大学信息科学与工程学院上次课内容回顾集合的概念集合的表示集合的关系特殊的集合：空集、全集、幂集集合的运算：3-4序偶与笛卡尔积1、序偶(有序2元组)：两个具有固定次序的客体组成一个序偶(有序2元组)，记作x，y，其中x是它的第一元素，y是它的第二元素。一、有序n元组例：平面直角坐标系中的一个点的坐标就构成为一个有序序偶，我们可用x，y表示。注：序偶是讲究次序的。例1，3和3，1表示平面上两个不同的点，这与集合不同，{1，3}和{3，1}是两个相等的集合。2、定义3-4.1：两个序偶相等，x，y=u，v，当且仅当x=u且y=v。一、有序n元组3、有序３元组：是一个序偶，其第一元素本身也是一个序偶，表示为x，y，z或x，y，z。4、有序n元组：有序n元组也是一个序偶，其第一元素是一个n-1元组。x1，x2，…，xn-1，xn，通常简记为：x1，x2，…，xn-1，xn，其中xi称作它的第i坐标，i=1，2，…，n。x1，x2，…，xn-1，xn=y1，y2，…，yn-1，yn的充要条件是xi=yi，i=1，2，…，n。序偶x,y其元素可以分别属于不同的集合，因此任给两个集合A和B，我们可以定义一种序偶的集合。1、定义3-4.2：设A和B是任意两个集合，由A中元素作第一元素，B中元素作第二元素构成序偶，所有这样序偶的集合称集合A和B的笛卡尔积或直积。记作AB。即AB={x，y|xA∧yB}二、笛卡尔积2、n个集合的笛卡尔积：集合A1，A2，…，An，则特别地，约定：若A=或B=，则AB=，BA=例题若A={，}，B={1，2，3}，求AB，BA，AA，BB以及(AB)(BA)。解：AB={，1，，2，，3，，1，，2，，3}BA={1，，1，，2，，2，，3，，3，}AA={，，，，，，，}BB={1，1，1，2，1，3，2，1，2，2，2，3，3，1，3，2，3，3}(AB)(BA)=若A、B均是有限集，|A|=m，|B|=n，则|AB|=mn。三、笛卡尔积的性质1、对于任意集合A，A=，A=。2、笛卡尔积运算不满足交换律，当A，B，AB时ABBA。3、笛卡尔积运算不满足结合律，即当A，B，C均非空时(AB)CA(BC)。4、定理3-4.1：对任意三个集合A、B、C，有(1)A(BC)=(AB)(AC)(2)A(BC)=(AB)(AC)(3)(BC)A=(BA)(CA)(4)(BC)A=(BA)(CA)由以上两条有：A(BC)(AB)(AC)证明两个集合相等，可以证明它们互相包含。则aA，bBC，即aA，bB，且bc，证明：(2)a，bA(BC)，即a，bAB且a，bAC，有a，b(AB)(AC)，得A(BC)(AB)(AC)a，b(AB)(AC)，则a，bAB且a，bAC，则aA，bB，且aA，bC，则bBC。所以a，bA(BC)，所以(AB)(AC)A(BC)5、定理3-4.2：对于任意集合A、B、C，若C，则ABACBCCACB证明：设ACBC。xA，因C，任取yC，有x，yAC因为ACBC，所以x，yBC所以xB，所以AB设AB。x，yAC，则xA，yC，又因AB，所以xB，所以x，yBC，所以ACBC同样，定理的第二部分ABCACB可以类似地证明。6、定理3-4.3：对任意四个非空集合，ABCD的充分必要条件是AC，BD。证明：充分性。设AC，BD。由定理3-4.2，因BD，A，所以ABAD。又AC，D非空，所以ADCD，所以ABCD。必要性。设ABCD。xA，yB，所以x，yAB，又因ABCD，所以x，yCD，所以xC，yD，所以AC，BD证明定理3-4.3用到集合包含的传递性：(AB)∧(BC)(AC)3-5关系及其表示•兄弟关系•师生关系•朋友关系•恋人关系•大于关系一、关系（Relation）1、关系定义3-5.1：任一序偶的集合确定了一个二元关系R，a，bR记作aRb，称a与b有关系，a，bR记作aRb，称a与b没有关系。例如，={x，y|x，y是实数且xy}说明：(1)把关系R这种无形的联系用集合这种“有形”的实体来描述，为今后的描述和论证带来方便。(2)序偶是讲究次序的，如果有a，bR未必有b，aR，即a与b有关系R，未必b与a有关系R。例：甲与乙有父子关系，但乙与甲没有父子关系。2、前域、值域定义3-5.2：二元关系R中，•所有序偶的第一元素的集合domR称为R的前域，即：domR={x|(y)x，yR}•所有序偶的第二元素的集合ranR称为R的值域，即：ranR={y|(x)x，yR}。•R的前域和值域一起称作的域，记作FLDR。即：FLDR=domRranR2、前域、值域例题1设H={1，2，1，4，2，4，3，4}，求domH，ranH，FLDH。解：domH={1，2，3}，ranH={2，4}，FLDH={1，2，3，4}3、X到Y的关系定义3-5.3：令X和Y是任意两个集合，XY的子集R称作X到Y的关系。如果R是X到Y的关系，则domRX，ranRY。当X=Y时，关系R是XX的子集，这时称R为在X上的二元关系。3、X到Y的关系例题2设X={1，2，3，4}，求X上的关系及dom，ran。解：={2，1，3，1，4，1，3，2，4，2，4，3}dom={2，3，4}，ran={1，2，3}4、特殊的关系(1)全域关系：对于集合X和Y，称XY为X到Y的全域关系。记作U。称为空关系。(2)二元关系：R是XX的子集，称R是X上的二元关系(3)恒等关系：Ix称为X上的恒等关系iffIx={x,x|xX}例题3若H={f，m，s，d}表示一个家庭中的父、母、子、女四个人的集合，确定H上的全域关系和空关系，另外再确定H上的一个关系，指出该关系的值域和前域。解：•设H上的同一家庭成员的关系为H1，H上的互不相识的关系为H2，则：H1为全域关系，H2为空关系；•设H上的长幼关系为H3，H3={f，s，f，d，m，s，m，d}，domH3={f，m}，ranH3={s，d}解：H={1，1，1，3，2，2，2，4，3，3，3，1，4，4，4，2}S={4，1}HS={1，1，1，3，2，2，2，4，3，3，3，1，4，4，4，2，4，1}HS=XX={1，1，1，2，1，3，1，4，2，1，2，2，2，3，2，4，3，1，3，2，3，3，3，4，4，1，4，2，4，3，4，4}H={1，2，1，4，2，1，2，3，3，2，3，4，4，1，4，3}S-H={4，1}例题4设X={1，2，3，4}，若H={x，y|(x-y)/2是整数}，S={x，y|(x-y)/3是正整数}，求HS，HS，H，S-H。5、定理3-5.1：若Z和S是集合X到Y的两个关系，则Z和S的并、交、补、差仍是到的关系。关系的表示方法•集合法•关系矩阵•关系图二、关系的表示1、集合为直观地表示A到B的关系,采用如下的图示:•用大圆圈表示集合A和B,里面的小圆圈表示集合中的元素;•若a∈A,b∈B,且(a,b)∈ρ,则在图示中将表示a和b的小圆圈用直线或弧线连接起来,并加上从结点a到结点b方向的箭头。例设A＝｛1,2,3,4,5｝,B＝｛a,b,c｝,则ρ1＝｛(1,a),(1,b),(2,b),(3,a)｝是A到B的关系,而ρ2＝｛(a,2),(c,4),(c,5)｝是B到A的关系。其集合表示法如下：2、关系矩阵：设给定两个有限集合X={x1，x2，…，xm}，Y={y1，y2，…，yn}，R是X到Y的关系，则R的关系矩阵MR，其中[rij]mn，rij=1，当xi，yjR，rij=0，当xi，yjR。111102010310040005000M2010000000000011aMbc其关系矩阵表示为：例设A＝｛1,2,3,4,5｝,B＝｛a,b,c｝,则ρ1＝｛(1,a),(1,b),(2,b),(3,a)｝是A到B的关系,而ρ2＝｛(a,2),(c,4),(c,5)｝是B到A的关系。关系矩阵的写法也可以简化,当约定了元素的次序后,可以不写最左列和最上行的元素。如2010000000000011M1110010100000000M关于关系矩阵的几点说明：(1)空关系的关系矩阵的所有元素为0。(2)全关系的关系矩阵的所有元素为1。(3)恒等关系的关系矩阵的所有对角元为1，非对角元为0，此矩阵为单位矩阵。(4)如果R是X上的二元关系时，则其关系矩阵是一个方阵。例题5设X={x1,x2,x3,x4},Y={y1,y2,y3},R={x1,y1,x1,y3,x2,y2,x2,y3,x3,y1,x4,y1,x4,y2}，写出关系矩阵MR。例题6设A={1,2,3,4}，写出集合A上大于关系的关系矩阵。P108例题3、关系图：设有限集合X={x1，x2，…，xm}，Y={y1，y2，…，yn}，X到Y的一个关系为R，则R的关系图：(1)做出m个结点分别记作x1，x2，…，xm，n个结点分别记作y1，y2，…，yn，(2)如果xi，yjR，则可自结点xi至yj作一有向弧;(3)如果xi，yjR，则xi至yj没有线段联结。例设A＝｛-2,-1,0,1｝,写出A上的＜关系、≤关系、＞关系、UA和IA,并分别写出这些关系的定义域和值域（这里＜、≤、＞分别表示通常的小于、小于等于和大于）。并画出关系图。解＜＝｛(-2,-1),(-2,0),(-2,1),(-1,0),(-1,1),(0,1)｝Dom＜＝｛-2,-1,0｝Ran＜＝｛-1,0,1｝≤＝｛(-2,-2),(-2,-1),(-2,0),(-2,1),(-1,-1),(-1,0),(-1,1),(0,0),(0,1),(1,1)｝Dom≤＝ARan≤＝A＞＝｛(-1,-2),(0,-1),(0,-2),(1,-2),(1,-1),(1,0)｝Dom＞＝｛-1,0,1｝Ran＞＝｛-2,-1,0｝UA＝｛(-2,-2),(-2,-1),(-2,0),(-2,1),(-1,-2),(-1,-1),(-1,0),(-1,1),(0,-2),(0,-1),(0,0),(0,1),(1,-2),(1,-1),(1,0),(1,1)｝IA＝｛(-2,-2),(-1,-1),(0,0),(1,1)｝DomUA＝RanUA＝DomIA＝RanIA＝A图2例题用图例题7设X={x1,x2,x3,x4},Y={y1,y2,y3},R={x1,y1,x1,y3,x2,y2,x2,y3,x3,y1,x4,y1,x4,y2}，画出R的关系图。例题8设A={1,2,3