LOGIC trong khoa học máy tính

Chia sẻ: 124357689 124357689 | Ngày: | Loại File: PDF | Số trang:124

Thêm vào BST

Báo xấu

117
lượt xem 28
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mình cũng như các bạn, khi học môn logic này đã gặp phải những khó khăn khi tiếp cận nó. Mình được biết rằng, nhiều bạn cũng vì khi mở nó ra toàn bằng tiếng Anh, mở từ điển ra để dịch thì vẫn rất khó hiểu nhiều lúc ghép lại cũng không nhìn ra được vấn đề nên việc học nhiều lúc cũng bí. Nên mình xin mạn phép được dịch nó ra, cũng coi như là một tài liệu để các bạn dùng song song với tài liệu của thầy phát để tham khảo thêm, cũng như giúp cho các bạn trình độ tiếng...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: LOGIC trong khoa học máy tính

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG LOGIC (Bản dịch) 1
Lời nói đầu Mình cũng như các bạn, khi học môn logic này đã gặp phải những khó khăn khi tiếp cận nó. Mình được biết rằng, nhiều bạn cũng vì khi mở nó ra toàn bằng tiếng Anh, mở từ điển ra để dịch thì vẫn rất khó hiểu nhiều lúc ghép lại cũng không nhìn ra được vấn đề nên việc học nhiều lúc cũng bí. Nên mình xin mạn phép được dịch nó ra, cũng coi như là một tài liệu để các bạn dùng song song với tài liệu của thầy phát để tham khảo thêm, cũng như giúp cho các bạn trình độ tiếng Anh còn yếu biết, tạm thời có tài liệu để có thêm thời gian chuẩn bị trình độ tiếng Anh của mình chuẩn bị với các môn chuyên nghành tiếp theo tốt hơn. Vì tài liệu các môn chuyên nghành về sau này, theo như các thầy nói thì nói chung hầu hết là tiếng Anh. Các bạn không nên chỉ dùng tài liệu này, mà hãy dung tài liệu của thầy đã phát và chỉ dùng tài liệu này như để tham khảo thêm mà thôi. Mình không dịch hết tất cả mà chỉ dịch những phần nào mà thầy đã dạy, và liên quan đến logic mà thôi để các bạn không học thầy Hải cũng có thể tiếp cận được với tài liệu. Cụ thể là sau khi tham khảo các lớp và các khoá mình dịch các phần sau: 2
- Lecture 1: từ trang 6-42 - Lecture 2: từ trang 4-28 - Lesson 4: từ slide 4.2- 4.30 - Lesson 5: từ slide 5.2- 5.20 Mình trình bày các trang theo bố cục giống như trong giáo trình bài giảng thầy đã phát để bạn tiện tham khảo. Ở mỗi trang mình cũng ghi rõ số trang hay slide tương ứng với tài liệu. Ngoài ra còn một phần là phần phụ lục, các bạn có thể tham khảo thêm. Nó có nêu ra phương pháp giải và giải một số bài tập có trong sách, cũng như giải thích một số vấn đề các bạn hay thắc mắc khi gặp phải trong quá trình học. Mình đã cố ghắng dịch sát nghĩa nhất có thể nhưng do trình độ có hạn nhiều câu có thể không đúng thuật ngữ nên phải dịch lái đi hoặc đôi khi quá ghượng ép nên gây ra khó hiểu. Cuối cùng, do thời gian hoàn thành gấp rút và mình cũng chỉ là học sinh, nên nếu có điều gì đó không đúng khi dịch ra trong tài liệu này mong các bạn thông cảm. 3
Mục Lục Lecture 1 5 Lecture 2 43 Lesson 4 69 Lesson 5 99 Ph ụ L ụ c 119 4
LOGIC TRONG KHOA HỌC MÁY TÍNH LECTURE 1 (từ trang 6 đến trang 42) 5
Trang 6: logic Logic hình thức được xác định bởi những cú pháp và ngữ nghĩa của nó. Cú pháp:  Bảng chữ cái: là một tập các kí hiệu.  Một dãy hữu hạn của những kí hiệu này được gọi là một biểu thức.  Một tập các quy tắc thì xác định nên biểu thức xây dựng đúng. Ngữ nghĩa:  Đem đến nghĩa cho biểu thức xây dựng đúng.  Định nghĩa hình thức của quy nạp và đệ quy là cần phải có để cung cấp ngữ nghĩa một cách chính xác. 6
Trang 7: logic mệnh đề Logic mệnh đề đơn giản nhưng quan trọng tột cùng trong khoa học máy tính. 1. Nó là cơ sở cho những lí lẽ hàng ngày (trong lập trình, LSATs,..) 2. Nó là nguyên lí đằng sau những mạch số. 3. Một số vấn đề có thể được dịch sang logic mệnh đề 4. Nó là một phần quan trọng của những logic phức tạp hơn( cụ thể như logic bậc nhất cũng còn được gọi là logic vị từ). 7
Trang 8: logic mệnh đề: cú pháp Bảng chữ cái: ( Ngoặc trái Khởi đầu nhóm ) Ngoặc phải Kết thúc nhóm Kí hiệu phủ định Tiếng Việt : không  Kí hiệu phụ thuộc Tiếng Việt : và  Kí hiệu độc lập Tiếng Việt : hoặc  Kí hiệu điều kiện Tiếng Việt : kéo theo  Kí hiệu điều kiện 2 chiều Tiếng Việt : tương đương  A1 Kí hiệu mệnh đề 1 A2 Kí hiệu mệnh đề 2 …. An Kí hiệu mệnh đề n …. Chúng ta đang cho rằng bảng chữ cái là đếm được. Nhưng, hầu như mọi kết quả của chúng ta đều thỏa mãn rằng bảng chữ cái là tập không đếm được. 8
Trang 9: logic mệnh đề : cú pháp Bảng chữ cái:  Những kí hiệu liên từ mệnh đề:  , , ,  ,  .    Những kí hiệu logic:  , , ,  ,  ,(,).    Những tham số hay kí hiệu phi logic: A1, A2, A3,…. Nghĩa của những kí hiệu logic thường là duy nhất. Nhưng nghĩa của các kí hiệu phi logic thì phụ thuộc vào ngữ cảnh. 9
Trang 10: logic mệnh đề : cú pháp Một biểu thức là một dãy những kí hiệu. Một dãy được biểu thị chính xác bởi một danh sách các phần tử bị chia bởi những dấu phẩy bị đóng trong những dấu ngoặc nhọn. Ví dụ: (A1 A2)   ((  A1) A2)   )) )A5  Để cho tiện, ta sẽ viết những dãy này như một chuỗi của những kí hiệu đơn, với cách hiểu rằng hình thức cấu trúc đó đại diện chính xác cho một dãy gồm những kí hiệu trong chuỗi đó. Hình thức nghĩa trở nên quan trọng khi cố gắng chứng minh những vấn đề của những biểu thức. Chúng ta muốn giới hạn những biểu thức được chấp nhận. 10
Trang 11: logic mệnh đề : cú pháp Chúng ta xác định tập W các công thức xây dựng đúng (wff’s) như sau: (a) Mọi biểu thức gồm có một kí hiệu mệnh đề đơn là thuộc W. (b) Nếu α,β thuộc W, thì (  α), (α β), (α β), (α β), (α β) cũng vậy.     (c) Không biểu thức nào nữa thuộc W nếu không thoả mãn (a) hoặc (b). Định nghĩa này là quy nạp : tập được xác định bởi việc sử dụng như một phần của định nghĩa. Bạn sẽ sử dụng định nghĩa này để chứng minh rằng )) )A5 là không thuộc wff’s như thế  nào? Mục (c) quá mơ hồ cho mục đích của chúng ta. Có 2 cách để làm việc này một cách chính xác: top-down(trên xuống dưới) và bottom-up(dưới lên trên). Cả hai đều đòi hỏi hình thức định nghĩa quy nạp. 11
Trang 12: Quy nạp Giả sử chúng ta có một giả thiết P được xác định với những phần tử của n số tự nhiên. Ta muốn chứng minh rằng P thoả mãn với tất cả những số tự nhiên. Trường hợp cơ sở: Chứng minh P thoả mãn 0. Trường hợp quy nạp: Chứng minh với P thoả mãn n thì P thoả mãn n+1. 12
Trang 13: Ví dụ: n(n  1) n P(n) là giả thiết  i  2 i 0 0(0  1) 0 Trường hợp cơ sở:  i  2 i 0 k (k  1) k Trường hợp quy nạp: giả sử rằng P(k):  i  2 i 0 Thì k 1 k  i   i  (k  1) i 0 i 0 k ( k  1)   ( k  1) 2 k ( k  1)  2( k  1)  2 ( k  1)(k  2)  2 Từ P(0) thoả mãn và P(k) P(k+1), theo đó P(n) thoả mãn với tất cả các số tự nhiên n.  13
Trang 14: quy nạp Quy nạp toán học là một trường hợp đặc biệt của một nguyên lí tổng quat hơn. Trường hợp tổng quát, khi một tập được xác định một cách quy nạp, quy nạp có thể được sử dụng để chứng minh những vấn đề về những phần tử của tập đó. Định nghĩa quy nạp là cái gì? 14
Trang 15: quy nạp Cho U là tập vũ trụ nào đó, và giả sử chúng ta muốn xác định tập con C nào đó của tập U theo quy nạp. Việc này có thể được làm như sau:  B là tập con khởi đầu của U  F là một họ các hàm trên U Một cách tự nhiên, B là trường hợp cơ sở cho định nghĩa quy nạp của chúng ta. Những phần tử thuộc tập này là những phần tử để chúng ta bắt đầu với: tập F miêu tả cách để đạt được những phần tử mới từ những phần tử cũ. Tập C là tập của tất cả các phần tử hoặc là thuộc B hoặc có thể đạt được từ B sử dụng những hàm trong F. Ví dụ: Những số tự nhiên N có thể xác định như sau: Cho U là tập tất cả các số thực, B={0} và F={succ} với succ là hàm phần tử tiếp theo xác định succ(x)=x+1. 15
Trang 16: quy nạp Định nghĩa quy nạp tổng quát  U là một tập vũ trụ  B là một tập con khởi đầu của U  F là một họ các hàm trên U Làm thế nào chúng ta sử dụng các giả thiết này để đạt được tập C đề ra? Chúng ta có thể xác định tập C* là phiên bản top-down của tập C như sau:  Một tập S là đóng dưới họ hàm F khi và chỉ khi với mỗi f ∈F, nếu x1,…,xn∈ S và f(x1,…,xn)=y với y∈ U thì y∈ S.  Một tập S là quy nạp được nếu B⊆ S và S là đóng dưới họ hàm F.  Tập C* được xác định như là giao của tất cả các tập con quy nạp được của U. Tập này là top-down vì ta lấy những thứ rất lớn (những tập quy nạp được) và sử dụng giao của chúng để cấu trúc nên tập cần tìm. 16
Trang 17: Quy nạp Nhớ lại định nghĩa quy nạp của những số tự nhiên của chúng ta:  U=R với R là tập các số thực  B={0}  F={succ} với succ(x)=x+1 R là đóng dưới succ và cũng là quy nạp được vì 0∈ R Vậy thì sao với  Tập tất cả những số nguyên ?  Tập ,1,2,3,….- ?  Tập ,0.5,1.5,2.5,…- ? Không khó để thấy rằng N là tập nhỏ nhất đóng và quy nạp được. 17
Trang 18: Quy nạp Định nghĩa quy nạp tổng quát  U là một tập vũ trụ  B là một tập con khởi đầu của U  F là một họ các hàm trên U Chúng ta có thể xác định tập C*, phiên bản bottom-up của tập C như sau: Một dãy kiến trúc là một dãy hữu hạn các phần tử của U để với mỗi i
Trang 19: Quy nạp Ví dụ: Nhớ lại định nghĩa quy nạp của những số tự nhiên của chúng ta:  U=R với R là tập các số thực  B={0}  F={succ} với succ(x)=x+1 Những dãy kiến trúc của định nghĩa này là :     … Tập tất cả các phần tử cuối cùng trong các dãy kiến trúc đưa đến N. 19
Trang 20: Quy nạp Bạn có thể có nghi ngờ, với mọi các định nghĩa quy nạp, luôn luôn có trường hợp C*=C*. Chứng minh: C*⊂ C*: chúng ta chứng minh tập C* là tập quy nạp được. Rõ rang, B⊂ C* từ C1= B. Giả sử x1,…,xn∈ C* và f(x1,…,xn)=y với f∈ F. Thì ta có thể liên kết các dãy kiến trúc với mỗi xi và thêm y để đưa ra một dãy kiến trúc hợp lí có y. Vậy, C* là tập đóng dưới F và vậy C* là quy nạp được. Từ C* là giao của tất cả các tập quy nạp được, dẫn đến C*⊂ C*. C*⊂ C*: ta chứng minh rằng nếu là dãy kiến trúc nào đó thì xn∈ C*. Ta sử dụng thuyết quy nạp với n. Với trường hợp cơ sở, khi n=0, ta có x0∈ B nên dẫn đến x0∈ C*. Với trường hợp quy nạp, xem xét dãy . Ta biết rằng, f ( x j ,...., x j )  x với 0≤jk