Bài giảng : Logic part 2

Chia sẻ: Ouiour Isihf | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST

Báo xấu

135
lượt xem 29
download

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

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ì?

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng : Logic part 2

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
Trang 21: Quy nạp Từ C*=C*, ta có thể gọi đơn giản là tập C. Chúng ta cũng coi nó như một tập sinh ra từ B bởi F. Từ đây, cho một tập có định nghĩa quy nạp, ta có thể chứng minh những vấn đề của nó bằng việc sử dụng nguyên lí sau: Nguyên lí quy nạp: Nếu C là tập sinh ra từ B bởi F và S là một tập bao gồm tập B và đóng dưới F (S là quy nạp được), thì C⊂ S. Chứng minh: Từ S là quy nạp được, và C=C* là giao của tất cả các tập quy nạp được, dẫn đến C⊂ S. Bây giờ ta có thể chứng minh quy nạp toán học là một trường hợp riêng của nguyên lí quy nạp. 21
Trang 22: Quy nạp Ví dụ: Xét lại lần nữa những số tự nhiên được xác định quy nạp như sau:  U=R với R là tập các số thực  B={0}  F={succ} với succ(x)=x+1 Cho N là tập sinh ra từ B bởi F. n(n  1) n i  Cho S là tập tất cả những số thực n thoả mãn . 2 i 0 Chúng ta đã sớm chứng minh được rằng 0∈ S và nếu k∈ S thì k+1∈ S. Nói cách khác, S là tập quy nạp được. Do đó, bằng nguyên lí quy nạp, N⊂ S. n(n  1) n Vậy,  i  với tất cả những số tự nhiên n. 2 i 0 22
Trang 23: Logic mệnh đề: biểu thức xây dựng đúng Chúng ta bây giờ có thể sử dụng hình thức định nghĩa quy nạp để xác định tập các công thức xây dựng đúng trong logic mệnh đề.  U= tập tất cả các biểu thức  B= tập những biểu thức gồm các kí hiệu mệnh đề đơn.  F= tập các công thức xây dựng biểu thức: -ℰ˥ (α)=(˥α) -ℰ∧(α,β)=(α∧β) -ℰ∨(α,β)=(α∨β) -ℰ→(α,β)=(α→β) -ℰ↔(α,β)=(α↔ β) 23
Trang 24: Logic mệnh đề: WFF’S Từ định nghĩa quy nạp của wff’s, ta có thể sử dụng nguyên lí quy nạp để chứng minh những vấn đề của tập W các công thức wff’s. Ví dụ: Chứng minh rằng mọi wff có cùng số ngoặc trái và số ngoặc phải. Chứng minh: Cho l(α) là số ngoặc trái và r(α) là số ngoặc phải của một biểu thức α. Cho S là tập tất cả các công thức α sao cho l(α)=r(α). Chúng ta sẽ chứng minh rằng W⊂ S. Điều này dẫn đến từ nguyên lí quy nạp nếu ta có thể chứng minh được S là tập quy nạp được. Trường hợp cơ sở: Chúng ta phải chứng minh B⊂ S. Nhớ lại rằng B là tập bao gồm những kí hiệu mệnh đề đơn. Nên rõ ràng rằng với những biểu thức như thế: l(α)=r(α)=0 24
Trang 25: Logic mệnh đề: WFF’S Trường hợp quy nạp: Chúng ta phải chứng minh rằng S là đóng dưới mỗi công thức xây dựng nên biểu thức trong F.  ℰ˥: Giả sử α∈ S. Ta biết rằng ℰ  (α)=(  α). Dẫn đến l(ℰ  (α))=1 + l(α) và r(ℰ  (α))=1+r(α). Nhưng bởi vì α∈S , ta có l(α)=r(α), nên dẫn đến l(ℰ  (α))= r(ℰ  (α)) và vì vậy, ℰ  (α)∈ S.  ℰ∧: Giả sử α,β∈ S. Ta biết rằng ℰ∧(α,β)=(α∧β). Vậy l(ℰ∧(α,β))=1+l(α)+l(β) và r(ℰ∧(α,β))= 1+r(α)+r(β). Vì điều kiện trước đó, dẫn đến từ giả thiết quy nạp có ℰ∧(α,β)∈ S. Các hàm với ℰ∨, ℰ→, ℰ↔ tương tự với trường hợp ℰ∧.  Từ S bao gồm B và đóng dưới các biểu thức trong F, nên nó quy nạp được. Dẫn đến bởi nguyên lí quy nạp W⊂ S. 25
Trang 26: logic mệnh đề: wff Bây giờ ta có thể quay lại câu hỏi bằng cách nào chứng minh một biểu thức không là một wff. Ta biết công thức )) )A5 không là một wff bằng cách nào?  Nó không có cùng số ngoặc trái và ngoặc phải. Dẫn đến từ định lí ta đã vừa mới chứng minh rằng )) )A5 không là một wff.  26