Một số kết quả về hàm chọn

TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, Trường Đại học Khoa học, ĐH Huế Tập 13, Số 1 (2018)
 MỘT SỐ KẾT QUẢ VỀ HÀM CHỌN
 TÓM TẮT
 Hàm chọn xuất hiện nhiều trong các lĩnh vực của toán, toán ứng dụng và khoa 
 học máy tính. Bài báo này nghiên cứu một số tính chất mới của hàm chọn đặc 
 biệt cũng như tính đóng của lớp hàm chọn đặc biệt đối với phép toán hội và một 
 số vấn đề liên quan.
 Từ khóa: hàm chọn, toán tử bao đóng, phụ thuộc hàm.
1 MỞ ĐẦU
Chúng ta đã biết hàm chọn xuất hiện nhiều trong các lĩnh vực của toán ứng dụng và khoa
học máy tính (chẳng hạn xem [2, 4, 5, 7]). Các mô tả tương đương của phụ thuộc hàm đã
được nghiên cứu từ khá lâu [3, 4, 6, 7]. Hàm chọn và toán tử bao đóng là hai trong số các
mô tả tương đương đó. Các mô tả tương đương này chính là các toán tử thiết lập tương
ứng giữa các tập con của một tập hữu hạn cho trước thỏa mãn một số tiên đề. Nhiều kết
quả quan trọng của phụ thuộc hàm đã thu được từ hàm chọn và toán tử bao đóng. Ngoài
ra, bản thân hàm chọn và toán tử bao đóng cũng được xem như các công cụ toán học để
phát triển một số kết quả trong các lĩnh vực khác như cơ sở dữ liệu, khai phá dữ liệu, tập
thô, tập mờ, lý thuyết quyết định, ...
 Mục đích chính của bài báo là nghiên cứu một số đặc trưng cơ bản của hàm chọn để
làm sáng tỏ thêm cấu trúc đại số của nó. Với cách tiếp cận như vậy bài báo được tổ chức
thành 5 mục. Sau mở đầu, Mục 2 trình bày một số khái niệm và kết quả cơ sở của toán
tử bao đóng, hàm chọn và hàm chọn đặc biệt. Mục 3 tìm hiểu thêm một số tính chất thú
vị của hàm chọn đặc biệt. Tính đóng của lớp hàm chọn đặc biệt đối với phép toán đại số
như hội, hợp thành và một số vấn đề liên quan được nghiên cứu trong Mục 4. Cuối cùng
là kết luận.
2 ĐỊNH NGHĨA
Mục này giới thiệu khái niệm toán tử bao đóng, hàm chọn và hàm chọn đặc biệt. Các khái
niệm và kết quả trong mục này có thể tìm thấy trong [2, 4, 6, 7, 8].
 Xét một tập hữu hạn bất kỳ U. Ánh xạ c : P(U) → P(U) được gọi là hàm chọn trên U
nếu với mọi X ∈ P(U) ta có c(X) ⊆ X.
Ví dụ 2.1. Các ánh xạ sau là các hàm chọn cơ bản:
 (1) Ánh xạ rỗng e : P(U) → P(U) xác định bởi e(X) = ∅, với mọi X ⊆ U.
 (2) Ánh xạ đồng nhất i : P(U) → P(U) xác định bởi i(X) = X, với mọi X ⊆ U.
 T P → P T \
 (3) Ánh xạ b1 : (U) (U) xác định bởi b1 (X) = X T , với T là một tập con cố
định cho trước của U và với mọi X ⊆ U.
 13
 T P → P T ∩
 (4) Ánh xạ b2 : (U) (U) xác định bởi b2 (X) = X T , với T là một tập con cố
định cho trước của U và với mọi X ⊆ U.
Nhận xét 2.1. Rõ ràng ta thấy:
 ∅ T T
 (1) Nếu T = thì b1 = i và b2 = e.
 T T
 (2) Nếu T = U thì b1 = e và b2 = i.
 Ánh xạ f:P(U) −→ P(U) thỏa các tính chất sau:
 (C1) X ⊆ f(X),
 (C2) nếu X ⊆ Y thì f(X) ⊆ f(Y ),
 (C3) f(f(X)) = f(X),
với mọi X, Y ⊆ U, được gọi là toán tử bao đóng (TTBĐ) trên U. Ký hiệu Cl(U) là tập tất cả
các TTBĐ trên U.
 Bây giờ ta xét TTBĐ f ∈ Cl(U). Từ f, chúng ta xây dựng ánh xạ cf : P(U) → P(U)
như sau:
 cf (X) = U \ f(U \ X) (1)
với mọi X ⊆ Y . Dễ thấy cf là một hàm chọn. Lúc này, chúng ta có mối tương quan quan
trọng sau giữa TTBĐ và hàm chọn.
Định lý 2.1 ([4]). Mối quan hệ (1) là tương ứng 1-1 giữa các TTBĐ với các hàm chọn thỏa hai
điều kiện:
 (H1) nếu cf (X) ⊆ Y ⊆ X thì cf (X) = cf (Y ),
 (H2) nếu X ⊆ Y thì cf (X) ⊆ cf (Y ),
với mọi X, Y ⊆ U.
 Người ta gọi các hàm chọn thỏa hai điều kiện (H1) và (H2) là các hàm chọn đặc biệt
(HCĐB). Ký hiệu Ch(U) là tập tất cả các HCĐB trên U.
 Như vậy, từ Định lý 2.1 chúng ta thấy có một tương ứng 1-1 giữa lớp các HCĐB và
lớp các TTBĐ. Mặt khác, chúng ta đã biết TTBĐ là một mô tả tương đương của phụ thuộc
hàm [2]. Do đó, HCĐB cũng là một mô tả tương đương của phụ thuộc hàm. Điều này có
nghĩa, để nghiên cứu và phân tích các đặc trưng logic của phụ thuộc hàm chúng ta có thể
dùng công cụ HCĐB.
 T T
Ví dụ 2.2. Dễ kiểm chứng được các hàm chọn cơ bản e, i, b1 , b2 là các HCĐB.
3 TÍNH CHẤT CỦA HÀM CHỌN ĐẶC BIỆT
Mục này tìm hiểu một số tính chất của HCĐB. Đầu tiên chúng ta có kết quả cơ sở sau đây.
Mệnh đề 3.1 ([6]). Nếu c ∈ Ch(U) thì c(c(X)) = c(X) với mọi X ⊆ U.
 Hàm chọn đặc biệt cũng có thêm một số tính chất thú vị nữa.
Mệnh đề 3.2. Cho c ∈ Ch(U). Khi đó, với mọi X, Y ⊆ U ta có
 (1) c(X ∪ Y ) ⊇ c(X) ∪ c(Y ).
 (2) c(X ∩ Y ) ⊆ c(X) ∩ c(Y ).
 (3) c(c(X) ∩ Y ) = c(X ∩ c(Y )) = c(X ∩ Y ).
 14
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, Trường Đại học Khoa học, ĐH Huế Tập 13, Số 1 (2018)
Chứng minh. (1) Theo (H2), chúng ta có c(X ∪ Y ) ⊇ c(X) và c(X ∪ Y ) ⊇ c(Y ). Do vậy,
c(X ∪ Y ) ⊇ c(X) ∪ c(Y ).
 (2) Lập luận tương tự (1), chúng ta cũng có c(X ∩ Y ) ⊆ c(X) và c(X ∩ Y ) ⊆ c(Y ). Suy
ra c(X ∩ Y ) ⊆ c(X) ∩ c(Y ).
 (3) Chúng ta chỉ cần chứng minh c(c(X) ∩ Y ) = c(X ∩ Y ), sau đó hoán đổi vai trò của
X và Y ta sẽ thu được (3).
 Theo (H2) và định nghĩa hàm chọn, chúng ta có c(X ∩ Y ) ⊆ c(X) và c(X ∩ Y ) ⊆
c(Y ) ⊆ Y . Do đó, c(X ∩ Y ) ⊆ c(X) ∩ Y . Mặt khác, c(X) ∩ Y ⊆ X ∩ Y . Như vậy, chúng ta
thu được
 c(X ∩ Y ) ⊆ c(X) ∩ Y ⊆ X ∩ Y.
 Áp dụng (H1), suy ra c(c(X) ∩ Y ) = c(X ∩ Y ).
 Các bao hàm thức ngược lại trong các tính chất (1) và (2) của Mệnh đề 3.2 là không
đúng. Ta xét các phản ví dụ sau.
Ví dụ 3.1. Cho tập U = {a, b}. Chúng ta định nghĩa ánh xạ ca : P(U) → P(U) như sau:
với mọi X ⊆ U {
 ∅ nếu a ̸∈ X
 ca(X) =
 X ngược lại.
 Dễ kiểm chứng được ca ∈ Ch(U).
 Bây giờ ta xét X = {a} và Y = {b}. Khi đó chúng ta có:
 ca(X) = X
 ca(Y ) = ∅
 ca(X ∪ Y ) = U.
 Suy ra ca(X ∪ Y ) ≠ ca(X) ∪ ca(Y ). Điều này có nghĩa bao hàm thức ngược lại của tính
chất (1) trong Mệnh đề 3.2 không đúng.
 U U
Ví dụ 3.2. Cho tập U = {a, b, c}. Xét ánh xạ cb : 2 → 2 xác định bởi:
 {
 ∅ nếu X = {b}
 cb(X) =
 X ngược lại.
 Dễ kiểm chứng được cb ∈ Ch(U).
 Với X = {a, b} và Y = {b, c}, chúng ta thu được:
 cb(X) = X
 cb(Y ) = Y
 cb(X ∩ Y ) = ∅.
 Do đó cb(X ∩ Y ) ≠ cb(X) ∩ cb(Y ). Như vậy bao hàm thức ngược lại của tính chất (2)
trong Mệnh đề 3.2 cũng không đúng.
 Bây giờ, xét HCĐB c ∈ Ch(U). Ký hiệu F ix(c) = {X ⊆ U : c(X) =X}. Ta gọi các phần
tử trong F ix(c) là các điểm bất động của c. Dễ thấy F ix(c) chứa ∅ như là phần tử nhỏ nhất.
Mệnh đề 3.3. Cho c ∈ Ch(U). Nếu X, Y ∈ F ix(c), thì
 c(X ∪ Y ) = c(X) ∪ c(Y ).
 15
Chứng minh. Giả sử X, Y ∈ F ix(c). Theo định nghĩa hàm chọn, ta có
 c(X ∪ Y ) ⊆ X ∪ Y
 = c(X) ∪ c(Y ).
 Mặt khác, theo Mệnh đề 3.2 ta cũng có thêm:
 c(X ∪ Y ) ⊇ c(X) ∪ c(Y ).
Hệ quả 3.1.
 1) ∅ ∈ F ix(c).
 2) X, Y ∈ F ix(c) ⇒ X ∪ Y ∈ F ix(c).
 Như vậy, tập tất cả điểm bất động của HCĐB là đóng đối với phép toán hợp.
4 TÍNH ĐÓNG VÀ MỘT SỐ VẤN ĐỀ LIÊN QUAN CỦA HÀM CHỌN ĐẶC BIỆT
Ký hiệu Ma(U) là tập tất cả các ánh xạ P(U) → P(U). Chúng ta xét các ánh xạ f1, f2, g, h, k ∈
Ma(U). Các ánh xạ g, h và k xác định như sau:
 g(X) = f1(X) ∩ f2(X),
 h(X) = f1(X) ∪ f2(X),
 k(X) = f1(f2(X)),
với mọi X ⊆ U, tương ứng được gọi là hội, tuyển và hợp thành của f1, f2 và lần lượt được
ký hiệu là g = f1 ∧ f2, h = f1 ∨ f2 và k = f1f2.
 Bây giờ xét U1,U2 là hai tập hữu hạn phân biệt và hai ánh xạ f1 ∈ Ma(U1), f2 ∈
Ma(U2). Ánh xạ l : P(U1 ∪ U2) → P(U1 ∪ U2) xác định bởi l(X) = f1(X ∩ U1) ∪ f2(X ∩ U2)
với mọi X ⊆ U1 ∪ U2 được gọi là tích trực tiếp của f1 và f2, ký hiệu là l = f1 × f2.
 Lớp HCĐB là đóng đối với phép toán tuyển và tích trực tiếp, không đóng đối với phép
toán hợp thành [7]. Điều kiện cần và đủ để lớp HCĐB đóng đối với phép toán hợp thành
cũng được chỉ ra trong [7]. Tuy nhiên, trong [7] (Bổ đề 3.7) người ta khẳng định thêm lớp
HCĐB là đóng đối với phép toán hội bằng cách sử dụng công cụ TTBĐ. Trong kết quả
sau, bài báo khẳng định kết quả đó không đúng.
Mệnh đề 4.1. Hội hai HCĐB là một hàm chọn thỏa (H2) nhưng không thỏa (H1).
Chứng minh. Giả sử c1, c2 ∈ Ch(U). Suy ra c1(X) ∩ c2(X) ⊆ X với mọi X ⊆ U. Do đó,
c1 ∧ c2 là một hàm chọn trên U.
 Mặt khác với X ⊆ Y ⊆ U, chúng ta có c1(X) ⊆ c1(Y ) và c2(X) ⊆ c2(Y ). Nên c1(X) ∩
c2(X) ⊆ c1(Y ) ∩ c2(Y ), nghĩa là hàm c1 ∧ c2 thỏa (H2).
 Bây giờ, chúng ta xây dựng một phản ví dụ như sau: với U = {a, b} và hai ánh xạ
