Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng : Logic part 3

Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ

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 . .

TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.