Bài tập phụ thuộc hàm

NH P MÔN CSDL QUAN H So n b i b môn Công ngh ph n m m Ậ Ệ ở ộ ệ ề ạ ầ

2. BµI TËP VÒ phỤ THUỘC HÀM

M C TIÊU C A BÀI NÀY GIÚP NG

I H C

ƯỜ Ọ

c t m quan tr ng c a lý thuy t c a ph thu c hàm

ủ

ụ

ọ

ộ

Ụ  

ượ ầ ụ

ế ủ ị

i thi u, bài toán thành viên đ gi

Ủ Hi u đ ể V n d ng các thu t toán tính bao đóng, đ nh nghĩa suy di n theo ậ ễ ể ả i ề

ủ ố

ể



ế Áp d ng các thu t toán đ gi

ậ tiên đ , theo quan h , tìm ph t ệ quy t các bài t p c th . ụ ể ậ ậ

ụ

ế

ể ả ụ

ứ

ậ

ộ

i quy t các bài t p liên quan: Tìm ậ bao đóng, ch ng minh m t ph thu c hàm có d th a trong t p các ư ừ ộ ph thu c hàm không,...

ụ

ộ

Ắ

Ế

A/ NH C L I LÝ THUY T I. M T S Đ NH NGHĨA, TÍNH CH T

Ạ Ộ Ố Ị

Ấ

1. Đ nh nghĩa ph thu c hàm ụ ộ ị

XY, trong đó X,Y˝ U. ậ

ộ ậ cho U là m t t p thu c tính, m t ph thu c hàm trên U là m t phát bi u có ụ ể ộ ộ ộ ộ

" u,v ˛ R, n u u.X=v.X thì u.Y=v.Y.

ụ ệ ệ ả ộ ộ ế ậ ố ộ ớ Đ nh nghĩa: ị d ng ạ XY, Cho R là quan h trên t p thu c tính U, nói r ng quan h R tho mãn ph thu c hàm ằ n u v i 2 b b t kì trong R mà chúng gi ng nhau trên t p thu c tính X thì chúng cũng gi ng ố nhau trên t p thu c tính Y, nghĩa là ế ộ ộ ấ ậ

XY là m t ph thu c hàm trên U thì ta nói t p thu c tính Y ph thu c hàm vào t p N u f=ế ậ thu c tính X (Y functional dependent on X ) ho c t p thu c tính X xác đ nh hàm t p thu c ộ ặ ậ ộ tính Y (X functional determines Y).

ụ ụ ậ ộ ộ ộ ộ ậ ộ ị

ụ ụ ệ ộ ộ ộ Cho f là m t ph thu c hàm trên U, n u quan h R tho mãn ph thu c hàm f thì ta ký hi u ệ R(f), n u R không tho mãn ph thu c hàm thì ta ký hi u ả ệ ø R(f). ế ộ ụ ế ả

F thì R(f) hay nói m t cách t ừ

f ˛ ư

ệ ằ ả ộ ậ ng đ ộ ậ ệ ụ ế ỉ ế ươ ươ ộ Cho F là m t t p các ph thu c hàm trên U, nói r ng quan h R tho mãn t p ph thu c ụ ớ " hàm F, ký hi u là R(F) n u và ch n u v i ng quan h R tho mãn t p ph thu c hàm F n u nh nó tho mãn t ng ph thu c hàm trong t p đó. ộ ụ ụ ệ ế ả ậ ả ậ ộ ộ

ị c đ quan h là m t c p ệ ượ ộ ặ a =(U, F) trong đó U là t p h u h n các thu c tính ữ ậ ạ ộ Đ nh nghĩa: L ồ còn F là t p các ph thu c hàm trên U. ụ ậ ộ

2. M t s tính ch t c a ph thu c hàm: ấ ủ ộ ố ụ ộ ả ạ " X, Y˝ U, Y˝ X, thì XY ầ " X, Y, Z˝ U, n u có X ế

Y và YZ thì XZ " X, Y˝ U, n u Xế  Y và " Z˝ U thì XZYZ ầ " X, Y, Z, W ˝ U, n u Xế Y, YZ W thì XZW ắ ả ạ ặ " X˝ U thì XX " X, Y, Z ˝ U, n u có X YZ thì có: 1) Tính ch t ph n x : ấ 2) Tính ch t b c c u: ấ ắ 3) Tính ch t gia tăng: ấ 4) Tính ch t t a b c c u: ấ ự 5) Tính ch t ph n x ch t: ấ 6) Lu t tách: ậ ế

