Key: 

  • Luật phân rã: X → YZ => X → Y, X →Z
  • Luật hợp: X → Y, X → Z => X →YZ
  • Luật bắt cầu giả: X → Y và WY → Z => WX → Z
  • Luật phản xạ: XY → XY

 

Cho lược đồ quan hệ  (U,F) với :

U = ABCDEGH và tập phụ thuộc hàm 

F = {AB → E , AG →  J , BE →  I , E →  G ,  GI →  H}

  •          f = AB → GH , Chứng minh f được suy diễn từ F 

 

Hướng dẫn giải :

Cách 1:

  • AB → E, E → G (gt)

=> AB → G  (Luật bắc cầu)  (1)

  • AB → E, BE → I (gt)

=> ABB → I  (hay  AB →  I)  (Bắt cầu giả)  (2)

(Giải thích:  Theo như bát cầu giả có: X → Y và WY → Z => WX → Z . Như vậy X là AB, W là B và Z là I)

  • Từ (1) và (2) => AB → GI (Luật kết hợp)  (3)
  • Mà GI → H (gt) Kết hợp với (3)  => AB → H (Luật bắc cầu) (4)
  • Từ (1) và (4) => AB → GH (Luật hợp) (đpcm)

Cách 2:

F = {AB → E , AG →  I , BE →  I , E →  G ,  GI →  H}

(Ở đây là AG → I chứ không phải J nha, do đề này mình ghép nó vào luôn cho cùng một mạch bài làm)

  • AB → E (gt)  và E → G (gt) => AB → G (Luật bắt cầu giả) (1)
  • AG → I (gt) và GI → H (gt) => AG → H (Luật bắt cầu giả) (2)
  • Từ (1) và (2) => AB → H (Luật hợp) (3)
  • AB → G (gt) và  (3)  => AB → GH (đpcm)

Cách 3 :

F = {AB → E , AG →  J , BE →  I , E →  G ,  GI →  H}

Ta có : AB → AB (luật phản xạ)

  • AB → E  => AB → ABE (1)
  • BE → I  từ (1) => AB → ABEI (2)
  • E → G từ (2)  => AB → ABEIG (3)
  • GI → H từ (3) => AB → ABEIGH (4)
  • Từ (4) ta có AB → GH (Luật phân rã) – đpcm . 

Cách 4 : (Siêu tốc) – (Hệ quả của cách 3)

F = {AB → E , AG →  J , BE →  I , E →  G ,  GI →  H}

Tìm bao đóng AB+

  • AB+ ={ABEIGHJ}

Có chứa GH nên suy ra AB →  GH – đpcm .