Ch−¬ng 1. Quan hÖ
Bμi tËp cho 1.1
1. Cã bao nhiªu quan hÖ kh¸c nhau tõ tËp cã mphÇn tö ®Õn tËp cã nphÇn
tö?
Quan hÖ bï cña quan hÖ R,kýhiÖulμR,lμtËp c¸c cÆp ®−îc s¾p
{(a, b)|(a, b)/∈R}.T×mR−1vμRtrong c¸c tr−êng hîp sau:
2. Rlμquan hÖ <trªn Z.
3. Rlμquan hÖ chia hÕt trªn N+
4. Rlμquan hÖ hμm , nghÜa lμR={(a, f(a))|f(a)lμ¶nh cña aqua ¸nh
x¹ f}.
5. LiÖt kª 16 quan hÖ kh¸c nhau trªn tËp {0,1}
6. Trongsè16quanhÖkh¸cnhautrªntËp{0,1}, nh÷ng quan hÖ nμolμ
a. Ph¶n x¹
b. §èi xøng.
c. Ph¶n xøng.
d. B¾c cÇu.
7. Cã bao nhiªu quan hÖ trªn tËp gåm nphÇn tö lμ
a. Ph¶n x¹
b. §èi xøng.
c. Ph¶n xøng.
8. Cho Rlμquan hÖ cã tÝnh ph¶n x¹ trªn tËp A. Chøng minh r»ng Rncòng
cãtÝnhphnx¹víimäisènguyªnd−¬ng n.
9. Cho Rlμquan hÖ cã tÝnh ®èi xøng trªn tËp A. Chøng minh r»ng Rn
còng cã tÝnh ®èi xøng víi mäi sè nguyªn d−¬ng n.
10. ChØ ra mét vÝ dô vÒ mét quan hÖ b¾c cÇu Rsao cho R2=R
Bμi tËp cho 1.2
1. Cho tËp A={1,2,3,4}. BiÓudiÔnc¸cquanhÖR, S trªn Ab»ng ma
trËn víi thø tù cña c¸c phÇn tö cña A®−îc liÖt kª t¨ng dÇn vμR, S cho
sau ®©y:
a. R={(1,1),(1,2),(2,3),(4,2)}.
1
b. S={(1,1),(1,3),(2,1),(2,3),(2,4),(3,1),3,2),(4,1)}
2. Cho tËp A={a, b, c, d}vμc¸c quan hÖ P, Q trªn tËp A®−îc biÓu diÔn
bëi ma trËn sau (t−¬ng øng víi thø tù ®· ®−îc liÖt kª cña phÇn tö cña
A): a. MP=⎛
⎜
⎝
1010
0101
1100
0011
⎞
⎟
⎠;b.MQ=⎛
⎜
⎝
1001
0110
1010
0011
⎞
⎟
⎠.H·y
liÖt kª c¸c cÆp thuéc mçi quan hÖ P, Q.
3. C¸c quan hÖ ®· cho trong c¸c bμitËp1vμ2 cã nh÷ng tÝnh chÊt g× trong
c¸c tÝnh chÊt ph¶n x¹, ®èi xøng, ph¶n xøng, b¾c cÇu.
4. T×m c¸c ma trËn biÓu diÔn cña c¸c quan hÖ P−1,P,P2víi Plμquan
hÖ t×m ®−îc trong bμitËp2.
5. T×m c¸c ma trËn biÓu diÔn cña c¸c quan hÖ
P∪Q, P ∩Q, P Q, QP, P 2,P3,P4
víi PvμQlμc¸cquanhÖcãmatrËnbiÓudiÔnMP,M
Qcho trong bμi
tËp 2.
6. VÏ c¸c ®å thÞ biÓu diÔn c¸c quan hÖ R, S cho trong bμitËp1vμc¸c ®å
thÞbiÓudiÔnc¸cquanhÖP, Q t×m ®−îc trong bμitËp2.
7.Chøngminhr»ngnÕuMRlμma trËn biÓu diÔn quan hÖ Rth× M[k]
Rlμ
ma trËn biÓu diÔn quan hÖ Rk,víik=1,2,3,....
8. BiÓu diÔn quan hÖ b»ng danh s¸ch liªn kÕt.
9. BiÓu diÔn quan hÖ b»ng m¶ng c¸c b¶n ghi
Bμi tËp cho 1.3.
1. Cho Rlμquan hÖ {(a, b)|a=b}trªn tËp hîp c¸c sè nguyªn Z. T×m bao
®ãng ph¶n x¹ cña R.
2. Cho Rlμquan hÖ {(a, b)|alμ−íc cña b}trªn tËp hîp c¸c sè tù nhiªn
N. T×m bao ®ãng ®èi xøng cña R.
3. Chøng minh r»ng:
Bao ®ãng ph¶n x¹ cña quan hÖ RlμS=R∪I.
Bao ®ãng ®èi xøng cña quan hÖ RlμS=R∪R−1.
4. Chøngminhr»ngnÕuRlμquan hÖ trªn tËp h÷u h¹n A®−îc biÓu diÔn
bëi ma trËn MR, th×:
2
a. Ma trËn biÓu diÔn bao ®ãng ph¶n x¹ cña RlμMR∨In.
b. Ma trËn biÓu diÔn bao ®ãng ®èi xøng cña RlμMR∨Mt
Rtrong ®ã
Mtlμma trËn chuyÓn vÞ cña M.
5. Dïng c¸c thuËt to¸n 1 vμ2 ®Ó t×m bao ®ãng b¾c cÇu cña c¸c quan hÖ sau
®©y:
a. R={(1,0)}trªn tËp A={0,1}
b. R={(a, b),(a, c)}trªn tËp A={a, b, c}.
c. R={(a, a),(a, b),(b, c),(b, d),(c, a),(d, a),(d, b)}trªn tËp A=
{a, b, c, d}.
6. ViÕt mét ch−¬ng tr×nh thùc hiÖn c¸c c«ng viÖc sau ®©y:
a. NhËp sè phÇn tö ncña tËp Avμc¸cphÇntöcñaAlμc¸c ch÷ c¸i
b. NhËp c¸c cÆp ch÷ c¸i thuéc mét quan hÖ Rtrªn A.
c.X¸c®ÞnhmatrËnbiÓudiÔnquanhÖRvμin ra mμnh×nhmatrËn®ã.
d. T×m vμin ra mμnh×nhmatrËnbiÓudiÔnquanhÖbao®ãngb¾ccÇu
cña R.
e. In ra mμn h×nh tÊt c¶ c¸c cÆp phÇn tö cña bao ®ãng b¾c cÇu cña R.
Bμi tËp cho 1.4.
1.Chøngtár»ngmçiquanhÖt−¬ng ®−¬ng ®Òu cã thÓ biÓu diÔn bëi ma
trËn khèi d¹ng
MR=⎛
⎜
⎜
⎝
A11 A12 ··· A1k
A21 A22 ··· A2k
.
.
..
.
.··· ···
Ak1Ak2··· Akk
⎞
⎟
⎟
⎠
trong ®ã
Aij =ma trËn cã mäi phÇn tö b»ng 1 nÕu i=j
ma trËn kh«ng (cã mäi phÇn tö b»ng 0) nÕu i=j
2. CãthÓcãbaonhiªuquanhÖt−¬ng ®−¬ng trªn mét tËp cã nphÇn tö?
3