Bài giảng : Logic part 3

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

Thêm vào BST

Báo xấu

141
lượt xem 21
download

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

Trang 27: Đệ quy Giả sử ta muốn xác định một hàm có miền xác định là tập được xác định bằng quy nạp. Một cách tự nhiên để làm việc này là sử dụng đệ quy. Cho một định nghĩa quy nạp với tập vũ trụ U, tập cơ sở B⊂ U, và một họ hàm F có một hay nhiều ngôi từ U và qua nó trả lại một phần tử của U.

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 3

Trang 27: Đệ quy Giả sử ta muốn xác định một hàm có miền xác định là tập được xác định bằng quy nạp. Một cách tự nhiên để làm việc này là sử dụng đệ quy. Cho một định nghĩa quy nạp với tập vũ trụ U, tập cơ sở B⊂ U, và một họ hàm F có một hay nhiều ngôi từ U và qua nó trả lại một phần tử của U. Cho C là tập được xác định bằng định nghĩa quy nạp này. Bây giờ ta muốn xác định một hàm h có miền xác định là C. Ta có thể làm việc này như sau:  Cho mỗi x∈ B, xác định được cụ thể h(x).  Cho mỗi hàm f(x0,…,xn)⊂ F, có một quy tắc tính toán hàm h(f(x0,…,xn)) theo h(x0),…,h(xn). 27
Trang 28: Đệ quy Ví dụ: Nhớ lại công thức quy nạp của N: U=R, B={0}, F={succ}. Giả sử ta muốn xác định một hàm giai thừa fact(). Ta có thể xác định như sau:  Fact(0)=1;  Fact(succ(n))=(n+1)fact(n) Tuy nhiên, một định nghĩa đệ quy như vậy không đảm bảo sự tồn tại của một hàm. Xem xét định nghĩa tập quy nạp thêm hàm của N: U=R, B={0}, F={succ,mult} với mult(x,y)=x*y. Bây giờ ta xác định hàm h như sau:  h(0)=1;  h(succ(n))=h(n)+2;  h(mult(m,n))=h(m)*h(n) h(1) bằng bao nhiêu? Ta có thể chắc chắn rằng định nghĩa đệ quy trện là xác định đúng bằng cách nào? 28
Trang 29: Đệ quy Để đảm bảo định nghĩa đệ quy được xây dựng đúng, một định nghĩa quy nạp của tập C phải thoả mãn thêm những yêu cầu:  Giới hạn của mỗi hàm f∈ F đến C phải là tương ứng 1-1.  Phạm vi của giới hạn của mỗi hàm trong F phải là rời với tất cả phạm vi giới hạn của các hàm khác trong F và từ B. Nếu gặp các điều kiện này, ta nói C được sinh ra một cách tự do trừ B bởi F. Định lí đệ quy: Giả sử C là sinh ra tự do từ B bởi F. Cũng giả sử V là một tập và h là một hàm từ B →V. Giả sử tổng quát hơn với mỗi hàm f: Un→U trong F, có tương ứng một hàm f :Vn→V. Thì tồn tại duy nhất một hàm h : C→V để: -Với x∈ B, h (x)=h(x) và -Với mỗi f: Un→U trong F và x1,…,xn∈ C thì h (f(x1,…,xn))= f ( h (x1),…, h (xn)). 29
Trang 30: Đệ quy Cho C là tập sinh ra tự do từ B bởi F, Chứng minh rằng: h: B→V và f :Vn→V với mỗi f: Un→U trong F xác định một hàm duy nhất h : C→V Chứng minh vắn tắt: Một hàm g: D→E được gọi là chấp nhận được nếu D⊂ C, E⊂ V và  mỗi x∈ B∩D, g(x)=h(x)  với mỗi f : Un→U trong F và x1,…,xn∈ C, nếu f(x1,…,xn)∈ D thì g(f(x1,…,xn))= f (g(x1),…, g(xn)) Cho K là tập tất cả các hàm chấp nhận được, và là giao của K. Thì thoả các yêu cầu h h của chúng ta. Đặc biêt:  h là một hàm  h là một hàm chấp nhận được  Miền xác định của h là cả tập C  h là duy nhất Những chi tiết đã lược bỏ( yêu cầu chứng minh lại sử dụng nguyên lí quy nạp) 30
Trang 31: Logic mệnh đề : ngữ nghĩa Cho một wff α và một giá trị (có thể đúng hoặc sai) cho mỗi kí hiệu mệnh đề trong α, ta có thể xác định giá trị của α. Ta làm chính xác việc này bằng cách nào? Cho v là một hàm từ B vào {0,1}, với 0 miêu tả sai và 1 miêu tả đúng. Nhớ lại định nghĩa quy nạp của wff’s, B chứa những kí hiệu mệnh đề. Bây giờ, ta xác định v là một hàm từ W vào {0,1} như sau:  Với mỗi kí hiệu mệnh đề Ai, v (Ai)=v(Ai)  v ( ℰ  (α))=1- v (α)  v ( ℰ (α,β))=min( v (α), v (β)) ∧  v ( ℰ (α,β))=max( v (α), v (β)) ∨  v ( ℰ→(α,β))=max(1- v (α), v (β))  v ( ℰ↔(α,β))=1-| v (α)- v (β)| Nguyên lí đệ quy bảo đảm rằng v là xác định đúng… dưới những điều kiện gì? 31
Trang 32: Logic mệnh đề: ngữ nghĩa Thuyết đọc được duy nhất: Từ định nghĩa quy nạp của tập W các công thức của chúng ta, W là sinh ra tự do bởi F. Đặc biệt, giới hạn của mỗi hàm F đến W phải là tương ứng 1-1 và có phạm vi rời với tất cả phạm vi giới hạn của các hàm khác trong F và từ B. Đầu tiêu ta cần bổ đề sau. Bổ đề Mọi dãy khởi đầu thực sự của một wff chứa một số ngoặc vượt quá, và dẫn đến nó không là wff. Chứng minh: Cho S là tập các công thức xây dựng đúng thoả mãn giả thiết trên. Chúng ta sẽ chứng minh rằng S là quy nạp được. Đầu tiên chú ý rằng những phần tử của tập B gồm tất cả kí hiệu mệnh đề đơn nên không thể có khả năng có cấu trúc của những dãy khởi đầu thực sự từ những phần tử này. Vậy, B⊂ S. 32
Trang 33: Logic mệnh đề: ngữ nghĩa Chứng minh tiếp tục: Để CM: S đóng trên ℰ∧, giả sử rằng α, β∈ S và xem xét dãy khởi đầu thực sự của ℰ∧(α,β). Có 6 khả năng sau: ( (α0 , với α0 là dãy khởi đầu thực sự của α (α (α∧ (α∧β0, với β0 là dãy khởi đầu thực sự của β (α∧β Bằng việc sử dụng giả thiết quy nạp và thực sự rằng (đã chứng minh trước đó) tất cả wff’s có cùng số ngoặc trái và ngoặc phải, mỗi trong những trường hợp nay có thể được xem như có ngoặc trái nhiều hơn ngoặc phải. Vậy, ℰ∧(α,β)∈ S. Những trường hợp với ℰ  , ℰ∨, ℰ→ và ℰ↔ là tương tự. 33
Trang 34: Logic mệnh đề: ngữ nghĩa Thuyết đọc được duy nhất: Từ định nghĩa quy nạp của tập W các công thức wff của chúng ta, W là sinh ra tự do bởi F. Đặc biệt, giới hạn của mỗi hàm F đến W phải là tương ứng 1-1 và có phạm vi rời với tất cả phạm vi giới hạn của các hàm khác trong F và từ B. Chứng minh: Để chứng minh biểu thức ℰ∧ giới hạn đến W là 1-1, giả sử rằng (α∧β)=(µ∧ℴ) với α,β,µ và ℴ là những wff. Từ việc cả 2 đều bắt đầu bằng ngoặc trái, dẫn đến α∧β)=µ∧ℴ). Từ α và µ là những wff, bổ đề trước dẫn đến rằng không thể hoặc một trong trong hai là tiền tố của cái còn lại, và vậy thì α=µ. Với đối số đi cùng còn lại thì cũng chứng minh rằng β=ℴ. Những đối số khác tương tự có thể được áp dụng để chứng minh rằng các hàm khác là 1-1 và phạm vi của chúng là rời nhau. 34
Trang 35: Một thuật toán để kiểm tra wff’s Bổ đề Cho α là một wff. Thì chính xác 1 trong các điều sau đúng:  α là một kí hiệu mệnh đề đơn  α=(  β) với β là một wff  α=(µ⊕β) với ⊕ là một trong { , ,  ,  -, β là dãy khởi đầu cân bằng ngoặc đầu tiên   của việc bỏ dấu ngoặc ( từ α và µ, β là wff. Chứng minh bổ đề như là một bài tập. 35
Trang 36: Một thuật toán kiểm tra wff Đại lượng vào: biểu thức α Đại lượng ra: đúng hoặc sai (chỉ việc α là wff hay không) 0.Bắt đầu với kiến trúc cây khởi đầu T chứa gốc đơn dán nhãn là α. 1.Nếu tất cả các lá của T được dán nhãn với kí hiệu mệnh đề, trả về giá trị đúng. 2.Lựa chọn một lá dán nhãn với một biểu thức α1 với α1 không phải kí hiệu mệnh đề. 3.Nếu α1 không bắt đầu với “(“ trả về giá trị sai. 4.Kiểm tra α1 để tìm β là dãy khởi đầu thực sự cân bằng ngoặc đầu tiên của α1. Nếu không có β thoả mãn, trả về giá trị sai. 5.Nếu α1=(  β), thì thêm một lá con của lá được dán nhãn α1, dán nhãn cho nó là β và nhảy về bước 1. 6.Nếu α1=(β⊕µ) với ⊕ là một trong { , ,  ,  } và β là cân bằng ngoặc, thì thêm 2 lá con   của lá được dán nhãn α1, dán nhãn cho chúng là β và µ, và nhảy về bước 1. 7.Trả về giá trị sai. 36
Trang 37: một thuật toán kiểm tra wff Tính kết thúc: Ta chứng minh tính kết thúc của thuật toán này thế nào? Ta có thể chứng minh rằng tổng của độ dài của tất cả các biểu thức dán nhãn ở lá sẽ giảm dần với mỗi vòng lặp. Tính đúng: Nếu thuật toán trả về đúng với đại lượng vào α, thì α là một wff. Chứng minh bằng quy nạp trên cây T sinh ra bởi thuật toán từ lá lên đến rễ. Tính đầy đủ: Nếu α là một wff, thì thuật toán sẽ trả lại giá trị đúng. Chứng minh việc này sử dụng nguyên lí quy nạp với tập các wff. 37
Trang 38: Kí hiệu tiện lợi Kí hiệu mệnh đề đa dạng hơn: A,B,C,p,q,…. Ngoặc ở phía ngoài có thể lược bớt đi: A∧B thay vì (A∧B) Kí hiệu phủ định được ưu tiên hơn liên từ hai ngôi:  A∧B nghĩa là ((  A)∧B) {∧,∨- ưu tiên hơn ,→,↔}: A∧B→  C∧D là (A∧B)→((  C)∧D) Khi một kí hiệu được sử dụng lặp lại, nhóm nó lại như sau: A∧B∧C là ((A∧B)∧C) Chú ý tiện lợi đó chỉ làm rõ ràng cho wff, không phải với tất cả biểu thức. 38
Trang 39: Logic mệnh đề: ngữ nghĩa Tập công thức xây dựng đúng W: U= tất cả các biểu thức B={A1,A2,A3,…- F={ ℰ  , ℰ∧,ℰ∨,ℰ→,ℰ↔} Cho phép gán v: B→{0,1} với các kí hiệu mệnh đề, ta có thể xây dựng một hàm v cho các công thức trong W như sau:  Với mỗi kí hiệu mệnh đề Ai, v (Ai)=v(Ai)  v ( ℰ  (α))=1- v (α)  v ( ℰ (α,β))=min( v (α), v (β)) ∧  v ( ℰ (α,β))=max( v (α), v (β)) ∨  v ( ℰ (α,β))=max(1- v (α), v (β)) →  v ( ℰ↔(α,β))=1-| v (α)- v (β)| Định lí đệ quy và thuyết đọc được duy nhất đảm bảo rằng v là xác định đúng. 39