Một số vấn đề về phụ thuộc hàm và phụ thuộc hàm xấp xỉ trong lý thuyết tập thô và ứng dụng vào bài toán rút gọn thuộc tính

Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 60, 4 - 2019 161
MỘT SỐ VẤN ĐỀ VỀ PHỤ THUỘC HÀM VÀ PHỤ THUỘC HÀM 
XẤP XỈ TRONG LÝ THUYẾT TẬP THÔ VÀ ỨNG DỤNG VÀO BÀI 
TOÁN RÚT GỌN THUỘC TÍNH 
Nguyễn Bá Tường1* , Nguyễn Bá Quảng2 
Tóm tắt: Trong bài viết này chúng tôi trình bày một số khái niệm và tính chất 
liên quan đến hệ thông tin S = (U, A), phụ thuộc hàm, phụ thuộc xấp xỉ, vùng dương 
trong lý thuyết tập thô. Chúng tôi nghiên cứu các tính chất của vùng dương, các 
ràng buộc giữa các thuộc tính và đặc biệt giữa các thuộc tính điều kiện trong hệ 
quyết định, trên cơ sở đó xây dựng thuật toán heuristic tìm tập rút gọn trong bảng 
quyết định sử dụng độ phụ thuộc của thuộc tính. 
 Từ khóa: Phân hoạch; Quan hệ; Xấp xỉ; Tập thô; Phụ thuộc hàm; Phụ thuộc xấp xỉ; Rút gọn thuộc tính. 
1. MỘT SỐ KHÁI NIỆM CƠ BẢN 
Hầu hết các định nghĩa, khái niệm cơ bản trong bài viết này được trích từ các tài liệu 
tham khảo [1-5]. 
Định nghĩa 1. Quan hệ tương đương trên tập U 
R là quan hệ tương đương trên tập U nếu R  U U và R thỏa mãn ba tính chất phản 
xạ, đối xứng, bắc cầu. 
Chú ý: Thay cho (u,v) R đôi khi ta viết uRv. 
Quan hệ tương đương R trên U sẽ chia U thành các nhóm tương đương, ta ký hiệu họ 
các nhóm tương đương đó là U/R. 
Vậy U/R = {[t]R: với t U và [t]R là lớp các phần tử t’ mà tRt’}. 
Định nghĩa 2. Phân hoạch của U 
Cho tập U hữu hạn, khác rỗng. 
Họ E = {E1, E2, ..., Ek} các tập con của U là phân hoạch của U nếu E thỏa mãn 3 điều 
kiện: 
(1) Tính khác rỗng: Các Ei khác rỗng. 
(2) Tính rời nhau: Ei Ej =  nếu i j. 
(3) Tính đầy đủ: 
k
i
iE
1 
 = U. 
