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

习题课-关系


习题课
主要内容 ? 有序对与笛卡儿积的定义与性质 ? 二元关系、从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-1) 1 《命题及其关系习题课 命题及其关系》一、 知识点 1、四种命题及其关系(用图表示) (互为逆否命题的两个命题 2、充...
习题课
习题课_理学_高等教育_教育专区。习题课 1. 设关系模式 R(职工名,项目名,工资,部门名,部门经理),若每个职工可参加多个项目, 各领一份工资;每个项目只属于一...
功能关系习题课教案
功能关系习题课教案_理化生_高中教育_教育专区。功能关系习题课教案 专题课:功能关系一、复习:各种形式的能发生转化是通过力做功来实现的。做功的过程就是能量转化...
第三课时集合关系的习题课
第三课时 集合间关系习题课 制作者: 刘新岩 时间___ 姓名__ 一.教学目标: 能力目标:能够写出一个集合的所有子集或真子集; 能够运用分类讨论法、数形结合法...
《变量之间的关系》习题课1
《变量之间的关系习题课1_数学_初中教育_教育专区。蓬莱市实验中学数学学科教师教案 课题: 《变量之间的关系习题课 设计人 唐芬 教学目标:复习本章所学,并...
第十课时:功能关系 综合应用习题课
第十课时:功能关系 综合应用习题课_其它课程_高中教育_教育专区。高三一轮物理复习教学案,内容详细,非常实用。2015 年石榴高级中学高三物理教学案设计人 审核: 课时...
习题课 速度位移关系
速度位移关系 习题课 一、选择题 1.(2014· 宁德高一检测)物体在做匀减速直线运动时(运动方向不变),下面结论正确的 是( ) A.加速度越来越小 B.加速度总与...
立体几何 线面、面面关系习题课2
立体几何 线面、面面关系习题课2_高一数学_数学_高中教育_教育专区。立体几何 基础 实用2.3.6《空间线面、面面关系习题课 2 【学习目标】 知识与技能:掌握...
第35课时 习题课(功能关系)
第35 课时 习题课(功能关系) 自主预习 学习目标 理解功能关系并能解决实际问题。 自主研修 功和能的关系:合力做功是___变化的量度;重力做功是___变化的量度;...
A平行关系判定习题课教案
A平行关系判定习题课教案_数学_高中教育_教育专区。“直线与平面平行判定”习题课一.写出直线与平面平行的判定定理(文字语言表达,数学语言表达并画图) 二.解决下列...
更多相关标签: