离散数学-二元关系与运算-专业数学教材.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《离散数学-二元关系与运算-专业数学教材.ppt》由会员分享,可在线阅读,更多相关《离散数学-二元关系与运算-专业数学教材.ppt(61页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、1.二元有序组二元有序组二元有序组二元有序组:由两个元素由两个元素x和和y按一定顺序按一定顺序排成二元组,记作:排成二元组,记作:。4.1 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
2、 B符号化:A B=|xA y B例例4.1 设A=a,b,B=0,1,2,求A B,B A解:解:根据笛卡儿积的定义知A B=,B A=,一般地:如果|A|=m,|B|=n,则|A B|=|B A|=m n,(1)若A,B中有一个空集,则笛卡儿积是空集,即:B=A =(2)当AB,且A,B都不是空集时,有ABBA(3)当A,B,C都不是空集时,有(A B)C A(B C)因为(A B)C中的元素,z,而A(B C)中的元素为 x,。(4)A(BC)=(A B)(A C)(对的分配律)(BC)A=(B A)(C A)A(BC)=(A B)(A C)(BC)A=(B A)(C A)我们证明:A(
3、BC)=(A B)(A C)(?)(?)(?)要证明两个集合相等,通常有两种方法:一是证两个集合相互包含;二是利用已有的集合运算的性质(算律和已证明过的公式),仿照代数恒等式的证明方法,一步步从左(右)边推出右(左)边,或从左、右边分别推出同一个集合式子。一般说来,最基本的集合相等关系要用第一种证法,比较复杂的集合相等关系用第二种方法更好,但第二种方法的使用取决于我们对算律和常用公式的熟练程度。证明:证明:用第一种方法对于任意的 A (BC)xA y(BC)xA(yB yC)(xA yB)(xA yC)A B A C(A B)(A C)A(BC)=(A B)(A C)例例4.2 设A=1,2,
4、求P(A)A解:解:P(A)A=,1,2,1,2=,n阶笛卡儿积:=(x1,x2,xn)|x1A1 x2A2 xnAnA1 A2 An1,2,二二元元关关系系:如如果果一一个个集集合合的的元元素素都都是是二二元元有有序序组组,则则这这个个集集合合称称为为一一个个二二元元关系,记作:关系,记作:R。如果 R ,记作 x R y如果 R ,记作 x R y3、二元关系的数学定义、二元关系的数学定义从从A到到B的二元关系:的二元关系:设设A,B为集合,为集合,A B的任的任何子集所定义的二元关系叫做从何子集所定义的二元关系叫做从A到到B的二元关系。的二元关系。若A=B,叫做 A上的二元关系;若|A|
5、n,则|A A|n2。就是说,A上有 个不同的二元关系,其中包括空关系、全域关系UA和恒等关系IA。A A的所有子集有 个。例例4.3 设A=a,b,写出P(A)上的包含关系R:解:解:P(A)=,a,ba,bR=,1.关系矩阵:设A=x1,x2,xn),R是A上的关系,rij=1 若xi R xj0 若xi R xj(i,j=1,2,n)则 (rij)nxn=是R的关系矩阵令:二、二元关系的表示方法2.关系图:以E=|xiA xjA xiRxj为有向边集组成的有向图G=以V=A=x1,x2,xn 为顶点集,卡盟排行榜 卡盟 Microsoft Office PowerPoint,是微软公司的
6、演示文稿软件。用户可以在投影仪或者计算机上进行演示,也可以将演示文稿打印出来,制作成胶片,以便应用到更广泛的领域中。利用Microsoft Office PowerPoint不仅可以创建演示文稿,还可以在互联网上召开面对面会议、远程会议或在网上给观众展示演示文稿。Microsoft Office PowerPoint做出来的东西叫演示文稿,其格式后缀名为:ppt、pptx;或者也可以保存为:pdf、图片格式等例例4.4 设A=1,2,3,4,R=,是A上的关系,试写出R的关系矩阵并画出关系图:解:解:关系矩阵:0 0 1 10 0 0 00 1 0 01 1 0 0关系图:134 24.2 4
7、.2 关系的运算关系的运算关系关系R的定义域:的定义域:domR=x|(y)R(即即R中有序组的第中有序组的第一个元素构成的集合一个元素构成的集合)关关系系R的的值值域域:ranR=y|(x)R(即即R中中有有序序组组的的第第二个元素构成的集合二个元素构成的集合)一、关系的定义域与值域例例4.5 下列关系都是整数集Z上的关系,分别求出它们的定义域和值域:(1)R1=|x,y Z xy(2)R2=|x,y Z x2+y2=1(3)R3=|x,y Z y=2x(4)R4=|x,y Z|x|=|y|=3 解:解:domR1=ranR1=Z解:解:R2=,domR2=(?)ranR2=(?)(1)R1
8、=|x,y Z xy(2)R2=|x,y Z x2+y2=1,解:解:domR3=Z,ranR3=偶数 解:解:domR4=ranR4=(?)(3)R3=|x,y Z y=2x(4)R4=|x,y Z|x|=|y|=3 二、关系的常用运算F是任意关系,F的逆F1=|yFx F、G是任意两个关系,F与G的合成记作:F G=|(z)(xGz zFy)关系F在集A上的限制,记作:F|A=|xFy xA集A在关系F下的象FA=ran(F|A)(1)逆:(2)合成:(3)限制:(4)象:例例4.6 设F,G是N上的关系,其定义为:F=|x,yN y=x2G=|x,yN y=x+1求 G1,F G,G F
9、,F|1,2,F1,2解:解:由定义知:G1=|y,xN y=x+1列出G1 中的元素就是G1=,为了求F G,可以先直观表示如下:对任何xNx x+1=G即 y=(x+1)2因此 F G=|x,yN y=(x+1)2 同理可求 G F=|(?)(自己做!)发现 F G G FF|1,2=,F 1,2=ran(F|1,2)=1,4F Z Z2=y关系运算的性质:关系运算的性质:设F、G、H、为任意关系,则有:(1)(F1)1=F(2)domF1=ranF,ranF1=domF(3)(F G)H=F (G H)(4)(F G)1=G1 F1(5)F (GH)=F GF H (对的分配律)(6)F
10、 (GH)F GF H (对的半分配律)(7)(GH)F=G FH F(8)(GH)F G FH F(?)(?)任取 (F G)1 F G(z)(G F)(z)(G1 F1)G1 F1(4)(F G)1=G1 F1的证明:任取F (GH)(z)(GH)F)(z)(GH)F)(注意对括号的顺序)(z)(G F(H F)F GF H F (GH)=F GF H(5)F (GH)=F GF H的证明:4.3 4.3 关系的性质关系的性质R的关系矩阵:主对角线元素全是1R的关系图:每个顶点都有环自反性:x A 有R (R是A上的关系)关系矩阵:主对角线元素全是0关系图:每个顶点都没有环反自反性:x A
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 二元关系 运算 专业 数学 教材
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内