Bài giảng Luận lý toán học - Chương 1: Tổng quan (Phần 1)

Nội dung text: Bài giảng Luận lý toán học - Chương 1: Tổng quan (Phần 1)

1. LUẬN LÝ TỐN HỌC (Mathematical Logic) Nguyễn Thanh Sơn Khoa KHMT&CN ĐH Bách Khoa TpHCM email : ntson@cse.hcmut.edu.vn http:\\www.cse.hcmut.edu.vn\~ntson ntsơn
2. NỘI DUNG Chương 1. Tổng quan Chương 2. Luận lý mệnh đề (propositional logic) Chương 3. Luận lý vị từ (predicates logic) Chương 1 ntsơn
3. Chương 1. Tổng quan ntsơn
4. Nhất quán & Mâu thuẫn Một người phát biểu rằng : ”Thật sai lầm khi kiểm duyệt các chương trình truyền hình cĩ tính chất bạo lực, vì hành vi con người khơng bị ảnh hưởng từ những điều họ nhìn thấy trên truyền hình. Tuy nhiên sẽ cĩ ích khi trình chiếu trên truyền hình những hình ảnh tốt đẹp về đất nước, vì nĩ sẽ làm cho những người chống đối chính quyền thấy được hành vi chống đối của mình là vơ nghĩa”. Chương 1 ntsơn
5. Nhất quán & Mâu thuẫn Nếu tín lý thứ nhất là hành vi con người khơng bị ảnh hưởng bởi truyền hình là đúng, thì tín lý thứ hai là nội dung trên truyền hình khơng thể làm thay đổi hành vi của người chống đối. Do đĩ người ta gọi hệ thống tín lý này là khơng nhất quán hay mâu thuẫn vì cĩ hai tín lý khơng đồng thời cùng đúng trong mọi tình huống. Chương 1 ntsơn
6. Nhất quán & Mâu thuẫn Một lớp các tín lý được gọi là nhất quán nếu cĩ một hồn cảnh mà tất cả tín lý cùng được gán giá trị đúng. Ngược lại, là khơng nhất quán nếu trong mọi hồn cảnh tất cả các tín lý đều khơng thể cùng được gán giá trị đúng. Khơng nhất quán cịn được gọi là mâu thuẫn. Chương 1 ntsơn
7. Nhất quán & khơng cĩ giá trị Một người tin rằng “Trái đất là trung tâm của vũ trụ nên mặt trời xoay chung quanh trái đất “. Hệ thống này là nhất quán nhưng khơng nhất quán với kiến thức đang biết. Nghĩa là các hệ thống tín lý được đề cập đến khơng chứa các tín lý tiềm ần, mặc nhiên. Logic chỉ khảo sát các tín lý hiển hiện, được chỉ định rõ ràng. Chương 1 ntsơn
8. Nhất quán & Mâu thuẫn Ngồi ra, sự mơ hồ của biểu diễn tín lý cĩ thể làm hệ thống khơng nhất quán. Do người ta cĩ thể hiểu các tín lý theo một cách nào đĩ để hệ thống trở thành khơng nhất quán. Chương 1 ntsơn
9. Nhất quán & Mâu thuẫn Kiểu nhất quán trong logic là sự tương thích giữa các tín lý. Sự tương thích ở đây là việc đồng thời cùng đúng của các tín lý. Logic khơng quan tâm những kiểu nhất quán khác. Chương 1 ntsơn
10. Lịch sử logic[12] Logic là nền tảng của tất cả lý luận “cĩ lý”. Người Hy lạp cổ đã nhận ra vai trị của logic trong tốn học và triết học. Một luận đề cĩ tính hệ thống về logic xuất hiện đầu tiên trong tác phẩm Organon của Aristotle. Tác phẩm này cĩ ảnh hưởng lớn lên triết học, khoa học, tơn giáo, suốt thời kỳ trung cổ. Chương 1 ntsơn
11. Lịch sử logic[12] Logic của Aristotle được diễn tả bằng ngơn ngữ thơng thường -> mơ hồ. Các triết gia muốn logic được diễn tả cĩ tính hình thức (formal) và bằng ký hiệu (symbolical) như tốn học. Leibniz cĩ lẽ là người đầu tiên hình dung ra ý tưởng này và gọi tên là formalism. Chương 1 ntsơn
12. Lịch sử logic[12] Từ symbolic logic xuất hiện trong ấn bản năm 1847 cĩ tên The Mathematical Analysis of Logic của G. Boole và Formal Logic của A. De Morgan. Logic lúc này được xem là một phần của tốn học. Đánh dấu sự nhận thức rằng tốn học khơng chỉ là số (arithmetic) và hình (geometry) mà bao gồm các chủ đề được diễn tả bằng ký hiệu + các quy luật và các thao tác trên ký hiệu. Chương 1 ntsơn
13. Lịch sử logic[12] Từ thời Boole và DeMorgan, logic và tốn học quyện vào nhau chặt chẽ. Logic là thành phần của tốn học đồng thời là ngơn ngữ của tốn học. Cuối thế kỷ 19 và đầu thế kỷ 20 người ta tin rằng tất cả các ngành tốn học cĩ thể được giản lược vào symbolic logic và làm cho nĩ trở thành thuần tuý hình thức. Chương 1 ntsơn
14. Lịch sử logic[12] Vào những năm 1930, niềm tin này bị lung lay bởi K. Gưdel. K. Gưdel chỉ ra rằng luơn luơn cĩ các chân lý (truths) khơng thể dẫn xuất được từ bất kỳ hệ thống hình thức nào. Chương 1 ntsơn
15. Logic Thuật ngữ : Luận lý học (tiếng Việt) Logos (tiếng Hy lạp) Hướng tiếp cận truyền thống, logic là một ngành của triết học. Ngày nay (từ thế kỷ 19), logic là một ngành của tốn học. Chương 1 ntsơn
16. Logic Thuật ngữ symbolic logic được dùng để đối kháng với philosophical logic. Symbolic logic cịn cĩ tên là metamathematics. Sau này symbolic logic cĩ tên là Mathematical logic do Giuseppe Peano đặt. Mathematical logic là logic được mơ hình và nghiên cứu một cách tốn học. Chương 1 ntsơn
17. Logic Cơ bản mathematical logic vẫn là logic của Aristotle. Từ quan điểm ký hiệu thì mathematical logic là một ngành của đại số trừu tượng (abstract algebra). Chương 1 ntsơn
18. Logic[Factasia] Theo Factasia : Logic là cơ sở hợp lý và là nền tảng cho tốn học, cho khoa học, cho kỹ thuật, và đặc biệt cho cơng nghệ thơng tin. Chương 1 ntsơn
19. Logic[Factasia] Đối với các chuyên gia máy tính. Một ngơn ngữ hình thức cĩ cú pháp và ngữ nghĩa chặt chẽ và các qui luật dẫn tới các lý luận đúng sẽ trở thành một logic. Chương 1 ntsơn
20. Logic[Factasia] Đối với các nhà tư tưởng. Logic là việc nghiên cứu về những sự thật và những hệ thống hình thức dẫn xuất ra các sự thật, đồng thời khám phá ý nghĩa triết học của các sự thật. Chương 1 ntsơn
21. Mục tiêu của Logic • Khảo sát lý luận trong thế giới thực. – Tương quan giữa các phát biểu của 1 ngơn ngữ hình thức hoặc phi hình thức (consistency, entailment, ). • Mơ hình hĩa lý luận của thực tế. – Hệ thống chứng minh (proof). Chương 1 ntsơn
22. Phân loại[1] • Inductive logic cĩ quá trình lý luận từ những trường hợp cá biệt suy ra một kết luận tổng quát. • Deductive logic cĩ quá trình lý luận từ một phát biểu tổng quát suy ra một kết luận cá biệt. Chương 1 ntsơn
23. Inductive & Deductive logic[1] • Inductive – Được dùng trong tình huống khơng đầy đủ thơng tin. – Thời gian lấy thơng tin lâu. – Chi phí để cĩ thơng tin cao.  kết luận tạm thời và để thống kê. • Deductive – Kết luận chính xác – Nghèo nàn Chương 1 ntsơn
24. Định nghĩa Logic[2] • Ngơn ngữ hình thức là ngơn ngữ cĩ : – cú pháp – ngữ nghĩa và – hệ thống chứng minh. • Logic là 1 ngơn ngữ hình thức. Chương 1 ntsơn
25. Định nghĩa Logic[2] • Cú pháp cho biết cái gì được logic chấp nhận. • Ngữ nghĩa là ý nghĩa thực tế của các đối tượng trong logic. • Cú pháp là hình thức cịn ngữ nghĩa là nội dung của các đối tượng trong logic. • Hệ thống chứng minh sản sinh các đối tượng mới từ các đối tượng cĩ sẵn. Chương 1 ntsơn
26. Chương 2 : Luận lý mệnh đề ntsơn
27. Nội dung I. Cấu trúc của luận lý mệnh đề (LLMĐ) II. Suy luận tự nhiên trong LLMĐ III. Ngữ nghĩa của LLMĐ Chương 1 ntsơn
28. I. Cấu trúc của luận lý mệnh đề ntsơn
29. Thuật ngữ[11] • Luận lý mệnh đề (LLMĐ) cĩ tên tiếng Anh : – Propositional logic. – Propositional Calculus. • Từ calculus là một thuật ngữ chung cho bất kỳ lãnh vực tốn học liên quan tới việc tính tốn (calculating). Thí dụ : số học được gọi là calculus of numbers. Chương 1 ntsơn
30. Khảo sát 1 định nghĩa LLMĐ[11] • Propositional Calculus là việc tính tốn trên các mệnh đề (propositions hoặc statement). Mệnh đề là câu khai báo cĩ giá trị đúng (T) hoặc sai (F).  xuất hiện một số vấn đề : - định nghĩa câu khai báo ? - dựa vào đâu để đánh giá đúng sai ? Chương 1 ntsơn
31. Đối tượng khảo sát của LLMĐ • Các loại câu của ngơn ngữ tự nhiên (NNTN) được định nghĩa từ Văn Phạm của NNTN. • LLMĐ chỉ khảo sát câu khai báo. • Câu khai báo thỏa một số điều kiện được LLMĐ gọi là cơng thức nguyên (atom). • Cơng thức nguyên (CTN) là phần tử cơ bản của LLMĐ. Chương 1 ntsơn
32. Câu khai báo Thí dụ : “trời sẽ mưa" là câu khai báo. “hãy đi ra khỏi lớp" khơng là câu khai báo. "2+2 = 4" là câu khai báo. "1 = 0" là câu khai báo. Chương 1 ntsơn
33. Câu khai báo Thí dụ : * Đại số là một ngành tốn học. (đ) * Mọi người cần cĩ một đức tin. (đ|s) * Mặt trời là một khối vuơng. (đ|s) * “2+2 = 4”. (đ|s) * A. Lincoln đã là tổng thống của Mỹ. (đ) Chương 1 ntsơn
34. Cơng thức nguyên • Cơng thức nguyên là câu khai báo : - được biểu diễn bằng một ký hiệu. - đánh giá được đ, s. - sự đánh giá đúng sai khơng thay đổi theo khơng gian & thời gian. • Giá trị đúng sai của 1 câu khai báo được gọi là thực trị (truth value). Chương 1 ntsơn
35. Cơng thức nguyên Thí dụ : “Đồn Thị Điểm là dịch giả của Chinh phụ ngâm” → được ký hiệu là A (trong LLMĐ). “Mặt trời xoay quanh trái đất”. → được ký hiệu là B. “Nếu hàm số f liên tục thì f khả vi”. → được ký hiệu là C. “Phong đi câu cá vào ngày chúa nhật”. → được ký hiệu là D. Chương 1 ntsơn
36. Cơng thức • Thế giới thực tạo sự liên kết giữa câu để tăng khả năng diễn đạt. • Luận lý mệnh đề cũng mơ phỏng lại sự liên kết này. (A→B)(C(D)) Câu + câu + câu + câu Luận lý mệnh đề Thế giới thực Chương 1 ntsơn
37. Tốn tử • Chỉ một số liên từ trong thế giới thực được mơ phỏng lại trong LLMĐ thành các tốn tử. hoặc, hay,  và,  nếu thì , → khơng,  tương đương,  Luận lý mệnh đề Thế giới thực Chương 1 ntsơn
38. Cơng thức • Cơng thức hồn hảo là sự kết hợp hữu hạn lần các cơng thức nguyên bằng các tốn tử , , , →. • Cơng thức hồn hảo (well-formed formula - WFF) được gọi tắt là cơng thức (CT). Chương 1 ntsơn
39. Đại số Boolean • Luận lý mệnh đề được biểu diễn dưới dạng một cấu trúc đại số. • , với B là tập cơng thức nguyên. Chương 1 ntsơn
40. Cây phân tích • Cây phân tích (parse tree) là biểu diễn bằng đồ thị của một cơng thức. Cây phân tích là cây nhị phân cĩ gốc, đỉnh là tốn tử và lá là CT nguyên. Thí dụ : (Q → P)  ((Q → Q)  Q)  →   P → R Q Q R Chương 1 ntsơn
41. Cây phân tích • Đường (path) của một cây phân tích là một hành trình đi từ gốc đến đỉnh lá. Thí dụ :  →  X  X  Z Y Chương 1 ntsơn
42. Cây phân tích • Chiều cao của 1 cây phân tích là số cạnh của con đường dài nhất cộng 1. Thí dụ :    →  → → X  X Z Y Z X   Chiều cao là 4 Y Z X Chiều cao là 5 Chương 1 ntsơn
43. Vấn đề của các tốn tử • Các liên từ “or”, “xor”. Tên cướp mang súng hoặc dao : S  D. (cĩ thể cả 2) Con dao được làm bằng sắt hoặc gỗ : S  G. (chỉ một trong hai) Chương 1 ntsơn
44. Vấn đề về “và”[11] • P : “Thiên hà này sẽ biến mất vào lỗ đen của vũ trụ" và Q : "2+2 = 4," cái gì là P  Q? Giải P  Q : “Thiên hà này sẽ biến mất vào lỗ đen của vũ trụ và 2+2=4," cách diễn đạt sau sẽ làm ngạc nhiên : “Khơng những thiên hà này sẽ biến mất vào lỗ đen của vũ trụ mà cịn cĩ 2+2=4 " (not only but). Chương 1 ntsơn
45. Vấn đề về “và”[11] • Đánh giá mệnh đề P  (Q) ? Giải P  (Q) cĩ nghĩa là : " Thiên hà này sẽ biến mất vào lỗ đen của vũ trụ" và 2+2 ≠ 4," hoặc nĩi cách khác : " Thiên hà này sẽ biến mất vào lỗ đen của vũ trụ" hơn thế nữa (moreover) hai cộng hai khác bốn. Chương 1 ntsơn
46. Hết slide Chương 1 ntsơn
47. Bài tập Chương 2 : Luận lý mệnh đề ntsơn
48. Câu khai báo 1. Phát biểu nào là câu khai báo và chỉ ra thực trị : a. Khơng được mở máy tính. b. Thành phố Mỹ Tho ở đâu ? c. Ở sơng Sài Gịn khơng cĩ cá sấu. d. Việc lập trình rất hứng thú. e. A(BC) = (AB)(AC), A,B,C là tập hợp. f. Hơm nay là ngày thứ 3. g. 2 + 3 = 6. h. Hà Nơi là thủ đơ của VN. i. Thiết kế CSDL là bắt buộc khi lập trình. Chương 1 ntsơn
49. Câu khai báo 2. Tìm phủ định của các câu khai báo sau : a. Ở sơng Sài Gịn khơng cĩ cá sấu. b. A(BC) = (AB)(AC). c. Hơm nay là ngày thứ 3. d. 2 + 3 = 6 e. Hà Nơi là thủ đơ của nước VN. f. Nếu cĩ tiền tơi sẽ mua xe phân khối lớn. g. Thiết kế CSDL là bắt buộc khi lập trình. h. Tơi tới lớp mỗi khi gần cĩ kỳ thi. i. Số x là nguyên tố nếu nĩ khơng cĩ ước số khác 1, x. Chương 1 ntsơn
50. Câu khai báo 3. Biểu diễn đoạn văn sau bằng luận lý mệnh đề : Nếu anh ta mua xe thì anh ta trúng số hoặc thừa hưởng gia tài. Anh ta khơng thừa hưởng gia tài. Vậy nếu anh ta khơng trúng số thì anh ta khơng mua xe. Chương 1 ntsơn
51. Câu khai báo 4. Diễn tả các cơng thức luận lý mệnh đề bằng các phát biểu (câu khai báo) : M = Hơm nay thứ 5, N = Đi dã ngoại P = Câu cá. 1. M → (N  P) 2. M  N 3. P  M 4. N → M 5. M  (P  N) Chương 1 ntsơn
52. Hết slide Chương 1 ntsơn