TAILIEUCHUNG - Công thức suy dẫn trong mô hình dữ liệu dạng khối
Bài viết Công thức suy dẫn trong mô hình dữ liệu dạng khối đề xuất khái niệm công thức suy dẫn trong mô hình dữ liệu dạng khối, phát biểu và chứng minh một số tính chất về công thức suy dẫn, tính chất của họ tập đóng và khối chân lý trong lược đồ khối, điều kiện cần và đủ về khối chân lý của một hội suy dẫn, thuật toán xây dựng hội suy dẫn nhận một khối nhị phân làm khối chân lý. | Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 9-10/7/2015 CÔNG THỨC SUY DẪN TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI Trịnh Đình Thắng1, Trần Minh Tuyến2, Trịnh Ngọc Trúc3 1 ĐHSP Hà Nội 2, 2 ĐH Công đoàn, 3 ĐHSP Hà Nội 2 thangsp2@, tuyentm@, tructn@ TÓM TẮT- Báo cáo đề xuất khái niệm công thức suy dẫn trong mô hình dữ liệu dạng khối, phát biểu và chứng minh một số tính chất về công thức suy dẫn, tính chất của họ tập đóng và khối chân lý trong lược đồ khối, điều kiện cần và đủ về khối chân lý của một hội suy dẫn, thuật toán xây dựng hội suy dẫn nhận một khối nhị phân làm khối chân lý,. Ngoài ra, điều kiện cần và đủ để một công thức Boolean có thể biểu diễn qua một hội suy dẫn cũng đã được phát biểu và chứng minh ở đây. Từ khóa: Công thức suy dẫn, công thức Boolean, khối chân lý, lược đồ khối. I. MÔ HÌNH DỮ LIỆU DẠNG KHỐI A. Khối, lược đồ khối Định nghĩa [1] Gọi R = (id; A1, A2,., An ) là một bộ hữu hạn các phần tử, trong đó id là tập chỉ số hữu hạn khác rỗng, Ai (i=1n) là các thuộc tính. Mỗi thuộc tính Ai (i=1n) có miền giá trị tương ứng là dom(Ai). Một khối r trên R, kí hiệu r(R) gồm một số hữu hạn phần tử mà mỗi phần tử là một họ các ánh xạ từ tập chỉ số id đến các miền trị của các thuộc tính Ai (i=1n). Nói một cách khác: t∈ r(R) ⇔ t = { ti : id → dom(Ai)}i=1n . Ta kí hiệu khối đó là r(R) hoặc r(id; A1, A2,., An ), đôi khi nếu không gây nhầm lẫn ta kí hiệu đơn giản là r. Định nghĩa [1] Cho R = (id; A1, A2,., An ), r(R) là một khối trên R. Với mỗi x∈ id ta kí hiệu r(Rx) là một khối với Rx = ({x}; A1, A2,., An ) sao cho: tx∈ r(Rx) ⇔ tx = {tix = ti } i=1n , ở đây t∈ r(R), t = { ti : id → dom(Ai)}i=1n , x Khi đó r(Rx) được gọi là một lát cắt trên khối r(R) tại điểm x. B. Phụ thuộc hàm Sau đây, để cho đơn giản ta sử dụng các kí hiệu: x(i) = (x; Ai ) ; id(i) = {x(i)
đang nạp các trang xem trước
