Tìm phủ tối thiểu của tập phụ thuộc hàm: T = {ABH → CK, A → D, C → E, BGH → F, F → AD, E → F, BH → E}


========== Bài Làm ==========


1. Tách vế phải của các thuộc tính hàm thành các thuộc tính đơn lẻ:

ABH → C
ABH → K
A → D
C → E
BGH → F
F → A
F → D
E → F
BH → E


2. Loại bỏ các thuộc tính dư thừa phía bên trái của mỗi thuộc tính hàm:

2.1. Xét ABH → C


- Loại A trong ABH → C: Ta có (BH)+ = (BHEFADK) chứa A, nên A dư thừa.
- Loại B trong ABH → C: Ta có (AH)+ = (AHD) không chứa B, nên B không dư thừa.
- Loại H trong ABH → C: Ta có (AB)+ = (ABD) không chứa H, nên H không dư thừa.
-> Kết quả: T = {BH → C, ABH → K, A → D, BGH → F, F → A, F → D, E → F, BH → E}


2.2. Xét ABH → K


- Loại A trong ABH → K: Ta có (BH)+ = (BHEFADK) chứa A, nên A dư thừa.
- Loại B trong ABH → K: Ta có (AH)+ = (AHD) không chứa B, nên B không dư thừa.
- Loại H trong ABH → K: Ta có (AB)+ = (ABD) không chứa H, nên H không dư thừa.
-> Kết quả: T = {BH → C, BH → K, A → D, BGH → F, F → A, F → D, E → F, BH → E}

2.3. Xét BGH → F


- Loại B trong BGH → F: Ta có (GH)+ = (GH) không chứa B, nên B không dư thừa.
- Loại G trong BGH → F: Ta có (BH)+ = (BHEFDACK) không chứa G, nên G không dư thừa.
- Loại H trong BGH → F: Ta có (BG)+ = (BG) không chứa H, nên H không dư thừa.
-> Kết quả: T = {BH → C, BH → K, A → D, BGH → F, F → A, F → D, E → F, BH → E}


2.4. Xét BH → E

- Cả B và H đều không dư thừa.
-> Giữ nguyên.


3. Loại bỏ các phụ thuộc hàm dư thừa: T = {BH → C, BH → K, A → D, BGH → F, F → A, F → D, E → F, BH → E}


3.1. Thử loại bỏ BH → C:

Ta có: (BH)+ = (BHEFDAK) không chứa C, nên BH → C không dư thừa.
-> Kết quả giữ nguyên.

3.2. Thử loại bỏ BH → K:


Ta có: (BH)+ = (BHCEFDA) không chứa K, nên BH → K không dư thừa.
-> Kết quả giữ nguyên.


3.3. Thử loại bỏ A → D:


Ta có: (A)+ = (A) không chứa D, nên A → D không dư thừa.
-> Kết quả giữ nguyên.


3.4. Thử loại bỏ BGH → F:


Ta có: (BGH)+ = (BHEFDAKC) chứa F nên BGH → F dư thừa.
-> Kết quả: T = {BH → C, BH → K, A → D, F → A, F → D, E → F, BH → E}


3.5. Thử loại bỏ F → A:


Ta có: (F)+ = (FD) không chứa A, nên không dư thừa.
-> Kết quả giữ nguyên.


3.6. Thử loại bỏ F → D:


Ta có: (F)+ = (FAD) chứa D, nên dư thừa.
-> Kết quả: T = {BH → C, BH → K, A → D, F → A, E → F, BH → E}


3.7. Thử loại bỏ E → F:


Ta có: (E)+ = (E) không chứa F, nên không dư thừa.
-> Kết quả giữ nguyên.


3.8. Thử loại bỏ BH → E:


Ta có: (BH)+ = (BHCK) không chứa E, nên không dư thừa.
-> Kết quả giữ nguyên.


========= Kết quả cuối cùng ===============

T = {BH → C, BH → K, A → D, F → A, E → F, BH → E}


1. BH → C
2. BH → K
3. A → D
4. F → A
5. E → F
6. BH → E
Bài viết liên quan