XY XZ

Trang 1

NH P MÔN CSDL QUAN H So n b i b môn Công ngh ph n m m Ậ Ệ ở ộ ệ ề ạ ầ

" X, Y, Z ˝ U, n u có X  Y và XZ thì có XYZ ế

ấ ộ " X, Y, Z, W ˝ U, n u Xế Y, Z W thì XZYW 7) Lu t h p: ậ ợ 8) Tính ch t c ng tính:

ệ ˝ Y thì Y X

3. H tiên đ Amstrong ề F1 - Lu t ph n x ậ ả F2 - B c c u ắ ạ " X,Y˝ U, n u Xế ầ " X, Y, Z ˝ U n u có ế

thì XZ

XY YZ

F3 - Lu t gia tăng " X, Y, Z ˝ U, n u có X Y thì XZYZ ậ ế

ề ị ẫ ệ ộ ộ ụ 4. Đ nh nghĩa suy d n theo h tiên đ ậ ề ệ ẫ ộ c t Cho F là t p ph thu c hàm trên U, f là m t ph thu c hàm trên U ( f có th không ể ├ f n u nh f ư ế ề ụ F theo h tiên đ Amstrong và kí hi u là F t p F sau m t s h u h n l n áp d ng các lu t c a h tiên đ ủ ộ ệ ố ữ ụ ệ ạ ầ ậ ậ ượ ừ ậ

ậ F thì F├ f c suy d n t t p F theo h tiên đ Amstrong. f ˛ ậ ấ ả ộ t c các ph thu c hàm đ ụ ượ ẫ ừ ậ ệ ề

+ =F thì ta nói F là m t t p đ y đ

ộ thu c F), nói r ng f suy d n đ c t ượ ừ ằ có th nh n đ ể Amstrong. Nh n xét: V iớ " + là t p t F+ ủ ậ ụ ế ọ ộ ộ ậ ầ ủ c g i là bao đóng c a t p ph thu c hàm F, n u F ụ ậ ộ Kí hi u Fệ Ta th y ấ F˝ F+ đ ượ các ph thu c hàm, đôi khi ta còn nói F là t p đóng. 5. Đ nh nghĩa suy d n theo quan h ệ ẫ ị

ụ ụ ộ Cho F là m t t p các ph thu c hàm trên t p thu c tính U, f là m t ph thu c hàm ộ t p F theo quan h và ký hi u F ộ ằ ệ ộ ộ ậ trên U, (f có th không thu c F), nói r ng f đ ╞f, n u và ch n u v i m i quan h R trên U, n u R tho mãn F thì R cũng tho mãn f. ậ c suy d n t ượ ế ộ ẫ ừ ậ ả ể ỉ ế ệ ả ế ệ ớ ọ

c suy d n t ệ ậ ấ ả t c các ph thu c hàm đ ụ ộ ượ ẫ ừ ậ t p F theo quan h . ệ Ký hi u F* là t p t F*={f:XY | X,Y˝ U, F╞f}

ấ ủ ộ ˝ đây ta suy ra F F*. ˝ ộ Tính ch t c a F*: Cho F và G là hai t p ph hàm trên t p thu c tính U khi đó ta có: ậ ậ ụ ạ ớ " f ˛ F thì F ╞f t 1. Tính ph n x : V i ừ ả G thì F* ˝ G*. 2. Tính đ n đi u: N u F ế ệ ơ 3. Tính lu đ ng: V i m i t p ph thu c hàm F thì ta luôn có (F*)*=F*. ớ ụ ỹ ẳ 6. Bao đóng c a t p thu c tính ủ ậ ọ ậ ộ

˝ U, bao đóng c a t p thu c tính X, kí hi u là X Cho t p ph thu c hàm F trên U, X ộ ụ ủ ậ ệ ộ ậ c xác đ nh nh sau: đ ư ị ượ X+= { A | A˛ U và XA˛ F+ }

ậ ộ ậ ủ ộ

* Thu t toán tìm bao đóng c a m t t p thu c tính Input a = (U,F), X˝ U Output X+ =?

(0), X(1), X(2),... theo quy n p nh sau

Thu t toán ậ ư ạ

(i) (i>=0)

s r ng đã xây d ng đ c th i t c là đã bi t X Ta xác đ nh dãy X ị (0)=X 1. Đ t Xặ 2. Gi ả ử ằ ự ượ c đ n b ế ướ ứ ứ ế

Trang 2

