Giáo trình Toán rời rạc (Phần 2) - Lâm Thị Ngọc Châu

49 trang cucquyet12 6970

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Toán rời rạc (Phần 2) - Lâm Thị Ngọc Châu", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_toan_roi_rac_phan_2_lam_thi_ngoc_chau.pdf

Nội dung text: Giáo trình Toán rời rạc (Phần 2) - Lâm Thị Ngọc Châu

Chương 3: Vị từ và lượng từ CHƯƠNG 3 : VỊ TỪ VÀ LƯỢNG TỪ 3.1. Tổng quan • Mục tiêu của chương 3 Học xong chương này, sinh viên phải nắm bắt được các vấn đề sau: - Thế nào là vị từ, không gian của vị từ, trọng lượng của vị từ. - Thế nào là lượng từ, lượng từ tồn tại, lượng từ với mọi. - Cách biểu diễn một câu thông thường thành biểu thức logic. • Kiến thức cơ bản cần thiết Các kiến thức cơ bản trong chương này bao gồm: - Các phép toán đại số, hình học cơ bản để xác định được giá trị đúng, sai của các phát biểu. - Có khả năng suy luận. - Nắm vững các phép toán logic trong chương 1. • Tài liệu tham khảo Phạm văn Thiều, Đặng Hữu Thịnh. Toán rời rạc ứng dụng trong tin học. Nhà xuất bản Khoa học và Kỹ thuật, Hà Nội - 1997 (chương 1.3, trang 32 - 52). • Nội dung cốt lõi - Định nghĩa vị từ, không gian của vị từ, trọng lượng của vị từ. - Định nghĩa lượng từ, lượng từ với mọi, lượng từ tồn tại. - Dịch các câu thông thường thành biểu thức logic. 3.2. Các định nghĩa Trong toán học hay trong chương trình của máy tính, chúng ta thường gặp những câu có chứa các biến như sau : "x>3", "x=y+3", "x+y=z" Các câu này không đúng cũng không sai vì các biến chưa được gán cho những giá trị xác định. Trong chương này, chúng ta sẽ xem xét cách tạo ra những mênh đề từ những câu như vậy. Trang: 48
Chương 3: Vị từ và lượng từ 3.2.1. Định nghĩa vị từ (Prédicat) Một vị từ là một khẳng định P(x,y, ) trong đó có chứa một số biến x,y, lấy giá trị trong những tập họp A,B, cho trước, sao cho : - Bản thân P(x,y, ) không phải là mệnh đề. - Nếu thay x, y , bằng những giá trị cụ thể thuộc tập họp A, B, cho trước ta sẽ được một mệnh đề P(x, y, ), nghĩa là khi đó chân trị của P(x, y, ) hoàn toàn xác định. Các biến x, y, được gọi là các biến tự do của vị từ. Ví dụ 1: Các câu có liên quan đến các biến như: "x>3", "x + y = 5" rất thường gặp trong toán học và trong các chương trình của máy tính. Các câu này không đúng cũng không sai vì các biến chưa được cho những giá trị xác định. Nói cách khác, vị từ có thể xem là một hàm mệnh đề có nhiều biến hoặc không có biến nào, nó có thể đúng hoặc sai tùy thuộc vào giá trị của biến và lập luận của vị từ. Ví dụ 2: Câu {n là chẳn} là một vị từ. Nhưng, khi cho n là một số cụ thể là chẳn hay là lẻ ta được một mệnh đề: n = 2 :{2 là chẳn}: mệnh đề đúng. n = 5 :{5 là chẳn}: mệnh đề sai. Vị từ {n là chẳn} có 2 phần. Phần thứ nhất là biến x là chủ ngữ của câu. Phần thứ hai "là chẳn" cũng được gọi là vị từ, nó cho biết tính chất mà chủ ngữ có thể có. Ký hiệu: P(n) = {n là chẳn} Tổng quát, người ta nói P(n) là giá trị của hàm mệnh đề P tại n. Một khi biến n được gán trị thì P(n) là một mệnh đề. Ví dụ 3: Cho vị từ P(x) = {x>3}. Xác định chân trị của P(4) và P(2). Giải: P(4) = {4>3} : mệnh đề đúng. P(2) = {2>3} : mệnh đề sai. 3.2.2. Không gian của vị từ (Prédi cat) Người ta có thể xem vị từ như là một ánh xạ P, với mỗi phần tử x thuộc tập hợp E ta được một ảnh P(x)∈{∅, 1}. Tập hợp E này được gọi là không gian của vị từ. Không gian này sẽ chỉ rõ các giá trị khả dĩ của biến x làm cho P(x) trở thành mệnh đề đúng hoặc sai. Trang: 49
Chương 3: Vị từ và lượng từ 3.2.3. Trọng lượng của vị từ (Prédi cat) Chúng ta cũng thường gặp những câu có nhiều biến hơn. Vị từ xuất hiện cũng như một hàm nhiều biến, khi đó số biến được gọi là trọng lượng của vị từ. Ví dụ 1: Vị từ P(a,b) = {a + b = 5} là một vị từ 2 biến trên không gian N. Ta nói P có trong lượng 2. Trong một vị từ P(x1, x2, , xn) có trọng lượng là n. Nếu gán giá trị xác định cho một biến trong nhiều biến thì ta được một vị từ mới Q(x1, x2, xn) có trọng lượng là (n-1). Qui luật này được áp dụng cho đến khi n=1 thì ta có một mệnh đề. Vậy, thực chất mệnh đề là một vị từ có trọng lượng là ∅. Ví dụ 2: Cho vị từ P(x, y, z ) = {x + y = z}. Cho x = ∅ : Q(y,z) = P(∅, y, z) = {∅ + y = z} y = ∅ : R(z) = Q(∅, z) = P(∅, ∅, z) = {∅ + ∅ = z} z = ∅ : T = P(∅, ∅, 1) = {∅ + ∅ = 1} mệnh đề sai. Câu có dạng P(x1, x2, , xn) được gọi là giá trị của hàm mệnh đề P tại (x1, x2, , xn) và P cũng được gọi là vị từ. 3.2.4. Phép toán vị từ Phép toán vị từ sử dụng các phép toán logic mệnh đề và là sự mở rộng của phép toán mệnh đề để thể hiện rõ hơn các tri thức. Ví dụ 1: Cần viết câu "nếu hai người thích một người thì họ không thích nhau" dưới dạng logic vị từ. Trước khi viết câu trên ta hãy tìm hiểu các câu đơn giản được viết như sau: "Nam thích Mai" được viết theo phép toán vị từ là: thích (Nam, Mai). "Đông thích Mai" được viết theo phép toán vị từ là: thích (Đông, Mai). Tổng quát khẳng định trên được viết như sau: Thích (X, Z) AND thích (Y, Z) → NOT thích (X, Y) ⇔ (Thích (X, Z) ∧ thích (Y, Z) → ¬ thích (X, Y) Ví dụ 2: Cho vị từ "Quả bóng màu xanh". Phép toán vị từ cho phép mô tả theo quan hệ tri thức theo dạng: (quả bóng, xanh). Cách thể hiện này thuận tiện đối với việc dùng biến và hàm trong xử lý tri thức. Trong lĩnh vực trí tuệ nhân tạo, để lập trình trên các vị từ người ta sử dụng ngôn ngữ Trang: 50
Chương 3: Vị từ và lượng từ Prolog. Đó là một ngôn ngữ cấp cao có đặc điểm gần với ngôn ngữ tự nhiên, do ông C.Cameraller (Đại học Marseilles, Pháp) và nhóm đồng sự cho ra đời năm 1973. Ví dụ: Ta có tam đoạn luận sau: "Người ta ai cũng chết Socrates là người Vậy Socrates phải chết" Trong phần này chúng ta không đi sâu vào ngôn ngữ Prolog (vì sẽ học kỹ ở môn ngôn ngữ lập trình) mà chỉ giới thiệu các khái niệm trong lập trình Prolog có sử dụng các vị từ. a) Hằng: Là một giá trị xác định trong không gian của vị từ. các hằng được ký hiệu bởi các chữ thường dùng để đặt tên các đối tượng đặc biệt hay thuộc tính. b) Biến: Dùng để thể hiện các lớp tổng quát của các đối tượng hay các thuộc tính. Biến được viết bằng các ký hiệu bắt đầu là chữ in hoa. Vậy có thể dùng vị từ có biến để thể hiện các vị từ tương tự. Ví dụ: Vị từ "Quả bóng màu xanh" có thể viết lại: "X màu Y". Quả bóng xanh là các hằng được xác định trong không gian của vị từ. X, Y là biến. c) Các vị từ: Một sự kiện hay mệnh đề trong phép toán vị từ được chia thành phần. Vị từ và tham số. Tham số thể hiện một hay nhiều đối tượng của mệnh đề, còn vị từ dùng để khẳng định về đối tượng. Ví dụ: Câu "X thích Y" có dạng thích (X, Y). Thích là vị từ cho biết quan hệ giữa các đối tượng trong ngoặc. Đối số là các ký hiệu thay cho các đối tượng của bài toán. d) Hàm: Được thể hiện bằng ký hiệu, cho biết quan hệ hàm số. Ví dụ: Hoa là mẹ của Mai, Đông là cha của Cúc. Hoa và Đông là bạn của nhau. Ta co hàm số được viết để thể hiện quan hệ này. Mẹ (Mai) = Hoa Cha (Cúc) = Đông Trang: 51
Chương 3: Vị từ và lượng từ Bạn (Hoa, Đông) Các hàm được dùng trong vị tự là: Bạn (Mẹ (Mai), Cha (Cúc) 3.3. Các lượng từ Khi tất cả các trong môtk hàm mệnh đề điều được gán cho một giá trị xác định. Ta được chân trị của hàm mệnh đề. Tuy nhiên, còn có một cách khác để biến các vị từ thành mệnh đề mà người ta gọi là sự lượng hóa (hay lượng từ). 3.3.1. Lượng từ tồn tại ( ∃ ) Câu xác định "Tập hợp những biến x làm cho P(x) là đúng không là tập hợp rỗng" là một mệnh đề. Hay "Tồn tại ít nhất một phần tử x trong không gian sao cho P(x) là đúng" là một mệnh đề được gọi là lượng từ tồn tại của P(x). Ký hiệu: ∃x P(x) . 3.3.2. Lượng từ với mọi ( ∀ ) Câu xác định "Tập hơp những x làm cho P(x) đúng là tất cả tập hợp E" là một mệnh đề. Hay "P(x) đúng với mọi giá trị x trong không gian" cũng là một mệnh đề được gọi là lượng từ với mọi của P(x). Ký hiệu: ∀xP(x) Ví dụ: Cho vị từ P(x) = {số nguyên tự nhiên x là số chẵn}. Xét chân trị của hai mệnh đề ∀xP(x) và ∃xP(x). Giải: ∀x P(x) = {tất cả số nguyên tự nhiên x là số chẵn} là mệnh đề sai khi x = 5. ∃x P(x) = {hiện hữu một số nguyên tự nhiên x là số chẵn} là mệnh đề đúng khi x = 10. Chú ý: Cho P là một vị từ có không gian E. Nếu E = {e1, e2, en}, mệnh đề ∀xP(x) là đúng khi tất cả các mệnh đề P(e1), P(e2), P(en) là đúng. Nghĩa là ∀x P(x) ⇔ P(e1) ∧ P(e2) ∧ ∧ P(en) là đúng. Tương tự ∃xP(x) là đúng nếu có ít nhất một trong những mệnh đề P(e1), P(e2), P(en) là đúng. Nghĩa là ∃xP(x) ⇔ P(e1)∨ P(e2) ∨ ∨ P(en) là đúng. Trang: 52
Chương 3: Vị từ và lượng từ - Nếu không gian E là một tập trống thì ∀xP(x) và ∃xP(x) có chân trị như thế nào ? (Sinh viên tự giải đáp). Ví dụ: Cho P(a,b) = {cặp số nguyên tương ứng thỏa a + b = 5} Hãy xác định chân trị của các mệnh đề sau: ∀(a,b) P(a,b) {Tất cả cặp số nguyên tượng ứng F ∃(a,b) P(a,b) {Hiện hữu một cặp số nguyên tương ứng (a,b) sao cho a + b V = 5} ∃b∀a P(a,b) {Hiện hữu một cặp số nguyên tương ứng b sao cho cho mọi F số nguyên tương ứng a ta có a + b = 5} ∀a∃b P(a, b) {Mọi số nguyên tương ứng a, hiện hữu một số nguyên tưng V ứng b sao cho a + b = 5} ∃a∀b P(a,b) {Hiện hữu một cặp số nguyên tương ứng a sao cho cho mọi F số nguyên tương ứng b ta có a + b = 5} ∀b∃a P(a, b) {Mọi số nguyên tương ứng b, hiện hữu một số nguyên tưng V ứng a sao cho a + b = 5} Định lý 1: Cho vị từ P(a, b) có trọng lượng là 2. Khi đó: a) ∀a∀b P(a,b) và ∀b∀a P(a, b) là có cùng chân trị. Nghĩa là : ∀a∀b P(a,b) ↔∀b∀a P(a, b) Ký hiệu: ∀(a,b) P(a,b) b) ∃a∃b P(a,b) và ∃b∃a P(a, b) là có cùng chân trị. Nghĩa là: ∃a∃b P(a,b) ↔ ∃b∃a P(a, b) Ký hiệu: ∃(a,b) P(a,b) c) Nếu ∃a∀b P(a,b) là đúng thì ∀b∃a P(a,b) cũng đúng nhưng điều ngược lại chưa đúng. Nghĩa là : ∃a∀b P(a,b) → ∀b∃a P(a,b) d) Nếu ∃b∀a P(a,b) là đúng thì ∀a∃b P(a,b) cũng đúng nhưng điều ngược lại chưa đúng. Nghĩa là : ∃b∀a P(a,b) → ∀a∃b P(a,b) Trang: 53
Chương 3: Vị từ và lượng từ Định lý 2: 1. ¬ (∀ x P(x)) và ∃ x (¬ P(x) là có cùng chân trị. 2. ¬ (∃ x P(x)) và ∀ x (¬ P(x) là có cùng chân trị. Giải thích: 1. Phủ định với ∀x P(x) nói rằng tập hợp những x làm cho P(x) đúng không là tất cả tập hợp E. Vậy nói rằng hiện hữu ít nhất một phần tử x ∈ E mà ở chúng P(x) là sai hay nói rằng hiện hữu ít nhất một phần tử x ∈ E mà ở chúng P(x) là đúng. 2. ¬ ∃ x P(x) nói rằng tập hợp những x mà ở chúng P(x) là đúng là tập hợp trống. Nghĩa là, tập hợp những x mà ở chúng P(x) là sai là tập hợp E hay không có phần tử nào làm P(x) đúng. Ta có ∀ x (¬ P(x)). Ví dụ: Phủ định của "Mọi số nguyên n là chia chẵn cho 3" là "Tồn tại ít nhất một số nguyên n không chia chẵn cho 3" - Phương pháp ứng dụng. Để đạt được phủ định của một mệnh đề xây dựng bằng liên kết của những biến của vi từ với phương tiện định lượng, người ta thay thế những định lượng với mọi ∀ bởi tồn tại ∃, tồn tại ∃ bởi với với mọi ∀ và sau cùng thay thế vị từ bằng phủ định của vị từ đó. Định lý 3: Cho P và Q là hai vị từ có cùng không gian. 1. Mệnh đề ∀x (P(x) ∧ Q(x)) và (∀x (P(x) ∧ ∀x (Q(x)) là có cùng chân trị. 2. Nếu mệnh đề ∃x (P(x) ∧ Q(x)) là đúng thì ta có mệnh đề: (∃x P(x)) ∧ (∃xQ(x)) cũng đúng. 3. Mệnh đề ∃x (P(x) ∨ Q(x)) và (∃xP(x) ∨ ∃xQ(x)) là có cùng chân trị. 4. Nếu mệnh đề ∀x (P(x) ∨ Q(x)) là đúng thì ta có mệnh đề ∀xP(x) ∨ ∀xQ(x) là đúng, nhưng điều ngược lại không luôn luôn đúng. Chú thích: Nếu P và Q là hai vị từ có cùng không gian E. Ta có : - Tập họp A⊂ E : Tập hợp những phần tử x thuộc E mà ở chúng thì P(x) là đúng. - Tập họp B⊂ E: Tập hợp những phần tử x thuộc E mà ở chúng thì Q(x) là đúng. Trang: 54
Chương 3: Vị từ và lượng từ Khi đó người ta lưu ý rằng, A∧B là tập hợp những x thuộc E mà ở chúng mệnh đề P(x)∧Q(x) là đúng. Trong khi đó A∨B là tập hợp những x của E mà ở đó mệnh đề P(x)∨Q(x) là đúng. 3.4. Dịch các câu thông thường thành biểu thức logic Sau khi đã được giới thiệu về các lượng từ, chúng ta có thể biểu diễn được một tập hợp rộng lớn các câu thông thường thành các biểu thức logic. Việc làm này nhằm mục đích loại đi những điều chưa rõ ràng và người ta có thể sử dụng các câu suy luận này trong việc lập trình logic và trí tuệ nhân tạo. Ví dụ 1: Biểu diễn câu "Mọi người đều có chính xác một người bạn tốt nhất" thành một biểu thức logic. Giải: Giả sử B(x,y) là câu "y là bạn tốt của x". Để dịch câu trong ví dụ cần chú ý B(x,y) muốn nói rằng đối với mỗi cá nhân x có một cá nhân khác là y sao cho y là bạn tốt nhất của x, nếu z là một cá nhân khác y thì z không phải là bạn tốt nhất của x. Do đó, câu trong ví dụ có thể dịch thành: ∀x ∃y ∀z [B(x,y) ∧ ((z ≠ y) → ¬ B(x, z))] Ví dụ 2: Biểu diễn câu: "Nếu một người nào đó là phụ nữ và đã sinh con, thì người đó sẽ là mẹ của một người nào khác" thành một biểu thức logic: Giải: Giả sử F(x) = "x là phụ nữ" P(x) = "x đã sinh con" và M(x,y) = "x là mẹ của y" Vì trong ví dụ áp dụng cho tất cả mọi người nên ta có thể viết nó thành biểu thức như sau: ∀x (F(x) ∧ P(x)) → ∃y M(x,y) Ví dụ 3: Xét các câu sau. Hai câu đầu tiên là tiền đề và câu ba là kết luận. Toàn bộ tập hợp 3 câu này được gọi là một suy lý. "Tất cả sư tử Hà Đông đều hung dữ". "Một số sư tử Hà Đông không uống cà phê". "Một số sinh vật hung dữ không uống cà phê". Giải: Gọi P(x)= {x là sư tử hà đông} Q(x)= {x hung dữ} R(x)= {x uống cà phê} Giả sử rằng không gian là tập hợp toàn bộ các sinh vật, ta có cách suy diễn sau: Trang: 55
Chương 3: Vị từ và lượng từ ∀x ( P(x) → Q(x) ∃x ( P(x) ∧ ¬ R(x)) ∃x ( Q(x) ∧ ¬ R(x)) 3.5. Tổng kết chương 3 Có một số điều cần lưu ý trong việc phủ định các lượng từ trong định lý 2. Ví dụ : Hãy xét phủ định của câu sau đây : "Tất cả sinh viên trong lớp đều đã học môn Toán rời rạc 2" Câu này chính là câu sử dụng lượng từ với mọi như sau: ∀xP(x) Trong đó P(x) = { x đã học môn Toán rời rạc 2 }. Phủ định của câu này là : " Không phải tất cả các sinh viên trong lớp đều đã học môn Toán rời rạc 2". Điều này có nghĩa là :" Có ít nhất một sinh viên ở lớp này chưa học Toán rời rạc 2" . Đây chính là lượng từ tồn tại của phủ định hàm mệnh đề ban đầu được viết như sau : ∃x¬P(x). Ta có : ¬ ∀xP(x) ⇔ ∃x¬P(x) ¬ ∃xP(x) ⇔ ∀x¬P(x) Phép phủ định các lượng từ được minh họa rõ hơn trong bảng chú thích sau: Phủ định Mệnh để tương Khi nào phủ định là Khi nào sai đương đúng ¬ ∃xP(x) ∀x¬P(x) P(x) sai với mọi x Có một x để P(x) là ¬ ∀xP(x) ∃x¬P(x) Có một x để P(x) sai đúng P(x) đúng với mọi x 3.6. Bài tập chương 3 1. Cho 2 vị từ P(x) xác định như sau: P(x) = {x ≤ 3} Q(X) = {x+ 1 là số lẻ} Nếu không gian là tập số nguyên, hãy xác định chân trị của những mệnh đề sau: Trang: 56
Chương 3: Vị từ và lượng từ a) P(1) b) Q(1) c) ¬ P(3) d) Q(6) e) P(7)∧Q(7) f) P(3)∧Q(4) g) P(4) h) ¬ (P(-4)∨Q(-3) i) ¬ P(-4) ∧¬ Q(-3) 2. Các vị từ P(x), Q(x) được cho như bài tập 1. R(x) = {x > 0}. Nếu không gian vẫn là tập số nguyên. a) Xác định chân trị của những mệnh đề sau: 1. P(3) ∨ [Q(3)∨¬ R(3)] 2. ¬P(3) ∧ [Q(3) ∨ [Q(3) ∨ R(3)] 3. P(2) → [Q(2) → R(2)] 4. [P(2) ⇔ Q(2)] → R(2) 5. P(0) → [¬ Q(1) ⇔ R(1) 5. [P(-1) ⇔ Q(-2) ⇔ R(-3) b) Xác định tất cả các giá trị x sao cho [P(x) ∧ Q(x)] ∧ R(x) là một mệnh đề đúng. c) Tìm 5 giá trị nguyên dương nhỏ nhất cảu x sao cho vị từ. P(x) → [¬ Q(x) ∧ R(x) là mệnh đề đúng. 3. Cho vị từ P(x) được xác định như sau: P(x) = {x2 = 2x} trên không gian là tập hợp số nguyên. Xác định giá trị đúng, sai của những mệnh đề: a) P(0) b) P(1) c) P(2) d) P(-2) e) ∃x P(x) f) ∀x P(x) 4. Cho 2 vị từ 2 biến P(x,y) và Q(x,y) được xác định như sau: P(x,y) = {x2 ≥ y} Q(x,y) = {x+2 <y} Nếu không gian là tập số thực, xác định chân trị của các mệnh đề a) P(2,4) b) Q(1,π) 1 1 c) P(-3,8)∧Q(1,3) d) P( , )∨¬Q(-2,-3) 2 3 e) P(2,2)→Q(1,1) f) P(1,2)⇔¬Q(1,2) 5. Trong một chương trình Pascal, n là một biến nguyên và A là mảng chứa 20 giá trị nguyên A[1],A[2], A[20] được khai báo như sau: for n:=1 to 20 do A[n]:=n*n-n; Hãy viết dạng kí hiệu của những mệnh đề sau: nếu xem A[n] như vị từ một biến n trên không gian các số nguyên từ 1 đến 20: a) Mọi phần tử của mảng đều không âm. Trang: 57
Chương 3: Vị từ và lượng từ b) Số nguyên A[20] là phần tử lớn nhất trong mảng. c) Tồn tại 2 phần tử trong mảng A mà phần tử sau gấp 2 lần phần tử trước. d) Các phần tử trong mảng được xếp theo thứ tự tăng dần. e) Mọi phần tử trong mảng đều khác nhau. Chứng minh các mệnh đề trên. 6. Trên không gian là tập số nguyên, cho các vị từ sau: P(x) = {x>0) Q(x) = {x là số chẵn} R(x) = {x là số chính phương} S(x) = {x chia hết cho 4} T(x) = {x chia hết cho 5} a) Viết dạng ký hiệu của những mệnh đề sau: 1. Có ít nhất 1 số nguyên chẵn. 2. Tồn tại 1 số nguyên dương là số chẵn. 3. Nếu x chẵn, thì x không chia hết cho 5. 4. Không có số nguyên chẵn nào là chia hết cho 5. 5. Tồn tại 1 số nguyên chẵn chia hết cho 4. 6. Nếu x chẵn và x là số chính phương, thì x chia hết cho 4. b) Xác định chân trị của mỗi mệnh đề a). Với mỗi mệnh đề sai, hãy cho một dẫn chứng cụ thể. c) Viết thành lời các dạng ký hiệu sau: 1. ∀x [R(x) → P(x)] 2. ∀x [S(x) → Q(x)] 3. ∀x [S(x) → ¬T(x)] 4. ∃x [S(x) ∧¬ R(x)] 5. ∀x [¬ R(x) ∨¬ Q(x) ∨ S(x)] 7. Cho các vị từ trên không gian là tập số thực như sau: P(x) = {x ≥ 0) Q(x) = {x2 ≥ 0} R(x) = {x2 - 3x -4 = 0} S(x) = {x2 - 3 > 0} Xác định giá trị đúng, sai của những mệnh đề sau. Theo dẫn chứng hoặc giải thích cụ thể: Trang: 58
Chương 3: Vị từ và lượng từ a) ∃x [P(x) R(x)] b) ∀x [P(x) → Q(x)] c) ∀x [Q(x) → S(x)] d) ∀x [R(x) ∨ S(x)] e) ∀x [R(x) → P(x)] 8. Cho 3 vị từ P(x), Q(x), R(x) được xác định như sau: P(x) = {x2 - 8x + 15 = 0) Q(x) = {x là số lẻ} R(x) = {x > 0} Trên tập không gian là tất cả các số nguyên, hãy xác định giá trị đúng, sai của những mệnh đề sau. Cho dẫn chứng hoặc giải thích cụ thể: a) ∀x [P(x) → Q(x)] b) ∀x [Q(x) → P(x)] c) ∃x [P(x) → Q(x)] d) ∃x [Q(x) → P(x)] e) ∃x [R(x) ∧ P(x)] f) ∀x [P(x) → R(x)] g) ∃x [R(x) → P(x)] h) ∀x [¬ Q(x) →¬ P(x)] i) ∃x [P(x) → (Q(x) ∧ R(x))] j) ∀x [(P(x) ∨ Q(x) → R(x)] 9. Cho 3 vị từ P(x), Q(x), R(x) như sau: P(x) = {x2 - 7x + 10 = 0) Q(x) = {x2 - 2x -3 = 0} R(x) = {x < 0} a) Xác định giá trị đúng, sai của những mệnh đề sau, cho dẫn chứng hoặc giải thích cụ thể, nếu không gian là tập số nguyên. 1. ∀a [P(x) →¬ R(x)] 2. [Q(x) → R(x)] 3. ∃x [Q(x) → R(x)] 3. ∃x [P(x) → R(x)] b) Câu hỏi như phần a) nhưng không gian là tập Z' c) Câu hỏi như phần a) nhưng không gian chỉ gồm 2 số nguyên 2, 5. 10. Cho P(x) = {x học ở lớp hơn 5 giờ mỗi ngày trong tuần} Không gian là tập hợp các sinh viên. Hãy diễn đạt các lượng từ sau thành câu thông thường. a) ∃x P(x) b) ∀x P(x) c) ∃x ¬ P(x) d) ∀x ¬ P(x) Trang: 59
Chương 3: Vị từ và lượng từ 11. Cho vị từ P(x,y) = {x đã học môn y} với không gian của x là tập hợp tất cả các sinh viên lớp bạn và không gian của y là tập hợp tất cả các môn tin học của học kỳ mà bạn đang học. Hãy diễn đạt các lượng từ sau thành các câu thông thường: a) ∃x ∃y P(x,y) b) ∃x ∀y P(x,y) c) ∀x ∃y P(x,y) d) ∃y ∀x P(x,y) e) ∀y ∃x P(x,y) f) ∀x ∀y P(x,y) 12. Cho vị từ: P(x) = {x nói được tiếng anh} Q(x) = {x biết ngôn ngữ C++} Cho không gian là tập hợp các sinh viên lớp bạn. Hãy diễn đạt các câu sau bằng cách dùng P(x), Q(x), các lượng từ và các phép toán logic. a) Có một sinh viên ở lớp bạn nói được tiếng Anh và biết C++ b) Có một sinh viên ở lớp bạn nói được tiếng Anh nhưng không biết C++ c) Mọi sinh viên ở lớp bạn đều nói được tiếng Anh hoặc biết C++ d) Không có một sinh viên nào ở lớp bạn nói được tiếng Anh hoặc biết C++ 13. Cho tân từ: P(x) = {xl là sinh viên) Q(x) = {x là kẻ ngu dốt} R(x) = {x là kẻ vô tích sự} Bằng cách dùng các lượng từ, các phép toán logic và với các vị từ P(x), Q(x), R(x). Hãy diễn đạt các câu sau với không gian là toàn thể sinh viên: a) Không có sinh viên nào là kẻ ngu dốt b) Mọi kẻ ngu dốt đều là vô tích sự. c) Không có sinh viên nào là vô tích sự. Trang: 60
Chương 3: Vị từ và lượng từ CHƯƠNG 3 : VỊ TỪ VÀ LƯỢNG TỪ 48 3.1. Tổng quan 48 3.2. Các định nghĩa 48 3.2.1. Định nghĩa vị từ (Prédicat) 49 3.2.2. Không gian của vị từ (Prédi cat) 49 3.2.3. Trọng lượng của vị từ (Prédi cat) 50 3.2.4. Phép toán vị từ 50 3.3. Các lượng từ 52 3.3.1. Lượng từ tồn tại ( ∃ ) 52 3.3.2. Lượng từ với mọi ( ∀ ) 52 3.4. Dịch các câu thông thường thành biểu thức logic 55 3.5. Tổng kết chương 3 56 3.6. Bài tập chương 3 56 Trang: 61
Chương 4: Lý thuyết tập mờ & Logic mờ CHƯƠNG 4 : LÝ THUYẾT TẬP MỜ & LOGIC MỜ 4.1. Tổng quan • Mục tiêu của chương 4 Học xong chương này, sinh viên phải nắm bắt được các vấn đề sau: - Thế nào là khái niệm của tập mờ, mệnh đề mờ, suy diễn mờ. - Các phép toán trên tập mờ và logic mờ. • Kiến thức cơ bản cần thiết Các kiến thức cơ bản trong chương này bao gồm: - Nắm vững các phép toán logic trong chương 1. - Các suy luận ở chương 2. • Tài liệu tham khảo Nguyễn Hoàng Cương, Bùi Công Cường, Nguyễn Doãn Phước, Phan Xuân Minh, Chu Văn Hỷ, Hệ mờ và ứng dụng. Nhà xuất bản Khoa học và Kỹ thuật, Hà Nội - 1998. • Nội dung cốt lõi - Giới thiệu khái niệm về tập mờ, các phép toán trên tập mờ. - Mệnh đề mờ và các phép toán logic mờ. - Suy diễn mờ. 4.2. Giới thiệu Như đã biết, trong những suy luận đời thường cũng như các suy luận khoa học, logic toán học đóng một vai trò rất quan trọng. Ngày nay, xã hội càng phát triển thì nhu cầu con người ngày càng cao. Do đó, sự tiến bộ của khoa học cũng rất cao. Suy luận logic mệnh đề đã giới thiệu trong chương 1 (tạm gọi là logic nguyên thủy hay logic rõ) với hai giá trị đúng, sai hay 1, 0 đã không giải quyết được hết các bài toán phức tạp nảy sinh trong thực tế. Trang 61
Chương 4: Lý thuyết tập mờ & Logic mờ Ví dụ: quần áo như thế nào được gọi là dầy, là mỏng để máy giặt biết được mà có chế độ tự động sấy khô cho hợp lý ? Hay trong thơ văn có câu: " Trăng kia bao tuổi trăng già? Núi kia bao tuổi gọi là núi non? " Khái niệm trăng già hay núi non là không được định nghĩa rõ ràng. Những bài toán như vậy ngày một nhiều hơn trong các lĩnh vực điều khiển tối ưu, nhận dạng hệ thống, nói chung là trong các quá trình quyết định nhằm giải các bài toán với các dữ liệu không đầy đủ, hoặc không được định nghĩa một cách rõ ràng (trong điều kiện thiếu thông tin chẳng hạn). Một cách tiếp cận mới đã mang lại nhiều kết quả thực tiễn và đang tiếp tục phát triển đó là cách tiếp cận của lý thuyết tập mờ (FUZZY SET THEORY), do giáo sư Lotfi Zadeh của trường đại học California - Mỹ đề ra năm 1965. Công trình này thực sự đã khai sinh một ngành khoa học mới là lý thuyết tập mờ và đã nhanh chóng được các nhà nghiên cứu công nghệ mới chấp nhận ý tưởng. Một số kết quả bước đầu và hướng nghiên cứu tiếp theo góp phần tạo nên những sản phẩm công nghiệp đang được tiêu thụ trên thị trường. Lý thuyết tập mờ ngày càng phong phú và hoàn chỉnh, đã tạo nền vững chắc để phát triển logic mờ. Có thể nói logic mờ (Fuzzy logic) là nền tảng để xây dựng các hệ mờ thực tiển, ví dụ trong công nghiệp sản xuất xi măng, sản xuất điện năng, các hệ chuyên gia trong y học giúp chuẩn đoán và điều trị bệnh, các hệ chuyên gia trong xử lý tiếng nói, nhận dạng hình ảnh, Công cụ chủ chốt của logic mờ là tiền đề hóa và lập luận xấp xỉ với phép suy diễn mờ. Trong chương này, mục đích chính là giới thiệu khái niệm tập mờ, logic mờ, tập trung đi vào các phép toán cơ bản và bước đầu đi vào lập luận xấp xỉ với phép suy diễn mờ. 4.3. Khái niệm tập mờ (fuzzy set) Như chúng ta đã biết, tập hợp thường là kết hợp của một số phần tử có cùng một số tính chất chung nào đó. Ví dụ : tập các sinh viên. Ta có : T = { t / t là sinh viên } Vậy, nếu một người nào đó là sinh viên thì thuộc tập T, ngược lại là không thuộc tập T. Tuy nhiên, trong thực tế cuộc sống cũng như trong khoa học kỹ thuật có Trang 62
Chương 4: Lý thuyết tập mờ & Logic mờ nhiều khái niệm không được định nghĩa một cách rõ ràng. Ví dụ, khi nói về một "nhóm sinh viên khá", thì thế nào là khá ? Khái niệm về khá không rõ ràng vì có thể sinh viên có điểm thi trung bình bằng 8.4 là khá, cũng có thể điểm thi trung bình bằng 6.6 cũng là khá ( dải điểm khá có thể từ 6.5 đến 8.5), Nói cách khác, "nhóm sinh viên khá" không được định nghĩa một cách tách bạch rõ ràng như khái niệm thông thường về tập họp. Hoặc, khi chúng ta nói đến một "lớp các số lớn hơn 10" hoặc " một đống quần áo cũ", , là chúng ta đã nói đến những khái niệm mờ, hay những khái niệm không được định nghĩa một cách rõ ràng. Các phần tử của nhóm trên không có một tiêu chuẩn rõ ràng về tính "thuộc về" ( thuộc về một tập họp nào đó). Đây chính là những khái niệm thuộc về tập mờ. Trong đối thoại hàng ngày chúng ta bắt gặp rất nhiều khái niệm mờ này. Ví dụ, một ông giám đốc nói: " Năm qua chúng ta đã gặt hái được một số thành tích đáng khen ngợi. Năm tới đây chúng ta phải cố gắng thêm một bước nữa". Đây là một câu chứa rất nhiều khái niệm mờ. Như vậy, logic rõ có thể biểu diễn bằng một đồ thị như sau Logic mờ cũng có thể biểu diễn bằng một đồ thị nhưng là đồ thị liên tục Định nghĩa tập mờ (Fuzzy set): Cho Ω là không gian nền, một tập mờ A trên Ω tương ứng với một ánh xạ từ Ω đến đoạn [0,1]. A : Ω → [0,1] được gọi là hàm thuộc về (membership function) Kí hiệu A = {(a, µA(a)) / a∈ Ω} Trang 63
Chương 4: Lý thuyết tập mờ & Logic mờ Trong đó, µA(a) ∈ [0,1] chỉ mức độ thuộc về (membership degree) của phần tử a vào tập mờ A. Khoảng xác định của hàm µA(a) là đoạn [0, 1], trong đó giá trị 0 chỉ mức độ không thuộc về, còn giá trị 1 chỉ mức độ thuộc về hoàn toàn. Ví dụ 1: Một sự biểu diễn tập mờ cho số "integer nhỏ". µ int Ví dụ 2: Một sự biểu diễn tập mờ cho các tập người đàn ông thấp, trung bình và cao. µ chiều cao Ví dụ 3: Cho Ω = {1, 2, 3, 4, 5}, tập mờ A trên Ω tương ứng với ánh xạ µA như sau: µA : 1 → 0 2 → 1 3 → 0.5 4 → 0.3 5 → 0.2 Ta có tập mờ A = {(1,0), (2,1), (3,0.5), (4,0.3), (5,0.2)} Cách viết trên là sự liệt kê các phần tử khác nhau cùng với mức độ thuộc về tập họp A. Từ định nghĩa trên chúng ta có thể suy ra: - Tập mờ A là rỗng nếu và chỉ nếu hàm thuộc về µA(a)= 0 ,∀a∈ Ω - Tập mờ A là toàn phần nếu và chỉ nếu µA(a) = 1 ,∀a∈ Ω - Hai tập mờ A và B bằng nhau nếu µA(x) = µB(x) với mọi x trong Ω. Trang 64
Chương 4: Lý thuyết tập mờ & Logic mờ Ví dụ 4: Cho Ω = {1, 2, 3, 4, 5}, tập mờ A trên Ω tương ứng với ánh xạ µA như ví du trên. A = {(1,0), (2,1), (3,0.5), (4,0.3), (5,0.2)} Tập mờ B trên Ω tương ứng với ánh xạ µB như sau: µB : 1 → 0 2 → 1 3 → 0.5 4 → 0.3 5 → 0.2 Ta có tập mờ B = {(1,0), (2,1), (3,0.5), (4,0.3), (5,0.2)} Nhận thấy, µA(x) = µB(x) với mọi x trong Ω. Vậy A= B. 4.4. Các phép toán về tập mờ Để có thể tiến hành mô hình hóa các hệ thống có chứa tập mờ và biểu diễn các qui luật vận hành của hệ thống này, trước tiên chúng ta cần tới việc suy rộng các phép toán logic cơ bản với các mệnh đề có chân trị trên đoạn [0, 1]. Cho Ω = {P1, P2, } với P1, P2, là các mệnh đề. Tập mờ A trên Ω tương ứng với ánh xạ v như sau: v : Ω → [0, 1] ∀Pi ∈Ω → v(Pi) Ta gọi v(Pi) là chân trị của mệnh đề Pi trên [0, 1]. 4.4.1. Phép bù Phép phủ định trong logic kinh điển là một trong những phép toán cơ bản cho việc xây dựng phép bù của 2 tập hợp. Để suy rộng phép này trong tập mờ chúng ta cần tới toán tử v(NOT P). Toán tử này phải thỏa các tính chất sau : - v(NOT P) chỉ phụ thuộc vào v(P). - Nếu v(P)=1 thì v(NOT P)=0 - Nếu v(P)=0 thì v(NOT P)=1 - Nếu v(P1) ≤ v(P2) thì v(NOT P1) ≥ v(NOT P2) Định nghĩa 1 : Trang 65
Chương 4: Lý thuyết tập mờ & Logic mờ Hàm n : [0,1] → [0, 1] không tăng thỏa mãn các điều kiện n(0) = 1, n(1) = 0, được gọi là hàm phủ định. Ví dụ : n(x) = 1 - x hay n(x) = 1 - x2 là các hàm phủ định. Ta có nhận xét : - Nếu v(P1) v(NOT P2) - v(NOT P) phụ thuộc liên tục vào v(P) - v(NOT (NOT P)) = v(P) Định nghĩa 2 (Phần bù của một tập mờ): c Cho n là hàm phủ định, phần bù A của tập mờ A là một tập mờ với hàm thuộc về được xác định bởi : µ C (a) A = n(µA(a)) , với mỗi a∈ Ω. Đồ thị của hàm thuộc về có dạng sau: x x c µA µA x x Hình a Hình b Hình a : Hàm thuộc về của tập mờ A Hình b : Hàm thuộc về của tập mờ Ac Ví dụ : với n(x) = 1 - x thì ta có : µ C (a) A = n(µA(a)) = 1-µA(a) , với mỗi a∈ Ω. Cho Ω = {1, 2, 3, 4, 5}, và A là tập mờ trong Ω như sau: A = {(1,0), (2,1), (3,0.5), (4,0.3), (5,0.2)} Ta có : c A = {(1,1), (2,0), (3,0.5), (4,0.7), (5,0.8)} Định nghĩa 3: a. Hàm phủ định n là nghiêm ngặt (strict) nếu nó là hàm liên tục và giảm nghiêm ngặt. Trang 66
Chương 4: Lý thuyết tập mờ & Logic mờ b. Hàm phủ định n là mạnh (strong) nếu nó là chặt và thỏa n(n(x)) = x , ∀x∈[0, 1]. Định nghĩa 4: Hàm ϕ = [a,b] → [a,b] gọi là một tự đồng cấu (automorphism) của đoạn [a,b] nếu nó là hàm liên tục, tăng nghiêm ngặt và ϕ(a) = a, ϕ(b) = b. Định lý 1: Hàm n:[0,1] → [0,1] là hàm phủ định mạnh khi và chỉ khi có một tự đồng cấu -1 ϕ của đoạn [0,1] sao cho N(x) = Nϕ(x) = ϕ (1 - ϕ(x)). Định lý 2 : Hàm n: [0,1] →[0,1] là hàm phủ định nghiêm ngặt khi và chỉ khi có hai phép tự đồng cấu ψ, ϕ của [0,1] sao cho n(x) = ψ (1- ϕ(x)). 4.4.2. Phép giao Phép hội AND trong logic kinh điển là cơ sở để định nghĩa phép giao của 2 tập mờ. AND thoả các tính chất sau : - v(P1 AND P2) chỉ phụ thuộc vào v(P1), v(P2). - Nếu v(P1)=1 thì v(P1 AND P2) = v(P2) , với mọi P2 - Giao hoán v(P1 AND P2) = v(P2 AND P1) - Nếu v(P1) ≤ v(P2) thì v(P1 AND P3) ≤ v(P2 AND P3), với mọi P3 - Kết hợp v(P1 AND (P2 AND P3 )) = v((P1 AND P2 )AND P3 ) Định nghĩa 5: Hàm T : [0,1]2 → [0,1] là phép hội (t-chuẩn) khi và chỉ khi thỏa các điều kiện sau: - T(1, x) = x, với mọi 0≤ x ≤1. - T có tính giao hoán, nghĩa là : T(x,y) = T(y,x), với mọi 0≤ x,y ≤1. - T không giảm theo nghĩa : T(x,y) ≤ T(u,v), với mọi x ≤ u, y ≤ v. - T có tính kết hợp : T(x,T(y,z)) = T(T(x,y),x), với mọi 0≤ x,y,z ≤1. Từ các tính chất trên có thể suy ra T(0,x) = 0. Ví dụ : T(x,y) = min(x,y) Trang 67
Chương 4: Lý thuyết tập mờ & Logic mờ T(x,y) = max(0,x+y-1) T(x,y) = x.y (tích đại số của x và y) Định nghĩa 6: Cho hai tập mờ A, B trên cùng không gian nền Ω với hàm thuộc về µA(a), µB(a), cho T là một phép hội . Ứng với phép hội T, tập giao của hai tập mờ A, B là một tập mờ trên Ω với hàm thuộc về cho bởi : µA∩B(a) = T(µA(a), µB(a)) ∀a∈Ω Với T(x,y)=min(x,y) ta có : µA∩B(a) = min(µA(a), µB(a)) Với T(x,y) = x.y ta có: µA∩B(a) = µA(a).µB(a) (tích đại số) Ta có thể biểu diễn phép giao của hai tập mờ qua hai hàm T(x,y)=min(x,y) và T(x,y) = x.y theo các đồ thị sau đây: - Hình a : Hàm thuộc về của hai tập mờ A và B - Hình b: Giao của hai tập mờ theo T(x,y) = min(x,y) - Hình c: Giao của hai tập mờ theo T(x,y) = x.y µ µ µ µB(x) µA(x) µB(x) µA(x) µB(x) µA(x) xx x Hình a Hình b Hình c Ví dụ : Cho Ω = {1, 2, 3, 4, 5}, và A, B là các tập mờ trong Ω như sau: A = {(1,0), (2,1), (3,0.5), (4,0.3), (5,0.2)} B = {(1,0), (2,0.5), (3,0.7), (4,0.2), (5,0.4)} Với T(x,y) = min(x,y), ta có : A∩B = {(1,0), (2,0.5), (3,0.5), (4,0.2), (5,0.2)} A∩Ac = {(1,0), (2,0.1), (3,0.5), (4,0.3), (5,0.2)} Trang 68
Chương 4: Lý thuyết tập mờ & Logic mờ 4.4.3. Phép hợp Phép tuyển OR trong logic kinh điển là cơ sở để định nghĩa phép hợp của 2 tập mờ. OR thoả các tính chất sau : - v(P1 OR P2) chỉ phụ thuộc vào v(P1), v(P2). - Nếu v(P1) = 0 thì v(P1 OR P2) = v(P2) , với mọi P2 - Giao hoán v(P1 OR P2) = v(P2 OR P1) - Nếu v(P1) ≤ v(P2) thì v(P1 OR P3) ≤ v(P2 OR P3), với mọi P3 - Kết hợp v(P1 OR (P2 OR P3 )) = v((P1 OR P2 ) OR P3 ). Định nghĩa 7: Hàm S :[0,1]2 → [0,1] được gọi là phép tuyển (t- đối chuẩn) nếu thỏa các tiên đề sau : - S(0, x) = x, với mọi 0≤ x ≤1. - S có tính giao hoán, nghĩa là : S(x,y) = S(y,x), với mọi 0≤ x,y ≤1. - S không giảm theo nghĩa : S(x,y) ≤ S(u,v), với mọi x ≤ u, y ≤ v. - S có tính kết hợp : S(x,S(y,z)) = S(S(x,y),x), với mọi 0≤ x,y,z ≤1. Từ các tính chất trên suy ra S(1,x) = 1. Ví dụ : S(x,y) = max(x,y) S(x,y) = min(1, x+y) S(x,y) = x + y - x.y Định nghĩa 8: Cho hai tập mờ A, B trên cùng không gian nền Ω với hàm thuộc về µA(a), µB(a). Cho S là phép tuyển , phép hợp của hai tập mờ A, B là một tập mờ trên Ω với hàm thuộc về cho bởi : µA∪B(a) = = S(µA(a), µB(a)) , ∀a∈Ω Với S(x,y) = max(x,y) ta có : µA∪B(a) = max(µA(a), µB(a)) ( xem hình a) Với S(x,y) = min(1, x+y) µA∪B(a) = min(1, µA(a) + µB(a)) (xem hình b) Với S(x,y) = x + y + x.y µA∪B(a) = µA(a) + µB(a) - µA(a).µB(a) (xem hình c) Trang 69
Chương 4: Lý thuyết tập mờ & Logic mờ Có thể biểu diễn giao của các tập mờ với các phép toán trên bằng các đồ thị sau : µ µ µ µB(x) µA(x) µB(x) µA(x) µB(x) µA(x) x x x Hình a: Hình b Hình c Ví dụ : Cho Ω = {1, 2, 3, 4, 5}, và A, B là các tập mờ trong Ω như sau: A = {(1,0), (2,1), (3,0.5), (4,0.3), (5,0.2)} B = {(1,0), (2,0.5), (3,0.7), (4,0.2), (5,0.4)} Ta có : A∪B = {(1,0), (2,1), (3,0.7), (4,0.3), (5,0.4)} A∪Ac = {(1,1), (2,1), (3,0.5), (4,0.7), (5,0.8)} 4.4.4. Một số qui tắc Trong logic rõ với hai giá trị đúng, sai, có nhiều qui tắc đơn giản mà chúng ta thường sử dụng xem như tính chất hiển nhiên. Ví dụ : với bất kỳ tập rõ A ⊂ Ω, ta có: A∩Ac = ∅ và A ∪Ac = Ω. Thực ra, những qui tắc này có được là nhờ vào sự xây dựng toán học trước đó. Chuyển sang lý thuyết tập mờ thì hai tính chất quen dùng này đã không còn đúng nữa. Do đó, chúng ta cần xem xét lại một số tinh chất. • Tính lũy đẳng (demportancy) Chúng ta nói T là lũy đẳng nếu T(x,x) = x, ∀x∈[0,1]. Tương tự, S là lũy đẳng nếu S(x,x) = x, ∀x∈[0,1]. • Tính hấp thu (absorption) Có hai dạng hấp thu : - T(S(x,y),x) = x , ∀x,y∈[0,1]. - S(T(x,y),x) = x , ∀x,y∈[0,1]. Trang 70
Chương 4: Lý thuyết tập mờ & Logic mờ • Tính phân phối (distributivity) Có hai biểu thức xác định tính phân phối: - S(x,T(y,z)) = T(S(x,y), S(x,z)), ∀x,y,z∈[0,1]. - T(x,S(y,z)) = S(T(x,y), T(x,z)), ∀x,y,z∈[0,1]. • Luật De Morgan Cho T là t-chuẩn, S là t-đối chuẩn, n là phép phủ định. Chúng ta có bộ ba (T,S,n) là một bộ ba De Morgan nếu : n(S(x,y)) = T(nx,ny) 4.4.5. Phép kéo theo Chúng ta sẽ xét phép kéo theo như một mối quan hệ, một toán tử logic. Ta có các tiên đề sau cho hàm v(P1 → P2) : - v(P1 → P2) chỉ phụ thuộc vào v(P1), v(P2). - Nếu v(P1) ≤ v(P3) thì v(P1 → P2) ≥ v(P3 → P2), ∀P2 - Nếu v(P2) ≤ v(P3) thì v(P1 → P2) ≤ v(P1 → P3), ∀P1 - Nếu v(P1) = 0 thì v(P1 → P) = 1 , ∀P. - Nếu v(P1) = 1 thì v(P → P1) = 1 , ∀P. - Nếu v(P1) = 1 và v(P2) = 0 thì v(P1 → P2) = 0. Tính hợp lý của những tiên đề này dựa vào logic kinh điển và những tư duy trực quan của phép suy diễn. Từ tiên đề ban đầu (v(P1 → P2) chỉ phụ thuộc vào v(P1), 2 v(P2)) khẳng định sự tồn tại của hàm số I(x,y) xác định trên [0,1] với mong muốn tính chân trị của phép kéo theo qua biểu thức v(P1 → P2) = I(v(P1), v(P2)) Định nghĩa 9: Phép kéo theo của một hàm số I : [0,1]2 → [0,1] thỏa các điều kiện sau : - Nếu x ≤ z thì I(x,y) ≥ I(z,y), ∀y∈[0,1]. - Nếu y ≤ u thì I(x,y) ≤ I(z,y), ∀x∈[0,1]. - I(0,x) = 1, ∀x∈[0,1]. - I(x,1) = 1, ∀x∈[0,1]. - I(1,0) = 0 Định nghĩa 10: Trang 71
Chương 4: Lý thuyết tập mờ & Logic mờ Cho T là t-chuẩn, A là t-đối chuẩn, n là phép phủ định. Hàm IS(x,y) xác định trên [0,1]2 bằng biểu thức : IS(x,y) = S(n(x),y) Ví dụ : Cho Ω = {1, 2, 3, 4, 5}, và A, B là các tập mờ trong Ω như sau: A = {(1,0), (2,1), (3,0.5), (4,0.3), (5,0.2)} B = {(1,0), (2,0.5), (3,0.7), (4,0.2), (5,0.4)} Với S(x,y) = max(x,y) và n(x) = 1 - x ta có : Is (0,0) = S(n(0),0) = 1 Is (1,0.5) = S(n(1),0.5) = 0.5 Is (0.5,0.7) = S(n(0.5),0.7) = 0.7 Is (0.3,0.2) = S(n(0.3),0.2) = 0.7 Is (0.2,0.4) = S(n(0.2),0.4) = 0.8 4.5. Logic mờ 4.5.1. Định nghĩa mệnh đề mờ Trong logic rõ thì mệnh đề là một câu phát biểu có giá trị đúng hoặc sai. Trong logic mờ thì mỗi mệnh đề mờ là một câu phát biểu không nhất thiết là đúng hoặc sai. Mệnh đề mờ được gán cho một giá trị trong khoảng từ 0 đến 1 để chỉ mức độ đúng (độ thuộc về) của nó. Ví dụ : " Nam trông khá đẹp trai" " Chiếc xe này chạy cũng được đấy". " Cô ấy sống tạm gọi là hạnh phúc". Cho Ω = {P1, P2, } với P1, P2, là các mệnh đề. Tập mờ A trên Ω tương ứng với ánh xạ v như sau: v : Ω → [0, 1] ∀Pi ∈Ω → v(Pi) Ta gọi v(Pi) là chân trị của mệnh đề Pi trên [0, 1]. Các phép toán trên mệnh đề mờ là các phép toán logic mờ dựa trên các tập mờ. Ký hiệu mức độ đúng (chân trị) của mệnh đề mờ P là v(P). Ta có : 0≤ v(P)≤ 1. Trang 72
Chương 4: Lý thuyết tập mờ & Logic mờ 4.5.2. Các phép toán trên logic mờ Các phép toán mệnh đề trong logic mờ được định nghĩa như sau: . Phép phủ định : v(P ) = 1 - v(P) . Phép tuyển : v(P1∨ P2) = max(v(P1), v(P2)) . Phép hội : v(P1∧ P2) = min(v(P1), v(P2)) Ví dụ 1: Cho P, Q, R là các mệnh đề mờ với : v(P) = 0.1, v(Q)= 0.9, v(R) = 0.8. Mệnh đề M = (P∧Q)∨R có chân trị (độ thuộc về) là : 0.8 . Phép kéo theo: v(P→Q) = v( P ∨Q) = max(v( P ), v(Q)) Ví dụ 2: Cho P, Q là các mệnh đề mờ với : v(P) = 0.1, v(Q)= 0.6 Mệnh đề v(P→Q) = v( P ∨Q) = max(v( P ), v(Q)) = max(1- 0.1, 0.6) = 0.9 4.6. Suy diễn mờ (Fuzzy inference) Suy diễn mờ hay còn gọi là suy luận xấp xỉ là quá trình suy ra những kết luận dưới dạng các mệnh đề mờ trong điều kiện của qui tắc "Nếu Thì ", với các dữ liệu đầu vào cho trước là không được rõ ràng. Thông thường, suy diễn mờ hay sử dụng luật Modus Ponnens hoặc Modus Tollen. Trong logic rõ, Modus Ponnen diễn đạt như sau: Mệnh đề 1 (Luật hoặc tri thức): P → Q Mệnh đề 2 (sự kiện): P đúng Kết luận : Q đúng Trong suy diễn mờ, luật được diễn đạt dưới dạng sau : Luật mờ : Nếu x=A thì y=B Sự kiện mờ : x=A' Kết luận : y=B' Trang 73
Chương 4: Lý thuyết tập mờ & Logic mờ trong đó A, A' là các tập mờ trên không gian nền U, B và B' là các tập mờ trên không gian nền V. Ví dụ : Luật mờ : Nếu góc tay quay ga lớn thì xe đi nhanh Sự kiện mờ : Góc tay quay khá lớn Kết luận : Xe đi khá nhanh Trong logic rõ Modus Tollen có dạng: Mệnh đề 1 (Luật hoặc tri thức): P → Q Mệnh đề 2 (sự kiện): ¬Q đúng Kết luận : ¬P đúng Trong suy diễn mờ, luật được diễn đạt dưới dạng sau : Luật mờ (hoặc tri thức mờ): P → Q Sự kiện mờ : ¬Q khá đúng Kết luận : ¬P khá đúng Ví dụ : Luật mờ : Nếu góc tay quay ga lớn thì xe đi nhanh Sự kiện mờ : Xe không đi nhanh lắm Kết luận : Góc tay quay không lớn lắm Để ứng dụng suy diễn mờ vào trong bài toán thực tế thì vấn đề mấu chốt mà chúng ta cần thực hiện đó là xây dựng cơ chế lập luận xấp xỉ. Sau đây, chúng tôi xin trình bày một ứng dụng suy luận xấp xỉ trong việc chẩn đoán bệnh lao phổi. Trong phạm vi của chương này, chúng tôi chỉ trình bày phần sơ lược về cách xây dựng suy luận xấp xỉ. Trước hết chúng ta hãy đi tìm hiểu về qui trình chẩn đoán. Hiện nay, khi một bệnh nhân đến khám tại một viện lao, bác sĩ tiến hành chẩn đoán theo các bước sau: Giai đoạn 1: khám lâm sàng - Khám ban đầu : nhìn bề ngoài (tóc, da, mắt, ) - Hỏi về tình trạng của cơ thể bệnh nhân để có thêm nhiều thông tin. - Từ các triệu chứng lâm sàng tiến hành chẩn đoán khẳng định khả năng mắc bệnh của bệnh nhân. Trang 74
Chương 4: Lý thuyết tập mờ & Logic mờ - Nếu hết giai đoạn này, bác sĩ không có nghi ngờ gì về bệnh lao, ông ta sẽ đưa ra câu trả lời phủ định bệnh lao và có thể gợi ý về khả năng bệnh nhân mắc một khác. Bệnh nhân sẽ được khuyên là nên quay lại nếu bệnh nặng hơn mà không rõ căn nguyên. - Ngược lại, nếu tới cuối giai đoạn lâm sàng bệnh nhân bị nghi là đã mắc bệnh lao thì giai đoạn chẩn đoán thứ hai sẽ được tiến hành để có kết luận chắc chắn. Giai đoạn 2: khám cận lâm sàng - Khám nghiệm đờm, - Chụp X quang. Hầu hết các triệu chứng cận lâm sàng đều có ảnh hưởng rất mạnh đến khả năng mắc bệnh của bệnh nhân. Vì vậy, bệnh trạng được khẳng định hoặc loại trừ một cách chắc chắn trong giai đoạn này. Sau đó, bác sĩ sẽ có kết luận và đưa ra một phương án điều trị thử. Nếu bệnh trầm trọng thì bệnh nhân được điều trị lao phổi thử, nếu không quá trầm trọng thi điều trị bắng kháng sinh. Bởi vì, nếu thực tế không phải là lao phổi mà chỉ bị viêm phổi thì điều trị kháng sinh sẽ đem lại kết quả tích cực. Ngược lại, nếu thực sự mắc bệnh lao phổi thì chỉ phương án điều trị lao phổi mới có tác dụng. Toàn bộ qui trình được thể hiện qua lược đồ sau: Trang 75
Chương 4: Lý thuyết tập mờ & Logic mờ Chẩn đoán lâm sàng Không bệnh lao phổi Nghi ngờ bệnh lao phổi Chẩn đoán cận lâm sàng Khẳng định lao phổi Loại trừ lao phổi Không có kết luận Điều trị lao phổi Điều trị thử Bệnh nặng Bệnh không quá nặng Thử Điều trị lao phổi Thử Điều trị kháng sinh không hiệu quả Hiệ u quả tốt không hiệu quả Hiệ u quả tốt Khẳng định và điều trị lao phổi Loại trừ lao phổi Trang 76
Chương 4: Lý thuyết tập mờ & Logic mờ Xây dựng suy diễn xấp xỉ : Có 3 đối tượng mà chúng ta cần quan tâm : 1. Bệnh nhân : ký hiệu là P (Patient) 2. Các triệu chứng : S (Symptom) Bao gồm : lâm sàng, cận lâm sàng, gọi chung là các triệu chứng. Ta có : S = {S1, S2, , Sn} 3. Bệnh cần chẩn đoán : lao phổi D (Disease) Nhận thấy giữa các đối tượng trên xuất hiện những quan hệ mờ : Quan hệ triệu chứng - bệnh nhân : RSP Quan hệ này được sử dụng làm thông tin đầu vào cho cơ chế lập luận trong quá trình chẩn đoán, được xác định bởi µSP ∈[0,1]. Giá trị này thể hiện mức độ xuất hiện của triệu chứng S trên bệnh nhân P. Nói cách khác, RSP là một tập mờ có hàm thuộc về xác định như sau: µSP : RSP → [0,1] Với µSP = 0 có nghĩa là chắc chắn bệnh nhân không có triệu chứng S. Với µSP = 1 có nghĩa là chắc chắn bệnh nhân có triệu chứng S. Với 0 < µSP < 1 có nghĩa là bệnh nhân có triệu chứng S với mức độ xuất hiện là µSP. Ví dụ : Giả sử để xem xét mức độ sốt của bệnh nhân để đưa ra liều luợng thuốc, có các phát biểu mờ (luật mờ) như sau : • IF sốt nhẹ THEN liều lượng asperine thấp • IF sốt THEN liều lượng asperine bình thường • IF sốt cao THEN liều lượng asperine cao • IF sốt rất cao THEN liều lượng asperine cao nhất Trang 77
Chương 4: Lý thuyết tập mờ & Logic mờ SN S SC SRC 37 38 38.7 39 40 41 oC TBT CCN 0 200 400 600 800 1000 mg Thông thường người ta sẽ thực hiện 3 bước: – Mờ hóa (fuzzyfication) giá trị nhập vào – Suy luận Mờ – Khử tính mờ (defuzzyfication) cho giá trị xuất ra Vậy nếu bệnh nhân sốt ở 38.7 độ => liều lượng kê đơn là 480mg Phần => là cả quá trình khử tính mờ (làm rõ hóa) chúng tôi không trình bày chi tiết ở đây, có thể dựa vào đồ thị để suy ra kết quả. Ngoài ra, đôi khi bác sĩ phải đi đến kết luận "không rõ" đối với một triệu chứng nào đó. Khi đó, µSP được định nghĩa là một giá trị rất bé như sau: µSP = ε ≈ 0 Kế tiếp, chúng ta phải xác định quan hệ bệnh nhân - bệnh lao phổi : RPD . Xác định mối quan hệ này cũng có nghĩa là đưa ra kết quả chẩn đoán về khả năng mắc bệnh của bệnh nhân. 4.7. Tổng kết chương 4 Tất cả những kiến thức trình bày trong chương này chỉ là phần cơ bản của lý thuyết tập mờ và logic mờ. Chúng tôi không đi sâu vào chi tiết mà chỉ nhằm mục đích trình bày các khái niệm và các phép toán để sinh viên nắm bắt được vấn đề là bên cạnh logic rõ còn có logic mờ. Sinh viên có thể tìm hiểu sâu hơn về logic mờ ở năm thứ tư trong phần ứng dụng logic mờ vào điều khiển tự động hóa (dành cho lớp điện tử) hay ứng dụng logic mờ trong trí tuệ nhân tạo. Tuy vậy, hy vọng rằng với các cơ sở kiến thức nền về logic mệnh đề, suy luận toán học, vị từ và lý thuyết tập mờ trong giáo trình này là hành trang hữu ích để đi vào các tri thức cao hơn. Trang 78
Chương 4: Lý thuyết tập mờ & Logic mờ 4.8. Bài tập chương 4 1. Cho Ω = {6, 2, 7, 4, 9}, các tập mờ A, B, C trên Ω tương ứng với ánh xạ µA , µB và µC như sau: A = {(6,0.2), (2,0.9), (7,0.5), (4,0.3), (9,0.2)} B = {(6,0), (2,1), (7,0.5), (4,0.6), (9,0.1)} C = {(6,0.3), (2,0.1), (7,1), (4,0), (9,0.5)} a/ Tính các tập AC, BC và CC với hàm thuộc về là 1-x b/ Tính A∩B, B∩C, A∩B∩C, A∩CC, A∩CC với T(x,y) = min(x,y) c/ Tính A∪B, B∪C, A∪B∪C, A∪CC, A∪CC với S(x,y) = max(x,y) 2. Cho các tập mờ A,B,C được định nghĩa trên nền số nguyên Ω = [0,5] với các hàm x 1 thuộc về như sau: µA = và µB = x + 2 x Hãy xác định các tập mờ sau ở dạng liệt kê và đồ thị : a/ Tính các tập AC, BC và CC với hàm thuộc về là 1-x b/ Tính A∩B, B∩C, A∩B∩C, A∩CC, A∩CC với T(x,y) = min(x,y) c/ Tính A∪B, B∪C, A∪B∪C, A∪CC, A∪CC với S(x,y) = max(x,y) 3. Thiết lập mô hình phân loại sinh viên qua các tập mờ sinh viên cần cù, sinh viên thông minh và sinh viên lười. 4. Cho A là tập mờ xác định trên nền X. Hãy chỉ ra rằng biểu thức A∩CC = X không đúng như đối với tập họp kinh điển. 5. Kiểm tra xem tập mờ A, B với các hàm thuộc về xác định ở bài tập 2 là thỏa hai công thức của De Morgan. Trang 79
Chương 4: Lý thuyết tập mờ & Logic mờ CHƯƠNG 4 : LÝ THUYẾT TẬP MỜ & LOGIC MỜ 61 4.1. Tổng quan 61 4.2. Giới thiệu 61 4.3. Khái niệm tập mờ (fuzzy set) 62 4.4. Các phép toán về tập mờ 65 4.4.1. Phép bù 65 4.4.2. Phép giao 67 4.4.3. Phép hợp 69 4.4.4. Một số qui tắc 70 4.4.5. Phép kéo theo 71 4.5. Logic mờ 72 4.5.1. Định nghĩa mệnh đề mờ 72 4.5.2. Các phép toán trên logic mờ 73 4.6. Suy diễn mờ (Fuzzy inference) 73 4.7. Tổng kết chương 4 78 4.8. Bài tập chương 4 79 Trang 80
Predicates and Quantiﬁers: Suggested Exercises 1. Write each of the following expressions so that negations are only applied to propositional functions (and not quantiﬁers or connectives). (a) ¢¡¤£¦¥¨§© £¢§© (b) ¡¦£¤¥¨§ £§©¥¨£¦ ¢¡¤§ £§© (c) ¢¡¤£¥¨§ £§©¡¤§© £¢§ (d) ¢¡¤£¦ ¥¨§! ¢¡¦"# £"¨ $%¥"¨ £§¦"¨ ¥"( §¦£"¨!) §¦"(£¦!* £¢§¤+"#-,#¥"¨ £¢"¨ (e) ¥¨£& ¢¡¤§!' £ § £ § 2. Let £§© =” likes ”, where the universe of discourse for and is the set of all people. For each of the following, translate the expression to English, and tell the truth value. (a) ¡¤£©¡¤§ £§© (b) ¡¤£¦¥¨§ £¢§© (c) ¡¤§©¥¨£¤ £¢§© (d) ¡¤£¤ £¢/.10©2¦354© (e) ¢¡¤£©¡¤§ £§© (f) ¡¤£¦ ¢¡¤§ £§© (g) ¡¤£¦ ¢¡¤§© £§© £(6879§6;: ¡!"= £¢§¤+"# (c) ¡¤£¦¥¨§©¥"= £¢§¤+"# (d) ¡¤£©¡¤§©¥"# £¢§¦"¨ (e) ¡¤£¦¥¨§=¡¦"# £¢§¦"¨ (f) ¥¨£¦¥¨§©¥"= £¢§¤+"# (g) ¥"# ?+@©+"# (h) ¥¨£¤¥§¨ £¢§¤/A> (i) ¥¨£¦¥¨§ £¢§¦@= 4. Write each of the following sentences using quantiﬁers and propositional functions (if it is possible). (a) All disc golfers play ultimate frisbee. (b) If all students in my class do their homework, then some of the students will pass. (c) If none of the students in my class study, then all of the students in my class will fail. (d) Not everybody knows how to throw a frisbee 300 feet. (e) Some people like ice cream, and some people like cake, but everybody needs to drink water. (f) Everybody loves somebody. (g) Everybody is loved by somebody. (h) Not everybody is loved by everybody. (i) Nobody is loved by everybody. (j) You can’t please all of the people all of the time, but you can please some of the people some of the time. (k) If only somebody would give me some money, I would buy a new house. (l) Nobody loves me, everybody hates me, I’m going to eat some worms. (m) Every rose has it’s thorn, and every night has it’s dawn.
Rules of Inference Tautology Rule p→(p∨q) Addition (p∧q)→p Simplification ((p)∧(q))→ (p∧q) Conjunction [p∧(p→q)]→q Modus Ponens [¬q∧(p→q)]→¬p Modus Tollens [(p→q)∧(q→r)]→(p→r) Hypothetical Syllogism [(p∨q) ∧¬p]→q Disjunctive Syllogism (p→q)→ (¬q→¬p) Contrapositive Rules of Inference for Quantifiers ∀x P(x) Universal instantiation ∴ P(c) if c∈U P(c) for arbitrary c∈U Universal generalization ∴ ∀x P(x) ∃x P(x) Existential instantiation ∴ P(c) for some c∈U P(c) for some c∈U Existential generalization ∴ ∃x P(x)
Equivalence Relations ¡ Deﬁnition: A relation on a set is called an equivalence relation if it is reﬂexive, symmetric, and transitive. Recall the deﬁnitions: ¢ ¡ ¤ ¤ ¨ ¦ reﬂexive: £¥¤ §©¨ for all . ¢ ¡ ¤ ¤ ¨ ¨ ¦ ¦ ¦ £ § symmetric: £¥¤ §©¨ when , for . ¢ ¤ ¤ ¨ ¨ ¦ ¦ ¦ £ § transitive: £ §©¨ and £ § implies , ¡ ¤ ¨ for ¦ ¦ . If two elements are related by an equivalence relation, they are said to be equivalent. 1
Examples 1. Let be the relation on the set of English words such that if and only if starts with the same letter as . Then is an equivalence relation. 2. Let be the relation on the set of all human beings such that if and only if was born in the same country as . Then is an equivalence relation. 3. Let be the relation on the set of all human beings such that if and only if owns the same color car as . Then is an not equivalence relation. 2
¤ Pr is Let ¢ ¢ an oof: is If Since Thus, equi ¤ symmetric. is By reﬂe v ¤ alence deﬁnition, be , Congruence for xi ¤ a ¤ v positi e. some relation. £ , ¤ v then e inte £ ¤ § inte ¦ ¤ ger , § , and ger we ¤ 3 . . we ha Then Modulo Using v e ha if that v the and , e this,we for ¤ relation only some ¤ ¤ proceed: if inte ger , , so and .
Therefore, ¢ ¤ and If ¤ ¤ we congruence ha v e £ ¤ ¤ and , and §"! modulo £ 4 , § and , for is an inte ! is equi , then gers transiti v alence we and v £ ha e. ! v relation e . Thus, § ¦
¡ Deﬁnition: Let be an equivalence relation on a set . The equivalence class of¤ is ¤ ¤ ¨ % ¦ £ § # $ '& ¤ % In words, # $ is the set of all elements that are related to the ¡ ¤ element ¨ . If the relation is clear, we can omit the ¤ ¤ % # $ subscript (i.e. # $ instead of ). ¤ ¨ % If # $ , then is called a representative of the equivalence class. 5
Examples Continued 1. The equivalence class of Xenon is all words starting with the letter X. That is, is an English word starting with the letter X # Xenon $ 2. The equivalence class of Chuck Cusack is all people born in the United States of America. That is, ¡ ¡ is a person that was born in the U.S.A. $ # Chuck Cusack 6
¤ Thus, The # $ ( . congruence Example: #*2 $43 # #*) $ 0 $ + class # Congruence $43 & '& & of & & & an ¦ & ¦ & & inte , 1 ¦ ¦ 7 ¦ ger . , - Classes ¦ ¦ ¤ ) ¦ ) ¦/. ¦/. modulo ¦ ¦ ¦ ) ¦ 2 1 Modulo & ¦ & ¦/5 ¦ & & & & & ¦ & & is denoted by
Equivalence Classes and Partitions ¡ Theorem 1: Let be an equivalence relation on a set . The following statements are equivalent: & - & & ¤ ¤ ¤ ) 9 8 # $ # $ # $76 # $ - - ) ) : : Proof: Show that : , , and . Notice that this theorem says that if the intersection of two equivalence classes is not empty, then they are equal. That is, two equivalence classes are either equal or disjoint. 8
of ( Deﬁnition: nonempty > is ; ¡ ¡ A is an of , ; e subsets whose xample, of = 8 a set @ ¦ 9 union ¡ and ; often collection > ; such . That ¦ that - & is, ¦ & of & a disjoint ¦D partition .)
; Theorem 2: Let be an equivalence relation on a set . Then the equivalence classes of form a partition of ; . ¡ > = ; ¨ ¡ = ¨ is an equivalence relation that has the sets < , , as its equivalence classes. Proof (informal): The equivalence classes of an equivalence ¤ ¤ ¨ % relation are nonempty (since # $ ), and by Theorem 1 are disjoint. Since every element of the set ; is in some ¤ ¤ ¨ % equivalence class (e.g. # $ ), the equivalence classes partition ; . 10
the Deﬁne No some Example: (Proof w equi , assume = . of a v It relation alence Theorem is W not e we EGF can E E E7X E U Z P classes +JI H hard +\I +JI +JI +SI H H H H on ha partition 2, v ; e K7L to K7L K7L K7L K7L continued) L a by L L L L L modulo L L L L see partition ¤ MON M M M M N N N N V [ that the P Y T F MON MON MON MON 11 M N if 2 set X this U Z P and Q M M M M as X M U Z P F ¡ of M M MW[ MWV is M follo ¤ L R R7L R R R ¦ v M M M according of M ¨ alence a ¡ set < for relation ; . to
w English Example: same ords letter as w follo ords _ ¤ # #ed # as Let = $ ^ f ¤` ws: $ deﬁned . $ Then be & & & the we by ¤ d equi ^ ^ ¦ _ can ¤ ¦ D] ¤ v = 12 a alence partition ¦ ¦ ¤ d ¦ _ if ` D ^ and ^ ` ¤ ¦ d ¦ ¤ relation = only ¦ _ f ^ the ¦ d & ¦ bc b & if set & b D & ¦ on & & ¦ of & ¦ & starts & the & English ¦ set with of the
Logical Equivalences Equivalence Name p∨T ⇔ T Domination laws p∧F ⇔ F p∧T ⇔ p Identity laws p∨F ⇔ p p∨p ⇔ p Idempotent laws p∧p ⇔p ¬(¬p) ⇔p Double negation law p∨¬p ⇔ T Cancellation laws p∧¬p ⇔ F (Unofficial name) p∨q ⇔ q∨p Commutative laws p∧q ⇔ q∧p (p∨q)∨r ⇔ p∨(q∨r) Associative laws (p∧q)∧r ⇔ p∧(q∧r) p∨(q∧r) ⇔ (p∨q)∧(p∨r) Distributive laws p∧(q∨r) ⇔ (p∧q)∨(p∧r) ¬(p∧q) ⇔ ¬p∨¬q De Morgan’s laws ¬(p∨q) ⇔ ¬p∧¬q (p→q) ⇔ (¬p∨q) Implication law