当前位置:首页 >> 数学 >>

习题课-关系


习题课
主要内容 ? 有序对与笛卡儿积的定义与性质 ? 二元关系、从A到B的关系、A上的关系 ? 关系的表示法:关系表达式、关系矩阵、 关系图 ? 关系的运算:定义域、值域、域、逆、合 成、幂 ? 关系运算的性质: A上关系的自反、反自反、 对称、反对称、传递的性质 ? A上关系的自反、对称、传递闭包 ? A上的等价关系、等价类、商集与A的划分 ? A上的偏序关系与偏序集

基本要求
? ? ? ? 熟练掌握关系的三种表示法 能够判定关系的性质 掌握含有关系运算的集合等式 掌握等价关系、等价类、商集、划分、哈斯图、 偏序集等概念 ? 计算A?B, dom R, ranR, fldR, R?1, R?S , Rn , r(R), s(R), t(R), Mi ? 求等价类和商集A/R ? 给定A的划分?,求出? 所对应的等价关系

基本要求
? 求偏序集中的极大元、极小元、最大元、 最小元、上界、下界、上确界、下确界 ? 掌握基本的证明方法 证明涉及关系运算的集合等式 证明关系的性质、闭包性质的证明 、证 明关系是等价关系或偏序关系

证明中用到关系运算的定义和公式
x?domR ? ?y(<x,y>?R) y?ranR ? ?x(<x,y>?R) <x,y>?R ? <y,x>?R?1 <x,y>?R?S ? ?t (<x,t>?R?<t,y>?S) y?R?A] ? ?x (x?A ? <x,y>?R) r(R) = R?IA s(R) = R?R?1 t(R) = R?R2?…

习题课
设A = {1, 2, 3}, R = {<1,1>, <1,2>, <2,1>, <2,2>, <3,1>} , S = {<1,2>, <1,3>,<2,2>}, 求: (1) R?1 (2) dom R, ran R, fld R (3) R?S, R3 (4) r(R), s(R), t(R)

习题课
(1) R?1 = {<1,1>, <2,1>, <1,2>, <2,2>, <1,3 >} (2) domR = {1, 2, 3}, ranR = {1,2}, fldR = {1, 2, 3} (3) R?S = {<1,2>, <1,3>, <2,2>, <2,3>, <3,2>, <3,3>} R3 = {<1,1>, <1,2>, <2,1>, <2,2>, <3,1>, <3,2>} (4) r(R) = {<1,1>, <1,2>, <2,1>, <2,2>, <3,1>, <3,3>} s(R) = {<1,1>,<1,2>,<2,1>, <2,2>, <3,1>, <1,3>} t(R) = {<1,1>, <1,2>, <2,1>, <2,2>, <3,1>, <3,2>}

习题课
设R是Z上的模 n 等价关系, 即 x?y ? x ? y(modn), 试给出由R确定的Z的划分?. 解 设除以 n 余数为 r 的整数构成等价类 [r], 则 [r] ={ kn+r | k?Z }, r = 0, 1, …, n?1 ? = { [r] | r = 0, 1, …, n?1}

习题课已知集合 X 与关系 R,试求 r(R) s(R)
t(R).

X ? {a, b, c, d }, R ? {? a, b ?, ? b, c ?, ? c, d ?, ? d , a ?}
解:
a
R: d
b

a
r ( R) :

b

c

d

c

习题课

X ? {a, b, c, d }, R ? {? a, b ?, ? b, c ?, ? c, d ?, ? d , a ?}
a
R: d
b

a
s( R) :

b

c

d

c

习题课
a
R: d
b

a

b

R?R :
2

c
b

d

c
b

a

a

d
R?R ?R :
2 3

c

d

c
R ? R 2 ? R3 ? R 4 :

习题课
设偏序集 <A, R> 的哈斯图如图所示. (1) 写出A和R的集合表达式 (2) 求极大元、极小元、最大元、最小元、上 (确)界 、下(确)界 a 解 (1) A = {a, b, c, d, e} c b R = {<d,b>, <d,a>, 图11 <d,c>, <e,c>, <e,a>, e <b,a>, <c,a>}?IA d = {<a,a>,<b,a>,…}

习题课
b

a c
d

e

极大元 最小元 上界 上确界 下界 下确界