NH P MÔN CSDL QUAN H So n b i b môn Công ngh ph n m m Ậ Ệ ở ộ ệ ề ầ ạ

c i+1 nh sau ế ư

3. Xây d ng ti p b ự X(i+1)= X(i) ¨ Z(i) = ¨ ướ Z(i) trong đó Yj v i đi u ki n : ề ớ ệ

X

˛

j

X

Y

ủ ậ ợ ế

Y F (1) ˝ Xi (2) J ¸ X(i) (3) ụ ộ c thêm vào.

(i) chính là h p c a các v ph i c a các ph thu c hàm trong t p F mà có v ủ ậ ỉ

ế ả ượ ế Vì v y Zậ ả ủ trái là t p con c a t p tr c mà có v ph i ch a đ ướ ư đi u ki n (3) ch có tác d ng tăng t c đ tính toán ụ ậ ệ ề ố ộ

ậ i ch s i nào đó đ ồ ạ ặ ở ộ ể Nh n xét: X(0), X(1), X(2),... là m t dãy không gi m và b ch n trên b i U, do đó t n t ị ả X(i)= X(i+1) (*), g i i là ch s nh nh t khi đó X ỉ ố + = X(i) hay khi X(i) = U thì X+ = X(i) = U. ỉ ố ấ ọ ỏ

+ =F+ ượ

7. Ph thu c hàm d th a ư ừ ụ ộ ˛ F, f ộ ậ ụ ứ ủ ụ ộ ộ ộ đ ượ c g i là d th a trong F n u nh (F-f) ư ng f đ c g i là d th a trong F n n nó suy d n đ ư ừ ươ ế ẫ ọ ượ ừ c t Cho F là m t t p các ph thu c hàm trên U, f là m t ph thu c hàm c a F t c f ư ừ ọ Hay có th nói t ể t p F sau khi đã b đi ph thu c hàm f. ỏ ậ ế ng đ ộ ươ ụ

Thu t toán thành viên ậ

Input ậ ụ ộ - T p ph thu c hàm F - f ˛ F Output ư ừ - True n u nh f là d th a trong F - False n u nh f là không d th a trong F ư ư ế ế ư ừ Method ọ ỏ ậ ạ c ượ

c 2, còn không thì k t thúc thu t toán ướ ế ậ ế ậ

+ và so sánh v i t p con Y ta có ngay câu tr l

2) Gi s thì f là d th a trong F còn ng ư ừ ượ c ả ử f=XY n u Gế 1) t m xoá f kh i F, g i G là t p thu đ G=F-f, n u ế G„f thì chuy n qua b ể và k t lu n f là không d th a trong F ư ừ ├ f t c ứ Y˝ X G i f là không d th a. ư ừ ﬁ i X l ạ ỉ ầ ư ậ ớ ậ ả ờ Y có thu cộ

Nh v y, ta ch c n tính X vào F+ hay không. 8. Ph thu c hàm d th a ư ừ ụ ộ

II. CÁC VÍ DỤ

ệ a c đ quan h = (U,F) v iớ ồ

Ví d 1:ụ Cho l ượ U = ABCDEGH F={ BC ADE, AC BDG, BE ABC, CD BDH, BCH ACG}

Trang 3

NH P MÔN CSDL QUAN H So n b i b môn Công ngh ph n m m Ậ Ệ ở ộ ệ ề ạ ầ

ng h p ườ ợ

Hãy tính X+ trong các tr a) X=BD b) X=ABE c) X=CDG

+ =X=BD

F =BD

(ADE ¨ Z(0) =ABE ¨ ABC=ABCE Z(1) =ABCE ¨ Z(2) = ABCDEG ¨ BDG)=ABCDEG BDH=ABCDEGH=U iả Gi a) đ t X(0)=BD (=X) ặ Z(0) =BD ¨ X(1) = X(0) ¨ Suy ra X(0)= X(1) v y Xậ b) đ t X(0)=ABE (=X) ặ X(1) = X(0) ¨ X(2) = X(1) ¨ X(3) = X(2) ¨ +=U V y Xậ

Ví d 2 :ụ s có t p Áp d ng bài toán thành viên ụ Gi ả ử Hãy cho bi ậ F={XYW, XWZ, ZY, XYZ} tế XYZ có d th a trong F hay không? ư ừ

iả ạ Z ra kh i Fỏ

G ( bao đóng c a XY trong t p G)

G= XYWZ th nên Z

G hay G├ (XYZ) th nên ph thu c hàm XY

ủ ậ ˝ (XY)+ ế ụ ế ộ Z là dư Gi 1) T m th i xoá XY ờ G:=F-{XYZ}={XYW, XWZ, ZY} 2) Tính (XY)+ ta có (XY)+ th a trong F. ừ

ụ ứ ệ

Ộ Ố Ư III. M T S L U Ý  Tiên đ Amstrong. Áp d ng h tiên đ amstrong trong các bài toán ch ng minh. ề ề  Ph thu c hàm theo quan h và theo tiên đ , bao đóng c a t p các thu c tính và c a ủ

ủ ậ ụ ệ ề ộ ộ t p các ph thu c hàm. ụ ậ ộ

Ẫ

CD, ACEBG, BCD AE, CH DG} ậ ậ F+) ?

B/ BÀI T P M U Ậ Bài s 1:ố Cho t p thu c tính U=ABCDEGH ộ Cho t p ph thu c hàm F={ AB ộ ụ ỏ ằ F├ f hay không (f ˛ f=BCDH AG, h i r ng

ướ ẫ ứ ệ ề ệ ế ầ ấ H ng d n: ụ ph thu c hàm c n ch ng minh sau đó l n l Áp d ng h tiên đ Amstrong đ ch ng minh, đ u tiên c n làm xu t hi n v trái c a ủ ộ ầ t áp d ng 3 tiên đ đ suy ra ĐPCM. ề ể ể ầ ượ ứ ụ ụ ầ

Gi iả ạ ả ấ

ạ ấ ắ ầ thi

BCDH BCD (1) ( tính ch t ph n x ) BCDAE ( gt) (2) BCDACE ( gia tăng) (3) ACE A (ph n x ) (4) ả Suy ra BCDH A theo tính ch t b c c u(5) ACE BG (6) gi t ả ế BGG (7) ph n xả ạ

Trang 4

NH P MÔN CSDL QUAN H So n b i b môn Công ngh ph n m m Ậ Ệ ở ộ ệ ề ạ ầ

ầ ắ Suy ra ACE G(8) b c c u Suy ra BCDH G (9) b c c u ắ ầ

ừ ậ T (5) và (9) theo lu t c ng tính ( lu t ghép) ậ ộ Suy ra BCDH AG ˛ F+ ( đpcm)

Bài s 2:ố

ng h p ườ ợ

Cho a =(U,F); U=ABCDEGH F={ ABBCP, EBGH, ACD BG, DAEH} Hãy tính X+ trong các tr a) X=AC b) X=CD c) X=ABG

ướ t các b c c a thu t toán tính bao đóng. H ng d n: Áp d ng l n l ướ ủ ậ ẫ ầ ượ ụ

Gi iả

f = X(0) nên X+=AC

AEH =ACDEH ( BGH ¨ BG) = ACDEH ¨ ( BGH ¨ BG) = ABCDEGH =U

(BCD ¨ BG ¨ AEH)= ABCDEGH =U

C/ BÀI T P T GI

a) Vì X=AC X(0)= X=AC X(1) = X(0) ¨ b) Vì X=CD X(0)=X=CD X(1) = X(0) ¨ X(2)= X(1)¨ Do X(2)=U nên X+=U c) Vì X=ABG X(0)=X=ABG X(1)= ABG ¨ BCD=ABCDG X(2)= ABCDG ¨ Do X(2)=U nên X(3)= X(2) hay X(3)=U I Ậ Ự Ả

c đ quan h ồ

