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

习题课-关系


习题课
主要内容 ? 有序对与笛卡儿积的定义与性质 ? 二元关系、从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、在奥运比赛项目中,高台跳水是我国运动员的强项。质量为 m 的跳水运动员进入水中后受到水的阻力而做减速运动,设水对他的阻力大小恒...
习题课 命题及其关系
习题课一、基础过关 命题及其关系 1. “lg x>lg y”是“ x> y”的___条件. →→ 2. 在△ABC 中,“△ABC 为钝角三角形”是“AB· <0”的___条件...
第十课时:功能关系 综合应用习题课
第十课时:功能关系 综合应用习题课_其它课程_高中教育_教育专区。高三一轮物理复习教学案,内容详细,非常实用。2015 年石榴高级中学高三物理教学案设计人 审核: 课时...
第三课时集合关系的习题课
第三课时 集合间关系习题课 制作者: 刘新岩 时间___ 姓名__ 一.教学目标: 能力目标:能够写出一个集合的所有子集或真子集; 能够运用分类讨论法、数形结合法...
《变量之间的关系》习题课1
《变量之间的关系习题课1_数学_初中教育_教育专区。蓬莱市实验中学数学学科教师教案 课题: 《变量之间的关系习题课 设计人 唐芬 教学目标:复习本章所学,并...
数据库关系数据例题
数据库关系数据例题_从业资格考试_资格考试/认证_教育专区。数据库关系模式 作业1: 已知关系模式 R<U, F>, U={A,B,C,D}, F={A?C, C?A, B?AC, D...
立体几何 线面、面面关系习题课2
立体几何 线面、面面关系习题课2_高一数学_数学_高中教育_教育专区。立体几何 基础 实用2.3.6《空间线面、面面关系习题课 2 【学习目标】 知识与技能:掌握...
空间图形的基本关系习题课
2015 届神木四中高一数学组 空间图形的基本关系与公理(习题课)第 周第 课时 编写人:史会婷 高一 班 审核人:薛向荣 组 姓名 使用人: 编写时间:2012. 11. 26...
...版数学必修2导学案:《空间线面、面面关系》习题课2
《空间线面、面面关系习题课 2 一、学习目标: 知识与技能:掌握线线、线面、面面关系的判断和性质; 过程与方法:应用线线、线面、面面关系的判断和性质关系...
关系代数讲解与例题
(6)检索不学 C2 课的学生姓名与年龄。 π SNAME,AGE(S)-π SNAME,AGE(σ...关系代数习题讲解 暂无评价 10页 2下载券 3.2代数式例题与讲解 7页 免费 ...
更多相关标签: