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.
Nội dung trích xuất từ tài liệu:
Bài giảng : Logic part 3Trang 27: Đệ quyGiả 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ộthay 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 địnhbằ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). 27Trang 28: Đệ quyVí 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ộthà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. Xemxét định nghĩa tập quy nạp thêm hàm của N: U=R, B={0}, F={succ,mult} vớimult(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? 28Trang 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 Cphả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)). 29Trang 30: Đệ quyCho 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→VChứ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 hcủ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ấtNhữ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) 30Trang 31: Logic mệnh đề : ngữ nghĩaCho một wff α và một giá trị (có thể đúng hoặc sai) cho mỗi kí hiệu mệnh đề trong α, tacó 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ĩaquy 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ì? 31Trang 32: Logic mệnh đề: ngữ nghĩaThuyế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ấtcả 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ứngminh 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ôngthể 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. 32Trang 33: Logic mệnh đề: ngữ nghĩaChứ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ể đượcxem 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ự. ...