GH, Gﬁ A} Bài t p 1: ậ Cho l ượ U=ABCDEGH và t p ph th c hàm ậ D, CDﬁ F={AB ﬁ f=ABﬁ E, ch ng minh r ng v i m i quan h R trên U n u R tho F thì R cũng tho f. ệ ằ ệ a =(u, F) v iớ ụ ộ E, CEﬁ ớ C, Bﬁ ứ ế ả ả ọ

ồ

Bài t p 2: ậ Cho l ượ U=ABCDEGHIJ và t p ph th c hàm F={ABﬁ H} f=ABﬁ GH, ch ng minh r ng f suy d n đ F c đ quan h (=(U, F) v i ớ ệ ậ E, AGﬁ J, BEﬁ ứ ụ ộ I, Eﬁ G, GIﬁ ằ ẫ c t ượ ừ

c đ quan h (=(u, F) v i ớ ệ ượ ồ Bài t p 3ậ Cho l U=ABCDEGH và t p ph th c hàm ụ ộ ậ

Trang 5

NH P MÔN CSDL QUAN H So n b i b môn Công ngh ph n m m Ậ Ệ ở ộ ệ ề ạ ầ

F={ABﬁ C, Bﬁ D, CDﬁ E, CEﬁ GH, Gﬁ A}

Hãy ch ng minh ứ a. ABﬁ E b. BGﬁ C c. ABﬁ G

ụ ộ ậ ồ

c đ quan h (=(u, F) và t p ph th c hàm I, Eﬁ G, GIﬁ H} ﬁ GH suy d n đ F Bài t pậ 4 Cho l ệ ượ F={ABﬁ E, AGﬁ I, BEﬁ Ch ng minh r ng AB ằ c t ượ ừ ứ ẫ

c đ quan h (=(u, F) và t p ph th c hàm ụ ộ ượ ậ ồ

Bài t p 5ậ Cho l ệ F={ABﬁ C, Bﬁ D, CDﬁ E, CEﬁ GH, Gﬁ A} Ch ng minh r ng AB ﬁ E v à ABﬁ G suy d n đ F ứ ẫ ằ c t ượ ừ

ụ ủ ộ

Bài t p 6ậ Tìm ph không d c a t p ph thu c hàm ư ủ ậ F={Aﬁ C, ABﬁ C, Cﬁ DI, ECﬁ AB, EIﬁ C}

ﬁ D suy d n đ F ẫ c t ượ ừ

(cid:204) B, hãy ch ng minh A ứ

Bài t p 7ậ Cho F={Aﬁ B, Cﬁ D} v i Cớ

Bài t p 8ậ

ﬁ Y đ c g i là d th a trong t p ph thu c hàm F n u nh ộ ộ ượ ọ ư ừ ụ ế ậ ộ ư F+= (F-

M t ph thu c hàm X ụ {Xﬁ Y})+ cho F={Xﬁ YW, XWﬁ Z, Zﬁ Y, XYﬁ Z} hãy cho bi ﬁ Z có d th a trong F hay không t ph thu c hàm XY ộ ụ ế ư ừ

ư ủ ủ Bài t p 9ậ Tìm ph không d c a F={ Xﬁ YZ, ZWﬁ P, Pﬁ Z, Wﬁ XPQ, XYQﬁ YW, WQﬁ YZ}

c đ quan h F Bài t p 10 ậ Cho l ượ hãy cho bi ồ t các ph th c hàm nào d ế ệ R(ABCD) v à F={Aﬁ B, BCﬁ D} i đây có th suy d n đ ể ụ ộ ướ ẫ c t ượ ừ

1. ACﬁ D 2. Bﬁ D 3. ADﬁ B

ﬁ P suy d n đ Bài t p 11 ậ F={XYﬁ W, Yﬁ Z, WZﬁ P, WPﬁ QR, Qﬁ X} F c t ch ng minh r ng XY ượ ừ ứ ằ ẫ

Bài t p 12 ậ Lo i b các ph thu c hàm d th a trong t p ạ ỏ ư ừ ụ ậ ộ

Trang 6

NH P MÔN CSDL QUAN H So n b i b môn Công ngh ph n m m Ậ Ệ ở ộ ệ ề ạ ầ

F={Xﬁ Y, Yﬁ X, Yﬁ Z. Zﬁ Y, Xﬁ Z, Zﬁ X}

Bài t p 13 ậ cho F={XYﬁ W, Yﬁ Z, WZﬁ P, WPﬁ ﬁ Q suy d n đ ch ng minh r ng XY F ứ ằ ẫ QR, Qﬁ X} c t ượ ừ

Bài t p 14 ậ Cho F={Aﬁ BC, Eﬁ C, Dﬁ AEF, AFﬁ B,AFﬁ D} ph thu c hàm AF(B có d th a trong F không ư ừ ụ ộ

c g i là d th a n u ộ ư ừ ượ ọ ế Y ˛ F+ ư ừ ạ ỏ ậ ộ

Bài t p 15 ậ N u ế Xﬁ Y ˛ F , A˛ X, thu c tính A đ { X- A } ﬁ hãy lo i b các thu c tính d th a trong các t p sau: a. F={Xﬁ YW, XWﬁ Z, Zﬁ Y, XYﬁ Z } b. F={Aﬁ BC, Eﬁ C, Dﬁ AEF, ABFﬁ BD }

ề ứ ấ ﬁ Y và YZﬁ W thì XZﬁ W ự ậ ủ ầ ạ

ặ N u ế Xﬁ Y và Zﬁ W thì XZﬁ YW N u ế Xﬁ Y và Xﬁ Z th ì Xﬁ YZ ấ ợ

Bài t p 16 ậ S d ng các lu t c a h tiên đ Amstrong ch ng minh các tính ch t sau: ệ ử ụ a. Tính t a b c c u: N u X ế ắ ﬁ X b. Tính ph n x ch t X ả c. Tính c ng tính : ộ d. Tính ch t h p : e. Tính tách : N u ế Xﬁ YZ thì Xﬁ Y v à Xﬁ Z f. Tính tích lu : ỹ N u ế Xﬁ YZ, Zﬁ VW thì Xﬁ YVW

ệ a =(U, F) v i U=ABCDEG và ớ ượ ồ

Bài t pậ 17 Cho l c đ quan h F={Aﬁ C, BCﬁ D, Dﬁ E, Eﬁ A}. Hãy tính

a) (AB)+ b) ((DE)+A)+

c đ quan h ệ a =(U, F) v i U=ABCDEG và ớ ồ Bài t p 18 ậ Cho l ượ F={Bﬁ C, ACﬁ D, Dﬁ G, AGﬁ E} hãy cho bi tế

a) ABﬁ G˛ F+ b) BDﬁ AD˛ F+

c đ quan h ồ ớ ượ ệ a =(U, F) v i U=ABCDEGH

F ẫ ﬁ BHE ﬁ DH không suy d n đ ệ ọ c t ượ ừ ế ả ả ớ Bài t pậ 19 Cho l F={ABﬁ GH, GDﬁ AHE, Cﬁ AGH, HEﬁ BC } a) tính (CE)+ b) tính (CD)+ c) Ch ng minh r ng ABE ứ d) Ch ng minh r ng v i m i quan h R trên U N u R tho F thì R cũng tho ACD ứ e) Ch ng minh r ng F├ ABE ứ ằ ằ ằ