Bổ đề 1. Cho U là tập hữu hạn khác rỗng. Khi đó 
a. Với mọi quan hệ tương đương R trên U thì U/R là một phân hoạch. 
b. Với mọi phân hoạch E = { E1, E2, ..., Ek} của U luôn tồn tại quan hệ tương đương R 
trên U để U/R = E. 
Chứng minh: 
a. Ta chứng minh U/R = {[t]R} là một phân hoạch 
(1) Tính khác rỗng: với mọi t thì [t]R khác rỗng vì ít nhất chứa t. 
(2) Tính rời nhau: giả sử [t]R và [t’]R là hai nhóm khác nhau, ta chứng minh 
[t]R [t’]R = . Thật vậy nếu [t]R và [t’]R có phần tử chung t’’ thì dễ 
thấy rằng [t]R = [t’’]R = [t’]R => [t]R = [t’]R vô lý. 
(3) Tính đầy đủ: 
Ut
Rt
][ = U vì phép hợp lấy với mọi t thuộc U. 
Công nghệ thông tin & Cơ sở toán học cho tin học 
N. B. Tường, N. B. Quảng, “Một số vấn đề về phụ thuộc hàm  rút gọn thuộc tính.” 162 
b. Giả sử E = {E1, E2, ..., Ek} là phân hoạch của U. 
Ta xây dựng quan hệ R trên U để U/R = E. Đặt R = 
k
i
ii EE
1 
 dễ dàng thử lại rằng R 
là quan hệ tương đương trên U và U/R = E đpcm. 
Định nghĩa 3. Hệ thông tin đầy đủ (complete information system) là S = (U, A), Trong 
đó U = {t1, t2, ..., tm} là tập hữu hạn, khác rỗng các đối tượng (Universe). A = {A1, A2, 
..., An} là tập hữu hạn, khác rỗng các thuộc tính. Giá trị (thông tin) của đối tượng t U tại 
thuộc tính a A là t.a. Tương tự với mọi t U và X  A, khi đó t.X là chiếu của t lên 
X. Nếu giá trị của đối tượng t tại a có nhiều hơn một giá trị thì hệ thông tin là đa trị (a set-
value information system). 
Trong bài viết này ta chỉ xét hệ thông tin đầy đủ, nên thay cho hệ thông tin đầy đủ S 
=(U, A) ta chỉ viết hệ thông tin S = (U, A). 
Trong bài viết ta sẽ dùng các ký tự X, Y, Z, V, W,... để chỉ các tập thuộc tính và các ký 
tự thường a, b, c, d, e,... để chỉ các thuộc tính, mặt khác ta dùng XY thay cho X  Y và 
abc thay cho {a, b, c}. 
Thông thường hệ thông tin được biểu diễn dạng bảng hai chiều (xem Bảng 1). 
Thí dụ trong Bảng 1: S = (U, A), với U = { t1, t2, t3, t4, t5, t6, t7, t8, t9, t10}; 
A = {a, b, c, d, e}; t1.a = 1, t1.abcd = (1, 1, 1, 1), t2.abcde = (2, 1, 1, 1, 1) 
 Bảng 1. Hệ thông tin đầy đủ. 
U a b c d e 
t1 1 1 1 1 1 
t2 2 1 1 1 1 
t3 2 1 2 2 1 
t4 3 2 2 2 1 
t5 3 2 2 2 2 
t6 3 2 2 3 2 
t7 2 2 3 3 2 
t8 1 2 3 1 3 
t9 1 3 3 1 3 
t10 1 3 1 1 2 
Định nghĩa 4. Hệ thông tin S’ = (U’, A ) là hệ thông tin con của S = (U, A) nếu U’  U. 
Định nghĩa 5. Hệ quyết định là hệ tin SD mà trong tập thuộc tính A có tập thuộc tính 
quyết định D. 
Vậy hệ quyết định SD = (U, A); trong đó A = C  D; C  D = . Tập C được gọi là 
tập thuộc tính điều kiện, D là tập thuộc tính quyết định. 
Phân hoạch U/C = { X1, X2, ..., Xk} là phân hoạch điều kiện. 
Phân hoạch U/D = {Y1, Y2, ..., Yl} là phân hoạch quyết định. 
Định nghĩa 6. Hệ quyết định SD = (U, C  D ) là nhất quán nếu mọi cặp t, t’ U mà 
t.C = t’.C thì t.D = t’.D. Nói cách khác SD là nhất quán nếu các đối tượng giống nhau trên 
C thì giống nhau trên D. 
Định nghĩa 7. Cho hệ thông tin S = (U, A); 
Tập R  A được gọi là tập rút gọn của A nếu R là tập tối thiểu thỏa mãn 
U/R = U/A. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 60, 4 - 2019 163
Thí dụ xét hệ thông tin trong Bảng 1 ta có R = acde là một rút gọn vì R là tập tối thiểu 
mà U/R = U/A. R tối thiểu ở đây phải hiểu rằng bỏ khỏi R một thuộc tính thì tập còn lại 
cho phân hoạch khác U/A. Chẳng hạn ta có R = acde là rút gọn vì U/R = U/acde 
=U/A và U/cde ≠ U/A, U/ade ≠ U/A, U/ace ≠ U/A, U/acd ≠ U/A. 
Định nghĩa 8. Cho hệ thông tin S = (U, A), X  A . Trên tập đối tượng U xác định 
quan hệ IND(X) như sau: IND(X) = { (t, t’) U U: t.X = t’.X}. Quan hệ IND(X) 
được gọi là quan hệ bất khả phân biệt (hay quan hệ giống nhau) trên tập thuộc tính X của 
các đối tượng t và t’. 
Rõ ràng rằng quan hệ IND(X) là quan hệ tương đương trên U. Khi đó phân hoạch 
U/IND(X) ta sẽ ký hiệu là U/X và U/X = { [t]X: t U}. Trong đó [t]X = { t’ U: (t, t’) 
IND(X)} là lớp tương đương của đối tượng t. 
Định nghĩa 9. Cho hệ thông tin S = (U, A); X, Y  A. Nếu mỗi lớp tương đương của 
U/X là tập con của một lớp tương đương trong U/Y thì ta nói U/X mịn hơn U/Y và ký hiệu 
U/X U/Y. 
Bổ đề 2. Cho hệ thông tin S = (U, A), X  Y  A. Khi đó với mọi t U thì 
 a. [t]Y  [t]X 
 b. [t]X là hợp của một số lớp tương đương trong phân hoạch U/Y. Hay 
 [t]X =  [t’]Y (1) 
 c. IND(Y)  IND(X). 
 d. U/Y U/X. 
Chứng minh: 
a. Nếu X  Y  A thì [t]Y  [t]X. Thật vậy lấy t’ [t]Y => t.Y = t’.Y mặt khác theo 
giả thiết X nằm trong Y nên t.X = t’.X => t’ [t]X => [t]Y  [t]X đpcm. 
b. Để chứng minh mỗi lớp tương đương của U/X là hợp của một số lớp tương đương 
của U/Y ta giả sử rằng [t]X ={ t1, t2, ..., tk}, khi đó [t]X =[t1]X= [t2]X =...= [tk]X. Hiển nhiên 
rằng t1 [t1]Y, t2 [t2]Y,..., tk [tk]Y từ đây suy ra 
 [t]X = { t1, t2, ..., tk}  [t1]Y  [t2]Y  ...  [tk ]Y (*) 
 Mặt khác từ chứng minh phần a. ta lại có 
[t1]X  [t1]Y 
[t2]X  [t2]Y 
[t3]X  [t3]Y 
... 
[tk]X  [tk]Y 
Hợp hai vế ta có [t1]X  [t2]X ... [tk]X  [t1]Y  [t2]Y  ...  [tk]Y 
mà [t1]X  [t2]X  ...  [tk]X = [t]X nên [t]X  [t1]Y  [t2]Y  ...  [tk]Y (**) 
Từ (*) & (**) ta có [t]X = [t1]Y  [t2]Y  ...  [tk]Y đpcm. 
c. Chứng minh IND(Y)  IND(X): lấy (t, t’) IND(Y) => t.Y = t’.Y, mặt khác vì X 
 Y nên t.X = t’.X => (t, t’) IND(X) => IND(Y)  IND(X) đpcm. 
d. Chứng minh phần d suy từ phần a. 
Định nghĩa 10. Cho hệ thông tin S = (U, A); X, Y  A. 
164
U/X đư
{t9
ab) = U & POS(ab, abc) = {t
POS(R, D) = POS(C, D).
luôn có 
=t’.Y 
minh t 
2 ta l
t6}, {t
X ( hay X xác đ
thì t.Y = t’.Y. Khi 
S 
Vùng dương (positive region)
POS(X, Y) = 
Ví
, t10
Định nghĩa 11. 
Tập R 
Khi đó, R đư
Bổ đề 3.
và
Ch
Lấy t 
Để chứng minh t 
Lấy t’ 
Vì t.X = t’.X 
Suy ra POS(X, Y) 
Tương t
Th
ại có [t]
Ví d
U/a = {{ t
Vậy POS(a, b) = { t
U/ac = {{ t
Vậy POS(ac, bc) = {t
Suy ra POS(a, b) 
Định nghĩa 12. 
Định nghĩa 13. 
Tập Y đ
X 
ợc bao h
 dụ xét hệ thông tin trong Bảng 1 ta có U/ab = { { t
}} và U/abc = { { t
 POS(X, Y) 
ứng minh:
. T
ật vậy v
ụ xét hệ thống thông tin trong Bảng 1 
7}, {t

ừ t.Y
 POS(X, Y
8
k
N. B. Tư
 
 Cho h
POS(X, Y) ta ph
 [t]
ự ta chứng minh POS(X, Y) 
ì v
Y 
1, t
, t9
ư
 ( X
àm trong các nhóm c
C đư
ợc gọi l
XZ 
nên t’
= t’.Y & t.Z = t’.Z ta có t.YZ = t’.YZ => t’ 
ới mọi t thuộc POS(X, Y) th
 [t]
8, t9
1, t10
}, {t
ịnh phụ thuộc h
ợc gọi l
 )Y
ờng, N. B. Quảng, “Một số vấn đề về phụ thuộc h

Cho h
ệ thông tin S = (U, A). Khi đó với mọi bộ 3 tập thuộc tính X, Y, Z ta 
 POS(X, Y
=> t.XZ = t’.XZ => t.X = t’.X & t.Z = t’.Z.
\
Y\
, t10
 }, { t
10
Cho h
đó ta nói S th
Cho h
{[t]
ợc gọi l
 POS(XZ, YZ), ta ch

Z). 
Z => [t]
 }, { t
4
}}. 
 
Y n
X
1
ệ quyết định T = (U, C
à tập rút gọn miền d
 [t]
 POS(XZ, YZ) đpcm.
2
, t5
2}, {t
2} 
POS(ac, bc).
ệ thông tin S = (U, A ); X, Y 
ệ thông tin S = (U, A ); X, Y 
à 
ếu
}, {t
1
POS(X, Y) 
ải chứn
X m
X 
, t3, t
, t6 
 
ph
U/X: [t]
2}, {t
} 
à t
\Z) 
ặt khác v
 [t]
7 }, { t
}. 
3}, { t
{t3} 
àm Y) trong S, n
ỏa m
ụ thuộc h
 của X v
 {t
ập rút gọn của C
g minh t 
Y\
4

k(X
ủa U/Y. Hay
3}, {t
4, t5
Z => t 
4, t5
, t5
 { t
ãn ph
→Y) = 
à Y, ký hi
X 
, t6

ì t 

, t6 
, t6
4, t
Công ngh
 [t]
4, t
} 
ương.
 POS(XZ, YZ) 
ứng minh [t]
 POS(X, Y
 POS(X, Y
}} & U/b = {{ t
 }, {t
5, t
ụ thuộc h
àm đ
Y 
5, t6
 {t
 POS(XZ, YZ).
 POS(X, Y) nên [t]
ì [t]
ta có:
7}, {t
6 } 
Card
với [t]
}, {t
7} 

X 
{t
ếu với mọi cặp t, t’
ộ k(X→Y)
Card
ệ thông tin & C
ệu POS(X, Y) l
7}, {t
 {t
 D ); 
\Z). L
 
8, t
7} 
àm X 
(POS
Y 
8} = {t
nếu R l
XZ
[t]Y
\Z) đpcn.
1
9}} & U/bc = {{ t
 


(U
 U/Y}.
1}, {t
8}, {t
 
ấy t 
 m
, t2, t
{t8, t
 A. Ta nói Y ph
→ Y v
 A.
)
(X
1
 [t]
[t]YZ
ặt khác theo phần a. c
3 }, { t
9} = { t
 vào X trong S, ký hi
,Y
àm  rút g
2, t
9}, {t
, t4, t
à t
YZ
X 
. 
 POS(X, Y) ta ph
à ký hi
))
ơ s
à h
3}, {t
10
5, t
ập tối thiểu thỏa m
. 
 [t]
9, t
2
ở toán học cho tin học
ợp của các nhóm của 
4
}}. Khi đó POS(abc, 
6, t
Y 
10 }, { t
, t3
 U mà 
ệu: S 
, t5
7, t
=> t’
1, t2
, t4, t
ụ thuộc h
ọn 
, t6
8} 
4, t
}, {t
5, t
thu
}, {t
 [t]
5, t6
3 
6, t
t.X = t’.X
 X 
ộc tính.
7}, {t
Y 
ải chứng 
ủa bổ đề 
, t7, t
}, { t
7, t
àm vào 
→ Y.
=> t.Y 
8}}. 
4
8, t
”
8}, 
ãn 
(2)
, t5, 
9}.
ệu
(3)
Nghiên c
Tạp chí Nghi
t7, t
=> t, t’ 
ta đ
Vì POS(X, Y) = U nên v
t’.Y => S 
của phụ thuộc h
dàng
t.YZ = t’.YZ => S 
Thí d
8, t
Lưu 
Bổ đề 4. 
S 
Ch
- Đi
 Th
=> [t]
- Đi
 Th
Bổ đề 5.
S 
Ch
- Đi
ã ch
- 
Cho h
Tính ch
Ta luôn có S 
Ch
 
Tính ch
Nếu S 
Ch
 
Bây gi
Tính ch
Với mọi bộ ba các tập thuộc tính X, Y, Z, nếu S 
9}. Khi đó k(X→Y) = 
ý r
ứng minh:
ều kiện cần nếu S 
ật vậy lấy t’ 
ều kiện đủ nếu U/X 
ật vậ
ứng minh:
ều kiện cần giả sử S 
ứng minh với mọi t 
POS(X, Y) = 
Điều kiện đủ giả sử POS(X, Y) = U ta phải chứng minh S 
ứng minh:
t, t’ 
thấy rằng 
ứng minh:
t, t’ 
ứu khoa học công nghệ 
ụ xét hệ thông tin trong Bảng 1, đặt X = ac, Y = bc ta có POS(X, Y) = { t
ằng nếu k(X→Y) = 1 th
X → Y khi v
X 
 [t]
X → Y khi v
ệ 
ờ giả sử t.XZ = t’.XZ => t.X = t’.X & t.Z = t’.Z => t.Y =t’.Y & t.Z = t’.Z =>
ên c
Cho h
 [t]
y vì U/X 
X => t, t’ 
 Cho h
 X 
2. M
thông tin S = (U, A ); X, Y, Z, V 
ất 1.
 U n
ất 2. 
 X 
 U vì S 
ất 3. 
ứu KH&CN 
Y 
→ Y đpcm.
àm trong h
 Tính ph
 
Tính m
→ Y => S 
Tính B
ệ thông tin S = (U, A ); X, Y 
=> U/X 
ệ thông tin S = (U, A ); X, Y 
ỘT SỐ TÍNH CHẤT CỦA CÁC PHỤ THUỘC H
ếu t.X = t’.X => t.X = t’.X => S 
t, t’ 
à ch
 [t]
 U/Y nên m
à ch

 X 
X 
 XZ 
ỉ khi U/X 
X 
[t]Y
ỉ khi POS(X, Y) = U.
ới mọi t thuộc U ta luôn có [t]
ản xạ 
→ X. M
 U n
ở rộng hai vế
→ Y n
→ YZ đpcm.
ắc cầu
quân s
Card
 X 
=> t’.X = t.X và vì X 
 U/Y 
 => t.Y = t’.Y => S 
{[t]
ệ thông tin S = (U, A). 
ếu t.X = t’.X => t.Y = t’.Y => S 
→ Y &
U/Y ta s
 X 
 U thì [t]
X 
 XZ 
ự, Số
(
Card
POS
ì S 
ọi t 
→ Y ta ph
 U/X: [t]
ặt khác nếu Y 
→ YZ. Trong đó XZ = X 
ên t.X = t’.X => t.Y = t’.Y. 
 U/Y
ẽ chứng minh S 
 60, 4
)(
(
U
X
 t 
 U ta luôn có [t]
X 
,Y
X 
 [t]
X 
- 20
))
1
 U, ta s
ải chứng minh POS(X, Y) = U. Theo bổ đề 4 
Y. Suy ra
 [t]


19 
 = 
 
→ Y n
 X 
 
Y
 A. Sau đây chúng ta s
 X thì S 
10
8
 Y = S 
A. Khi đó
ẽ chứng minh [t]
→ Y.
A. Khi đó
 với [t]
X
 = 0.8 và ta có
ên t.Y = t’.Y => t’ 
X
X
 X 
→Y & S 
 X 
  
Y 
  
→ X. M
X 
→ Y. 
[t]Y
[t]Y
 X 
 

. L
U/Y}= U.
 => n
→ Y.
 X 
Z 
 S 
 
X
ấy t, t’ 
ếu t.X = t’.X th
ặt khác nếu Y 
→ Yđpcm.
Y 
 
→ Z => S 
X 
Y 
 [t]
ÀM
ẽ xét các tính chất 

Y. 
 [t]
 U 
2, t
0
Y
& t.X = t’.X 
 X 
3, t
 8.
 
 X 
165
4, t5
 Y
→ Y. 
ì t.Y = 
X. D
→ Z
, t6, 
ễ 
166
t’.X thì t.Y = t’.Y và vì S 
S 
tính ch
Tính ch
suy ra S 
ta có S 
ch
2 
Ch
Gi
Tính ch
Với mọi bộ bốn các tập thuộc tính X, Y, Z, V nếu S 
Ch
Vì S 
Với mọi bộ bốn các tập thuộc tính X, Y, Z, V nếu S 
Ch
Theo tính ch
Tính ch
Với mọi bộ bốn các tập thuộc tính X, Y, Z, V nếu S 
=> S 
Ch
Vì S 
ất 2 ta có S
Tính ch
Với m
=>
Ch
Theo tính ch
Theo gi
Theo gi
Theo tính ch
Theo tính ch
Bổ đề 6.
Ch
- Đi
Để chứng minh U/X = U/XY ta sẽ chứng minh 
 t 
Theo tính ch
Theo b
Vậy 
- Đi
ứng minh:
ả sử t.X = t’.X ta phải chứng minh t.Z = t’.Z. Thật vậ
X → Z đpcm.
ứng minh:
ất 3 ta có S 
ứng minh:
ứng minh:
 S 
ứng minh: 
ứng minh:
ều kiện cần giả sử S 
U ta có

ều kiện đủ giả sử U/X = U/XY.
ất 5. 
XZ 
X 
ọi bộ bốn tập thuộc tính X, Y, Z, V nếu S 
ả thiết ta có 
ả thiết ta có 
ổ đề 3 ta có [t]
 t 
N. B. Tư
ất 4. 
X → Y n
XZ 
→ Y
ất 6. 
XZ 
→ Y n
ất 7. 
X → XYZV
 Cho h
S 
 U [t]
Tính t
Tính m
ất 1 ta có S 
→ Y v
 Tính c
→ YV
Tính Tích l
ất 1 ta có 
ất 3
ất 6 cộng hai vế của (*) & (**)
 [t]
ất cộng hai vế (tính chất 6) ta có
ờng, N. B. Quảng, “Một số vấn đề về phụ thuộc h
\V đpcm.
YZ
 ta có 
ệ thông tin S = (U, A ); X, Y 
X → Y khi v
XY 
X
ựa bắc cầu
ên theo tính ch
XZ 
ở rộng trái, thu hẹp 
à ti
ên theo tính ch
 → YV theo tính ch
 [t]
S 
S 
S 
 = [t]
→ V đpcm. 
ếp tục theo tính chất 1 ta lại có S 
ộng đầy đủ 
X, M
 X 
 X 
 X 
X 
XY
ũy
→ Y
→ X
→ XY
 [t]
 => U/X = U/XY.
XZ 
à ch
 X 
ặt khác theo giả thiết & tính phản xạ của phụ thuộc h
XY
→ X, theo gi
ất 2 ta có S 
S 
S 
S 
S 
ỉ khi U/X = U/XY 
→ Y, ta ch
. 
 Y 
ất 2 ta có S 
 X 
 X 
 Y 
 X 
→ Z n
ất 3 ta có S 
→ X (*)
→ Y (**)
→ ZV
→ ZV (***) 
Công ngh
ph
ứng minh U/X = U/XY.
ải
 & (***) ta có S 
ả thiết ta có S 
XZ 
 
ệ thông tin & C
ên n
X 
XZ 
→ YZ, v
A. Khi đó
 t
ếu t.Y = t’.Y th
→Y & S 
→ YZ v
XZ 
 U, 
y vì S 
X→
X→Y &
→ YV đpcm.
[t]
Y =>S 
Y 
ì S
 X 
X 
àm  rút g
YZ 
à vì S
→ Y
→ Y &
=[t]
ơ s
 X 
X 
\
 S 
X → XYZV đpcm.
XY. 
ở toán học cho tin học
→ Y n
→ V => S 
→ Y theo tính ch
V => theo tính ch
Z 
Z 
 Th
ì t.Z = t’.Z => 
YZ 
XZ 
→ V 
→ V n
ật vậy theo bổ đề 
ọn 
→ V n
→ Y 
S 
thu
ên n
ên theo tính 
Y 
ộc tính.
ếu t.X = 
XZ 
ên theo 
\ V
→ ZV 
àm ta có
→ V.
ất 3 
ất 3 
”
Nghiên c
Tạp chí Nghi
[t]
Y. Tuy nhiên trong r
X 
mãn X 
card(POS(XZ, YZ))/Card(U) 
YZ ch
3. RÚT G
thu
độ phụ thuộc, độ quan trọng của thuộc tính dựa tr
heuris
tính quy
Vì U/X = U/XY nên 
XY 
Trong đ
→ Y m
Gọi T = (
Định nghĩa 14. 
Chúng ta g
Rõ ràng r
Định lý 1.
Ch
Để chứng minh (2) ta sẽ tính U
Dễ thấy rằng nếu [t]
Từ đây suy ra 
Từ chứng minh của định lý 1 ta có thuật toán tính độ chắc chắn c(X → Y).
Thu
Input H
Output c( X 
Algorithm
1.
2.
3.
4.
Định nghĩa 15. 
Chúng ta nói ph
Bổ đề 7.
Ch
Theo b
Tron
ộc từ Định nghĩa 14. Ph
Định nghĩa 16. 
= [t’]
→ Y. Nói cách khác T 
ứng minh: 
ật toán 1.
ứng minh:
ắc chắn trong S đpcm. 
g ph
tic tìm t
ứu khoa học công nghệ 
XY
à ch
UT: = 
Tính U/X, U/Y
For each t 
c( X 
ổ đề 3 ta có POS(X,Y) 
ỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH SỬ DỤNG ĐỘ PHỤ THUỘC 
ết định D v
ên c
 => [t]
ịnh nghĩa 12 ở tr
ỉ S’ con của S thoả m
U
ọi 
ằng 0 
 Cho h
ệ thông tin S = (U, A) & X, Y 
→ Y): = 
 N
ần n
ập rút gọn dựa tr
ứu KH&CN 
T, A) là h
đ
c( X 
k(X 
U
→ Y)
∅ 
ếu X → Y chắc chắn trong S th
ày, chúng tôi xây d
X
Cho h
ộ chắc chắn
ệ thông tin S = (U, A ); X, Y 
T = 
c(X
 Tính 
Cho h
ụ thuộc h
[2] Cho h
ào t
[t]Y
→ Y) = 
 c( X 
→ Y) = c(X → Y). 
X 

→Y)=card(U
 U if [t]
|
U
ập thuộc tính điều kiện C đ
 = [t’]
ất nhiều tr
ệ thông tin con cực đại (chứa nhiều bộ nhất) của S = (U, A) thỏa 
ệ thông tin S = (U, A ); X, Y 

 ( X 
U
T
ệ thông tin S = (U, A ); X, Y
quân s
 
ên chúng ta đ
→ Y) 
 [t]
{ [t]
X 
|
àm X 
ương pháp bao g
t 
X[t’]
 của phụ thuộc h
U|
U
Y thì [t]
X: [t]
→ Y).

≥ card(POS(X, Y))/card(U) = c(X → Y) ≥ minc => XZ → 
ên đ
ệ quyết định T = (U, C
ự, Số
 U 
Y
ãn ph
 X 
|
T
. 
 1 và n
T. Gi
T
 [t]
→ Y 

ộ quan trọng của thuộc tính.
 => [t]
ư
→ Y
X 
X 
)/card(U)=card(POS(X,Y))/card(U)=k(X
Y then U
 POS(XZ, YZ) và theo đ
ựng ph
 60, 4
[t]
ã nêu 
ờng hợp S không thỏa m
ụ thuộc h
ếu 
ả sử U/X = {[t]
 U
 [t]
ch
X 
Y = [t’]
c
T. Như v
Y 

T
ắc chắn trong S 
ương pháp rút g
- 20
= [t]
đ
àm X 
( X 
với [t]
 A.
 = U
ì XZ 
ồm các b
19 
XY
Y 
ịnh nghĩa S thỏa m
àm X 
(4)
→ Y) = 1 th

(5)
T 
ư
 =>
= > S 
→ Y trong S l
 A. Khi đó ta có 
ậy 
Y 
[t]
→ YZ ch
ên đ
ợc định nghĩa

→ Y. 

X: t
 U/Y } = POS(X, Y)
X 
 
ước: định nghĩa tập rút gọn dựa tr
ộ phụ thuộc v

t, t’
 A. 
 U}; U/Y={ [t]
A. Cho ngư
n
 D ), đ
X → Y
ì S 
ếu c(X → Y) 
ắc chắn trong S.
ịnh lý 1 ta có c(XZ → YZ) = 
ọn thuộc tính sử dụng độ phụ 
 U n
ộ phụ thuộc của tập thuộc 
ãn ph
à 
 X 
ỡng minc 
ếu [t]
ãn ph
→ Y. 
à đ
ụ thuộc h
Y: t 
≥ 
ề xuất thuật toán 
X
ụ thuộc h
→Y).
minc.
 = [t’]
 U}.
àm X 
[0, 1].
167
X 
=> 
→ 
àm 
ên 
Công nghệ thông tin & Cơ sở toán học cho tin học 
N. B. Tường, N. B. Quảng, “Một số vấn đề về phụ thuộc hàm  rút gọn thuộc tính.” 168 
 ,
C
POS C D
D
U
 
Theo Định nghĩa 14, dễ thấy rằng C D k C D c C D 
Định nghĩa 17. Cho hệ quyết định ,T U C D  , tập thuộc tính R C được gọi là 
tập rút gọn của C nếu thỏa mãn 
1) R CD D  
2)  , CR rr R D D   
Dễ thấy rằng, tập rút gọn bởi Định nghĩa 17 tương đương với tập rút gọn miền dương 
bởi Định nghĩa 14. 
Định nghĩa 18. Cho bảng quyết định ,T U C D  với B C và b C B . Độ 
quan trọng của thuộc tính b đối với B được định nghĩa bởi 
  B BB bSIG b D D  