{a, b, c} {c, d, e} {c, e} {c}

图11

习题课
设R是A上的二元关系, 设 S = {<a,b> |?c(<a,c>?R?<c,b>?R)}. 证明如果R是等价关系,则S也是等 价关系。

关系性质的证明方法
1. 证明R在A上自反 任取x, x?A ? ……………………..….……. ? <x,x>?R 前提 推理过程 结论 2. 证明R在A上对称 任取<x,y>, <x,y> ?R ? ………………………………. ? <y,x>?R 前提 推理过程 结论

关系性质的证明方法
3. 证明R在A上反对称 任取<x,y>, <x,y>?R?<y,x>?R ? …………………….. ? x = y 前提 推理过程 结论
4. 证明R在A上传递 任取<x,y>,<y,z>, <x,y>?R?<y,z>?R ? …………………….. ? <x,z>?R 前提 推理过程 结论

习题课 设R是A上的二元关系, 设
S = {<a,b> | ?c(<a,c>?R?<c,b>?R)}. 证明如果R是等价关系,则S也是等价关系。
(1) 证自反 任取x, x?A ? <x,x>?R ? ?x (<x,x>?R?<x,x>?R) ? <x,x>?S (2) 证对称 任取<x,y>, <x,y>?S ? ?c(<x,c>?R?<c,y>?R) ? ?c (<c,x>?R?<y,c>?R) ?<y,x>?S

(3) 证传递 任取<x,y>, <y,z>, <x,y>?S ? <y,z>?S ? ?c (<x,c>?R?<c,y>?R) ? ?d (<y,d>?R?<d,z>?R) ? <x,y>?R?<y,z>? R ? <x,z>?S

习题课试证对称关系的传递闭包也是对称关系 证明:
若 <a,b> ? t(R), 则有 i, 使得 <a,b>?R(i), 即存在 c1,c2,…,ci-1 ? X, <a,c1> ? R, <c1,c2> ? R, … , <ci-1,b> ? R 因为 R 是对称的,有 <b,ci-1> ? R, … , <c1,a> ? R, 得到 <b,a> ? R(i) , 即 <b,a> ? t(R). 得证.

习题课反对称关系的传递闭包总是反对称关系? 解:不一定,例如:

X ? {1,2,3}, R ? {? 1,2 ?, ? 2,3 ?, ? 3,1 ?} t ( R) ? {? 1,1 ?, ? 1,2 ?, ? 1,3 ?, ? 2,1 ?, ? 2,2 ?, ? 2,3 ?, ? 3,1 ?, ? 3,2 ?, ? 3,3 ?}
是对称的.

习题课

试证 性质 rs(R) = sr(R)

证明:设 I 是 A 上的恒等关系 A

sr ( R) ? s ( R ? I A ) ?1 ? (R ? I A ) ? (R ? I A ) ?1 ?1 ? R ? IA ? R ? IA ?1 ? R ? R ? IA ?? s( R) ? I A ? rs ( R)

习题课 若 R1? R2, 则 r(R1) ? r(R2)
法1. 因为R1? R2, 所以R1∪IA ? R2∪IA;

因此r(R1) ? r(R2)。
法2. 因为r(R2) 自反且R2 ? r(R2), 由于 R1? R2,所以R1 ? r(R2); 由r(R1)的定义,r(R1)是包含R1的最小 的自反关系;所以r(R1) ? r(R2)。

习题课 试证 性质 st(R) ? ts(R)
证明:已证若R1? R2, 则 s(R1) ? s(R2), t(R1) ? t(R2) 根据闭包的定义,可得 R ?s(R) 所以 t(R) ?ts(R) , st(R) ?sts(R)

又因为对称关系的传递闭包是对称的, 所以ts(R)是对称的, 而一个关系R是对称的充要条件是 R=s(R),所以 sts(R)= ts(R), 从而st(R) ? ts(R) . 得证.

Test1

已知 A ? {a, b}, B ? {1,2} 求 A? B B ? A A? A B ? B

Test1-Answer

A ? B ? {? a,1 ?, ? a,2 ?, ? b,1 ?, ? b,2 ?} B ? A ? {? 1, a ?, ? 1, b ?, ? 2, a ?, ? 2, b ?} A ? A ? {? a, a ?, ? a, b ?, ? b, a ?, ? b, b ?} B ? B ? {? 1,1 ?, ? 1,2 ?, ? 2,1 ?, ? 2,2 ?}

