计算机类本科规划教材：《离散数学》课程配套电子教案（PPT课件讲稿）第4章 二元关系

第4章二元关系 第4章二元关系 4.1二元关系及其表示 4.2关系的运算 4.3关系的性质 4.4关系的闭包运算 4.5等价关系 4.6相容关系 4.7序关系 返回总目录

第4章 二元关系 第4章 二元关系 4.1 二元关系及其表示 4.2 关系的运算 4.3 关系的性质 4.4 关系的闭包运算 4.5 等价关系 4.6 相容关系 4.7 序关系 返回总目录

第4章二元关系 第4章二元关系 4.1二元关系及其表示 4.1.1二元关系的概念 定义4.1.1设A和B是任意集合，如果RcA×B,则称R是 A到B的二元关系。如果R是A到A的二元关系，则称R是A上 的二元关系。 设A=1,2,3},B-a,b},R=<1,D,<2,D,<3,b>。R是A 到B的二元关系。S=了<3,1>，<2,2>，<2,1>，<1,1>7。S是A上的 二元关系。 定义4.1.2设A和B是任意集合，RCAXB,若<x,>∈R, 则称x与y有R关系。记为xRy。若<x,>R,则称x与y没有R 关系。记为xRy

第4章 二元关系 第4章 二元关系 4.1二元关系及其表示 4.1.1二元关系的概念 定义4.1.1设A和B是任意集合，如果RA×B，则称R是 A到B的二元关系。如果R是A到A的二元关系，则称R是A上 的二元关系。 设A=1,2,3，B=a,b，R=1,a,2,a,3,b。R是A 到B的二元关系。S=3,1,2,2,2,1,1,1。S是A上的 二元关系。 定义4.1.2设A和B是任意集合，RA×B，若x,yR， 则称x与y有R关系。记为xRy。若x,yR，则称x与y没有R 关系。记为x R y

第4章二元关系 如果R是A到B的二元关系，根据定义4.1.2，<x,y>∈R与 xRy, <x,>R与xRy的意义相同。 定义4.1.3设A和B是任意集合，空集O叫做A到B的空关 系，仍然记为☑。A,B的笛卡尔积AXB叫做A到B的全域关 系，记为E。集合<a,心laeA}叫做A上的恒等关系。记为L4。 【例4.1】设A=a,b,B=1,2},求A上的恒等关系I和 A到B的全域关系AXB。 解：A上的恒等关系I月<a,a心，<b,b>,A到B的全域关系 E=AXB=<a,1>,<a,2>,<b,1>,<b,2> 定理4.1.1设A是具有n个元素的有限集，则A上的二元关 系有22种。 证明：设A为具有n个元素的有限集，即4=n,由排列组 合原理知AXA=n2? 根据定理3.1.2有P(A×A)F24XL2”2, 即A×A的子集有2”个。所以具有n个元素的有限集A上有2种 二元关系

第4章 二元关系 如果R是A到B的二元关系，根据定义4.1.2，x,yR与 xRy，x,yR与x y的意义相同。 定义4.1.3设A和B是任意集合，空集叫做A到B的空关 系，仍然记为。A，B的笛卡尔积A×B叫做A到B的全域关 系，记为E。集合a,a|aA叫做A上的恒等关系。记为IA。 【例4.1】设A=a,b，B=1,2，求A上的恒等关系IA和 A到B的全域关系A×B。 解：A上的恒等关系IA =a,a,b,b，A到B的全域关系 E =A×B=a,1,a,2,b,1,b,2 定理4.1.1设A是具有n个元素的有限集，则A上的二元关 系有2 n2种。 证明：设A为具有n个元素的有限集，即|A|=n，由排列组 合原理知|A×A|=n 2 。根据定理3.1.2有|P (A×A) |=2 |A×A|=2 ， 即A×A的子集有2 个。所以具有n个元素的有限集A上有2 种 二元关系。 2 n 2 n 2 n R

第4章二元关系 4.1.2二元关系的表示 1.用列举法表示二元关系 例4.1中的A到B的全域关系 E=A×B-<a,1>,<a,2>,<b,1>,<b,2> A上的恒等关系 I<a,a心，<b,b>} 都是用列举法表示的。 2.用描述法表示二元关系 设R是实数集，LR<x,>|x∈R∧yER∧x≤y,LR是 实数集R上的二元关系

第4章 二元关系 4.1.2二元关系的表示 1.用列举法表示二元关系 例4.1中的A到B的全域关系 E=A×B=a,1,a,2,b,1,b,2 A上的恒等关系 IA =a,a,b,b 都是用列举法表示的。 2.用描述法表示二元关系 设R是实数集，LR = x,y | xR∧yR∧x≤y， LR是 实数集R上的二元关系

第4章二元关系 3.用矩阵表示二元关系 如果A,B是有限集， A=a1,42,…,amy B=b1,b2,…,bn7, R是A到的二元关系，R的关系矩阵定义为： MR)nxn 1 <a,b;>ER 0 <abR i=1,…,mj=1,…,n 称为二元关系R的关系矩阵

第4章 二元关系 3.用矩阵表示二元关系 如果A，B是有限集， A=a1 ,a2 ,…,am ， B=b1 ,b2 ,…,bn ， R是A到B的二元关系，R的关系矩阵定义为： MR = mn R R b b a a r j j i i ij          = , , 0 1 i=1,…,m j=1,…,n 称为二元关系R的关系矩阵。 ( ) ij r