ba, ca : P(U) → P(U) xác định bởi:
 ba(X) = X \{a}
 và {
 ∅ nếu a ̸∈ X
 ca(X) =
 X ngược lại
 16
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, Trường Đại học Khoa học, ĐH Huế Tập 13, Số 1 (2018)
 với mọi X ⊆ U. Dễ kiểm chứng được ba, ca ∈ Ch(U).
 Lúc này
 ba ∧ ca(U) = ba(U) ∩ ca(U) = {b}
 ba ∧ ca({b}) = ba({b}) ∩ ca({b}) = ∅.
 Suy ra ba ∧ ca({b}) ≠ ba ∧ ca(U).
 Như vậy, chúng ta có ba ∧ ca(U) ⊆ {b} ⊆ U nhưng ba ∧ ca({b}) ≠ ba ∧ ca(U). Điều này
có nghĩa ba ∧ ca không thỏa (H1).
 Vậy, c1 ∧ c2 không thỏa (H1).
 Để ý thêm hai HCĐB ba và ca trong phản ví dụ của chứng minh Mệnh đề 4.1 cũng
khẳng định hợp thành của hai HCĐB không có tính giao hoán và không thỏa (H1), do đó
không phải là một HCĐB:
 baca(U) = ba(ca(U)) = {b}
 baca({b}) = ba(ca({b}) = ∅
 caba(U) = ca(ba(U) = ∅.
 Suy ra baca(U) ≠ caba(U), và do đó baca ≠ caba. Ngoài ra, baca({b}) ≠ baca(U). Nên,
với baca(U) ⊆ {b} ⊆ U nhưng baca({b}) ≠ baca(U). Nghĩa là, baca không thỏa (H1).
 Trường hợp, hợp thành hai HCĐB có tính giao hoán khi và chỉ khi nó là một HCĐB
[6].
 Bây giờ, tiếp theo chúng ta tìm hiểu một số tính chất của phép toán hội, hợp thành và
mối tương quan giữa chúng. Xét hai ánh xạ f1, f2 ∈ Ma(U). Ta nói f1 hẹp hơn f2, ký hiệu
f1 ≤ f2, nếu f1(X) ⊆ f2(X) với mọi X⊆U.
 Có thể thấy ngay quan hệ hẹp hơn là một quan hệ thứ tự trên Ma(U). Dễ kiểm chứng,
trên Ma(U) phép toán hội và tuyển có tính phân phối phải (nhưng không phân phối trái)
đối với phép toán hợp thành. Từ định nghĩa quan hệ hẹp hơn, chúng ta dễ dàng rút ra
ngay một điều kiện đủ để lớp HCĐB là đóng đối với phép toán hội là: với mọi HCĐB
c1, c2 ∈ Ch(U), nếu c1 ≤ c2 hoặc c2 ≤ c1, thì c1 ∧ c2 ∈ Ch(U).
Mệnh đề 4.2. Nếu c1 ∈ Ch(U) và c2 là một hàm chọn, thì
 c1c2 = c1 ⇔ c1 ≤ c2.
Chứng minh. Giả sử c1c2 = c1. Vì c1 ∈ Ch(U), nên c1c2(X) ⊆ c2(X) với mọi X ⊆ U, và
do đó c1(X) ⊆ c2(X) với mọi X ⊆ U.
 Ngược lại, giả sử c1 ≤ c2. Vì c2 là một hàm chọn, suy ra c1(X) ⊆ c2(X) ⊆ X với mọi
X ⊆ U. Vận dụng (H1) đối với c1, chúng ta thu được c1c2(X) = c1(X) với mọi X ⊆ U.
Bỏ đề 4.1. Với mọi ánh xạ f1, f2 ∈ Ma(U) và c ∈ Ch(U) ta có
 (1) c(f1 ∧ f2) ≤ cf1 ∧ cf2.
 (2) c(f1 ∨ f2) ≥ cf1 ∧ cf2.
Chứng minh. (1) Theo định nghĩa phép toán hội và Mệnh đề 3.2, với mọi X ⊆ U ta có
 c(f1 ∧ f2)(X) = c(f1(X) ∩ f2(X))
 ⊆ c(f1(X)) ∩ c(f2(X))
 = cf1 ∧ cf2(X).
 Suy ra, c(f1 ∧ f2) ≤ cf1 ∧ cf2.
 17
 (2) Lập luận tương tự như (1), chúng ta cũng có
 c(f1 ∨ f2)(X) = c(f1(X) ∪ f2(X))
 ⊇ c(f1(X)) ∩ c(f2(X))
 = cf1 ∧ cf2(X).
 Do đó, c(f1 ∨ f2) ≥ cf1 ∨ cf2
Bỏ đề 4.2. Nếu c1, c2 ∈ Ch(U), thì c1c2 ≤ c1 ∧ c2.
Chứng minh. Vì c1, c2 ∈ Ch(U), nên c2(X) ⊆ X, và do đó c1(c2(X)) ⊆ c1(X), với mọi
X ⊆ U. Hơn nữa, c1(c2(X))⊆c2(X) với mọi X ⊆ U. Như vậy, c1c2(X) ⊆ c1 ∧ c2(X) với
mọi X ⊆ U.
Bỏ đề 4.3. Cho c1, c2 ∈ Ch(U). Nếu c1c2 có tính giao hoán, thì
 (c1 ∧ c2)(c1 ∧ c2) = c1c2.
Chứng minh. Theo Mệnh đề 3.1, Bổ đề 4.1, Bổ đề 4.2 và tính phân phối phải của phép hội
đối với phép hợp thành ta có:
 (c1 ∧ c2)(c1 ∧ c2) = c1(c1 ∧ c2) ∧ c2(c1 ∧ c2)
 ≤ (c1c1 ∧ c1c2) ∧ (c2c1 ∧ c2c2)
 = (c1 ∧ c1c2) ∧ (c2c1 ∧ c2)
 = c1c2 ∧ c2c1
 = c1c2.
 Hơn nữa, theo Bổ đề 4.2, c1c2 ≤ c1 ∧ c2. Bởi định nghĩa quan hệ nhỏ hơn, suy ra
(c1c2)(c1c2) ≤ (c1 ∧c2)(c1c2). Cũng từ c1c2 ≤ c1 ∧c2 và Mệnh đề 4.1, suy ra (c1 ∧c2)(c1c2) ≤
(c1 ∧ c2)(c1 ∧ c2). Như vậy, chúng ta thu được (c1c2)(c1c2) ≤ (c1 ∧ c2)(c1 ∧ c2). Cuối cùng,
vì c1c2 có tính giao hoán, nên c1c2 ∈ Ch(U) [6]. Do vậy, c1c2 ≤ (c1 ∧ c2)(c1 ∧ c2). Điều này
có nghĩa (c1 ∧ c2)(c1 ∧ c2) = c1c2.
 Từ các kết quả cơ sở trên, chúng ta rút ra được mối tương quan sau giữa phép toán
hội và phép toán hợp thành.
Mệnh đề 4.3. Cho c1, c2 ∈ Ch(U) và c1c2 có tính giao hoán. Nếu c1 ∧c2 ∈ Ch(U), thì c1 ∧c2 =
c1c2.
Chứng minh. Giả sử c1 ∧ c2 ∈ Ch(U). Theo Mệnh đề 3.1 và Bổ đề 4.3, chúng ta thu được:
 c1c2 = (c1 ∧ c2)(c1 ∧ c2)
 = c1 ∧ c2.
5 KẾT LUẬN
Đầu tiên bài báo nghiên cứu một số tính chất thú vị của HCĐB. Sau đó tính đóng của lớp
HCĐB đối với phép toán hội cũng được tìm hiểu. Cuối cùng một số tính chất của phép
toán hội, hợp thành trên lớp các HCĐB cũng được nghiên cứu trong bài báo.
 18
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, Trường Đại học Khoa học, ĐH Huế Tập 13, Số 1 (2018)
 TÀI LIỆU THAM KHẢO
 [1] Armstrong W. W. (1974), Dependency structures of database relationships,
 Information processing 74, pp. 580-583.
 [2] Danilov V., Koshevoy G. (2009), Choice functions and extensive operators, Order, 26, pp.
 69-94.
 [3] Demetrovics J., Furedi Z., Katona G.O.H. (1985), Minimum matrix representation of closure
 operations, Discrete Applied Mathematics 11, pp. 115-128.
 [4] Demetrovics J., Hencsey G., Libkin L., Muchnik I. (1992), On the interaction between closure
 operations and choice functions with applications to relational databases, Acta Cybernetica 10,
 pp. 129-139.
 [5] Moulin H. (1985), Choice functions over a finite set: A summary, Soc. Choice Welf. 2, pp.
 147-160.
 [6] Vu Duc Nghia, Bina Ramamurthy (2002), Properties of composite of closure
 operations and choice functions, Acta Cybernetica 15, pp. 457-465.
 [7] Vu Duc Nghia (2004), Relationships between closure operations and choice functions
 equivalent descriptions of a family of functional dependencies, Acta Cybernetica 16, pp.
 485-506.
 [8] Nguyen Hoang Son, Vu Duc Thi (2018), Some the combinatorial characteristics of closure
 operations, Algebra and Discrete Mathematics, Accepted.
 SOME RESULTS ABOUT CHOICE FUNCTION
 Nguyen Hoang Son
 Department of Mathematics, University of Sciences, Hue University
 Abstract
 This paper investigates some new properties of special choice functions, as well as the
 closeness of special choice functions class under intersection operation, and some related
 problems.
 Keywords: Choice function, closure operation, functional dependency.
 19
Một số kết quả về hàm chọn 
 Ông i T 
 gi ng d y t i 
 : 
 20