Bài giảng toán rời rạc

Chia sẻ: Lê Trang | Ngày: | Loại File: PDF | Số trang:88

Thêm vào BST

Báo xấu

200
lượt xem 64
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong cuộc sống chúng ta thường gặp rất nhiều hiện tượng được diễn tả bởi thuật ngữ quan hệ, chẳng hạn quan hệ bạ bè, quan hệ đồng hương, quan hệ thầy trò,...Hoặc cuối năm học ta thường quan tâm điến điểm trung bình chung học tập của các thành viên trong lớp.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng toán rời rạc

Tr−êng §¹i häc Vinh NguyÔn Trung Hßa To¸n rêi r¹c Vinh - 2010 0
Ch−¬ng 1. Quan hÖ 1.1. Quan hÖ hai ng«i vμ c¸c tÝnh chÊt 1.1.1. §Þnh nghÜa vμ c¸c vÝ dô Trong cuéc sèng ta th−êng gÆp rÊt nhiÒu hiÖn t−îng ®−îc diÔn t¶ bëi thuËt ng÷ quan hÖ, ch¼ng h¹n quan hÖ b¹n bÌ, quan hÖ ®ång h−¬ng, quan hÖ thÇy trß,... HoÆc cuèi n¨m häc ta th−êng quan t©m ®Õn ®iÓm trung b×nh chung häc tËp cña c¸c thμnh viªn trong líp, khi ®ã ta cã mèi quan hÖ gi÷a sinh viªn cña líp vμ sè thùc lμ ®iÓm trung b×nh chung häc tËp cña c¸c sinh viªn. Hay cuèi häc kú ta ph¶i xÕp lÞch thi häc kú, khi ®ã ta th−êng xÐt quan hÖ gi÷a líp trong khoa vμ m«n ®−îc líp ®ã häc trong häc kú, gäi t¾t lμ quan hÖ Häc, ch¼ng h¹n 45A Häc x¸c suÊt; 44B Häc to¸n rêi r¹c; 44B Häc kinh tÕ, 44A Häc t©m lý häc, 44A Häc kinh tÕ... Cã nghÜa lμ ta ph¶i ghÐp cÆp (líp x, m«n y) vμ hiÓu lμ líp x häc m«n y. Nh− vËy, tËp tÊt c¶ c¸c cÆp (líp x, m«n y) sao cho líp x häc m«n y ®Æc tr−ng cho quan hÖ Häc, vμ ta cã thÓ coi quan hÖ Häc lμ tËp con cña tÝch ®Ò-c¸c cña hai tËp c¸c líp vμ c¸c m«n häc. H×nh thøc ho¸ c¸c hiÖn t−îng Êy ta cã kh¸i niÖm quan hÖ, lμ mét kh¸i niÖm rÊt quan träng cña to¸n häc vμ ®−îc øng dông trong nhiÒu lÜnh vùc, ®Æc biÖt lμ trong tin häc. Mét quan hÖ hai ng«i tõ tËp A ®Õn tËp B lμ mét tËp con R cña tÝch ®Ò c¸c A × B . NÕu (a, b) ∈ R th× ta nãi r»ng a cã quan hÖ R víi b vμ ký hiÖu aRb thay thÕ cho ký hiÖu (a, b). VÝ dô 1. Quan hÖ Häc kú 4= {(a, b) víi a lμ mét líp nμo ®ã cña kho¸ 44, cßn b lμ mét m«n mμ líp a häc trong häc kú 4 (n¨m häc 2004-2005)}. Râ rμng quan hÖ Häc kú 4 lμ mét tËp con cña quan hÖ Häc ®· nãi ë trªn. VÝ dô 2. Quan hÖ trùc thuéc (hμnh chÝnh) lμ tËp con I cña tÝch ®Ò-c¸c cña tËp H tÊt c¶ c¸c huyÖn cña ViÖt nam vμ tËp T lμ tËp tÊt c¶ c¸c tØnh cña ViÖt nam. Khi ®ã (H−ng nguyªn, NghÖ an), (TÜnh gia, Thanh ho¸), (H−¬ng s¬n, Hμ tÜnh), (Nam ®μn, NghÖ an) lμ nh÷ng phÇn tö cña tËp I vμ ta th−êng nãi H−ng nguyªn trùc thuéc NghÖ an, TÜnh gia trùc thuéc Thanh ho¸, H−¬ng s¬n trùc thuéc Hμ tÜnh, Nam ®μn trùc thuéc NghÖ an. VÝ dô 3. Mét hμm sè bÊt kú trªn miÒn x¸c ®Þnh D lμ mét quan hÖ tõ D ®Õn R, mμ mçi phÇn tö cña quan hÖ nμy lμ mét cÆp (x, f (x)), vμ ®©y lμ mét lo¹i quan hÖ hai ng«i ®Æc biÖt, ë chç mäi x ∈ D ®Òu cã vμ chØ cã duy nhÊt mét f (x) t−¬ng øng. 1
Trong sè c¸c quan hÖ hai ng«i, ta quan t©m ®Æc biÖt ®Õn c¸c quan hÖ hai ng«i trªn mét tËp: Mét quan hÖ hai ng«i R trªn tËp A lμ mét quan hÖ tõ A ®Õn A, nghÜa lμ R lμ tËp con cña b×nh ph−¬ng ®Ò c¸c A × A. VÝ dô 4. XÐt tËp A tÊt c¶ sinh viªn líp 48K, ta cã c¸c quan hÖ hai ng«i sau: a. Quan hÖ ®ång h−¬ng, gåm tÊt c¶ c¸c cÆp hai sinh viªn (a, b) sao cho a cã gia ®×nh cïng huyÖn víi b. b. Quan hÖ c«ng t¸c, gåm tÊt c¶ c¸c cÆp hai sinh viªn (a, b) sao cho a cã c«ng viÖc cÇn trao ®æi víi b. c. Quan hÖ b¹n th©n, gåm tÊt c¶ c¸c cÆp hai sinh viªn (a, b) sao cho a ch¬i th©n víi b. d. Quan hÖ lín tuæi h¬n, gåm tÊt c¶ c¸c cÆp hai sinh viªn (a, b) sao cho a sinh tr−íc b. VÝ dô 5. XÐt tËp c¸c sè nguyªn Z : a. Quan hÖ ®ång d− theo m« ®un 5 trªn tËp c¸c sè nguyªn Z ®−îc ®Þnh nghÜa nh− sau: a ®−îc gäi lμ ®ång d− víi b theo m« ®un 5 khi vμ chØ khi a vμ b cã cïng sè d− khi chia cho 5. b. Quan hÖ < trªn tËp Z . 1.1.2. C¸c phÐp to¸n trªn tËp c¸c quan hÖ Gi¶ sö cã c¸c quan hÖ hai ng«i tõ tËp X ®Õn tËp Y , khi ®ã chóng ®Òu lμ c¸c tËp con cña tÝch ®Ò-c¸c X × Y , nªn cã thÓ xÐt c¸c phÐp to¸n tËp hîp lμ phÐp hîp, phÐp giao, phÐp trõ, phÐp lÊy hiÖu ®èi xøng. Chóng ®−îc xem lμ c¸c phÐp to¸n trªn c¸c quan hÖ vμ kÕt qu¶ cña chóng ®Òu lμ c¸c quan hÖ hai ng«i tõ X ®Õn Y . Ta sÏ x©y dùng vμi phÐp to¸n míi. PhÐp nghÞch ®¶o: Gi¶ sö R lμ mét quan hÖ hai ng«i tõ tËp X ®Õn tËp Y . Quan hÖ ng−îc (nghÞch ®¶o) cña quan hÖ R lμ quan hÖ S tõ Y ®Õn X sao cho S = {(y, x)|(x, y ) ∈ R}. Quan hÖ ng−îc cña R ®−îc ký hiÖu bëi R−1 . VÝ dô 1. NÕu X = {1, 2, 3, 4}, Y = {a, b, c}, R = {(1, b), (2, a), (4, c)} th× R−1 = {(b, 1), (a, 2), (c, 4)}. PhÐp hîp thμnh: Gi¶ sö R lμ mét quan hÖ hai ng«i tõ tËp X ®Õn tËp Y , S lμ mét quan hÖ hai ng«i tõ tËp Y ®Õn tËp Z . Hîp thμnh cña c¸c quan hÖ 2
R vμ S lμ quan hÖ T tõ X ®Õn Z víi T = {(x, z )|∃y ∈ Y sao cho (x, y ) ∈ R vμ (y, z ) ∈ S }. Quan hÖ hîp thμnh T ®−îc ký hiÖu bëi R ◦ S hoÆc RS . Chó ý r»ng RS cã thÓ lμ tËp rçng mÆc dÇu R vμ S ®Òu kh¸c rçng vμ phÐp hîp thμnh cã tÝnh chÊt kÕt hîp, nghÜa lμ (R ◦ S ) ◦ V = R ◦ (S ◦ V ). VÝ dô 2. Gi¶ sö X = {1, 2, 3, 4}, Y = {a, b, c}, Z = {α, β , γ }, R = {(1, b), (2, a), (3, b), (4, c)}, S = {(a, α), (b, γ ), (c, β )}, khi ®ã RS = {(1, γ ), (2, α), (3, γ ), (4, β )}. PhÐp luü thõa: Gi¶ sö R lμ mét quan hÖ hai ng«i trªn tËp X . Luü thõa bËc n cña quan hÖ R, ký hiÖu lμ Rn , víi n = 1, 2, ... lμ quan hÖ ®−îc x¸c ®Þnh bëi hÖ thøc truy håi Rn = Rn−1 R víi R1 = R. VÝ dô 3. Gi¶ sö X = {1, 2, 3, 4}, R = {(1, 2), (2, 1), (3, 2), (4, 3)}. Ta cã R2 = RR = {(1, 1), (2, 1), (3, 1), (4, 2)}, R3 = R4 = {(1, 1), (2, 1), (3, 1), (4, 1)}, vμ do ®ã Rn = R3 víi mäi n ≥ 3. 1.1.3. C¸c tÝnh chÊt cã thÓ cã cña quan hÖ hai ng«i trªn mét tËp a. Quan hÖ hai ng«i R trªn mét tËp X ®−îc gäi lμ cã tÝnh chÊt ph¶n x¹ nÕu víi mäi a ∈ X ®Òu cã aRa. VÝ dô 1. Quan hÖ ®ång h−¬ng ë vÝ dô 4, quan hÖ ®ång d− ë vÝ dô 5 (môc 1.1.1) lμ c¸c quan hÖ cã tÝnh ph¶n x¹. b. Quan hÖ hai ng«i R trªn mét tËp X ®−îc gäi lμ cã tÝnh chÊt ®èi xøng nÕu víi mäi a, b ∈ X , aRb khi vμ chØ khi bRa. VÝ dô 2. C¸c quan hÖ ®ång h−¬ng, b¹n th©n ë vÝ dô 4; quan hÖ ®ång d− ë vÝ dô 5 (môc 1.1.1) lμ c¸c quan hÖ cã tÝnh ®èi xøng. c. Quan hÖ hai ng«i R trªn mét tËp X ®−îc gäi lμ cã tÝnh chÊt ph¶n xøng nÕu víi mäi a, b ∈ X sao cho aRb vμ bRa th× a = b. VÝ dô 3. Quan hÖ < trªn tËp Z (vÝ dô 5 môc 2.1.1) cã tÝnh ph¶n xøng. d. Quan hÖ hai ng«i R trªn mét tËp X ®−îc gäi lμ cã tÝnh chÊt b¾c cÇu nÕu víi mäi a, b, c ∈ X sao cho aRb vμ bRc th× aRc. VÝ dô 4. C¸c quan hÖ ®ång h−¬ng, lín tuæi h¬n ë vÝ dô 4; c¸c quan hÖ ®ång d−, < ë vÝ dô 5 (môc 1.1.1) cã tÝnh chÊt b¾c cÇu. Sau ®©y ta cã ®Þnh lý vÒ mèi liªn hÖ gi÷a quan hÖ b¾c cÇu R vμ c¸c luü thõa cña R. 3
§Þnh lý 1. Quan hÖ R trªn tËp A cã tÝnh b¾c cÇu khi vμ chØ khi Rn ⊂ R víi mäi n = 1, 2, 3, .... Chøng minh. CÇn: Râ rμng R1 ⊂ R, tøc lμ víi n = 1 ®iÒu kiÖn cÇn ®· ®óng. Gi¶ sö Rn ⊂ R ta sÏ chøng minh Rn+1 ⊂ R. ThËt vËy, theo ®Þnh nghÜa cña luü thõa bËc n cña quan hÖ ta cã Rn+1 = Rn R nghÜa lμ víi mäi (x, z ), (x, z ) ∈ Rn+1 khi vμ chØ khi tån t¹i y ∈ A sao cho (x, y ) ∈ Rn vμ (y, z ) ∈ R. Theo gi¶ thiÕ quy n¹p, (x, y ) ∈ Rn kÐo theo (x, y ) ∈ R vμ do R cã tÝnh chÊt b¾c cÇu nªn tõ (x, y ) ∈ R vμ (y, z ) ∈ R suy ra (x, z ) ∈ R. VËy Rn+1 ⊂ R. §ñ: Gi¶ sö (x, y ) ∈ R vμ (y, z ) ∈ R, khi ®ã (x, z ) ∈ R2 . Theo gi¶ thiÕt Rn ⊂ R víi mäi n = 1, 2, ... nªn ta cã ngay R2 ⊂ R, suy ra (x, z ) ∈ R, tøc lμ R cã tÝnh b¾c cÇu. Bμi tËp: 1. Cã bao nhiªu quan hÖ kh¸c nhau tõ tËp cã m phÇn tö ®Õn tËp cã n phÇn tö? Quan hÖ bï cña quan hÖ R, ký hiÖu lμ R, lμ tËp c¸c cÆp ®−îc s¾p {(a, b)|(a, b) ∈ R}. T×m R−1 vμ R trong c¸c tr−êng hîp sau: / 2. R lμ quan hÖ < trªn Z . 3. R lμ quan hÖ chia hÕt trªn N + 4. R lμ quan hÖ hμm , nghÜa lμ R = {(a, f (a)) — f (a) lμ ¶nh cña a qua ¸nh x¹ f . 5. LiÖt kª 16 quan hÖ kh¸c nhau trªn tËp {0, 1} 6. Trong sè 16 quan hÖ kh¸c nhau trªn tËp {0, 1}, nh÷ng quan hÖ nμo lμ 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 n phÇn tö lμ a. Ph¶n x¹ b. §èi xøng. c. Ph¶n xøng. 8. Cho R lμ quan hÖ cã tÝnh ph¶n x¹ trªn tËp A. Chøng minh r»ng Rn còng cã tÝnh ph¶n x¹ víi mäi sè nguyªn d−¬ng n. 4
9. Cho R lμ 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 R sao cho R2 = R 1.2. BiÓu diÔn quan hÖ 1.2.1. Ma trËn logic vμ c¸c phÐp to¸n trªn c¸c ma trËn logic Gi¶ sö a, b lμ c¸c biÕn (biÕn boolean) chØ nhËn mét trong hai gi¸ trÞ 0 hoÆc 1 (gi¸ trÞ logic). Ta gäi tuyÓn cña a vμ b lμ gi¸ trÞ 1 nÕu a = 1 hoÆc b = 1 c = a ∨ b := 0 nÕu a = b = 0, ký hiÖu tuyÓn cña a vμ b bëi a ∨ b. Ta gäi héi cña a vμ b lμ gi¸ trÞ 1 nÕu a = b = 1 c = a ∧ b := 0 nÕu a = 0 hoÆc b = 0, ký hiÖu héi cña a vμ b bëi a ∧ b. Ma trËn logic cì m × n lμ mét ma trËn cã m dßng vμ n cét, trong ®ã c¸c phÇn tö cña nã chØ nhËn mét trong hai gi¸ trÞ 0 hoÆc 1. Gi¶ sö cho hai ma trËn A = [ai,j ] vμ B = [bi,j ] còng cì. a. TuyÓn (tæng boolean) cña hai ma trËn A vμ B , ký hiÖu A ∨ B , lμ ma trËn C = [ci,j ] trong ®ã ci,j = ai,j ∨ bi,j . b. Héi cña hai ma trËn A vμ B , ký hiÖu A ∧ B , lμ ma trËn C = [ci,j ] trong ®ã ci,j = ai,j ∧ bi,j . c. TÝch boolean cña ma trËn A cì m × n vμ ma trËn B cì n × p lμ ma trËn C = A ◦ B := [ci,j ] cì m × p trong ®ã ci,j = (ai,1 ∧ b1,j ) ∨ · · · ∨ (ai,k ∧ bk,j ) ∨ · · · ∨ (ai,n ∧ bn,j ) (c¸c dÊu ngoÆc cã thÓ ®−îc bá ®i). Ta ký hiÖu tÝch boolean cña hai ma trËn A vμ B lμ A ◦ B DÔ thÊy r»ng ma trËn vu«ng In = [δi,j ] cÊp n trong ®ã 1 nÕu i = j δi,j = 0 nÕu i = j 5
lμ ma trËn ®¬n vÞ ®èi víi phÐp nh©n boolean, nghÜa lμ víi mäi ma trËn A cì m × n (hoÆc mäi ma trËn B cì n × p) ta ®Òu cã A ◦ In = A (hoÆc In ◦ B = B ). §ång thêi tÝch boolean cã tÝnh chÊt kÕt hîp, nghÜa lμ A ◦ (B ◦ C ) = (A ◦ B ) ◦ C nÕu mét trong hai vÕ cña ®¼ng thøc nμy tån t¹i. ThuËt to¸n tÝnh tÝch boole cña ma trËn A cì m × n vμ ma trËn B cì n × p, l−u tr÷ kÕt qu¶ vμo ma trËn C . Víi i := 1 ®Õn m Víi j := 1 ®Õn p ci,j := 0 víi k := 1 ®Õn n ci,j := ci,j ∨ (ai,k ∧ bk,j ). V× tÝch boolean cña c¸c ma trËn logic cã tÝnh chÊt kÕt hîp nªn ta cã thÓ ®Þnh nghÜa luü thõa boolean nh− sau: d. Luü thõa boole bËc r cña mét ma trËn vu«ng logic A cÊp n, ký hiÖu bëi A[r] ®−îc ®Þnh nghÜa b»ng truy håi nh− sau: A[r] = A ◦ A[r−1] , víi r = 1, 2, ... vμ A[0] = In . hoÆc ®−îc x¸c ®Þnh bëi A[r] = A ◦ A ◦ · · · ◦ A r lÇn 1.2.2. BiÓu diÔn quan hÖ b»ng ma trËn a. X©y dùng biÓu diÔn Cho A lμ tËp hîp h÷u h¹n cã m phÇn tö ®· ®−îc ®¸nh sè thø tù A = {a1 , a2 , ...am } vμ B lμ tËp hîp h÷u h¹n cã n phÇn tö ®· ®−îc ®¸nh sè thø tù B = {b1 , b2 , ...bn } . Khi ®ã tÝch ®Ò c¸c A × B cã m × n phÇn tö vμ mét c¸ch tù nhiªn ta cã thÓ biÓu diÔn chóng nh− lμ mét b¶ng gåm m dßng vμ n cét, trong ®ã vÞ trÝ ë dßng i cét j lμ cÆp (ai , bj ). V× R lμ mét tËp con cña tÝch ®Ò c¸c A × B , nªn biÓu diÔn cña R sÏ ®−îc t¹o nªn tõ b¶ng ë trªn b»ng c¸ch cÆp nμo thuéc R sÏ ®−îc thay bëi 1, cÆp nμo kh«ng thuéc R sÏ ®−îc thay bëi 0. Tõ ®ã ta cã ®Þnh nghÜa biÓu diÔn sau: Gi¶ sö R lμ mét quan hÖ tõ tËp A ®Õn tËp B vμ c¸c phÇn tö cña A, B ®· ®−îc s¾p xÕp theo mét thø tù cè ®Þnh nμo 6
®ã A = {a1 , a2 , ...am }, B = {b1 , b2 , ...bn }. Ma trËn logic biÓu diÔn quan hÖ R lμ ma trËn MR = [ri,j ], trong ®ã nÕu (ai , bj ) ∈ R 1 ri,j = nÕu (ai , bj ) ∈ R 0 / §Ó ý r»ng thø tù cña c¸c phÇn tö cña A vμ B hoμn toμn tuú ý, tuy nhiªn ph¶i ®−îc cho tr−íc cè ®Þnh. Nãi c¸ch kh¸c øng víi mét thø tù cña c¸c phÇn tö trong A hoÆc B ta sÏ cã mét biÓu diÔn ma trËn cña quan hÖ R. §Æc biÖt khi A = B ta quy ®Þnh thø tù cña c¸c phÇn tö cña A vμ cña B lμ nh− nhau. b. C¸c vÝ dô. c. Ma trËn biÓu diÔn c¸c quan hÖ ph¶n x¹, ®èi xøng, ph¶n xøng BiÓu diÔn quan hÖ bëi ma trËn logic cho ta mét c¸ch nh×n trùc quan h¬n c¸c quan hÖ. Khi A = B , víi biÓu diÔn nμy ta dÔ dμng kiÓm tra c¸c tÝnh chÊt cña quan hÖ R. Quan hÖ R trªn tËp A cã tÝnh chÊt ph¶n x¹ khi vμ chØ khi MR lμ ma trËn cã mäi phÇn tö trªn ®−êng chÐo chÝnh b»ng 1. Quan hÖ R trªn tËp A cã tÝnh chÊt ®èi xøng khi vμ chØ khi MR lμ ma trËn ®èi xøng qua ®−êng chÐo chÝnh. Quan hÖ R trªn tËp A cã tÝnh chÊt ph¶n xøng khi vμ chØ khi MR lμ ma trËn cã ri,j = 0 hoÆc rj,i = 0 khi i = j . d. Ma trËn biÓu diÔn hîp, giao cña hai quan hÖ. Tõ ®Þnh nghÜa ma trËn biÓu diÔn quan hÖ vμ c¸c ®Þnh nghÜa hîp vμ giao cña hai quan hÖ (nh− lμ hîp vμ giao cña hai tËp hîp), tuyÓn, héi cña c¸c ma trËn logic ta dÔ dμng suy ra r»ng ma trËn biÓu diÔn hîp cña hai quan hÖ lμ tuyÓn cña hai ma trËn logic biÓu diÔn c¸c quan hÖ ®· cho vμ ma trËn biÓu diÔn giao cña hai quan hÖ lμ héi cña hai ma trËn logic biÓu diÔn c¸c quan hÖ ®· cho. e. Ma trËn biÓu diÔn hîp thμnh cña hai quan hÖ. §Þnh lý. Gi¶ sö A, B, C lμ c¸c tËp h÷u h¹n cã sè c¸c phÇn tö t−¬ng øng lμ m, n, p. Gi¶ sö R, S lμ c¸c quan hÖ hai ng«i tõ A ®Õn B vμ tõ B ®Õn C t−¬ng øng. Gäi MR = [ri,k ], MS = [sk,j ], MRS = [ti,j ] lμ c¸c ma trËn biÓu diÔn R, S, RS t−¬ng øng. Khi ®ã ta cã MRS = MR ◦ MS 7
Chøng minh: XÐt ti,j lμ phÇn tö bÊt kú (ë dßng i cét j ) cña MRS . Ta cã ti,j = 1 khi vμ chØ khi ai RScj , ®iÒu ®ã cã nghÜa lμ tån t¹i bk nμo ®ã thuéc B ®Ó ai Rbk vμ bk Scj , nghÜa lμ tån t¹i k ®Ó ri,k = 1 vμ sk,j = 1, nghÜa lμ (ri,1 ∨ s1,j ) ∧ . . . ∧ (ri,k ∨ sk,j ) ∧ . . . ∧ (ri,n sn,j ) = 1, nghÜa lμ phÇn tö ë dßng i cét j cña ma trËn tÝch MR ◦ MS b»ng 1. VËy MRS = MR ◦ MS . − 1.2.3. BiÓu diÔn quan hÖ b»ng ®å thÞ cã h−íng. a. §Þnh nghÜa ®å thÞ cã h−íng §å thÞ cã h−íng lμ mét bé ®«i G = (V, E ) trong ®ã V lμ mét tËp hîp, gäi lμ tËp c¸c ®Ønh; E ⊂ V 2 , lμ tËp c¸c cÆp s¾p thø tù c¸c phÇn tö cña V , ®−îc gäi lμ tËp c¸c c¹nh. Víi mçi c¹nh (a, b) ∈ E , ®Ønh a ®−îc gäi lμ ®Ønh ®Çu, b gäi lμ ®Ønh cuèi cña c¹nh. NÕu a trïng b, c¹nh (a, a) ®−îc gäi lμ mét khuyªn. §å thÞ cã h−íng th−êng ®−îc biÓu diÔn (minh ho¹) mét c¸ch trùc quan nh− h×nh vÏ d−íi ®©y: VÝ dô. b. §å thÞ cã h−íng biÓu diÔn quan hÖ Tõ ®Þnh nghÜa ®å thÞ cã h−íng ë trªn, nÕu R lμ mét quan hÖ hai ng«i trªn tËp hîp A, ta cã thÓ biÓu diÔn R nh− lμ mét ®å thÞ G = (A, R) (víi tËp A ®ãng vai trß cña tËp V ; TËp R ®ãng vai trß cña tËp E ). Do ®ã cã thÓ ®ång nhÊt mét quan hÖ R trªn tËp A víi mét ®å thÞ cã h−íng G vμ c¸ch tiÕp cËn nμy cho ta mét c¸ch nh×n trùc quan h¬n. 8
VÝ dô. Cho tËp A = {1, 2, 3, 4}, R lμ quan hÖ ”
VÝ dô: KiÓm tra tÝnh b¾c cÇu cña quan hÖ sau ®©y: Bμi tËp. 1. Cho tËp A = {1, 2, 3, 4}. BiÓu diÔn c¸c quan hÖ R, S trªn A b»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)}. 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 ⎛ ⎞ ⎛ ⎞ 1010 1001 ⎜0 1 0 1⎟ ⎜0 1 1 0⎟ A): a. MP = ⎝ b. MQ = ⎝ ⎠; ⎠. H·y 1100 1010 0011 0011 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μi tËp 1 vμ 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 , P 2 víi P lμ quan hÖ t×m ®−îc trong bμi tËp 2. 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 , P 3 , P 4 víi P vμ Q lμ c¸c quan hÖ cã ma trËn biÓu diÔn MP , MQ cho trong bμi tËp 2. 6. VÏ c¸c ®å thÞ biÓu diÔn c¸c quan hÖ R, S cho trong bμi tËp 1 vμ c¸c ®å thÞ biÓu diÔn c¸c quan hÖ P, Q t×m ®−îc trong bμi tËp 2. [k] 7. Chøng minh r»ng nÕu MR lμ ma trËn biÓu diÔn quan hÖ R th× MR lμ ma trËn biÓu diÔn quan hÖ Rk , víi k = 1, 2, 3, .... 1.3. C¸c bao ®ãng cña quan hÖ. 1.3.1. §Þnh nghÜa bao ®ãng. Mét quan hÖ R trªn mét tËp A cã thÓ cã hoÆc kh«ng cã mét tÝnh chÊt P nμo ®ã (ch¼ng h¹n tÝnh chÊt ®èi xøng). NÕu cã mét quan hÖ S trªn A cã tÝnh 10
chÊt P , chøa R sao cho mäi quan hÖ cã tÝnh chÊt P chøa R ®Òu chøa S th× S sÏ ®−îc gäi lμ bao ®ãng cña R ®èi víi P . Ch¼ng h¹n nÕu P lμ tÝnh chÊt ph¶n x¹, (®èi xøng, ph¶n xøng, b¾c cÇu) th× c¸c bao ®ãng cña R ®èi víi P sÏ ®−îc gäi lμ bao ®ãng ph¶n x¹, (bao ®ãng ®èi xøng, bao ®ãng ph¶n xøng, bao ®ãng b¾c cÇu). Cã thÓ nhËn thÊy r»ng bao ®ãng S cña mét quan hÖ R ®èi víi tÝnh chÊt P lμ giao cña mäi quan hÖ chøa R vμ cã tÝnh chÊt P . a. X¸c ®Þnh Bao ®ãng ph¶n x¹ Bao ®ãng ph¶n x¹ cña mét quan hÖ hai ng«i R trªn tËp A lμ hîp R ∪ ∆ cña R vμ quan hÖ b»ng nhau ∆ = {(a, a)|a ∈ A} trªn A (H·y chøng minh?). b. X¸c ®Þnh Bao ®ãng ®èi xøng. Bao ®ãng ®èi xøng cña mét quan hÖ hai ng«i R trªn tËp A lμ hîp R ∪ R−1 cña R vμ quan hÖ ng−îc R−1 = {(b, a)|(a, b) ∈ R} trªn A (H·y chøng minh?). §Ó x¸c ®Þnh bao ®ãng b¾c cÇu cña mét quan hÖ R ta cÇn ®−a ra mét sè kh¸i niÖm vμ kÕt qu¶ bæ trî. 1.3.2. §−êng ®i trong ®å thÞ cã h−íng a. §Þnh nghÜa. §−êng ®i tõ a ®Õn b, ®é dμi n trong ®å thÞ cã h−íng G lμ mét d·y cã thø tù gåm n c¹nh (x0 , x1 ), (x1 , x2 ), . . . , (xn−1 , xn ) trong G , trong ®ã x0 = a , xn = b vμ ®Ønh cuèi cña c¹nh thø i lμ ®Ønh ®Çu cña c¹nh thø i + 1, (i = 1, 2, . . . n − 1). §Ó ®¬n gi¶n h¬n ta cã thÓ sö dông ký hiÖu x0 , x1 , . . . , xn−1 , xn . §Ønh x0 ®−îc gäi lμ ®Ønh khëi ®Çu vμ xn ®−îc gäi lμ ®Ønh kÕt thóc cña ®−êng ®i. §−êng ®i cã ®Ønh khëi ®Çu vμ ®Ønh kÕt thóc trïng nhau th× ®−îc gäi lμ mét chu tr×nh. §Ó tr¸nh nhÇm lÉn ta quy −íc kh«ng cã ®−êng ®i ®é dμi 0, nghÜa lμ ®−êng ®i (a, a) lμ mét khuyªn vμ cã ®é dμi 1. Chó ý r»ng mét ®−êng ®i th× t−¬ng øng víi mét d·y c¸c ®Ønh, tuy nhiªn, mét d·y c¸c ®Ønh ch−a ch¾c ®· x¸c ®Þnh mét ®−êng ®i. 11
b. Vi dô. Trong c¸c d·y ®Ønh cho d−íi ®©y, d·y ®Ønh nμo lμ mét ®−êng ®i trong ®å thÞ G cho trªn h×nh vÏ? (a, b, d, c, b, a, e); (a, c, d, e, b, a, d); (a, d, g, b), c. §−êng ®i trong quan hÖ R. §Þnh lý vÒ ®−êng ®i ®é dμi n vμ quan hÖ Rn . Bëi v× mét ®å thÞ cã h−íng G cã thÓ t−¬ng øng 1-1 víi mét quan hÖ hai ng«i R trªn tËp c¸c ®Ønh cña nã, do ®ã tõ ®Þnh nghÜa ®−êng ®i ë trªn, ta cã thÓ ®Þnh nghÜa ®−êng ®i tõ a ®Õn b trong quan hÖ R lμ mét d·y c¸c phÇn tö (x0 , x1 ), (x1 , x2 ), . . . , (xn−1 , xn ) cña quan hÖ R, trong ®ã x0 = a , xn = b §Þnh lý 1. Gi¶ sö R lμ mét quan hÖ hai ng«i trªn tËp A. Cã mét ®−êng ®i chiÒu dμi n tõ a ®Õn b trong quan hÖ R khi vμ chØ khi (a, b) ∈ Rn . Chøng minh. (b»ng quy n¹p). Víi n = 1, ta cã ®−êng ®i chiÒu dμi 1 tõ a ®Õn b trong R nghÜa lμ (a, b) ∈ R1 , tøc lμ (a, b) ∈ R. Gi¶ sö ®Þnh lý ®óng víi n − 1, nghÜa lμ cã ®−êng ®i ®é dμi n − 1 tõ a ®Õn b trong R khi vμ chØ khi (a, b) ∈ Rn−1 . Víi n, ta cã ®−êng ®i ®é dμi n tõ a ®Õn b trong R khi vμ chØ khi tån t¹i mét d·y n phÇn tö thuéc R: (a, x1 ), (x1 , x2 ), . . . , (xn−2 , xn−1 ), (xn−1 , b). Víi n − 1 phÇn tö ®Çu ta x¸c ®Þnh mét ®−êng ®i trong R cã ®é dμi n − 1, do ®ã theo gi¶ thiÕt quy n¹p ta cã (a, xn−1 ) ∈ Rn−1 . KÕt hîp biÓu thøc liªn thuéc nμy víi phÇn tö thø n cña ®−êng ®i, ta cã (a, b) ∈ R ◦ Rn−1 , nghÜa lμ (a, b) ∈ Rn . − 1.3.3. X¸c ®Þnh bao ®ãng b¾c cÇu a. §Þnh nghÜa quan hÖ liªn th«ng. Cho R lμ mét quan hÖ trªn tËp A. Quan hÖ liªn th«ng R∗ t−¬ng øng víi R lμ quan hÖ bao gåm c¸c cÆp (a, b) 12
sao cho cã mét ®−êng ®i trong R tõ a ®Õn b. R∗ = {(a, b)|∃a = x0 , x1 , . . . , xn = b sao cho (xi−1 , xi ) ∈ R, ∀i = 1, . . . n}. Tõ ®Þnh lý ë cuèi môc tr−íc ta nh©n thÊy ngay r»ng R∗ lμ hîp cña tÊt c¶ c¸c tËp Rn , n = 1, 2, . . ., tøc lμ ∞ ∗ Rn R= n=1 b. C¸c vÝ dô §Þnh lý 2. Bao ®ãng b¾c cÇu cña quan hÖ R chÝnh lμ quan hÖ liªn th«ng R∗ t−¬ng øng víi R. §Ó chøng minh c¸c ®Þnh lý tiÕp theo ta sö dông kh¸i niÖm ®Ønh trong cña mét ®−êng ®i: Gi¶ sö a = x0 , x1 , . . . , xm−1 , xm = b lμ mét ®−êng ®i trong R tõ a ®Õn b. Khi ®ã c¸c ®Ønh xi víi 0 < i < n ®−îc gäi lμ c¸c ®Ønh trong cña ®−êng ®i ®· cho. Chó ý r»ng b¶n th©n a hoÆc b còng cã thÓ lμ c¸c ®Ønh trong. §Þnh lý 3. (vÒ BiÓu diÔn cña bao ®ãng b¾c cÇu R∗ )Gi¶ sö A lμ mét tËp cã n phÇn tö vμ R lμ quan hÖ hai ng«i trªn A ®−îc biÓu diÔn bëi ma trËn logic MR . Khi ®ã bao ®ãng b¾c cÇu R∗ cña R ®−îc biÓu diÔn bëi ma trËn logic [2] [n] MR∗ = MR ∨ MR ∨ . . . ∨ MR . Chøng minh. Tr−íc tiªn ta chøng minh nhËn xÐt sau: NÕu cã mét ®−êng ®i trong R tõ a ®Õn b th× cã mét ®−êng ®i trong R tõ a ®Õn b víi ®é dμi kh«ng qu¸ n, h¬n n÷a nÕu a = b th× cã mét ®−êng ®i trong R tõ a ®Õn b víi ®é dμi bÐ h¬n n. ThËt vËy, gi¶ sö cã mét ®−êng ®i ®é dμi m trong R tõ a ®Õn b lμ a = x0 , x1 , . . . , xm−1 , xm = b, nghÜa lμ ta cã m + 1 ®Ønh trªn ®−êng ®i nμy. Tuy nhiªn tËp A chØ cã n ®Ønh vμ gi¶ sö m > n, khi ®ã theo nguyªn lý Dirichle sÏ cã Ýt nhÊt hai ®Ønh xi , xj , (i < j ) thuéc ®−êng ®i cïng lμ mét ®Ønh cña x ∈ A, tøc lμ ®−êng ®i ®ang xÐt chøa mét chu tr×nh x, xi+1 , . . . , xj −1 , x (cã ®é dμi l > 0). NÕu xi hoÆc xj lμ ®Ønh trong, lo¹i bá chu tr×nh nμy ta vÉn cã mét ®−êng ®i tõ a ®Õn b vμ cã ®é dμi m1 = m − l < m. Cø lo¹i bá c¸c chu tr×nh 13
nh− trªn sau k b−íc nμo ®ã ta sÏ cã mét ®−êng ®i tõ a ®Õn b cã ®é dμi mk < mk−1 < . . . < m1 < m víi c¸c ®Ønh trong ®«i mét kh¸c nhau vμ kh¸c víi c¸c ®Ønh a, b (trõ tr−êng hîp ®Æc biÖt a = x0 ≡ xm = b). Do ®ã, - nÕu a = x0 ≡ xmk = b, ®−êng ®i cã tèi ®a n ®Ønh ph©n biÖt vμ cã ®Ønh ®Çu trïng ®Ønh cuèi, do ®ã ®é dμi mk < n. - nÕua = b, ®−êng ®i cã tèi ®a n-1 ®Ønh ph©n biÖt, nªn cã ®é dμi mk < n. Tõ nhËn xÐt trªn, ta nhËn thÊy mçi phÇn tö (a, b) ∈ R∗ t−¬ng øng víi mét ®−êng ®i cã ®é dμi kh«ng qu¸ n trong R, ®iÒu ®ã còng cã nghÜa lμ R∗ = R ∪ R2 ∪ . . . ∪ Rn do ®ã theo tÝnh chÊt liªn hÖ gi÷a c¸c phÐp to¸n ma trËn vμ phÐp to¸n quan hÖ ta cã [2] [n] MR∗ = MR ∨ MR ∨ . . . ∨ MR . e. C¸c thuËt to¸n x¸c ®Þnh bao ®ãng bÆc cÇu cña quan hÖ R ThuËt to¸n 1. Tõ ®Þnh lý trªn, ta cã thuËt to¸n sau ®Ó x¸c ®Þnh ma trËn MR∗ biÓu diÔn bao ®ãng b¾c cÇu cña quan hÖ R cã ma trËn MR . A := MR MR∗ := A; Víi i := 2 ®Õn n A := A MR MR∗ := MR∗ ∨ A ThuËt to¸n 2. (Warshall, 1960), (Roy, 1959). ThuËt to¸n Warshall sÏ x©y dùng d·y c¸c ma trËn logic W0 , W1 , . . . , Wn (k ) (k) trong ®ã W0 = MR , Wk = [wij ] sao cho wij = 1 khi vμ chØ khi cã mét ®−êng ®i tõ ®Ønh ai ®Õn ®Ønh aj mμ mäi ®Ønh trong cña nã chØ thuéc k ®Ønh ®Çu tiªn a1 , . . . , ak trong danh s¸ch c¸c ®Ønh (®· ®−îc s¾p) cña tËp nÒn A. Râ rμng Wn theo ®Þnh nghÜa trªn chÝnh lμ ma trËn MR∗ , biÒu diÔn cña R∗ . Ta sÏ x¸c ®Þnh Wk qua Wk−1 nh− sau: (k ) Gi¶ sö Wk = [wij ] lμ ma trËn logic trong d·y trªn, khi ®ã (k ) wij = 1 khi vμ chØ khi cã mét ®−êng ®i tõ ®Ønh ai ®Õn ®Ønh aj mμ mäi ®Ønh trong cña nã chØ thuéc tËp {a1 , . . . , ak } gåm k ®Ønh ®Çu tiªn 14
trong danh s¸ch c¸c ®Ønh (®· ®−îc s¾p) cña tËp nÒn A. Cã ba kh¶ n¨ng x¶y ra: - HoÆc tËp c¸c ®Ønh trong cña ®−êng ®i nμy kh«ng chøa ak , ®−êng ®i nμy (k−1) chÝnh lμ ®−êng ®i t−¬ng øng víi wij = 1. - HoÆc tËp c¸c ®Ønh trong cña ®−êng ®i nμy ®i qua ak chØ mét lÇn. Khi ®ã ®−êng ®i nμy sÏ ®−îc xÐt nh− lμ sù nèi tiÕp cña hai ®−êng ®i, tõ ai ®Õn ak vμ tõ ak ®Õn aj , mμ c¸c ®Ønh trong cña mçi ®−êng nμy chØ thuéc tËp c¸c (k−1) (k−1) ®Ønh {a1 , . . . , ak−1 }. §iÒu ®ã ®ång nghÜa víi wik = 1 vμ wkj = 1. - HoÆc tËp c¸c ®Ønh trong cña ®−êng ®i nμy ®i qua ak qu¸ 1 lÇn, khi ®ã ta sÏ x¸c ®Þnh ®−îc ®−êng ®i míi chØ ®i qua ak ®óng 1 lÇn b»ng c¸ch bá ®i (c¸c) chu tr×nh xuÊt ph¸t vμ kÕt thóc t¹i ak (tøc lμ ta quy vÒ kh¶ n¨ng thø hai ë trªn. (k−1) (k−1) (k−1) (k ) VËy wij = 1 khi vμ chØ khi wij = 1 hoÆc wik = 1 vμ wkj = 1, tøc lμ: (k−1) (k−1) (k−1) (k ) ∨ (wik ∧ wkj wij = wij ). Tõ ®ã ta cã thuËt to¸n Warshall sau ®©y: W := MR Víi k := 1 ®Õn n Víi i := 1 ®Õn n Víi j := 1 ®Õn n wij := wij ∨ wik ∧ wkj . Bμi tËp. 1. Cho R lμ 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 R lμ quan hÖ {(a, b)|a lμ −í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Ö R lμ S = R ∪ I . Bao ®ãng ®èi xøng cña quan hÖ R lμ S = R ∪ R−1 . 4. Chøng minh r»ng nÕu R lμ quan hÖ trªn tËp h÷u h¹n A ®−îc biÓu diÔn bëi ma trËn MR , th×: a. Ma trËn biÓu diÔn bao ®ãng ph¶n x¹ cña R lμ MR ∨ In . 15
t b. Ma trËn biÓu diÔn bao ®ãng ®èi xøng cña R lμ MR ∨ MR trong ®ã M t lμ 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. Gi¶ sö A lμ mét tËp gåm n ch÷ c¸i nμo ®ã , (n < 20). R lμ mét quan hÖ hai ng«i trªn A. 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ö n cña tËp A vμ c¸c phÇn tö cña A (lμ c¸c ch÷ c¸i). b. NhËp c¸c cÆp thuéc quan hÖ R trªn A. c. X¸c ®Þnh ma trËn biÓu diÔn quan hÖ R vμ in ra mμn h×nh ma trËn ®ã. d. T×m vμ in ra mμn h×nh ma trËn biÓu diÔn quan hÖ bao ®ãng b¾c cÇ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. 1.4. Quan hÖ t−¬ng ®−¬ng vμ quan hÖ thø tù. 1.4.1. Quan hÖ t−¬ng ®−¬ng Mét quan hÖ hai ng«i R trªn tËp hîp A ®−îc gäi lμ quan hÖ t−¬ng ®−¬ng nÕu nã cã (tháa m·n) ba tÝnh chÊt ph¶n x¹, ®èi xøng vμ b¾c cÇu. VÝ dô 1. Cho tËp A = {1, 2, 3, 4, 5, 6, 7, 8, 9} Trªn A ta ®Þnh nghÜa quan hÖ R nh− sau: ∀a, b ∈ A th× aRb ⇔ a + b = 2k víi k lμ mét sè nguyªn d−¬ng nμo ®ã. DÔ thÊy R lμ quan hÖ t−¬ng ®−¬ng trªn A. VÝ dô 2. XÐt tËp A lμ tËp hîp c¸c sinh viªn cña líp 48K vμ xÐt quan hÖ R lμ quan hÖ ®ång h−¬ng (cïng huyÖn) trªn A. DÔ thÊy R lμ quan hÖ t−¬ng ®−¬ng trªn A. VÝ dô 3. XÐt tËp hîp Z c¸c sè nguyªn vμ quan hÖ R lμ quan hÖ ®ång d− theo modun 5 trªn Z . Khi ®ã R còng lμ quan hÖ t−¬ng ®−¬ng trªn Z . 1.4.2. TËp th−¬ng MÖnh ®Ò. Mçi quan hÖ t−¬ng ®−¬ng R trªn mét tËp A sÏ x¸c ®Þnh mét ph©n ho¹ch cña tËp A, nghÜa lμ x¸c ®Þnh mét sù ph©n chia tËp A thμnh c¸c 16
tËp con A1 , A2 , ..., Aq nμo ®ã tháa m·n c¸c tÝnh chÊt: q Ai = A (1) i=1 Ai ∩ Aj = ∅ víi i = j (2) sao cho hai phÇn tö a, b cïng thuéc mét tËp con Ai khi vμ chØ khi aRb. ThËt vËy, víi mçi a ∈ A, gäi Ra lμ tËp tÊt c¶ c¸c phÇn tö cña A cã quan hÖ víi a, khi ®ã dÔ thÊy Ra = A a∈A mÆt kh¸c nÕu Ra ∩ Rb = ∅ th× tån t¹i c ∈ Ra ∩ Rb vμ víi mäi x ∈ Ra ta cã xRa, aRc, cRb suy ra xRb, nghÜa lμ x ∈ Rb vμ ng−îc l¹i. VËy nÕu Ra ∩ Rb = ∅ th× Ra ≡ Rb . §¸nh sè c¸c tËp con d−íi d¹ng A1 , A2 , ..., Aq ta cã ®iÒu ph¶i chøng minh. Mçi tËp con thuéc ph©n ho¹ch cña A ®−îc x¸c ®Þnh theo quan hÖ t−¬ng ®−¬ng R ®−îc gäi lμ mét líp t−¬ng ®−¬ng cña A theo quan hÖ t−¬ng ®−¬ng R. Líp t−¬ng ®−¬ng cña A theo quan hÖ t−¬ng ®−¬ng R, chøa phÇn tö a th−êng ®−îc ký hiÖu lμ a. TËp hîp bao gåm tÊt c¶ c¸c phÇn tö, trong ®ã mçi phÇn tö lμ mét líp t−¬ng ®−¬ng cña A theo quan hÖ t−¬ng ®−¬ng R ®−îc gäi lμ tËp th−¬ng cña tËp A theo quan hÖ t−¬ng ®−¬ng R, ký hiÖu lμ A/R. VÝ dô 4. - Quan hÖ t−¬ng ®−¬ng trong vÝ dô 1 x¸c ®Þnh ph©n ho¹ch cña tËp A thμnh hai tËp A1 = {1, 3, 5, 7, 9} = 1 = 3 = 5 = 7 = 9 vμ A2 = {2, 4, 6, 8} = 2 = 4 = 6 = 8. TËp th−¬ng A/R = {A1 , A2 } = {1, 2}. - Quan hÖ t−¬ng ®−¬ng trong vÝ dô 2 x¸c ®Þnh ph©n ho¹ch cña tËp A thμnh c¸c tËp Ai mμ mçi Ai lμ tËp tÊt c¶ c¸c sinh viªn cña A thuéc cïng mét huyÖn. Cã thÓ coi tËp th−¬ng lμ tËp c¸c huyÖn cã sinh viªn thuéc líp 48K. - Quan hÖ t−¬ng ®−¬ng trong vÝ dô 3 x¸c ®Þnh ph©n ho¹ch cña tËp A thμnh n¨m tËp A0 = {5k | k ∈ Z }, A1 = {5k + 1 | k ∈ Z }, A2 = {5k + 2 | k ∈ Z }, A3 = {5k + 3 | k ∈ Z }, A4 = {5k + 4 | k ∈ Z }. TËp th−¬ng Z/R = {0, 1, 2, 3, 4}, (chÝnh lμ Z5 quen thuéc). 17
Ng−îc l¹i, nÕu cã mét ph©n ho¹ch tËp A (nghÜa lμ cã sù ph©n chia tËp A thμnh c¸c tËp con tháa m·n (1) vμ (2) th× ph©n ho¹ch ®ã x¸c ®Þnh mét quan hÖ t−¬ng ®−¬ng trªn tËp A. ThËt vËy, gi¶ sö A1 , A2 , ..., Aq lμ mét ph©n ho¹ch cña tËp A. Ta x¸c ®Þnh quan hÖ R trªn A nh− sau: ∀a, b ∈ A, aRb ⇔ ∃Ai sao cho a ∈ Ai , b ∈ Ai , khi ®ã R lμ quan hÖ trªn A vμ - TÝnh chÊt ph¶n x¹ tháa m·n v× víi mäi a ∈ A, do ®iÒu kiÖn (1) ¾t tån t¹i i ®Ó a ∈ Ai , do ®ã aRa. - TÝnh chÊt ®èi xøng tháa m·n v× víi mäi a, b ∈ A, nÕu aRb th× ∃Ai sao cho a ∈ Ai , b ∈ Ai , tøc lμ ∃Ai sao cho b ∈ Ai , a ∈ Ai , tøc lμ bRa. - TÝnh chÊt b¾c cÇu tháa m·n v× víi mäi a, b, c ∈ A, nÕu aRb vμ bRc th× tõ aRb suy ra ∃Ai sao cho a ∈ Ai , b ∈ Ai vμ tõ bRc suy ra ∃Aj sao cho b ∈ Aj , c ∈ Aj . Tuy nhiªn theo ®iÒu kiÖn (2) ta cã i = j , do ®ã ∃Ai sao cho a ∈ Ai , c ∈ Ai , tøc lμ aRc. VÝ dô 5. Cho A = {1, 2, 3, 4, 5, 6} vμ ph©n ho¹ch A1 = {1, 4, 5}, A2 = {3}, A3 = {2, 6}. Khi ®ã quan hÖ t−¬ng ®−¬ng R t−¬ng øng lμ R = {(1, 1), (1, 4), (1, 5), (4, 1), (4, 4), (4, 5), (5, 1), (5, 4), (5, 5), (3, 3), (2, 2), (2, 6), (6, 2), (6, 6)} . 1.4.3. Quan hÖ thø tù Mét quan hÖ hai ng«i R trªn tËp hîp A ®−îc gäi lμ quan hÖ thø tù nÕu nã cã (tháa m·n) ba tÝnh chÊt ph¶n x¹, ph¶n xøng vμ b¾c cÇu. Ng−êi ta th−êng ký hiÖu quan hÖ thø tù bëi ký hiÖu < vμ nÕu a < b hoÆc b < a th× ta nãi r»ng hai phÇn tö a vμ b so s¸nh ®−îc víi nhau. TËp A víi quan hÖ thø tù ®−îc gäi lμ tËp s¾p thø tù. VÝ dô 6. Quan hÖ ”< ” trªn Z lμ quan hÖ thø tù. VÝ dô 7. Quan hÖ quan hÖ bao hμm ⊆ gi÷a c¸c tËp con cña mét tËp hîp X lμ quan hÖ thø tù trªn tËp P (X ) tÊt c¶ c¸c tËp con cña X . . VÝ dô 8. Quan hÖ ”Chia hÕt cho”, ký hiÖu lμ . trªn N lμ quan hÖ thø tù. ., 18
Trong vÝ dô 6, víi a, b tïy ý ta lu«n cã a < b hoÆc b < a. C¸c quan hÖ thø tù cã tÝnh chÊt mäi cÆp phÇn tö ®Òu cã thÓ so s¸nh ®−îc th× ®−îc gäi lμ quan hÖ thø tù toμn phÇn hoÆc thø tù tuyÕn tÝnh. Trong c¸c vÝ dô 7 vμ 8, kh«ng ph¶i hai phÇn tö bÊt kú ®Òu cã thÓ so s¸nh ®−îc. C¸c quan hÖ thø tù nh− vËy ®−îc gäi lμ quan hÖ thø tù bé phËn. Tõ quan hÖ thø tù < , nÕu a < b vμ a = b th× ta viÕt a < b vμ ta nãi r»ng ”