Trang 7

NH P MÔN CSDL QUAN H So n b i b môn Công ngh ph n m m Ậ Ệ ở ộ ề ệ ầ ạ

ủ ể

Bài t p 20 ậ Hãy tìm ph c c ti u c a ủ ự a) F={ABﬁ C, Aﬁ D, BDﬁ C} b) F={ABﬁ C, Aﬁ B}

BEG } . ﬁ ph thu c hàm f = BD CGH suy ệ a c đ quan h ồ AEG , ABE ﬁ ệ ứ ỏ ụ ộ Bài t p 21 ậ Cho l ượ F = { B ﬁ B ng các lu t c a h tiên đ Armstrong hãy ch ng t ằ ậ ủ t p các ph thu c hàm F. d n đ ẫ = (U, F) v i U = ABCDEGH và ớ CH , ACD ﬁ ề ộ c t ượ ừ ậ ụ

= (U,F) v i U = ABCDEGH và ệ a c đ quan h ớ DE} ﬁ BCD, ABC ﬁ DEG. Hãy ch ra r ng f có th d n đ t p F theo ộ ể ẫ ằ ỉ c t ượ ừ ậ Bài t p 22 ậ Cho l ồ ượ F = { AE ﬁ BD , DG ﬁ BEG , CEH ﬁ và m t ph thu c hàm f = ACE ụ ộ các lu t c a h tiên đ Armstrong. ậ ủ ề ệ

Bài t p 23 ậ

Cho l = (U, F) và X,Y,Z là các t p con c a t p thu c tính U. D a vào các ệ a c đ quan h ồ ượ ủ ậ ậ ﬁ ự c suy d n t ứ ụ ề ệ ộ ẫ ừ ﬁ ằ Y và X ﬁ ộ lu t c a h tiên đ Armstrong hãy ch ng minh r ng ph thu c hàm X ậ ủ Z cũng suy d n đ t p F khi và ch khi các ph thu c hàm X ậ ụ ẫ ộ ỉ YZ đ ượ t p F. c t ượ ừ ậ

Bài t p 24 ậ

= (U,F) v i U = ABCDEGH và ượ ệ a c đ quan h

ﬁ ộ BCD, ABC ﬁ DE} DEG. Hãy ch ra r ng f d n đ ỉ ằ ẫ c t ượ ừ ậ ệ t p F b ng vi c ằ ng d ng các lu t c a h tiên đ Armstrong. Cho l ồ ớ BD , DG ﬁ BEG , CEH ﬁ F = { AE ﬁ và m t ph thu c hàm f = ACE ộ ụ ụ ứ ậ ủ ệ ề