离散数学复习资料(3)

| 0 0 0 |

| 0 0 0 | MR^3= | 1 1 0 |

| 0 0 0 | | 0 0 0 |

可见： t(R)=MR ∪MR^2∪MR^3={,} 4、设 A={1,2,3,4}上的二元关系， R={<1,2>,<2,4>,<3,3>,<1,3>}，则：

r(R)={<1,1>,<2,2>,<4,4>,<1,2>,<2,4>,<3,3>,<1,3>} S(R)={<1,2>,<2,4>,<3,3>,<1,3>,<2,1>,<4,2>,<3,1>} t(R)=

MR= | 0 1 1 0 |

| 0 0 0 1 | ={<1,2>,<2,4>,<3,3>,<1,3>} | 0 0 1 0 |

| 0 0 0 0 |

MR^2= | 0 1 1 0 | | 0 1 1 0 | | 0 0 1 1 | | 0 0 0 1 | | 0 0 0 1 | =| 0 0 0 0 |

| 0 0 1 0 | 。| 0 0 1 0 | | 0 0 1 0 |

| 0 0 0 0 | | 0 0 0 0 | | 0 0 0 0 | ={<1,3>,<1,4>,<3,3>} MR^3= | 0 0 1 1 | | 0 1 1 0 | | 0 0 1 0 | | 0 0 0 0 | | 0 0 0 1 | =| 0 0 0 0 | | 0 0 1 0 | 。| 0 0 1 0 | | 0 0 1 0 |

| 0 0 0 0 | | 0 0 0 0 | | 0 0 0 0 | ={<1,3>,<3,3>} MR^4= | 0 0 1 0 | | 0 1 1 0 | | 0 0 1 0 | | 0 0 0 0 | | 0 0 0 1 | =| 0 0 0 0 |

| 0 0 1 0 | 。| 0 0 1 0 | | 0 0 1 0 |

| 0 0 0 0 | | 0 0 0 0 | | 0 0 0 0 | ={<1,3>,<3,3>} 可得t(R)={<1,2>,<2,4>,<3,3>,<1,3>} ∪{<1,3>,<1,4>,<3,3>} ∪{<1,3>,<3,3>} ∪{<1,3>,<3,3>}

={<1,2>,<1,4>,<2,4>,<3,3>,<1,3>}

5、设R、Q都是集合A上自反、对称、传递关系，则

s(R∩Q)=_________，t(R∩Q)=_________.因为_________也是自反、对称、传递的。 s(R)∩s(Q) t(R)∩t(Q) R∩Q 6、集合 A={1,2,3,4,5,6}的关系图如下所示，求： a) R,R^2，R^3及关系图

解： R={<1,3>,<1,5>,<2,5>,<3,3>,<4,5>,<5,4>} MR^2=

| 0 0 1 0 1 0 | | 0 0 1 0 1 0 | | 0 0 1 1 0 0 | | 0 0 0 0 1 0 | | 0 0 0 0 1 0 | | 0 0 0 1 0 0 | | 0 0 1 0 0 0 | | 0 0 1 0 0 0 | = | 0 0 1 0 0 0 | | 0 0 0 0 1 0 | 。| 0 0 0 0 1 0 | | 0 0 0 1 0 0 | | 0 0 0 1 0 0 | | 0 0 0 1 0 0 | | 0 0 0 0 1 0 | | 0 0 0 0 0 0 | | 0 0 0 0 0 0 | | 0 0 0 0 0 0 | R^2={<1,3>,<1,4>,<2,4>,<3,3>,<4,4>,<5,5>}

11

MR^3=

| 0 0 1 1 0 0 | | 0 0 1 0 1 0 | | 0 0 0 1 1 0 | | 0 0 0 1 0 0 | | 0 0 0 0 1 0 | | 0 0 0 0 1 0 | | 0 0 1 0 0 0 | 。| 0 0 1 0 0 0 | = | 0 0 1 0 0 0 | | 0 0 0 1 0 0 | | 0 0 0 0 1 0 | | 0 0 0 0 1 0 | | 0 0 0 0 1 0 | | 0 0 0 1 0 0 | | 0 0 0 1 0 0 | | 0 0 0 0 0 0 | | 0 0 0 0 0 0 | | 0 0 0 0 0 0 | R^3={<1,4>,<1,5>,<2,5>,<3,3>,<4,5>,<5,4>} b) r(R),s(R);

r(R)={<1,3>,<1,5>,<2,5>,<3,3>,<4,5>,<5,4>,<1,1>,<2,2>,<4,4>,<5,5>,<6,6>} s(R)={<1,3>,<3,1>,<1,5>,<5,1>,<2,5>,<5,2>,<4,5>,<5,4>}

7、令S为从X到Y的关系，T为从Y到Z的关系，对于 A X，定义S(A)={y|?S∧x?A} 证明： a) S(A) Y

b) (S。T)(A)=T(S(A));

c) S(A∪B)=S(A)∪S(B),其中B X d) S(A∩B) S(A)∩S(B)

8、设： R1和R2是A上的关系，证明： a) r(R1∪R2)=r(R1)∪r(R2);

证明如下：因为R1，R2是A上关系，所以R1∪R2也是A上关系； 由r(R1)=R1∪IA 和r(R2)=R2∪IA可得 r(R1)∪r(R2)= R1∪R2∪IA

又因r(R1∪R2)=(R1∪R2)∪IA 所以左右相等。

b) s(R1∪R2)=s(R1)∪s(R2); 证明如下：

左边=s(R1∪R2)=(R1∪R2)∪(R1∪R2)-1 右边=s(R1)∪s(R2)=R1∪R1-1∪R2∪R2-1 =R1∪R2∪R1-1∪R2-1 =(R1∪R2)∪(R1∪R2)-1 =左边 等式成立。

c) t(R1∪R2) t(R1)∪t(R2);

因为:t(R1)=R1∪R12∪R13∪...∪R1n(n为A中元素个数) t(R2)=R2∪R22∪R23∪...∪R2n

则 t(R1)∪t(R2)=R1∪R2∪R12∪R22∪R13∪R23∪...∪R1n∪R2n 左边=t(R1∪R2)=(R1∪R2)∪(R1∪R2)2∪......∪(R1∪R2)n 设A中有任意?R1 ，任意?R2 则有?t(R1) ?t(R2)

(1)因为,?(R1∪R2) (2)则有,?t(R1∪R2)(3)

因此由(1)(2)(3)式可得：t(R1∪R2) t(R1)∪t(R2); 3.6习题答案

12

1、给定集合X={x1,x2,....,x6},ρ是X上相容关系且Mρ简化矩阵为： 试求X的覆盖，并画出相容关系图。 解：覆盖如下：

{,,,,,,,,,, ,,,,,,,} 晓津觉得覆盖中的元素应该是集合：我的答案是： S={{x1,x2,x3},{x4,x5,x6}} 当然这只是一个覆盖。

2、从下面给出的关系图中，说明哪个是相容关系。 答：图3、4是相容关系。

3、设集合A={1,2,3,4}中的一个覆盖为 B={{1,2},{2,3,4}},求出确定的相容关系。 解： S1={1,2} S2={2,3,4}

根据定理3.6.1：ρ=S1×S1∪S2×S2

={<1,1>,<1,2>,<2,1>,<2,2>}∪{<2,2>,<2,3>,<2,4>,<3,2>,<3,4>,<3,3>,<4,2>,<4,3>,<4,4>} ={<1,1>,<1,2>,<2,1>,<2,2>,<2,3>,<2,4>,<3,2>,<3,4>,<3,3>,<4,2>,<4,3>,<4,4>}

4、设αβ是A上相容关系，

a) 复合关系α。β是A上的相容关系吗？

由于自反性通过,运算可保持;但对称性不能通过,保持。所以复合关系α。β不是A上的相容关系 b) α∪β是A上相容关系吗？ 是的

晓津补充证明如下:

(1)因为α，β是A上相容关系，若有任意x?A，则?α且?β， 所以?α∪β 因此α∪β是自反的。

(2)因为α，β是A上的相容关系，若有任意x,y?A且?α 则有?α； 若有任意u,v?A且?β，则有?β， 所以有，,,?α∪β 因此α∪β是对称的。

可得α∪β是A上相容关系。 c) α∩β是A上相容关系吗？ 是的

晓津证明如下：

(1)因为α，β是A上相容关系，则若有任意x?A,就有?α∩β，因此α∩β是自反的。

(2)因为α，β是A上相容关系，则若有任意x,y?A且?α且?β则有?α且?β 即,?α∩β 因此α∩β是对称的。

可得α∩β是A上相容关系。 3.7 习题参考答案

1、设R是一个二元关系，设S={ |存在某个C，使?R且?R}，证明R是一个等价关系，则S也是一个等价关系。 证明：

如果题目反一下是：S是一个等价关系，则R也是一个等价关系。或许能证出吧 晓津看法:题中的大写C应为小写c;请学友提供您的看法。 （1）∵R是自反，

∴若有x?A就有＜x，x＞?R

13

∴＜x，x＞?S ∴S是自反的。 （2）因有＜a，b＞?S

且存在c，使＜a，c＞?R且＜c，b＞?R ∵R是对称的

∴＜c，a＞?R，＜b，c＞?R ∴＜b，a＞?S ∴S是对称的

（3）设＜a，b＞，＜b，c＞?S

则存在d,e使＜a，d＞，＜d，b＞，＜b，e＞，＜e，c＞?R ∵R是传递的

∴＜a，b＞，＜b，c>?R ∴＜a，c＞?S 即S是传递的

因此得证S是等价关系。

2、设R是A上一个自反关系，证明：R是一个等价关系，当且仅当若 ?R,?R,则?R。 证明：由于R是一个等价关系，所以R是传递的。由此可知：若?R,根据对称性，则有?R 已知： ?R且?R,根据传递性，必有 ?R

晓津认为：jhju的证明中，已经在前提中确定了R是一个等价关系，这种理解应是不正确的。我的理解是： 前提：R是A上的自反关系

结论：R是一个等价关系 iff (aRb,aRc→bRc)

等价关系的充要条件是R为自反的，对称的和传递的。但是我也无法证出来。请胖胖、sphinx、菜虫虫和ryz和其他朋友提供您的思路好吗? 下面是linuxcn

和阮允准同学给出的证明(晓津作了综合)： 证明：1）

设有a,b,c?A，若有?R，?R 因为R是对称的，所以必有?R

又因为R是传递的，由,?R，有?R

2）由(a,b)?R,(a,c)?R,则(b,c)?R。证等价关系,其实只需证传递关系和对称关系。如下： 设有任意的?R ∵R是自反的 ∴?R ∴?R ∴R是对称的

对任意的,?R 由R是对称的 ∴?R

∴由?R，?R 可得?R ∴R是传递的 ∴R是等价关系。

3、设R为集合A上一个等价关系，对任何a?A,集合 [a]R=____[a]R={x| x?A,aRx}________称为元素a形成的等价类。[a]R≠φ，因为_____ A=φ______。 阮允准给出后一空的正确答案： a?[a] 4、设R是A上的自反和传递关系， 证明：R∩R-1 是A上的一个等价关系。 证明：R是A上的自反关系，所以

14

?R 且 ?R-1 ?R∩R-1 R是A上的传递关系, 则：

若有?R 且 ?R,则有?R

由于R又具有对称性，所以?R 且 ?R,则有?R R-1 也有：?R-1

且?R-1 ,则有?R-1 可见：?R∩R-1

且?R∩R-1 ,则有?R∩R-1

R是A上的对称关系，则有 ?R、?R R-1 是A上的对称关系，也有 ?R、?R 则有： ?R∩R-1 、?R∩R-1 由于R∩R-1

有对称性，传递性、自反性。所以说R∩R-1 是等价关系。

上面的红色部分有点问题，已知条件中并未给出这样的前提。晓津证明如下： (1)因为R是A上的自反关系,若有a?A，则 ?R且?R-1 即?R∩R-1

所以R∩R-1是自反的。

(2)因为R是A上的传递关系，则R-1也是A上传递关系，若有a,b,c?A,则 若?R∩R-1且?R∩R-1 必有?R∧?R 且?R-1∧ 因此有?R ∧?R-1 即?R∩R-1

所以R∩R-1是传递的。

(3)若有a,b?A 则

若?R∩R-1

就有?R且?R-1

同时因为?R，有?R-1;?R-1则有?R 因此有,?R∩R-1

________________________________________ 5、集合A={1,2,3,4,5}上划分为S={{1,2},{3,4,5}}, a) 写出由S导出的A上等价关系ρ;

b) 画出ρ的关系图，求Mρ。

解：a)ρ={{1,2}×{1,2}}∪{{3,4,5}×{3,4,5}}

={<1,1>,<1,2>,<2,1>,<2,2>}∪{<3,3>,<3,4>,<3,5>,<4,3>,<4,4>,<4,5>,<5,3>,<5,4>,<5,5>}

15

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散数学复习资料(3)在线全文阅读。