Bài viết 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ô. | 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ệ 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. k (3) Tính đầy đủ: E i 1 i = 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)
