CHƯƠNG 1: CƠ SỞ LÝ THUYẾT 1. Mệnh đề và các phép toán mệnh đề Chúng ta chỉ xét đến các mệnh đề toán học, có nghĩa là một phát biểu nào đó chỉ có hai giá trị: đúng hoặc sai, giá trị đúng (ký hiệu là 1 hoặc True,…), sai (ký hiệu là 0 hoặc False). Giá trị của mệnh đề được gọi là chân trị của mệnh đề đó.1: Các phát biểu sau đây là các mệnh đề. 1/ p = “2 là một số nguyên tố” là mệnh đề đúng nên chân trị của p là 1 2/ q = “5 là một số chẵn” là mệnh đề sai nên chân trị của q là 0 Trong việc khảo sát các mệnh đề, người ta còn phân ra làm hai loại là: mệnh đề sơ cấp và mệnh đề phức hợp.
Mệnh đề sơ cấp là các "nguyên tử" theo nghĩa là nó không thể được phân tích thành mệnh đề nhỏ hơn. Chẳng hạn ví dụ 1.1 Mệnh đề phức hợp. Mệnh đề phức hợp là mệnh đề được tạo thành từ một hay nhiều mệnh đề khác bằng cách sử dụng các liên kết logic như từ "NOT" dùng trong việc phủ định một mệnh đề, các từ nối: "AND", "OR", "", v.2: Mệnh đề sau đây là mệnh đề phức hợp. E = “2 là một số nguyên tố” AND “5 là một số chẵn” 1.
Các phép toán trên mệnh đề Ðiều mà chúng ta quan tâm ở đây không phải là xác định tính đúng hoặc sai của một mệnh đề sơ cấp. Bởi vì những mệnh đề này thường là những phát biểu nói lên một ý tưởng nào đó trong một phạm vi chuyên môn nhất định. Vấn đề mà ta quan tâm ở đây là làm thế nào để tính toán chân trị của các mệnh đề phức hợp theo các mệnh đề sơ cấp cấu thành mệnh đề phức hợp đó 4 nhờ vào các phép toán logic. Các phép toán logic được định nghĩa bằng bảng chân trị (truth table).
Bảng chân trị chỉ ra chân trị của mệnh đề phức hợp theo từng trường hợp của các chân trị của các mệnh đề sơ cấp tạo thành mệnh đề phức hợp. Bảng chân trị của các phép toán logic tất nhiên là phản ánh ngữ nghĩa tự nhiên của các từ liên kết tương ứng. Bảng chân trị không chỉ dùng để kê ra sự liên hệ chân trị giữa mệnh đề phức hợp với chân trị của các mệnh đề sơ cấp cấu thành nó, mà bảng chân trị còn được dùng với mục đích rộng hơn: liệt kê sự liên hệ chân trị giữa các mệnh với các mệnh đề đơn giản hơn cấu thành chúng. a) Phép phủ định Cho p là một mệnh đề, chúng ta dùng ký hiệu p để chỉ mệnh đề phủ định của mệnh đề p.3 : Nếu ta ký hiệu p là mệnh đề "5 < 3" thì p là ký hiệu cho mệnh đề "5 ≥ 3".
Trong trường hợp này p sai, p đúng. Ta có thể viết p = 0, p = 1. b) Phép hội Phép "hội", ký hiệu là ^ , cho p và q là hai mệnh đề, viết là p q là phép toán chỉ chân trị đúng ki và chỉ khi cả p và q đều đúng.4: Cho các mệnh đề p = "5 > -7", q = "2721 là một số nguyên tố", r = "một tam giác đều cũng là một tam giác cân". c) Phép tuyển Cho p và q là hai mệnh đề.
Ta ký hiệu mệnh đề "p tuyển với q" là p q. 5 Chân trị của mệnh đề này chỉ sai khi và chỉ khi cả p và q đều sai.5: Cho các mệnh đề p = "5 > 7", q = "2721 là một số nguyên tố", r = "một tam giác đều cũng là một tam giác cân". d) Phép kéo theo Phép kéo theo, ký hiệu bởi → , được đưa ra để mô hình cho loại phát biểu điều kiện có dạng : "nếu. Cho p và q là 2 mệnh đề, ta sẽ viết p → q để diễn đạt phát biểu "nếu p thì q".
Kết quả phép toán kéo theo → được cho trong bảng 1. Mệnh đề p → q, được đọc là "nếu p thì q. e) Phép kéo theo hai chiều Phép kéo theo 2 chiều hay phép tương đương, ký hiệu bởi ↔, được đưa ra để mô hình cho loại phát biểu điều kiện hai chiều có dạng : ". nếu và chỉ nếu.
Cho p và q là 2 mệnh đề, ta viết p ↔q để diễn đạt phát biểu "p nếu và chỉ nếu q". Phép toán tương đương ↔ được định nghĩa trong bảng tổng hợp các giá trị chân trị 1. Mệnh đề p ↔ q, được đọc là "p nếu và chỉ nếu q", còn được phát biểu dưới các dạng khác sau đây: "p khi và chỉ khi q". "p là điều kiện cần và đủ cho q".
Mệnh đề p ↔q có chân trị đúng (=1) trong các trường hợp p và q có cùng chân trị.1: Bảng tổng hợp giá trị chân trị của các phép toán cơ bản P q p pq pq pq pq 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 1 f) Độ ưu tiên của các toán tử logic Tương tự như đối với các phép toán số học, để tránh phải dùng nhiều dấu ngoặc trong các biểu thức logic, ta đưa ra một thứ tự ưu tiên trong việc tính toán. Ở trên ta có 5 toán tử logic: (không) , (và), (hay), →(kéo theo), ↔ (tương đương) ưu tiên mức 1 (cao nhất) , ưu tiên mức 2 (thấp hơn) →, ↔ ưu tiên mức 3 (thấp nhất) trong đó, các toán tử liệt kê trên cùng dòng có cùng độ ưu tiên. p q r là nhập nhằng. Cần phải dùng các dấu ngoặc để chỉ rõ nghĩa.
Các luật logic Các luật logic là cơ sở để ta thực hiện các biến đổi trên một biểu thức logic để có được một biểu thức logic mới tương đương logic với biểu thức logic có trước. Mỗi biểu thức logic cho ta một sự khẳng định về sự tương đương của 2 biểu thức logic. Ta sẽ sử dụng các qui tắc thay thế và các luật logic đã biết để thực hiện các phép biến đổi tương đương trên các biêu thức logic. Dưới đây, chúng ta sẽ liệt kê ra một số luật logic thường được sử dụng 7 trong lập luận và chứng minh.
Các luật nầy có thể được suy ra trực tiếp từ các bảng chân trị của các biểu thức logic. a) Các luật về phép phủ định p p 1 0 0 1 b) Luật giao hoán pq q p pq q p c) Luật kết hợp p (q r ) (q p) r p (q r ) (q p) r d) Luật phân bố p (q r ) ( p q ) ( p r ) p (q r ) ( p q ) ( p r ) e) Luật De Morgan ( p q ) p p ( p q ) p p f) Luật về phần tử bù p p 1 p p 0 g) Luật kéo theo p q p q h) Luật tương đương p q ( p q ) (q p ) i) Các luật đơn giản của phép tuyển p p p (tính lũy đẳng của phép tuyển) 8 p 1 1 (luật thống trị) p 0 0 (luật trung hòa) p ( p q ) p (luật hấp thụ) j) Các luật đơn giản của phép hội p p p (tính lũy đẳng của phép hội) p 1 p (luật trung hòa) p 0 0 (Luật thống trị) p ( p q) p (Luật hấp thụ) Những luật trên được chọn lựa để làm cơ sở cho chúng ta thực hiện các biến đổi logic, suy luận và chứng minh. Tất nhiên là còn nhiều luật logic khác mà ta không liệt kê ra ở đây. Mệnh đề chuẩn hội Dạng chuẩn tắc (chính tắc) của 1 biểu thức là biểu diễn biểu thức về dạng đơn giản, chỉ bao gồm các phép toán phủ định, hội tuyển của các mệnh đề.
Giả sử p1, p2, … , pn là các biến mệnh đề. Một biểu thức logic F theo các biến mệnh đề p1, p2,… , pn được gọi là một biểu thức tuyển cơ bản (tuyển sơ cấp) nếu nó có dạng sau: F q1 q2 .qn với q j p j hoặc q j p j (j = 1, 2, …, n) Ví dụ 1.7: x y z là một biểu thức tuyển cơ bản theo 3 biến mệnh đề x, y, z. Biểu thức logic E(p1, p2, … , pn) theo các biến mệnh đề p1, p2, … , pn được nói là có dạng chuẩn hội khi E có dạng: E E1 E2 . En Trong đó mỗi biểu thức con Ei đều có dạng chính tắc tuyển theo các biến p1, p2, … , pn.8: Các biểu thức sau đây có dạng chuẩn tắc hội (chính tắc hội): E ( x, y, z ) (x y z ) ( x y z ) ( x y z ) F ( p1 , p2 , p3 , p4 ) ( p1 p2 p3 p4 ) ( p1 p2 p3 p4 ) Định lý 1.1: Mọi biểu thức logic E(p1, p2, … , pn) đều có thể viết dưới dạng chính tắc hội duy nhất, không kể sự sai khác về thứ tự trước sau của các biểu thức tuyển cơ bản trong phép hội).
Nói một cách khác, ta có duy nhất một tập hợp các biểu thức tuyển cơ bản {E1, E2, … , Em} sao cho biểu thức E(p1, p2, … , pn) tương đương logic với biêu thức E1 E2 . [15] Chứng minh: Có thể dễ dàng nhận thấy, áp dụng tập các luật trong mục 1.3 ta có thể biến các biểu thức bất kỳ thành dạng tuyển của các biểu thức hội. Từ đó, ta có điều phải chứng minh. Cơ sở dữ liệu phân tán CSDL phân tán (Distributed Database System – DDBS) là một tập hợp dữ liệu có liên đới logic và được phân bố trên các nút của một mạng máy tính.
Phần lớn các hệ cơ sở dữ liệu phân tán được thiết kế theo hướng từ trên xuống (Top-Down). Thiết kế phân mảnh dữ liệu là công việc đầu tiên phải thực hiện.