30/09/2018, 21:00

Tìm phủ tối thiểu

Xin chào a chị, em là mem mới gia nhập diễn đàn, e có một chút thắc mắc về bài tập này, mong mọi ngời giúp đỡ.
Đề bài là tìm phủ tối thiểu với lược đồ bên dưới

*Đáp án và cách giải: (em chỉ tham khảo)

Bước 1: đưa vế phải về dạng 1 thuộc tính:
G = { AC->B (1),
BI->A (2), BI-> C (3), BI-> D (4),
ABC->D (5) ,
H->I (6) ,
ACE->B (7), ACE->C (8), ACE->G (9),
CG->A (10)}
Bước 2: Bỏ phụ thuộc hàm không quan trọng
o Bỏ (1): B không thuộc (AC)+, không bỏ (1)
o Bỏ (2): A không thuộc (BI)+, không bỏ (2)
o Bỏ (3): C không thuộc (BI)+, không bỏ (3)
o Bỏ (4): D thuộc (BI)+, bỏ (4).
o Bỏ (5): D không thuộc (ABC)+, không bỏ (5).
o Bỏ (6): I không thuộc (H)+, không bỏ (6).
o Bỏ (7): B thuộc (ACE)+, bỏ (7)
o Bỏ (8): C thuộc (ACE)+, bỏ (8)
o Bỏ (9): G không thuộc (ACE)+, không bỏ (9).
o Bỏ (10): A không thuộc (CG)+, không bỏ (10).
Vậy G = { AC->B (1),
BI-> A (2), BI-> C (3),
ABC->D (5) ,
H->I (6) ,
ACE->G (9),
CG->A (10)}
Bước 3: Bỏ thuộc tính vế trái không quan trọng
o Xét (1):
 Bỏ A: B không thuộc ©+, không bỏ được A
 Bỏ C: B không thuộc (A)+, không bỏ được C.
o Xét (2):
 Bỏ B: A không thuộc (I)+, không bỏ được B.
 Bỏ I: A không thuộc (B)+, không bỏ được I.
o Xét (3):
 Bỏ B: C không thuộc (I)+, không bỏ được B.
 Bỏ I: C không thuộc (B)+, không bỏ được I.
o Xét (5): ABC->D
 Bỏ A: D không thuộc (BC)+, không bỏ được A.
 Bỏ B: D thuộc (AC)+, bỏ B
 Bỏ C: D không thuộc (A)+, không bỏ được C
o Xét (9): ACE->G
 Bỏ A: G không thuộc (CE)+, không bỏ được A.
 Bỏ C: G không thuộc (AE)+, không bỏ được C.
 Bỏ E: G không thuộc (AC)+, không bỏ được E.
o Xét (10): CG->A
 Bỏ C: A không thuộc (G)+, không bỏ được C.
 Bỏ G: A không thuộc ©+, không bỏ được G.
Vậy phủ tối thiểu:
G = { AC->B, BI-> A, BI-> C, AC->D, H->I, ACE->G, CG->A}
Nhưng em giải ra nhiều hơn đáp án 3 cái:
BI->D
ACE ->G
ACE->B

E thắc mắc bước 2 như cách làm trên đã chính xác chưa, vì thường e làm đối với XY->Z,
Ở bước 2: Nếu kết quả X+, ko có Y thì ko loại Y, ngược lại có Y thì loại Y nên chỉ còn còn X->Z. Tương tự với tính Y+. Các làm ở bước 2 lại hoàn toàn khác e nên ra kết quả khác

Khoa Nguyen viết 23:09 ngày 30/09/2018

Nếu bạn giải quyết được rồi thì hãy post câu trả lời lên cho mọi ngườ cùng tham khảo. Diễn đàn khuyến khi ha điều đó chứ không khuyến khích hành đoogj này của bạn

Time.to.study viết 23:03 ngày 30/09/2018

Thank bạn đã góp ý, do vấn đề nằm ở chỗ mình đã giải bài này sai. Mình đã edit lại cho mọi người xem.

Bài liên quan
0