tailieunhanh - 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. | 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ở Be 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 xr B xác định được cụ thể h x . Cho mỗi hàm f x0 . xn e F có một quy tắc tính toán hàm h f x0 . xn theo h x3 . 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 fe 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 xr B h x h x và -Với mỗi f Un U trong F và x1 . xn e C thì h f x1z. xn f h xj . h xn . .