Dễ thấy rằng 0BSIG b . Độ quan trọng BSIG b đặc trưng cho chất lượng phân 
lớp của thuộc tính b đối với tập thuộc tính quyết định D và được sử dụng làm tiêu chuẩn 
lựa chọn thuộc tính cho thuật toán heuristic tìm tập rút gọn. 
Phần tiếp theo, chúng tôi trình bày thuật toán heuristic tìm một tập rút gọn. Ý tưởng 
của thuật toán là xuất phát từ tập rỗng :R  , lần lượt bổ sung vào R các thuộc tính có 
độ quan trọng lớn nhất cho đến khi tìm được tập rút gọn. 
Thuật toán ADAR (Attribute Dependency based Attribute Reduction). Thuật toán 
heuristic tìm một tập rút gọn sử dụng độ phụ thuộc. 
Đầu vào: Bảng quyết định ,T U C D  
Đầu ra: Một tập rút gọn R . 
1. :R  ; 
// Thêm dần vào R các thuộc tính có độ quan trọng lớn nhất 
2. While R CD D  do 
3. Begin 
4. Với mỗi a C R tính  R RR aSIG a D D  ; 
5. Chọn ma C R sao cho R m R
a C R
SIG a Max SIG a
 ; 
6. 
 : mR R a 
; 
7. End; 
 // Loại bỏ các thuộc tính dư thừa trong R nếu có 
8. Với mỗi a R 
9. Begin 
10. Tính 
  R a D ; 
11. If 
  CR a D D  then :R R a ; 
12. End; 
13. Return R; 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 60, 4 - 2019 169
Giả sử D d , dễ thấy độ phức tạp thời gian của thuật toán ADAR là 2 2O C U 
với C là số thuộc tính điều kiện, U là số đối tượng. 
4. KẾT LUẬN 
Chúng tôi đã giới thiệu một số nghiên cứu, tính chất đặc biệt, hữu ích, có tính hệ thống, 
cơ bản của các khái niệm liên quan đến hệ thông tin S =(U, A), phụ thuộc hàm, phụ thuộc 
hàm xấp xỉ, độ chắc chắn của phụ thuộc hàm dựa trên nền lý thuyết tập thô. Đặc biệt trong 
bài viết chúng tôi đã tự nêu và chứng minh chặt chẽ một định lý, 7 bổ đề và 7 tính chất của 
khái niệm phụ thuộc hàm trong hệ thông tin. Trong bài viết chúng tôi cũng đã nêu một thuật 
toán tìm độ chắc chắn của phụ thuộc hàm. Chúng tôi nghiên cứu về vùng dương, ràng buộc 
của các tập thuộc tính trong hệ tin, hệ quyết định, trên cơ sở đó xây dựng một thuật toán 
heuristic tìm tập rút gọn của bảng quyết định sử dụng độ phụ thuộc của thuộc tính. 
TÀI LIỆU THAM KHẢO 
[1] Chen, D., Cui, D., Wang, C., Wang, Z. "A Rough Set-Based Hierarchical clustering 
Algorithm for categorical Data". International Journal of Information Technology, 
Vol. 12, No.3, 2006, pp 149-159. 
[2] Han, J., Hu,X., Lin, T.Y. "Feature Subset Selection Based on Relative Dependency 
between Attributes". Rough Sets and Current Trends in Computing 2004, pp 176-185. 
[3] Yan-Yong Guan, Hong-Kai Wang. "Set-value information systems". Information 
Science, vol 176, 2006, pp 2507-2525. 
[4] Z. Pawlak (1991). "Rough sets: theoretical aspect of reasoning about data". 
[5] Nguyễn Bá Tường. "Cơ sở dữ liệu quan hệ và ứng dụng". Nhà xuất bản Thông Tin và 
Truyền Thông, 2011. 
ABSTRACT 
FUNCTIONAL DEPENDENCIES AND APPROXIMATE FUNCTIONAL 
DEPENDENCIES IN ROUGH SETS THEORY AND APPLICATION IN 
ATTRIBUTE REDUCTION PROBLEM. 
In this paper, we present some concepts and properties related to the S = (U, A) 
information system, dependence, approximation, positive region in the set theory. 
On this basis, the basis for further study of the properties of the positive region, the 
constraints between attributes and, in particular, between the conditional properties 
in the decision system are the premise of the algorithms. Finally, we propose a 
dependency based attribute reduction algorithm in decision tables. 
Keywords: Partition; Relation; Approximation; Rough sets; Functional dependency; Dependency 
approximation; Reduct. 
Nhận bài ngày 30 tháng 11năm 2018 
Hoàn thiện ngày 24 tháng 3 năm 2019 
Chấp nhận đăng ngày 16 tháng 4 năm 2019 
Địa chỉ: 1 Đại học SP kỹ thuật Hưng Yên; 
2 Đại học Kiến trúc Hà Nội. 
* Email: quangnb1@gmail.com.