离散数学,二元关系与运算.ppt

《离散数学,二元关系与运算.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二元关系和运算第四章1.二元有序组：由两个元素x和y按一定顺序排成二元组，记作：。§4.1二元关系的概念如：平面直角坐标系中点的坐标一、二元关系的概念二元有序组的性质(1)当xy时，(2)=，当且仅当x=u，y=v(1)、(2)说明有序组区别于集合n元有序组：由n个元素x1，x2，…，xn，按一定顺序排成的n元组，记作：(x1，x2，…，xn)。2.一种新的集合运算–––积运算：设A、B为两集合，用A中元素为第一元素，B中元素作为第二元素构成的二元有序组的全体叫做A和B的笛卡儿积。记作：AB符号化

2、：AB={

3、xAyB}例4.1设A={a,b}，B={0,1,2}，求AB，BA解：根据笛卡儿积的定义知AB={,,,}BA={<0,a>,<0,b>,}一般地：如果

4、A

5、=m，

6、B

7、=n，则

8、AB

9、=

10、BA

11、=mn,,<1,a>,<1,b>,<2,a>,<2,b>积运算的性质(1)若A，B中有一个空集，则笛卡儿积是空集，即：B=A=(2)当AB，且A，B都不是空集时，有ABBA(3)当A，B，C都不是空集时，有(AB)CA(BC)因为

12、(AB)C中的元素<,z>，而A(BC)中的元素为>。(4)A(B∪C)=(AB)∪(AC)(对∪的分配律)(B∪C)A=(BA)∪(CA)A(B∩C)=(AB)∩(AC)(B∩C)A=(BA)∩(CA)我们证明：A(B∪C)=(AB)∪(AC)(?)(?)(?)证明思想要证明两个集合相等，通常有两种方法：一是证两个集合相互包含；二是利用已有的集合运算的性质(算律和已证明过的公式)，仿照代数恒等式的证明方法，一步步从左(右)边推出右(左)边，或从左、右边分别推出同一个集合式子。一般说来，

13、最基本的集合相等关系要用第一种证法，比较复杂的集合相等关系用第二种方法更好，但第二种方法的使用取决于我们对算律和常用公式的熟练程度。证明：用第一种方法对于任意的A(B∪C)xAy(B∪C)xA(yByC)(xAyB)(xAyC)ABAC(AB)∪(AC)A(B∪C)=(AB)∪(AC)例4.2设A={1,2}，求P(A)A解：P(A)A={，{1}，{2}，{1,2}}={<,1>，<,2>，n阶笛卡儿积：={(x1,x2,…xn)

14、

15、x1A1x2A2…xnAn}A1A2…An{1,2}<{1},1>，<{1},2>，<{2},1>，<{2},2>，<{1,2},1>，<{1,2},2>}二元关系：如果一个集合的元素都是二元有序组，则这个集合称为一个二元关系，记作：R。如果R，记作xRy如果R，记作xRy3、二元关系的数学定义从A到B的二元关系：设A，B为集合，AB的任何子集所定义的二元关系叫做从A到B的二元关系。若A=B，叫做A上的二元关系；若

16、A

17、＝n，则

18、AA

19、＝n2。就是说，A上有个不同的二元关系，其中包括空关系、全域关系UA和恒

20、等关系IA。AA的所有子集有个。例4.3设A={a,b}，写出P(A)上的包含关系R：解：P(A)={,{a},{b}{a,b}}R={<,>,<,{a}>,<{,{b}>,<{a,b}>,<{a},{a}>,<{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>}A上关系的表示法1.关系矩阵：设A={x1,x2,…,xn)，R是A上的关系，rij=1若xiRxj0若xiRxj(i,j=1,2,…,n)则(rij)nxn=是R的关系矩阵令：二、二元关系的表示方法2.关系图：以E={

21、x

22、iAxjAxiRxj}为有向边集组成的有向图G=以V=A={x1,x2,…,xn}为顶点集，例4.4设A={1,2,3,4}，R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}是A上的关系，试写出R的关系矩阵并画出关系图：解：关系矩阵：0011000001001100关系图：1342§4.2关系的运算关系R的定义域：domR={x

23、(y)R}(即R中有序组的第一个元素构成的集合)关系R的值域：ranR={y

24、(x)R}(即R中有序组的第二个元素构成的集合)一、关系的定义域与值域例4.5下列关

25、系都是整数集Z上的关系，分别求出它们的定义域和值域：(1)R1={

26、x,yZx