已知 A ? {a, b}, B ? {1,2} 求 A? B B ? A A? A B ? B 解: A ? B ? B ? A

Test2
?X ?{ 1, 2 ,3} Y ? { r , s} R ?{? 1,r ?,? 2,s ?,? 3,r ?}R是?

?A ? {1, 2 ,3}

R是?

R ? { ? 1, 2 ? , ? 1,3 ? , ? 2 ,3 ? } ?A ? {1, 2 , 3} I A? {? 1,1 ?, ? 2,2 ?, ? 3,3 ?}

Test2-Answer
?X ?{ 1, 2 ,3} Y ? { r , s} R ?{? 1,r ?,? 2,s ?,? 3,r ?}从X到Y的关系

?A ? {1, 2 ,3}

R是A上的小于关系

R ? { ? 1, 2 ? , ? 1,3 ? , ? 2 ,3 ? } ?A ? {1, 2 , 3} I A? {? 1,1 ?, ? 2,2 ?, ? 3,3 ?}

集合A上的恒等关系

Test3
C ? {2, 3 ,6}
?L 是C上的小于关系 ?D是C上的整除关系

?C上的恒等关系 A ? {a, b } ?P(A)上的包含关系

Test3-Answer
C ? {2, 3 ,6}
?L 是C上的小于关系 ?D是C上的整除关系

?C上的恒等关系 A ? {a, b } ?P(A)上的包含关系
L ? { ? 2, 3 ? , ? 2,6 ? , ? 3 ,6 ? }

