离散数学09改

离散数学

下面学习本章的第三个知识点： 下面学习本章的第三个知识点：

关系及其表示法； 1、关系及其表示法； 关系的性质； 2、关系的性质； 关系的运算； 3、关系的运算； 等价关系与划分； 4、等价关系与划分； 序关系； 5、序关系； 相容关系。 6、相容关系。

离散数学

4.3 关系的运算二元关系是序偶的集合，因此，关系也有集合 二元关系是序偶的集合，因此，关系也有集合 诸如交 等运算， 诸如交、并、差、补等运算，其运算规则也是一 样的，只不过其元素是序偶罢了。 只不过其元素是序偶罢了。

若 xRy, x, y 则

? R

x, y ∈ R

离散数学

一、交、并、差、补1、定义定义4.3.1 设A和B是集合， A × B, 且 S A × B, 是集合， 定义 和 是集合 R 则交 R I S 、并 R U S 、差 R S 和 补 R 均是 A 和 B 上的二元关系，且 上的二元关系， x( R I S ) y xRy ∧ xSy ; x( R U S ) y xRy ∨ xSy ;x( R S ) y xRy ∧ xSy ; x R y xRy.

离散数学

例题讲解： 例题讲解： 上的关系， 例1 设 A = {1, 2, 3 },R1 和 R2 是 A 上的关系， 其中 R1 = { 1,1 , 2, 2 }; R2 = { 1,1 , 1, 2 , 2,1 }; 求 R1 I R2 , R1 U R2 , R1 R2 , R2 R1 , R2 . 解： R1 I R2 = { 1,1 } R1 U R2 = { 1,1 , 1, 2 , 2,1 , 2, 2 };

R2 = { 1, 3 , 2, 2 , 2, 3 , 3,1 , 3, 2 , 3, 3

R1 R2 = { 2, 2

};

R2 R1 = { 1, 2 , 2,1 };

}

离散数学

2、关系矩阵计算方法(1)关系矩阵的逻辑运算 )设 M R = (aij ) m×n 和 M S = (bij ) m×n 是关系矩阵，则 是关系矩阵，

(M R ∧ M S )[ i, j ] = M R [ i, j ] ∧ M S [ i, j ] = (aij ∧ bij ) m×n , (M R ∨ M S )[ i, j ] = M R [ i, j ] ∨ M S [ i, j ] = (aij ∨ bij ) m×n , ¬ M R [ i, j ] = (¬aij ) m×n .

离散数学

(2)交、并、差、补的关系矩阵计算方法 )M RIS = M R ∧ M S , M RUS = M R ∨ M S , M R S = M R ∧ ¬ M S , M R = ¬M R .

离散数学

例题讲解： 例题讲解： 用关系矩阵计算例1。 例2 用关系矩阵计算例 。 解：

M R1 I R2

1 0 0 1 1 0 1 0 0 = 0 1 0 ∧ 1 0 0 = 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 0 1 0 ∨ 1 0 0 = 1 1 0 = 0 0 0 0 0 0 0 0 0

M R1 U R2

离散数学

MR

2

1 1 0 0 0 1 = ¬ 1 0 0 = 0 1 1 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 = 0 1 0 ∧ 0 1 1 = 0 1 0 0 0 0 1 1 1 0 0 0

M R1 R2

离散数学

二、关系的逆1、定义定义4.3.2 设A和B是集合， A × B. 令 R B × A 是集合， 定义 和 是集合 R 1

且 R 1 = { y, x

的逆关系。 则称 R 1 是 R 的逆关系。 xRy },

离散数学

例题讲解： 例题讲解： 例3 设 F = { 3, 3 , 6, 2 解： F 1 = { 3, 3 ,

2, 6 求它的逆关系。 } ,求它的逆关系。 }

离散数学

2、逆运算的性质定理4.3.1 设 A 和 B 是集合，Ri A × B(i = 1, 2) ,则 是集合， 定理

(1)

(( R ) )1

1 1

= R1 ;

(2) ( R1 I R2 ) 1 = R1 1 I R2 1 ; (3) ( R1 U R2 ) 1 = R1 1 U R2 1 ; (4) ( R1 R2 ) 1 = R1 1 R2 1 ; (5)

(R )1

1

= ( R1 ) ; 1 1 1

(6) 若R1 R2 ,则R

R2 .

1

离散数学

请读P.83的定理证明和例 的定理证明和例4.3.2。 请读 的定理证明和例 。

离散数学

3、逆关系的关系矩阵和关系图R 1的关系矩阵是 R 的关系矩阵的转置矩阵。即 的关系矩阵的转置矩阵 转置矩阵。M R 1 = M RT

R 1的关系图是将 R 的关系图中的有向边反向。 的关系图中的有向边反向 有向边反向。

离散数学

三、关系的合成1、定义定义4.3.3 设 A、B 和 C 是集合，R1 A × B, R2 B × C. 是集合， 定义 、

R1 与 R2 的合成关系是 R1 o R2 A × C , 且

R1 o R2 = { x, z

x ∈ A ∧ z ∈ C ∧ y ( y ∈ B ∧ xR1 y ∧ yR2 z )}

离散数学

例题讲解： 例题讲解： P.84例4.3.3 例 例4 设 A = { 1, 2 } , R A × A , S A × A , 且

} ,S ={ 解： o S = { 1, 1 }; R

R = { 1, 2

2, 1

}, 求R o S和S o R。 S o R = { 2, 2 }

离散数学

例题讲解： 例题讲解： 例5 设 F = { 3, 3 , 6, 2

}, G = {

2, 3

},

求F o G和G o F。解： F o G = { 6, 3

} G o F = { 2, 3 }

可见：合成运算一般不满足交换律。 可见：合成运算一般不满足交换律。 那么，合成运算到底有哪些性质呢？ 那么，合成运算到底有哪些性质呢？

离散数学

2、合成运算的性质定理4.3.2 设 A、B 、C 和 D 是集合， 1 A × B , 是集合， 定理 R

R1 o (R2 o R3 ) = (R1 o R2 ) o R3 .

R2 B × C , R3 C × D , 则

可见：合成运算满足结合律。 可见：合成运算满足结合律。

离散数学

定理4.3.4 设 A、B 、C 和 D 是集合， 1 A × B , 是集合， 定理 R

R2 , R3 B × C , R4 C × D , 则

(1) R1 o (R2 U R3 ) = (R1 o R2 ) U (R1 o R3 ) ;

( 2) (3) ( 4) (5)

(R2 U R3 ) o R4 = (R2 o R4 ) U (R3 o R4 ) ; R1 o (R2 I R3 ) (R1 o R2 ) I (R1 o R3 ) ; (R2 I R3 ) o R4 (R2 o R4 ) I (R3 o R4 ) ; (R1 o R2 ) 1 = R2 1 o R1 1 .

离散数学

3、合成运算的关系矩阵设 M R = (aij )m×n , M S = (bij )n× p , 定义矩阵的运算 M R M S = (cij )m× p , 其中 cij = ∨ (aik ∧ bkj )n k =1

离散数学

定理 …… 此处隐藏：1584字，全部文档内容请下载后查看。喜欢就下载吧 ……