D ? { ? 2, 2 ? , ? 2,6 ? , ? 3 ,3 ? , ? 3,6 ? , ? 6,6 ? }
R? = {<?,?>,<?,{a}>,<?,{b}>,<?,{a,b}>,<{a},{a}>, <{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>}

Test4
已知有五个城市的航班服务,下表是从 ci到cj的航线的票价,
From To

C1 1900 1100 1900 2000

C1 C2 C3 C4 C5

C2 1400

C3 1000 2000

1800 2000 1000

C4 1500 1600 1900 1500

1200 2000

C5 2000 2200 2500 1500

R是定义在城市的集合 A={c1,c2,c3,c4,c5}上的关系, ci R cj当且仅当从ci到cj的票价 小于1500.

Test4-Answer
已知有五个城市的航班服务,下表是从 ci到cj的航线的票价,
From To

C1 1900 1100 1900 2000

1500 ? R是定义在城市的集合 A={c1,c2,c3,c4,c5}上的关系, ci R cj当且仅当从ci到cj的票价 小于1500.

C1 C2 C3 C4 C5

C2 1400

?

?

C3 1000 2000

?

1800 2000 1000

1200 2000

?

C4 1500 1600 1900

C5 2000 2200 2500 1500

解: R= {<c1,c2>, <c1,c3>, <c3,c1>, <c4,c3>, <c5,c2>}

Test5
已知 X ? {1,2,3,4} R ? {? x, y ? ( x, y ? X ) ? ( x ? y)} 试求 M R . 解: R ? {? 2,1 ?, ? 3,1 ?, ? 3,2 ?,
?0 ? ?1 ?? 1 ? ?1 ? 0 0 1 1 0 0 0 1 0? ? 0? 0? ? 0? ?

? 4,1 ?, ? 4,2 ?, ? 4,3 ?}

MR

Test5-Answer
已知 X ? {1,2,3,4} R ? {? x, y ? ( x, y ? X ) ? ( x ? y)} 试求 M R . 解: R ? {? 2,1 ?, ? 3,1 ?, ? 3,2 ?,
?0 ? ?1 MR ? ? 1 ? ?1 ? 0 0 1 1 0 0 0 1 0? ? 0? 0? ? 0? ?

? 4,1 ?, ? 4,2 ?, ? 4,3 ?}
1
2

4

3

Test6
已知
b

a
d

c

求关系及关系矩阵

Test6-Answer
已知
b

解:

a
d

c

R={<a,a>,<b,b> <c,a>,<c,b>,<c,c> <d,b>,<d,d>}
?1 ? 0 ? MR ? ?1 ? ?0 0 1 1 1 0 0 1 0 0? ? 0? 0? ? 1?

求关系及关系矩阵

Test7 已知集合 X 和关系 R, 试分别用关 X ? {a, b, c, d}, 系图和关系矩阵求 Rn.

R ? {? a, b ?, ? b, a ?, ? b, c ?, ? c, d ?}

Test7-Answer 已知集合 X 和关系 R, 试 求 Rn. X ? {a, b, c, d },

R ? {? a, b ?, ? b, a ?, ? b, c ?, ? c, d ?}
b

解:

R: a

c

d

R : a
4

2

b

c

d

R: a

3

b

c

d R : a

b

c

d

Test8 已知X={a,b,c}
R1 ? {? a, a ?, ? a, b ?, ? b, b ?, ? c, c ?}

R 2 ? {? a, a ?, ? a, b ?, ? b, b ?, ? c, a ?}

R 3? {? a, c ?, ? a, b ?, ? b, a ?, ? c, c ?}
R 4 ? {? a, a ?, ? a, b ?, ? b, a ?, ? c, c ?} R 5? {? a, a ?, ? a, b ?, ? b, a ?, ? b, b ?, ? c, c ?}

R 6 ? {? a, b ?, ? b, c ?, ? a, c ?}

R 7 ? {? a, b ?, ? b, c ?, ? c, a ?} R 8 ? {? a, b ?, ? a, c ?}

Test8 -Answer自反的
? R1 ? {? a, a ?, ? a, b ?, ? b, b ?, ? c, c ?}
R 2 ? {? a, a ?, ? a, b ?, ? b, b ?, ? c, a ?}

R 3? {? a, c ?, ? a, b ?, ? b, a ?, ? c, c ?}
R 4 ? {? a, a ?, ? a, b ?, ? b, a ?, ? c, c ?} ? R 5? {? a, a ?, ? a, b ?, ? b, a ?, ? b, b ?, ? c, c ?}

R 6 ? {? a, b ?, ? b, c ?, ? a, c ?}

R 7 ? {? a, b ?, ? b, c ?, ? c, a ?} R 8 ? {? a, b ?, ? a, c ?}

Test8 –Answer 反自反的
R1 ? {? a, a ?, ? a, b ?, ? b, b ?, ? c, c ?}

R 2 ? {? a, a ?, ? a, b ?, ? b, b ?, ? c, a ?}

R 3? {? a, c ?, ? a, b ?, ? b, a ?, ? c, c ?}
R 4 ? {? a, a ?, ? a, b ?, ? b, a ?, ? c, c ?} R 5? {? a, a ?, ? a, b ?, ? b, a ?, ? b, b ?, ? c, c ?}

? R 6 ? {? a, b ?, ? b, c ?, ? a, c ?} ? R 7 ? {? a, b ?, ? b, c ?, ? c, a ?} ? R 8 ? {? a, b ?, ? a, c ?}

Test8-Answer 对称的
R1 ? {? a, a ?, ? a, b ?, ? b, b ?, ? c, c ?}

R 2 ? {? a, a ?, ? a, b ?, ? b, b ?, ? c, a ?}

R 3? {? a, c ?, ? a, b ?, ? b, a ?, ? c, c ?}

? R 4 ? {? a, a ?, ? a, b ?, ? b, a ?, ? c, c ?} ? R 5? {? a, a ?, ? a, b ?, ? b, a ?, ? b, b ?, ? c, c ?}

R 6 ? {? a, b ?, ? b, c ?, ? a, c ?}
R 7 ? {? a, b ?, ? b, c ?, ? c, a ?} R 8 ? {? a, b ?, ? a, c ?}

Test8-Answer 反对称 ? R1 ? {? a, a ?, ? a, b ?, ? b, b ?, ? c, c ?} ? R 2 ? {? a, a ?, ? a, b ?, ? b, b ?, ? c, a ?}
R 3? {? a, c ?, ? a, b ?, ? b, a ?, ? c, c ?}
R 4 ? {? a, a ?, ? a, b ?, ? b, a ?, ? c, c ?} R 5? {? a, a ?, ? a, b ?, ? b, a ?, ? b, b ?, ? c, c ?}

? R 6 ? {? a, b ?, ? b, c ?, ? a, c ?} ? R 7 ? {? a, b ?, ? b, c ?, ? c, a ?} ? R 8 ? {? a, b ?, ? a, c ?}

Test8-Answer 传递的
? R1 ? {? a, a ?, ? a, b ?, ? b, b ?, ? c, c ?}
R 2 ? {? a, a ?, ? a, b ?, ? b, b ?, ? c, a ?}

R 3? {? a, c ?, ? a, b ?, ? b, a ?, ? c, c ?}
R 4 ? {? a, a ?, ? a, b ?, ? b, a ?, ? c, c ?} ? R 5? {? a, a ?, ? a, b ?, ? b, a ?, ? b, b ?, ? c, c ?}

? R 6 ? {? a, b ?, ? b, c ?, ? a, c ?} R 7 ? {? a, b ?, ? b, c ?, ? c, a ?} ? R 8 ? {? a, b ?, ? a, c ?}

问题:


不一定。

一个关系不是自反的,就一 定是反自反的吗?

如:A={1,2,3},
S={<1,1>,<1,2>,<2,3>,<3,3>} 则 S 既不是自反的也不是反自反的。

问题:



一个关系不是对称的,就一定 是反对称的吗?

不一定。

如:A={1,2,3},
S={<1,2>,<1,3>, <3,1>} 则 S 既不是对称的也不是反对称的。 IA={<1,1>,<2,2>,<3,3>} IA即是对称的,也是反对称的。

关系性质成立的充要条件
定理 设R为A上的关系, 则 (1) R 在A上自反当且仅当 IA ? R (2) R 在A上反自反当且仅当 R∩IA = ? (3) R 在A上对称当且仅当 R=R?1 (4) R 在A上反对称当且仅当 R∩R?1 ? IA (5) R 在A上传递当且仅当 R?R ? R

Test9 已知集合X与关系R,求r(R) s(R) t(R).

X ? {a, b, c},

R ? {? a, b ?, ? b, c ?}

Test9-Answer 求r(R) s(R) t(R).

X ? {a, b, c}, 解:

R ? {? a, b ?, ? b, c ?}

? R ? {? a, a ?, ? b, b ?, ? c, c ?} ? {? a, b ?, ? b, c ?, ? a, a ?, ? b, b ?, ? c, c ?}
-1 ? ? s( R) R R

r ( R) ? R ? I X

? {? a, b ?, ? b, c ?, ? b, a ?, ? c, b ?}

Test9-Answer(续)

X ? {a, b, c},
R ? {? a, c ?}
2

R ? {? a, b ?, ? b, c ?}
R ??
3 3

t ( R) ? R ? R ? R
2

? {? a, b ?, ? b, c ?} ?{? a, c ?} ? {? a, b ?, ? b, c ?, ? a, c ?}

Test10 已知集合 X 和关系 R, 试求 t(R).

X ? {a, b, c, d}, R ? {? a, b ?, ? b, a ?, ? b, c ?, ? c, d ?}

Test10 -Answer 已知集合 X 和关系 R, 试 求 t(R). X ? {a, b, c, d },

R ? {? a, b ?, ? b, a ?, ? b, c ?, ? c, d ?}

解:

R: a

b

c

d

t ( R) : a

b

c

d

Test10-Answer(续)
?0 ?1 MR ? ? ?0 ? ?0 ?0 ?1 M R3 ? ? ?0 ? ?0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0? ?1 ?0 0? ? M ?? R2 1? ?0 ? ? 0? ?0 0 1 0 0 1 0 0 0 1 0 0 0 0? ? 1? 0? ? 0? 0? 1? ? 0? ? 0?

M t (R) ? ?1 ?1 ? ?0 ? ?0 1 1 1? ? 1 1 1? 0 0 1? ? 0 0 0?

1? ?1 0 ?0 1 0? ? M 4 ?? 0? R ?0 0 ? ? 0? ?0 0

Test11 已知A ? {2,3,5,7,14,15,21}
偏序关系哈斯图如下

14

21

15

B ? {2,7,3,21,14} B 的极大元:

2

7

3

5

B 的极小元:

当 B=A 时,其极大元是?,极小元是?

? {2,3,5,7,14,15,21 } Test11-AnswerA 已知
偏序关系哈斯图如下

14

21

15

2

7

3

5

B ? {2,7,3,21,14} B 的极大元: 14, 21 B 的极小元:

2, 7, 3

极大元与极小元不惟一

当 B=A 时,其极大元是14,21,15,极小元 是2,7,3,5

Test12 ?

P{a, b}, R? ?
B={{a}, φ },
最大元: 最小元:

{a, b} {a} {b}

?

B? ={{a},{b}},
最大元: 最小元:

Test12-Answer ?

P{a, b}, R? ?
B={{a}, φ },
最大元:{a} 最小元:φ

{a, b} {a} {b}

?

B? ={{a},{b}},
最大元:无 最小元:无

Test13
j

k

h
f

i

B={a,b,c,d,e,f,g} 上界: 下界: B?={h,i,j,k} 上界: 下界: B??= 上界: 下界:

g

b

c a

d

e

Test13-Answer
j

k

h
f

i

B={a,b,c,d,e,f,g} 上界: h,i,j,k 下界:无 B?={h,i,j,k} 上界: 无 下界:a,b,c,d,e,f,g B??={h,i,f,g} 上界: k 下界:a

g

b

c a

d

e

上界、下界 不惟一

Test14
j

k

B={a,b,c,d,e,f,g}

h
f

i

B?={h,i,j,k}

g

b

c a

d

e

B??={h,i,f,g}

Test14-Answer
j

k

h
f

i

B={a,b,c,d,e,f,g} 上界: h,i,j,k 无上(下)确界 下界:无 B?={h,i,j,k} 上界: 无 无上(下)确界 下界: a,b,c,d,e,f,g

g

b

c a

d

e

B??={h,i,f,g} 上确界: 上界: k k 下确界: 下界:a a

Test15 <{2,3,6,12,24,36},整除关系> 画出哈斯图,并求 B = {2,3,6} 上、下(确)界

24 12
6

36

上界: 6,12,24,36

上确界:6
3

下(确)界: 无

2

Test16 <{1,2,…,12}, R整除>, 画出哈斯图,并求 B = {2,3,6} 上、下(确)界

8

12
上界: 6,12

4
10

6 3

9 7

上确界:6
下(确)界: 1

11

5

2 1

Test17

已知哈斯图, 求 B={c,d,e}的 上、下(确)界

e c
d

g

上界: e 上确界:e 下界: a,b

下确界:无

a

b

f

h

Test18-Answer
已知X={a,b,c,d,e}, C={{a,b},{c},{d,e}} 试写出由 C 导出的 X 中的等价关系 R , 并给出关系矩阵和关系图.

Test18-Answer
已知X={a,b,c,d,e}, C={{a,b},{c},{d,e}} 试写出由 C 导出的 X 中的等价关系 R , 并给出关系矩阵和关系图. 解:R ? {a, b} ? {a, b} ? {c} ? {c}

? {d , e} ? {d , e} ? {? a, a ?, ? a, b ?, ? b, a ?, ? b, b ?, ? c, c ?, ? d , d ?, ? d , e ?, ? e, d ?, ? e, e ?}

Test18-Answer(续)
?1 ? ?1 M R ? ?0 ? ?0 ?0 ? 1 0 0 0? ? 1 0 0 0? 0 1 0 0? ? 0 0 1 1? ? 0 0 1 1?

c

a

d

b

e

Test19 已知 X ? {a, b, c, d }

R ? {? a, a ?, ? a, b ?, ? b, a ?, ? b, b ? ? c, c ?, ? c, d ?, ? d , c ?, ? d , d ?}
试画出 R 的等价关系图, 并求出各元素 的 R 等价类.

Test19-Answer 已知 X ? {a, b, c, d }

R ? {? a, a ?, ? a, b ?, ? b, a ?, ? b, b ? ? c, c ?, ? c, d ?, ? d , c ?, ? d , d ?}
试画出 R 的等价关系图, 并求出各元素 的 R 等价类. d 解: b

a

c

?a?R ? ?b?R ? {a, b} ?c?R ? ?d ?R ? {c, d}

Test20 已知 A={a,b,c,d,e}

R ?{? a, a ?, ? a,b ?, ? a, c ?, ? a, d ?, ? a, e ?, ? b,b ?, ?b,c ?,?b,e ?,?c,c ?,?c,e ?,?d,d ?,?d,e ?,?e,e ?}
验证 <A,R> 是偏序集,画出哈斯图

Test20-Answer 已知 A={a,b,c,d,e}
验证 <A,R> 是偏序集,画出哈斯图
解:
?1 ? ?0 M R ? ?0 ? ?0 ? ?0 1 1 1 1? ? 1 1 0 1? 0 1 0 1? ? 0 0 1 1? 0 0 0 1? ?

R ?{? a, a ?, ? a,b ?, ? a, c ?, ? a, d ?, ? a, e ?, ? b,b ?, ?b,c ?,?b,e ?,?c,c ?,?c,e ?,?d,d ?,?d,e ?,?e,e ?}

关系矩阵对角线 都为1,且rij 和rji 不同时为1,所以 R 是自反的和反 对称的。

Test20-Answer(续)
关系图

e
d

哈斯图

e

c
b

c
b d

a
R是传递的。

COVA={<a,b>,<a,d>, <b,c>, <c,e>,<d,e>}

a

Test21
(1) A1={1,2,3,4}

?为小于等于关系
(3) A3={a, b}

(2) A2={φ ,{a},{a,b}, {a,b,c}} ?为包含关系

(4) A4={2,3,6,12,24,36} ?为P(A3)上的包含关系 ?为整除关系

Test21-Answer
A1={1,2,3,4}

?为小于等于关系 4 3 2 1

A2={φ ,{a},{a,b}, {a,b,c}} ?为包含关系

?

{a, b, c} {a, b} {a}

不同的偏序集, 哈斯图可以有同样的结构

Test21 –Answer <{2,3,6,12,24,36},整除关系>

? = {<2,6>, <2,12>, <2,24>, <2,36>,
<3,6>, <3,12>, <3,24>, <3,36>, <6,12>, <6,24>, <6,36>, <12,24>, <12,36>} ∪ IA COVA={<2,6>,<3,6>,<6,12>, <12,24>, <12,36>}

24 12
6

36

2

3

Test21-Answer

? P{a, b}, R? ?

{a, b} {a} {b}

?


相关文章:
习题课
习题课_理学_高等教育_教育专区。习题课 1. 设关系模式 R(职工名,项目名,工资,部门名,部门经理),若每个职工可参加多个项目, 各领一份工资;每个项目只属于一...
四种命题相互关系练习题
四种命题相互关系练习题_语文_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档四种命题相互关系练习题_语文_高中教育_教育专区。课时作业(二) [学业水平层次...
功能关系练习题
功能关系练习题 1.某人从一楼匀速率上到三楼的过程中,下述说法正确的是 ( 1...功能关系习题课 3页 1下载券 功能习题(附简单答案)功... 4页 2下载券 功能...
模式分解例题
模式分解例题_工学_高等教育_教育专区。数据库考试习题,模式分解 ...4)求学过数据库的先行课的学生学号。 程序设计题 现有关系数据库如下: 学生(...
练习课与复习课及其联系和区别
练习课的误区 1、上成新授课。把书中的习题当作例题或补充同类型的例题进行...6、总结——总结各知识间的相互关系,进一步明晰和完善学生的认知结构,通常借助...
集合间的关系典型例题
集合间的关系典型例题_高三数学_数学_高中教育_教育专区。集合间的关系典例分析...2.集合间的基本关系习题... 暂无评价 5页 免费 1.1.2集合间的基本关系习....
关系数据理论练习题
一、选择题 1 设有关系模式 W(C,P,S,G,T,R),其中各属性的含义是:C 课程,P 教师, S 学生,G 成绩,T 时间,R 教室,根据语义有如下数据依赖集: D={...
高一功能关系专项练习题
高一功能关系专项练习题_理化生_高中教育_教育专区。高一物理功能关系专题训练卷功能关系:功是能的转化的量度,做功的过程就是能量转化的过程,不同形式的能的转化又...
习题课(精选)答案(1-4章)
习题课(精选)答案(1-4章)_教育学_高等教育_教育专区。习题 第一章 1、按照...答:1.反应必须具有确定的化学计量关系, 即反应按一定的反应方程式进行, 这是...
三角形三边关系课堂练习题
三角形三边关系课堂练习题_数学_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 三角形三边关系课堂练习题_数学_初中教育_教育专区。环节三:课堂练习 1....
更多相关标签: